이 단원 목차
같은 변환을 두 알고리즘으로 계산합니다
DFT는 N개 복소 표본을 N개 복소 계수로 바꿉니다. 여기서는 정변환에 배율을 붙이지 않고 역변환에서 N으로 나눕니다.
FFT는 이 식을 분해해 빠르게 계산하는 알고리즘입니다. 새로운 변환이 아니며 입력에 없던 정보를 늘리지도 않습니다. 실험은 직접 DFT와 radix-two FFT를 모두 계산하고 복소 계수 차이까지 비교한 다음 크기를 그립니다.
cosine으로 숫자를 검산하기
N=8, 창당 한 주기, 위상 0이면 x[n]=cos(2πn/8)입니다. Euler 항등식으로 양·음 주파수 지수함수로 반씩 나누면 X[1]=4, X[7]=4이고 나머지는 0입니다. 그림은 두 쪽 크기 |X|/N이므로 두 봉우리 높이는 각각 0.5입니다. 내부 bin을 두 배로 만드는 단측 진폭 그림과 다릅니다.
표에는 부호 있는 창당 주기 수도 있습니다. bin 7은 −1을 나타냅니다. 짝수 N의 bin N/2는 하나뿐인 Nyquist bin이므로 두 번 세지 않습니다. 위상을 바꾸면 복소 계수가 회전하는데 크기 그림만으로는 보이지 않을 수 있습니다. 실수부·허수부도 함께 확인하세요.
radix two가 계산을 줄이는 방식
입력을 짝수 index와 홀수 index로 나누어 각각 절반 길이로 변환합니다.
이 한 쌍을 butterfly라고 합니다. N=8이면 butterfly는 (N/2)log₂N=12개이며 직접 합의 항은 64개입니다. N=64에서는 각각 192개와 4096개입니다. 서로 다른 단위의 알고리즘 계수이므로 실행 시간 비율이나 동일 비용의 기계 연산 수로 해석하면 안 됩니다. 메모리 접근·상수·하드웨어도 속도에 영향을 줍니다.
정수가 아닌 주기를 넣으면
창당 주기를 1.25로 바꾸세요. 관측 창을 주기 연장할 때 대개 경계가 어긋나 여러 bin으로 성분이 퍼집니다. 이것은 FFT 오차가 아닙니다. 직접 DFT도 같은 결과를 냅니다. 창당 주기를 고정한 채 N만 늘리면 정규화한 창을 더 촘촘히 표본화하는 것이며 같은 물리 tone을 더 오래 관측하는 상황이 자동으로 되지는 않습니다.
직접 풀기와 단위 확인
주기 수와 위상을 모두 0으로 두면 상수 입력입니다. X[0]=N만 남아 정규화 크기는 1이어야 합니다. 두 알고리즘과 역변환 오차로 검산하세요. 실제 Hz를 붙이려면 표본 간격이 필요하며 bin k는 부호를 접기 전 kfₛ/N입니다. index·창당 주기·radian/sample·Hz를 변환 계수 없이 섞지 마세요.
추가 읽기: Julius O. Smith III, Spectral Audio Signal Processing.
설명할 수 있나요?
실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.
선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.