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

خوارزمية برون هي خوارزمية تحويل فورييه سريع (FFT) تعتمد على أسلوب تحليل متعدد الحدود التكراري غير المألوف ، وقد اقترحها جي. برون عام 1978 لقوى العدد اثنين، ثم عممها إتش. موراكامي عام 1996 لتشمل أحجامًا زوجية مركبة عشوائية. ولأن عملياتها لا تتضمن سوى معاملات حقيقية حتى المرحلة الحسابية الأخيرة، فقد طُرحت في البداية كوسيلة فعالة لحساب تحويل فورييه المنفصل (DFT) للبيانات الحقيقية. مع ذلك، لم تشهد خوارزمية برون انتشارًا واسعًا، إذ تم تكييف مناهج تعتمد على خوارزمية كولي-توكي التقليدية لتحويل فورييه السريع بنجاح مع البيانات الحقيقية بكفاءة لا تقل عن كفاءة خوارزمية كولي-توكي. علاوة على ذلك، تشير الأدلة إلى أن خوارزمية برون قد تكون أقل دقة جوهريًا من خوارزمية كولي-توكي في ظل دقة عددية محدودة ( ستورن، 1993 ) .

ومع ذلك، توضح خوارزمية برون إطارًا خوارزميًا بديلًا يمكنه التعبير عن نفسه وخوارزمية كولي-توكي، وبالتالي يوفر منظورًا مثيرًا للاهتمام حول تحويلات فورييه السريعة التي تسمح بمزيج من الخوارزميتين وتعميمات أخرى.

