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

فرّق تسد

جيمس كولي وجون توكي نشروا الخوارزمية بتاعتهم سنة 1965، ولحد النهارده هي أكتر خوارزمية Fast Fourier Transform (تحويل فورييه السريع) أو FFT مستخدمة. والفكرة الأساسية بسيطة وأنيقة: الـ discrete Fourier transform (تحويل فورييه المتقطع) أو DFT الكبير ممكن يتقسم لتحويلات أصغر، والتحويلات دي بتتقسم هي كمان بشكل recursive لحد ما نوصل لتحويلات بسيطة جدًا. واستراتيجية "فرّق تسد" دي بتنزّل عدد العمليات من O(N²) لـ O(N log₂ N).

الملاحظة الجوهرية: لـ signal طولها N (وN قوة لـ 2)، الـ DFT اللي فيه N نقطة ممكن يتكتب كمجموعة من DFTs فيها N/2 نقطة — واحد للـ samples اللي الـ index بتاعها زوجي وواحد للفردي. وده اسمه الـ decimation in time (التحلل الزمني) أو DIT أو خوارزمية الـ radix-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] + الـ twiddle factor W_N^k × X_فردي[k]. والتفكيك ده بيقسم حجم المشكلة على اتنين في كل مستوى recursive.

عملية الـ butterfly

خطوة الدمج — إنك تجمع X_زوجي[k] وX_فردي[k] عشان يطلع X[k] — ماشية على نمط اسمه الـ butterfly (الفراشة). في كل مرحلة، أزواج من القيم بتتدمج بضرب مركّب واحد (الـ twiddle factor) وجمعين. والاسم جاي من شكل الـ signal flow graph اللي شبه جناحات الفراشة.

الخرج اللي فوق

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

بيجمع الزوجي مع الفردي المضروب في الـ twiddle factor.

الخرج اللي تحت

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] معناه إن كل butterfly بتعمل ضرب مركّب واحد وجمعين مركّبين بس.

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

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

ضرب مركّب واحد + جمعين مركّبين → خرجين. الكفاءة: الضعف مقارنةً بالحساب المنفصل.

التفكيك الـ recursive — الصورة الكاملة

قوة خوارزمية كولي-توكي جاية من تطبيق التفكيك بشكل recursive. بعد ما تقسم DFT فيه N نقطة لـ DFTين كل واحد N/2 نقطة، كل واحد فيهم بيتقسم لـ DFTين من N/4 نقطة، وهكذا لحد ما نوصل لتحويلات فيها نقطتين (butterfly واحدة بـ W = 1).

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

طول الـ signal 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 مرة.

الـ bit-reversal permutation

التقسيم الزوجي-الفردي المتكرّر بيعيد ترتيب samples الدخل بنمط معيّن. بعد log₂ N مرحلة تقسيم، الـ samples بتخلص في ترتيب الـ bit-reversal (عكس البت): الـ index بتاع كل sample في الـ array الجديدة هو عكس الـ index الأصلي في الـ binary. مثال في FFT فيه 8 نقط: الـ sample عند الـ index 3 (binary 011) بتروح للـ index 6 (binary 110).

عمليًا، الـ FFT بيتنفّذ in-place (في الموقع) بإنك تعمل الـ permutation ده الأول وبعدين تحسب مراحل الـ butterfly واحدة ورا التانية من الأصغر للأكبر. وده بيلغي تكلفة الـ memory الزيادة بتاعة الـ recursion.

الحساب in-place

FFT كولي-توكي ممكن يتحسب كله جوه array الدخل الأصلية — من غير ما يحتاج buffer مساعد. بعد الـ bit-reversal permutation، كل مرحلة butterfly بتكتب قيمتين الخرج فوق قيمتين الدخل بتوعها. ومع log₂ N مرحلة فيها N/2 butterfly، إجمالي الـ memory بيفضل N قيمة مركّبة طول الحساب.

الـ memory: O(N) — نفس حجم الدخل. مفيش حجز زيادة.

تحليل الـ complexity: ليه O(N log N)؟

عدد العمليات سهل تطلّعه. في كل مرحلة من الـ log₂ N مرحلة بتتعمل N/2 عملية butterfly. وكل butterfly بتكلّف ضرب مركّب واحد وجمعين مركّبين. يبقى:

الـ complexity بتاعة الـ 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 ضرب حقيقي و2 جمع حقيقي — يعني 6 عمليات حقيقية. والجمع المركّب هو 2 جمع حقيقي. فتكلفة كل butterfly 6 + 2 + 2 = 10 عمليات حقيقية، ومع (N/2)·log₂ N butterfly الـ FFT محتاج حوالي 5·N·log₂ N عملية حقيقية — قصاد 6N² للـ DFT المباشر. ولكل أطوال الـ signals العملية، الـ FFT أسرع بمراتب كتير.

أبعد من الـ radix-2: الـ radix-4 والـ split-radix

خوارزمية الـ radix-2 بتقسم كل DFT لنصّين. والـ radix-4 بيقسم لأرباع، وده بيقلّل عمليات الضرب في الـ twiddle factor (شوية twiddle factors عند مضاعفات N/4 بتساوي ±1 أو ±j، ومش محتاجة ضرب فعلي). والـ FFT الـ radix-4 بيوصل لحوالي 25% ضرب حقيقي أقل من الـ radix-2 لنفس N.

الـ radix-2 DIT

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

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

الـ radix-2 DIF

الـ decimation in frequency

بيقسم bins الخرج بدل samples الدخل. نفس عدد العمليات بتاع الـ DIT. الدخل بالترتيب الطبيعي؛ والخرج bit-reversed.

الـ radix-4

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

بيقسم لأربع تحويلات من N/4 نقطة. ضرب twiddle factor أقل — حوالي 25% أقل من الـ radix-2. محتاج N تبقى قوة لـ 4.

الـ split-radix

أقل عدد ضرب

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

عمليًا، الـ split-radix بيوصل للحد الأدنى النظري من الضرب الحقيقي لأطوال قوى الـ 2. وهو الأساس لمكتبات الـ FFT الاحترافية زي FFTW (أسرع تحويل فورييه في الغرب) اللي بتختار لوحدها أحسن تفكيك للـ hardware المستهدف.

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

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

الدرس 6.3 بيتكلّم عن الـ FFT عمليًا — أحجام قوى الـ 2، والـ zero-padding، وتحسينات الـ FFT للـ signals اللي قيمها حقيقية، وطريقة الـ overlap-add لمعالجة الـ signals الطويلة في تطبيقات الـ streaming.

أهم اللي اتعلّمناه

خوارزمية كولي-توكي بتقسم DFT فيه N نقطة لـ DFTين كل واحد N/2 نقطة (الزوجي والفردي)، بشكل recursive لحد نقطتين.
كل butterfly: ضرب مركّب واحد وجمعين مركّبين بيطلّعوا خرجين — مستغلّة التماثل W^{k+N/2} = −W^k.
الـ recursion فيه log₂ N مرحلة، كل واحدة N/2 butterfly. الإجمالي: (N/2)·log₂ N ضرب مركّب — O(N log N) كله.
عند N = 1,024: 5,120 ضرب مركّب قصاد 1,048,576 في الـ DFT المباشر — تسريع 205 مرة.
الحساب in-place عن طريق الـ bit-reversal permutation — memory O(N) بس.
الـ radix-4 والـ split-radix بيقلّلوا الضرب أكتر، والأخير بيوصل للحد الأدنى النظري.
مكتبات الـ FFT الحديثة (FFTW، Intel IPP، ARM Ne10) بتختار لوحدها أحسن خوارزمية للـ hardware.