الـ interpolation (الـ upsampling) | DSP-101

زيادة معدل البيانات

الدرس اللي فات اتكلّم عن الـ decimation — يعني تقليل الـ sampling rate بإنك تحتفظ بكل sample رقم M. أما الـ interpolation (الاستيفاء) فهو العملية العكسية: بيزوّد الـ sampling rate بمعامل L، وبيطلّع L sample من كل sample داخلة. وبينما الـ decimation بيرمي samples، الـ interpolation بيعمل samples جديدة.

الحاجة لزيادة الـ sampling rate بتظهر على طول في التطبيقات العملية. الـ digital-to-analog converter (DAC) بيشتغل بدقة أعلى لما يتغذّى بمعدل عالي؛ فإنك تعلّي الـ sampling rate بتاع الصوت 128 مرة قبل التحويل بيقلّل جامد متطلبات الـ analog reconstruction filter. وكمان الـ transmitter بتاع OFDM محتاج يدخّل pilot symbols وguard intervals، وده بيغيّر الـ sampling rate الفعّال ضمنيًا. وفي كل الحالات دي، الـ interpolation بمعامل صحيح L بيدّي الأساس المنهجي.

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

الـ interpolation بمعامل L = إدخال L−1 أصفار بين كل sample، وبعده anti-imaging low-pass filter بـ cutoff π/L وgain L. الأصفار بتعمل spectral images مزيّفة؛ والـ filter بيشيلها وبيسيب الـ signal اللي اتعملها upsampling المطلوبة بس.

الخطوة الأولى — إدخال الأصفار

المرحلة الأولى في الـ interpolator بسيطة في شكلها: دخّل L−1 أصفار بين كل sampleين ورا بعض في الدخل. لو سلسلة الدخل هي x[n]، سلسلة الأصفار المتدخّلة v[m] بتتعرّف كده:

الـ zero insertion (upsampling)

v[m] = \begin{cases} x[m/L] & \text{if } m = 0, \pm L, \pm 2L, \ldots \\ 0 & \text{otherwise} \end{cases}

v[m] هي سلسلة الأصفار المتدخّلة اللي بتشتغل بالمعدل الأعلى Lf_s. ومن كل L index خرج، sample واحدة بس اللي شايلة قيمة حقيقية من الدخل؛ والباقي بيساوي صفر.

ليه أصفار ومش تكرار الـ sample؟ تكرار نفس الـ sample L مرة بيكافئ الضرب في نبضة مستطيلة وده بيعمل تشويه حاد. أما إدخال الأصفار فأنضف رياضيًا: الـ z-transform بتاع v[m] هو V(z) = X(z^L)، وده نسخة مضغوطة في الـ frequency من الـ spectrum الأصلي من غير أي تشويه — بس نسخ طيفية زيادة (images) هتشيلها مرحلة الـ filtering اللي بعدها.

مشكلة الـ spectral images

إدخال الأصفار بيضغط الـ spectrum بمعامل L على محور الـ frequency، وفي نفس الوقت بيعمل L−1 نسخة طيفية من الـ signal الأصلية — اسمها الـ images (الصور) — متباعدة بالتساوي عند مضاعفات 2π/L. والـ images دي أوهام رياضية مش محتوى signal حقيقي، بس هتظهر كنغمات أو تشويه في الخرج لو مااتشالتش.

الـ spectrum بعد إدخال الأصفار

V\!\left(e^{j\omega}\right) = X\!\left(e^{j L\omega}\right)

V(e^jω) = X(e^jLω): spectrum الـ x[n] مضغوط بمعامل L في الـ frequency، ومعاه L−1 image عند 2πk/L للقيم k = 1, 2, ..., L−1.

خد مثال: upsampling بـ L = 4 لـ signal الـ bandwidth بتاعها B. بعد إدخال الأصفار بالمعدل الجديد 4f_s، الـ spectrum فيه النطاق الأصلي زائد تلات images عند إزاحات π/2 وπ و3π/2 راديان. والـ anti-imaging filter بيمسح النسخ التلاتة دي وبيسيب نطاق الـ frequency اللي قريب من الصفر بس — وده الـ signal اللي اتعملها upsampling المطلوبة.

