Cooley-Tukey algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. februar 2022; verifikation kræver 1 redigering .

Cooley-Tukey-algoritmen er den mest almindeligt anvendte algoritme til beregning af Fast Fourier Transform . Algoritmen gør det muligt at udtrykke en diskret Fourier-transformation af længde svarende til et vilkårligt sammensat tal gennem et vist antal transformationer af mindre længde ved brug af rekursion , hvilket reducerer kompleksiteten af beregninger til glatte . Opkaldt efter J. Cooley $N$ $O(N\log N)$ $N$ og J. Tukey .

Grundlæggende algoritme

For et vilkårligt naturligt tal, den diskrete Fourier-transformation af en kompleks vektor , hvor , er en kompleks vektor , hvor , hvis komponenter er givet af formlen $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,

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

For at konstruere algoritmen antages det, at der for nogle naturlige tal og og følgende substitution af indekser foretages [1] : $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}}

hvilket resulterer i

X(k_{2}+N_{2}k_{1})=\sum \limits _{j_{1}=0}^{N_{1}-1}\sum \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})}.

Dernæst transformeres vektorerne af input- og outputdata til todimensionelle arrays og givet af lighederne $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 er værd at bemærke, at komponenterne er bestilt anderledes end . $x$ $x$

Dernæst lad og . Det er indlysende . Derefter, hvad angår todimensionelle variable, transformeres formlen til 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}}\right).

Beregning af længdetransformationen kommer således ned til at gøre følgende: $N=N_{1}N_{2}$

Beregning af længdetransformationer . $N_1$ $N_2$
Multiplikation med komplekse "roterende" faktorer.
Beregning af længdetransformationer . $N_2$ $N_1$

Desuden, i stedet for komplekse additioner og komplekse multiplikationer af den oprindelige formel, indeholder det endelige skema ikke mere end komplekse additioner og komplekse multiplikationer [2] . $N^2$ $N^2$ $N(N_{1}+N_{2}-2)$ $N(N_{1}+N_{2}+1)$

Hver af længdetransformationerne eller kan beregnes ved hjælp af forskellige hurtige algoritmer, især igen ifølge ovenstående skema. I dette tilfælde kan længdetransformationen repræsenteres i en form, der kræver komplekse multiplikationer [3] . $N_1$ $N_2$ ${\textstyle N=\prod \limits _{i=1}^{n}N_{i}}$ ${\tekststil N\sum \limits _{i=1}^{n}N_{i))$

Algoritme til at basere to

I mange applikationer er længden af transformationen en potens af to: . Så, i ovenstående skema, er muligheder eller mulige . I dette tilfælde taler man om Cooley-Tukey-algoritmen i base to [3] ( radix-2 ) . ${\displaystyle N=2^{m))$ $N_{1}=2$ $N_{2}=2$

Hvis , så taler man om Cooley-Tukey-algoritmen med tidsudtynding [3] . I dette tilfælde transformeres ligningerne til formen $N_{1}=2$

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

Hvis vi introducerer notationen og , så kan ligningerne omskrives som ${\displaystyle E(k)=\sum \limits _{j=0}^{N/2-1}x(2j)\omega ^{2kj))$ ${\displaystyle O(k)=\sum \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 kaldes normalt en "sommerfugl" .

Denne procedure kan anvendes rekursivt på inputvektoren . Ved hvert trin opdeles -punkttransformationen i to -punktstransformationer, som igen opdeles på samme måde, indtil længden af transformationen bliver lig med én. Så er der et omvendt træk, ved hvert trin fordobles længden af resultaterne af transformationerne ved hjælp af "sommerfugle". Med denne implementering udføres komplekse multiplikationer og komplekse additioner. $N$ $(N/2)$ $(N/2)\log _{2}N$ $N\log _{2}N$

Denne proces er et eksempel på anvendelsen af skille og hersk- teknikken . Men i mange implementeringer undgås direkte rekursion, og i stedet krydses beregningstræet i bredde-først søgerækkefølge .

Hvis , så taler man om Cooley-Tukey-algoritmen med frekvensdecimering [4] . I dette tilfælde transformeres ligningerne til 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)&=&\sum \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 algoritme

Lade

a(k)=\venstre\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.

Giv slip

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

Ved at bruge formlerne for frekvensdecimeringsalgoritmen er det let at verificere, at følgende relation holder:

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

Denne base-to-modifikation af algoritmen kaldes Rader-Brenner-algoritmen . Det gør det muligt at reducere beregningsmæssig kompleksitet på grund af enklere multiplikationer med rent imaginære konstanter [5] . Lignende formler kan opnås ved brug af reelle konstanter [6] . $1/(2i\sin \left(2\pi k/N\right))$ $1/(2\cos \left(2\pi k/N\right))$

Historie

Algoritmen og dens rekursive implementering blev opfundet omkring 1805 af K. Gauss , da han interpolerede banerne for asteroiderne Pallas og Juno [7] . Så blev opdagelsen ikke udbredt og blev først offentliggjort efter videnskabsmandens død på ny latin . Gauss-resultatet blev genfundet flere gange i forskellige former i løbet af de næste 150 år og blev populært efter offentliggørelsen i 1965 af en artikel af J. Cooleyfra IBM og J. Tukey fra Princeton , hvor algoritmen endnu en gang blev genopdaget, og en bekvem implementering til en computer også blev beskrevet [8] .

Det faktum, at Gauss var opdageren af algoritmen, blev opdaget kun få år efter udgivelsen af Cooley og Tukey. I deres artikel henviste de kun til I.J. Goods arbejde, hvor Goode-Thomas-algoritmen blev beskrevet .

At udtrykke Fourier-transformationen af en længde i form af to længdetransformationer kaldes undertiden Danielsons lemma $N$ $N/2$ — Lanczos , da det blev opnået af disse to forfattere i 1942 [9] .

Noter

↑ Blahut, 1989 , s. 129.
↑ 1 2 Blahut, 1989 , s. 130.
↑ 1 2 3 Blahut, 1989 , s. 133.
↑ Blahut, 1989 , s. 134.
↑ Blahut, 1989 , s. 138.
↑ Nussbaumer, 1985 , s. 92.
↑ Heideman, MT , Johnson, DH , Burrus, CS Gauss og historien om den hurtige Fourier-transformation // IEEE ASSP Magazine. - IEEE , 1984. - Vol. 1 , iss. 4 . - S. 14-21 . - doi : 10.1109/MASSP.1984.1162257 .
↑ Cooley, JW , Tukey, JW En algoritme til maskinberegning af komplekse Fourier-serier // Mathematics of Computation. - 1965. - Bd. 19 . - S. 297-301 . - doi : 10.1090/S0025-5718-1965-0178586-1 .
↑ Danielson, GC , Lanczos, C. Nogle forbedringer i praktisk Fourier-analyse og deres anvendelse på røntgenspredning fra væsker // Journal of the Franklin Institute. - 1942. - Bd. 233 , udg. 4 . — S. 365–380 . - doi : 10.1016/S0016-0032(42)90767-1 .

Litteratur

Blahuth, R. Hurtige digitale signalbehandlingsalgoritmer. —M.:Mir, 1989. — 448 s. (Russisk)
Nussbaumer, G. Hurtige Fourier-transformations- og konvolutionsalgoritmer. - M . : Radio og kommunikation, 1985.
Rabiner, L. , Gould, B. Teori og anvendelse af digital signalbehandling. — M .: Mir , 1978.

Se også

Bluestein algoritme