خوارزمية رادر لتحويل فورييه السريع

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 15 صور
الموسوعة الحرة

خوارزمية رادر (1968)، [ 1 ] سميت على اسم تشارلز إم. رادر من مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا ، هي خوارزمية تحويل فورييه سريع (FFT) تحسب تحويل فورييه المنفصل (DFT) للأحجام الأولية عن طريق إعادة التعبير عن DFT على شكل التفاف دوري (الخوارزمية الأخرى لتحويل فورييه السريع للأحجام الأولية، خوارزمية بلوستين ، تعمل أيضًا عن طريق إعادة كتابة DFT على شكل التفاف).

بما أن خوارزمية رادر تعتمد فقط على دورية نواة DFT، فإنها قابلة للتطبيق مباشرة على أي تحويل آخر (من رتبة أولية) له خاصية مماثلة، مثل التحويل النظري للأعداد أو تحويل هارتلي المنفصل .

يمكن تعديل الخوارزمية لتحقيق توفير بمقدار الضعف في حالة تحويلات فورييه المنفصلة للبيانات الحقيقية، باستخدام إعادة فهرسة/تبديل معدل قليلاً للحصول على عمليتي التفاف دوري بنصف الحجم للبيانات الحقيقية؛ [ 2 ] يستخدم تعديل بديل لتحويلات فورييه المنفصلة للبيانات الحقيقية تحويل هارتلي المنفصل . [ 3 ]

قام وينوغراد بتوسيع خوارزمية رادر لتشمل أحجام DFT ذات القوى الأوليةصم{\displaystyle p^{m}}[ 4 ] [ 5 ] ويُشار إلى خوارزمية رادر اليوم أحيانًا بأنها حالة خاصة من خوارزمية وينوغراد لتحويل فورييه السريع ، والتي تُسمى أيضًا خوارزمية تحويل فورييه المضاعف (توليمييري وآخرون، 1997)، [ 6 ] والتي تُطبق على فئة أكبر من الأحجام. مع ذلك، بالنسبة للأحجام المركبة مثل قوى الأعداد الأولية، تُعد خوارزمية كولي-توكي لتحويل فورييه السريع أبسط بكثير وأكثر عملية في التنفيذ، لذا تُستخدم خوارزمية رادر عادةً فقط لحالات الأساس للأعداد الأولية الكبيرة في تحليل كولي-توكي التكراري لتحويل فورييه المنفصل. [ 3 ]

الخوارزمية

تمثيل مرئي لمصفوفة تحويل فورييه المنفصل (DFT) في خوارزمية تحويل فورييه السريع (FFT) لرادر. تتكون المصفوفة من ساعات ملونة تمثل مصفوفة DFT بحجم 11. من خلال تبديل الصفوف والأعمدة (باستثناء العمود الأول من كل منهما) وفقًا للمتتاليات الناتجة عن قوى الجذر الأولي للعدد 11، تصبح مصفوفة DFT الأصلية مصفوفة دائرية . ضرب متتالية بيانات بمصفوفة دائرية يكافئ الالتفاف الدوري مع متجه صف المصفوفة. هذه العلاقة مثال على أن المجموعة الضربية دورية.(Z/صZ)×≅جص-1{\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }\cong C_{p-1}}.

ابدأ بتعريف تحويل فورييه المنفصل:

Xك=∑ن=0شمال-1xنهـ-2πأناشمالنكك=0،...،شمال-1.{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}

إذا كان N عددًا أوليًا، فإن مجموعة المؤشرات غير الصفريةن∈{1،...،شمال-1}{\displaystyle n\in {}\{1,\dots ,N-1\}}تشكل زمرة تحت عملية الضرب بتردد N. ومن نتائج نظرية الأعداد لهذه الزمر وجود مولد لهذه الزمرة (يُسمى أحيانًا الجذر الأولي ، والذي يمكن إيجاده عن طريق البحث الشامل أو باستخدام خوارزميات أفضل قليلًا [ 7 ] ). هذا المولد هو عدد صحيح g بحيثن=زq(تعديلشمال){\displaystyle n=g^{q}{\pmod {N}}}لأي فهرس غير صفري n ولـ فريدq∈{0،...،شمال-2}{\displaystyle q\in {}\{0,\dots ,N-2\}}(تشكيل تقابل من q إلى n غير الصفري ). وبالمثل،ك=ز-ص(تعديلشمال){\displaystyle k=g^{-p}{\pmod {N}}}لأي مؤشر غير صفري k ولـ فريدص∈{0،...،شمال-2}{\displaystyle p\in {}\{0,\dots ,N-2\}}حيث يشير الأس السالب إلى المعكوس الضربي لـزصتعديلشمال{\displaystyle g^{p}\mod N}وهذا يعني أنه يمكننا إعادة كتابة تحويل فورييه المنفصل باستخدام هذين المؤشرين الجديدين p و q على النحو التالي:

