백과

2조의 N점의 유한 이산시간신호 x(n)와 h(n)(n=0, 1, …, N-1)의 재규격화(convolution)

ⓒ 한국사전연구사 | 저작권자의 허가 없이 사용할 수 없습니다.

또는 윗식에 있어서 n-i를 N을 법으로 하는 수로 한 순회 재규격화(circular convolution)를 구하기 위한 계산법을 말한다. 알고리즘으로서는, 직접계산에 의해 구하는 방법과, x(n)과 h(n)의 이산 푸리에 변환의 곱에 이산 역푸리에 변환을 하여 구하는 방법이 있다.

후자의 방법에 있어서, x(n)와 h(n)의 이산 푸리에 변환과 그것들의 곱의 이산 역푸리에 변환을 고속 푸리에 변환과 수론변환 등으로 계산하는 것에 따라, 곱셈횟수를 줄이고, 전체의 계산시간을 단축할 수 있다. 직접 계산에 의한 방법의 곱셈횟수가 N²회인 것에 대해, 고속 푸리에 변환을 쓴다고 하면, N가 2의 거듭제곱의 경우, 3Nlog₂N+N회의 복소곱셈횟수로 계산된다.