‘고속푸리에변환’ 역 알고리즘 찾아
디지털 혁명을 가능하게 한 핵심 알고리즘

[데일리비즈온 심재율 기자] 고속푸리에변환(FFT Fast Fourier Transform)이라고 불리는 것이 있다. 함수의 근삿값을 계산하는 알고리즘으로, 간단한 계산으로 영상 또는 아날로그 신호의 변환을 계산하기 위한 알고리즘이다.

이렇게 말하면 복잡하지만, FFT는 우리가 생각하는 것보다 훨씬 많이 사용되는 신호 처리 알고리즘이다.

미국 아이오와주립대학의 알렉산더 스토이체프 (Alexander Stoytchev) 부교수는 고속푸리에변환(FFT) 알고리즘이나 그 반대인 역고속푸리에변환(IFFT)이 신호처리의 핵심이라고 말할 정도다.

실생활에서 고속푸리에변환이나 역고속푸리에변환은 음악을 스트리밍하거나, 휴대폰 신호를 생성할 때, 인터넷을 검색하거나, 셀카를 찍을 때 항상 사용될 만큼 절대적으로 중요하다.

블라디미르 수호이(왼쪽)와 알렉산더 스토이체프 부교수 (사진=Paul Easker)
블라디미르 수호이(왼쪽)와 알렉산더 스토이체프 부교수 (사진=Paul Easker)

그래서 고속푸리에변환은 디지털 혁명을 가능하게 했다는 평가를 받는다.

FFT 알고리즘은 1965년에 발표됐다. 4년 후, 연구원들은 ‘처프Z변환’(CZT chirp z-transform)이라고 불리는 보다 용도가 많고 일반화된 버전을 개발했다. 그러나 이와 유사한 IFFT 알고리즘의 일반화는 50년 동안 해결되지 않았다.

최근 미국 아이오와 주립대학의 스토이체프 부교수와 박사과정 학생인 블라디미르 수호이(Vladimir Sukhoy)는 '역 처프Z변환'(ICZT inverse chirp z-transform)이라고 불리는 알고리즘을 발견함으로써 50년간 풀리지 않았던 신호처리의 퍼즐이 마침내 해결됐다.

스토이체프와 수호이는 네이처 리서치 저널인 사이언티픽 리포트(Scientific Reports) 저널 온라인 최신호에 이에 대한 논문을 게재했다.

모든 알고리즘과 마찬가지로 단계적인 과정을 거쳐 문제를 해결해야 한다. 이 경우 CZT 알고리즘의 출력을 다시 입력에서 찾아야 한다.

이 두 알고리즘은 프리즘과 약간 비슷하다. 첫 번째는 백색 빛의 파장을 여러 색깔의 스펙트럼으로 분리하고, 두 번째는 여러 색 스펙트럼을 다시 백색 빛으로 결합한다고 스토이체프는 설명했다.

스토이체프 교수는 자신의 ‘컴퓨터 인식’ 강좌에서 대학원생들이 고속 푸리에 변형을 이해할 수 있도록 돕기 위해 유사성을 찾다가 누락된 알고리즘 공식을 찾아야 한다는 생각을 갖게 됐다.

그는 신호 처리 관련 논문을 많이 읽었지만, 역처프Z변환에 대한 논문은 아무것도 찾을 수 없었다.

스토이체프는 "설명할 수 없었기 때문일까, 아니면 존재하지 않기 때문일까 궁금해졌다. 알고 보니 존재하지 않았던 것이다"고 말했다. 그래서 결국 직접 찾아 나선 것이다.

스토이체프틑 "역 알고리즘은 원래 알고리즘보다 더 어려운 문제여서 우리는 그것을 공격하기 위해 더 나은 정밀도와 더 강력한 컴퓨터가 필요했다"고 말했다. 그는 구조화된 행렬의 수학적 틀 안에서 알고리즘을 보는 것이 중요했다고 설명했다.

아이오와 주립대학 학생혁신센터의 제임스 올리버 (James Oliver) 소장은 "이 문제를 계속 공격하기 위해서는 용기가 필요했다"고 말했다. 올리버 소장은 스토이체프와 수호이가 3년간 이 연구를 추진할 수 있도록 필요한 연구 환경을 조성해줬다.

50년 동안 해결하지 못했던 수학적, 계산적 도전은 수년 동안 수고를 아끼지 않은 용기있는 연구원에 의해 풀렸다.

저작권자 © 데일리비즈온 무단전재 및 재배포 금지