Reproducción aleatoria de bits invertida en una matriz

Question

Para una función FFT, debo permutar o mezclar los elementos dentro de una matriz de forma invertida. Esa es una tarea común con las FFT porque la mayoría de las funciones de FFT de dos tamaños o bien esperan o devuelven sus datos de una manera invertida.

E.g. Supongo que la matriz tiene 256 elementos. Me gustaría intercambiar cada elemento con su patrón de bit invertido. Aquí hay dos ejemplos (en binario):

Element 00000001b should be swapped with element 10000000b 
Element 00010111b should be swapped with element 11101000b 

y así sucesivamente.

¿Alguna idea de cómo hacer esto rápido y más importante: en el lugar?

Ya tengo una función que hace este intercambio. No es difícil escribir uno. Como esta es una operación tan común en DSP, tengo la sensación de que hay formas más ingeniosas de hacerlo que mi bucle muy ingenuo.

El idioma en cuestión es C, pero cualquier idioma está bien.

Answer 1

Para intercambiar en su lugar con una sola pasada, itere una vez a través de todos los elementos para aumentar el índice. Realice un intercambio solo si el índice es menor que el índice invertido; esto saltará el problema de doble intercambio y también los casos de palindrome (elementos 00000000b, 10000001b, 10100101b) que son inversos al mismo valor y no se requiere un intercambio.

// Let data[256] be your element array 
for (i=0; i<256; i++) 
    j = bit_reverse(i); 
    if (i < j) 
    { 
     swap(data[i],data[j]); 
    } 

El bit_reverse() puede estar utilizando el truco de las operaciones de bits de Nathaneil. El bit_reverse() se llamará 256 veces pero el swap() se llamará menos de 128 veces.

Answer 2

El uso de una tabla de búsqueda preconstruida para hacer la asignación parece ser la solución obvia. Supongo que depende de cuán grandes sean las matrices con las que tratarás. Pero incluso si un mapeo directo no es posible, aún así iría a buscar una tabla, tal vez de patrones de tamaño byte que puede usar para construir el patrón de tamaño de palabra para el índice final.

Answer 3

Una forma rápida de hacerlo es cambiar cada bit adyacente sola, entonces los campos de 2 bits, etc. La forma más rápida de hacerlo es:

x = (x & 0x55) << 1 | (x & 0xAA) >> 1; //swaps bits 
x = (x & 0x33) << 2 | (x & 0xCC) >> 2; //swapss 2-bit fields 
x = (x & 0x0F) << 4 | (x & 0xF0) >> 4; 

Aunque difícil de leer, si esto es algo que debe optimizarse, puede querer hacerlo de esta manera.

Answer 4

Elemento 00000001b debe ser intercambiado con el elemento 10000000b

Creo que quieres decir "Elemento 00000001b debe ser intercambiado con el elemento 11111110b" en la primera línea? En lugar de activar 256 bytes, puede convertir el conjunto a (largo largo *) e intercambiar valores de 32 "largos", que deberían ser mucho más rápidos en máquinas de 64 bits (o 64 valores largos en un equipo de 32 bits))

En segundo lugar, si recorre ingeniosamente la matriz e intercambia todos los valores con su complemento, intercambiará todos los elementos dos veces, por lo que no ha hecho nada :-) Primero debe identificar cuáles son los complementos y dejarlos fuera de tu circuito.

Answer 5

