ओवरलैप-सेव विधि

संकेत आगे बढ़ाना में, ओवरलैप-सेव एक बहुत लंबे सिग्नल के बीच कन्वोल्यूशन # असतत कनवल्शन का मूल्यांकन करने के एक कुशल तरीके का पारंपरिक नाम है $x[n]$ और एक परिमित आवेग प्रतिक्रिया (एफआईआर) फ़िल्टर $h[n]$ :

y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],

(Eq.1)

कहाँ h[m] = 0 क्षेत्र के बाहर एम के लिए [1, M]. यह आलेख सामान्य अमूर्त नोटेशन का उपयोग करता है, जैसे ${\textstyle y(t)=x(t)*h(t),}$ या ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ जिसमें यह समझा जाता है कि कार्यों के बारे में विशिष्ट क्षणों के बजाय उनकी समग्रता में सोचा जाना चाहिए ${\textstyle t}$ (कन्वोल्यूशन#नोटेशन देखें)।

चित्र 1: चार प्लॉटों का अनुक्रम ओवरलैप-सेव कनवल्शन एल्गोरिदम के एक चक्र को दर्शाता है। पहला प्लॉट लोपास एफआईआर फिल्टर के साथ संसाधित होने वाले डेटा का एक लंबा अनुक्रम है। दूसरा प्लॉट डेटा का एक खंड है जिसे टुकड़ों में संसाधित किया जाना है। तीसरा प्लॉट फ़िल्टर किया गया खंड है, जिसमें प्रयोग करने योग्य भाग लाल रंग का है। चौथा प्लॉट आउटपुट स्ट्रीम से जुड़े फ़िल्टर किए गए सेगमेंट को दिखाता है।^{[upper-alpha 1]} एफआईआर फिल्टर एम=16 नमूनों वाला एक बॉक्सकार लोपास है, खंडों की लंबाई एल=100 नमूने हैं और ओवरलैप 15 नमूने हैं।

अवधारणा एक मनमानी लंबाई L के y[n] के छोटे खंडों की गणना करना और खंडों को एक साथ जोड़ना है। किसी भी पूर्णांक k के लिए n = kL + M से शुरू होने वाले खंड पर विचार करें और 'परिभाषित करें:'

x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}

y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].

फिर, के लिए $kL+M+1\leq n\leq kL+L+M$ , और समकक्ष $M+1\leq n-kL\leq L+M$ , हम लिख सकते हैं:

y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].

प्रतिस्थापन के साथ $j=n-kL$ , कार्य कंप्यूटिंग तक कम हो गया है $y_{k}[j]$ के लिए $M+1\leq j\leq L+M$ . इन चरणों को चित्र 1 के पहले 3 ट्रेस में दर्शाया गया है, सिवाय इसके कि आउटपुट का वांछित भाग (तीसरा ट्रेस) 1 से मेल खाता है। $j$ ≤ एल.^{[upper-alpha 2]}

यदि हम समय-समय पर x का विस्तार करते हैं_k[n] अवधि N ≥ L + M − 1 के साथ,' के अनुसार:'

x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],

संकल्प $(x_{k,N})*h\,$ और $x_{k}*h\,$ क्षेत्र में समतुल्य हैं $M+1\leq n\leq L+M$ . इसलिए यह एन-पॉइंट गोलाकार घुमाव | सर्कुलर (या चक्रीय) कनवल्शन की गणना करने के लिए पर्याप्त है $x_{k}[n]\,$ साथ $h[n]\,$ क्षेत्र में [1, एन]। उपक्षेत्र [M + 1, L + M] को आउटपुट स्ट्रीम में जोड़ा जाता है, और अन्य मान खारिज कर दिए जाते हैं। लाभ यह है कि डिस्क्रीट फूरियर ट्रांसफॉर्म#सर्कुलर कनवल्शन प्रमेय और क्रॉस-सहसंबंध प्रमेय के अनुसार, गोलाकार कनवल्शन की गणना रैखिक कनवल्शन की तुलना में अधिक कुशलता से की जा सकती है:'

y_{k}[n]\ =\ \scriptstyle {\text{IDFT}}_{N}\displaystyle (\ \scriptstyle {\text{DFT}}_{N}\displaystyle (x_{k}[n])\cdot \ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])\ ),

(Eq.2)

कहाँ:

