제07장 이산 푸리에 변환. 제07장 이산 푸리에 변환 푸리에 급수와 계수 에서의 이산주기신호 제07장 이산 푸리에 변환.

Presentation on theme: "제07장 이산 푸리에 변환. 제07장 이산 푸리에 변환 푸리에 급수와 계수 에서의 이산주기신호 제07장 이산 푸리에 변환."— Presentation transcript:

1

2 제07장 이산 푸리에 변환

3 푸리에 급수와 계수 에서의 이산주기신호 제07장 이산 푸리에 변환

4 앨리어스(aliased) 푸리에 급수 계수
지수부분의 표현 지수부분 표현과 의 정의를 사용하여 표현하면, 앨리어스(aliased) 푸리에 급수 계수 = 제07장 이산 푸리에 변환

5 앨리어스 푸리에 급수 계수를 이용한 이산 푸리에 급수
위 식에서 을 로 변수치환하고 의 정의를 사용하면, 이산 푸리에 급수 계수 제07장 이산 푸리에 변환

6 제07장 이산 푸리에 변환

7 과 같이 정의하면 이산 푸리에 급수 계수 제07장 이산 푸리에 변환

8 에 대한 정의를 이산 푸리에 급수에 대입 이산 푸리에 급수 일반적인 이산 푸리에 급수(DFS) 제07장 이산 푸리에 변환

9 제07장 이산 푸리에 변환

10 제07장 이산 푸리에 변환

11 제07장 이산 푸리에 변환

12 유한 이산 신호에 대한 정의 DTFT에서 일 때 DFT와 같아짐. 제07장 이산 푸리에 변환

13 제07장 이산 푸리에 변환

14 제07장 이산 푸리에 변환

15 제07장 이산 푸리에 변환

16 제07장 이산 푸리에 변환

17 제07장 이산 푸리에 변환

18 FT, DTFT, FS, DFS, DFT 의 관계 FT DTFT FS DFS DFT 제07장 이산 푸리에 변환

19 Fequency Sampling Theorem
If a sequece is time-limited(i.e., of finite duration) to [0, N-1], then the continuous spectrum of the sequence may be completely represented by N regularly-spaced frequeny-domain samples in [0, 2p), provided the samples are spaced not more than [rad] apart. frequency-domain sampling point ; w = 제07장 이산 푸리에 변환

20 무한 이산 신호 의 DTFT에서 표본값을 취하는 경우
주기 함수인 DTFT를 표본화 하여 이산 주기 함수인 DTF를 만든다. 제07장 이산 푸리에 변환

21 제07장 이산 푸리에 변환

22 제07장 이산 푸리에 변환

23 y[0]를 구하기 위하여 x1[n]의 원통에 x2[n] 의 원통을 업혀놓고 오버랩 되는 값들끼리 곱하여 더한다.
제07장 이산 푸리에 변환

24 을 구하기 위하여 업혀놓은 의 원통을 아래그림과 같이 시계 반대
을 구하기 위하여 업혀놓은 의 원통을 아래그림과 같이 시계 반대 방향으로 1만큼 이동시킨 후 오버랩 되는 값들끼리 곱하여 더한다. 제07장 이산 푸리에 변환

25 ; 선형 convolution 제07장 이산 푸리에 변환

26 입력 신호와 임펄스 응답이 각각 의 길이가 되도록 0을 삽입한 후 원형 컨볼루션을 수행
원형 컨볼루션에 의한 선형 컨볼루션의 수행 ; 입력 신호와 임펄스 응답이 각각 의 길이가 되도록 0을 삽입한 후 원형 컨볼루션을 수행 제07장 이산 푸리에 변환

27 제07장 이산 푸리에 변환

28 제07장 이산 푸리에 변환

29 Matlab n=[0:7]; x=[6 5 4 3 2 1]; h=[1 1 1]; y=conv(x,h) stem(n,y)
grid on y = 제07장 이산 푸리에 변환

30 제07장 이산 푸리에 변환

