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.