خوارزمية تكرارية تعتمد على البحث العميق لتحويل فورييه السريع للزوج المترافق

تحويل فورييه السريع ذو القاعدة المنقسمة يتمتع بنفس التعقيد الحسابي المنخفض الخاص بتحويل فورييه السريع للزوج المترافق. كلا التحويلين يمتلكان هيكل مسار البيانات غير المنتظم الذي يتم التعبير عنه بشكل مباشر فقط في الأشكال التكرارية. علاوة على ذلك، فإن النسخة الخاصة بالزوج المترافق لها نمط فهرسة مدخلات معقد يتطلب أن تعتمد التطبيقات التكرارية الموجودة على جداول محسوبة مسبقًا. ومع ذلك، فإنها تسمح بتحسين عرض النطاق الترددي للذاكرة حيث تتطلب تحميل عامل التدوير مرة واحدة لكل فراشة من نوع radix-4. في الخوارزميات الموجودة، يأتي ذلك بتكلفة استخدام جداول محسوبة مسبقًا إضافية أو إجراء استدعاءات دوال تكرارية. في هذه الورقة، نقدم مقاربتيْن جديدتيْن تعالجان كل من جدولة الفراشة وتوليد فهرسة المدخلات لتحويل فورييه السريع للزوج المترافق. الخوارزمية المقترحة صديقة للذاكرة لأنها تستند إلى البحث العميق، وغير تكرارية ولا تعتمد على جداول الفهرسة المحسوبة مسبقًا. من أجل تحقيق ذلك، نربط نمط تنفيذ الفراشة لتحويل فورييه السريع ذو القاعدة المنقسمة وتحويل فورييه السريع للزوج المترافق بتسلسل الحمل الثنائي. بناءً على هذه النتيجة، نصف كيف يمكن استخدام العمليات الحسابية الصحيحة الشائعة والعمليات البتية لأداء إعادة ترتيب المدخلات والتنقل في مسار تحويل البيانات بطريقة البحث العميق مع تعقيد مساحة O(1).