FFT using MATLAB 3조 개미핥기 2006440062 박창원 2006440095 유현우.

Presentation on theme: "FFT using MATLAB 3조 개미핥기 2006440062 박창원 2006440095 유현우."— Presentation transcript:

1 FFT using MATLAB 3조 개미핥기 박창원 유현우

2 -Nyquist-Shannon sampling theory -Fourier series -Fourier Transform
목차 -Nyquist-Shannon sampling theory -Fourier series -Fourier Transform -DTFT & DFT -FFT -각 이론들의 관계 -FFT Code

3 Nyquist-Shannon sampling theory
신호의 기본성질을 보존하면서 부하를 줄일 수 있는 최적화된 Sampling 주파수를 결정하는 이론(Shannon의 정리)이 있다. Nyquist Sampling Criterion 이라고 불리는 내용은 Sampling시 aliasing 현상을 막는 Sampling 속도는 측정하고자 하는 신호원의 최고 주파수의 2배 이상이 되도록 해야 한다. 그러나 보통 안정성으로 고려하여 2배 이상인 5~10배 정도로 크게 잡는 경우가 많다. <적합하게 Sampling 한 경우(위)와 Sampling주파수가 작아 Aliasing이 생긴 경우(아래)> *Sampling 주파수를 아무리 크게 해서 원신호로 복원해도 원신호와 완전하게 똑같지는 않으며 미세한 오류가 있다.

4 Fourier series 푸리에시리즈의 기본은 모든 신호는 sin과 cos의 합 또는 복소지수의 합으로 나타낼 수 있다는 것부터 시작이다. 여기서 복소지수는 오일러 공식에 의하면 sin과 cos으로 표현할 수 있으므로 결국 저 둘은 같은 뜻이라 할 수 있다.

5 Fourier series 푸리에시리즈의 식은 다음과 같다. 가중치 여기서 가중치인 Cn은 x(t)를 구할 때 단순히 주파수만 다른 신호들을 더한다고 해서 일정한 신호가 나오는 것은 아니기 때문에 그 신호 앞에 계수인 이 Cn을 넣어줌으로서 sin, cos의 크기를 정해주는 일종의 가중치인 것이다.

6 Fourier Series Example

7 Fourier Series Example

8 Fourier Transform 푸리에변환의 시작은 비주기인 신호를 무한의 주기신호로 보는 것부터 이다. 즉 말하자면 푸리에시리즈에서 주기신호를 분석하는데 반해서 푸리에변환에서는 비주기 신호에 대한 분석도 하겠다는 것이다.

9 Fourier Transform 푸리에시리즈(주기신호)에서 가중치는 이다. Cn을 으로 변환한다. 그리고 주기 T를 무한대로 증가시키면 선스펙트럼의 주파수 가 연속변수 f로 표현된다. 따라서 이 식을 주파수 도메인인 으로 표현할 수 있다.

10 Fourier Transform 그리고 주기가 무한대임에 따라서 그 역수인 주파수가 감소함에 따라서 그 길이를 df로 나타낼 수 있다. 그리고 푸리에 급수의 식을 이용해서 시간 영역에 대한 신호의 정의를 할 수 있다. 가 되고 결국 가 된다.

11 Fourier Transform Example
(a)의 함수를 Fourier Transform 하여라 f(t)의 식은 다음과 같다.

12 Fourier Transform Example
f(t)를 Fourier Transform 하면 위와 같이 Sinc 함수가 나오고 그것을 그림 (b)에서 표현하였다.

13 DTFT & DFT (1) 시간영역의 표본화 (DTFT)
그리고 이 표본화의 식은 다음과 같다. (임펄스 표본화)

14 DTFT & DFT (1) 시간영역의 표본화 (DTFT) 그리고 이 표본화 식을 Fourier Transform
이렇게 해서 나온 식은 시간영역에서는 표본화로 인해 discrete 하고 주파수영역에서는 주기 를 가지는 continuous 한 신호가 나오게 되는데 이런 변환을 DTFT라고 한다. 한편 푸리에 변환의 곱셈/컨볼루션 성질에 의해서 다음과 같은 식이 성립함을 알 수 있다. 위 식을 통해서도 푸리에 변환 X(f)가 주기 마다 반복되는 주기함수가 된다는 것을 알 수 있었다.

