FFT (Fast Fourier Transform) 개념 정리

본 글은 디지털 신호처리를 RTL(Verilog/VHDL)로 구현하고자 하는 독자를 위한 FFT 기본 개념 정리이다.
DFT의 원리부터 버터플라이 구조, twiddle factor ROM, bit-reversal address generator 등 하드웨어 구현을 위한 핵심 구조를 중심으로 설명한다.

---

1. 왜 FFT를 알아야 하는가

FFT(Fast Fourier Transform)는 DFT(Discrete Fourier Transform)를 빠르게 계산하는 알고리즘이다.
즉, 시간 영역(Time Domain)의 신호를 주파수 영역(Frequency Domain)으로 바꿔주는 핵심 수단이다.

RTL(하드웨어 설계) 관점에서 FFT를 알아야 하는 이유는 다음과 같다.

1. FIR 필터 이후 단계로서 복소수 연산 구조를 이해할 수 있다.
2. 곱셈기·덧셈기·메모리 접근 패턴이 실제 DSP 코어와 동일하다.
3. 파이프라인, 고정소수점, 스케일링 같은 실무 설계 기법을 배울 수 있다.

이미지 설명:
FFT가 시간 영역 입력을 받아 주파수 영역으로 바꾸는 전체 흐름을 보여준다.
(예: x[n] → FFT → X[k])

---

2. DFT의 정의와 한계

DFT는 신호 x[n]을 주파수로 변환하는 수학적 식이다.

X[k] = Σ_{n=0}^{N-1} x[n] · e^{-j(2πkn/N)}

• X[k]: k번째 주파수 성분
• N: 변환 포인트 수
• e^{-j(2πkn/N)}: 회전 인자 (twiddle factor)

용어 설명:

• 복소수(Complex Number): 실수(real)와 허수(imaginary)를 함께 다루는 수.
  FFT에서는 실수부와 허수부를 모두 계산해야 한다.
• 회전 인자(twiddle factor): 주파수별로 입력 신호를 회전(위상 이동)시키는 복소수 계수.

하지만 DFT의 연산량은 N²으로 매우 크다.
예를 들어 N=1024이면 약 100만 번의 곱셈/덧셈이 필요하다.
FPGA에서는 클럭 한계 때문에 비효율적이다.

---

3. FFT의 기본 원리

FFT는 DFT의 연산을 분할 정복(Divide and Conquer)으로 줄이는 알고리즘이다.

핵심 아이디어는 다음과 같다.

1. 입력을 짝수 인덱스와 홀수 인덱스로 나눈다.
2. 각 부분에 대해 DFT를 수행한다.
3. 두 결과를 회전 인자(W_N^k)로 결합한다.

수식으로 표현하면 다음과 같다.

X[k] = E[k] + W_N^k · O[k]
X[k + N/2] = E[k] - W_N^k · O[k]

• E[k]: 짝수 인덱스의 DFT 결과
• O[k]: 홀수 인덱스의 DFT 결과
• W_N = e^{-j(2π/N)}: 회전 인자

이 과정을 반복하면 전체 연산량이 O(N log₂N)으로 감소한다.
즉, 1024포인트 FFT는 약 1만 번 수준으로 줄어든다.

---

4. 버터플라이(Butterfly) 연산 구조

FFT의 최소 단위 연산은 버터플라이(Butterfly)라고 한다.
이 연산은 두 개의 입력 a, b를 받아 두 개의 출력 y0, y1을 만든다.

y0 = a + W^k · b
y1 = a - W^k · b

• a, b: 입력 복소수
• W^k: 회전 인자 (cosθ - j·sinθ)
• y0, y1: 출력 복소수

용어 설명:

• 버터플라이라는 이름은 데이터 흐름이 X자 형태로 교차되기 때문이다.
• 두 입력이 합쳐지고 다시 나뉘며, 나비의 날개 모양처럼 보인다.

Verilog로 표현하면 다음과 같다.

module butterfly(
    input  signed [15:0] ar, ai, br, bi,
    input  signed [15:0] wr, wi,
    output signed [15:0] y0r, y0i, y1r, y1i
);
    wire signed [31:0] pr = br*wr - bi*wi;
    wire signed [31:0] pi = br*wi + bi*wr;

    assign y0r = ar + (pr >>> 15);
    assign y0i = ai + (pi >>> 15);
    assign y1r = ar - (pr >>> 15);
    assign y1i = ai - (pi >>> 15);
endmodule

---

5. FFT의 RTL 블록 구성

하드웨어에서 FFT를 구성할 때는 아래의 다섯 블록을 기억하자.

