Cooley-Tukey-algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 februari 2022; verifiering kräver 1 redigering .

Cooley-Tukey-algoritmen är den vanligaste algoritmen för att beräkna Fast Fourier-transformen . Algoritmen gör det möjligt att uttrycka en diskret Fouriertransform med längd lika med ett godtyckligt sammansatt tal , genom ett visst antal transformationer av mindre längd med hjälp av rekursion , vilket reducerar komplexiteten i beräkningarna till jämna . Uppkallad efter J. Cooley $N$ $O(N\log N)$ $N$ och J. Tukey .

Grundläggande algoritm

För ett godtyckligt naturligt tal, den diskreta Fouriertransformen av en komplex vektor , där , är en komplex vektor , där , vars komponenter ges av formeln $N$ $x(j)$ $j=0,\ldots ,N-1$ $X(k)$ $k=0,\ldots ,N-1$

X(k)=\sum \limits _{j=0}^{N-1}x(j)\omega ^{kj},\;k=0,\ldots ,N-1,

var . ${\textstil \omega =e^{-{\frac {2\pi i}{N))))$

För att konstruera algoritmen antas det att för vissa naturliga tal och och följande substitution av index görs [1] : ${\displaystyle N=N_{1}N_{2))$ $N_1$ $N_2$

{\begin{array}{lll}&j=j_{1}+N_{1}j_{2},\ &j_{1}=0,\ldots ,N_{1}-1,\ &j_{2 }=0,\ldots ,N_{2}-1,\\&k=k_{2}+N_{2}k_{1},\ &k_{1}=0,\ldots ,N_{1}-1, \ &k_{2}=0,\ldots ,N_{2}-1,\end{array}}

vilket resulterar i

X(k_{2}+N_{2}k_{1})=\sum \limits _{j_{1}=0}^{N_{1}-1}\summa \limits _{j_{ 2}=0}^{N_{2}-1}x(j_{1}+N_{1}j_{2})\omega ^{(j_{1}+N_{1}j_{2})( k_{2}+N_{2}k_{1})}.

Därefter omvandlas vektorerna för in- och utdata till tvådimensionella arrayer och , givet av likheterna $x'$ $X'$

{\begin{array}{lll}&x'(j_{1},j_{2})=x(j_{1}+N_{1}j_{2}),\ &j_{1}=0 ,\ldots ,N_{1}-1,\ &j_{2}=0,\ldots ,N_{2}-1,\\&X'(k_{1},k_{2})=X(k_{2} }+N_{2}k_{1}),\ &k_{1}=0,\ldots ,N_{1}-1,\ &k_{2}=0,\ldots ,N_{2}-1.\end {array}}

Det är värt att notera att komponenterna är beställda annorlunda än . $X$ $x$

Nästa, låt och . Det är uppenbart att . Sedan, när det gäller tvådimensionella variabler, transformeras formeln till formen [2] $\omega ^{N_{1}}=\gamma$ $\omega ^{N_{2}}=\beta$ $\omega ^{N_{1}N_{2}j_{2}k_{1}}=1$

X'(k_{1},k_{2})=\sum \limits _{j_{1}=0}^{N_{1}-1}\beta ^{j_{1}k_{1 }}\left(\omega ^{j_{1}k_{2}}\sum \limits _{j_{2}=0}^{N_{2}-1}x'(j_{1},j_{ 2})\gamma ^{j_{2}k_{2}}\höger).

Att beräkna längdtransformationen kommer alltså ner på att göra följande: ${\displaystyle N=N_{1}N_{2))$

Beräkning av längdtransformationer . $N_1$ $N_2$
Multiplikation med komplexa "roterande" faktorer.
Beräkning av längdtransformationer . $N_2$ $N_1$

Dessutom, istället för komplexa additioner och komplexa multiplikationer av den ursprungliga formeln, innehåller det slutliga schemat inte mer än komplexa additioner och komplexa multiplikationer [2] . $N^2$ $N^2$ $N(N_{1}+N_{2}-2)$ $N(N_{1}+N_{2}+1)$

Var och en av längdtransformationerna eller kan beräknas med hjälp av olika snabba algoritmer, i synnerhet igen enligt ovanstående schema. I detta fall kan längdtransformationen representeras i en form som kräver komplexa multiplikationer [3] . $N_1$ $N_2$ ${\textstyle N=\prod \limits _{i=1}^{n}N_{i))$ ${\textstil N\sum \limits _{i=1}^{n}N_{i))$

Algoritm för att basera två

I många applikationer är längden på transformationen en potens av två: . Sedan, i ovanstående schema, alternativ eller är möjliga . I det här fallet talar man om Cooley-Tukey-algoritmen i bas två [3] ( radix-2 ) . $N=2^{m}$ $N_{1}=2$ $N_{2}=2$

Om , då talar man om Cooley-Tukey-algoritmen med tidsförtunning [3] . I detta fall omvandlas ekvationerna till formen $N_{1}=2$

{\begin{array}{rcl}X(k)&=&\sum \limits _{j=0}^{N/2-1}x(2j)\omega ^{2kj}+\omega ^{k}\summa \limits _{j=0}^{N/2-1}x(2j+1)\omega ^{2kj}\\X(k+N/2)&=&\summa \ gränser _{j=0}^{N/2-1}x(2j)\omega ^{2kj}-\omega ^{k}\summa \limits _{j=0}^{N/2-1} x(2j+1)\omega ^{2kj},\ k=0,\ldots ,N/2-1.\end{array}}

