오버랩-추가 방법

신호 처리에서 오버랩-add 방법은 다음과 같은 유한 임펄스 응답(FIR) $필터{\displaystyle }$ h${\displaystyle }$[${\displaystyle n}$ ${\displaystyle ]}$ ${\$$displaystyle x[n]}$을(를) 가진$$ 매우 긴 $신호{\displaystyle }$ x${\displaystyle }$[${\displaystyle n}$ ${\displaystyle ]}$ ${\$$displaystyle h[n]}$의 이산형 콘볼루션을 평가하는 효율적인 방법이다$.$

${\displaystyle 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).

개념은 x${\displaystyle }$[ $n{\displaystyle }$ ${\displaystyle ]}$ ${\displaystyle x[n]}$의 짧은 세그먼트를 가진 h[${\displaystyle n}$]의 다중 경련으로 문제를 나누는 것이다$.$

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

여기서 L은 임의 세그먼트 길이입니다.다음:

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

그리고 y[n]는 짧은 경련의 합으로 쓸 수 있다.^[1]

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

여기서 선형 컨볼루션 $y{\displaystyle {}_{}}$ ${\displaystyle k_{}}$[ ${\displaystyle n}$ ${\displaystyle ]x{}_{}}$x k [ n ${\displaystyle ]}$ ${\displaystyle ]}$ h${\displaystyle }$[${\displaystyle n}$ ${\displaystyle ]}$ ${\$은(는) 영역 외부에 0이다[1, L + M - 1].그리고 모든 파라미터 $N{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle L}$+ M${\displaystyle }$- ${\displaystyle 1}$,${\$에 대해 영역^[A] [1, N]에서 h [$n{\displaystyle ]}$ ${\$$k}[$$n],}$의 N 포인트 원형 콘볼루션과 동일하다.이점은 원형 콘볼루션 정리에 따라 원형 콘볼루션을 선형 콘볼루션보다 더 효율적으로 계산할 수 있다는 것이다.

${\displaystyle 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 알고리즘으로 구현된다.

가성음

다음은 알고리즘의 유사점이다.

(선형 콘볼루션에 대한 오버랩-add 알고리즘) h = FIR_impulse_response M = 길이(h) Nx = 길이(x) N = 8 x 2^ceiling(log2(M) ) (필터 길이 M보다 큰 2개의 최소 전력의 8배)  See next section for a slightly better choice.) step_size = N - (M-1)  (L in the text above) H = DFT(h, N) position = 0 y(1 : Nx + M-1) = 0  while position + step_size ≤ Nx do     y(position+(1:N)) = y(position+(1:N)) + IDFT(DFT(x(position+(1:step_size)), N) × H)     position = position + step_size end

효율성 고려사항

DFT와 IDFT가 FFT 알고리즘에 의해 구현되는 경우, 위의 가성소드는 FFT, 어레이의 제품, IFFT에 대한 N(log₂(N) + 1) 복합승수를 요구한다.^[B]각 반복은 N-M+1 출력 샘플을 생성하므로 출력 샘플당 복잡한 곱의 수는 다음과 같다.

${\displaystyle {\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{\displaystyle {}_{}}$ ${\displaystyle x_{}}$ ${\$의 긴 시퀀스에 Eq.2를 적용하는 것도 고려할 수 있다.복합 승수의 총 수는 다음과 같을 것이다.

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

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

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

Hence the cost of the overlap–add method scales almost as ${\displaystyle O\left(N_{x}\log _{2}N\right)}$ while the cost of a single, large circular convolution is almost ${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$.이 두 가지 방법은 Matlab 시뮬레이션에 의해 만들어진 그림 3에서도 비교된다.등고선은 두 방법을 모두 수행하는 데 걸리는 시간의 일정한 비율의 선입니다.오버랩 애드 방식이 더 빠를 때 비율이 1을 초과하고, 3에 이르는 비율이 보인다.

참고 항목

• 오버랩-저장 방법

메모들

참조

추가 읽기

• Oppenheim, Alan V.; Schafer, Ronald W. (1975). Digital signal processing. Englewood Cliffs, N.J.: Prentice-Hall. ISBN 0-13-214635-5.
• Hayes, M. Horace (1999). Digital Signal Processing. Schaum's Outline Series. New York: McGraw Hill. ISBN 0-07-027389-8.