الـ autocorrelation والـ cross-correlation | DSP-101

قياس التشابه بين الـ signals

الـ signal شبه نسخة متأخّرة منها في الزمن قد إيه؟ وإشارتين مختلفتين بيتطابقوا لحد فين لما تزحزح واحدة فيهم في الزمن؟ الأسئلة دي في قلب عملية الـ correlation (الارتباط)، ودي من أقوى العمليات في الـ digital signal processing. الـ correlation بيقيس العلاقة بين الـ signals على إزاحات زمنية مختلفة، وهو الأساس اللي قايم عليه كل حاجة من كشف الصدى في التسجيلات الصوتية لحد الـ correlation مع قمر GPS بيلف على ارتفاع 20,000 كيلومتر فوقك.

الـ correlation بييجي في شكلين: الـ autocorrelation (الارتباط الذاتي) اللي بيقارن الـ signal بنسخة متأخّرة منها، والـ cross-correlation (الارتباط المتبادل) اللي بيقارن signalين مختلفين. والعمليتين بيطلّعوا دالة في الإزاحة الزمنية، وشكل الدالة دي بيكشف بنية مستخبّية مبتبانش في الـ signals الأصلية.

الفكرة الأساسية

الـ correlation بيقيس قد إيه فيه overlap بين signalين لما واحدة فيهم تعدّي قدّام التانية. قمة موجبة كبيرة عند lag τ معناها تشابه كبير بين الـ signalين عند الإزاحة دي. وقمة عند الـ lag صفر في الـ autocorrelation بتكشف الـ periodicity بتاعة الـ signal.

الـ autocorrelation: الـ signal بتبص على نفسها

الـ autocorrelation للـ signal الـ discrete-time x[n] بيتعرّف إنه الـ inner product بين الـ signal ونسخة متأخّرة منها، مجموع على كل الأزمنة:

الـ autocorrelation

R_{xx}[l] = \sum_{n=-\infty}^{\infty} x[n]\, x[n - l]

R_xx[l] هو الـ autocorrelation عند الـ lag l. بنجمع حاصل ضرب الـ signal في نسخة متأخّرة بمقدار l sample على كل قيم n.

عند الـ lag l = 0، كل sample بتتضرب في نفسها، فـ R_xx[0] بيساوي الطاقة الكلية للـ signal. ودي دايمًا أكبر قيمة الـ autocorrelation بيوصلها — مفيش نسخة متزحزحة من الـ signal تقدر ترتبط بيها أقوى من ارتباط الـ signal بنفسها عند lag صفر.

ودالة الـ autocorrelation زوجية (even) دايمًا: R_xx[l] = R_xx[−l]. والتماثل ده منطقي بالبديهة — التأخير بمقدار l أو بمقدار −l بيدّي نفس درجة التشابه مع النفس.

كشف الـ periodicity

لو x[n] periodic بفترة N، يبقى الـ autocorrelation بتاعها ليه قمم عند الـ lags 0، ±N، ±2N، ... وده بيخلّي الـ autocorrelation أداة ممتازة لكشف الـ periodicities المستخبّية في الـ signals اللي فيها noise — حتى لما الـ periodicity دي متبانش خالص في الموجة في الزمن.

الـ cross-correlation: مقارنة signalين

لما نسأل: «هل الـ signalين دول بيشتركوا في بنية؟» أو «واحدة فيهم شبه التانية قد إيه عند إزاحة معيّنة؟»، بنحسب الـ cross-correlation. للـ signalين x[n] وy[n]:

الـ cross-correlation

R_{xy}[l] = \sum_{n=-\infty}^{\infty} x[n]\, y[n - l]

R_xy[l] هو الـ cross-correlation بين x وy عند الـ lag l. وعكس الـ autocorrelation، الـ cross-correlation عمومًا مش متماثل: R_xy[l] ≠ R_xy[−l].

