DSP - Computación in situ
Este uso eficiente de la memoria es importante para diseñar hardware rápido para calcular la FFT. El término cálculo in situ se utiliza para describir este uso de memoria.
Diezmamiento en secuencia de tiempo
En esta estructura, representamos todos los puntos en formato binario, es decir, en 0 y 1. Luego, invertimos esas estructuras. La secuencia que obtenemos después de eso se conoce como secuencia de inversión de bits. Esto también se conoce como diezmado en secuencia de tiempo. El cálculo in situ de una DFT de ocho puntos se muestra en formato tabular, como se muestra a continuación:
PUNTOS | FORMATO BINARIO | INVERSIÓN | PUNTOS EQUIVALENTES |
---|---|---|---|
0 | 000 | 000 | 0 |
1 | 001 | 100 | 4 |
2 | 010 | 010 | 2 |
3 | 011 | 110 | 6 |
4 | 100 | 001 | 1 |
5 | 101 | 101 | 5 |
6 | 110 | 011 | 3 |
7 | 111 | 111 | 7 |
Diezmamiento en secuencia de frecuencia
Además de la secuencia de tiempo, una secuencia de N puntos también se puede representar en frecuencia. Tomemos una secuencia de cuatro puntos para entenderlo mejor.
Sea la secuencia $ x [0], x [1], x [2], x [3], x [4], x [5], x [6], x [7] $. Agruparemos dos puntos en un grupo, inicialmente. Matemáticamente, esta secuencia se puede escribir como;
$$ x [k] = \ sum_ {n = 0} ^ {N-1} x [n] W_N ^ {nk} $$Ahora hagamos un grupo de secuencia número 0 a 3 y otro grupo de secuencia 4 a 7. Ahora, matemáticamente esto se puede mostrar como;
$$ \ Displaystyle \ sum \ limits_ {n = 0} ^ {\ frac {N} {2} -1} x [n] W_N ^ {nk} + \ Displaystyle \ sum \ limits_ {n = N / 2} ^ {N-1} x [n] W_N ^ {nk} $$Reemplacemos n por r, donde r = 0, 1, 2…. (N / 2-1). Matemáticamente,
$$ \ Displaystyle \ sum \ limits_ {n = 0} ^ {\ frac {N} {2} -1} x [r] W_ {N / 2} ^ {nr} $$Tomamos los primeros cuatro puntos (x [0], x [1], x [2], x [3]) inicialmente y tratamos de representarlos matemáticamente de la siguiente manera:
$ \ sum_ {n = 0} ^ 3x [n] W_8 ^ {nk} + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {(n + 4) k} $
$ = \ lbrace \ sum_ {n = 0} ^ 3x [n] + \ sum_ {n = 0} ^ 3x [n + 4] W_8 ^ {(4) k} \ rbrace \ times W_8 ^ {nk} $
ahora $ X [0] = \ sum_ {n = 0} ^ 3 (X [n] + X [n + 4]) $
$ X [1] = \ sum_ {n = 0} ^ 3 (X [n] + X [n + 4]) W_8 ^ {nk} $
$ = [X [0] -X [4] + (X [1] -X [5]) W_8 ^ 1 + (X [2] -X [6]) W_8 ^ 2 + (X [3] -X [7]) W_8 ^ 3 $
Podemos dividirlo aún más en dos partes más, lo que significa que en lugar de dividirlas como una secuencia de 4 puntos, podemos dividirlas en una secuencia de 2 puntos.