더북(TheBook)

그림 10-10은 8개의 데이터에 대하여 모든 단계에서 버터플라이 방법을 적용하였을 때의 데이터의 흐름을 보여준다. 입력 데이터의 순서가 좀 더 복잡하게 섞여 있는 것을 볼 수 있다. 그림 10-10에서는 데이터의 흐름이 왼쪽에서 오른쪽으로 진행될 때, 처음 2개의 데이터를 서로 버터플라이 방법에 의하여 곱하고, 다음에는 4개의 데이터를, 마지막에 전체 8개의 데이터를 서로 교차하여 곱해주는 것을 확인할 수 있다.

그림 10-10 버터플라이 방법에 의한 FFT 전체 계산 과정

그림 10-11은 8개의 데이터에 대하여 입력 데이터의 순서를 변경하는 방법의 예를 보여준다. 처음 8개의 데이터가 존재할 경우, 홀수 번째와 짝수 번째 데이터를 서로 분리하여 작성하면 두 번째 줄처럼 나뉘게 된다. 이 데이터들을 다시 홀수 번째와 짝수 번째의 순서대로 나누면 세 번째 줄처럼 나뉘어진다. 이처럼 맨 마지막에 두 개의 데이터로 분할될 때까지 데이터를 나누어주어야 한다.

그림 10-11 FFT 구현을 위한 입력 데이터의 순서 변환
신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.