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

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

${\displaystyle 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, جایگزین کنیم، بدست می‌آید:

${\displaystyle 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 است که به صورت زیر تعریف می‌شود:

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

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

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

${\displaystyle 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 در نظر گرفت، و پدینگ صفر تنها برای راحتی محاسباتی باشد. با این حال، به‌طور کلی صدق نمی‌کند:

${\displaystyle 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 می‌رسد (همانطور که در بالا شرح داده شد) برطرف شدنی است. بنابراین، این شاید ساده‌ترین راه باشد که آن را زیر مجموعه‌ای از خروجی‌های یک کانولوشن ساده خطی در نظر بگیریم.