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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم تبدیل سریع فوریه بلوستین (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 = –(kn)2/2 + n2/2 + k2/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.

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

اجازه دهید در مورد اینکه چه نوع کانولوشنی در الگوریتم Bluestein برای DFT مورد نیاز است دقیق ترشویم. اگر دنباله bn در 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 فرد، با این حال، bn غیرمتناوب است و ما از لحاظ فنی از negacyclic convolution به طول N استفاده کنیم. با این حال چنین تمایزاتی، زمانی که یک an با پدینگ صفر به طول حداقل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.)