الـ convolution (الالتواء) — العملية الأساسية | DSP-101

العملية اللي بتعرّف أنظمة LTI

في الدرس اللي فات أثبتنا إن الـ discrete-time system الـ linear الـ time-invariant (LTI) بيتوصف كله بالـ impulse response (الاستجابة النبضية) بتاعه h[n]. بس إزاي نحسب فعلًا الخرج y[n] لأي دخل x[n]؟ الإجابة هي الـ convolution (الالتواء) — ويمكن تكون أهم عملية رياضية في الـ signal processing كلها.

الـ convolution مش مجرد معادلة تتحفظ. هو طالع طبيعي من حقيقتين عارفينهم قبل كده: أي signal ممكن تتفكّك لمجموع impulses متزحزحة ومتضروبة في أوزان (خاصية الـ sifting)، والرد بتاع نظام LTI على impulse متزحزحة ومتضروبة في رقم هو نسخة متزحزحة ومتضروبة من h[n] (بفضل الـ linearity والـ time invariance). اجمع الحقيقتين ومجموع الـ convolution هيبانلك على طول.

مجموع الـ convolution

y[n] = \sum_{k=-\infty}^{\infty} x[k]\,h[n-k]

y[n] هو خرج نظام LTI الـ impulse response بتاعه h[n] لما ندخّل عليه x[n]. والمجموع ماشي على كل الأعداد الصحيحة k؛ وعمليًا بيبقى محدود لما x أو h تكون مدتها محدودة.

الرمز y[n] = (x * h)[n] بيستخدم النجمة عشان يقول convolution. خد بالك: في معالجة الـ signals المستمرة النجمة ساعات بتعني الـ complex conjugate كمان — بس السياق دايمًا بيشيل اللبس. وفي الـ DSP في الزمن المنفصل، x[n] * h[n] معناها مجموع الـ convolution اللي فوق ده وبس.

مجموع الـ convolution جاي منين؟

نبدأ من خاصية الـ sifting بتاعة الـ unit impulse δ[n]: أي signal x[n] ممكن تتكتب كتراكب من impulses متضروبة في أوزان ومتزحزحة:

نقط مطر بتقع على بركة ساكتة، كل نقطة بتطلّع حلقات موج بتتفرد وتدخل في بعض. — كل نقطة بتطلّع نفس الموجة، على قد حجمها، ومزاحة لحظة ما وقعت. الموجات اللي بتدخل في بعض بتتجمع، والمجموع ده هو الـ convolution.

خاصية الـ sifting

x[n] = \sum_{k=-\infty}^{\infty} x[k]\,\delta[n-k]

كل sample x[k] بتدّي وزن لـ unit impulse مركزها k. والـ signal هي مجموع الـ impulses المتزحزحة دي.

دلوقتي نطبّق عملية نظام LTI T{·} على الطرفين. بفضل الـ linearity، T بتعدّي جوه المجموع ومعاملات التكبير. وبفضل الـ time invariance، الرد على δ[n − k] هو h[n − k] (نسخة من h[n] متزحزحة بـ k). يبقى:

اشتقاق الـ convolution

y[n] = T\!\left\{\sum_k x[k]\,\delta[n-k]\right\} = \sum_k x[k]\,h[n-k]

الـ linearity بتعدّي المجموع جوه T. والـ time invariance بتحوّل T{δ[n−k]} لـ h[n−k]. والنتيجة مجموع الـ convolution — طالع بالاشتقاق مش مفروض.

الاشتقاق ده بيوضّح ليه الـ convolution مش مجرد خوارزمية شاطرة: هو النتيجة اللي مفيش منها مهرب لمعنى إن النظام يبقى LTI. أي نظام linear time-invariant لازم يطلّع خرجه بالـ convolution. ولو مقدرتش تكتب نظام بالشكل ده، يبقى يا nonlinear يا time-varying.

التفسير بالرسم: اقلب، زحزح، اضرب، اجمع

الشعار الرباعي "اقلب، زحزح، اضرب، اجمع" بيوصف إزاي تحسب مجموع الـ convolution عند أي index خرج n. تخيّل إنك بتعدّي نسخة مقلوبة من h فوق x، وبتضرب العناصر اللي قصاد بعض عند كل مكان، وبعدين تجمع النواتج.

الخطوة 1

اقلب

اقلب h في الزمن عشان تاخد h[−k]. ده الـ kernel متشاف "بالعكس" على محور k.

الخطوة 2

زحزح

حرّك الـ kernel المقلوب n sample عشان تاخد h[n−k]. وكل ما n تزيد الـ kernel بيتزحزح يمين.

الخطوة 3

اضرب

احسب حاصل الضرب x[k] · h[n−k] لكل عدد صحيح k.

الخطوة 4

اجمع

اجمع كل النواتج. المجموع هو y[n]، sample خرج واحدة.

