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

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

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

اگر N یک عدد اول باشد، بنابراین مجموعهٔ شاخص‌های غیر صفر آن N = 1،...، N - 1 یک گروه به پیمانه N تحت عمل ضرب به شکل می‌دهد. یکی از نتایج از نظریه اعداد از چنین گروه‌هایی است که یک سازنده‌ای از گروه وجود دارد(گاهی اوقات به نام ریشه اولیه)، یک عدد صحیح g به‌طوری‌که n = g^q (به پیمانه N) برای هر شاخص غیر صفر n و برای q منحصربه‌فرد در 0،...، N - 2 درخواست وجود دارد. به‌طور مشابه k = g^–p (به پیمانه N) برای هر k در شاخص غیر صفر و P منحصربه‌فرد در 0،...، N - 2، که در آن توان منفی نشانگر ضرب معکوس gp در پیمانهٔ N است. این بدان معنی است که می‌توانیم DFT را با استفاده از این شاخص‌های جدید p و q بازنویسی کنیم:

${\displaystyle X_{0}=\sum _{n=0}^{N-1}x_{n},}$

${\displaystyle X_{g^{-p}}=x_{0}+\sum _{q=0}^{N-2}x_{g^{q}}e^{-{\frac {2\pi i}{N}}g^{-(p-q)}}\qquad p=0,\dots ,N-2.}$

(به یاد می آورید که x_n و X_k به‌طور ضمنی در N دوره‌ای هستند، و همچنین e^2πi=1. بنابراین، تمام اندیس‌ها و توان هابه پیمانه N گرفته شده اند، که مورد نیاز گروه محاسباتی است.)

جمع نهایی بالا، دقیقاً کانولوشن حلقوی از دو توالی a_q و b_q به طول N-1 است (q=0,1,...,N-2) تعریف شده به صورت زیر:

${\displaystyle a_{q}=x_{g^{q}}}$

${\displaystyle b_{q}=e^{-{\frac {2\pi i}{N}}g^{-q}}.}$

از آنجا که N - 1 مرکب است، این کانولوشن می‌تواند به‌طور مستقیم از طریق قضیه کانولوشن و الگوریتم‌های FFT معمولی انجام پذیرد. با این حال، ممکن است کارآمد نباشد اگر N - 1 خود دارای عوامل اول بزرگ باشد، نیاز به استفاده بازگشتی الگوریتم ریدر دارد. در عوض، می‌توان کانولوشن حلقوی طول (N-1) را دقیق محاسبه کرد. توسط پدینگ صفر کردن آن تا طول حداقل ((2N-1)-1) برای توان دو، که سپس می‌تواند در زمان (O(N log N بدون برنامه‌های بازگشتی الگوریتم ریدر ارزیابی شود.

این الگوریتم، نیاز به (O(N عمل جمع و زمان (O(N log N برای کانولوشن دارد. در عمل، (O(N جمع اغلب می‌تواند با جذب شدن در جمع‌های کانولوشن انجام شود. در صورتی که کانولوشن با یک جفت از FFTs انجام شود، سپس مجموع x_n که از خروجی عبارت صفرام DC FFT بدست می‌آید a_q به علاوه x₀ داده می‌شود و با اضافه کردن آن را به DC از x₀ می‌تواند به تمام خروجی‌های اضافه شده کانولوشن قبل از FFT معکوس اضافه شود. در عین حال، این الگوریتم نیاز به عملیات ذاتی بیشتر از FFTs از اندازه مرکب نزدیک خود دارد، و به‌طور معمول در عمل 3-10 بار به طول می انجامد.

اگر الگوریتم ریدر با استفاده از FFTs با اندازه N - 1 برای محاسبه کانولوشن انجام شود، به جای پدینگ صفر همانطور که در بالا ذکر شد، بهره وری به شدت به N و تعداد دفعاتی که الگوریتم ریدر باید به صورت بازگشتی اعمال شود وابسته می‌شود. بدترین حالت زمانی خواهد بود که N–1 برابر 2N₂ شود که در آن N₂ اول باشد، و N₂–1 = 2N₃ که در آن N₃ اول و به همین ترتیب تا آخر. در چنین مواردی، با فرض این که زنجیرهٔ اعداد اول تا یک مقدار محدود ادامه یابد، برنامه‌های بازگشتی الگوریتم ریدر در واقع به( O(N² زمان نیاز دارد. چنین N_j اعداد اول سوفی ژرمن نامیده می‌شوند، و چنین دنباله‌ای از آن‌ها زنجیره کانینگهام از نوع اول است. طول زنجیره کانینگهام، با این حال، مشاهده شده که آرام تر از( log₂(N رشد می‌کند، بنابراین الگوریتم ریدری که به این صورت پیاده‌سازی شده باشد احتمالاً( O(N log N نیست، هر چند احتمالاً برای بدترین مورد بدتر از( O(N log N بوده‌است. اما خوشبختانه، با پدینگ صفر پیچیدگی( O(N log N را می‌توان تضمین کرد.