رسم تخطيطي للفراشة

في سياق خوارزميات تحويل فورييه السريع ، تُعرف " الفراشة" بأنها جزء من العملية الحسابية يجمع نتائج تحويلات فورييه المنفصلة الأصغر (DFTs) في تحويل فورييه منفصل أكبر، أو العكس (تقسيم تحويل فورييه منفصل أكبر إلى تحويلات فرعية). يُستمد اسم "الفراشة" من شكل مخطط تدفق البيانات في حالة الأساس 2، كما هو موضح أدناه. ^{[ 1 ]} يُعتقد أن أول ظهور موثق لهذا المصطلح في تقرير تقني صادر عن معهد ماساتشوستس للتكنولوجيا عام 1969. ^{[ 2 ] [ 3 ]} ويمكن إيجاد البنية نفسها في خوارزمية فيتربي ، المستخدمة لإيجاد التسلسل الأكثر احتمالاً للحالات المخفية.

يُستخدم مصطلح "الفراشة" عادةً في سياق خوارزمية كولي-توكي لتحويل فورييه السريع (FFT) ، التي تُقسّم تحويل فورييه المنفصل (DFT) ذي الحجم المركب n  = rm إلى r تحويلات أصغر حجمها m، حيث r هو "أساس" التحويل. ثم تُدمج هذه التحويلات الأصغر عبر فراشات حجمها r ، وهي بدورها تحويلات DFT حجمها r (تُجرى m مرة على مخرجات التحويلات الفرعية المقابلة) مضروبة مسبقًا بجذور الوحدة (المعروفة بعوامل التدوير ). (هذه هي حالة "التقليل الزمني"؛ ويمكن أيضًا عكس الخطوات، وهي حالة "التقليل الترددي"، حيث تأتي الفراشات أولًا وتُضرب لاحقًا بعوامل التدوير. انظر أيضًا مقالة كولي-توكي لتحويل فورييه السريع ). 

في حالة خوارزمية كولي-توكي ذات الأساس 2، فإن الفراشة هي ببساطة تحويل فورييه منفصل بحجم 2 يأخذ مدخلين ( x0 _، x1 ) (المخرجات المقابلة للتحويلين الفرعيين) ويعطي مخرجين ( _y0 ، y1 _{) وفقًا} للصيغة (دون تضمين عوامل التدوير ) :  

${\displaystyle y_{0}=x_{0}+x_{1}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}.\,}$

إذا قام المرء برسم مخطط تدفق البيانات لهذا الزوج من العمليات، فإن الخطوط ( x0 _, x1 ₎ إلى ( _y0 , y1 ) _تتقاطع وتشبه أجنحة الفراشة ، ومن هنا جاء الاسم (انظر أيضًا الرسم التوضيحي على اليمين).  

وبشكل أكثر تحديدًا، خوارزمية تحويل فورييه السريع (FFT) ذات أساس 2 مع تقليل عدد المدخلات في الوقت الفعلي على n  =  2^ ^p مدخلًا بالنسبة إلى جذر أولي من الرتبة n للوحدة ${\displaystyle \omega _{n}^{k}=e^{-{\frac {2\pi ik}{n}}}}$يعتمد على O( n  log ₂ n ) من الفراشات بالشكل التالي: 

${\displaystyle y_{0}=x_{0}+x_{1}\omega _{n}^{k}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}\omega _{n}^{k},\,}$

حيث k عدد صحيح يعتمد على جزء التحويل الذي يتم حسابه. في حين أنه يمكن إجراء التحويل العكسي المقابل رياضيًا عن طريق استبدال ω بـ ω ^{− 1} (وربما الضرب بمعامل قياس إجمالي، اعتمادًا على اتفاقية التوحيد القياسي)، يمكن أيضًا عكس الفراشات مباشرة:

${\displaystyle x_{0}={\frac {1}{2}}(y_{0}+y_{1})\,}$

${\displaystyle x_{1}={\frac {\أوميغا _{n}^{-k}}{2}}(y_{0}-y_{1}),\,}$

يتوافق مع خوارزمية FFT ذات التردد المتناقص.

يمكن أيضًا استخدام خوارزمية الفراشة لتحسين عشوائية المصفوفات الكبيرة من الأرقام العشوائية جزئيًا، وذلك بجعل كل كلمة مكونة من 32 أو 64 بت على اتصال سببي مع كل كلمة أخرى من خلال خوارزمية تجزئة مرغوبة، بحيث يكون لتغيير أي بت واحد إمكانية تغيير جميع البتات في المصفوفة الكبيرة. ^{[ 4 ]}

• مخطط رياضي
• معادلة زاسنهاوس
• مخطط تدفق الإشارة

• شرح مخططات تحويل فورييه السريع ومخططات الفراشة .
• مخططات الفراشة لتطبيقات FFT المختلفة (Radix-2، Radix-4، Split-Radix) .