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

서 론 1. 이산 푸리에 변환의 기초 이론 2. 푸리에의 여러 형태와의 관계 3. 이산 푸리에 변환의 구현시 계산상 문제 서 론 1. 이산 푸리에 변환의 기초 이론 2. 푸리에의 여러 형태와의 관계 3. 이산 푸리에 변환의 구현시 계산상 문제 4. 다양한 고속 푸리에 변환 알고리즘 이산 푸리에 변환 (DFT) 디지털 신호를 주파수 영역에서 분석 고속 푸리에 변환 (FFT) 계산 속도가 빠르다.

이산 푸리에 급수와 이산 푸리에 변환의 차이 이산 푸리에 급수 이산 푸리에 변환 1. 주기 신호에 응용 2. 스펙트럼 선의 고조파 형태 3. 스펙트럼 계수 ak 1. 비주기 신호에 응용 2. 선형 시불변 시스템에 적용 3. 에 대한 연속함수 이산 푸리에 변환은 비주기적인 신호 x[n]을 주기 신호로 고려 이산 푸리에 변환 이산 푸리에 역변환

이산 푸리에 변환, 푸리에 변환, 이산 푸리에 급수 한 주기 비주기 신호와 푸리에 변환 스펙트럼 주기 신호와 이산 푸리에 급수

이산 푸리에 변환의 특성 선형성 시간이동 컨벌루션 변조

이산 푸리에 변환의 특성 x[n]이 실수이면 X[k]의 실수부: 우함수 X[k]의 허수부: 기함수 대칭성 : 절반의 계수로 표현 x[n]이 복소수이면, 대칭성이 존재하지 않음 - 이산 푸리에 변환 정의시 모든 계수 필요 x[n]이 실수이고 우함수이면 (x[n]=x[-n]) => 스펙트럼은 허수부가 모두 0인 cosine 항만 존재 x[n]이 실수이고 기함수이면 => 스펙트럼은 실수부가 모두 0인 sine 항만 존재

이산 푸리에 변환 계산 계산 속도 : 알고리즘과 프로그램을 작성할 때뿐만 아니라 하드웨어에 의해서도 정해지므로 매우 복잡한 문제 곱셈 : 많은 계산시간 소모, 특별한 목적의 디지털 신호처리 하드웨어 설계 필요 수행속도가 느리다 이산 푸리에 변환 이산 푸리에 역변환 x[n]이 실수인 경우 진폭과 위상 실수부 : 허수부 : 각각 2N2 만큼의 실수 곱셈 계산 필요

이산 푸리에 변환 계산 x[n]이 복소수인 경우 (계산이 더욱 복잡해 짐) 실수부 : 허수부 : 각각 4N2 만큼의 실수 곱셈 계산 필요 곱셈이 존재하기 때문 계산 속도 느림 (계산시간 : N2 에 비례) (예) 2048개 또는 4096개 샘플 경우 : 수 분 해결점 : 이산 푸리에 변환과 역이산 푸리에 변환의 주기성으로 인한 => k와 n이 변함에 따라 같은 값의 곱셈이 반복 계산 대책 1. 고속 푸리에 변환 알고리즘 2. 코사인과 사인값을 메모리에 저장하였다 이용

고속 푸리에 변환 (FFT) WNkn : 주기함수, 같은 계산 값이 반복 WN = exp(-j2/N) N = 8인 경우 WNkn의 주기성 - k와 n이 각각 0에서 7 사이 - 총 64개 - 8개의 WNkn - 4개의 고정값

고속 푸리에 변환 접근 방법 1. 전통적인 분해 방법 - 데이터 N이 2의 승수 ( )인 경우 적용 - 시분할형(decimation-in-time) - x[n]을 각각 N/2 샘플인 두개의 신호로 분리 2. 인덱스 접근 방법 - 데이터 N의 개수가 임의의 수에 적용

