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

주파수 빈: 기록 길이가 주파수를 구분하는 세밀함을 정한다

기온 여덟 칸에서는 주파수 번호 k가 「하루에 몇 번」이라 읽기 쉬웠지만, 실제 기록은 초 단위다. 휴대폰 만보기 앱은 가속도계가 1초에 수십 번 측정한 가속도에서 1초에 몇 걸음을 딛는지(걸음 주파수)를 읽는다. 1초에 32번, 4초 동안 측정하면 칸이 128개다. 이때 계수 번호 k = 7은 몇 Hz의 물결이고, 걸음이 1.8 Hz(1분에 108걸음)면 어느 번호에 나타날까? 번호 사이에 떨어지면 칸 끝에 0을 붙여 칸 수를 늘려서 더 잘게 읽어 낼 수 있을까?

4초 동안의 걸음

칸 사이 시간 간격을 Δ = 1/32초라 하자. 칸 N = 128개는 T = NΔ = 4초 동안의 기록이다. 주파수 번호 k는 「기록 전체 동안 물결이 몇 번 반복되나」였으니, 1초에는 k/4번, 다시 말해 k/4 Hz다. 이웃한 번호 사이가 0.25 Hz다.

1분에 108걸음, 1.8 Hz로 걸을 때의 가속도 변화를 코사인 물결로 두고 계수를 구하면, 크기가 가장 큰 번호는 k = 7(1.75 Hz)이고 2|X|/N은 0.944다. 옆의 k = 8(2.0 Hz)에도 0.226이 나온다. 1.8 Hz는 1.75와 2.0 사이라 어느 번호에도 딱 일치하지 않고, 둘에 나뉘어 묻어난다. 앱이 가장 큰 번호를 그대로 읽으면 1분에 105걸음이라 3걸음 모자라게 센다.

이번에는 128칸 끝에 0을 896개 붙여 1024칸으로 만들어 변환한다. 이렇게 신호 끝에 0을 붙여 칸 수를 늘리는 일을 제로 패딩 (끝에 0 붙이기 / zero padding)이라 한다. 번호 사이가 32/1024 = 0.03125 Hz로 여덟 배 잘게 나뉘고, 가장 큰 번호가 1.8125 Hz, 1분에 108.75걸음이다. 64배(8192칸)로 제로 패딩하면 1.80078 Hz, 108.05걸음이다. 제로 패딩한 1024칸의 계수 가운데 여덟 번째마다 하나씩 뽑으면 128칸의 계수와 똑같다. 제로 패딩은 새 정보를 보태지 않고, 128칸이 이미 정한 매끈한 곡선 위에서 점을 더 촘촘히 찍어 보는 일이다.

이렇게 주파수 번호 하나가 맡는 주파수 폭을 주파수 빈 (번호 하나가 맡는 주파수 칸 / frequency bin)이라 하고, 이웃한 빈 사이의 간격 1/T를 빈 간격(bin spacing)이라 한다. 번호 k의 주파수와 함께 적으면 아래와 같다.

