En matemáticas aplicadas, una permutación de inversión de bits es una permutación de una secuencia de n elementos, donde n = 2 k es una potencia de dos . Se define indexando los elementos de la secuencia por los números del 0 al n - 1 y luego invirtiendo las representaciones binarias de cada uno de estos números (rellenados para que cada uno de estos números binarios tenga una longitud exactamente k ). Luego, cada elemento se asigna a la nueva posición dada por este valor invertido. La permutación de inversión de bits es una involución , por lo que repetir la misma permutación dos veces vuelve al orden original de los elementos.
Esta permutación se puede aplicar a cualquier secuencia en tiempo lineal mientras se realizan solo 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 cuando se invierten 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 . Al repetir la misma permutación en esta nueva secuencia, se vuelve a la secuencia inicial.
Escribiendo 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 de tamaño 2 k , para k = 0, 1, 2, 3, ... están
- k = 0: 0
- k = 1: 0 1
- k = 2: 0 2 1 3
- k = 3: 0 4 2 6 1 5 3 7
- k = 4: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
(secuencia A030109 en la OEIS )
Cada permutación en esta secuencia se puede generar concatenando dos secuencias de números: la permutación anterior, duplicada, 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 agregar 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 .
Generalizaciones
La generalización para n = b m un número entero arbitrario b > 1 es una base de - b dígitos-reversión de permutación , en el que los base- b (radix- b dígitos) del índice de cada elemento se invierten para obtener el índice permutado. Una generalización adicional a tamaños compuestos arbitrarios es una inversión de dígitos de base mixta (en la que los elementos de la secuencia están indexados por un número expresado en una base mixta, cuyos dígitos están invertidos por la permutación).
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 usar para intercalar dos secuencias de datos de igual longitud en el lugar. [1]
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, llamada Efficient Ordering , [2] opera con números compuestos y se basa en descomponer el número en sus componentes primos.
La segunda extensión, llamada EBR (Extended Bit-Reversal), [3] es similar en espíritu a la inversión de bits. Dada una matriz de tamaño n , EBR llena la matriz con una permutación de los números en el rangoen tiempo lineal. Los números sucesivos están separados en la permutación por al menos posiciones.
Aplicaciones
La inversión de bits es más importante para los algoritmos FFT de Radix-2 Cooley – Tukey , 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. [4]
La permutación de inversión de bits también se ha utilizado para diseñar límites inferiores en el cálculo distribuido. [5]
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 las representaciones binarias de coma fija 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, escuando esos números se consultan en orden inverso de bits. Este límite se aplica incluso a árboles como los árboles abiertos que pueden reorganizar sus nodos entre accesos. [6]
En estudios musicales, la permutación de inversión de bits también se ha utilizado para correlacionar las funciones de clasificación del peso métrico y las frecuencias de inicio del corpus clásico en una medida de tiempo común (4/4). [7]
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. [8]
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 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. [9] Sin embargo, calcular la reversió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 utilizando solo cálculos de índice simples. [10]
Otra consideración que es aún más importante para el rendimiento de estos algoritmos es el efecto de la jerarquía de la 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. [8] [9] 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. [11]
Referencias
- ^ Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), "In-place permuting and perfect shuffling using involutions", Information Processing Letters , 113 (10-11): 386-391, doi : 10.1016 / j.ipl.2013.02.017 , MR 3037467.
- ^ Herman, Gabor T. (2009). Fundamentos de la tomografía computarizada (2ª ed.). Londres: Springer. pag. 209 . ISBN 978-1-85233-617-2.
- ^ 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 aleatorio". Algoritmos numéricos . 77 (4): 1141-1157. doi : 10.1007 / s11075-017-0356-3 .
- ^ B. Gold y CM Rader, Procesamiento digital de señales (Nueva York: McGraw-Hill, 1969).
- ^ 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 de ACM sobre Teoría de la Computación (STOC '84) , págs. 493 –503, doi : 10.1145 / 800057.808719 , ISBN 978-0897911337.
- ^ Wilber, Robert (1989), "Límites inferiores para acceder a árboles de búsqueda binaria con rotaciones" , 27º Simposio anual sobre los fundamentos de la informática (sfcs 1986) , págs. 61–70, doi : 10.1109 / SFCS.1986.28 , ISBN 0-8186-0740-8.
- ^ Murphy, Scott (2020), "Common Rhythm as Discrete Derivative of its Common-Time Meter" (PDF) , MusMat: Revista Brasileña de Música y Matemáticas , 4 , págs. 1-11.
- ^ a b Karp, Alan H. (1996), "Bit reversal on uniprocessors", 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 encuesta en 1996.
- ^ a b 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.
- ^ Jeong, Jechang; Williams, WJ (1990), "Un algoritmo rápido recursivo de inversión de bits", Conferencia internacional sobre acústica, habla y procesamiento de señales (ICASSP-90) , 3 , págs. 1511-1514, doi : 10.1109 / ICASSP.1990.115695.
- ^ 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.