DSP - Convoluzione circolare DFT

Prendiamo due sequenze di durata finita x 1 (n) e x 2 (n), aventi lunghezza intera come N. Le loro DFT sono rispettivamente X 1 (K) e X 2 (K), come mostrato di seguito -

$$ X_1 (K) = \ sum_ {n = 0} ^ {N-1} x_1 (n) e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0,1,2 .. .N-1 $$ $$ X_2 (K) = \ sum_ {n = 0} ^ {N-1} x_2 (n) e ^ {\ frac {j2 \ Pi kn} {N}} \ quad k = 0 , 1,2 ... N-1 $$

Ora proveremo a trovare la DFT di un'altra sequenza x 3 (n), che è data come X 3 (K)

$ X_3 (K) = X_1 (K) \ volte X_2 (K) $

Prendendo l'IDFT di quanto sopra otteniamo

$ x_3 (n) = \ frac {1} {N} \ displaystyle \ sum \ limits_ {n = 0} ^ {N-1} X_3 (K) e ^ {\ frac {j2 \ Pi kn} {N}} $

Dopo aver risolto l'equazione di cui sopra, finalmente, otteniamo

$ x_3 (n) = \ displaystyle \ sum \ limits_ {m = 0} ^ {N-1} x_1 (m) x_2 [((nm)) _ N] \ quad m = 0,1,2 ... N- 1 $

Punti di confronto Convoluzione lineare Convoluzione circolare
Mutevole Spostamento lineare Spostamento circolare
Campioni nel risultato della convoluzione $ N_1 + N_2−1 $ $ Max (N_1, N_2) $
Trovare la risposta di un filtro Possibile Possibile con zero padding

Metodi di convoluzione circolare

In generale, ci sono due metodi, che vengono adottati per eseguire la convoluzione circolare e sono:

  • Metodo del cerchio concentrico,
  • Metodo di moltiplicazione di matrici.

Metodo del cerchio concentrico

Siano $ x_1 (n) $ e $ x_2 (n) $ due sequenze date. I passaggi seguiti per la convoluzione circolare di $ x_1 (n) $ e $ x_2 (n) $ sono

  • Prendi due cerchi concentrici. Traccia N campioni di $ x_1 (n) $ sulla circonferenza del cerchio esterno (mantenendo uguale distanza punti successivi) in senso antiorario.

  • Per tracciare $ x_2 (n) $, tracciare N campioni di $ x_2 (n) $ in senso orario sul cerchio interno, iniziando il campione posizionato nello stesso punto del 0 ° campione di $ x_1 (n) $

  • Moltiplica i campioni corrispondenti sui due cerchi e aggiungili per ottenere l'output.

  • Ruota il cerchio interno in senso antiorario con un campione alla volta.

Metodo di moltiplicazione di matrici

Il metodo Matrix rappresenta le due sequenze date $ x_1 (n) $ e $ x_2 (n) $ in forma di matrice.

  • Una delle sequenze date viene ripetuta tramite lo spostamento circolare di un campione alla volta per formare una matrice NXN.

  • L'altra sequenza è rappresentata come matrice di colonne.

  • La moltiplicazione di due matrici dà il risultato di convoluzione circolare.