الگوریتم تبدیل سریع فوریه بلوستین

الگوریتم تبدیل سریع فوریه بلوستین (Bluestein's FFT algorithm)، که عموماً به نام (chirp z-transform algorithm (1969 معروف است، یک الگوریتم تبدیل سریع فوریه(FFT) است که تبدیل فوریه گسسته(DFT) از اندازه‌های دلخواه (شامل مقادیر اول) را با ارائه دوباره DFT به عنوان کانولوشن، محاسبه می‌کند. الگوریتم دیگر برای FFT از اندازه‌های اول، الگوریتم تبدیل سریع فوریه ریدر است،که آن نیز با بازنویسی DFT به عنوان کانولوشن بدست می‌آید. در واقع، الگوریتم Bluestein می‌تواند برای محاسبه تبدیل کلی تر از DFT، بر اساس تبدیل زد یک طرفه مورد استفاده قرار گیرد.

الگوریتم

به یاد می‌آورید که DFT توسط فرمول زیر تعریف می‌شود:

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.$

اگر nk را در توان توسط رابطه nk = –(k–n)²/2 + n²/2 + k²/2, جایگزین کنیم، بدست می‌آید:

$X_{k}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}\left(x_{n}e^{-{\frac {\pi i}{N}}n^{2}}\right)e^{{\frac {\pi i}{N}}(k-n)^{2}}\qquad k=0,\dots ,N-1.$

این جمع دقیقاً کانولوشنی از دو توالی a_n و b_n به طول (N ( n = 0,...,N–1 است که به صورت زیر تعریف می‌شود:

$a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}$

$b_{n}=e^{{\frac {\pi i}{N}}n^{2}}$

با ضرب خروجی کانولوشن درb^*k(عوامل مرحله N ) داریم:

$X_{k}=b_{k}^{*}\sum _{n=0}^{N-1}a_{n}b_{k-n}\qquad k=0,\dots ,N-1.$

این کانولوشن به نوبه خود، می‌تواند با یک جفت از FFT (به علاوه FFT که از قبل برای b_n محاسبه می‌شود) از طریق قضیه کانولوشن انجام شود. نکته کلیدی این است که این FFT از طول یکسان N نیستند: چنین کانولوشنی را می‌توان دقیقاً از FTT محاسبه کرد. تنها کافیست با پر کردن مجموعه از صفر، آن را به طول بزرگتر یا مساوی 2N–1 در آورد(پدینگ صفر یا zero padding). به‌طور خاص ، می‌توان یکی را به توان دو یا برخی اندازه‌های بسیار مرکب دیگر پد کنیم، که FFT می‌تواند به نحو احسن انجام شود. برای مثال الگوریتم کولی-توکی(Cooley–Tukey) در زمان (O(N log N. بنابراین، الگوریتم Bluestein روشی را فراهم می‌کند که در (O(N log N، الگوریتم DFT با اندازه اول را محاسبه می‌کند، هرچند چندین بار کندتر از الگوریتم کولی-توکی برای اندازه‌های مرکب است.

اجازه دهید در مورد اینکه چه نوع کانولوشنی در الگوریتم Bluestein برای DFT مورد نیاز است دقیق ترشویم. اگر دنباله b_n در n دوره‌ای با دوره N داشت، آن را می‌شود کانولوشن حلقوی از طول N در نظر گرفت، و پدینگ صفر تنها برای راحتی محاسباتی باشد. با این حال، به‌طور کلی صدق نمی‌کند:

$b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}e^{{\frac {\pi i}{N}}(2Nn+N^{2})}=(-1)^{N}b_{n}.$

بنابراین، برای N زوج کانولوشن حلقوی است، اما در این مورد N مرکب می‌باشد و به‌طور معمول، الگوریتم کارآمد تر FFT مانند کولی-توکی استفاده می‌شود. برایN فرد، با این حال، b_n غیرمتناوب است و ما از لحاظ فنی از negacyclic convolution به طول N استفاده کنیم. با این حال چنین تمایزاتی، زمانی که یک a_n با پدینگ صفر به طول حداقل2N - 1 می‌رسد (همانطور که در بالا شرح داده شد) برطرف شدنی است. بنابراین، این شاید ساده‌ترین راه باشد که آن را زیر مجموعه‌ای از خروجی‌های یک کانولوشن ساده خطی در نظر بگیریم.

منابع

• Leo I. Bluestein, "A linear filtering approach to the computation of the discrete Fourier transform," Northeast Electronics Research and Engineering Meeting Record 10, 218-219 (1968).
• Lawrence R. Rabiner, Ronald W. Schafer, and Charles M. Rader, "The chirp z-transform algorithm and its application," Bell Syst. Tech. J. 48, 1249-1292 (1969). Also published in: Rabiner, Shafer, and Rader, "The chirp z-transform algorithm," IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969).
• D. H. Bailey and P. N. Swarztrauber, "The fractional Fourier transform and applications," SIAM Review 33, 389-404 (1991). (Note that this terminology for the z-transform is nonstandard: a fractional Fourier transform conventionally refers to an entirely different, continuous transform.)
• Lawrence Rabiner, "The chirp z-transform algorithm—a lesson in serendipity," IEEE Signal Processing Magazine 21, 118-119 (March 2004). (Historical commentary.)