15 DTFT Example 아래의 비주기 펄스열의 DTFT를 구하라. x(n)이 비주기 함수이므로 로 표현할 수 있다.

16 DTFT & DFT (2) 주파수 영역의 표본화 시간영역을 표본화하여 얻은 신호를 푸리에 변환을 통해서 얻은 위의 식은 식에서 보는 바와 같이 연속적인 값이다. 따라서 컴퓨터에서 이 식을 처리하기 위해서는 다시 표본화를 하여야 한다. 그래서 이번에는 y(t)의 푸리에 변환쌍 Y(f)를 주파수상에서 표본화와 푸리에 역변환을 하기로 하였다. 나머지 과정은 위에서 한 방법에 푸리에 역변환을 한점을 빼고는 동일하다. 이번에는 이 푸리에 변환쌍이 To마다 반복되는 주기함수가 된다는 것을 알 수 있다.

17 DTFT & DFT (3) 시간 및 주파수 영역 표본화
위에서 신호를 디지털 시스템으로 표현하기 위하여 앞선 단계에서 시간영역에서의 표본화와 주파수영역에서의 주기화, 그리고 주파수영역에서의 표본화와 시간영역에서의 주기화를 하였다. 다음 단계로 시간영역에서 표본화와 주기화를 동시에 하여 얻은 신호의 퓨리에 변환을 하기로 하였다. 이 변환을 하기 위해서 앞에서 썼던 조건을 그대로 썼다. 표본화와 주기화를 동시에 한 값은 다음과 같다. 그리고 앞에서 썼던 조건을 이용해서 푸리에 변환을 한 값은 다음과 같다. 결과적으로 x(t)에서의 표본화와 주기화를 한것의 푸리에 변환은 그 값이 주파수상에서 표본화하고 주기화한 스펙트럼으로서 얻어진다는 것을 알 수 있다.

18 DTFT & DFT (4) 이산 푸리에 변환 이제 본격적으로 이산 신호처리를 하기 위해서 앞서 신호의 주기 To가 표본화 간격 Ts의 정수배(N배)가 되도록 설정해야 한다. 그리고 시간과 주파수의 한 주기에는 모두 N개의 표본만 구성되도록 표본화 간격을 설정하여야 한다. (1)에서 했던 시간영역에서의 표본화와 그 값의 푸리에 변환을 하였던 것을 이용하고 위에서 설정하였던 N개의 표본을 구성하도록 식을 세우면 다음과 같다. 이로서 이 식을 통해서 시간영역과 주파수영역 모두에서 discrete한 신호를 얻을 수 있다. 를 위와 같이 정의하여서 이를 DFT(Discrete Fourier Transform)라고 부른다.

19 DTFT & DFT (4) 이산 푸리에 변환 그리고 이 식에서 퓨리에 역변환을 위해서 양변에 을 곱하고 k=0,1, .. , N-1 에 대한 합을 구한다. 따라서 이 식은 이 되고 이 식을 정리해서 이 되고 이를 이산 푸리에 역변환이라 한다.

20 x(n+N) = x(n), X(k+N) = X(k)
DTFT & DFT (5) DFT의 특성 <1>주기성(periodicity) x(n+N) = x(n), X(k+N) = X(k) 즉 x(n) , X(k) 모두 주기함수 <2>선형성(linearity)

21 DTFT & DFT (5) DFT의 특성 <3> 수열의 순환 이동
DFT of x[n] (finite duration sequence) 길이가 N이하인 유한길이 신호 x[n]의 DTF는 다음과 같은 주기 신호의 DFT와 동일 만일 을 k만큼 이동시키면 여기에 해당하는 유한 길이 신호 은 그리고 이 표기를 다음과 같이 한다.

22 DTFT & DFT (5) DFT의 특성 <4> DFT의 대칭 특성

23 DTFT & DFT (5) DFT의 특성 <5> 실수 신호와 DFT x[n]이 실수이면, 다음 관계 성립
<증명>

24 DTFT & DFT (5) DFT의 특성 <6> x[n]이 실수이고 우함수인 경우:
만일 위와 유사한 방법으로 이다. 즉 X(k)는 순허수이다.

