오버랩-저장 방법

신호 처리에서 오버랩-세이브는 매우 긴 $x[n]$ x $x[n]$ [ $x[n]$ $x[n]$ $x[n]$ 과 $x[n]$ (와) 유한 임펄스 응답( $h[n]$ ) 필터 h $h[n]$ [ $h[n]$ {\ $displaystyle$ h $h[n]$ n $]}$ 사이의 이산형 콘볼루션을 평가하는 효율적인 방법을 위한 전통적인 이름이다.

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

(Eq.1)

여기서 h[m] = 영역 밖에서 m의 경우 0 [1, M]This article uses common abstract notations, such as ${\textstyle y(t)=x(t)*h(t),}$ or ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ in which it is understood that the functions should be thought of in their totality, rather than at specific instants ${\textstyle t}$ (see Convolution#Notation).

그림 1: 네 개의 그림 순서는 겹침-저장 콘볼루션 알고리즘의 한 사이클을 나타낸다.첫 번째 플롯은 저역 통과 FIR 필터로 처리해야 하는 긴 데이터 시퀀스다.두 번째 그림은 조각처럼 처리되는 데이터의 한 부분이다.세 번째 그래프는 필터링된 세그먼트이며 사용 가능한 부분은 빨간색으로 채색된다.네 번째 그림은 출력 스트림에 추가된 필터링된 세그먼트를 보여준다.^[A]FIR 필터는 M=16 샘플이 있는 박스카 로우패스(boxcar lowpass)이며, 세그먼트의 길이는 L=100 샘플이며 겹치는 샘플은 15개 샘플이다.

임의 길이 L의 y[n]의 짧은 세그먼트를 계산하고 세그먼트를 함께 결합하는 개념이다.정수 k에 대해 n = kL + M에서 시작하는 세그먼트를 고려하여 다음을 정의하십시오.

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

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

Then, for $kL+M+1\leq n\leq kL+L+M$ , and equivalently $M+1\leq n-kL\leq L+M$ , we can write:

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

With the substitution $j=n-kL$ , the task is reduced to computing $y_{k}[j]$ for $M+1\leq j\leq L+M$ . These steps are illustrated in the first 3 traces of Figure 1, except that the desired portion of the output (third trace) corresponds to1 ≤ j ≤ L.^[B]

주기 N + L + M - 1로 x[n]을_k 주기적으로 연장하는 경우, 다음과 같이 하십시오.

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

the convolutions $(x_{k,N})*h\,$ and $x_{k}*h\,$ are equivalent in the region $M+1\leq n\leq L+M$ . It is therefore sufficient to compute the N-point circular (or cyclic) convolution of ${\displaystyle x_{k}[n$ $]\,}$ $h[n]\,$ 에 h $h[n]\,$ [ $h[n]\,$ $h[n]\,$ ${\$ 이 $x_{k}[n]\,$ (가) 있는 경우 $h[n]\,$ [1, N].하위 영역 [M + 1, L + M]을 출력 스트림에 추가하고, 나머지 값은 폐기한다.이점은 원형 콘볼루션 정리에 따라 원형 콘볼루션을 선형 콘볼루션보다 더 효율적으로 계산할 수 있다는 것이다.

y_{k}[n]\\\scriptstyle {\text{IDFT}_{N}\displaystyle(\\scriptstyle {\text{D)FT}_{N}\displaystyle(x_{k}[n])\cdot \scriptstyle {\text{D)FT}_{N}\디스플레이 스타일(h[n])\),

(Eq.2)

여기서:

DFT와_N IDFT는_N 이산 푸리에 변환과 그 역(N개의 이산형 점들에 대해 평가)을 참조한다.
$L은 N$ = L+ $M-1$ 이 2의 정수 출력이고, 변환은 효율을 위해 FFT 알고리즘으로 구현된다.
원형 콘볼루션의 선행 및 후행 에지 효과가 중첩되고 추가되며 ^[C]이후 폐기된다.^[D]

가성음

(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) 위치 = 위치 + step_size 끝

효율성 고려사항

그림 2: 비용 함수 N

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

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

⁡ N

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

+ 1 )

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

-

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

+

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

{\

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

을 최소화하는 N 값(2의 정수 검정력)의 그래프.

DFT와 IDFT가 FFT 알고리즘에 의해 구현되는 경우, 위의 가성소드는 FFT, 어레이의 제품, IFFT에 대한 N(log₂(N) + 1) 복합승수를 요구한다.^[E]각 반복은 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가 모두 복합적으로 계산된 경우다.또한 주어진 M에 대해 Eq.3은 N에 대한 최소값을 가지고 있다는 점에 유의한다.그림 2는 다양한 필터 길이(M)에 대해 Eq.3을 최소화하는 N 값을 그래프로 나타낸 것이다.

Eq.1 대신 길이 $N_{x}$ $N_{x}$ ${\$ 의 $N_{x}$ 긴 시퀀스에 Eq.2를 적용하는 것도 고려할 수 있다.복합 승수의 총 수는 다음과 같을 것이다.

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

비교적으로, 유사코드 알고리즘에 의해 요구되는 복잡한 승수의 수는 다음과 같다.

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

Hence the cost of the overlap–save method scales almost as $O\left(N_{x}\log _{2}N\right)$ while the cost of a single, large circular convolution is almost $O\left(N_{x}\log _{2}N_{x}\right)$ .

겹침-해제

오버랩-디스크^[1] 및 오버랩-스크랩은^[2] 여기에서 설명하는 동일한 방법에 대해 덜 일반적으로 사용되는 라벨이다.그러나 이러한 라벨은 두 방법 모두 "저장"하지만 한 가지 방법만 무시하기 때문에 (중복-저장보다) 중복-추가와 구별하는 것이 실제로 더 낫다."저장"은 세그먼트 k + 1을 처리하기 위해 세그먼트 k의 M - 1 입력(또는 출력) 샘플이 필요하다는 사실만을 가리킨다.

오버랩 확장-저장

중복 저장 알고리즘은 시스템의 다른 일반적인 작동을 포함하도록 확장할 수 있다.^[F]^[3]

추가적인 IFFT 채널은 전방 FFT를 재사용하여 첫 번째 채널보다 더 저렴하게 처리할 수 있다.
샘플링 속도는 서로 다른 크기의 FFT와 역 FFT를 사용하여 변경할 수 있다.
주파수 빈을 재배열하여 주파수 변환(초기화)을 수행할 수 있음

참고 항목

오버랩-추가 방법

메모들

^ 라비너와 골드, 그림 2.35, 네 번째 흔적.
^ 바람직하지 않은 에지 효과를 마지막 M-1 출력으로 이동하는 것은 잠재적 런타임 편리하다. 왜냐하면 IDFT는 계산되고 복사되는 대신 y $y[n]$ [ $y[n]$ $y[n]$ $y[n]$ 버퍼로 $y[n]$ 계산할 수 있기 때문이다.그런 다음 다음 다음 IDFT로 에지 효과를 덮어쓸 수 있다.다음 각주는 충동 반응의 시간 이동에 의해 변속이 어떻게 수행되는지 설명한다.
^ 선행 및 후행 에지 효과를 별도로 보존하는 오버랩 추가 방법과 혼동하지 마십시오.
^ 가장자리 효과는 $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ ( $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ h $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ [ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ ${\$ )를 교체하여 IDFT 출력의 전면에서 후면까지 이동할 수 있다. $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $}$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ ${N}\displaystyle($ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ M $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ - $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ = $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ [ n $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ + $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ - $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ - ${\$ ) $FT}_{N}\디스플레이 스타일(h[n+M-1])$ $=\\scriptstyle {\text{D$ $FT}_{N}\displaystyle(h[n+M-1-N])$ 은 $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ N-길이 버퍼가 M-1 샘플에 의해 순환(회전)된다는 것을 의미한다.따라서 h(M) 요소는 n=1이다.h(M-1) 요소는 n=N. h(M-2)는 n=N-1 등에 있다.
^ N=2^k needs (N/2₂) log(N)에 대한 Cooley-Tukey FFT 알고리즘 – FFT – 정의 및 속도 참조
^ 칼린 외 1999, 페이지 31, 콜 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" (PDF). IEEE Signal Processing Magazine (March 2006): 158–161.

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.
미국 특허 6898235, 칼린, 조, 콜린스Terry & Hays, Peter 등, 1999-12-10년에 출판된 "하이퍼채널화를 이용한 광대역 통신 차단 및 방향 찾기 장치"는 https://patentimages.storage.googleapis.com/4d/39/2a/cec2ae6f33c1e7/US6898235.pdf에서도 2005-05-24를 발행할 수 있다.

외부 링크

Deepa Kundur 박사, 오버랩 추가 및 오버랩 세이브, 토론토 대학

[1] 라비너와 골드, 그림 2.35, 네 번째 흔적.

[2] 바람직하지 않은 에지 효과를 마지막 M-1 출력으로 이동하는 것은 잠재적 런타임 편리하다. 왜냐하면 IDFT는 계산되고 복사되는 대신 y $y[n]$ [ $y[n]$ $y[n]$ $y[n]$ 버퍼로 $y[n]$ 계산할 수 있기 때문이다.그런 다음 다음 다음 IDFT로 에지 효과를 덮어쓸 수 있다.다음 각주는 충동 반응의 시간 이동에 의해 변속이 어떻게 수행되는지 설명한다.

[3] 선행 및 후행 에지 효과를 별도로 보존하는 오버랩 추가 방법과 혼동하지 마십시오.

[4] 가장자리 효과는 $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ ( $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ h $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ [ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ ${\$ )를 교체하여 IDFT 출력의 전면에서 후면까지 이동할 수 있다. $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $}$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ ${N}\displaystyle($ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ M $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ - $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ = $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ [ n $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ + $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ - $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ - ${\$ ) $FT}_{N}\디스플레이 스타일(h[n+M-1])$ $=\\scriptstyle {\text{D$ $FT}_{N}\displaystyle(h[n+M-1-N])$ 은 $\scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),$ N-길이 버퍼가 M-1 샘플에 의해 순환(회전)된다는 것을 의미한다.따라서 h(M) 요소는 n=1이다.h(M-1) 요소는 n=N. h(M-2)는 n=N-1 등에 있다.

[5] N=2^k needs (N/2₂) log(N)에 대한 Cooley-Tukey FFT 알고리즘 – FFT – 정의 및 속도 참조

[8] 칼린 외 1999, 페이지 31, 콜 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" (PDF). IEEE Signal Processing Magazine (March 2006): 158–161.

[A]

[B]

[C]

[D]

[E]

[1]

[2]

[F]

[3]

Search