Chapter 11(DFT).ppt

1、Chapter 11Discrete Fourier Transform (DFT),Links the DFT and DTFT, DFS,Identifies the limited resolution of the DFT and problems such as smearing that arise from it,Applies the DFT to non-periodic and periodic signals,The fast DFT algorithm -FFT,Defines and interprets the DFT,The definition of DFT（D

2、iscrete Fourier Transform):,11.1 DFT BASICS,According to the definition, DFT used to calculate the spectrum of discrete periodic signals, in fact, any finite length signal can be seen as a cycle of the periodic signal; Infinite length signals must be truncated to finite length signals to calculate.,

3、1. Links the DFT and DTFT：,The Discrete Fourier transform (DFT) of x(n) is its N-point sampling DTFT transform, namely = 2k/N.,11.2 Links the DFT and other transform,Links the DTFT and DFT, between signal and IDFT,Non-periodic signal,DTFT spectrum,DFT spectrum within the signal window is the samplin

4、g form of the DTFT,The signals generated by the inverse DFT is part of the window.,2. Links the DTFT and Z transform：,Links the DFT and other transform,The z transform of finite sequence x (n) with length is N,The DTFT of finite sequence x (n) with length is N,The Discrete Time Fourier transform (DT

5、FT) of sequence x(n) is its z-transform values on the unit circle（z = ej ).,3. DFT and Z-transform：,Sampling the unit circle of as,Calculate X(z)：,Links the DFT and other transform,The DFT is sampling values of its z transformations on the unit circle.,Links the DFT and other transform,The links DFT

6、, DTFT and the Fourier transform is described as,Time domain sampling Time-domain windowing Frequency-domain sampling,Links the DFT and other transform,Time-domain and frequency -domain are continuous, non-periodic,Time-domain is discrete, non-periodic; frequency -domain is continuous cycle,Time-dom

7、ain is discrete, non-periodic; frequency-domain is continuous, periodic (copy), to quantified and spectrum aliasing of errors,Time-domain vector multiplication, frequency -domain convolution,Sample in the time domain,Time-domain is discrete, non-periodic; frequency domain is continuous and periodic,

8、The time-domain is discrete, non-periodic; frequency-domain is continuous, periodic and frequency leakage (plus windows directly generated error),Time-domain vector multiplication, frequency domain convolution,Window in the time-domain,Frequency domain is discrete, non-, time domain is continuous, p

9、eriodic,Frequency-domain is discrete and periodic , time-domain is discrete, periodic,Multiply the frequency domain loss, time-domain convolution,Sample in the Frequency-domain,Aliasing in the spectrum and quantified window process caused the error, but the DFT sample values are very close to the or

10、iginal signal spectrum DFT is close to the original spectrum on the N sampling points exactly.,Links the DFT and other transform,5. The links DFT and DFS,Links the DFT and other transform,The DFT covers the frequency range of 0 to fs. Frequency sampling points are at intervals of fs / N. Frequency i

11、nterval is smaller, the resolution is better ; the interval is greater, the DFT resolution is worse.,DFT frequency interval (frequency resolution),DFT component X (k) located at：,k = N / 2, f is the Nyquist boundary of fs/2,. Thus, k = 0 N / 2 , DFT points carry all the necessary amplitude and phase

12、 information, the remaining points are the mirror copy of the important signal frequency, symmetry about k = N / 2. This is the magnitude of the DFT spectrums feature .,DFT example,Ex11.4(p444)： The following figure shows the 40 seconds cosine wave, these two signals are added together and combined

13、with random noise to produced a signal x(t). Analysis its spectrum.,The signal contains two major frequency components, 1/16Hz and 3/8Hz. Now sampling fs = 6.4Hz, the digital frequency of signal：,x(n)：,DFT example,The digital signals 256 sampling points (envelope) within 40 seconds with 6.4Hz sampli

