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

**الگوریتم تبدیل سریع فوریه بلوستین** ([//en.wikipedia.org/w/index.php?title=Bluestein%27s_FFT_algorithm&oldid=468778059 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* = &ndash;(*k*&ndash;*n*)2/2 + *n*2/2 + *k*2/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*&ndash;1 است که به صورت زیر تعریف می‌شود:

:a_n = x_n e^{-\frac{\pi i}{N} n^2 }
:b_n = e^{\frac{\pi i}{N} n^2 }

با ضرب خروجی کانولوشن درb**<sub>*k*</sub>*(عوامل مرحله 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&ndash;92 (1969).
* D. H. Bailey and P. N. Swarztrauber, "The fractional Fourier transform and applications," *[//en.wikipedia.org/w/index.php?title=Society_for_Industrial_and_Applied_Mathematics&oldid=443230102 SIAM Review]* **33**, 389-404 (1991).  (Note that this terminology for the z-transform is nonstandard: a [//en.wikipedia.org/w/index.php?title=Fractional_Fourier_transform&oldid=460573665 fractional Fourier transform] conventionally refers to an entirely different, continuous transform.)
* Lawrence Rabiner, "The chirp z-transform algorithm&mdash;a lesson in serendipity," *IEEE Signal Processing Magazine* **21**, 118-119 (March 2004).  (Historical commentary.)

رده:الگوریتم‌های تبدیل سریع فوریه
رده:تبدیل‌های انتگرالی
رده:تحلیل زمان–بسامد