fk=kNΔ=k fsN,빈 간격=1T,T=NΔ\textcolor{#0078e1}{f}_{\textcolor{#0078e1}{k}} = \frac{\textcolor{#0078e1}{k}}{\textcolor{#3c4bff}{N}\textcolor{#697800}{\Delta}} = \frac{\textcolor{#0078e1}{k}\,\textcolor{#697800}{f_s}}{\textcolor{#3c4bff}{N}}, \qquad \text{빈 간격} = \frac{1}{\textcolor{#a67a63}{T}}, \qquad \textcolor{#a67a63}{T} = \textcolor{#3c4bff}{N}\textcolor{#697800}{\Delta}
fk번호 k 가 나타내는 주파수 (Hz: 1 초에 몇 번)k주파수 번호N칸 수Δ칸 간격 (초)fs=1/Δ1 초에 재는 횟수 (여기서는 32)T기록 길이 (초)\begin{array}{ll} \textcolor{#0078e1}{f}_{\textcolor{#0078e1}{k}} & \text{번호 } k \text{ 가 나타내는 주파수 (Hz: 1 초에 몇 번)} \\ \textcolor{#0078e1}{k} & \text{주파수 번호} \\ \textcolor{#3c4bff}{N} & \text{칸 수} \\ \textcolor{#697800}{\Delta} & \text{칸 간격 (초)} \\ \textcolor{#697800}{f_s} = 1/\textcolor{#697800}{\Delta} & \text{1 초에 재는 횟수 (여기서는 32)} \\ \textcolor{#a67a63}{T} & \text{기록 길이 (초)} \end{array}

빈 간격은 칸 간격이 아니라 기록 길이가 정하므로, 1초에 1000번씩 측정해도 4초만 측정하면 빈 간격은 0.25 Hz다. 제로 패딩하면 번호가 촘촘해져 봉우리 자리를 더 잘 읽을 수 있지만, 봉우리의 폭은 여전히 1/T 쯤이다. 길이 T 동안만 측정한 기록은 끝없이 이어지는 물결에 폭 T 인 상자 윈도우를 곱한 것이라, 봉우리가 그 상자의 푸리에 변환인 sinc 모양으로 번지고 처음 0 이 봉우리에서 1/T Hz 떨어진 곳에 오기 때문이다. 가장 높은 번호 N/2는 fs/2 = 16 Hz이고, 그 위의 번호는 켤레 대칭 때문에 음의 주파수다.

왼쪽: 1.8 Hz 걸음 4초 기록. 갈색 점은 128칸 그대로의 계수(0.25 Hz 마다), 보라 선은 제로 패딩으로 1024칸으로 늘린 계수다. 가운데·오른쪽: 1.8 Hz 와 1.9 Hz 두 걸음을 4초, 10초 기록한 것(보라 선은 8192칸으로 제로 패딩). 회색 점선이 실제 걸음 주파수(s4_pad.py, figs.py)
왼쪽: 1.8 Hz 걸음 4초 기록. 갈색 점은 128칸 그대로의 계수(0.25 Hz 마다), 보라 선은 제로 패딩으로 1024칸으로 늘린 계수다. 가운데·오른쪽: 1.8 Hz 와 1.9 Hz 두 걸음을 4초, 10초 기록한 것(보라 선은 8192칸으로 제로 패딩). 회색 점선이 실제 걸음 주파수(s4_pad.py, figs.py)
직접 움직여 보기주파수 빈과 제로 패딩크게 열기

레이더의 도플러: 펄스를 몇 번 쏘아야 두 속도가 갈리나

구급차가 다가올 때는 사이렌이 높게 들리다가 지나가고 나면 낮아진다. 다가오는 물체에 부딪혀 되돌아온 전파도 이렇게 주파수가 바뀌고, 레이더 스피드건과 군의 감시 레이더는 바뀐 양으로 물체의 속도를 측정한다. 전파가 갔다가 돌아오므로 바뀐 양은 「2 × 다가오는 속력 ÷ 전파의 파장」이고, 바뀐 주파수의 양을 도플러 주파수라 한다. 같은 거리에서 두 차량이 조금 다른 속력으로 다가오면 레이더는 두 대를 볼까, 한 대를 볼까? 두 걸음을 가르던 물음과 같은 물음이다.

파장 3 cm(약 10 GHz) 전파로 20 m/s와 21.5 m/s로 다가오는 두 차량을 본다고 하자. 도플러 주파수는 2 × 20 / 0.03 = 1333.3 Hz와 2 × 21.5 / 0.03 = 1433.3 Hz로, 100 Hz 차이다. 펄스 도플러 레이더는 전파를 짧은 펄스로 끊어 쏘고, 같은 거리에서 돌아온 메아리를 펄스마다 하나씩 모은다. 1초에 5000번 쏜다면 펄스와 펄스 사이에 두 메아리의 위상이 96.0°와 103.2°씩 돌아가므로, 모은 값은 1초에 5000번 측정한 1333.3 Hz와 1433.3 Hz 물결의 합이다. 레이더는 펄스마다 모은 값을 이산 푸리에 변환해서 봉우리 자리로 속도를 읽는다. 모은 펄스가 N개면 빈 간격은 5000/N Hz이고, 기록 길이 T = N/5000초의 역수 1/T와 같다.

펄스 16번(3.2 ms)이면 빈 간격이 312.5 Hz, 속도로 바꾸면 0.03 ÷ (2 × 0.0032) = 4.69 m/s다. 8192칸으로 제로 패딩해도 봉우리는 20.75 m/s에 하나뿐이어서, 레이더는 두 차량을 한 대로 본다. 펄스 50번(10 ms)이면 빈 간격이 100 Hz(1.5 m/s)가 되어 19.72 m/s와 21.77 m/s에 봉우리가 둘 서고, 128번(25.6 ms)이면 20.0 m/s와 21.5 m/s로 실제 속도에 맞는다. 1.8 Hz와 1.9 Hz 걸음을 구분하는 데 10초가 필요했던 것과 같은 계산이다. 두 도플러 주파수를 구분하려면 기록 길이가 차이의 역수, 1/100 Hz = 10 ms쯤 돼야 한다.

같은 거리에서 20 m/s와 21.5 m/s로 다가오는 두 차량을 펄스 도플러 레이더로 본 스펙트럼(파장 3 cm, 1초에 펄스 5000번, 8192칸으로 제로 패딩). 펄스 16번(3.2 ms)이면 봉우리 하나, 50번(10 ms)이면 둘로 갈라지기 시작하고, 128번(25.6 ms)이면 회색 점선의 실제 속도에 맞는다. 숫자는 이 책의 장난감 설정이다(sources/dft-fft/s5_radar.py)
같은 거리에서 20 m/s와 21.5 m/s로 다가오는 두 차량을 펄스 도플러 레이더로 본 스펙트럼(파장 3 cm, 1초에 펄스 5000번, 8192칸으로 제로 패딩). 펄스 16번(3.2 ms)이면 봉우리 하나, 50번(10 ms)이면 둘로 갈라지기 시작하고, 128번(25.6 ms)이면 회색 점선의 실제 속도에 맞는다. 숫자는 이 책의 장난감 설정이다(sources/dft-fft/s5_radar.py)

펄스를 오래 모을수록 속도를 잘게 가르지만 공짜는 아니다. 모으는 동안 두 차량이 속력을 바꾸지 않아야 봉우리가 한 위치에 유지된다. 「기록 내내 같은 물결이 반복된다」는 이산 푸리에 변환의 전제를 레이더도 그대로 진다. 한 방향에 오래 머물수록 다른 방향을 살필 시간도 줄어든다.

ML에서: 긴 합성곱을 고속 푸리에 변환으로 계산할 때의 제로 패딩

글 길이만큼 긴 합성곱 커널을 쓰는 언어 모델이 있다. 폴리(Michael Poli)와 동료들의 Hyena(2023)는 어텐션 대신 길이 L인 입력에 길이 L인 합성곱 커널을 걸고, 이 합성곱을 고속 푸리에 변환으로 계산한다. 두 신호를 각각 이산 푸리에 변환해 주파수마다 곱하고 되돌리면 합성곱이 나온다는 성질을 쓰는 것인데, 왜 그렇게 되는지는 평행이동 대칭을 다루며 따진다. 이렇게 하면 칸마다 곱해 더하는 L²번 대신 L log L에 비례하는 계산으로 끝난다. 논문은 Hyena 가 잘 최적화한 어텐션보다 길이 8천에서 두 배, 6만 4천에서 100배 빠르다고 보고했다. 그런데 논문은 고속 푸리에 변환에 넣기 전에 입력과 합성곱 커널 끝을 제로 패딩해 길이를 2L − 1로 맞춘다고 적었다(공개된 코드는 한 칸 더 넉넉한 2L칸을 쓴다). 빈 간격을 잘게 하려는 것은 아니다. 무엇 때문인지는 아래 문제 12에서 본다.

문제 10. 맥박을 15초만 세면

1분에 73번 뛰는 맥박을 측정한다. (가) 15초 동안 센 수에 4를 곱하는 방법으로 얻을 수 있는 값은 무엇인가? 10초, 30초, 60초 동안 세면? (나) 이 방법의 눈금(얻을 수 있는 값 사이의 간격, 본문의 빈 간격에 해당)은 세는 시간과 어떤 관계인가? (다) 15초 세고 나서 「나머지 45초 동안은 0번 뛰었다」고 치고 60초 동안 센 것처럼 계산하면 눈금이 1이 되는가?

1분에 73번 뛰는 맥박의 박동과 세는 시간 10초·15초·30초·60초(problems_figs.py)
1분에 73번 뛰는 맥박의 박동과 세는 시간 10초·15초·30초·60초(problems_figs.py)
김민준 M01
김민준

(가)는 15초면 18.25번 뛰니까 18이나 19를 세서 72나 76이에요. 10초면 72나 78, 30초면 72나 74, 60초면 73이요.

이서연 S01
이서연

(나)는 15초에 4, 10초에 6, 30초에 2, 60초에 1이니까 눈금이 60/T야. 오래 셀수록 잘게 구분돼.

이서연 S03
이서연

그럼 (다)처럼 60초 동안 센 걸로 치면 T = 60이니까 눈금이 1이 되고, 15초만 세고도 60초만큼 잘게 구분되겠네?

김민준 M05
김민준

눈금은 1이 되는데… 센 수는 18이니까 맥박이 18이 돼 버려. 4를 안 곱하면 이렇게 나와.

이서연 S04
이서연

아, 눈금만 촘촘해지고 값은 엉뚱해졌네.

선생님 T14
선생님

그래서 제로 패딩으로 늘린 계산은 패딩하기 전의 진폭을 일치시키려고 원래 칸 수로 나눠요. 그렇게 해도 늘어나는 것이 있을까요?

이서연 S08
이서연

새로 센 박동은 하나도 없어요. 15초 동안의 정보로 할 수 있는 건 그대로고, 계산이 그 사이 값을 매끈하게 이어 줄 뿐이에요. 걸음 봉우리 자리를 1.8 Hz 근처로 더 잘 읽어 낸 건 물결이 하나뿐이라 봉우리 꼭대기를 찾기만 하면 됐기 때문이고요.

김민준 M11
김민준

제로 패딩은 저화질 사진을 확대해서 칸을 촘촘하게 다시 그리는 일이네요. 그래도 멀리서 찍은 간판 글씨가 새로 읽히지는 않잖아요.

문제 11. 두 사람이 함께 걸으면

두 사람이 나란히 걷는데 한 사람은 1.8 Hz, 다른 사람은 1.9 Hz 로 걷고, 가속도계(1초에 32번)에는 두 사람의 걸음 진동이 같은 크기로 더해져 잡힌다. (가) 4초 기록을 8192칸으로 제로 패딩해 변환하면 봉우리가 몇 개 보이는가? (나) 10초, 20초 기록이면? (다) 두 걸음을 구분하려면 얼마나 오래 측정해야 하는가? (위젯 4의 「문제 11」 단추로 확인해 보자.)

1초에 32번 측정한 1.8 Hz 와 1.9 Hz 걸음 진동의 처음 4초(위)와 비교할 기록 길이 4초·10초·20초(아래)(problems_figs.py)
1초에 32번 측정한 1.8 Hz 와 1.9 Hz 걸음 진동의 처음 4초(위)와 비교할 기록 길이 4초·10초·20초(아래)(problems_figs.py)
김민준 M01
김민준

64배나 제로 패딩하면 빈 간격이 0.004 Hz쯤이니까, 0.1 Hz 떨어진 두 봉우리는 넉넉히 분리되겠죠. 두 개요.

선생님 T01
선생님

위젯에서 4초로 해 봐요.

김민준 M06
김민준

봉우리가 1.8516 Hz에 하나뿐이에요. 1.8과 1.9 사이에 뭉뚝한 봉우리 하나요. 칸을 아무리 늘려도 분리 안 돼요.

이서연 S01
이서연

봉우리 하나의 폭이 1/T 쯤이랬잖아. 4초면 폭이 0.25 Hz라 0.1 Hz 떨어진 두 봉우리가 한 덩어리로 겹쳐. 10초면 폭이 0.1 Hz라 1.7812와 1.918에 두 봉우리가 서고, 20초면 1.793과 1.9062로 실제 걸음 주파수 1.8, 1.9 Hz에 더 가까워져.

선생님 T13
선생님

그래요. 두 주파수를 가르려면 기록 길이가 차이의 역수, 1/0.1 = 10초쯤은 돼야 해요. 제로 패딩은 봉우리 하나의 자리를 잘 읽게 할 뿐, 겹친 봉우리를 떼어 주지는 못해요.

김민준 M05
김민준

레이더도 똑같네요. 1.5 m/s 차이로 다가오는 두 차는 도플러 주파수가 100 Hz 차이니까, 펄스를 10 ms 넘게 모아야 두 대로 보여요. 1초에 5000번 쏘면 50번이요.

이서연 S01
이서연

두 사람의 걸음은 0.1 Hz 차이라 10초, 레이더는 100 Hz 차이라 10 ms. 차이가 천 배 크니까 측정하는 시간은 천 분의 일이면 돼.

이서연 S11
이서연

두 물결의 차이만큼 느린 맥놀이가 한 번은 다 지나가야 둘이 다르다는 걸 알 수 있는 거네. 0.1 Hz 맥놀이 한 번이 10초야.

위젯 4 · 문제 11 설정
위젯에서 열기: 위젯 4 · 문제 11 설정

문제 12. 고속 푸리에 변환으로 합성곱 하기

칸 u = [1, 2, 3, 4] 와 합성곱 커널 h = [1, 1] 의 합성곱을 구한다. (가) 칸마다 곱해 더하는 방법(h 를 한 칸씩 밀며 겹친 곳을 곱해 더하기)으로 구하라. 결과는 몇 칸인가? (나) u 와 h(끝에 0을 둘 붙여 4칸으로)를 각각 칸 4개의 이산 푸리에 변환으로 바꿔 주파수마다 곱한 뒤 되돌리면 무엇이 나오는가? (다) 칸 5개, 7개로 제로 패딩하면? Hyena 는 길이 L 인 입력과 합성곱 커널을 왜 2L − 1 칸으로 제로 패딩하는가? (위젯 4 아래쪽의 칸 수 슬라이더로 확인해 보자.)

칸 u = [1, 2, 3, 4] 와 합성곱 커널 h = [1, 1] 을 칸 4개·5개·7개로 맞춘 모습. 회색 0 은 끝에 붙인 0(problems_figs.py)
칸 u = [1, 2, 3, 4] 와 합성곱 커널 h = [1, 1] 을 칸 4개·5개·7개로 맞춘 모습. 회색 0 은 끝에 붙인 0(problems_figs.py)
이서연 S01
이서연

(가)는 h를 한 칸씩 밀면서 겹친 곳을 곱해 더하면 [1, 1 + 2, 2 + 3, 3 + 4, 4] = [1, 3, 5, 7, 4]로 다섯 칸이에요.

김민준 M01
김민준

(나)는 numpy 로 해 볼게. [5, 3, 5, 7]이 나와. 첫 칸이 1이 아니라 5네. 어디서 어긋났지?

선생님 T01
선생님

넣은 건 맞아요. 5는 어디서 왔을까요? (가)의 결과와 비교해 봐요.

김민준 M05
김민준

1 + 4요. 다섯째 칸 4가 칸 4개 안에 들어갈 자리가 없어서 맨 앞으로 넘어가 첫 칸에 더해졌어요.

이서연 S01
이서연

이산 푸리에 변환은 칸 N개가 한 바퀴로 이어진 것처럼 다뤘잖아. 칸 번호 4가 칸 번호 0과 같은 자리야. 그래서 넘친 부분이 처음으로 돌아와 겹쳐.

선생님 T01
선생님

그럼 (다)처럼 칸을 늘리면요?

김민준 M01
김민준

칸 5개면 [1, 3, 5, 7, 4]로 맞고, 7개면 [1, 3, 5, 7, 4, 0, 0]이에요. 넘칠 자리가 생겼네요.

선생님 T02
선생님

길이 L인 입력과 길이 L인 합성곱 커널이면 결과는 몇 칸이에요?

이서연 S02
이서연

한 칸씩 밀어 보면, 처음 겹칠 때부터 다 빠져나갈 때까지… L + L − 1 = 2L − 1칸이에요.

선생님 T01
선생님

Hyena 가 딱 그만큼 제로 패딩하는 건 왜일까요?

이서연 S08
이서연

그만큼 있어야 넘친 부분이 돌아와 겹칠 자리가 없으니까요. 빈 간격을 잘게 하려는 게 아니라, 한 바퀴로 이어 붙인 칸에서 끝이 처음과 겹치지 않게 하려는 거였네요.

김민준 M03
김민준

그럼 칸 수를 2의 거듭제곱으로 조정하고 싶을 땐 어떡해?

이서연 S01
이서연

2L − 1보다 큰 2의 거듭제곱까지 제로 패딩하면 돼. 8칸으로 해도 [1, 3, 5, 7, 4, 0, 0, 0]이었어.

김민준 M11
김민준

칸 4개를 한 바퀴로 잇는 건, 자리가 네 개뿐인 원형 식탁에 다섯 명이 앉아 마지막 사람이 첫 사람 자리에 끼어 앉는 것과 비슷하네요. 의자를 2L − 1개만큼 넉넉히 놓아야 해요.