Permutación de inversión de bits

Permutación que invierte los números binarios

Un conjunto de Hammersley cuyas coordenadas son los números enteros de 0 a 255 y sus inversiones de bits.

En matemáticas aplicadas, una permutación de inversión de bits es una permutación de una secuencia de elementos, donde es una potencia de dos . Se define indexando los elementos de la secuencia por los números de a , representando cada uno de estos números por su representación binaria (rellenada para que tenga una longitud exactamente ) y asignando cada elemento al elemento cuya representación tiene los mismos bits en el orden inverso. ${\displaystyle n}$ ${\displaystyle n=2^{k}}$ ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle k}$

Repetir la misma permutación dos veces vuelve al orden original de los elementos, por lo que la permutación de inversión de bits es una involución .

Esta permutación se puede aplicar a cualquier secuencia en tiempo lineal , realizando únicamente cálculos de índices simples. Tiene aplicaciones en la generación de secuencias de baja discrepancia y en la evaluación de transformadas rápidas de Fourier .

Ejemplo

Considere la secuencia de ocho letras abcdefgh . Sus índices son los números binarios 000, 001, 010, 011, 100, 101, 110 y 111, que al invertirse se convierten en 000, 100, 010, 110, 001, 101, 011 y 111. Por lo tanto, la letra a en la posición 000 se asigna a la misma posición (000), la letra b en la posición 001 se asigna a la quinta posición (la numerada 100), etc., dando la nueva secuencia aecgbfdh . Repitiendo la misma permutación en esta nueva secuencia se regresa a la secuencia inicial.

Escribiendo los números de índice en decimal (pero, como arriba, comenzando con la posición 0 en lugar del inicio más convencional de 1 para una permutación), las permutaciones de inversión de bits en los elementos, para , son: ^[1] ${\displaystyle n=2^{k}}$ ${\displaystyle k=0,1,2,3,\dots }$

Cada permutación de esta secuencia puede generarse concatenando dos secuencias de números: la permutación anterior, con sus valores duplicados, y la misma secuencia con cada valor aumentado en uno. Así, por ejemplo, al duplicar la permutación de longitud 4 0 2 1 3 se obtiene 0 4 2 6 , al sumar uno se obtiene 1 5 3 7 , y al concatenar estas dos secuencias se obtiene la permutación de longitud 8 0 4 2 6 1 5 3 7 . ^[2]

Generalizaciones

La generalización a las representaciones de base , para , y para , es una permutación de inversión de dígitos , en la que los dígitos base del índice de cada elemento se invierten para obtener el índice permutado. La misma idea también se puede generalizar a los sistemas numéricos de base mixta . En tales casos, la permutación de inversión de dígitos debe invertir simultáneamente los dígitos de cada elemento y las bases del sistema numérico, de modo que cada dígito invertido permanezca dentro del rango definido por su base. ^[3] ${\displaystyle b}$ ${\displaystyle b>2}$ ${\displaystyle n=b^{k}}$ ${\displaystyle b}$

Las permutaciones que generalizan la permutación de inversión de bits invirtiendo bloques contiguos de bits dentro de las representaciones binarias de sus índices se pueden utilizar para intercalar dos secuencias de datos de igual longitud en el lugar. ^[4]

Existen dos extensiones de la permutación de inversión de bits para secuencias de longitud arbitraria. Estas extensiones coinciden con la inversión de bits para secuencias cuya longitud es una potencia de 2, y su propósito es separar elementos adyacentes en una secuencia para el funcionamiento eficiente del algoritmo de Kaczmarz . La primera de estas extensiones, llamada ordenación eficiente , ^[5] opera sobre números compuestos, y se basa en la descomposición del número en sus componentes primos.

La segunda extensión, llamada EBR (extended bit-reversal), es similar en espíritu a la inversión de bits. Dada una matriz de tamaño , EBR llena la matriz con una permutación de los números en el rango en tiempo lineal. Los números sucesivos están separados en la permutación por al menos posiciones. ^[6] ${\displaystyle n}$ ${\displaystyle 0\ldots n-1}$ ${\displaystyle \lfloor n/4\rfloor }$

Aplicaciones

La inversión de bits es más importante para los algoritmos de FFT de Cooley-Tukey de base 2 , donde las etapas recursivas del algoritmo, que operan en el lugar , implican una inversión de bits de las entradas o salidas. De manera similar, las inversiones de dígitos de base mixta surgen en las FFT de Cooley-Tukey de base mixta. ^[7]

La permutación de inversión de bits también se ha utilizado para diseñar límites inferiores en la computación distribuida. ^[8]

La secuencia de Van der Corput , una secuencia de números de baja discrepancia en el intervalo unitario , se forma reinterpretando los índices de la permutación de inversión de bits como representaciones binarias de punto fijo de números racionales diádicos .

Las permutaciones de inversión de bits se utilizan a menudo para encontrar límites inferiores en estructuras de datos dinámicas . Por ejemplo, sujeto a ciertas suposiciones, el costo de buscar los números enteros entre y , inclusive, en cualquier árbol de búsqueda binario que contenga esos valores, es cuando esos números se consultan en orden de bits invertido. Este límite se aplica incluso a árboles como los árboles splay a los que se les permite reorganizar sus nodos entre accesos. ^[9] ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle \Omega (n\log n)}$

Algoritmos

Debido principalmente a la importancia de los algoritmos de transformada rápida de Fourier , se han ideado numerosos algoritmos eficientes para aplicar una permutación de inversión de bits a una secuencia. ^[2]

