FFT 버터플라이 연산 계산기
표본 수열을 넣으면 고속 푸리에 변환(FFT)의 비트 역순 정렬과 단계별 나비(버터플라이) 연산을 트위들 인자와 함께 하나씩 보여줍니다.
쉼표나 공백으로 구분, 2의 거듭제곱 개(2·4·8·16·32·64). 현재 4개
1. 비트 역순 정렬
재귀적으로 짝수·홀수를 계속 반으로 쪼개는 과정을 반복문으로 펼치면, 입력이 인덱스의 이진수를 뒤집은 순서로 재배열됩니다.
| 원래 인덱스 | 역순 정렬 후 값 |
|---|---|
| [0] ← 원래 [0] | 1 |
| [1] ← 원래 [2] | 3 |
| [2] ← 원래 [1] | 2 |
| [3] ← 원래 [3] | 4 |
2. 단계별 나비 연산 (총 2단계, log₂4)
1단계 — 블록 크기 2
[0]↔[1] · W₂⁰= 1 → 4, -2
[2]↔[3] · W₂⁰= 1 → 6, -2
2단계 — 블록 크기 4
[0]↔[2] · W₄⁰= 1 → 10, -2
[1]↔[3] · W₄¹= 0 − i → -2 + 2i, -2 − 2i
3. 최종 결과 X[k]
| k | X[k] | 크기 |
|---|---|---|
| 0 | 10 | 10 |
| 1 | -2 + 2i | 2.8284 |
| 2 | -2 | 2 |
| 3 | -2 − 2i | 2.8284 |
사용 방법
- 1표본 수열을 쉼표나 공백으로 구분해 넣습니다. 개수는 2의 거듭제곱(2·4·8·16·32·64)이어야 합니다.
- 2비트 역순 정렬로 재배열된 순서를 확인합니다.
- 3log₂N 단계를 거치며 각 단계의 나비 연산(top±W·bottom)과 트위들 인자 W를 확인합니다.
- 4최종 결과 X[k]를 정의 그대로의 DFT(dft-calc)와 대조해 같은 값인지 확인합니다.
자주 묻는 질문
Cooley-Tukey 고속 푸리에 변환(FFT)에서 두 값을 트위들 인자로 묶어 새 두 값을 만드는 기본 연산입니다. top' = top + W·bottom, bottom' = top − W·bottom으로 계산하며, 다이어그램으로 그리면 나비 모양이 되어 이런 이름이 붙었습니다.
정의 그대로의 DFT는 O(N²)으로 모든 쌍을 곱해 더하지만, FFT는 절반씩 나눠 재사용하는 분할정복으로 O(N log N)에 같은 결과를 냅니다. 이 계산기는 그 나비 연산 과정을 단계별로 보여주고, edu/dft-calc의 정의 그대로 계산한 값과 같은지 대조할 수 있습니다.
짝수/홀수로 계속 반씩 쪼개는 재귀 분할 과정을 반복문으로 펼치면, 입력이 처리되는 순서가 각 인덱스의 이진수를 뒤집은 순서와 같아집니다. 그래서 계산을 시작하기 전에 미리 이 순서로 재배열해 둡니다.
W_m^j = e^(−2πi·j/m)입니다. m은 그 단계의 블록 크기(2, 4, 8 ... 순으로 커짐)이고 j는 블록 안에서의 위치입니다. 전체 표본 수 N이 아니라 그 단계의 블록 크기 m을 기준으로 삼는 것이 핵심입니다.
2의 거듭제곱만 지원하며(2·4·8·16·32·64), 나비 연산 개수가 화면에 다 나열되도록 64개까지로 제한했습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 실수 표본만 입력받습니다(허수부는 0으로 둡니다).
- 표본 개수는 2의 거듭제곱이어야 하며 최대 64개까지 지원합니다.
- Cooley & Tukey(1965) 원 논문의 radix-2 분할정복 절차를 그대로 구현한 결정적 알고리즘이라 dataExpiry 등록 대상이 아닙니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 5일 · 결과는 참고용 추정치입니다.