الـ decimation (التخفيض) | DSP-101

تقليل معدل البيانات

كل signal رقمية ليها sampling rate — عدد الـ samples اللي بتتجمع في الثانية. وكتير المعدل ده بيبقى أعلى من اللي التطبيق محتاجه. الـ receiver اللاسلكي العريض النطاق بيعمل digitizing بـ 100 ميجاهرتز مع إن الـ signal المطلوبة واخدة 200 كيلوهرتز بس. ومحطة معالجة الصوت بتسجّل بـ 96 كيلوهرتز مع إن الناتج النهائي هيتشغّل بـ 44.1 كيلوهرتز. وفي الحالتين، إنك تشيل samples زيادة بيضيّع الـ memory والتخزين وطاقة المعالجة. والـ decimation (التخفيض) هو العملية المنهجية لتقليل الـ sampling rate بإنك تشيل samples بطريقة رياضية مظبوطة.

الـ decimation بمعامل M معناه إنك تحتفظ بكل sample رقم M وتشيل الباقي؛ والناتج signal بمعدل 1/M من المعدل الأصلي. بس فيه تحذير حاسم: متقدرش ترمي الـ samples وخلاص من غير ما تشيل الـ frequencies اللي هتعمل aliasing (الالتباس الترددي) في الـ signal اللي معدلها أقل. وإنك تعمل الخطوة دي صح هو جوهر الـ decimation.

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

الـ decimation بمعامل M = anti-aliasing low-pass filter وبعده إنك تحتفظ بكل sample رقم M. والـ filter إجباري — لو نسيته بيدخل aliasing بيبوّظ الـ signal على طول.

الـ decimation الساذج: إيه اللي بيحصل؟

افترض إن معاك signal بمعدل f_s = 8 كيلوهرتز وعايز تعمل لها decimation لـ 2 كيلوهرتز (M = 4). الطريقة الساذجة: احتفظ بالـ sample 0، وارمي الـ samples 1 و2 و3، وبعدين احتفظ بالـ sample 4، وهكذا. والسلسلة الخارجة هي y[n] = x[4n].

المشكلة هي نظرية Nyquist متطبّقة على المعدل الجديد. عند 2 كيلوهرتز، متقدرش تمثّل غير الـ frequencies اللي أقل من 1 كيلوهرتز من غير aliasing. بس الـ signal الأصلية اللي بـ 8 كيلوهرتز ممكن يبقى فيها طاقة لحد 4 كيلوهرتز. ولما تحتفظ بكل sample رابعة، كل حاجة فوق الـ Nyquist الجديد (1 كيلوهرتز) بتتطوي حوالين المعدل الجديد (2 كيلوهرتز): مكوّن عند 2.5 كيلوهرتز بيستقر عند |2500 − 2000| = 500 هرتز في الخرج — فوق مكوّن الـ 500 هرتز الأصلي. وبيختلطوا بشكل مينفعش يتفصل، والتلوّث ده مالوش رجوع؛ مفيش معالجة بعدين تقدر تلغي الـ aliasing بعد ما يحصل.

الـ decimation

y[n] = x[Mn]

السلسلة اللي اتعملها decimation y[n] بتتاخد بإنك تحتفظ بكل sample رقم M من x[n]. وفي الـ frequency domain الـ spectrum بيتضغط بمقدار M وبيتجمع M نسخة — وده بيعمل aliasing لو الـ signal مكانتش band-limited عند π/M.

الـ anti-aliasing filter

الحل واضح من حيث المبدأ: قبل الـ decimation بمعامل M، طبّق low-pass filter بـ cutoff frequency f_c = f_s/(2M). ده بيشيل كل الطاقة عند حد الـ Nyquist الجديد أو فوقه، فمفيش حاجة بتفضل تعمل aliasing. والـ decimator الكامل بيتكوّن من مرحلتين ورا بعض: الأول الـ low-pass filter، وبعدين الـ sample selector.

الـ cutoff frequency

f_c = \frac{f_s}{2M} \quad\Leftrightarrow\quad \omega_c = \frac{\pi}{M}

الـ anti-aliasing filter لازم يقطع عند الـ Nyquist frequency بتاعة معدل الخرج أو أقل — يعني f_c = f_s/(2M)، وده نص الـ sampling rate بتاع الخرج f_s/M. (وفرّق بين المصطلحين: الـ Nyquist rate هو أقل sampling rate وقيمته 2f_max؛ أما الـ Nyquist frequency فهي أعلى frequency ممكن تتمثّل، وقيمتها نص الـ sampling rate. ولو قسمنا الـ Nyquist frequency على اتنين هنا، الـ cutoff هينزل octave كاملة.) وبالـ digital frequency المتطبّعة (راديان/sample على المعدل الأصلي)، الـ cutoff هو π/M.

الـ anti-aliasing filter ممكن يبقى FIR أو IIR. ولأغلب تطبيقات الـ decimation، الـ FIR filters هي الأحسن لأنها بتدّي linear phase (من غير تشويه شكل الموجة)، واستقرار مضمون، وتصميم مباشر.

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

للـ decimation بمعامل M، صمّم FIR low-pass filter بـ cutoff ω_c = π/M (راديان/sample على معدل الدخل). ودرجة الـ filter بتحدّد المقايضة بين حدّة الـ transition band والتكلفة الحسابية: taps أكتر ← roll-off أحدّ بس ضرب أكتر لكل sample دخل.

إيه اللي بيحصل في الـ frequency domain

