Perhonen (FFT)

Butterfly  on Cooley - Tukey FFT-algoritmin perusvaihe nopean Fourier-muunnoksen laskemiseksi .

Butterfly-vaiheen kesto määrittää Fourier-muunnoksen laskennan keston. [yksi]

Yksinkertaisimmassa muodossaan (radix-2 perhonen) on kaksipistemuunnos.

"Perhosten" laskentakaava: [1]

Nimet: , – alkupisteet; , – tulospisteet, – kompleksikerroin.

FFT-tietojen kokoa varten on laskettava 2-Radix Butterfly -operaatio. [1] [2] [3]

Joskus käytetään korkeamman asteen perhosoperaatioita: Radix-4, Radix-8. Radix-4 on noin 20 % tehokkaampi suurten tietomäärien Fourier-muunnoksessa. Yli 8:n operaatiota ei käytännössä käytetä merkityksettömän suorituskyvyn lisäyksen ja toteutusvaikeuksien (resurssien kulutuksen) vuoksi. [4] [5]

Samanlaista rakennetta voidaan käyttää Viterbi-algoritmin toteutuksissa (ACS-toiminto - Add-Compare-Select) [6] .

Muistiinpanot

  1. ↑ 1 2 3 Kokonaisluvun FFT:n toteutus prosessoreissa, joissa on ARM-arkkitehtuuri // Piiri nro 3 maaliskuu 2001
  2. ↑ L. Rabiner ja B. Gould "Digitaalisen signaalinkäsittelyn teoria ja sovellukset".
  3. ↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 29. joulukuuta 2012. Arkistoitu alkuperäisestä 14. elokuuta 2003. 
  4. ↑ http://www.ece.ucdavis.edu/~bbaas/281/slides/Handout.fft2.pdf Arkistoitu 6. joulukuuta 2012 Wayback Machine Higher Radicesissa
  5. ↑ http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html Arkistoitu 30. huhtikuuta 2010 Wayback Machine Radix-4 FFT -algoritmissa; Kuva TC.3.9 Perusperhosen laskenta kantaluku-4 FFT-algoritmissa
  6. ↑ Viterbi-algoritmin käyttöönotto nykypäivän digitaalisissa viestintäjärjestelmissä Arkistoitu 25. joulukuuta 2012 Wayback Machinessa // Suunnittelu ja uudelleenkäyttö (EETimes): "Viterbi ACS:n ohjeet perustuvat Viterbi-perhonen rakenteeseen ja symmetriaan. Rakennetta kutsutaan nimellä "perhonen". sen fyysinen samankaltaisuus eläimen kanssa." Kuvat 8-10

Linkit