خوارزمية كولي-توكي | DSP-101

فرّق تسد

نشر جيمس كولي وجون توكي خوارزميتهما عام 1965، وهي أكثر خوارزميات تحويل فورييه السريع (FFT) استخداماً حتى اليوم. الفكرة المحورية بسيطة وأنيقة: يمكن تقسيم تحويل فورييه المتقطع (DFT) الكبير إلى تحويلات أصغر، وتُقسَّم هذه بدورها تكرارياً حتى نصل إلى تحويلات بسيطة جداً. تُخفّض هذه الاستراتيجية "فرّق تسد" عدد العمليات من O(N²) إلى O(N log₂ N).

الملاحظة الجوهرية: لإشارة طولها N (حيث N قوة للعدد 2)، يمكن التعبير عن DFT ذي N نقطة بصفته مجموعة من DFT ذي N/2 نقطة — واحد للعينات ذات الفهارس الزوجية وآخر للفهارس الفردية. هذا يُعرف بـالتحلل الزمني (DIT) أو خوارزمية الراديكس-2.

تحلل DIT

X[k] = X_{\text{even}}[k] + W_N^{\,k}\,X_{\text{odd}}[k], \quad k = 0,1,\ldots,N-1

X[k] لـ N نقطة = X_زوجي[k] + معامل التلوين W_N^k × X_فردي[k]. يُقلّص هذا التحليل حجم المشكلة إلى نصفها في كل مستوى تكراري.

عملية الفراشة

خطوة الدمج — ضم X_زوجي[k] وX_فردي[k] لتشكيل X[k] — تتبع نمطاً يُسمى الفراشة (Butterfly). في كل مرحلة، تُدمج أزواج من القيم بضرب واحد مركّب (معامل التلوين) وجمعين. يأتي الاسم من شكل مخطط تدفق الإشارة الذي يشبه أجنحة الفراشة.

الخرج العلوي

X[k] = X_{\text{even}}[k] + W_N^{\,k}\,X_{\text{odd}}[k]

يجمع الزوجي مع الفردي المضروب بمعامل التلوين.

الخرج السفلي

X\!\left[k+\tfrac{N}{2}\right] = X_{\text{even}}[k] - W_N^{\,k}\,X_{\text{odd}}[k]

يطرح — مستغلاً تماثل W^{k+N/2} = −W^k.

لاحظ أن كلا الخرجين يشتركان في نفس حاصل الضرب W_N^k · X_فردي[k]. حساب هذا الضرب مرة واحدة ثم الجمع للحصول على X[k] والطرح للحصول على X[k + N/2] يعني أن كل فراشة تنجز ضرباً مركّباً واحداً وجمعين مركّبين فقط.

استغلال التماثل

بما أن W_N^{k+N/2} = −W_N^k (كما أثبتنا في الدرس 6.1)، يمكن حساب X[k] وX[k+N/2] من نفس زوج خرجَي التحويل الفرعي. كل فراشة تنتج خرجَين بتكلفة ضرب واحد فقط — كفاءة مضاعفة مقارنةً بحساب كل خرج على حدة.

ضرب مركّب 1 + جمعان مركّبان → 2 خرج. الكفاءة: ضعف مقارنة بالحساب المنفصل.

التحليل التكراري — الصورة الكاملة

قوة خوارزمية كولي-توكي تأتي من تطبيق التحليل بشكل تكراري. بعد تقسيم DFT ذي N نقطة إلى DFT-ين كل منهما N/2 نقطة، يُقسَّم كل منهما إلى DFT-ين من N/4 نقطة، وهكذا حتى نصل إلى تحويلات ذات نقطتين (فراشة واحدة بمعامل W = 1).

لـ N = 8 كمثال توضيحي، يحتوي شجرة التكرار على log₂ 8 = 3 مراحل. في كل مرحلة تُحسب N/2 = 4 فراشات. إجمالي العمليات: 3 مراحل × 4 فراشات = 12 ضرباً مركّباً. DFT المباشر يحتاج 64. للمقارنة عند N = 1,024:

طول الإشارة N	DFT المباشر (N²)	FFT كولي-توكي (N/2·log₂N)	التسريع
8	64	12	5×
64	4,096	192	21×
256	65,536	1,024	64×
1,024	1,048,576	5,120	205×
4,096	16,777,216	24,576	683×
1,048,576	~1.1 × 10¹²	~10,485,760	~100,000×

يتنامى التسريع مع N — مما يجعل FFT متفوقاً بصورة متزايدة للتحويلات الكبيرة التي تتطلبها التطبيقات الحديثة. عند N = 2²⁰ ≈ مليون، يكون FFT أسرع بنحو 100,000 مرة.

تبديل عكس البت

يُعيد التقسيم الزوجي-الفردي المتكرر ترتيب عينات الدخل بنمط محدد. بعد log₂ N مرحلة من التقسيم، تنتهي العينات في ترتيب عكس البت: فهرس كل عينة في المصفوفة المعاد ترتيبها هو عكس الفهرس الأصلي ثنائياً. مثال في FFT ذي 8 نقاط: العينة عند الفهرس 3 (ثنائي 011) تنتقل إلى الفهرس 6 (ثنائي 110).

في التطبيق العملي، يُنفَّذ FFT في الموقع (In-Place) بتطبيق هذا التبديل أولاً ثم حساب مراحل الفراشة تكرارياً من الأصغر إلى الأكبر. هذا يلغي تكلفة الذاكرة الإضافية للتكرار العودي.

