무한서고

푸리에 오디세이(Fourier Odyssey): 푸리에 변환 for 컴퓨터(Fourier Transform for computer)

0) 서론

저번 포스팅까지 해서 우리는 '푸리에 ~~~'의 모든 개념과 도구 그리고 표현들에 대해서 알아보았습니다.

사실상 저번 포스팅까지가 이 푸리에 오디세이의 클라이맥스, 즉 가장 높은 산을 등정하여 그 정상까지 올라온 것이라고 할 수 있겠죠!

이제는 이 정상이 어떻게 생겼는지도 한번 살펴보고, 이 정상에서만 볼 수 있는 경치를 음미하며 살살 하산하면 이제 이 대장정은 끝을 맞이합니다.

오늘은 이 정상 즉 '푸리에 변환'이 컴퓨터에서 어떻게 활용되는지 한 번 살펴보도록 하겠습니다.

1) 컴퓨터에서의 푸리에 변환

사실상 개념적으로만 봐도, 이 푸리에 변환이라는건 정말 현대사회에서 없으면 안될 이론 같아 보이죠?

모든 신호 처리의 근간이 되니까요.

그러나 우리가 지금까지 경험해 왔듯이 이 수식은 계산이 극악으로 복잡하다는 최악의 단점이 있습니다.

특히나 비주기 함수까지 '완벽하게' 분석을 하려면,  '적분', '연속', '무한'의 개념이 필수적으로 필요하죠.

그러나 이 신호처리에서 컴퓨터라는 엄청난 계산장치를 사용하지 않고 사람이 매번 계산을 한다던가 하는건 정말 매우 비효율적이죠.

더군다나 실시간 처리는 완전히 요원할 것입니다.

근데 컴퓨터는 '적분', '연속', '무한'이 세 가지를 정말 제일 못합니다.

따라서 컴퓨터에게 이 푸리에 변환을 맡기지 못하느냐... 하면, '네 푸리에 변환의 원래 식 자체는 절대 못맡깁니다'가 답입니다.

그러나 하늘이 무너져도 솟아날 구멍은 있다고, 컴퓨터는 대신에 '단순', '반복' 작업을 세상에서 제일 잘합니다.

그리고 이런 컴퓨터를 위해 등장한 것이 바로 이산 푸리에 변환(Discrete Fourier Transform, DFT)와 고속 푸리에 변환(Fast Fourier Transform, FFT)이며, 이것이 오늘날 모든 디지털 신호 처리의 심장 역할을 하게 됩니다.

각 개념을 간단하게 말하자면 컴퓨터는 '연속'이 아니라 연속처럼 보이는 '이산'값(샘플링&양자화라고도 하죠)만을 취급할 수 있기 때문에 나온 것이 이산 푸리에 변환(Discrete Fourier Transform), 그리고 계산이 너무 복잡하기 때문에 알고리즘상 속도를 개선시켜 나온게 고속 푸리에 변환(Fast Fourier Transform) 입니다.

그리고 여기서 재밌게도 똑같은 '푸리에 변환'이라는 타이틀을 달고 있지만, 컴퓨터에게 시키는 작업은 엄밀히는 '푸리에 급수'로 근사하는 작업입니다.

왜냐면 컴퓨터는 '연속'을 처리하지 못하고 '이산'적이기 때문이죠.

다시 한 번 정리하죠.