14、ng rate：,n=0:255; x=cos(2*pi*n/102.4)+cos(6*pi*n/51.2)+0.8*(rand(1,256)-0.5) plot(n,x); axis(0 255 2.5 2.5);,The amplitude spectrum calculated by DFT,f=fft(x); plot(n,abs(f); axis(0 255 0 140);,K = N / 2 = 128 point symmetry,K = N / 2 = 128 point symmetry,K = N / 2 = 128 point symmetry,Amplitude spe

15、ctrum of 0 to 127,plot(n(1:128),abs(f(1:128); axis(0 128 0 140);,Amplitude spectrum of 0 to 20,plot(n(1:20),abs(f(1:20),Lower frequency cosine 1/16Hz, i.e. between k = 2 and k = 3.,Higher frequency cosine 3/8Hz, i.e. k = 15,The digital signals 512 sampling points within 80 seconds with 6.4Hz samplin

16、g rate ：,n=0:511; x=cos(2*pi*n/102.4)+cos(6*pi*n/51.2)+0.8*(rand(1,256)-0.5) plot(n,x); axis(0 512 2.5 2.5);,The calculation of the DFT spectrum amplitude,f=fft(x); plot(n,abs(f); axis(0 512 0 300);,the amplitude spectrum of 040,plot(n(1:40),abs(f(1:40),Low frequency cosine 1/16 Hz, k = 5,High frequ

17、ency cosine 3/8 Hz , k = 15,DFT example,The DFT magnitude spectral envelope of Non-periodic signal will show the size of the change, but no clear peak. The DFT spectrum of periodic signal will appear narrow peak. These peaks lie in the harmonic frequencies.,The relationship of DFT and the periodic c

18、omponent of the signal,DFT example,example 11.8(p455)： The figure shows a portion of Touch-Tone signal for the number “4” . The 1024 samples are collected at 8kHz.,The peaks in the magnitude of the DFT spectrum reveals that the signal has two components,700Hz and 1209Hz, respectively. So the key num

19、ber 4 is identified.,DFT example,example 11.10(p458)： Digital white noise signal and its DFT magnitude spectrum as,Because there is no obvious peak, the signal is not periodic. In addition, because the contribution of all frequencies of the white noise signal are equal, all the amplitude spectrum ar

20、e approximately flat.,The finite set of time samples selected by a DFT is often said to lie within the DFT window,11.4 DFT Window effects,Spectral leakage,there is a clear difference between the spectrum of the truncated sequence and the spectrum of the original sequence.,Spectral interference,32 sa

21、mples,128 samples,Spectrum of sinusoid using rectangular windows of different lengths.,The window length is shorter, the peak is wider.,64 samples ( windows length),Select sinusoidal peak side lobe is less than the main lobe at least 40dB in order to approximate. Hamming window, Blackman window and

22、Kaiser window can achieve this goal. Use a longer window to improve the accuracy of signal analysis in the practical application .,Spectrum of sinusoid using nonrectangular windows,The spectrogram plots frequency against time so that each vertical slice of diagram contains the DFT magnitudes for one

23、 window of time.,11.5 Spectrograms,Spectrogram of phrase,Spectrograms,Humpback whale sounds Spectrogram,Spectrograms,Wider spacing indicates higher base frequency,Spectrogram of bird song,Spectrograms,Frequency changes rapidly,Spectrogram of Echolocation sounds,A wide frequency range,Spectrograms,Sp

24、ectrogram of Didgeridoo sound,A strong tone,Spectrograms,Big Ben bell audio spectrum,Low-frequency tone,Spectrograms,Telephone busy signal spectrum,Dual Tone Multi Frequency（DTMF） Repeat sequences of the two mono,Spectrograms,Motorcycle passing spectrogram,Doppler shift,Spectrograms,11.7 FFT basics,

25、Visible that, each calculation of X (k) need N complex multiplications and N-1 complex additions. Calculate all of the X (k) requires N2 complex multiplications and N(N-1)N2 complex addition, and with the increasing of N, it shows a nonlinear increasing.,The basic way to reduce the computational com

26、plexity,1、 Decomposition A combination of the larger N points DFT is decomposed into a number of small points of DFT can reduce the computational complexity. This is also the basic technical means of the FFT.,The basic way to reduce the computational complexity,N/4,N/2,N,N2/2,(N/2)2,(N/2)2,N2,N/2,N/4,N/4,N/4,2 Use the characteristics of the rotation factor WN,symmetrical characteristic:,The basic way to reduce the computational complexity,Periodicity,Special value,The basic