FFT 합성곱 결과가 앞쪽에서 틀릴 때: zero-padding으로 원형 겹침 해결하기

FFT로 두 배열을 변환해 곱한 뒤 역변환했는데, 직접 계산한 합성곱과 앞부분부터 다르다면 변환 길이를 살펴야 합니다. 길이 N의 DFT에서 주파수 성분을 곱하고 역변환하면 기본적으로 길이 N의 원형 합성곱을 얻습니다. 선형 합성곱이 목적이라면 두 입력을 충분한 길이로 zero-padding한 뒤 변환해야 합니다. 숫자 몇 개로 값이 어디에 겹쳐 들어가는지 확인해 보겠습니다.

1. 먼저 선형 합성곱의 정답을 손으로 만듭니다

입력은 a = [1, 2, 4], b = [3, 5, 2]입니다. 인덱스는 0부터 시작하고 배열 밖의 값은 0으로 취급합니다. 선형 합성곱의 k번째 값은 인덱스의 합이 k인 두 원소의 곱을 모두 더한 것입니다.

c[0] = 1×3 = 3
c[1] = 1×5 + 2×3 = 11
c[2] = 1×2 + 2×5 + 4×3 = 24
c[3] = 2×2 + 4×5 = 24
c[4] = 4×2 = 8

따라서 정답은 [3, 11, 24, 24, 8]입니다. 입력 길이가 각각 M과 K이면 전체 선형 합성곱의 출력 길이는 M + K - 1입니다. 여기서는 3 + 3 - 1 = 5칸이 필요합니다.

이 단계의 정답을 준비해 두면 ‘FFT가 출력했으니 맞을 것’이라는 가정 없이 비교할 수 있습니다. 긴 배열부터 디버깅하기보다 손으로 다섯 칸을 계산할 수 있는 입력이 원인 확인에 유리합니다.

2. 길이 3으로 변환하면 뒤의 값이 앞쪽으로 돌아옵니다

두 배열을 길이 3 그대로 FFT한 뒤 성분별로 곱하고 IFFT하면 [27, 19, 24]가 나옵니다. 선형 합성곱의 마지막 두 값이 그냥 사라진 것이 아닙니다.

길이 3의 원형 합성곱에서는 인덱스 3이 0으로, 인덱스 4가 1로 돌아옵니다. 같은 나머지 인덱스에 놓인 값들이 더해집니다.

원형 결과[0] = c[0] + c[3] = 3 + 24 = 27
원형 결과[1] = c[1] + c[4] = 11 + 8 = 19
원형 결과[2] = c[2] = 24

이처럼 유한한 칸을 한 바퀴 돌며 겹치는 것이 원형 합성곱입니다. 두 입력의 길이를 줄이지 않은 N에 대해, 선형 결과의 인덱스를 N으로 나눈 나머지 위치에 합친다고 생각하면 이번 오류가 보입니다.

FFT가 잘못 계산한 것이 아니라 요청한 변환 길이에 맞는 다른 연산을 계산한 것입니다. 선형 결과가 필요했는데 원형 결과를 비교하고 있었던 셈입니다.

3. 두 입력을 모두 최소 5칸으로 늘립니다

이번 입력의 선형 결과를 겹침 없이 담으려면 FFT 길이 N을 5 이상으로 정합니다. N = 5라면 a는 [1, 2, 4, 0, 0], b는 [3, 5, 2, 0, 0]으로 취급됩니다.

길이를 4로만 늘리면 충분하지 않습니다. 마지막 c[4] = 8이 c[0]에 더해져 [11, 11, 24, 24]가 됩니다. ‘입력보다 조금 길다’가 아니라 ‘두 길이의 합에서 1을 뺀 만큼 충분하다’가 기준입니다.

NumPy의 fft에 n을 입력 길이보다 크게 주면 뒤쪽을 0으로 채워 변환합니다. 반대로 n이 입력 길이보다 작으면 입력이 잘립니다. 두 FFT가 같은 n을 쓰는지와, 그 n이 M + K - 1 이상인지 함께 확인해야 합니다.

패딩은 입력을 변환하기 전에 적용합니다. 이미 길이 3으로 겹쳐 계산된 IFFT 결과 뒤에 0을 두 개 붙여도 원래의 다섯 값으로 복원되지 않습니다.

4. Python으로 원형 결과와 선형 결과를 비교합니다

다음 예제는 NumPy를 사용할 수 있는 Python 환경에서 실행합니다. 파일이나 네트워크를 사용하지 않고 배열만 계산합니다.

import numpy as np

a = np.array([1., 2., 4.])
b = np.array([3., 5., 2.])
length = len(a) + len(b) - 1

circular = np.fft.ifft(
    np.fft.fft(a) * np.fft.fft(b)
)
linear = np.fft.ifft(
    np.fft.fft(a, n=length)
    * np.fft.fft(b, n=length),
    n=length,
)
direct = np.convolve(a, b, mode="full")

