ओवरलैप सेव मेथड

संकेत संसाधन में, ओवरलैप-सेव एक बहुत लंबे सिग्नल $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)

जहां क्षेत्र [1, M] के बाहर m के लिए h[m] = 0 है।

यह आलेख सामान्य अमूर्त संकेतन का उपयोग करता है, जैसे ${\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$ , कार्य $M+1\leq j\leq L+M$ के लिए कंप्यूटिंग $y_{k}[j]$ तक कम हो गया है। इन चरणों को चित्र 1 के पहले 3 अनुरेख में दर्शाया गया है, सिवाय इसके कि प्रक्षेपण का वांछित भाग (तीसरा ट्रेस) 1 $j$ ≤ L से मेल खाता है। ^{[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$ क्षेत्र में समतुल्य हैं इसलिए यह क्षेत्र [1, n] में $h[n]\,$ के साथ $x_{k}[n]\,$ के एन-बिंदु परिपत्र (या चक्रीय) कनवल्शन की गणना करने के लिए पर्याप्त है। उपक्षेत्र [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)

जहाँ:

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

छद्मकोड

(Overlap-save algorithm for linear convolution)
h = FIR_impulse_response
M = length(h)
overlap = M − 1
N = 8 × overlap    (see next section for a better choice)
step_size = N − overlap
H = DFT(h, N)
position = 0

while position + N ≤ length(x)
    yt = IDFT(DFT(x(position+(1:N))) × H)
    y(position+(1:step_size)) = yt(M : N)    (discard M−1 y-values)
    position = position + step_size
end

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

चित्र 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