كرّر ده لكل قيمة n عشان تبني sequence الخرج كلها. ممكن يبان شغل آلي، بس التفسير بالشكل قوي: الـ convolution بين signal وbox filter (مستطيل من الآحاد) بيحسب متوسط محلّي — كل sample خرج هي متوسط window بتتزحلق. والـ convolution مع derivative kernel بيبرّز التغيّرات المفاجئة. والـ convolution مع echo kernel بيضيف نسخة متأخرة. وأي filter طوله محدود هو نفسه "الـ convolution kernel" بتاعه.

مثال محلول

خلّي x[n] = {1, 2, 3} (مش صفر عند n = 0, 1, 2) وh[n] = {1, 1} (مش صفر عند n = 0, 1). طول الخرج = 3 + 2 − 1 = 4 samples.

y[0] = x[0]h[0] = 1·1 = 1

y[1] = x[0]h[1] + x[1]h[0] = 1·1 + 2·1 = 3

y[2] = x[1]h[1] + x[2]h[0] = 2·1 + 3·1 = 5

y[3] = x[2]h[1] = 3·1 = 3

y[n] = {1, 3, 5, 3} — المجموع المتحرك للـ window اللي فيها عنصرين.

الخصائص الجبرية للـ convolution

الـ convolution ماشي على تلات قوانين جبرية شبه قوانين الضرب العادي، وبتبسّط تحليل الأنظمة المتسلسلة والمتوازية:

الـ commutativity

x[n]*h[n] = h[n]*x[n]

تقدر تعمل الـ convolution بأي ترتيب: x * h = h * x.

الـ associativity

(x*h_1)*h_2 = x*(h_1*h_2)

filterين متسلسلين بيتدمجوا في filter واحد مكافئ.

الـ distributivity

x*(h_1+h_2) = x*h_1 + x*h_2

الـ filters المتوازية بتتدمج: الـ filtering بـ (h₁ + h₂) بيساوي إنك تعمل filtering بـ h₁ وh₂ كل واحد لوحده وتجمع الخرجين.

الـ commutative property (الخاصية الإبدالية) مفاجئة بالذات: بتقول إن تطبيق filter h على signal x بيدّي نفس النتيجة بالظبط زي تطبيق الـ signal x على الـ filter h. التفسيرين بيبانوا مختلفين خالص، بس الرياضيات واحدة. وعمليًا، المهندسين بيختاروا أنهي واحد فيهم يقلبوه ويعدّوه حسب أيهم أرخص في الحساب للـ signals اللي في إيديهم.

الـ associative property (الخاصية الترابطية) هي أساس تصميم الـ filters: نظامين LTI متسلسلين (خرج الأول بيغذّي التاني) بيتصرّفوا كنظام LTI واحد الـ impulse response بتاعه h₁ * h₂. ومعنى كده إن ترتيب الـ filters المتسلسلة مبيأثّرش على الخرج النهائي، وإنك تقدر تحسب سلسلة filters كاملة مقدّمًا وتدمجها في kernel واحد قبل التشغيل.

الـ convolution مع الـ impulse: العملية المحايدة

الـ unit impulse δ[n] هي العنصر المحايد للـ convolution، زي ما الضرب في 1 بيسيب الرقم زي ما هو:

محايد الـ convolution

x[n]*\delta[n] = x[n]

الـ convolution بين أي signal والـ unit impulse بيرجّع الـ signal من غير تغيير. ونظام LTI عنده h[n] = δ[n] هو الـ identity system — بيعدّي أي signal من غير تعديل.

وبشكل أعم، الـ convolution مع impulse متزحزحة δ[n − n₀] بيطلّع delay صافي: x[n] * δ[n − n₀] = x[n − n₀]. وده بيقولّنا إن الـ delay line المثالي نظام LTI الـ impulse response بتاعه sample واحدة عند الزمن n₀. وكل memory تأخير رقمية وكل وحدة echo وكل reverb processor مبني على المبدأ ده.

طول الخرج والـ complexity الحسابية

لما x[n] يكون فيها N sample مش صفر وh[n] فيها M sample مش صفر، الـ convolution y[n] = x * h بيبقى فيه N + M − 1 sample مش صفر بالظبط. وسهل تشوف ده: أول sample خرج مش صفر بتظهر في اللحظة اللي أول sample مش صفر في x بتقابل فيها أول sample مش صفر في h، وآخر sample بتظهر في اللحظة اللي آخر sample مش صفر في كل واحد فيهم بتعدّي التانية.

طول الخرج

L_y = N + M - 1

signal طولها N مع kernel طوله M بيطلّعوا خرج طوله N + M − 1. ولـ IIR filter (M لانهائي) الخرج بيمتد للانهاية.