• 우리는 컴퓨터라는 엄청난 계산 장치를 활용하면 푸리에 변환을 훨씬 빠르고 정확하게 사용하여 실생활에 많은 도움을 줄 수 있다는걸 알고있습니다.
  
  
• 그러나 컴퓨터는 '적분', '무한', '연속'이라는 개념이 들어간, 수학적으로 완벽한 '참 값'을 주는 푸리에 변환(적분)을 그 자체로는 절대로 처리하지 못합니다.
  
  
• 그래서 어떻게 하면 컴퓨터에게 이 푸리에 변환을 시킬 수 있을까 고민했습니다.
  
  
• 일단 연속이 불가능 하기때문에(실제로 컴퓨터는 연속 데이터를 처리하지 못합니다) 샘플링으로 이 값을 이산화 된 값으로 바꿉니다.(여기서 나이퀴스트-샤넌 샘플링 정리(Nyquist–Shannon Sampling Theorem)이란 것이 있는데, 간단히 말해 최대 주파수의 두 배 속도로 샘플링을 하면 원래 신호를 완벽하게 샘플링(추출)할 수 있다는 정리입니다.)
  
  
• 그리고 샘플링을 하려면, '구간'이 필요하기 때문에 신호를 특정한 구간(window)으로 자릅니다.
  
  
• 이 구간 안에서 이산화된 값을 푸리에 급수로 계산하여 '근사값'을 얻습니다.(연속은 푸리에 적분, 이산은 푸리에 급수였죠?)

그래서 실제적으로 컴퓨터는 '푸리에 급수'만 쓰는 격입니다.

2) 컴퓨터에서의 푸리에 변환의 문제점 - 구간(Window) 설정의 문제점

위에서 이산푸리에 변환과 고속푸리에변환 모두 우리가 잘라낸 유한한 구간(Window)의 데이터가 영원히 주기적으로 반복된다고 '강제로 가정'하고 계산합니다.

그리고 여기서 이 구간이 짧으면 ‘언제’ 시작되었는진 정확하게 알아도 ‘어떤 주파수'가 들어있는지는 불명확해지고, 반대로 이 구간이 길면 ‘시간'이 불명확해져도 ‘어떤 주파수'가 들어있는지가 명확해지죠.

푸리에 변환판 불확정성 원리(Gabor-Heisenberg 불확정성 원리)라고 볼 수 있겠네요.(시간 분해능 vs 주파수분해능)
(시간 영역에서의 정밀도($\Delta t$)와 주파수 영역에서의 정밀도($\Delta f$)의 곱은 특정 상수($\frac{1}{4\pi}$)보다 항상 크거나 같다는 것이 수학적으로 증명되어 있습니다. $\Delta t \cdot \Delta f \geq \frac{1}{4\pi}$)

참고로 이 구간(window)는 전적으로 분석 목적에 따라 달라집니다.

• 리듬/타악기 분석: '언제' 쳤는지가 중요하므로 짧은 구간을 씁니다.
• 화성/선율 분석: '무슨 음'인지가 중요하므로 긴 구간을 씁니다.
• 음성 분석: 말은 '시간'에 따라 빠르게 변하지만 '음높이'도 구별해야 하므로, 그 중간의 적절한 값 (보통 20~30ms)을 경험적으로 사용합니다.

3) 컴퓨터에서의 푸리에 변환의 문제점 - 급수에서 적분으로 확장시에 발생했던 문제점들

과거 '푸리에 적분' 포스팅에서 왜 급수에서 적분으로 개념을 확장해야 하는지 세가지 문제점을 말씀드렸는데 기억나시나요?

• 1) 내가 정한 L값에 따라 주파수 성분이 멋대로 바뀌고(기본주파수는 L과 관련이있죠?)
• 2) 억지로 자른 경계면(대표적으로 x=0)의 불연속 문제(Gibbs phenomenon:불연속점이 있는 함수를 푸리에 급수로 근사할 때, 불연속점 주변에서 오버슈팅(overshooting)이 발생하는 현상) 때문에 있지도 않던 '유령' 주파수들이 잔뜩 튀어나옵니다
• 3) 더불어 단 한번만 있는 신호였는데도 2L주기를 가지고 무한히 반복하는 신호처럼 호도하기까지하죠.

이렇게 세 가지 큰 문제점 때문에 푸리에 급수에서 푸리에 적분으로 개념 확장이 필수적이었죠.

근데, 지금은 또 반대로 푸리에 적분(변환)에서 푸리에 급수와 유사한 이산적인 도구로 근사를 하고 있습니다.

따라서 저 세가지 문제가 따라올 수밖에 없겠죠?

