Chirp-algoritme

Chirp-algoritme ( Bluestein-algoritme ) er en algoritme til beregning af den hurtige Fourier-transformation , som består i at reducere beregningen af den diskrete Fourier-transformation til beregningen af foldning .

For , , er formlen for algoritmen afledt af formlen for den diskrete Fourier-transformation af et signal til et signal som følger [1] : $n\in \mathbb {N}$ ${\displaystyle \omega =e^{-{\frac {2\pi i}{n))))$ $\beta ={\sqrt {\omega ))$ $x$ $x$

X(k)=\sum \limits _{j=0}^{n-1}x(j)\omega ^{kj}=\sum \limits _{j=0}^{n-1 }x(j)\beta ^{2kj}=\beta ^{-k^{2}}\sum \limits _{j=0}^{n-1}\beta ^{(jk)^{2} }{\bigg (}\beta ^{-j^{2}}x(j){\bigg )},\;k=0,\ldots ,n-1

Ved at bruge notationen kan vi omskrive denne formel i en mere kompakt form: $a(j)=x(j)\beta ^{-j^{2}}$ $b(j)=\beta ^{j^{2))$

X(k)=b^{*}(k)\left(a*b\right),\;k=0,\ldots ,n-1

Her betyder det hævede skrift kompleks bøjning , og symbolet betyder foldning. Mængderne kaldes nogle gange chirp ( eng. chirp ). $^{*}$ $*$ $b(j)$

Algoritmen indeholder -point foldning, hvis beregning kræver operationer, og yderligere multiplikationer, det vil sige, at det samlede antal operationer har størrelsesordenen , så Bluestein-algoritmen er asymptotisk ikke mere effektiv end den direkte beregning af Fourier-transformationen. Men i nogle applikationer giver det mulighed for en enklere hardwareimplementering. Desuden kan den direkte beregning af foldningen erstattes af hurtige algoritmer [2] . $n$ $O(n^{2})$ $2n$ $O(n^{2})$

For eksempel ved hjælp af foldningssætningen , kan du erstatte beregningen af foldningen med beregningen af to diskrete Fourier-transformationer, som hver kan beregnes ved hjælp af en hurtig algoritme, for eksempel Cooley-Tukey-metoden og dermed , sikre implementeringen af Bluestein-algoritmen med beregningsmæssig kompleksitet . Mængderne og deres Fourier-transformation kan også beregnes på forhånd og gemmes i hukommelsen til senere genbrug. $O(n\log n)$ $b(j)$

Noter

↑ Blahut, 1989 , s. 147.
↑ Blahut, 1989 , s. 149.

Litteratur

Blahuth, R. Hurtige digitale signalbehandlingsalgoritmer. —M.:Mir, 1989. — 448 s. (Russisk)