Fjäril (FFT)

Butterfly  är ett elementärt steg i Cooley -Tukey FFT-algoritmen för att beräkna den snabba Fouriertransformen .

Varaktigheten av fjärilssteget bestämmer varaktigheten av beräkningen av Fouriertransformen. [ett]

I sin enklaste form (radix-2 fjäril) är en tvåpunktsförvandling.

Formel för att beräkna "fjärilar": [1]

Beteckningar: , – Inledande punkter; , – resultatpoäng, – komplex koefficient.

För FFT-data av storlek krävs det att man beräknar 2-Radix Butterfly-operationen. [1] [2] [3]

Ibland används fjärilsoperationer av högre ordning: Radix-4, Radix-8. Radix-4 är cirka 20 % effektivare för Fouriertransformeringen av stora datamängder. En operation större än 8 används praktiskt taget inte på grund av obetydliga prestandavinster och svårigheter vid implementering (resursförbrukning). [4] [5]

En liknande struktur kan användas i implementeringar av Viterbi-algoritmen (ACS-operation - Add-Compare-Select) [6] .

Anteckningar

  1. ↑ 1 2 3 Implementering av en heltals-FFT på processorer med ARM-arkitektur // Krets nr 3 mars 2001
  2. ↑ L. Rabiner och B. Gould "Teori och tillämpningar av digital signalbehandling".
  3. ↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 29 december 2012. Arkiverad från originalet 14 augusti 2003. 
  4. ↑ http://www.ece.ucdavis.edu/~bbaas/281/slides/Handout.fft2.pdf Arkiverad 6 december 2012 på Wayback Machine Higher Radices
  5. ↑ http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html Arkiverad 30 april 2010 på Wayback Machine Radix-4 FFT Algorithm; Figur TC.3.9 Grundläggande fjärilsberäkning i en radix-4 FFT-algoritm
  6. ↑ Implementering av Viterbi-algoritmen i dagens digitala kommunikationssystem Arkiverad 25 december 2012 på Wayback Machine // Design And Reuse (EETimes): "Viterbi ACS-instruktioner är baserade på Viterbi fjärilsstruktur och symmetri. Strukturen kallas "fjäril" pga. till dess fysiska likhet med djuret.”, Figurer 8-10

Länkar