डीएफटी_N और आईडीएफटी_N असतत फूरियर रूपांतरण और इसके व्युत्क्रम का संदर्भ लें, जिसका मूल्यांकन एन असतत बिंदुओं पर किया गया है, और
$L$ को प्रथागत रूप से ऐसे चुना जाता है $N = L+M-1$ एक पूर्णांक पावर-ऑफ़-2 है, और दक्षता के लिए परिवर्तनों को फास्ट फूरियर ट्रांसफॉर्म एल्गोरिदम के साथ कार्यान्वित किया जाता है।
वृत्ताकार कनवल्शन के अग्रणी और अनुगामी किनारे-प्रभावों को ओवरलैप किया जाता है और जोड़ा जाता है,^{[upper-alpha 3]} और बाद में त्याग दिया गया।^{[upper-alpha 4]}

छद्मकोड

<स्पैन स्टाइल=रंग:हरा; >(रैखिक कनवल्शन के लिए ओवरलैप-सेव एल्गोरिदम)
एच = एफआईआर_आवेग_प्रतिक्रिया
एम = लंबाई(एच)
ओवरलैप = एम - 1
एन = 8 × ओवरलैप <स्पैन शैली = रंग: हरा; >(बेहतर विकल्प के लिए अगला भाग देखें)
चरण_आकार = एन - ओवरलैप
एच = डीएफटी(एच, एन)
स्थिति = 0

'जबकि' स्थिति + एन ≤ लंबाई (एक्स)
    yt = IDFT(DFT(x(स्थिति+(1:N))) × H)
    y(स्थिति+(1:step_size)) = yt(M : N) (M−1 y-मान त्यागें)
    स्थिति = स्थिति + चरण_आकार
'अंत'

दक्षता संबंधी विचार

चित्र 2: एन (2 की पूर्णांक घात) के मानों का एक ग्राफ जो लागत फ़ंक्शन को न्यूनतम करता है

{\tfrac {N\left(\log _{2}N+1\right)}{N-M+1}}

जब डीएफटी और आईडीएफटी को एफएफटी एल्गोरिदम द्वारा कार्यान्वित किया जाता है, तो उपरोक्त छद्मकोड की आवश्यकता होती है N (log₂(N) + 1) एफएफटी, सरणियों के उत्पाद और आईएफएफटी के लिए जटिल गुणन।^{[upper-alpha 5]} प्रत्येक पुनरावृत्ति उत्पन्न करती है N-M+1 आउटपुट नमूने, इसलिए प्रति आउटपुट नमूने में जटिल गुणन की संख्या लगभग है:

{\frac {N(\log _{2}(N)+1)}{N-M+1}}.\,

(Eq.3)

उदाहरण के लिए, जब M=201 और N=1024, Eq.3 13.67 के बराबर है, जबकि प्रत्यक्ष मूल्यांकन Eq.1 प्रत्येक आउटपुट नमूने के लिए 201 तक जटिल गुणन की आवश्यकता होगी, सबसे खराब स्थिति तब होगी जब x और h दोनों जटिल-मूल्यवान हों। यह भी ध्यान दें कि किसी दिए गए एम के लिए, Eq.3 में N के संबंध में न्यूनतम है। चित्र 2 N के मानों का एक ग्राफ है जो न्यूनतम करता है Eq.3 फ़िल्टर लंबाई (एम) की एक श्रृंखला के लिए।

के बजाय Eq.1, हम आवेदन करने पर भी विचार कर सकते हैं Eq.2 लंबाई के एक लंबे क्रम के लिए $N_{x}$ नमूने. जटिल गुणन की कुल संख्या होगी:

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

तुलनात्मक रूप से, स्यूडोकोड एल्गोरिदम द्वारा आवश्यक जटिल गुणन की संख्या है:

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

इसलिए ओवरलैप-सेव पद्धति की लागत लगभग समान है $O\left(N_{x}\log _{2}N\right)$ जबकि एक एकल, बड़े गोलाकार कनवल्शन की लागत लगभग है $O\left(N_{x}\log _{2}N_{x}\right)$ .

ओवरलैप–त्यागें

ओवरलैप-त्यागें^[1]और ओवरलैप-स्क्रैप^[2]यहां वर्णित समान विधि के लिए आमतौर पर कम उपयोग किए जाने वाले लेबल हैं। हालाँकि, ये लेबल वास्तव में ओवरलैप-ऐड विधि|ओवरलैप-ऐड से अलग करने के लिए बेहतर (ओवरलैप-सेव से) हैं, क्योंकि दोनों विधियां सहेजती हैं, लेकिन केवल एक को हटा देती हैं। सेव केवल इस तथ्य को संदर्भित करता है कि खंड k से M - 1 इनपुट (या आउटपुट) नमूने खंड k + 1 को संसाधित करने के लिए आवश्यक हैं।

ओवरलैप का विस्तार-सहेजें

ओवरलैप-सेव एल्गोरिदम को सिस्टम के अन्य सामान्य संचालन को शामिल करने के लिए बढ़ाया जा सकता है:^{[upper-alpha 6]}^[3]