전통적인 분해 방법 기수 2 (radix-2) 시분할형 FFT 알고리즘 N = 8인 경우 n = { 0, 1, 2, 3, 4, 5, 6, 7 } n = { 0, 2, 4, 6 } n = { 1, 3, 5, 7 } n = { 0, 4 } n = { 2, 6 } n = { 1, 5 } n = { 3, 7 } - 2점 푸리에 변환이 될 때까지 계속 분할

인덱스 접근 방법 - DFT의 길이를 N = N1N2 와 같이 두 수의 곱으로 표현 n = ( M1 n1 + M2 n2 ) N where n1 = 0, 1, 2 … (N1 - 1) n2 = 0, 1, 2 … (N2 - 1) M1 , M2 : 상수 N : modulo k = ( J1 k1 + J2 k2 ) N DFT의 시간축 인덱스 n1 과 n2 의 값이 특정 범위에서 변하면 n값은 범위에서 변한다 DFT의 주파수축 인덱스 예 : 4점 푸리에 변환을 2점 푸리에 변환으로 분할 N1 = N2 = 2 이면 N = N1 N2 = 4 M1 = 2, M2 = 1, J1 = 1, J2 = 2 이면 n = 2n1 + n2 n1, n2 = 0 또는 1 k = k1 + 2k2 k1, k2 = 0 또는 1 N = 4 일 때의 푸리에 변환식

인덱스 접근 방법 N = 4 일 때의 푸리에 변환 두개의 N/2점 이산 푸리에 변환 4점 변환방정식

신호 흐름도 (signal flow graph)

신호 흐름도 (signal flow graph) W40 = 1 = W20 ; W42 = W21 = -1 ; W43 = W42 W41 = W21 W41

고속 푸리에 변환 나비 (FFT butterfly) 한 개의 덧셈과 한 개의 뺄셈 나비와 회전요소가 결합

예제 7.1 8점, 기수 2인 시분할 고속 푸리에 변환은 0과 1인 6개의 독립 변수를 가진 인덱스 표로 정의 n = 4n1 + 2n2 + n3 및 k = k1 + 2k2 + 4k3 (7.41) (a) n과 k의 인덱스 표를 만들고, 출력이 원래 순서로 나올 때 순서가 바뀐 입력 순서를 표현 (b) 가중치가 W8 승수로 표현되는 고속 푸리에 변환의 신호 흐름도를 작성 (c) 2점 고속 푸리에 변환 나비와 회전 요소를 고려하여 신호 흐름도를 재구성하고 FFT의 경우 필요한 복소수 곱셈 계산의 수를 계산 풀이 (a) 원래 순서의 출력 순서가 바뀐 입력 순서

(b)

(c) - W84 = -1이므로 W86 = W84 W82 = (-1) W82 - -1이 기본 나비 안에 결합 - W82는 회전 요소

입력 및 출력 순서의 변환 입력 순서를 바꾸었으나, 만약 출력 순서를 바꾼다면 입력 순서를 바꾸지 않아도 된다

비트 반전

주파수 분할(decimation-in-frequency) FFT - 시분할과 반대 - 주파수 영역에서 시분할 방법에 대한 이원적(opposite or dual)쌍 - 입력값 대신 출력값이 분할 n = n1 + 2n2 , k = 2k1 + k2, X = X[n1, n2]

예제 7.2 주파수 분할 고속 푸리에 변환에서 8점, 기수 2, 조건을 갖는 인덱스 대응식은 n = n1 + 2n2 + 4n3 및 k = 4k1 + 2k2 + k3 FFT에 대한 신호의 흐름도를 그리고 W8의 승수로 모든 가지의 가중치를 나타내라. 기본적인 2점 FFT의 나비선도와 회전 요소를 이용해서 또 다른 형태의 신호 흐름도를 그려라. (데이터의 순서 바뀜은 출력에만 존재한다고 가정) 풀이

- W87 = W84 W83 = (-1) W83

- 16점 고속 푸리에 변환 경우 N = 16, N1 = N2 = 4  인덱스 대응식 : n = 4n1+ n2 및 k = k1+4k2  입력 순서 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15

DFT 특성