Om vi introducerar notationen och , då kan ekvationerna skrivas om som ${\displaystyle E(k)=\summa \limits _{j=0}^{N/2-1}x(2j)\omega ^{2kj))$ ${\displaystyle O(k)=\summa \limits _{j=0}^{N/2-1}x(2j+1)\omega ^{2kj))$

{\begin{array}{rcl}X(k)&=&E(k)+\omega ^{k}O(k)\\X(k+N/2)&=&E(k)- \omega ^{k}O(k),\ k=0,\ldots ,N/2-1.\end{array}}

En sådan operation brukar kallas en "fjäril" .

Denna procedur kan tillämpas rekursivt på ingångsvektorn . Vid varje steg delas -punktstransformationen upp i tvåpunktstransformationer, som i sin tur delas upp på samma sätt tills transformationens längd blir lika med en. Sedan finns det ett omvänt drag, vid varje steg fördubblas längden på resultaten av transformationerna med hjälp av "fjärilar". Med denna implementering utförs komplexa multiplikationer och komplexa additioner. $N$ $(N/2)$ $(N/2)\log _{2}N$ $N\log _{2}N$

Denna process är ett exempel på tillämpningen av dela och erövra tekniken . I många implementeringar undviks dock direkt rekursion och istället korsas beräkningsträdet i bredd-först sökordning .

Om , då talar man om Cooley-Tukey-algoritmen med frekvensdecimering [4] . I detta fall omvandlas ekvationerna till formen $N_{2}=2$

{\begin{array}{rcl}X(2k)&=&\sum \limits _{j=0}^{N/2-1}{\bigg (}x(j)+x(j +N/2){\bigg )}\omega ^{2kj},\\X(2k+1)&=&\summa \limits _{j=0}^{N/2-1}{\bigg ( }x(j)-x(j+N/2){\bigg )}\omega ^{j(2k+1)},\ k=0,\ldots ,N/2-1.\end{array} }

Raider-Brenner algoritm

Låta

a(k)=\left\lbrace {\begin{array}{rl}0,&k=0,\\{\dfrac {x(k)-x(k+N/2)}{2i\ sin \left(2\pi k/N\right)}},&k=1,\ldots ,N/2-1\end{array}}\right.

släpp det

A(k)=\sum \limits _{j=0}^{N/2-1}a(j)\omega ^{2kj},\ k=0,\ldots ,N/2-1 .

Med hjälp av formlerna för frekvensdecimeringsalgoritmen är det lätt att verifiera att följande relation gäller:

X(2k+1)=A(k)-A(k+1)+(x(0)-x(N/2)),\ k=0,\ldots ,N/2-1.

Denna bas-två-modifiering av algoritmen kallas Rader-Brenner-algoritmen . Det gör det möjligt att minska beräkningskomplexiteten på grund av enklare multiplikationer med rent imaginära konstanter [5] . Liknande formler kan erhållas med hjälp av reella konstanter [6] . $1/(2i\sin \left(2\pi k/N\right))$ $1/(2\cos \left(2\pi k/N\right))$

Historik

Algoritmen och dess rekursiva implementering uppfanns omkring 1805 av K. Gauss när han interpolerade banorna för asteroiderna Pallas och Juno [7] . Då blev upptäckten inte utbredd och publicerades först efter vetenskapsmannens död på nytt latin . Gauss-resultatet återupptäcktes flera gånger i olika former under de kommande 150 åren och blev populärt efter publiceringen 1965 av en artikel av J. Cooleyfrån IBM och J. Tukey från Princeton , där algoritmen återigen upptäcktes, och en bekväm implementering för en dator beskrevs också [8] .

Det faktum att Gauss var upptäckaren av algoritmen upptäcktes bara några år efter publiceringen av Cooley och Tukey. I sin artikel hänvisade de bara till I.J. Goods arbete, där Goode-Thomas-algoritmen beskrevs .

Att uttrycka Fouriertransformen av en längd i termer av två längdtransformer kallas ibland Danielsons lemma $N$ $N/2$ — Lanczos , eftersom den erhölls av dessa två författare 1942 [9] .

Anteckningar

↑ Blahut, 1989 , sid. 129.
↑ 1 2 Blahut, 1989 , sid. 130.
↑ 1 2 3 Blahut, 1989 , sid. 133.
↑ Blahut, 1989 , sid. 134.
↑ Blahut, 1989 , sid. 138.
↑ Nussbaumer, 1985 , sid. 92.
↑ Heideman, MT , Johnson, DH , Burrus, CS Gauss och historien om den snabba Fourier-transformen // IEEE ASSP Magazine. - IEEE , 1984. - Vol. 1 , iss. 4 . - S. 14-21 . - doi : 10.1109/MASSP.1984.1162257 .
↑ Cooley, JW , Tukey, JW En algoritm för maskinberäkning av komplexa Fourierserier // Mathematics of Computation. - 1965. - Vol. 19 . - S. 297-301 . - doi : 10.1090/S0025-5718-1965-0178586-1 .
↑ Danielson, GC , Lanczos, C. Några förbättringar av praktisk Fourier-analys och deras tillämpning på röntgenspridning från vätskor // Journal of the Franklin Institute. - 1942. - Vol. 233 , utg. 4 . — S. 365–380 . - doi : 10.1016/S0016-0032(42)90767-1 .

Litteratur

Blahuth, R. Snabba digitala signalbehandlingsalgoritmer. —M.:Mir, 1989. — 448 sid. (ryska)
Nussbaumer, G. Fast Fourier Transform and Convolution Algoritms. - M . : Radio och kommunikation, 1985.
Rabiner, L. , Gould, B. Teori och tillämpning av digital signalbehandling. — M .: Mir , 1978.

Se även

Bluestein algoritm