अतिरिक्त आईएफएफटी चैनलों को फॉरवर्ड एफएफटी का पुन: उपयोग करके पहले की तुलना में अधिक सस्ते में संसाधित किया जा सकता है
विभिन्न आकार के आगे और उलटे एफएफटी का उपयोग करके नमूना दरों को बदला जा सकता है
फ़्रीक्वेंसी अनुवाद (मिश्रण) फ़्रीक्वेंसी डिब्बे को पुनर्व्यवस्थित करके पूरा किया जा सकता है

यह भी देखें

ओवरलैप-जोड़ने की विधि

↑ Rabiner and Gold, Fig 2.35, fourth trace.
↑ Shifting the undesirable edge effects to the last M-1 outputs is a potential run-time convenience, because the IDFT can be computed in the $y[n]$ buffer, instead of being computed and copied. Then the edge effects can be overwritten by the next IDFT. A subsequent footnote explains how the shift is done, by a time-shift of the impulse response.
↑ Not to be confused with the Overlap-add method, which preserves separate leading and trailing edge-effects.
↑ The edge effects can be moved from the front to the back of the IDFT output by replacing $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ with $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ meaning that the N-length buffer is circularly-shifted (rotated) by M-1 samples. Thus the h(M) element is at n=1. The h(M-1) element is at n=N. h(M-2) is at n=N-1. Etc.
↑ Cooley–Tukey FFT algorithm for N=2^k needs (N/2) log₂(N) – see FFT – Definition and speed
↑ Carlin et al. 1999, p 31, col 20.

संदर्भ

↑ Harris, F.J. (1987). D.F.Elliot (ed.). Handbook of Digital Signal Processing. San Diego: Academic Press. pp. 633–699. ISBN 0122370759.
↑ Frerking, Marvin (1994). Digital Signal Processing in Communication Systems. New York: Van Nostrand Reinhold. ISBN 0442016166.
↑ Borgerding, Mark (2006). "Turning Overlap–Save into a Multiband Mixing, Downsampling Filter Bank". IEEE Signal Processing Magazine. 23 (March 2006): 158–161. doi:10.1109/MSP.2006.1598092.

Rabiner, Lawrence R.; Gold, Bernard (1975). "2.25". Theory and application of digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. pp. 63–67. ISBN 0-13-914101-4.
US patent 6898235, Carlin,Joe; Collins,Terry & Hays,Peter et al., "Wideband communication intercept and direction finding device using hyperchannelization", published 1999-12-10, issued 2005-05-24 , also available at https://patentimages.storage.googleapis.com/4d/39/2a/cec2ae6f33c1e7/US6898235.pdf

बाहरी संबंध

Dr. Deepa Kundur, Overlap Add and Overlap Save, University of Toronto

[1] Rabiner and Gold, Fig 2.35, fourth trace.

[2] Shifting the undesirable edge effects to the last M-1 outputs is a potential run-time convenience, because the IDFT can be computed in the $y[n]$ buffer, instead of being computed and copied. Then the edge effects can be overwritten by the next IDFT. A subsequent footnote explains how the shift is done, by a time-shift of the impulse response.

[3] Not to be confused with the Overlap-add method, which preserves separate leading and trailing edge-effects.

[4] The edge effects can be moved from the front to the back of the IDFT output by replacing $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ with $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ meaning that the N-length buffer is circularly-shifted (rotated) by M-1 samples. Thus the h(M) element is at n=1. The h(M-1) element is at n=N. h(M-2) is at n=N-1. Etc.

[5] Cooley–Tukey FFT algorithm for N=2^k needs (N/2) log₂(N) – see FFT – Definition and speed

[8] Carlin et al. 1999, p 31, col 20.

[f.harris-6] Harris, F.J. (1987). D.F.Elliot (ed.). Handbook of Digital Signal Processing. San Diego: Academic Press. pp. 633–699. ISBN 0122370759.

[Frerking-7] Frerking, Marvin (1994). Digital Signal Processing in Communication Systems. New York: Van Nostrand Reinhold. ISBN 0442016166.

[Borgerding-9] Borgerding, Mark (2006). "Turning Overlap–Save into a Multiband Mixing, Downsampling Filter Bank". IEEE Signal Processing Magazine. 23 (March 2006): 158–161. doi:10.1109/MSP.2006.1598092.

[upper-alpha 1]

[upper-alpha 2]

[upper-alpha 3]

[upper-alpha 4]

[upper-alpha 5]

[1]

[2]

[upper-alpha 6]

[3]

ओवरलैप-सेव विधि

Contents