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

이산 푸리에 변환 (DFT) 디지털 신호를 주파수 영역에서 분석 고속 푸리에 변환 (FFT) 계산 속도가 빠르다.

이산 푸리에 급수와 이산 푸리에 변환의 차이 (3장 참조) 이산 푸리에 급수와 이산 푸리에 변환의 차이 (3장 참조) 이산 푸리에 급수 이산 푸리에 변환 1. 주기 신호에 응용 2. 스펙트럼 선의 고조파 형태 3. 스펙트럼 계수 ak 1. 비주기 신호에 응용 2. 선형 시불변 시스템에 적용 3. 에 대한 연속함수 - 유사하나 - 스펙트럼이 주기적 이유 : 신호가 샘플링 되었기 때문

7.2.1 이산 푸리에 변환의 원리 이산 푸리에 변환 * 식 3.1, 22 참조 (7.1) 역이산 푸리에 변환 * 식 3.2, 24 참조 (7.2)

- 이산 푸리에 변환과 역이산 푸리에 변환은 주기적으로 반복되는 신호 에서 한 주기로 제한된 신호를 선택 - 이산 푸리에 변환은 비주기적인 신호 x[n]을 계산 편의상 주기 신호로 생각 - 이산 푸리에 변환과 역이산 푸리에 변환의 차이점은 1/N의 유무와 지수 항에서의 부호에서의 부호 - 이산 푸리에 변환을 계산하는 알고리즘을 알고 있다면 시간 영역과 주 파수 영역간의 대칭 때문에 역이산 푸리에 변환은 쉽게 계산

식(7.1), 식(7.2)와 식(3.1), 식(3.2) 차이 - 유사 - 차이점 1. 1/N이 분석식이 아닌 합성식에 있음 2. ak 대신 X[k]로 나타남 식(7.1)은 두가지 기능을 갖는다. - x(n)이 주기적이면 이산 푸리에 급수 - x(n)이 비주기적이면 이산 푸리에 변환 - 주기가 N인 주기 신호와 길이가 N인 비주기 신호는 N개의 값으로 제한

X() 또는 H() : 연속 스펙트럼 함수 - 컴퓨터나 하드웨어에서는 연속함수를 처리할 수 없슴. - 에 대해 근사화된 이산 형태로 샘플링된 함수 - 적은 샘플 : 기대하지 않은 함수 - 과다 샘플 : 계산량 증가 - 샘플링 이론에 따른 적절한 샘플

샘플링 이론 “The continuous spectrum of a signal with limited duration To seconds may be completely represented by regularly-spaced frequency-domain samples, provided the samples are spaced not more 1/ To Hz apart.” 샘플링 간격:T, 한 주기:To초, 샘플 수:N개 - 시간 영역 표현 : To = NT - 주파수 영역 표현 : f = 1/ To = 1/NT Hz 또 2/NT 라디안/초

 주파수 간격 :  = T = 2 f T = 2 / N  샘플수 : 2 / ( 2 / N ) = N개 (한주기는 2)  X[k] : 주파수 영역에서 푸리에 변환 X()의 샘플값  자유도 : 2N개 (신호가 복소수인 경우) N개 (신호가 실수인 경우)  절반의 스펙트럼 계수로 전체 스펙트럼을 표시함 - 이유 : 스펙트럼의 대칭성 때문

이산 푸리에 변환, 푸리에 변환과 이산 푸리에 급수 사이의 관계

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

코사인 함수: 우함수, 사인 함수 : 기함수 만약 x[n]이 실수이면 X[k]의 실수부: 우함수 X[k]의 허수부: 기함수 대칭성 : 절반의 계수로 표현 x[n]이 복소수이면, 대칭성이 존재 않음 - 이산 푸리에 변환 정의시 모든 계수 필요

x[n]이 실수이고 우함수이면 (x[n]=x[-n]) => 스펙트럼은 허수부가 모두 0인 코사인항만 존재 x[n]이 실수이고 기함수이면 => 스펙트럼은 실수부가 모두 0인 사인항만 존재

7.2.3 이산 푸리에 변환 계산 계산 속도 : 알고리즘과 프로그램을 작성할 때뿐만 아니라 하드웨어에 의해서도 정해지므로 매우 복잡한 문제 곱셈 : - 많은 계산시간 소모 - 특별한 목적의 디지털 신호처리 하드웨어 설계 필요 식(7.1), (7.2) : 수행속도가 느리다.

신호 x[n]이 실수인 경우 이산 푸리에 변환 역 이산 푸리에 변환 차이 : 1/N과 지수항의 부호 => 식(7.10)만 다룬다.

진폭과 위상 실수부: 허수부:

신호 x[n]이 복소수인 경우 실수부 : 허수부 :

곱셈이 존재하기 때문 계산 속도 느림 식(7.17), 식(7.18) => 각각 4N2 만큼의 실수 곱셈 계산 필요 식(7.12), 식(7.13) => 각각 2N2 만큼의 실수 곱셈 계산 필요 계산시간 : N2 에 비례 (예) 2048개 또는 4096개 샘플 경우 : 수 분

해결점 : 이산 푸리에 변환과 역이산 푸리에 변환의 주기성으로 인한 => k와 n이 변함에 따라 같은 값의 곱셈이 반복 계산 대책 1. 고속 푸리에 변환 알고리즘 탄생 2. 코사인과 사인값을 메모리에 저장하였다 이용 예 : 64개 샘플 경우 cos(2kn/64) k, n이 0부터 63까지 sin(2kn/64) 변하기 때문. 먼저 한번 계산하고 표에 저장. - 표를 사용하는 경우는 사용하지 않는 것에 비해 50% 계산 절약.

표를 이용하여 구한 이산 퓨리에 변환 (그림 3.3과 비교) 표를 이용하여 구한 이산 퓨리에 변환 (그림 3.3과 비교)

이산 푸리에 변환을 빠르게 하는 다양한 연구 방법 이산 푸리에 변환을 빠르게 하는 다양한 연구 방법 - x[n]의 값의 일부분을 영으로 바꿈 - x[n]의 일부 값을 계산에서 제외 - Goertzel 알고리즘 : 이산 푸리에 변환을 WNkn의 주기로 나타낸 순환 디지털 필터의 출력. - Radar 알고리즘 : 순환 이산 푸리에 변환 방식 - Chirp z 변환방법 : 주파수 변조 함수를 신호에 곱하는 방법

7.3 고속 푸리에 변환 (FFT) WNkn : 주기함수, 같은 계산 값이 반복 WN = exp(-j2/N) - 시간 소비를 줄인다기 보다는 여러 기능과 장점 그리고 제약을 가지는 알 고리즘들의 결합

N = 8인 경우 WNkn의 주기성 - k, n이 각각 0에서 7까지 변환 - 총 64개 - 4개의 고정값

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