Este código usa una tabla de búsqueda para revertir los números de 64 bits muy rápidamente. Para su ejemplo de lenguaje C, también incluí versiones para números de 32, 16 y 8 bits (se supone que int es de 32 bits). En un lenguaje orientado a objetos (C++, C#, etc.), acababa de sobrecargar la función.

No tengo un C-compiler a la mano, así que, afortunadamente, no me perdí nada.

unsigned char ReverseBits[] = 
{ 
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 
    0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 
    0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 
    0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 
    0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 
    0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 
    0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 
    0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 
    0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 
    0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 
    0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 
    0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 
    0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 
    0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 
    0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 
    0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF 
}; 


unsigned long Reverse64Bits(unsigned long number) 
{  
    unsigned long result; 

    result = 
     (ReverseBits[ number  & 0xff] << 56) | 
     (ReverseBits[(number >> 8) & 0xff] << 48) | 
     (ReverseBits[(number >> 16) & 0xff] << 40) | 
     (ReverseBits[(number >> 24) & 0xff] << 32) | 
     (ReverseBits[(number >> 32) & 0xff] << 24) | 
     (ReverseBits[(number >> 40) & 0xff] << 16) | 
     (ReverseBits[(number >> 48) & 0xff] << 8) | 
     (ReverseBits[(number >> 56) & 0xff]); 

    return result; 
} 

unsigned int Reverse32Bits(unsigned int number) 
{ 
    unsigned int result; 

    result = 
     (ReverseBits[ number  & 0xff] << 24) | 
     (ReverseBits[(number >> 8) & 0xff] << 16) | 
     (ReverseBits[(number >> 16) & 0xff] << 8) | 
     (ReverseBits[(number >> 24) & 0xff]); 

    return result; 
} 

unsigned short Reverse16Bits(unsigned short number) 
{ 
    unsigned short result; 

    result = 
     (ReverseBits[ number  & 0xff] << 8) | 
     (ReverseBits[(number >> 8) & 0xff]); 

    return result; 
} 

unsigned char Reverse8Bits(unsigned char number) 
{ 
    unsigned char result; 

    result = (ReverseBits[number]); 

    return result; 
} 

disfrutar,

Robert C.Cartaino

Answer 6

Si piensa en lo que está sucediendo con el índice de bits intercambiados, se contará de la misma manera que el índice sin bits se cuenta, solo con los bits en el orden inverso al recuento convencional.

En lugar de puntear el índice cada vez que pasa por el ciclo, puede implementar manualmente un equivalente '++' que utiliza bits en el orden incorrecto para hacer un ciclo indexado doblemente. Comprobé que gcc en O3 detalla la función de incremento, pero si es más rápido, entonces, al buscar el número cada vez que se realiza una búsqueda, es para que el perfilador lo diga.

Aquí hay un programa de prueba ilustrativo.

#include <stdio.h> 

void RevBitIncr(int *n, int bit) 
{ 
    do 
    { 
     bit >>= 1; 
     *n ^= bit; 
    } while((*n & bit) == 0 && bit != 1); 
} 

int main(void) 
{ 
    int max = 0x100; 
    int i, j; 

    for(i = 0, j = 0; i != max; ++i, RevBitIncr(&j, max)) 
    { 
     if(i < j) 
      printf("%02x <-> %02x\n", i, j); 
    } 

    return 0; 
} 

Answer 7

El siguiente enfoque calcula el siguiente índice invertido en bits del anterior como en la respuesta de Charles Bailey, pero de una manera más optimizada. Tenga en cuenta que al incrementar un número simplemente se voltea una secuencia de bits menos significativos, por ejemplo desde 0111 hasta 1000. Entonces, para calcular el siguiente índice invertido en bits, debes voltear una secuencia de bits más significativos. Si su plataforma objetivo tiene una instrucción CTZ ("recuento de ceros finales"), esto puede hacerse de manera eficiente.

Ejemplo usando GCC __builtin_ctz:

void brswap(double *a, unsigned n) { 
    unsigned bits = __builtin_ctz(n); 

    for (unsigned i = 0, j = 0; i < n; i++) { 
     if (i < j) { 
      double tmp = a[i]; 
      a[i] = a[j]; 
      a[j] = tmp; 
     } 

     // Compute a mask of LSBs. 
     unsigned mask = i^(i + 1); 
     // Length of the mask. 
     unsigned len = __builtin_ctz(i + 1) + 1; 
     // Align the mask to MSB of n. 
     mask <<= bits - len; 
     j ^= mask; 
    } 
} 

Sin una instrucción CTZ, también puede utilizar la división entera:

void brswap(double *a, unsigned n) { 
    for (unsigned i = 0, j = 0; i < n; i++) { 
     if (i < j) { 
      double tmp = a[i]; 
      a[i] = a[j]; 
      a[j] = tmp; 
     } 

     // Find least significant zero bit. 
     unsigned bit = ~i & (i + 1); 
     // Using division to bit-reverse a single bit. 
     unsigned rev = (n/2)/bit; 
     // XOR with mask. 
     j ^= (n - 1) & ~(rev - 1); 
    } 
}