블록	역할	구현 형태
Sample RAM	입력/출력 데이터 저장	Dual-Port RAM
Twiddle ROM	회전 인자 저장	BRAM / ROM
Address Generator	버터플라이 페어 주소 계산	Counter + Bit-reversal
Butterfly Unit	복소 곱·덧셈 수행	DSP Slice
Stage Controller	각 스테이지 순환 제어	FSM 또는 Counter

---

6. DIT vs DIF 구조 비교

FFT는 구현 방식에 따라 DIT와 DIF로 나뉜다.

구분	DIT (Decimation-In-Time)	DIF (Decimation-In-Frequency)
입력 순서	bit-reversal 필요	정상 순서 가능
출력 순서	정상 순서	bit-reversal 필요
장점	메모리 접근 단순	스트리밍 설계에 유리
단점	입력 변환 필요	출력 재정렬 필요

설명:

• DIT: 입력 데이터를 짝수/홀수로 나눠 처리 → 출력이 순차적
• DIF: 주파수 영역에서 나눠 처리 → 출력이 섞인(bit-reversed) 순서

RTL에서는 DIF 구조가 더 단순해 실시간(Streaming) FFT에 자주 사용된다.

---

7. 비트 리버설(Bit-Reversal) 주소

FFT 결과를 정렬하려면 비트 리버설(bit-reversal)이 필요하다.

Index	Binary	Bit-Reversed	New Index
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

Verilog 예시:

function [LOGN-1:0] bit_reverse(input [LOGN-1:0] idx);
    integer i;
    begin
        for (i = 0; i < LOGN; i = i + 1)
            bit_reverse[i] = idx[LOGN-1-i];
    end
endfunction

---

8. 고정소수점(Fixed-Point) 스케일링

FFT는 스테이지마다 덧셈과 뺄셈이 반복되므로 값이 커질 수 있다.
이를 방지하기 위해 스케일링(scaling)을 적용한다.

구분	설명
Stage-wise Scaling	각 스테이지마다 1bit Right Shift (2배 축소)
Block Floating Point	전체 블록의 최대값 기준으로 공통 스케일
Saturation Logic	Overflow 시 최대값 고정 (Clip)

용어 설명:

• Fixed-point: 소수점을 고정된 비트 위치에 두는 방식 (예: Q1.15).
• Overflow: 계산 결과가 표현 가능한 범위를 넘는 현상.

---

9. 파이프라인 및 메모리 구조

FFT는 Stage 간 데이터 종속성이 적으므로 파이프라인을 쉽게 적용할 수 있다.

• 파이프라인(Pipeline): 연산 단계를 분리해 클럭당 처리량을 높이는 구조
• Dual-Port RAM: 동시에 읽고 쓰는 메모리
• Ping-Pong Buffer: Stage마다 입력/출력 버퍼를 교대로 사용

---

10. Verilog 루프 예시 (N=8, DIF 구조)

for (stage = 0; stage < LOGN; stage = stage + 1) begin
    group_size = 1 << (stage + 1);
    half = 1 << stage;

    for (g = 0; g < N; g = g + group_size) begin
        for (i = 0; i < half; i = i + 1) begin
            a = mem[g + i];
            b = mem[g + i + half];
            tw = twiddle_rom[i * (N >> (stage + 1))];
            {y0, y1} = butterfly(a, b, tw);
            mem[g + i]         = y0;
            mem[g + i + half]  = y1;
        end
    end
end

용어 해설:

• group_size: 한 번에 연산되는 데이터 그룹의 크기
• half: 한 버터플라이 페어의 간격
• twiddle_rom: 각 스테이지에서 사용할 회전 인자 ROM
• mem[]: 현재 스테이지의 샘플 메모리

---

11. 합성(Synthesis) 시 고려 사항

항목	설명
Twiddle ROM	BRAM 매핑 (16bit × N/2)
복소곱	DSP Slice 활용 (4-mul 구조)
Adder Tree	파이프라인으로 Timing Closure
Fmax 향상	Stage별 Register 삽입
Bit Width	Overflow 방지를 위한 Guard Bit 확보

---

12. 결론 및 다음 포스팅 예고

이번 글에서는 FFT의 수학적 원리부터 RTL 구조까지 단계별로 설명했다.
DFT보다 효율적인 FFT는 RTL 설계에서 “복소곱, 메모리 접근, 파이프라인”을 모두 포함한 종합 예제다.

다음에는 위 개념을 활용하여 FFT RTL 설계 프로젝트를 진행할 예정이다.