طريقة التداخل والإضافة

في معالجة الإشارات ، تُعد طريقة التداخل والجمع طريقة فعالة لتقييم الالتفاف المنفصل لإشارة طويلة جدًا${\displaystyle x[n]}$باستخدام مرشح استجابة نبضية محدودة (FIR)${\displaystyle h[n]}$:

أين${\displaystyle h[m]=0}$ل${\displaystyle m}$خارج المنطقة${\displaystyle [1,M].}$ 

تستخدم هذه المقالة رموزًا تجريدية شائعة، مثل:${\textstyle y(t)=x(t)*h(t),}$أو${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$حيث يُفهم أنه ينبغي التفكير في الوظائف ككل، بدلاً من التفكير فيها في لحظات محددة.${\textstyle t}$(انظر Convolution#Notation ).

تتمثل الفكرة في تقسيم المشكلة إلى عدة عمليات التفاف من${\displaystyle h[n]}$مع مقاطع قصيرة من${\displaystyle x[n]}$:

${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}$

أين${\displaystyle L}$طول القطعة عشوائي. إذن :

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}$

و${\displaystyle y[n]}$يمكن كتابتها كمجموع عمليات التفاف قصيرة : ^{[ 1 ]}

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}$

حيث الالتفاف الخطي${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,}$يساوي صفرًا خارج المنطقة${\displaystyle [1,L+M-1].}$وبالنسبة لأي معلمة${\displaystyle N\geq L+M-1,\,}$^{[ أ ]} إنه يعادل${\displaystyle N}$الالتفاف الدائري ذو النقاط لـ${\displaystyle x_{k}[n]\,}$مع${\displaystyle h[n]\,}$في المنطقة${\displaystyle [1,N].}$ وتكمن الميزة في أن عملية الالتفاف الدائري يمكن حسابها بكفاءة أكبر من عملية الالتفاف الخطي، وفقًا لنظرية الالتفاف الدائري :

أين :

• يشير كل من DFT _N و IDFT _N إلى تحويل فورييه المنفصل ومعكوسه، ويتم تقييمهما على${\displaystyle N}$نقاط منفصلة، ​​و
• ${\displaystyle L}$يتم اختيارها عادة بحيث${\displaystyle N=L+M-1}$هو عدد صحيح من قوى العدد 2، ويتم تنفيذ التحويلات باستخدام خوارزمية FFT ، من أجل الكفاءة.

فيما يلي تمثيل برمجي زائف للخوارزمية :

( خوارزمية التداخل والجمع للالتفاف الخطي ) h = مرشح FIR M = طول(h) Nx = طول(x) N = 8 × 2^ceiling( log2(M) ) (ثمانية أضعاف أصغر قوة للعدد اثنين أكبر من طول المرشح M. انظر القسم التالي لاختيار أفضل قليلاً.) step_size = N - (M-1) (L في النص أعلاه) H = DFT(h, N) الموضع = 0 y(1 : Nx + M-1) = 0 بينما يكون الموضع + حجم_الخطوة ≤ Nx نفّذ y(position+(1:N)) = y(position+(1:N)) + IDFT(DFT(x(position+(1:step_size)), N) × H) الموضع = الموضع + حجم_الخطوة نهاية

عند تطبيق تحويل فورييه المنفصل (DFT) وتحويل فورييه العكسي المنفصل (IDFT) باستخدام خوارزمية تحويل فورييه السريع (FFT)، يتطلب الكود الزائف أعلاه حوالي N (log ₂ (N) + 1) عملية ضرب معقدة لتحويل فورييه السريع، وضرب المصفوفات، وتحويل فورييه العكسي المنفصل (IFFT). ^{[ ب ]} تنتج كل تكرار N-M+1 عينة إخراج، لذا فإن عدد عمليات الضرب المعقدة لكل عينة إخراج هو حوالي :

على سبيل المثال، عندما${\displaystyle M=201}$و${\displaystyle N=1024,}$المعادلة 3 تساوي${\displaystyle 13.67,}$بينما يتطلب التقييم المباشر للمعادلة 1 ما يصل إلى${\displaystyle 201}$عمليات الضرب المعقدة لكل عينة إخراج، وأسوأ حالة هي عندما يكون كلاهما${\displaystyle x}$و${\displaystyle h}$هي ذات قيم مركبة. لاحظ أيضًا أنه لأي قيمة معطاة${\displaystyle M,}$للمعادلة 3 قيمة دنيا بالنسبة إلى${\displaystyle N.}$ الشكل 2 هو رسم بياني لقيم${\displaystyle N}$التي تقلل من قيمة المعادلة 3 لمجموعة من أطوال المرشحات (${\displaystyle M}$).

بدلاً من المعادلة 1 ، يمكننا أيضاً النظر في تطبيق المعادلة 2 على سلسلة طويلة من الطول${\displaystyle N_{x}}$العينات. سيكون العدد الإجمالي لعمليات الضرب المركبة كما يلي:

${\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}$

وبالمقارنة، فإن عدد عمليات الضرب المعقدة المطلوبة بواسطة خوارزمية الشفرة الزائفة هو:

${\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}$

وبالتالي، تتناسب تكلفة طريقة التداخل والإضافة تقريبًا مع${\displaystyle O\left(N_{x}\log _{2}N\right)}$بينما تبلغ تكلفة عملية الالتفاف الدائري الكبير الواحد تقريبًا${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$تُقارن الطريقتان أيضًا في الشكل 3، الذي تم إنشاؤه بواسطة محاكاة MATLAB . تمثل الخطوط الكنتورية نسبة ثابتة بين الوقت اللازم لتنفيذ كلتا الطريقتين. عندما تكون طريقة التداخل والجمع أسرع، تتجاوز النسبة 1، وتُلاحظ نسب تصل إلى 3.

• طريقة التداخل والحفظ
• الالتفاف الدائري#مثال

• أوبنهايم، آلان ف.؛ شيفر، رونالد و. (1975). معالجة الإشارات الرقمية . إنجلوود كليفس، نيوجيرسي: برنتيس هول. ISBN 0-13-214635-5.
• هايز، إم. هوراس (1999). معالجة الإشارات الرقمية . سلسلة شوم الموجزة. نيويورك: ماكجرو هيل. ISBN 0-07-027389-8.
• سينوباري، نادر شاكيباي؛ فانينغ، غاريث جيه؛ كيو، إيمون؛ تشو، يان؛ ييه، تشين-تشيا مايكل؛ زيمرمان، زاكاري؛ معين، عبد الله (2019). "الارتباط المتقاطع فائق الكفاءة (SEC-C): رمز ترشيح متطابق سريع مناسب لأجهزة الكمبيوتر المكتبية" (ملف PDF) . رسائل البحوث الزلزالية . 90 (1): 322-334 . doi : 10.1785/0220180122 . ISSN 0895-0695 .