25 아래의 비주기 펄스열 x(n)의 DFT를 구하여라.
DFT Example 아래의 비주기 펄스열 x(n)의 DFT를 구하여라. n을 4라고 지정하고 DFT를 수행하였다. 이 되고 오일러 공식에 의하면 따라서 위의 식을 전개하면 가 나오고 위의 X(k)의 그래프가 나오게 된다.

26 FFT 정의 고속 푸리에 변환(高速 푸리에 變換, Fast Fourier transform, FFT)은 이산 푸리에 변환(Discrete Fourier transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘이다. FFT는 디지털 신호 처리에서 편미분 방정식의 근을 구하는 알고리즘에 이르기까지 많은 분야에서 사용한다. x0,...,xn − 1이 복소수라고 가정할 때, DFT는 다음과 같이 정의한다.

27 FFT (2) 설명 예) N이 8인 경우에 주기성 N이 8이면 n은 0~7까지 8개이며, k는 0~7까지라고 하였다.

28 FFT 예) N이 8인 경우에 주기성 n과 k의 값을 조건으로 하면 이를 통해서 다음과 같은 사실을 알 수 있다.
• x[n]을 각각 N/2 샘플인 두 개의 신호로 분리한 후에 전개

29 FFT (3) 전통적인 분해 방법 N/2 샘플로 나누기 위해서 짝수번째 신호와 홀수번째 신호로 나누었으며 각각의 n값을 2r, 2r+1로 두었다.

30 FFT (3) 전통적인 분해 방법 이렇게 G[k]와 H[k]의 전개로 나눌 수 있다. 이를 이용해서 만약 N=8이면
2점 푸리에 변환이 이루어질 때까지 나누고 를 이용해서 최종적으로 2점 까지 나눈 G[k], H[k]의 값을 구할 수 있어서 DFT의 수행을 더 빠르게 할 수 있다.

31 FFT (4) FFT 알고리즘 <1> 쿨리-튜키 알고리즘(Cooley-Tukey algorithm)
가장 일반적으로 사용되는 FFT 알고리즘은 쿨리-튜키 알고리즘(Cooley-Tukey algorithm)이다. 이 알고리즘은 분할 정복 알고리즘을 사용하며, 재귀적으로 n 크기의 DFT를 n = n1 n2가 성립하는 n1, n2 크기의 두 DFT로 나눈 뒤 그 결과를 O(n) 시간에 합치는 것이다. 이 방법은 1965년에 J. W. 쿨리와 J. W. 튜키가 발표하여 널리 알려졌지만, 나중에 카를 프리드리히 가우스가 1805년에 같은 방법을 이미 개발하였으며, 그 뒤에도 제한된 형태의 FFT가 종종 발견되었음이 밝혀졌다. 쿨리-튜키 알고리즘은 보통 크기 n을 재귀적으로 2등분하여 분할 정복을 적용하기 때문에 n = 2k인 경우에 많이 적용된다. 하지만 일반적으로 n1과 n2는 같을 필요가 없으며, 따라서 n이 임의의 합성수일 때에도 적용 가능하다. 쿨리-튜키 알고리즘은 DFT를 더 작은 크기의 DFT로 나누기 때문에, 뒤에 설명된 다른 FFT 알고리즘과 함께 사용될 수 있다.

32 FFT (4) FFT 알고리즘 <1> 쿨리-튜키 알고리즘(Cooley-Tukey algorithm)
원리에 대한 설명은 다음과 같다. 정의에서 W = e − 2π / N라고 하고 다시 정리하면, 예를 들어 N = 4일 때, 이 식을 행렬을 지수의 짝홀을 기준으로 위의 식을 다음과 같이 변형할 수 있다.

33 FFT (4) FFT 알고리즘 <1> 쿨리-튜키 알고리즘(Cooley-Tukey algorithm)
이는 다음과 같이 다시 쓸 수 있으므로, N = 4인 DFT는 N = 2인 DFT 두 개를 사용해서 계산할 수 있다. 이 과정을 재귀적으로 적용하면 N = 2k인 DFT를 O(k, N에 의한) 시간 안에 할 수 있다. 이런 분할 과정을 그림으로 그리면 나비 모양의 그림이 나오기 때문에 나비 연산(Butterfly operation)이라고도 불린다.