تذكر أن تحويل فورييه المنفصل (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 ⁿ ( n = 0, ..., N − 1):       $${\displaystyle \omega _{N}^{n}=e^{-{\frac {2\pi i}{N}}n}}$$ ونعرّف متعددة الحدود x ( z ) التي معاملاتها هي x _n : $${\displaystyle x(z)=\sum _{n=0}^{N-1}x_{n}z^{n}.}$$

ويمكن فهم تحويل فورييه المنفصل (DFT) على أنه اختزال لهذه المعادلة متعددة الحدود؛ أي أن X _k يُعطى بواسطة: $${\displaystyle X_{k}=x(\omega _{N}^{k})=x(z)\mod (z-\omega _{N}^{k})}$$ حيث يرمز mod إلى عملية حساب باقي القسمة على كثير الحدود . يكمن سر الخوارزميات السريعة مثل خوارزمية برون أو كولي-توكي في إمكانية تنفيذ هذه المجموعة من عمليات حساب باقي القسمة N على مراحل متكررة.

لحساب تحويل فورييه المنفصل (DFT)، نحتاج إلى تقييم الجزء المتبقي من${\displaystyle x(z)}$حساب باقي قسمة كثيرات الحدود من الدرجة الأولى N كما هو موضح أعلاه. يُكافئ حساب هذه البواقي واحدة تلو الأخرى حساب صيغة تحويل فورييه المنفصلة (DFT) المعتادة مباشرةً، ويتطلب O( ^N² ) عملية. مع ذلك، يمكن دمج هذه البواقي بشكل متكرر لتقليل التكلفة، باستخدام الحيلة التالية: إذا أردنا حساب${\displaystyle x(z)}$modulo اثنين من كثيرات الحدود${\displaystyle U(z)}$و${\displaystyle V(z)}$يمكننا أولاً أخذ الباقي بتردد حاصل ضربهما${\displaystyle U(z)}$${\displaystyle V(z)}$مما يقلل من درجة متعددة الحدود${\displaystyle x(z)}$ويجعل عمليات حساب باقي القسمة اللاحقة أقل تكلفة حسابية.

حاصل ضرب جميع الحدود الجبرية${\displaystyle (z-\omega _{N}^{k})}$بالنسبة لـ k = 0.. N - 1 يكون ببساطة${\displaystyle z^{N}-1}$(التي جذورها هي بوضوح الجذور العددية للوحدة). ثم يرغب المرء في إيجاد تحليل تكراري لـ${\displaystyle z^{N}-1}$إلى كثيرات حدود ذات عدد قليل من الحدود ودرجات أصغر فأصغر. لحساب تحويل فورييه المنفصل، يتم أخذ${\displaystyle x(z)}$يتم حساب باقي القسمة لكل مستوى من مستويات هذا التحليل بالتتابع، بشكل متكرر، حتى الوصول إلى أحاديات الحدود والنتيجة النهائية. إذا كان كل مستوى من مستويات التحليل يقسم كل متعددة حدود إلى عدد O(1) (محدود بقيمة ثابتة) من متعددات الحدود الأصغر، ولكل منها عدد O(1) من المعاملات غير الصفرية، فإن عمليات باقي القسمة لهذا المستوى تستغرق زمنًا قدره O( N )؛ وبما أن عدد المستويات سيكون لوغاريتميًا، فإن التعقيد الكلي هو O( N log N ).

وبشكل أكثر وضوحاً، لنفترض على سبيل المثال أن${\displaystyle z^{N}-1=F_{1}(ض)F_{2}(ض)F_{3}(ض)}$وذلك${\displaystyle F_{ك}(ض)=F_{ك,1}(ض)F_{ك,2}(ض)}$وهكذا. ستتألف خوارزمية FFT المقابلة من حساب x _k ( z ) = x ( z ) mod F _k ( z )، ثم حساب x _{k , j} ( z ) = x _k ( z ) mod F _{k , j} ( z )، وهكذا، مما يؤدي إلى إنشاء المزيد والمزيد من كثيرات الحدود المتبقية ذات درجات أصغر فأصغر حتى الوصول إلى النتائج النهائية من الدرجة 0.

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

تقوم خوارزمية برون الأساسية لقوى العدد اثنين N = 2 ⁿ بتحليل z ^{2 n} - 1 بشكل متكرر عبر القواعد التالية:

$${\displaystyle ض^{2M}-1=(ض^{M}-1)(ض^{M}+1)\,}$$$${\displaystyle z^{4M}+az^{2M}+1=(z^{2M}+{\sqrt {2-a}}z^{M}+1)(z^{2M}-{\sqrt {2-a}}z^{M}+1)}$$

حيث a ثابت حقيقي بقيمته المطلقة | a | ≤ 2. إذا${\displaystyle a=2\cos(\phi )}$،${\displaystyle \phi \in (0,\pi )}$، ثم${\displaystyle {\sqrt {2+a}}=2\cos {\tfrac {\phi }{2}}}$و${\displaystyle {\sqrt {2-a}}=2\cos({\tfrac {\pi }{2}}-{\tfrac {\phi }{2}})}$.

في المرحلة s ، حيث s = 0، 1، 2، n - 1، تتكون الحالة الوسيطة من 2 ^s من كثيرات الحدود${\displaystyle p_{s,0},\dots ,p_{s,2^{s}-1}}$من الدرجة 2 ^{ن - س} - 1 أو أقل، حيث $${\displaystyle {\begin{aligned}p_{s,0}(z)&=p(z)\mod \left(z^{2^{ns}}-1\right)&\quad &{\text{and}}\\p_{s,m}(z)&=p(z)\mod \left(z^{2^{ns}}-2\cos \left({\tfrac {m}{2^{s}}}\pi \right)z^{2^{n-1-s}}+1\right)&m&=1,2,\dots ,2^{s}-1\end{aligned}}}$$

من خلال بناء تحليل z ^{2 n} - 1 ، فإن كثيرات الحدود p _{s و m} ( z ) تشفر كل منها 2 ^{n - s} قيمة $${\displaystyle X_{k}=p(e^{2\pi i{\tfrac {k}{2^{n}}}})}$$ في تحويل فورييه، بالنسبة لـ m = 0، تكون المؤشرات المغطاة هي k = 0 ، 2k ^، 2∙ ^2s ، 3∙ ^2s ، ...، (2n ^{- s -} 1)∙ ^2s ، وبالنسبة لـ m > 0 تكون المؤشرات المغطاة هي k = m ، 2s ^{+ 1} - m ، 2s ^{+ 1} + m ، 2∙ ^{2s + 1} - m ، 2∙ ^{2s + 1} + m ، ...، ²ⁿ - m .

خلال الانتقال إلى المرحلة التالية، متعددة الحدود${\displaystyle p_{s,\ell }(z)}$يتم اختزالها إلى كثيرات الحدود${\displaystyle p_{s+1,\ell }(z)}$و${\displaystyle p_{s+1,2^{s}-\ell }(z)}$عن طريق قسمة كثيرات الحدود. إذا أردنا الحفاظ على ترتيب كثيرات الحدود تصاعديًا، فإن هذا النمط يتطلب تطبيقًا باستخدام مصفوفتين. ينتج عن التطبيق الحالي تسلسل مؤشرات يمكن التنبؤ به، ولكنه غير مرتب إلى حد كبير، فعلى سبيل المثال، بالنسبة لـ N = 16، يكون الترتيب النهائي للباقي الخطي الثمانية هو (0، 4، 2، 6، 1، 7، 3، 5).

في نهاية التكرار، بالنسبة لـ s = n -1 ، يتبقى 2 ^{n -1} من كثيرات الحدود الخطية التي تشفر معاملين فورييه X ₀ و X _{2 ^{n -1}} للأولى، وبالنسبة لأي كثيرة حدود أخرى k ، المعاملات X _k و X _{2 ⁿ - k} .

في كل مرحلة تكرارية، تُختزل جميع كثيرات الحدود من الدرجة المشتركة 4M⁻¹ إلى جزأين من نصف الدرجة 2M⁻¹ . قاسم حساب باقي هذه كثيرات الحدود هو كثيرة حدود تربيعية zᵐ ^، بحيث يمكن اختزال جميع عمليات الاختزال إلى قسمة كثيرات حدود تكعيبية على كثيرات حدود تربيعية. يوجد N /2 = 2ⁿ⁻¹ من هذه القسمات الصغيرة في كل مرحلة، مما يؤدي إلى خوارزمية O ( N log N ) لتحويل فورييه السريع ⁽ FFT) ^.

علاوة على ذلك، بما أن جميع هذه كثيرات الحدود لها معاملات حقيقية بحتة (حتى المرحلة الأخيرة)، فإنها تستغل تلقائيًا الحالة الخاصة التي تكون فيها المدخلات x_{_n} حقيقية بحتة لتوفير ما يقارب النصف في الحساب والتخزين. ويمكن أيضًا الاستفادة مباشرةً من حالة البيانات المتناظرة الحقيقية لحساب تحويل جيب التمام المنفصل ( تشين وسورنسن ، 1992 ) .