L×

الـ sampling rate بتاع الخرج بالنسبة للدخل

π/L

الـ cutoff بتاع الـ anti-imaging filter (راديان/sample بمعدل الخرج)

L−1

الـ spectral images اللي لازم تتشال

الخطوة التانية — الـ anti-imaging filter

المرحلة التانية هي low-pass filter بـ cutoff ω_c = π/L (محسوب بالـ sampling rate الأعلى) وgain بيساوي L. الـ filter ده بيعدّي النسخة الطيفية الأساسية اللي متمركزة عند الصفر وبيكبت كل الـ L−1 image. وgain الـ filter في الـ passband بيتظبط على L عشان يعوّض نزول الـ amplitude بمعامل L اللي جاي من إدخال الأصفار.

مواصفات الـ anti-imaging filter

H\!\left(e^{j\omega}\right) = \begin{cases} L & |\omega| \le \pi/L \\ 0 & \text{otherwise} \end{cases}

الـ filter المثالي H(e^jω) = L عند |ω| ≤ π/L وصفر غير كده. بيعدّي النطاق المطلوب بـ gain واحد (بعد ما يعوّض النزول 1/L من إدخال الأصفار) وبيشيل كل الـ images.

زي الـ decimation، الـ FIR filters هي الاختيار المعياري للـ interpolation. لأنها linear phase ومستقرة وسهلة التصميم بطريقة الـ windowed-sinc أو Parks-McClellan. ودرجة الـ filter المطلوبة لـ attenuation معيّن في الـ stopband بتعتمد على عرض الـ transition band — كل ما الـ transition band يضيق احتجنا معاملات أكتر.

قاعدة تصميم الـ filter

صمّم FIR low-pass filter بـ gain L وcutoff ω_c = π/L (راديان/sample بمعدل الخرج) مع attenuation كفاية في الـ stopband يكبت الـ spectral images. والـ filter بيشتغل بالمعدل الأعلى Lf_s، فعدد معاملاته بيتضرب على طول في الحمل الحسابي.

الـ filter بيعمل إيه في الـ frequency domain

من منظور الـ frequency domain، الـ interpolation فيه أناقة رياضية. مرحلة إدخال الأصفار بتضغط الـ spectrum وبتكرّره L مرة على [0, 2π]. وبعدين الـ low-pass filter بيختار الحتة اللي في النص بس — اللي متمركزة عند الصفر — وبيكبّرها بمعامل L. والنتيجة signal الـ spectrum بتاعها نسخة متظبّط الـ amplitude بتاعها من الأصل، وبقت واخدة [−π/L, +π/L] جوه النطاق الأوسع [−π, +π] بتاع الـ signal الخارجة.

في الـ time domain، الـ filter بيحسب فعلًا interpolation موزون بين samples الدخل المعروفة. والـ impulse response المثالية h[n] = L · sinc(n/L) هي الـ kernel المثالي للـ interpolation — وعمليًا بتتستخدم نسخة windowed منها. وكل sample خرج مجموع خطي للـ samples اللي جنبها في الدخل، بأوزان شكلها sinc بتوصل لقمتها عند أماكن الـ samples الحقيقية وبتقل بنعومة بينها.

خرج الـ interpolator المثالي

y[m] = \sum_{k} x[k]\, h[m - kL]

الخرج اللي اتعمله interpolation y[m] هو الـ convolution بين سلسلة الأصفار المتدخّلة والـ anti-imaging filter. وعند أماكن الـ samples m = nL الخرج بيساوي x[n] بالظبط؛ وبين samples الدخل الـ filter بيحسب interpolation ناعم موزون بالـ sinc.

التنفيذ الكفء: الـ polyphase decomposition

الـ interpolator الساذج بيحسب الـ anti-imaging filter كله عند معدل الخرج العالي Lf_s، مع إن L−1 من كل L samples دخل بتساوي صفر — وده هدر واضح في عمليات الضرب. والـ polyphase decomposition (التحليل متعدد الطور) بيعيد تنظيم الـ filter عشان يشتغل بمعدل الدخل الأقل.