34 FFT (4) FFT 알고리즘 <2> Prime Factor Algorithm (PFA)
prime-factor algorithm (PFA) 는 Good–Thomas algorithm (1958/1963)으로도 불린다. 이 알고리즘은 DFT에서 표현하였던 크기 N을 N1*N2 즉 DFT에서 차원을 두 개의 차원인 N1 N2로 표현하였는데 이는 오직 N1과 N2가 소인수일 때 쓰이는 알고리즘이다. <3> Bruun's FFT algorithm Bruun's FFT algorithm은 FFT에서 비정상인 재귀 다항식의 분해방식의 접근에 기초한 알고리즘이다. 이 연산이 마지막 단계까지 오직 real 계수만 포함하기 때문에 이것은 초기에는 real data의 DFT에 주로 많이 쓰였다. 그러나 이 알고리즘의 접근을 일반적인 쿨리-튜키 알고리즘을 기본으로 하여서 이 알고리즘은 real data의 사용에 성공적으로 정착하게 되었다.

35 FFT (4) FFT 알고리즘 <4> Rader's FFT algorithm
Rader's FFT algorithm은 주기적 컨볼루션을 이용하는 소인수 크기의 DFT에서 사용되는 알고리즘이다. <5> Bluestein's FFT algorithm Bluestein's FFT algorithm은 보통 chirp z-transform algorithm 이라 불린다. 이 알고리즘은 컨볼루션으로 표현되는 DFT가 임의의 크기를 가질 때 사용되는 알고리즘이다.

36 각 이론들의 관계 CTFT와 DTFT와의 관계 CTFT (Continuous Time Fourier Transform)
: 연속시간 푸리에 변환

37 각 이론들의 관계 CTFT와 DTFT와의 관계

38 각 이론들의 관계 (2) DFT와 Fourier Series와의 관계 주기 신호의 경우 다음과 같이 표현 가능

39 각 이론들의 관계 (3) DFT와 Fourier Transform와의 관계

40 FFT Code (1) example3 분석

41 FFT Code (1) example3 분석

42 FFT Code (1) example3 분석

43 FFT Code (2) example4 분석

44 FFT Code (2) example4 분석

45 FFT Code (2) example4 분석

46 FFT Code (2) example4 분석

47 FFT Code (3) Matlab 속의 FFT Matlab에서 FFT가 어떤 역할을 하는지 help fft를 실행해보았다.

48 FFT Code (3) Matlab 속의 FFT 답변을 보면 fft의 결과인 X(k)를 구하는 식으로
라고 나와 있는 것을 볼 수 있다. 이는 기존에 구했던 의 식 과는 다른 모습 을 보이는데 matlab의 식을 분석한 결과 exp함수에서 n과 k의 개수가 각각 (n-1), (k-1)을 취하고 있으므로 결국에는 표본의 개수가 기존의 식과 같이 N개가 되는 FFT를 표현한다는 것을 알 수 있었다.

49 FFT Code (3) Matlab 속의 FFT
그리고 code중에서 fft_mod라는 것이 있어서 이것도 help를 이용해서 알아보았다. 그 결과 이와 같은 설명을 얻을 수 있었다. 위의 설명을 통해서 zero padded된 x를 구할 때 위와 같은 명령어를 쓴다는 것을 알 수 있었다. 여기서 zero padded된 x란 x의 값 뒤에 0을 넣는 다는 뜻으로 이 값을 FFT하게 되면 zero padded이전의 신호보다 좀더 oversample된 신호를 얻을 수 있다. 이런 방법을 사용하는 이유는 fft를 실행하면서 신호의 주기를 정확히 맞추지 못할 때가 사용하기 위해서이다.

50 <참고 자료> 귀족고양이님 네이버블로그(그림) -Nyquist이론
< Fourier Series 그래프 참고 < DFT의 특성 참고 DTFT, DFT 문제 참고 < FFT 이론 참고 < FFT 알고리즘 참고 < Matlab의 FFT 참고 < <