DSP - Calcolo sul posto

Questo uso efficiente della memoria è importante per progettare hardware veloce per calcolare la FFT. Il termine calcolo sul posto viene utilizzato per descrivere questo utilizzo della memoria.

Decimazione in sequenza temporale

In questa struttura, rappresentiamo tutti i punti in formato binario, cioè in 0 e 1. Quindi, invertiamo quelle strutture. La sequenza che otteniamo dopo è nota come sequenza di inversione di bit. Questo è anche noto come decimazione in sequenza temporale. Il calcolo sul posto di un DFT a otto punti viene mostrato in un formato tabulare come mostrato di seguito -

PUNTI FORMATO BINARIO INVERSIONE PUNTI EQUIVALENTI
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

Decimazione in sequenza di frequenza

Oltre alla sequenza temporale, una sequenza N punti può essere rappresentata anche in frequenza. Prendiamo una sequenza di quattro punti per capirla meglio.

Sia $ x [0], x [1], x [2], x [3], x [4], x [5], x [6], x [7] $. Raggrupperemo due punti in un gruppo, inizialmente. Matematicamente, questa sequenza può essere scritta come;

$$ x [k] = \ sum_ {n = 0} ^ {N-1} x [n] W_N ^ {nk} $$

Ora creiamo un gruppo di sequenza numero da 0 a 3 e un altro gruppo di sequenza da 4 a 7. Ora, matematicamente questo può essere mostrato come;

$$ \ 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} $$

Sostituiamo n con r, dove r = 0, 1, 2 ... (N / 2-1). Matematicamente,

$$ \ displaystyle \ sum \ limits_ {n = 0} ^ {\ frac {N} {2} -1} x [r] W_ {N / 2} ^ {nr} $$

Inizialmente prendiamo i primi quattro punti (x [0], x [1], x [2], x [3]) e proviamo a rappresentarli matematicamente come segue:

$ \ 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} $

ora $ 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 $

Possiamo ulteriormente suddividerlo in altre due parti, il che significa che invece di romperle come sequenza di 4 punti, possiamo suddividerle in una sequenza di 2 punti.