31 Matlab N=8 n=[0:7]; x=[6 5 4 3 2 1 0 0]; h=[1 1 1 0 0 0 0 0];
X=fft(x); H=fft(h); Y=X.*H; y=ifft(Y); y=real(y) stem(n,y) grid on y = 제07장 이산 푸리에 변환

32 제07장 이산 푸리에 변환

33 Matlab N=6 n=[0:5]; x=[6 5 4 3 2 1]; h=[1 1 1 0 0 0]; X=fft(x);
H=fft(h); Y=X.*H; y=ifft(Y); y=real(y) stem(n,y) grid on y = 제07장 이산 푸리에 변환

34 DFT를 사용하여 주파수 영역에서 선형 컨볼루션을 수행하는 방법
제07장 이산 푸리에 변환

35 BLOCK CONVOLUTION 제07장 이산 푸리에 변환

36 제07장 이산 푸리에 변환

37 제07장 이산 푸리에 변환

38 에러가 발생하도록 원형 컨볼루션을 수행하나, 에러가 생긴 부분을 버리고 저장하는 방식
제07장 이산 푸리에 변환

39 제07장 이산 푸리에 변환

40 Overlap-save method implementation
Nx ; the length of input sequence M ; the length of impulse response N ; block length M-1 ; the length of preappend zeros(or overlapped part) L=N-(M-1) ; the length of non-overlapped part K=floor((Nx+(M-1)-1)/L)+1 ; the total number of blocks where floor ; the truncation operation xk[n] ; the kth block input , yk[n] = xk[n] h[n] ; the kth block output y[n] ; the linear convolution output which is obtained discarding the first (M-1) smples from each yk[n] and concatenating the remaining samples 제07장 이산 푸리에 변환

41 h=[1 1 1 ]; %impulse response N=4; %block length
Matlab Overlap-Save method clear x=[ ]; %input h=[1 1 1 ]; %impulse response N=4; %block length Nx=length(x); %length of x M=length(h); %length of h M1=M-1; %overlapped length of a block L=N-M1; %nonoverlapped length of a block h=[h zeros(1,N-M)]; %length of h => N x=[zeros(1,M1), x, zeros(1,N-1)]; % preappend (M-1) zeros to x K=floor((Nx+M1-1)/L); %the number of blocks Y=zeros(K+1,N); 제07장 이산 푸리에 변환

42 % convoluton with succesive blocks for k=0:K
Matlab % convoluton with succesive blocks for k=0:K xk=x(k*L+1:k*L+N); %the kth block of input x %circular convolution Xk=fft(xk,N); H=fft(h,N); Yk=Xk .* H; yk=ifft(Yk); yk=real(yk); Y(k+1,:)=yk; end Y=Y(:,M:N)'; %discard the 1st (M-1) samples y=(Y(:))'; %concatenating for the final output y 제07장 이산 푸리에 변환

43 Matlab %plot y n=[0:length(y)-1]; stem(n,y) grid on y = 6 11 15 12
제07장 이산 푸리에 변환

44 DFT : X(k) = Wx[n] (column vector) or X(k) = x[n]W (row vector)
의 정의 ; where 행렬 표현 ; DFT : X(k) = Wx[n] (column vector) or X(k) = x[n]W (row vector) IDFT: X(k) = 1/N * W*x[n] (column vector) or X(k) = 1/N * x[n] W* (row vector) 제07장 이산 푸리에 변환

45 Matlab DFT 제07장 이산 푸리에 변환

46 Matlab IDFT 제07장 이산 푸리에 변환

47 Ex.) Sol.) 제07장 이산 푸리에 변환

48 %X=(1-exp(-j*4*w)) ./ (1-exp(-j*w));
Matlab %% --DTFT-- x=[ ]; w=[0:1:1000]*pi/500; %X=(1-exp(-j*4*w)) ./ (1-exp(-j*w)); X=1+exp(-j*w)+exp(-j*2*w)+exp(-j*3*w); magX=abs(X); angX=angle(X)*180/pi; %% --Plot DTFT-- subplot(2,1,1); plot(w/pi,magX); grid; hold on subplot(2,1,2); plot(w/pi,angX); grid; hold on 제07장 이산 푸리에 변환

