Permutación de inversión de bits

Permutación que invierte números binarios

Un conjunto de Hammersley cuyas coordenadas son los números enteros del 0 al 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 desde hasta , representando cada uno de estos números mediante su representación binaria (rellenada para tener una longitud exacta ) 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 mientras se realizan únicamente cálculos de índice 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. Así, 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 que está numerada 100), etc., dando la nueva secuencia aecgbfdh . Repetir la misma permutación en esta nueva secuencia regresa a la secuencia inicial.

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

Cada permutación en esta secuencia se puede generar 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, duplicar la permutación de longitud 4 0 2 1 3 da 0 4 2 6 , sumar uno da 1 5 3 7 y concatenar estas dos secuencias da la permutación de longitud 8 0 4 2 6 1 5 3 7 . ^[2]

Generalizaciones

La generalización a representaciones de base , para y para , es una permutación de inversión de dígitos , en la que los dígitos de 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]

Hay dos extensiones de la permutación de inversión de bits a 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, denominada ordenamiento eficiente , ^[5] opera sobre números compuestos, y se basa en descomponer el número en sus componentes primos.

La segunda extensión, llamada EBR (inversión de bits extendida), 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 FFT Cooley-Tukey radix-2 , donde las etapas recursivas del algoritmo, que operan in situ , 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 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 inverso de bits. Este límite se aplica incluso a árboles como los árboles extendidos a los que se les permite reorganizar sus nodos entre accesos. ^[9] ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle \Omega (n\log n)}$

Algoritmos

Principalmente debido 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 comúnmente utilizada en el análisis de algoritmos, un algoritmo simple que escanea los índices en el orden de entrada y los 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 de pasos no constante. Los algoritmos alternativos pueden realizar una permutación de inversión de bits en tiempo lineal utilizando únicamente 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 resultar útil separar los pasos del algoritmo que calcula los datos de índice utilizados para representar la permutación (por ejemplo, utilizando la duplicación y la concatenación). método) 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 usando una dispersión vectorial más sofisticada). operaciones de recolección ). ^[2]

Otra consideración que es aún más importante para el rendimiento de estos algoritmos es el efecto de la jerarquía de memoria en el tiempo de ejecución. Debido a este efecto, 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 invertido de bits. ^[12]

Se ha prestado mucha atención a la mejora del rendimiento de las inversiones de bits tanto en monoprocesadores como en multiprocesadores en los campos de la informática de alto rendimiento. Porque el desarrollo de algoritmos conscientes de la arquitectura puede utilizar mejor los recursos de hardware y software del sistema, incluidos cachés, TLB y multinúcleos, lo que acelera significativamente el cálculo. ^[13]

Referencias

1. Sloane, N. J. A. (ed.), "Sequence A030109", La enciclopedia en línea de secuencias enteras , Fundación OEIS
2. Karp, Alan H. (1996), "Inversión de bits en 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 rápidos de inversión de bits", Conferencia internacional IEEE sobre acústica, habla y procesamiento de señales, ICASSP '89, Glasgow, Escocia, 23-26 de mayo de 1989 , págs. , doi :10.1109/ICASSP.1989.266624, S2CID  15028026
4. Yang, Qingxuan; Ellis, Juan; Mamakani, Khalegh; Ruskey, Frank (2013), "Permutación in situ y barajado perfecto mediante involuciones", Cartas de procesamiento de información , 113 (10–11): 386–391, arXiv : 1204.1958 , doi : 10.1016/j.ipl.2013.02.017, SEÑOR  3037467, S2CID  14672841.
5. Herman, Gabor T. (2009), Fundamentos de la tomografía computarizada (2ª ed.), Londres: Springer, p. 209, ISBN 978-1-85233-617-2
6. Gordon, Dan (junio de 2017), "Un enfoque de desrandomización para recuperar señales de banda limitada en una amplia gama de frecuencias de muestreo aleatorias", Algoritmos numéricos , 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 círculo" (PDF) , Actas del Decimosexto Simposio Anual 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, S2CID  14307262.
11. Jeong, Jechang; Williams, WJ (1990), "Un algoritmo rápido de inversión de bits recursivo", 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 invertido 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 monoprocesadores y multiprocesadores de memoria compartida", SIAM Journal on Scientific Computing , 22 (6): 2113–2134, doi :10.1137/S1064827599359709, MR  1856305