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

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

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

الگوریتم ریدر (به انگلیسی: Rader's FFT algorithm) یک الگوریتم تبدیل سریع فوریه(FFT) است که تبدیل فوریه گسسته(DFT) اندازه‌های اول را با ارایه دوباره DFT به عنوان کانولوشن حلقوی، محاسبه می‌کند.(الگوریتم دیگر برای FFT از اندازه های اول، الگوریتم تبدیل سریع فوریه بلوستین است که آن نیز بازنویسی DFT به عنوان یک کانولوشن می باشد.) از آنجا که الگوریتم ریدر تنها به دوره تناوب هسته DFT بستگی دارد، به طور مستقیم با هر تبدیل دیگری (با ترتیب اول) با یک خاصیت مشابه قابل انطباق است، مانند تبدیل نظریه عددی و یا تبدیل گسسته هارتلی. این الگوریتم می تواند با به دست آوردن یک فاکتور از دو ذخیره از DFT ها از داده های حقیقی، با استفاده از حذف یا اندیس گذاری مجددی (re-indexing/permutation) که کمی اصلاح شده، برای به دست آوردن دو نیم-اندازه کانولوشن حلقوی از داده های حقیقی اصلاح شود(چو و Burrus، 1982)؛تطابق جایگزین برای DFT از داده های واقعی، با استفاده از تبدیل گسسته هارتلی،توسط جانسون و فریگو (2007) شرح داده شد. Winograd را گسترش داد تا شامل DFT های توان اول از اندازه p^m شود، و امروزه گاهی الگوریتم ریدر به عنوان مورد خاصی از الگوریتم تبدیل سریع فوریه ی Winograd یاد می شود. همچنین به نام الگوریتم ضرب تبدیل فوریه نیز شناخته می شود، که شامل دسته ی بسیار بزرگتری از اندازه ها می شود.با این حال، در اندازه های مرکب از قبیل توان های اول، الگوریتم تبدیل سریع فوریه کولی-توکی بسیار ساده تر و برای پیاده سازی عملیتر هستند، بنابراین الگوریتم ریدر به طور معمول تنها برای موارد پایه بزرگ اول تجزیه بازگشتی DFT کولی-توکی مورد استفاده قرار می گیرد(جانسون و فریگو (2005).

الگوریتم[ویرایش]

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

 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 = gq (به پیمانه N) برای هر شاخص غیر صفر n و برای q منحصربه‌فرد در 0،...، N - 2 درخواست وجود دارد. به طور مشابه k = gp (به پیمانه N) برای هر k در شاخص غیر صفر و P منحصربه‌فرد در 0،...، N - 2، که در آن توان منفی نشانگر ضرب معکوس gp در پیمانه ی N است. این بدان معنی است که می توانیم DFT را با استفاده از این شاخص های جدید p و q بازنویسی کنیم:

 X_0 =  \sum_{n=0}^{N-1} x_n,
 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.

(به یاد می آورید که xn و Xk به طور ضمنی در N دوره ای هستند، و همچنین e2πi=1. بنابراین، تمام اندیس ها و توان هابه پیمانه N گرفته شده اند، که مورد نیاز گروه محاسباتی است.)

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

a_q = x_{g^q}
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 انجام شود، سپس مجموع xn که از خروجی عبارت صفرام DC FFT بدست می آید aq به علاوه x0 داده می شود و با اضافه کردن آن را به DC از x0 می تواند به تمام خروجی های اضافه شده کانولوشن قبل از FFT معکوس اضافه شود. در عین حال ، این الگوریتم نیاز به عملیات ذاتی بیشتر از FFTs از اندازه مرکب نزدیک خود دارد، و به طور معمول در عمل 3-10 بار به طول می انجامد.

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

منابع[ویرایش]

  • C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE 56, 1107–1108 (1968).
  • S. Chu and C. Burrus, "A prime factor FTT [sic] algorithm using distributed arithmetic," IEEE Transactions on Acoustics, Speech, and Signal Processing 30 (2), 217–227 (1982).
  • Matteo Frigo and Steven G. Johnson, "The Design and Implementation of FFTW3," Proceedings of the IEEE 93 (2), 216–231 (2005).
  • S. Winograd, "On Computing the Discrete Fourier Transform", Proc. National Academy of Sciences USA, 73(4), 1005–1006 (1976).
  • S. Winograd, "On Computing the Discrete Fourier Transform", Mathematics of Computation, 32(141), 175–199 (1978).
  • R. Tolimieri, M. An, and C.Lu, "Algorithms for Discrete Fourier Transform and Convolution," Springer-Verlag, 2nd ed. , 1997.