الالتفاف كضرب مصفوفات

الإشارات والعمليات الخطية

الالتفاف هو العملية الأساسية لأنظمة LTI الخطية الثابتة زمنيًا. بالنظر إلى إشارة مدخل x واستجابة نبضة (مرشح) h، ينتج التفافهما إشارة مخرج y. رياضيًا: (x * h)[n] = Σₖ x[k] h[n−k].

الالتفاف عملية خطية: تضاعف المدخل يضاعف المخرج؛ مجموع المدخلات يعطي مجموع المخرجات. هذه ملاحظة جوهرية، لأنها تعني أن الالتفاف يمكن كتابته كـ ضرب مصفوفة-متجه. في كل مكان توجد فيه عملية خطية على متجه منتهٍ، ثمة مصفوفة مختبئة وراءها.

الفكرة الجوهرية

كل عملية خطية من ℝⁿ إلى ℝᵐ مكافئة للضرب في مصفوفة m×n ما. الالتفاف خطي، إذن لا بد أن تكون له مصفوفة. البنية الخاصة للالتفاف — تكرار معاملات المرشح — تحدد الشكل المحدد لتلك المصفوفة.

مصفوفة تيبليتز

عند كتابة التفاف إشارة طولها N مع مرشح طوله M، يتضح أن كل عينة مخرج y[n] هي حاصل ضرب داخلي لـ x مع نسخة إزاحية من h. جمع جميع عينات المخرج في معادلة مصفوفية يكشف مصفوفة تيبليتز H — مصفوفة يحمل فيها كل قطر (من الزاوية العلوية اليسرى إلى اليمنى السفلية) قيمة ثابتة.

لمرشح h = [h₀, h₁, h₂, ...]، تبدو مصفوفة تيبليتز H كالآتي:

القطر الرئيسي: كله h₀
القطر الفرعي الأول: كله h₁
القطر الفرعي الثاني: كله h₂
... وهكذا

مخرج الالتفاف هو ببساطة حاصل ضرب المصفوفة-متجه y = Hx. كل صف من H نسخة إزاحية من المرشح h، مع أصفار مبطّنة حسب الحاجة.

التفاف تيبليتز

\mathbf{y} = H\mathbf{x}, \quad H_{ij} = h[i-j]

الالتفاف y = x * h مكافئ لحاصل ضرب المصفوفة-متجه y = Hx، حيث H مصفوفة تيبليتز. يحمل كل قطر في H نفس معامل المرشح — الخاصية المُعرِّفة لمصفوفة تيبليتز. يتطلب الحساب المباشر عمليات O(N²) للإشارات ذات الطول N.

الالتفاف الدائري والمصفوفات الدائرية

الالتفاف الخطي (اللادوري) مع الحشو بالأصفار يعطي مصفوفات تيبليتز. لكن إذا فرضنا شروط حدود دورية — نعامل الإشارة كأنها تلتف حول نفسها — نحصل على الالتفاف الدائري، ومصفوفته مصفوفة دائرية.

في المصفوفة الدائرية، كل عمود إزاحة دورية للعمود الذي على يساره. العمود الأول يحدد المصفوفة بأكملها. مثلًا، إذا كان العمود الأول [h₀, h₁, h₂, h₃]ᵀ، يصبح العمود الثاني [h₃, h₀, h₁, h₂]ᵀ، والثالث [h₂, h₃, h₀, h₁]ᵀ، وهكذا. وعنصريًا، C_ij = h[(i−j) mod N] — القاعدة نفسها التي في مصفوفة تيبليتز أعلاه، لكنها الآن تلتف حول نفسها.

للمصفوفات الدائرية خاصية جبرية رائعة: تشترك جميعها في نفس مجموعة المتجهات الذاتية بصرف النظر عن القيم المحددة في العمود الأول. تلك المتجهات الذاتية هي متجهات قاعدة DFT — الأسية المركبة e^(j2πkn/N) لـ k = 0, 1, ..., N−1.

لماذا الالتفاف الدائري؟

ينشأ الالتفاف الدائري بشكل طبيعي عند العمل مع الإشارات الدورية وتحويل DFT. لاستخدام طرق FFT للالتفاف الخطي، نحشو الإشارات بالأصفار إلى طول كافٍ، ثم نجري الالتفاف الدائري الذي يعطي نفس نتيجة الالتفاف الخطي في المنطقة غير الملتفة.

DFT يُقطرن المصفوفات الدائرية

لأن متجهات قاعدة DFT هي المتجهات الذاتية لكل مصفوفة دائرية، فإن مصفوفة DFT المُسماة F تُقطرن جميع المصفوفات الدائرية في آنٍ واحد. هذا هو السبب الأعمق لأن الالتفاف يصبح ضربًا نقطيًا في نطاق التردد.

لتكن C مصفوفة دائرية N×N و F مصفوفة DFT ذات N نقطة (المدخل (k,n) هو ω^(kn)/√N حيث ω = e^(−j2π/N)). عندها C تقبل التحليل الطيفي:

تقطرن DFT

C = F^{-1} \Lambda F