그러면 이 문제들은 어떻게 해결할 수 있을까요?

물론, '근원적인 해결'은 불가능합니다. 애초에 저 문제들을 해결하려고 적분으로 확장한건데, 그걸 다시 급수와 유사한 이산적인 도구를 사용하는 상황에서 무조건 이 문제들은 발생할 수밖에 없죠.

그래서 공학적으로 여러가지 트릭을 써서 이 문제들을 '완벽히 제거'한 것은 아니지만, '충분히 무시할 수 있을 만큼 잘 관리하고 완화하는' 방식으로 해결하고 있습니다.

1] 내가 정한 L값에 따라 주파수 성분이 멋대로 바뀐다

원인: '유한한 길이($L$)'로 신호를 잘라내는 행위, 즉 '창(Windowing)'을 씌우는 행위 때문에 발생합니다.

해결: 영 채우기(Zero padding)

아까 위에서 구간(window)를 짧게 정의하면 시간 해상도가 올라가고, 길게 정의하면 주파수 해상도가 올라간다고 말씀드렸죠?

그리고 주파수 해상도가 높을수록 이 합성 신호에 들어있는 주파수들을 잘 분해할 수 있겠죠?

그래서 일정 길이 이상의 구간을 설정해주면 주파수 성분이 멋대로 바뀌는 것을 방지할 수 있습니다.

그런데 이 신호가 매우 짧은 신호라 구간을 길게 설정할 수 없으면 어떻게 될까요? 혹은 짧은 구간을 보고 싶은데 주파수 해상도는 높았으면 하는 경우에는요?

바로 이때 사용하는 방법이 영 채우기(Zero padding)입니다.

1초 짜리 신호를 분석하고 싶은데 이렇게 구간을 설정할 경우 주파수 해상도가 낮아지면, 이 1초짜리 신호 뒤에 9초 분량의 0 데이터를 덧붙여 총 10초짜리 신호를 만듭니다. 

DFT/FFT의 주파수 해상도( $\Delta f$ )는 총 샘플링 시간 ( $T = N \cdot \Delta t$ )에 반비례합니다. ( $\Delta f = 1/T$ )

신호 뒤에 0을 덧붙여 $T$를 10배로 늘리면, 주파수 해상도가 10배 더 조밀해집니다.

이것이 새로운 주파수 정보를 '창조'하는 것은 아니지만, 기존에 듬성듬성 보였던 주파수 스펙트럼을 훨씬 더 촘촘하게 보간(interpolation)하여 진짜 피크(peak) 주파수가 어디인지 더 정확하게 찾아낼 수 있게 해줍니다.

따라서 1번 문제도 어느정도 해결이 되었습니다.

2] 경계면 불연속과 '유령' 주파수 (Gibbs/Spectral Leakage)

원인:

억지로 자른 경계면의 불연속 문제 (Gibbs) 때문에 있지도 않던 '유령' 주파수들이 잔뜩 튀어나온다.

이것이 가장 심각한 문제일 수 있으며, 전문 용어로 '스펙트럼 누설(Spectral Leakage)'이라고 부릅니다.

신호를 단순히 네모난 칼(Rectangular Window)로 뚝 잘라내는 순간, 신호의 시작과 끝에 매우 급격한 '점프'(불연속점)가 생깁니다. 푸리에 해석의 관점에서 "급격한 변화 = 수많은 고주파 성분의 합"입니다.

따라서 DFT는 "아! 이 신호를 만들려면 원래 신호의 주파수뿐만 아니라, 이 '급격한 점프'를 만들기 위한 온갖 종류의 (있지도 않던) 고주파 성분들이 필요하구나!"라고 판단하여 '유령' 주파수를 스펙트럼 전체에 뿌려버립니다.

해결: 테이퍼링 윈도우 (Tapering Window)

네모난 '직사각형 창(Rectangular Window)'이 문제의 원흉입니다.

작동 원리: 신호를 네모로 뚝 자르는 대신, 양 끝을 0으로 수렴하도록 부드럽게 눌러주는 다른 모양의 창(Window Function)을 원본 신호에 곱해줍니다.

