Motýlí diagram - Butterfly diagram

Graf toku signálu připojení vstupů X (vlevo) na výstupy y které na nich (vpravo) závisí na „motýlovém“ kroku radix-2 Cooley – Tukey FFT. Tento diagram se podobá a motýl (jako v motýl morpho 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á Fourierova transformace algoritmy, a motýl je část výpočtu, která kombinuje výsledky menších diskrétní Fourierovy transformace (DFT) do většího DFT nebo naopak (rozbití většího DFT na subtransformace). Název „motýl“ pochází z tvaru diagramu toku dat v případě radix-2, jak je popsáno níže.^[1] Nejčasnější výskyt v tisku termínu je myšlenka být v roce 1969 MIT technická zpráva.^[2][3] Stejnou strukturu lze nalézt také v Viterbiho algoritmus, slouží k nalezení nejpravděpodobnější sekvence skrytých stavů.

Nejčastěji se výraz „motýl“ objevuje v kontextu Cooley – Tukey FFT algoritmus, který rekurzivně rozbije DFT z kompozitní velikost n = rm do r menší transformace velikosti m kde r je „radix“ transformace. Tyto menší DFT se poté kombinují pomocí size-r motýly, které samy o sobě mají velikost DFT r (provedeno m časy na odpovídajících výstupech dílčích transformací) předem vynásobené kořeny jednoty (známý jako dvojité faktory ). (Toto je případ „decimace v čase“; lze také provést kroky obráceně, známé jako „decimace ve frekvenci“, kde jsou motýli na prvním místě a jsou následně vynásobeni dvojitými faktory. Viz také Cooley – Tukey FFT článek.)

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₀, X₁) (odpovídající výstupy dvou dílčích transformací) a dává dva výstupy (y₀, y₁) podle vzorce (bez dvojité faktory ):

${ displaystyle y_ {0} = x_ {0} + x_ {1} ,}$

${ displaystyle y_ {1} = x_ {0} -x_ {1}. ,}$

Pokud někdo nakreslí diagram toku dat pro tuto dvojici operací, (X₀, X₁) do (y₀, y₁) čáry se kříží a připomínají křídla a motýl, odtud název (viz také obrázek vpravo).

Radix-2 v čase s decimací zalomí délkuN DFT do dvou délekN/ 2 DFT následované kombinační fází skládající se z mnoha operací motýlů.

Přesněji řečeno, radix-2 decimační algoritmus FFT zapnutý n = 2 ^str vstupy s ohledem na primitiva n-tý kořen jednoty ${ displaystyle omega _ {n} ^ {k} = e ^ {- { frac {2 pi ik} {n}}}}$ spoléhá na O (n log₂ n) motýli v podobě:

${ displaystyle y_ {0} = x_ {0} + x_ {1} omega _ {n} ^ {k} ,}$

${ displaystyle y_ {1} = x_ {0} -x_ {1} omega _ {n} ^ {k}, ,}$

kde k je celé číslo v závislosti na části transformace, která se počítá. Zatímco odpovídající inverzní transformaci lze matematicky provést nahrazením ω s ω⁻¹ (a případně vynásobením faktorem celkového měřítka, v závislosti na normalizační konvenci), lze také přímo obrátit motýly:

${ displaystyle x_ {0} = { frac {1} {2}} (y_ {0} + y_ {1}) ,}$

${ displaystyle x_ {1} = { frac { omega _ {n} ^ {- k}} {2}} (y_ {0} -y_ {1}), ,}$

odpovídá 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 pomocí 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.^[4]

Viz také

• Matematický diagram
• Lemma Zassenhaus
• Graf toku signálu

Reference

externí odkazy

• vysvětlení diagramů FFT a motýlů.
• motýlí diagramy různých implementací FFT (Radix-2, Radix-4, Split-Radix).