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

혼동하기 쉬운 점과 요약

토론 1. 계수의 크기가 같으면 이산 푸리에 변환은 토큰 순서를 모르나

글 [1, 2, 3, 4] 와 한 칸씩 돌려 놓은 [4, 1, 2, 3] 의 칸 4개 이산 푸리에 변환을 비교한다. 계수의 크기가 같으면 두 글을 구분할 수 없는가?

선생님 T01
선생님

글 [1, 2, 3, 4]를 한 칸씩 돌려 [4, 1, 2, 3]으로 놓아요. 두 글의 계수를 비교하면 어떨까요?

이서연 S04
이서연

한 칸 돌리면 계수마다 길이 1인 화살표가 곱해질 뿐이라 크기는 바뀌지 않아요. 크기가 다 같으면 이산 푸리에 변환은 두 글을 구분 못 하는 거니까, 결국 순서는 모르는 것 아닐까요?

김민준 M01
김민준

계산해 볼게. [1, 2, 3, 4]는 [10, −2 + 2i, −2, −2 − 2i], [4, 1, 2, 3]은 [10, 2 + 2i, 2, 2 − 2i]야. 크기는 10, 2.83, 2, 2.83으로 똑같아.

선생님 T02
선생님

크기는 같네요. 계수 자체도 같나요?

이서연 S06
이서연

아니요. −2 + 2i가 2 + 2i로 바뀌었어요. 각도가 135°에서 45°로 돌았네요.

김민준 M02
김민준

−2는 2가 됐고. FNet 처럼 실수 부분만 넘기면 [10, −2, −2, −2]와 [10, 2, 2, 2]라서 다음 층이 받는 숫자부터 달라.

선생님 T01
선생님

그럼 순서는 계수의 어디에 들어 있는 걸까요?

이서연 S07
이서연

각도요. 한 칸 돌리면 주파수 k인 계수가 시계 방향으로 k × 90°씩 돌아요. 크기는 「어떤 물결이 얼마나」만 말하고 「어디서부터」는 각도가 말하는 거였어요. 이산 푸리에 변환은 순서를 알고, 크기만 보면 그걸 놓칠 뿐이에요.

선생님 T13
선생님

그래요. k = 0 줄만 합이고, 나머지 줄은 칸 번호마다 다른 화살표를 곱하니까 순서가 바뀌면 계수가 바뀌어요. 바뀌는 것이 크기가 아니라 각도일 수도 있을 뿐이에요.

토론 2. 계수를 칸 수보다 많이 구하면 더 정확히 되살릴 수 있나

문제 1 의 기온 네 칸 [14, 11, 21, 22] 에서 계수를 X[0] 부터 X[7] 까지 여덟 개 구해, 되돌리는 식을 1/8 로 쓰면 기온이 더 잘 되살아나는가?

선생님 T01
선생님

문제 1의 기온 네 칸 [14, 11, 21, 22]에서 계수를 X[0]부터 X[7]까지 여덟 개 구한다고 해요. 계수가 두 배면 기온을 더 잘 되살릴 수 있을까요?

김민준 M04
김민준

계수가 많을수록 물결을 더 많이 쓰는 거니까 더 정확해지겠죠. 칸 사이 값까지 잡힐 것 같아요.

이서연 S03
이서연

그 전에 X[4]부터 구해 보자. 칸 4개면 화살표가 네 번 곱해 1이 되니까, k = 4면 칸마다 곱하는 화살표가 전부 1이야.

김민준 M01
김민준

그럼 X[4]는 그냥 합 68이네. X[0]이랑 같아. X[5]도 계산하면 −7 + 11i로 X[1]이고.

선생님 T02
선생님

여덟 개를 다 넣고 1/8로 되돌리면 무엇이 나올까요?

김민준 M06
김민준

같은 계수가 두 번씩 들어가니까 합이 두 배, 1/8로 나누면… 처음과 똑같은 [14, 11, 21, 22]예요. 더 정확해진 것도 없고 칸 사이 값이 생긴 것도 아니에요.

이서연 S07
이서연

새 계수가 아니라 이미 있던 걸 한 번 더 센 거니까. 칸 네 개로 서로 다르게 보이는 화살표는 네 개뿐이야.

김민준 M08
김민준

계수를 N개보다 많이 구해 봐야 X[k + N] = X[k]라 같은 걸 또 더할 뿐이네요. 칸 N개에 서로 다른 계수는 N개예요.

혼동하기 쉬운 점

혼동하기 쉬운 생각 바른 생각 나온 문제
계수를 구할 때 화살표를 시계 반대 방향 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 줄만 합이고, 나머지 줄은 칸 번호마다 다른 화살표를 곱하므로 순서가 바뀌면 결과가 바뀐다 토론 1
반대로 돌기만 하면 두 화살표의 합이 실수 축에 머문다 길이와 출발 각도까지 실수 축에 비친 거울상(켤레)이어야 한다 문제 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

요약

기온 여덟 칸이든 칸 백만 개든, 칸 N개로 서로 다르게 보이는 도는 화살표는 N개뿐이라 칸은 계수 N개로 늘지도 줄지도 않고 다시 적힌다. 계수만 들고 있어도 칸이 하나도 틀리지 않고 돌아오며, 그 계수는 같은 화살표가 되풀이되는 덕에 반으로 나눠 계산을 다시 쓰면 빨리 구해진다.

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/>제로 패딩은 번호만 촘촘히"]

