Motýl (FFT)

Butterfly  je základním krokem v Cooley -Tukey FFT algoritmu pro výpočet rychlé Fourierovy transformace .

Doba trvání kroku Butterfly určuje dobu trvání výpočtu Fourierovy transformace. [jeden]

Ve své nejjednodušší podobě (radix-2 butterfly) je dvoubodová transformace.

Vzorec pro výpočet "Motýlů": [1]

Označení: , – počáteční body; , – výsledné body, – komplexní koeficient.

Pro data FFT o velikosti je nutné vypočítat operaci 2-Radix Butterfly. [1] [2] [3]

Někdy se používají motýlkové operace vyššího řádu: Radix-4, Radix-8. Radix-4 je asi o 20 % účinnější pro Fourierovu transformaci velkého množství dat. Operace větší než 8 se prakticky nepoužívá kvůli nevýznamnému nárůstu výkonu a potížím při implementaci (spotřeba zdrojů). [4] [5]

Obdobnou strukturu lze použít v implementacích Viterbiho algoritmu (operace ACS - Add-Compare-Select) [6] .

Poznámky

  1. ↑ 1 2 3 Implementace celočíselného FFT na procesorech s architekturou ARM // Circuitry No. 3 March 2001
  2. ↑ L. Rabiner a B. Gould „Teorie a aplikace číslicového zpracování signálu“.
  3. ↑ Archivovaná kopie (odkaz není dostupný) . Získáno 29. prosince 2012. Archivováno z originálu 14. srpna 2003. 
  4. ↑ http://www.ece.ucdavis.edu/~bbaas/281/slides/Handout.fft2.pdf Archivováno 6. prosince 2012 na Wayback Machine Higher Radices
  5. ↑ http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html Archivováno 30. dubna 2010 na Wayback Machine Radix-4 FFT Algorithm; Obrázek TC.3.9 Základní výpočet motýla v algoritmu radix-4 FFT
  6. ↑ Implementace Viterbiho algoritmu v dnešních digitálních komunikačních systémech Archivováno 25. prosince 2012 na Wayback Machine // Design And Reuse (EETimes): „Instrukce Viterbi ACS jsou založeny na Viterbiho motýlí struktuře a symetrii. Struktura se nazývá „motýlí“ kvůli k jeho fyzické podobnosti se zvířetem.“, obrázky 8-10

Odkazy