X0=∑ن=0شمال-1xن،{\displaystyle X_{0}=\sum _{n=0}^{N-1}x_{n},}
Xز-ص=x0+∑q=0شمال-2xزqهـ-2πأناشمالز-(ص-q)ص=0،...،شمال-2.{\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 ، وأيضًا أنهـ2πأنا=1{\displaystyle e^{2\pi i}=1}( هوية أويلر ). وبالتالي، يتم أخذ جميع المؤشرات والأسس بتردد N كما هو مطلوب في حساب المجموعة.

المجموع النهائي، أعلاه، هو بالضبط التفاف دوري للمتتاليتين a q و b q (بطول N – 1، لأنq∈{0،...،شمال-2}{\displaystyle q\in {}\{0,\dots ,N-2\}}) مُعرَّف بواسطة:

أq=xزq{\displaystyle a_{q}=x_{g^{q}}}
بq=هـ-2πأناشمالز-q.{\displaystyle b_{q}=e^{-{\frac {2\pi i}{N}}g^{-q}}.}

تقييم عملية الالتفاف

بما أن N – 1 عدد مركب، يمكن إجراء هذا الالتفاف مباشرةً باستخدام نظرية الالتفاف وخوارزميات تحويل فورييه السريع التقليدية. مع ذلك، قد لا يكون ذلك فعالاً إذا كان N – 1 نفسه يحتوي على عوامل أولية كبيرة، مما يستدعي استخدام خوارزمية رادر بشكل متكرر. بدلاً من ذلك، يمكن حساب التفاف دوري بطول ( N – 1) بدقة عن طريق إضافة أصفار إلى طوله ليصبح 2( N – 1) – 1 على الأقل، ولنقل إلى قوة من قوى العدد 2 ، والذي يمكن تقييمه بعد ذلك في زمن O( N log N ) دون الحاجة إلى تطبيق خوارزمية رادر بشكل متكرر.

تتطلب هذه الخوارزمية، بالتالي، O( N ) عملية جمع بالإضافة إلى O( N log N ) من الوقت اللازم لعملية الالتفاف. عمليًا، يمكن غالبًا إجراء عمليات الجمع O( N ) عن طريق دمجها في عملية الالتفاف: إذا تم إجراء الالتفاف بواسطة زوج من تحويلات فورييه السريعة (FFT)، فإن مجموع x<sub> n </sub> يُعطى بواسطة خرج التيار المستمر (الصفري) لتحويل فورييه السريع لـ q زائد x <sub> 0 </sub>، ويمكن إضافة x<sub> 0 </sub> إلى جميع المخارج بإضافته إلى حد التيار المستمر لعملية الالتفاف قبل تحويل فورييه السريع العكسي. مع ذلك، تتطلب هذه الخوارزمية عمليات أكثر بطبيعتها من تحويلات فورييه السريعة ذات الأحجام المركبة القريبة، وعادةً ما تستغرق من 3 إلى 10 أضعاف الوقت عمليًا.

إذا تم تنفيذ خوارزمية رادر باستخدام تحويلات فورييه السريعة (FFT) بحجم N – 1 لحساب الالتفاف، بدلاً من استخدام التصفير كما ذُكر سابقًا، فإن الكفاءة تعتمد بشكل كبير على N وعدد مرات تطبيق خوارزمية رادر بشكل متكرر. أسوأ حالة هي عندما يكون N – 1 مساويًا لـ 2N² حيث N² عدد أولي، و N² – 1 مساويًا لـ 2N³ حيث N³ عدد أولي ، وهكذا. تُسمى هذه الأعداد Nⱼ بأعداد صوفي جيرمان الأولية ، ويُطلق على هذا التسلسل منها اسم سلسلة كننغهام من النوع الأول. مع ذلك، يمكن دائمًا استخدام التصفير كبديل إذا كان N – 1 يحتوي على عامل أولي كبير.

مراجع

  1. ↑ CM Rader، "تحويلات فورييه المنفصلة عندما يكون عدد عينات البيانات أوليًا"، وقائع IEEE 56، 1107-1108 (1968).
  2. ↑ S. Chu and C. Burrus, "A prime factor FTTalgorithm using distributed arithmetic," IEEE Transactions on Acoustics, Speech, and Signal Processing 30 (2), 217 – 227 (1982).
  3. 1 2 ماتيو فريجو وستيفن جي جونسون ، " تصميم وتنفيذ FFTW3 "، وقائع IEEE 93 (2)، 216-231 (2005).
  4. ↑ S. Winograd, "حول حساب تحويل فورييه المنفصل"، وقائع الأكاديمية الوطنية للعلوم بالولايات المتحدة الأمريكية ، 73 (4)، 1005 – 1006 (1976).
  5. ↑ S. Winograd, "حول حساب تحويل فورييه المنفصل"، رياضيات الحساب ، 32 (141)، 175 – 199 (1978).
  6. ↑R. Tolimieri, M. An, and C.Lu, Algorithms for Discrete Fourier Transform and Convolution, Springer-Verlag, 2nd ed., 1997.
  7. ↑Donald E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd edition, section 4.5.4, p. 391 (Addison–Wesley, 1998).