이산 푸리에 변환과 고속 푸리에 변환

자주 하는 실수와 요약

자주 하는 실수

실수 바른 생각 나온 문제
계수를 구할 때 화살표를 시계 반대 방향 e+2πikn/N로 곱한다 계수는 거꾸로, 시계 방향 e−2πikn/N로 돌려 곱한다. 방향을 바꾸면 X[1] 과 X[N−1] 이 자리를 바꿔 가장 높은 시각이 거울처럼 뒤집힌다 문제 1
계수를 N개보다 많이 구하면 더 정확히 되돌릴 수 있다 ζN = 1 이라 X[k + N] = X[k]. 서로 다른 계수는 N개뿐이고, 더 구하면 같은 것을 한 번 더 더하게 된다 문제 2
이산 푸리에 변환은 곱해서 더할 뿐이라 토큰 순서를 모른다 k = 0 줄만 합이고, 나머지 줄은 칸 번호마다 다른 화살표를 곱하므로 순서가 바뀌면 결과가 바뀐다 문제 3
반대로 돌기만 하면 두 화살표의 합이 실수 축에 머문다 길이와 출발 각도까지 실수 축에 비친 거울상(켤레)이어야 한다 문제 4
어느 신호든 계수 절반만 남겨도 된다 켤레 대칭은 칸이 실수일 때만 성립한다. 복소수 칸이면 계수 N개가 모두 새 정보다 문제 5
실수 부분만 남겨도 칸을 되살릴 수 있다 실수 칸이면 Re X[k] = Re X[N−k] 라 숫자가 모자란다. 반대칭 부분이 모두 사라진다 문제 6
고속 푸리에 변환의 곱셈은 단마다 칸 수만큼이다 버터플라이 하나의 곱 ζkb 를 두 출력이 나눠 쓰므로 단마다 N/2번이고, 1·−1·i·−i 곱을 빼면 더 적다 문제 8
곱셈이 적은 쪽이 늘 빠르다 하드웨어가 잘하는 꼴(큰 행렬 곱)이면 곱셈이 몇십 배 많아도 빠를 수 있다. 칸 수가 커지면 N/log₂N 이 벌어져 결국 뒤집힌다 문제 9
제로 패딩하면 주파수를 더 잘게 가를 수 있다 번호만 촘촘해진다. 두 주파수를 가르는 힘은 기록 길이 T 가 정하고, 차이의 역수만큼은 재야 한다 문제 10, 11
이산 푸리에 변환으로 곱하고 되돌리면 칸마다 곱해 더한 합성곱과 같다 칸이 한 바퀴로 이어져 넘친 끝이 처음에 겹친다. 결과 길이 2L − 1 칸 이상으로 제로 패딩해야 같다 문제 12

요약

flowchart LR
  A["칸 N개<br/>x[n]"] --> B["이산 푸리에 변환<br/>계수 N개, 되돌릴 수 있다"]
  B --> C["실수 칸이면 켤레 대칭<br/>절반만 새 정보"]
  B --> D["반으로 나눠 다시 쓰기<br/>N² → N log₂N"]
  B --> E["빈 간격 1/T<br/>제로 패딩은 번호만 촘촘히"]

막힌 곳