الـ cross-correlation بيوصل لقمته عند الـ lag اللي الـ signalين بيتطابقوا فيه أحسن تطابق. فلو y[n] هي بس x[n] متأخّرة بمقدار d sample — زي ما بيحصل في الصدى أو في انعكاس multipath — يبقى R_xy[l] هيبقى ليه قمة حادة عند l = d. وده مفتاح الـ time delay estimation.

GPS

بيعمل correlation مع الـ PRN codes عشان يحدّد تأخير القمر الصناعي

سونار

بيقيس المسافة بالـ correlation بين النبضة المبعوتة والمستقبَلة

صوت

بيقدّر خصائص الأوضة عن طريق correlation الانعكاسات

الـ correlation قصاد الـ convolution

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

الـ correlation عن طريق الـ convolution

R_{xy}[l] = x[l] * y[-l]

الـ cross-correlation بين x وy بيساوي الـ convolution بين x والنسخة المقلوبة في الزمن من y، وده بيسمح بحساب كفء بالـ FFT.

والعلاقة دي مهمة عمليًا: معناها إنك تقدر تحسب أي correlation بكفاءة عالية عن طريق الـ FFT. نظرية الـ convolution بتقول إن الـ convolution في الزمن بيساوي الضرب في الـ frequency، ومن هنا الوصفة: احسب الـ FFT لـ x وللنسخة المقلوبة في الزمن من y، اضرب الناتجين نقطة بنقطة، وبعدين خد الـ inverse FFT. والناتج هو الـ cross-correlation، في O(N log N) عملية بدل O(N²).

معامل الـ correlation المتطبّع

قيمة الـ correlation الخام بتعتمد على amplitude الـ signals — فالـ signal العالية بتطلّع قيم correlation أكبر بس عشان الـ samples بتاعتها أكبر، مش عشان هي شبه نفسها أكتر. وعشان نقارن الـ correlation بين signals وسياقات مختلفة، بنطبّع (normalize) النتيجة بإننا نقسمها على جذر حاصل ضرب طاقتين الـ signalين.

الـ cross-correlation المتطبّع

\rho_{xy}[l] = \frac{R_{xy}[l]}{\sqrt{R_{xx}[0]\, R_{yy}[0]}}

الـ cross-correlation المتطبّع ρ_xy[l] دايمًا بيقع في النطاق [−1، +1]. القيمة +1 معناها correlation موجب تام؛ و−1 معناها correlation سالب تام؛ و0 معناها مفيش correlation عند الـ lag ده.

والـ correlation المتطبّع هو المقياس المفضّل لما تحب تعرف هل signalين شبه بعض في الشكل بغض النظر عن الـ amplitude. هتلاقيه في التعرّف على الأنماط، وفي الـ template matching في معالجة الصور، وفي الاتصالات الرقمية اللي الـ receiver فيها بيقارن signal مستقبَلة فيها noise بمكتبة من أشكال الموجات المعروفة.

الخصائص الأساسية

فيه خصائص كتير بتخلّي الـ correlation أداة تحليل تعتمد عليها. القمة عند الـ lag صفر: الـ autocorrelation دايمًا بيوصل لأقصاه عند l = 0، يعني R_xx[0] ≥ |R_xx[l]| لكل قيم l. التماثل: R_xx[l] = R_xx[−l] للـ autocorrelation، وR_xy[l] = R_yx[−l] للـ cross-correlation. الـ linearity: لو y = αx، يبقى الـ cross-correlation بيتضرب في α. العلاقة الطيفية: حسب نظرية وينر-خينتشين، تحويل فورييه للـ autocorrelation بيساوي الـ power spectral density (كثافة الطيف الطاقوي) بتاعة الـ signal — ورابط عميق بين بنية الـ signal في الزمن ومحتواها في الـ frequency.

وينر-خينتشين

S_{xx}(e^{j\omega}) = \sum_{l=-\infty}^{\infty} R_{xx}[l]\, e^{-j\omega l}