منظور الـ frequency domain بيخلّي الـ decimation بديهي. الـ signal اللي الـ spectrum بتاعها واخد النطاق [0, π/M] راديان/sample (بعد ما الـ filter يشيل كل حاجة فوقه) — لما نحتفظ بكل sample رقم M، الـ DTFT بتاع الخرج بيبقى مجموع M نسخة متزحزحة من spectrum الدخل، كل واحدة مقسومة على M:

spectrum الـ signal اللي اتعملها decimation

Y\!\left(e^{j\omega}\right) = \frac{1}{M}\sum_{k=0}^{M-1} X\!\left(e^{j(\omega - 2\pi k)/M}\right)

spectrum الخرج Y(e^jω) هو مجموع M نسخة متزحزحة في الـ frequency من spectrum الدخل المترشّح، وبينهم مسافة 2π/M. ولو الدخل band-limited عند π/M، النسخ دي مبتتداخلش — مفيش aliasing.

لأن الـ anti-aliasing filter بيضمن إن spectrum الدخل صفر فوق π/M، فالـ M نسخة في المجموع مبيتداخلوش. وspectrum الخرج نسخة ممطوطة من الـ passband بتاع الـ signal — الـ frequencies اللي كانت في [0, π/M] دلوقتي بتتمد عشان تاخد [0, π] عند المعدل الجديد (الأقل). والـ signal بتتضغط طيفيًا: نفس المعلومات بتاخد الـ bandwidth الكامل للـ signal الخارجة.

1/M

معدل الخرج بالنسبة للدخل

π/M

أقصى cutoff آمن (راديان/sample)

M×

معامل المط الطيفي في الخرج

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

الـ decimator الساذج بيحسب كل samples خرج الـ filter وبعدين بيرمي M−1 من كل M — هدر واضح. والـ polyphase decomposition (التحليل متعدد الأوجه) بيستغل بنية الـ decimation عشان ميحسبش الـ samples اللي هتترمي.

الـ FIR filter اللي طوله N بيتقسم لـ M sub-filter (فروع polyphase)، كل واحد طوله تقريبًا N/M. والفرع k فيه معاملات الـ filter عند الـ indices k، k+M، k+2M، ... . وللـ decimator، فرع واحد بس هو اللي بيلزم لكل sample خرج — فالحساب بيقل بمعامل M. والتكلفة الكلية بتنزل من N عملية ضرب لكل sample دخل لحوالي N/M لكل sample خرج.

الـ polyphase decomposition

E_k[n] = h[nM + k], \quad k = 0, 1, \ldots, M-1

الـ filter h[n] بيتحلّل لـ M فرع polyphase E_k[n] = h[nM + k]. كل فرع بيشتغل على المعدل الأقل بتاع الخرج، وده بيقلّل الحساب بمعامل M.

اعتبارات عملية

الـ decimation الصحيح قصاد الكسري: المعامل M لازم يبقى عدد صحيح موجب. وللـ decimation بنسبة مش صحيحة (مثلًا 44.1 كيلوهرتز لـ 32 كيلوهرتز = 320:441)، بتجمع الـ upsampling والـ decimation: اعمل upsampling الأول بمعامل L، وبعدين decimation بمعامل M، وتختار L وM بحيث L/M تبقى النسبة المطلوبة. وده اللي اسمه الـ rational sample rate conversion.

الـ multistage decimation: لقيم M الكبيرة (مثلًا M = 64)، الـ FIR filter اللي مرحلة واحدة محتاج معاملات كتير عشان يحقق متطلبات الـ transition band الضيقة. والطريقة متعددة المراحل بتسلسل decimators أصغر (مثلًا decimation بـ 4 وبعدين 4 وبعدين 4) بـ filters أبسط في كل مرحلة، وده بيقلّل التكلفة الكلية جامد.

الـ CIC filters للـ decimation الشديد: الـ CIC filters (Cascaded Integrator-Comb) بنية حسابية من غير ضرب، مثالية لنسب decimation عالية جدًا (M = 256 أو أكتر). وبتتستخدم كتير في محوّلات الـ ΣΔ والـ front-ends بتاعة الـ SDR.

الدرس الجاي: الـ interpolation (الاستيفاء) / الـ upsampling — العملية العكسية: إنك تدخّل samples عشان تعلّي المعدل، مع anti-imaging filter بيمنع ظهور نسخ طيفية في الخرج.

أهم النقط

الـ decimation بمعامل M بيقلّل الـ sampling rate بمعامل M بإنك تحتفظ بكل sample رقم M؛ وهو الأداة الأساسية لتقليل معدل البيانات في الـ multirate signal processing.
الـ decimation الساذج بيعمل aliasing: النسخ الطيفية بتتداخل وبتبوّظ الـ signal على طول. والـ anti-aliasing low-pass filter (cutoff π/M) إجباري قبل الـ decimation.
في الـ frequency domain، الـ decimation بمعامل M بيمط الـ spectrum بمقدار M وبيجمع M نسخة متزحزحة؛ ولو الـ signal band-limited عند π/M، النسخ مبتتداخلش.
الـ polyphase decomposition بيلغي الحساب الضايع بإنه بيشغّل الـ filter على المعدل الأقل بتاع الخرج، فبينزّل التكلفة بمعامل M تقريبًا.
نسب الـ decimation الكبيرة بتتنفّذ بكفاءة على مراحل ورا بعض؛ والـ CIC filters بتتعامل مع الـ decimation الشديد (M بالمئات) من غير ضرب.
الـ decimation هو النص الأول من الـ sample rate conversion؛ والنسب المش صحيحة بتجمع الـ decimation مع الـ interpolation للتحويل بين أي sample rates.