정리 연습문제

물음. 칸 8개짜리 신호에 이산 푸리에 변환을 했다. 서로 다른 계수는 몇 개인가?

  • [x] 8개. 주파수 번호는 8마다 반복된다 〔맞음: 8분의 1 바퀴씩 도는 화살표는 8번이면 제자리라 번호에 8을 더해도 같은 계수가 나온다. 8개면 칸을 그대로 되살린다.〕
  • [ ] 원하는 만큼. 16개를 구하면 더 정확히 되살린다 〔틀림: 9번째부터는 앞의 계수가 반복된다. 더 구하면 같은 것을 한 번 더 더하게 된다.〕
  • [ ] 4개. 계수는 늘 절반이다 〔틀림: 절반만 새 정보인 것은 칸이 실수일 때뿐이다.〕

물음. 계수의 절반만 계산해 저장해도 신호를 되살릴 수 있는 경우는?

  • [x] 칸이 모두 실수인 신호 〔맞음: 실수 칸이면 반대쪽 번호의 계수가 켤레라서 절반에서 나머지를 얻는다.〕
  • [ ] 어느 신호든 된다 〔틀림: 칸이 복소수이면 칸 수만큼의 계수가 모두 새 정보다.〕
  • [ ] 어느 신호든 계수의 실수 부분만 남기면 된다 〔틀림: 실수 칸이면 실수 부분은 반대쪽 번호끼리 같아 숫자가 모자란다. 반대칭 부분이 모두 사라진다.〕

물음. 칸 1024개(2를 10번 곱한 수)짜리 신호를 고속 푸리에 변환으로 계산한다. 정의대로 하나하나 곱할 때보다 곱셈이 대략 몇 분의 1로 주는가?

  • [ ] 2분의 1. 반으로 나눠 다시 쓰기 때문이다 〔틀림: 반으로 나누기를 한 번이 아니라 열 단 거듭한다.〕
  • [x] 약 100분의 1 〔맞음: 그대로는 칸 수의 제곱, 고속 푸리에 변환은 칸 수에 단 수 10을 곱한 만큼이라 1024를 10으로 나눈 만큼 준다.〕
  • [ ] 1024분의 1 〔틀림: 단마다 곱셈이 남아서 단 수 10만큼은 곱해야 한다.〕

물음. 걸음을 4초 동안 기록했다. 주파수가 0.1 Hz 차이 나는 두 걸음을 가르려고 뒤에 0을 붙여 칸을 네 배로 늘렸다. 두 걸음이 갈리는가?

  • [ ] 갈린다. 빈 간격이 네 배 촘촘해졌다 〔틀림: 0을 붙이면 번호만 촘촘해질 뿐 새로 측정한 것은 없다.〕
  • [x] 갈리지 않는다. 0.1 Hz 차이를 구분하려면 10초는 측정해야 한다 〔맞음: 두 주파수를 구분하는 힘은 기록 길이가 정하고, 차이의 역수만큼은 측정해야 한다.〕
  • [ ] 0을 더 많이 붙이면 갈린다 〔틀림: 0을 얼마나 붙이든 기록 길이는 4초 그대로다.〕

물음. 길이 100칸인 두 신호를 각각 변환해 주파수마다 곱하고 되돌려 합성곱을 구하려 한다. 칸마다 곱해 더한 합성곱과 같게 하려면 몇 칸 이상으로 제로 패딩해야 하는가?

  • [ ] 100칸 그대로 해도 된다 〔틀림: 칸이 한 바퀴로 이어져 있어 넘친 끝이 처음에 겹쳐 더해진다.〕
  • [x] 199칸 이상 〔맞음: 합성곱 결과는 199칸이라 그만큼 자리를 마련해야 넘친 끝이 처음에 겹치지 않는다.〕
  • [ ] 400칸 이상 〔틀림: 더 늘려도 결과는 같지만 199칸이면 충분하다.〕

물음. 길이 512에서는 행렬 곱의 곱셈 수가 고속 푸리에 변환보다 몇십 배 많다. 그런데 어떤 칩에서는 행렬 곱이 더 빨랐다. 왜 그런가?

  • [ ] 측정이 잘못되었다. 곱셈이 적은 쪽이 늘 빠르다 〔틀림: 계산 시간은 곱셈 수만으로 정해지지 않는다.〕
  • [x] 그 칩이 큰 행렬 곱을 아주 잘해서다. 길이가 아주 길어지면 다시 고속 푸리에 변환이 이긴다 〔맞음: 하드웨어가 잘하는 형태면 곱셈이 많아도 빠를 수 있다. 길이가 커질수록 곱셈 수 차이가 벌어져 결국 뒤집힌다.〕
  • [ ] 행렬 곱이 길이와 상관없이 늘 빠르다 〔틀림: 곱셈 수 차이는 길이가 길수록 벌어져서, 아주 긴 길이에서는 고속 푸리에 변환이 이긴다.〕

막힌 곳

이제 우리는 칸 N개를 계수 N개로 빠짐없이 옮겨 적고, 그 계수를 반으로 나눠 다시 쓰는 계산으로 빨리 구할 수 있다. 다만 계수가 옮겨 적는 것은 칸에 적힌 값뿐이다.