الـ FIR anti-imaging filter h[n] اللي طوله N بيتقسم لـ L فرع polyphase E_k[n] = h[nL + k] لكل k = 0, 1, ..., L−1. كل فرع فيه حوالي N/L معامل وبيعالج سلسلة الدخل x[n] بالمعدل الأصلي f_s. ونتايج الـ L فرع بيتعملها commutation (بالتناوب) عشان تكوّن stream الخرج بالمعدل الأعلى Lf_s.

الـ polyphase decomposition للـ interpolation

E_k[n] = h[nL + k], \quad k = 0, 1, \ldots, L-1

الـ interpolation filter بيتقسم لـ L فرع polyphase E_k. الفرع k بيطلّع samples الخرج m = nL + k. وكل الفروع بتشتغل بمعدل الدخل f_s، وده بيقلّل الحسابات الكلية بمعامل L مقارنة بالتنفيذ بالمعدل العالي.

الـ polyphase interpolator هو الهيكل المعياري في الـ sample rate converters الصوتية، وسلاسل الـ upsampling للـ DACs، والـ transmitters بتاعة الـ software-defined radio. بيتجنّب كل عمليات الضرب في samples الدخل اللي قيمتها صفر، وتكلفة الـ filter بتبقى متناسبة مع N/L مش N.

التطبيقات العملية

الـ upsampling في الـ DACs: الـ DACs الصوتية بتعلّي الـ sampling rate على طول بمعامل 128 أو 256 قبل التحويل. وتشغيل المحوّل بمعدل عالي جدًا بيبعّد متطلبات الـ analog anti-imaging filter برا نطاق السمع البشري، فبيكفّي roll-off هادي — وده بيبسّط الدواير التناظرية جامد.

الـ pulse shaping في الاتصالات الرقمية: في أنظمة زي 4G LTE أو DVB، stream الـ symbols في الـ baseband بيتعمله upsampling وبعدين بيعدّي على root-raised-cosine (RRC) filter. وخطوة الـ upsampling بتدخّل الـ samples اللازمة بين الـ symbols عشان الـ RRC filter يقدر يشكّل كل نبضة ويقلّل الـ intersymbol interference.

معالجة الصور والفيديو: التكبير والـ super-resolution الاتنين محتاجين interpolation: لازم تخلّق قيم pixels جديدة بين نقط شبكة الـ sampling بتاعة الصورة الأصلية. والـ anti-imaging filter في الـ spatial domain هو المقابل المكاني للـ anti-imaging filter الزمني في الصوت — بيمنع الـ ringing والـ aliasing في الصورة المتكبّرة.

الدرس الجاي: الـ sample rate conversion — الجمع بين الـ upsampling بـ L والـ decimation بـ M عشان تحوّل بأي نسبة كسرية، زي 44.1 كيلوهرتز ↔ 48 كيلوهرتز.

أهم النقط

الـ interpolation بمعامل L بيزوّد الـ sampling rate بإنه بيدخّل L−1 أصفار بين كل sample دخل، وبعدين بيطبّق anti-imaging low-pass filter بـ cutoff π/L وgain L.
إدخال الأصفار بيضغط الـ spectrum وبيعمل L−1 spectral image عند مضاعفات 2π/L؛ ودي أوهام رياضية لازم الـ anti-imaging filter يكبتها.
الـ anti-imaging filter المثالي هو low-pass filter حاد بـ gain L؛ وعمليًا بيتستخدم FIR filter من نوع windowed-sinc أو Parks-McClellan.
الـ polyphase decomposition بيقسم الـ filter لـ L فرع بيشتغلوا بمعدل الدخل، وده بيلغي كل عمليات الضرب في الـ samples الصفرية وبيقلّل التكلفة بمعامل L.
الـ interpolation بيشغّل الـ upsampling في الـ DACs، والـ pulse shaping في الاتصالات الرقمية، والـ super-resolution في الصور — في كل حتة محتاج فيها تخلّق samples خرج أكتر من samples الدخل.
الجمع بين الـ interpolation بـ L والـ decimation بـ M بيخلّيك تعمل sample rate conversion كسري (L/M)، ودي موضوع الدرس الجاي.