الحساب في الموقع

يمكن حساب FFT كولي-توكي بالكامل داخل مصفوفة الدخل الأصلية — دون الحاجة لمخزن مساعد. بعد تبديل عكس البت، تكتب كل مرحلة فراشة فوق قيمتَي دخلها قيمتَي الخرج. مع log₂ N مرحلة من N/2 فراشة لكل منها، يبقى إجمالي بصمة الذاكرة N قيمة مركّبة طوال الحساب.

الذاكرة: O(N) — نفس حجم الدخل. لا تخصيص إضافي.

تحليل التعقيد: لماذا O(N log N)؟

عدد العمليات سهل الاشتقاق. في كل مرحلة من مراحل log₂ N تُنجز N/2 عملية فراشة. كل فراشة تكلف ضرباً مركّباً واحداً وجمعين مركّبين. إذن:

تعقيد FFT

T_{\text{FFT}} = \frac{N}{2}\log_2 N \text{ complex multiplications},\quad N\log_2 N \text{ complex additions}

إجمالي الضربات المركّبة: (N/2)·log₂ N. إجمالي الجمعات المركّبة: N·log₂ N. معاً: O(N log₂ N) — تخفيض جذري من O(N²).

الضرب المركّب هو 4 ضربات حقيقية وجمعان حقيقيان — أي 6 عمليات حقيقية. والجمع المركّب هو جمعان حقيقيان. إذاً تكلفة كل فراشة 6 + 2 + 2 = 10 عمليات حقيقية، ومع (N/2)·log₂ N فراشة يحتاج FFT نحو 5·N·log₂ N عملية حقيقية — مقابل 6N² لـ DFT المباشر. ولجميع أطوال الإشارات العملية، FFT أسرع بمراتب كثيرة.

ما وراء الراديكس-2: الراديكس-4 والراديكس المقسّم

خوارزمية الراديكس-2 تقسم كل DFT إلى نصفين. الراديكس-4 يقسم إلى أرباع، مما يُقلّل عمليات الضرب بمعامل التلوين (بعض معاملات التلوين عند مضاعفات N/4 تساوي ±1 أو ±j، ولا تحتاج ضرباً فعلياً). يُحقق FFT الراديكس-4 تقريباً 25% ضربات حقيقية أقل من الراديكس-2 لنفس N.

الراديكس-2 الزمني

الخوارزمية الكلاسيكية

يقسم إلى نصفَين زوجي/فردي. N يجب أن يكون قوة للعدد 2. يحتاج (N/2)·log₂ N ضرباً مركّباً. الأبسط في التطبيق.

الراديكس-2 الترددي

تحلل الترددات

يقسم بنود الخرج بدلاً من عينات الدخل. نفس عدد العمليات للزمني. الدخل بالترتيب الطبيعي؛ الخرج معكوس البت.

الراديكس-4

التقسيم الرباعي

يقسم إلى أربع تحويلات من N/4 نقطة. ضربات معامل تلوين أقل — نحو 25% أقل من الراديكس-2. يتطلب N قوة للعدد 4.

الراديكس المقسّم

الحد الأدنى من الضربات

يستخدم الراديكس-2 للمجموعات الزوجية والراديكس-4 للفردية. يُحقق أدنى عدد معروف من الضربات الحقيقية لأطوال قوى 2.

في التطبيق العملي، يُحقق الراديكس المقسّم الحد النظري الأدنى من الضربات الحقيقية لأطوال قوى 2. وهو الأساس لمكتبات FFT الاحترافية كـ FFTW (أسرع تحويل فورييه في الغرب) التي تختار تلقائياً أمثل تحليل للأجهزة المستهدفة.

ملاحظة تاريخية

كانت خوارزمية كولي-توكي معروفة لكارل فريدريش غاوس حول عام 1805 — قبل أعمال فورييه على التحويلات. استخدمها غاوس لاستيفاء مدارات الكويكبات. أُعيد اكتشافها وانتشرت عام 1965، فحوّلت مجالات من معالجة الصوت إلى التصوير الطبي. وُصفت بأنها من أهم الخوارزميات العددية في القرن العشرين.

يتناول الدرس 6.3 FFT في التطبيق العملي — أحجام قوى 2، الحشو بالأصفار، تحسينات FFT للإشارات الحقيقية القيمة، وطريقة overlap-add لمعالجة الإشارات الطويلة في تطبيقات البث المستمر.

أبرز ما تعلمناه

تقسّم خوارزمية كولي-توكي DFT ذا N نقطة إلى DFT-ين كل منهما N/2 نقطة (الزوجية والفردية)، بشكل تكراري حتى نقطتين.
كل فراشة: ضرب مركّب واحد وجمعان مركّبان تنتج خرجَين — مستغلةً تماثل W^{k+N/2} = −W^k.
التكرار له log₂ N مرحلة، كل منها N/2 فراشة. الإجمالي: (N/2)·log₂ N ضرباً مركّباً — O(N log N) كلياً.
عند N = 1,024: 5,120 ضرباً مركّباً مقابل 1,048,576 في DFT المباشر — تسريع 205 مرة.
الحساب في الموقع عبر تبديل عكس البت — ذاكرة O(N) فحسب.
الراديكس-4 والراديكس المقسّم يُقلّلان الضربات الإضافية، والأخير يُحقق الحد النظري الأدنى.
مكتبات FFT الحديثة (FFTW، Intel IPP، ARM Ne10) تختار تلقائياً أمثل خوارزمية للأجهزة.