np.testing.assert_allclose(
    circular, [27, 19, 24],
    rtol=1e-12, atol=1e-12,
)
np.testing.assert_allclose(
    linear, direct,
    rtol=1e-12, atol=1e-12,
)
print(np.round(circular.real, 10))
print(np.round(linear.real, 10))
print(direct)

출력은 다음과 같습니다. 표시를 위해 실수부를 반올림했지만, 위의 일치 검사는 반올림하기 전의 복소수 결과를 비교합니다.

[27. 19. 24.]
[ 3. 11. 24. 24.  8.]
[ 3. 11. 24. 24.  8.]

첫 줄은 패딩 없는 길이 3의 원형 합성곱입니다. 둘째 줄은 길이 5로 패딩한 FFT 결과이고, 셋째 줄은 np.convolve의 전체 선형 합성곱입니다. 두 검사문을 함께 두어 잘못된 길이의 결과까지 의도한 방식으로 재현되는지 확인합니다.

예제는 기본 정규화 방식을 사용합니다. NumPy의 기본 IFFT에는 역변환의 1/N 배율이 반영되므로 결과를 N으로 한 번 더 나누지 않습니다. 별도의 norm 옵션을 선택한 코드라면 그 정규화 규칙까지 맞춰 비교해야 합니다.

실수 입력이라도 부동소수점 연산 때문에 아주 작은 허수부나 오차가 생길 수 있습니다. 그래서 예제에서는 허용 오차를 둡니다. 큰 입력이나 다른 수치 범위에도 이 허용 오차가 항상 적절하다고 가정하지는 않습니다.

5. 실수 전용 변환에서는 역변환 길이도 명시합니다

실수 입력만 다룬다면 rfft와 irfft를 사용할 수도 있습니다. 앞 예제의 a, b, length, direct를 그대로 사용합니다.

spectrum = (
    np.fft.rfft(a, n=length)
    * np.fft.rfft(b, n=length)
)
real_linear = np.fft.irfft(spectrum, n=length)
np.testing.assert_allclose(
    real_linear, direct,
    rtol=1e-12, atol=1e-12,
)

길이 5의 실수 신호는 rfft 결과가 3개 성분입니다. 이 성분 수만 보고 irfft가 원래 길이 5를 항상 알아내는 것은 아닙니다. n을 생략하면 기본 출력 길이가 2×(3-1) = 4가 되므로, 여기서는 n=length를 반드시 전달합니다.

정방향 패딩 길이를 맞췄는데도 결과 길이가 하나 짧다면 이 부분을 확인하세요. 복소수 입력을 다룰 때는 실수 전용 변환이나 .real을 무조건 적용하지 말고 복소수 정보를 보존해야 합니다.

6. 길이 문제와 수치 오차를 구분합니다

NumPy에서 선형 합성곱을 얻기 위한 변환 길이가 꼭 2의 거듭제곱일 필요는 없습니다. 이 예제는 N = 5로 계산합니다. 성능 등의 이유로 N = 8을 선택해도 충분한 길이이므로 앞의 M + K - 1개 값이 선형 결과에 해당하고, 뒤쪽에는 수치 오차 범위의 0이 남습니다.

직접 구현한 FFT에는 별도의 길이 제약이 있을 수 있습니다. ‘선형 합성곱에 필요한 최소 길이’와 ‘선택한 구현이 받는 길이’를 나누어 판단해야 합니다.

또한 작은 배열에서는 FFT가 직접 합성곱보다 항상 빠르다고 단정할 수 없습니다. 여기서 np.convolve를 함께 사용한 목적은 속도 경쟁이 아니라 계산 결과를 대조하기 위해서입니다.

[27, 19, 24]처럼 값이 크게 달라진 원형 겹침은 반올림으로 고칠 수 없습니다. 반대로 아주 작은 오차만 남았다면 길이와 정규화를 확인한 뒤 수치 정밀도 문제를 살핍니다. 큰 정수 계수의 정확한 연산까지 부동소수점 FFT가 자동으로 보장하는 것은 아닙니다.

핵심 요약

두 입력을 길이 N으로 FFT해 곱하고 역변환하면 원형 합성곱을 계산합니다. 부족한 칸의 값은 앞쪽으로 겹쳐 들어갈 수 있습니다.

선형 합성곱이 목적이라면 두 입력 모두 같은 N ≥ M + K - 1로 패딩합니다. 결과에 나중에 0을 붙이는 방법으로는 원형 겹침을 되돌릴 수 없습니다.

작은 직접 계산과 np.convolve로 대조하고, rfft를 썼다면 irfft의 n도 명시하세요. 길이 오류와 부동소수점 오차는 서로 다른 문제입니다.