종류: 해닝(Hanning), 해밍(Hamming), 블랙맨(Blackman) 창 등이 유명합니다.

효과: 신호의 양 끝이 부드럽게 0이 되므로, 강제로 잘라낸 경계면에서의 '불연속 점프'가 사라집니다.

결과: "급격한 변화"가 사라졌으므로, DFT가 만들어내던 "급격한 변화를 만들기 위한 가짜 고주파 성분들", 즉 '유령' 주파수(Spectral Leakage)가 획기적으로 줄어듭니다.

한계: 물론 윈도우 함수를 사용하면 스펙트럼의 '주 피크'가 약간 뭉툭해지는(해상도 저하) 단점이 있지만, 스펙트럼 전체가 '유령' 주파수로 오염되는 것보다 훨씬 나은 절충안입니다.

3] 강제 주기성

원인: 이 또한 '유한한 길이($L$)'로 신호를 잘라내는 행위, 즉 '창(Windowing)'을 씌우는 행위 때문에 발생합니다.

컴퓨터는 $N$개의 샘플 데이터(총 시간 $T$)만 볼 수 있으며, DFT는 이 $N$개의 샘플이 영원히 반복된다고 가정합니다.

해결: 영 채우기(Zero padding)

이 또한 영 채우기(Zero padding)으로 해결이 가능합니다.

작동 원리: 우리가 분석하려는 실제 신호(예: 1초짜리 "딱!" 소리)가 있다면, 그 뒤에 9초 분량의 '0' (완전한 침묵) 데이터를 덧붙여 총 10초짜리 신호로 만듭니다.

강제 주기성 완화 예시:

Before: "[딱!][딱!][딱!][딱!][딱!]" → 실제와 전혀 다른 신호

After: "[딱! ....(침묵 9초).... ][딱! ....(침묵 9초).... ]"

이렇게 하면 "딱!" 소리가 10초에 한 번씩 울리는 신호가 됩니다. 여전히 주기적이긴 하지만, 원래 신호인 '단발성 소리'와 훨씬 더 유사해졌습니다. 주기($L$)를 충분히 길게 늘려서 주기성으로 인한 왜곡(Aliasing)을 최소화하는 것입니다.

이 기법들은 완벽한 수학적 '해결'이라기보다는, 공학적인 '절충(Trade-off)'과 '최적화'에 가깝습니다.

4) 마무리

그 동안 등반하시느라 고생하셨을 여러분을 위해 오늘은 이 푸리에 변환이 컴퓨터에서 실제로 어떻게 작동되는지에 대해 개념적으로 간단하게 알아보는 시간을 가졌습니다.

의외로 재밌지 않나요?

푸리에 급수의 한계를 돌파하기 위해 수학적으로 푸리에 적분이라는 개념으로 확장시키고 이것이 결국 푸리에 변환이라는 개념을 창출하였는데,

이 엄청난 개념을 활용하기 위해서는 컴퓨터라는 계산기계의 활용이 필수적이 되었으나,

이 계산기계의 태생적 한계로 확장된 수학적 개념을 사용하지 못하고 다시 푸리에 급수와 같은 형태로 회귀하면서,

이 두 문제(정확성 vs 컴퓨터 이용 가능성)를 해결하기 위해 또 다른 방법론들이 도입되었다는 사실이요!

그리고 재밌게도 이 두 지점이 '수학'과 '공학'을 가르는 요소이지 않나 싶어요.

수학은 "어떻게 해서든 가장 '엄밀하고 정확한' 정보를 얻을 수 있느냐" 라면

공학은 "이 개념을 어떻게 현실과 잘 타협할 것이냐" 니까요!

약간의 쉬어가는 코너였습니다.

이제 이 기나긴 푸리에 오디세이도 슬슬 마지막 포스팅만 남았습니다.

푸리에라는 산 꼭대기 위에서만 볼 수 있는 절경이 남았다구요!

조금만 더 힘내보죠!