الحساب المباشر لمجموع الـ convolution محتاج حوالي N · M عملية multiply-accumulate — يعني O(N·M) في الإجمالي. ومع الـ signals الطويلة والـ filters الطويلة ده بيبقى مكلّف. والـ Fast Fourier Transform (تحويل فورييه السريع) أو FFT بيخلّيك تحسبه في O((N+M) log(N+M)) عملية عن طريق الـ convolution theorem (مبرهنة الالتواء) اللي بتقول إن الـ convolution في الـ time domain بيساوي الضرب نقطة بنقطة في الـ frequency domain. والـ FFT convolution ده هو حصان الشغل في معالجة الصوت الحديثة، وfiltering الصور، وأنظمة الاتصالات.

الـ convolution المباشر قصاد الـ FFT

لمقطع صوت مدته ثانية واحدة عند 44,100 هرتز (N = 44,100 sample) متعمله filtering بـ room impulse response مدته 0.5 ثانية (M = 22,050 sample)، الـ convolution المباشر محتاج حوالي 44,100 × 22,050 ≈ 972 مليون عملية ضرب. والـ FFT convolution بينزّلها لحوالي (66,150) × log₂(66,150) ≈ 1.1 مليون عملية — أسرع بحوالي 1000 مرة. وعمليًا، طريقة الـ overlap-add أو الـ overlap-save بتطبّق الـ FFT convolution على blocks ورا بعض من الـ stream.

مباشر: O(N·M) | FFT: O((N+M) log(N+M))

FIR وIIR: عيلتين من أنظمة LTI

الـ convolution بيقسم أنظمة LTI طبيعي لعيلتين حسب مدة الـ impulse response:

أنظمة FIR (الـ finite impulse response، الاستجابة النبضية المنتهية) الـ impulse response بتاعها h[n] مش صفر غير لعدد محدود من الـ samples. ومجموع الـ convolution بتاعها محدود — سهل تحسبه مباشرة ومضمون إنه مستقر. الـ moving average filters والـ matched filters وأغلب الـ filters المتصمّمة بالـ windows كلها FIR. والخرج عند أي لحظة n معتمد على window محدودة من الدخلات اللي فاتت.

أنظمة IIR (الـ infinite impulse response، الاستجابة النبضية اللانهائية) الـ impulse response بتاعها ممتد للانهاية. وعادةً بتتنفّذ بـ difference equations مش بالـ convolution المباشر، لأن جمع عدد لانهائي من الحدود مش عملي. خد recursive filter من الدرجة الأولى: y[n] = αy[n−1] + x[n]. الـ impulse response بتاعه h[n] = αⁿu[n] — بيصغر exponential بس عمره ما بيخلص فعلًا. والـ IIR filters تقدر توصل لانتقائية حادة في الـ frequency بمعاملات أقل بكتير من الـ FIR filters المكافئة، بس محتاجة تحليل استقرار دقيق (|α| < 1 في المثال اللي فوق).

خرج FIR

y[n] = \sum_{k=0}^{M-1} h[k]\,x[n-k]

مجموع محدود على M معامل. مستقر دايمًا؛ وبيسمح بـ linear phase.

الـ difference equation بتاعة IIR

y[n] = \alpha\,y[n-1] + x[n]

recursive: الخرج معتمد على خرجات فاتت. مستقر لما |α| < 1.

الدرس الجاي بيدخل بعمق في الـ impulse response وأنظمة LTI: إزاي أي نظام LTI بيتوصف بـ h[n]، وإزاي difference equations الـ FIR والـ IIR بتطلّع الـ impulse responses بتاعتها، وإزاي الأنظمة المتسلسلة والمتوازية بتتجمع.

أهم النقط

الـ convolution y[n] = Σ x[k]·h[n−k] هو معادلة الخرج الأساسية لأي نظام LTI؛ وطالع على طول من الـ linearity والـ time invariance وخاصية الـ sifting.
الطريقة الرباعية بالرسم — اقلب h، زحزحه بمقدار n، اضربه في x نقطة بنقطة، اجمع — بتدّي تفسير بالحدس لحساب الـ convolution عند كل index خرج.
الـ convolution commutative (x*h = h*x)، وassociative ((x*h₁)*h₂ = x*(h₁*h₂))، وdistributive على الجمع.
الـ unit impulse δ[n] هي المحايد: x[n] * δ[n] = x[n]؛ والـ impulse المتزحزحة δ[n−n₀] بتمثّل delay صافي.
الـ convolution بين signal طولها N وkernel طوله M بيطلّع خرج طوله N+M−1؛ والـ complexity المباشرة O(N·M)، وبالـ FFT بتنزل لـ O((N+M)log(N+M)).
أنظمة FIR الـ impulse response بتاعها محدود ومضمونة الاستقرار؛ وأنظمة IIR الـ impulse response بتاعها لانهائي، بتتنفّذ بالـ recursion ومحتاجة تتأكد من استقرارها.