이산 푸리에 변환(DFT)을 적은 연산으로 정확하게 계산하는 알고리즘의 총칭. N점 DFT를 절반 크기의 DFT로 차례차례 나누어 공통 계산을 묶는 방법(쿨리-튜키 알고리즘)이 대표적이며, 연산 횟수는 정의대로의 약 N²회에서 약 N log₂N회로 줄어든다. N = 1024이면 약 100분의 1이다. 점수가 2의 거듭제곱일 때 가장 간단한 형태가 되지만, 다른 점수에 쓸 수 있는 방법도 있다. 스펙트럼 해석 외에 OFDM의 변조·복조나 긴 합성곱의 고속 계산에도 사용된다.
일본어 명칭: 高速フーリエ変換(FFT)
고속 푸리에 변환(FFT)은(는) 디지털 신호 처리의 기초, 무선 통신의 기초 등 2개 분야의 연습 문제 4개에 나와요.
분야: 디지털 신호 처리의 기초
N점 DFT를 짝수 번째와 홀수 번째 샘플의 두 N/2점 DFT로 나누면, 회전 인자 e^(−j2πk/N)을 곱해 더하고 빼는 것만으로 원래 결과를 조립할 수 있습니다. 이를 반복하면 log₂N단으로 나뉘고 각 단의 연산은 약 N회이므로, 전체는 N log₂N 정도가 됩니다. 이 덧셈·뺄셈의 쌍은 그 모양 때문에 '버터플라이 연산'이라고 부릅니다.
비는 N/log₂N으로, N = 1024이면 1024 ÷ 10 = 102.4, N = 65536이면 65536 ÷ 16 = 4096입니다. 점수가 클수록 효과가 크며, 실시간 스펙트럼 표시나 통신 수신기처럼 많은 DFT를 연속으로 계산하는 용도에는 빼놓을 수 없습니다.
두 계열의 합성곱은 주파수 쪽에서는 곱셈이 됩니다. 그래서 양쪽을 FFT로 변환해 곱하고 역FFT로 되돌리면, 긴 FIR 필터의 합성곱을 직접 계산하는 것보다 적은 연산으로 구할 수 있습니다. 다만 DFT끼리의 곱셈은 순환 합성곱에 해당하므로, 제로 패딩으로 길이를 맞추어 끝부분이 반대쪽으로 돌아 들어가는 것을 막아야 합니다.
정답: B. 약 100분의 1
N² = 1024² ≈ 105만, N log₂N = 1024 × 10 = 10240이며, 비는 N/log₂N = 1024 ÷ 10 = 102.4, 즉 약 100분의 1입니다. N이 클수록 차이는 벌어져서, 예를 들어 N = 65536에서는 약 4096분의 1이 됩니다. FFT는 DFT를 절반 크기의 DFT로 차례차례 나누어 공통 계산을 묶음으로써 연산을 줄입니다.
아닙니다. 2의 거듭제곱일 때가 가장 간단하고 빠른 경우가 많지만, 3이나 5 등의 인수로 나누는 혼합 기수 FFT나 소수 점수를 다루는 방법도 있으며, 일반적인 라이브러리는 임의의 점수를 계산할 수 있습니다. 2의 거듭제곱으로 맞추고 싶을 때는 제로 패딩으로 점수를 늘리기도 합니다.
같은 값을 계산하는 방법이므로 반올림 오차를 제외하면 일치합니다. FFT는 근사가 아니라, 계산 순서를 궁리하여 같은 결과를 빠르게 얻는 알고리즘입니다.
FFT는 DFT를 절반 크기의 DFT로 차례차례 나누어 공통 계산을 묶음으로써 연산을 줄입니다.
N점 DFT를 정의대로 계산하면 약 N²회, FFT(고속 푸리에 변환)로는 약 N log₂N회의 연산으로 …제로 패딩은 피크의 위치를 읽기 쉽게 하거나, FFT를 위해 점수를 2의 거듭제곱으로 맞추는 데 사용됩니다.
256점 신호 뒤에 0을 768개 덧붙여(제로 패딩) 1024점 DFT를 계산했다. 256점 그대로 DFT…송신 측은 역고속 푸리에 변환(IFFT), 수신 측은 고속 푸리에 변환(FFT)으로 효율적으로 처리할 수 있으며, 무선 LAN, 4G LTE, 5G NR, 지상파 디지털 방송 등에 사용되고 있습니다.
OFDM(직교 주파수 분할 다중)에 대한 설명으로 적절한 것은?또한 CP가 심볼 끝부분의 복사본이므로, 늦게 도착한 전파도 FFT로 처리하는 구간 안에서는 주기적인 신호로 보여 부반송파 사이의 직교성이 유지됩니다.
OFDM에서 각 심볼 끝부분의 일부를 복사하여 심볼 앞에 덧붙이는 순환 전치(CP, cyclic prefi…OFDM(직교 주파수 분할 다중) 주파수 분해능(Frequency Resolution) 군지연(Group Delay) 데시메이션(Decimation) 선형 위상(Linear Phase) 스펙트럼 누설(Spectral Leakage) 이동 평균 필터(Moving Average Filter) 이산 푸리에 변환(Discrete Fourier Transform) 임펄스 응답(Impulse Response) 차분 방정식(Difference Equation)