2.3: Cálculo in Place de la DFT y Scrambling

Debido a que el uso de ambos mapas de índice tipo uno y dos desacoplan los cálculos de las filas y columnas de la matriz de datos, los resultados de cada\(N_i\) DFT de longitud corta se pueden escribir de nuevo sobre los datos, ya que no será necesario nuevamente después de que se transforme esa fila o columna en particular. Esto se ve fácilmente en las figuras en la sección 2.2 donde el DFT de la primera fila de se\(x(n_1,n_2)\) puede volver a poner sobre los datos en lugar de escribirse en una nueva matriz. Una vez finalizados todos los cálculos, el DFT total está en la matriz de los datos originales. Esto da un ahorro significativo de memoria sobre el uso de una matriz separada para la salida.

Desafortunadamente, el uso de cálculos in place da como resultado el orden de los valores de DFT que se permutan o se cifran. Esto se debe a que los datos se indexan de acuerdo con la ecuación del mapa de entrada y los resultados se ponen en las mismas ubicaciones en lugar de las ubicaciones dictadas por la ecuación del mapa de salida. Por ejemplo, con una FFT de longitud 8 radix-2, el mapa de índice de entrada es

\[n=4n_{1}+2n_{2}+n_{3} \nonumber \]

que para satisfacer la ecuación requiere un mapa de salida de

\[k=k_{1}+2k_{2}+4k_{3} \nonumber \]

Los cálculos in place colocarán los resultados de DFT en las ubicaciones del mapa de entrada y estos deben reordenarse o descifrarse en las ubicaciones dadas por el mapa de salida. El examen de estos dos mapas muestra que la salida cifrada está en un orden de “bit invertido”.

Para ciertas aplicaciones, este orden de salida cifrada no es importante, pero para muchas aplicaciones, el orden debe ser descifrado antes de que el DFT pueda considerarse completo. Debido a que la base de la FFT de radix-2 es la misma que la base de la representación numérica binaria, la dirección correcta para cualquier término se encuentra invirtiendo los bits binarios de la dirección. La parte de la mayoría de los programas FFT que realiza esta reordenación se denomina contador de bits invertidos. En los apéndices se encuentran ejemplos de diversos descifradores.

El desarrollo aquí utiliza el mapa de entrada y el algoritmo resultante se llama “decimation-in-frequency”. Si se usa la salida en lugar del mapa de entrada para derivar el algoritmo FFT de manera que se obtenga el orden de salida correcto, el orden de entrada debe ser cifrado para que sus valores estén en ubicaciones especificadas por el mapa de salida en lugar del mapa de entrada. Este algoritmo se llama “decimation-in-time”. La aleatorización es el mismo conteo de bits inversos que antes, pero precede al algoritmo FFT en este caso. El mismo proceso de un postunscrambler o pre-scrambler ocurre para los cálculos in place con los mapas de tipo uno. Es posible hacer el descifrado mientras se calcula la FFT y evitar un descifrador separado. Esto se hace para la FFT Cooley-Tukey y para la PFA.

Si se usa una FFT de radio 2, el descifrador es un contador de bits invertidos. Si se usa una FFT de radix-4, el unscrambler es un contador invertido de base 4, y de manera similar para radix-8 y otros. Sin embargo, si para la FFT de radio 4, las DFT de longitud corta (mariposas) tienen sus salidas en orden reverenciado por bits, la salida de la FFT total de radix-4 estará en orden invertido de bits, no en orden invertido de base 4. Esto significa que cualquier\(2^n\) radix-FFT puede usar el mismo contador de bits invertidos de radix-2 como unscrambler si se usan las mariposas adecuadas.

Colaborador

• ContribeeBurrus