Motýlí diagram - Butterfly diagram

Tento článek je o motýlích diagramech v algoritmech FFT; pro diagramy slunečních skvrn stejného jména viz sluneční cyklus .
Graf toku signálu spojující vstupy x (vlevo) s výstupy y, které na nich závisí (vpravo) pro „motýlí“ krok radix-2 Cooley – Tukey FFT. Tento diagram připomíná motýla (jako u morpho motýla zobrazeného pro srovnání), odtud název, i když v některých zemích se také nazývá diagram přesýpacích hodin.

V kontextu rychlých algoritmů Fourierovy transformace je motýl částí výpočtu, která kombinuje výsledky menších diskrétních Fourierových transformací (DFT) do většího DFT nebo naopak (rozdělení většího DFT do dílčích transformací). Název „motýl“ pochází z tvaru diagramu toku dat v případě radix-2, jak je popsáno níže. Nejčasnější výskyt tohoto termínu se předpokládá v technické zprávě MIT z roku 1969 . Stejnou strukturu lze také najít v algoritmu Viterbi , který se používá k nalezení nejpravděpodobnější sekvence skrytých stavů.

Nejčastěji se termín „motýl“ objevuje v kontextu Cooley – Tukey FFT algoritmu , který rekurzivně rozkládá DFT složené velikosti n  =  rm na r menších transformací velikosti m, kde r je „radix“ transformace. Tyto menší DFT jsou poté kombinovány pomocí motýlů velikosti R , které samy o sobě jsou DFT velikosti r (prováděné m krát na odpovídajících výstupech subtransformací ) předem vynásobené kořeny jednoty (známé jako dvojité faktory ). (Toto je případ „decimace v čase“; lze také provést kroky v opačném směru, známé jako „decimace ve frekvenci“, kde jsou motýli na prvním místě a jsou post-násobeni součiniteli dvou faktorů. Viz také článek Cooley – Tukey FFT .)

Radix-2 motýlí diagram

V případě algoritmu radix-2 Cooley – Tukey je motýl jednoduše DFT velikosti 2, který bere dva vstupy ( x 0x 1 ) (odpovídající výstupy dvou subtransformací) a dává dva výstupy ( y 0y 1 ) podle vzorce (bez faktorů dvojnásobné hodnoty ):

Pokud nakreslíme diagram toku dat pro tuto dvojici operací, čáry ( x 0x 1 ) až ( y 0y 1 ) se protínají a podobají se křídlům motýla , odtud název (viz také obrázek vpravo ).

Radix-2 FFT s decimací v čase rozdělí délku - N DFT na dvě délky - N / 2 DFT následovanou kombinační fází skládající se z mnoha operací motýlů.

Přesněji řečeno, radix-2 decimation-in-time FFT algoritmus na n  = 2 p vstupech s ohledem na primitivní n -tý kořen jednoty spoléhá na O ( n  log  n ) motýlů ve tvaru:  

kde k je celé číslo v závislosti na vypočítané části transformace. Zatímco odpovídající inverzní transformaci lze matematicky provést nahrazením ω s ω −1 (a případně vynásobením faktorem celkového měřítka, v závislosti na konvenci normalizace), lze motýly také přímo invertovat:

odpovídající algoritmu FFT s decimací ve frekvenci.

Jiná použití

Motýl lze také použít ke zlepšení náhodnosti velkých polí částečně náhodných čísel, a to přivedením každého 32 nebo 64 bitového slova do kauzálního kontaktu s každým dalším slovem prostřednictvím požadovaného hashovacího algoritmu, takže změna v kterémkoli jednom bitu má možnost změny všech bitů ve velkém poli.

Viz také

Reference

  1. ^ Alan V. Oppenheim, Ronald W. Schafer a John R. Buck, diskrétní zpracování signálu , 2. vydání (Upper Saddle River, NJ: Prentice Hall, 1989)
  2. ^ CJ Weinstein (1969-11-21). Kvantovací efekty v digitálních filtrech (zpráva). Laboratoř MIT Lincoln . str. 42 . Citováno 2015-02-10 . Tento výpočet, označovaný jako „motýl“
  3. ^ Cipra, Barry A. (06.06.2012). "FFT a Butterfly Diagram" . mathoverflow.net . Citováno 2015-02-10 .
  4. ^ * Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Oddíl 7.2 Zcela hašování velkého pole“ , Numerické recepty: Umění vědeckých výpočtů (3. vydání), New York: Cambridge University Press, ISBN  978-0-521-88068-8

externí odkazy