الـ autocorrelation ↔ الـ power spectral density عن طريق الـ DTFT.

حد القمة

R_{xx}[0] = \sum_{n} x^2[n] = E_x

الـ autocorrelation عند الـ lag صفر بيساوي الطاقة الكلية للـ signal.

التطبيقات

الـ time delay estimation: في array فيها مايكين، الصوت بيوصل لكل مايك في أوقات مختلفة شوية. ولما تعمل correlation بين signalين المايكين بتظهر قمة عند الـ lag المقابل للتأخير بينهم، ومنها بتتحسب جهة مصدر الصوت. وده أساس الـ beamforming.

الرادار والسونار: الرادار بيبعت نبضة معروفة وبيسجّل الصدى اللي راجع. ولما تعمل correlation بين شكل الموجة المبعوتة والـ signal المستقبَلة بتظهر قمة عند الـ lag اللي بيساوي ضعف مسافة الهدف مقسوم على سرعة الضوء. وارتفاع القمة بيدل على قد إيه الهدف بيعكس، وحدّتها بتدل على دقة تحديد المسافة. واستخدام أشكال موجات طويلة من نوع الـ pulse compression بيسمح إنك تبعت طاقة عالية وتحافظ على دقة مسافة عالية — وكل ده عن طريق الـ correlation.

الـ acquisition بتاع GPS: كل قمر صناعي بيبث code pseudo-random noise (PRN) فريد بيتكرّر كل ملّي ثانية. والـ receiver بتاع GPS بيولّد نسخة محلية من الـ code المتوقّع وبيعمل cross-correlation مع الـ signal المستقبَلة، وهو بيزحلق على كل الإزاحات الزمنية الممكنة. ولما القمة تظهر، الـ receiver بيعرف زمن وصول الـ signal ومنه المسافة بين القمر والـ receiver. وأربع قياسات زي دي من أقمار مختلفة كفاية تحدّد الموقع. ولولا الـ correlation السريع كان الـ GPS اللي نعرفه مستحيل حسابيًا.

معالجة الصوت: الـ autocorrelation بيتستخدم في خوارزميات تقدير الـ pitch (زي AMDF وYIN). الـ fundamental frequency للصوت الـ voiced بتطلّع قمة قوية في الـ autocorrelation عند فترة النغمة الأساسية. وكشف القمة دي أمتن بكتير من إنك تحاول تحدّد الـ pitch على طول من الموجة اللي فيها noise.

الدرس الجاي: الـ signal detection في الـ noise — إزاي تقرّر هل الـ signal موجودة أصلًا، وإيه الأدوات الإحصائية (معيار Neyman-Pearson، منحنيات ROC) اللي بتحكم القرار ده.

أهم النقط

الـ autocorrelation بيقيس تشابه الـ signal مع نسخة متأخّرة منها؛ ودايمًا زوجي وبيوصل لأقصاه عند الـ lag صفر (بيساوي الطاقة الكلية).
الـ cross-correlation بيقيس التشابه بين signalين على الإزاحات؛ والقمة عند l بتشاور على أحسن تطابق بينهم عند إزاحة l sample.
الـ cross-correlation بيساوي الـ convolution بين الـ signal الأولى والعكس الزمني للتانية، وده بيخلّيك تحسبه في O(N log N) بالـ FFT.
التطبيع بطاقتين الـ signalين بيدّي معامل من غير أبعاد في [−1، +1] بيقيس تشابه الشكل بغض النظر عن الـ amplitude.
نظرية وينر-خينتشين بتربط الـ autocorrelation بالـ power spectral density، فبتوحّد البنية في الزمن ومحتوى الـ frequency.
الـ correlation ليه دور محوري في الـ acquisition بتاع GPS، والـ pulse compression في الرادار، والـ time delay estimation في arrays المايكات، وتقدير الـ pitch.