49 subplot(2,1,1); stem(w/pi,magX,'filled'); grid;
Matlab %% --DFT-- x=[ ]; N=4; w=[0:1:N-1]*2*pi/N; n=[0:1:N-1]; k=[0:1:N-1]; WN=exp(-j*2*pi/N); nk=n'*k; WNnk=WN .^ nk; X=x*WNnk; magX=abs(X); angX=angle(X)*180/pi; %% --Plot DFT-- subplot(2,1,1); stem(w/pi,magX,'filled'); grid; xlabel('frequency in pi units'); ylabel('|X|'); title('Magnitude of the DTFT(DFT)'); subplot(2,1,2); stem(w/pi,angX,'filled'); grid; xlabel('frequency in pi units'); ylabel('Degrees'); title('Phase of the DTFT(DFT)'); 제07장 이산 푸리에 변환

50 제07장 이산 푸리에 변환

51 Radix-2 FFT 알고리듬 N = 2n , n ;integer - DIT(Decimation-In-Time) 알고리듬
DIF(Decimation-In-Frequency) 알고리듬 computational complexity; (total number of complex multiplications) 제07장 이산 푸리에 변환

52 DFT와 FFT의 연산량 비교(복소수곱셈의 수)
DFT : N x N = N2 FFT : stage 수 x 각 stage의 곱셈수 = N DFT FFT 32 1024 80 64 4096 192 128 16384 448 제07장 이산 푸리에 변환

53 (Decimation – In –Time)
, 위 식에서 홀수 신호와 짝수 신호를 다음과 같이 정의하고 또한, 이므로 제07장 이산 푸리에 변환

54 부터 까지의 은 위 식에서 은? 도 마찬가지로 해서 과 을 대입하면, DIT의 결과 : 제07장 이산 푸리에 변환

55 8-point DFT를 2개의 4-point로 구현하는 구조
제07장 이산 푸리에 변환

56 4-point DFT를 2개의 2-point로 구현하는 구조
W2 0 = 1 이므로, P(0) = p[0] + p[1] P(1) = p[0] – p[1] 제07장 이산 푸리에 변환

57 제07장 이산 푸리에 변환

58 역비트 순(bit-reversed order)의 과정 ;
제07장 이산 푸리에 변환

59 (Decimation – In –Frequency)
N=2N1 인 경우에 이산 신호를 앞의 N1개와 뒤의 N1개로 나누어 표현할 수 있다. 위의 마지막 식에서 알 수 있듯이 k가 짝수일 때와 홀수일 때에 결과 값이 달라 진다. 제07장 이산 푸리에 변환

60 짝수 DFT (k =2r; 짝수) 홀수 DFT (k =2r+1; 홀수) 제07장 이산 푸리에 변환

61 제07장 이산 푸리에 변환

62 제07장 이산 푸리에 변환

63 스케일 인수 1/N 은 각 스테이지에서 1/2 의 곱을 수행하는 것이 일반적인
과 의 자리만 바꾸고 곱셈 계수 을 으로 치환한다. 스케일 인수 1/N 은 각 스테이지에서 1/2 의 곱을 수행하는 것이 일반적인 방법이다. 이 경우 곱의 연산은 비트(bit)로 구성된 수를 우측으로 1비트 shift시키면 된다. 제07장 이산 푸리에 변환

64 7-1, 7-4, 7-7, 7-9 7-1 y[n]={-3, -6, 3, 6} 7-4 x[n]={0, a, b, c}=
H.W.(7장 연습문제) 7-1, 7-4, 7-7, 7-9 7-1 y[n]={-3, -6, 3, 6} 7-4 x[n]={0, a, b, c}= 7-7 y[n]={7,13,18,15,12,9,5,2} 7-9 (b) |X(0)|=4, |X(1)|=0, |X(2)|=0, |X(3)|=0 제07장 이산 푸리에 변환