الالتفاف الخطي والدائري: لماذا نضيف الأصفار قبل تحويل فورييه؟

ابدأ بأربعة معاملات خطية

نحدد x[0]=2 و x[1]=−1 و x[2]=3، ونحدد h[0]=1 و h[1]=2. كل قيمة خارج هذه الفهارس تساوي صفرًا بالتعريف. الفهرس عدد صحيح يحدد الموضع، والقيم نفسها بلا وحدة فيزيائية.

نعرف y[n]=Σⱼ x[j]h[n−j]، حيث يشمل الجمع كل j الصحيح؛ تبقى حدود قليلة لأن المدخلين محدودان. عند n=0 نحصل على 2×1=2، وعند n=1 نحصل على 2×2+(−1)×1=3.

عند n=2، الناتج (−1)×2+3×1=1. وعند n=3، الناتج 3×2=6. إذن y=[2,3,1,6] بفهارس من صفر إلى 3، وخارجها صفر.

يمكن مراجعة الحساب بضرب (2−z+3z²)(1+2z). الناتج 2+3z+z²+6z³؛ معامل zⁿ يساوي y[n] لأن ضرب zʲ في zᵏ يجمع الفهرسين j+k. الرمز z هنا وسيلة جبرية لتنظيم الحساب.

لا نشترط أن تكون القيم موجبة أو أن يكون مجموعها واحدًا. قيمة −1 مسموحة؛ المثال لا يمثل توزيعًا احتماليًا. إذا احتجت مراجعة توزيع الضرب وجمع الحدود المتشابهة، يوجد رابط كثيرات الحدود أسفل المقال.

شاهد كيف يعود الفهرس إلى الصفر

حاصل ضرب التحويلين وعكسه يعطي التفافًا دائريًا. [1]

لفهم ذلك في مثالنا نختار N=3، ونمد h إلى [1,2,0]، بينما x طولها ثلاثة أصلًا.

نعرف c₃[n]=Σⱼ₌₀² x[j]hₚ[(n−j) mod 3]، حيث hₚ=[1,2,0]. معنى mod 3 هو الباقي في المجموعة {0,1,2}؛ مثلًا −1 يعود إلى 2 و−2 يعود إلى 1. نستخدم هذه القاعدة للفهارس فقط.

عند n=0 تكون الحدود 2×1+(−1)×0+3×2=8. وعند n=1 نحصل على 2×2+(−1)×1+3×0=3. وعند n=2 نحصل على 2×0+(−1)×2+3×1=1.

إذن c₃=[8,3,1]. الناتج الخطي يضع 6 عند الفهرس 3، أما الطول الدائري الثلاثي فيعامل 3 كباقي صفر؛ لذلك c₃[0]=y[0]+y[3]=2+6. القيمتان الأخريان تبقيان 3 و1 في هذا المثال.

في صيغة كثيرات الحدود، العمل بترديد z³−1 يجعل z³=1. الحد 6z³ يعود إلى الثابت: 2+3z+z²+6 يصبح 8+3z+z². هذه طريقة ثانية لرؤية الطي نفسه.

القص إلى أول ثلاث قيم خطية يعطي [2,3,1]، وليس [8,3,1]. الالتفاف الدائري القصير يغيّر إحدى القيم المحتفظ بها؛ لا يمكن وصفه بأنه حذف آخر قيمة فقط.

أضف الأصفار ثم تحقق بتحويل أربع نقاط

للمدخلين بطولين M و L، يكفي أن نختار طولًا مشتركًا N≥M+L−1 ونمد كليهما بالأصفار. [1]

في برهاننا، نلاحظ أن كل حاصل ضرب x[j]h[k] يقع خطيًا في j+k بين صفر و M+L−2؛ إذا كان N أكبر من أقصى فهرس، فلا يلتف أي موضع.

بصورة أدق، يجمع الناتج الدائري عند الباقي r جميع معاملات y ذات الفهارس الموافقة له بترديد N. عندما تقع الفهارس الممكنة كلها بين صفر و N−1، توجد قيمة خطية واحدة في كل موضع؛ فتتطابق القيمتان. هذا برهان للطول الكافي، وليس مجرد نجاح تجربة.

في مثالنا N=4 يكفي. نستخدم xₚ=[2,−1,3,0] و hₚ=[1,2,0,0]. القيم الأصلية وفهارسها باقية؛ نضيف أصفارًا عند النهاية. لا نضع الأصفار بين عناصر المتتالية، لأن ذلك يغير الفهارس والمسألة.

للحساب المباشر للتحويل نثبت الاتفاقية X[k]=Σₙ₌₀³ xₚ[n] exp(−2πikn/4)، و H[k] بالطريقة نفسها، مع i²=−1. نثبت العكسي y[n]=(1/4)Σₖ₌₀³ Y[k] exp(+2πikn/4). اختلاف الاتفاقية يتطلب ضبط الإشارة وعامل القياس.

جذر التحويل هنا exp(−2πi/4)=−i. بالتعويض، X=[4,−1+i,6,−1−i]، و H=[3,1−2i,−1,1+2i]. مثالًا، X[1]=2+(−1)(−i)+3(−1)=−1+i.

نضرب عنصرًا بعنصر عند الفهرس نفسه: Y[k]=X[k]H[k]. نحصل على Y=[12,1+3i,−6,1−3i]؛ مثلًا (−1+i)(1−2i)=1+3i لأن i²=−1.

عند العكس، n=0 يعطي (12+1+3i−6+1−3i)/4=2. وعند n=1 يكون الجمع 12+(1+3i)i+6−(1−3i)i=12، ثم القسمة على 4 تعطي 3.

عند n=2 يصبح الجمع 12−(1+3i)−6−(1−3i)=4، فيعطي 1. وعند n=3 يصبح 12−(1+3i)i+6+(1−3i)i=24، فيعطي 6. هكذا يعود الناتج [2,3,1,6] كاملًا، رغم ظهور قيم مركبة في الوسط.

اضبط الطول ونوع الناتج المطلوب

إذا اخترنا N=5 ومددنا المدخلين بالأصفار إلى خمس نقاط، فلا يوجد طي أيضًا. الالتفاف الدائري يصبح [2,3,1,6,0]. الطول الخطي المخصص للمدخلين هو أربع نقاط؛ لذلك نأخذ القيم ذات الفهارس 0 إلى 3.

الشرط N≥M+L−1 كافٍ لجميع المدخلات بهذين الطولين. قد تسمح أصفار طرفية فعلية بطول أقل في حالة خاصة، لكن لا نعتمد ذلك من غير فحص؛ القيم غير الصفرية في مثالنا تعطي نهاية 6 عند الفهرس 3.

توثق SciPy أن fftconvolve يستخدم التحويل السريع، وأن full يعيد الالتفاف الخطي الكامل. [2] هذه واجهة تتولى الحساب المطلوب؛ أما تركيب ضرب تحويلات بطول تختاره بنفسك فيحتاج مراجعة شرط الحشو.

راجع قبل المقارنة: طول كل مدخل، وموضع الفهرس صفر، والامتداد خارج المجال، وطول التحويل، واتفاقية الإشارة والتطبيع، ثم هل تريد الناتج الكامل أو جزءًا منه. لا تقارن طولًا دائريًا ثلاثيًا بأربع قيم خطية ثم تنسب الفرق إلى خطأ تقريب.

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

لم نشغّل FFT أو fftconvolve أو MATLAB لإنتاج قياس أداء. راجعنا الحساب الجبري المباشر والقيم المركبة الدقيقة؛ الصور رسوم حسابية أصلية وليست صور شاشة من برنامج.