كل مصفوفة دائرية C تُقطرَن بواسطة مصفوفة DFT المسماة F. تحتوي المصفوفة القطرية Λ على القيم الذاتية لـ C على قطرها، وهي بالضبط DFT للعمود الأول من C — أي DFT للمرشح h. F⁻¹ = F* (المنقول المرافق)، لأن F أحادية. انتبه للترتيب: هو F⁻¹ΛF وليس FΛF⁻¹. بناء المصفوفة الدائرية من العمود الأول هو ما يضع المعكوس على اليسار؛ أما المصفوفة المُزاحة بالصفوف فهي Cᵀ، وهي تنفّذ الارتباط الدائري لا الالتفاف.

القيم الذاتية λₖ = H[k] هي مجرد التمثيل في نطاق التردد للمرشح. إذن الالتفاف الدائري Cx = y يصبح، في نطاق التردد، Λ(Fx) = Fy — وهو ضرب نقطي لـ DFT لـ x في DFT لـ h، معطيًا DFT لـ y.

الالتفاف السريع بالـ FFT

الحساب المباشر للالتفاف N-نقطة عبر ضرب المصفوفات يتطلب عمليات O(N²). لكن تقطرن DFT يُظهر لنا مسارًا أسرع: احسب DFT لـ x و h، اضربهما نقطيًا، ثم خذ DFT العكسي. باستخدام خوارزمية FFT، يتطلب كل تحويل O(N log N) عملية فحسب.

الالتفاف السريع بالـ FFT

\mathbf{y} = \text{IFFT}\!\left(\text{FFT}(\mathbf{x}) \odot \text{FFT}(\mathbf{h})\right)

الرمز ⊙ يدل على الضرب النقطي (عنصر بعنصر). ثلاث عمليات بمقياس FFT (تحويلان أماميان وعكسي واحد) تحل محل ضرب المصفوفة بتعقيد O(N²)، مُخفِّضةً التعقيد الكلي إلى O(N log N). عند N = 10⁶ هذا تسريع هائل بنسبة ~50,000×.

هذه من أكثر رؤى تصميم الخوارزميات تأثيرًا في الهندسة بأسرها. الالتفاف المعتمد على FFT يدعم مضغطات الصوت والفيديو ومعالجة إشارات الاتصالات اللاسلكية وتصفية الصور وضغط نبضات الرادار وكشف الموجات الجاذبية وعدد لا حصر له من التطبيقات الأخرى.

الجمع المتداخل والحفظ المتداخل

عندما تكون الإشارة المدخل x طويلة جدًا (أو غير معروفة الطول أو لانهائية)، فإن تطبيق FFT عملاقة واحدة غير عملي. تُقسّم طريقتا الجمع المتداخل والحفظ المتداخل الإشارة المدخل إلى كتل قابلة للإدارة وتجمع النتائج للحصول على نفس مخرج الالتفاف الخطي المفرد.

الجمع المتداخل

قسّم x إلى كتل غير متداخلة x₁, x₂, x₃, .... احشُ كل كتلة بالأصفار إلى طول N + M − 1 (حيث N طول الكتلة و M−1 رتبة المرشح). احسب الالتفاف الدائري لكل كتلة مع h عبر FFT، منتجًا كتل مخرج تتداخل بمقدار M−1 عينة. اجمع الذيول المتداخلة للكتل المتجاورة لإعادة بناء الالتفاف الخطي الكامل.

الحفظ المتداخل

اجمع كتل إشارة المدخل ذات الطول N التي تتداخل مع الكتلة السابقة بمقدار M−1 عينة. احسب الالتفاف الدائري لكل كتلة مع h عبر FFT. اتخلص من أول M−1 عينة من كل كتلة مخرج (الملوثة بالالتفاف الدائري)، واحفظ فقط العينات الصالحة N − M + 1. تسلسل الأجزاء المحفوظة لاسترداد الالتفاف الخطي.

تحقق كلتا الطريقتين نفس تعقيد O(N log N) لكل عينة مخرج كالنهج المباشر بـ FFT، لكنهما تتطلبان ذاكرة O(N) فحسب في أي وقت — أمر بالغ الأهمية للمعالجة الفورية للإشارات المتدفقة.

أهم النقاط

الالتفاف عملية خطية، إذن يقابل الضرب في مصفوفة — تحديدًا مصفوفة تيبليتز (معاملات المرشح الإزاحية على كل قطر). الالتفاف الدائري يقابل مصفوفة دائرية ذات الخاصية الخاصة أن مصفوفة DFT تُقطرِنها: C = F⁻¹ΛF. القيم الذاتية Λ هي DFT للمرشح h. هذا التقطرن هو الأساس الجبري لسبب مساواة الالتفاف للضرب النقطي في نطاق التردد. يستغل الالتفاف المعتمد على FFT هذا لتقليل التعقيد من O(N²) إلى O(N log N). يمتد نهجا الجمع المتداخل والحفظ المتداخل هذا للإشارات الطويلة أو المتدفقة، مع الحفاظ على الكفاءة وإبقاء استخدام الذاكرة محدودًا.