Debido a que la permutación de inversión de bits es una involución, se puede realizar fácilmente en el lugar (sin copiar los datos en otra matriz) intercambiando pares de elementos. En la máquina de acceso aleatorio que se usa comúnmente en el análisis de algoritmos, un algoritmo simple que escanea los índices en el orden de entrada e intercambia cada vez que el escaneo encuentra un índice cuya inversión es un número mayor realizaría un número lineal de movimientos de datos. ^[10] Sin embargo, calcular la inversión de cada índice puede requerir un número no constante de pasos. Los algoritmos alternativos pueden realizar una permutación de inversión de bits en tiempo lineal mientras usan solo cálculos de índice simples. ^[11] Debido a que las permutaciones de inversión de bits pueden repetirse varias veces como parte de un cálculo, puede ser útil separar los pasos del algoritmo que calculan los datos de índice utilizados para representar la permutación (por ejemplo, utilizando el método de duplicación y concatenación) de los pasos que utilizan los resultados de este cálculo para permutar los datos (por ejemplo, escaneando los índices de datos en orden y realizando un intercambio siempre que la ubicación intercambiada sea mayor que el índice actual, o utilizando operaciones de dispersión-reunión de vectores más sofisticadas ). ^[2]

Otra consideración que es aún más importante para el desempeño de estos algoritmos es el efecto de la jerarquía de memoria en el tiempo de ejecución. Debido a este efecto, los algoritmos más sofisticados que consideran la estructura de bloques de la memoria pueden ser más rápidos que este escaneo ingenuo. ^{[2] [10]} Una alternativa a estas técnicas es un hardware informático especial que permite acceder a la memoria tanto en orden normal como en orden inverso de bits. ^[12]

En los campos de la computación de alto rendimiento se ha prestado mucha atención a la mejora del rendimiento de las inversiones de bits tanto en procesadores monoprocesadores como multiprocesadores, ya que el desarrollo de algoritmos que tienen en cuenta la arquitectura puede aprovechar al máximo los recursos de hardware y software del sistema, incluidos los cachés, TLB y núcleos múltiples, acelerando significativamente el cálculo. ^[13]

Referencias

1. Sloane, N. J. A. (ed.), "Secuencia A030109", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
2. Karp, Alan H. (1996), "Inversión de bits en procesadores monoprocesadores", SIAM Review , 38 (1): 1–26, CiteSeerX 10.1.1.24.2913 , doi :10.1137/1038001, MR  1379039 Karp examina y compara 30 algoritmos diferentes para la inversión de bits, desarrollados entre 1965 y la publicación de su estudio en 1996.
3. Elster, Anne C. (1989), "Algoritmos de inversión rápida de bits", IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '89, Glasgow, Escocia, 23-26 de mayo de 1989 , págs. 1099-1102, doi :10.1109/ICASSP.1989.266624, S2CID  15028026
4. Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), "Permutación in situ y mezcla perfecta mediante involuciones", Information Processing Letters , 113 (10–11): 386–391, arXiv : 1204.1958 , doi :10.1016/j.ipl.2013.02.017, MR  3037467, S2CID  14672841.
5. Herman, Gabor T. (2009), Fundamentos de la tomografía computarizada (2.ª ed.), Londres: Springer, pág. 209, ISBN 978-1-85233-617-2
6. Gordon, Dan (junio de 2017), "Un enfoque de desaleatorización para recuperar señales de banda limitada en una amplia gama de frecuencias de muestreo aleatorias", Numerical Algorithms , 77 (4): 1141–1157, doi :10.1007/s11075-017-0356-3, S2CID  254889989
7. B. Gold y CM Rader, Procesamiento digital de señales (Nueva York: McGraw–Hill, 1969).
8. Frederickson, Greg N.; Lynch, Nancy A. (1984), "El impacto de la comunicación sincrónica en el problema de elegir un líder en un anillo" (PDF) , Actas del decimosexto simposio anual de la ACM sobre teoría de la computación (STOC '84) , págs. 493–503, doi : 10.1145/800057.808719 , ISBN 978-0897911337.
9. Wilber, Robert (1989), "Límites inferiores para acceder a árboles de búsqueda binaria con rotaciones", 27.º Simposio anual sobre fundamentos de la informática (sfcs 1986) , págs. 61-70, doi :10.1109/SFCS.1986.28, ISBN 0-8186-0740-8.
10. Carter, Larry; Gatlin, Kang Su (1998), "Hacia un programa óptimo de permutación de inversión de bits", Actas del 39.º Simposio anual sobre fundamentos de la informática (FOCS) , págs. 544-553, CiteSeerX 10.1.1.46.9319 , doi :10.1109/SFCS.1998.743505, ISBN  978-0-8186-9172-0, Número de identificación del sujeto  14307262.
11. Jeong, Jechang; Williams, WJ (1990), "Un algoritmo recursivo rápido de inversión de bits", Conferencia internacional sobre acústica, habla y procesamiento de señales (ICASSP-90) , vol. 3, págs. 1511-1514, doi :10.1109/ICASSP.1990.115695, S2CID  122373780.
12. Harley, TR; Maheshwaramurthy, GP (2004), "Generadores de direcciones para mapear matrices en orden inverso de bits", IEEE Transactions on Signal Processing , 52 (6): 1693–1703, doi :10.1109/TSP.2004.827148, S2CID  10043478.
13. Zhang, Zhao; Zhang, Xiaodong (2000), "Inversiones rápidas de bits en uniprocesadores y multiprocesadores de memoria compartida", SIAM Journal on Scientific Computing , 22 (6): 2113–2134, doi :10.1137/S1064827599359709, MR  1856305