《数字信号处理a（双语）chapter 5-finite-length discrete transformb-1140318.ppt》由会员分享，可在线阅读，更多相关《数字信号处理a（双语）chapter 5-finite-length discrete transformb-1140318.ppt（90页珍藏版）》请在三一文库上搜索。
1、Chapter 5,Finite-Length Discrete Transforms,Part B: Operations on Finite-Length Sequences and DFT Properties,Circular Time-reversal of a Sequence （Section 2.3.1 ） Circular Shift of a Sequence（Section 2.3.2 and 5.7 ） Circular Convolution（Section 5.4 and 5.7 ） Classification of Finite-Length Sequences
2、 ( Section 5.5) DFT Symmetry Relations and Theorems (Section 5.6 and 5.7) Fourier-Domain Filtering (Section 5.8) Computation of the DFT of Real Sequences (Section 5.9) Linear Convolution Using the DFT( Section 5.10),Operations on Finite-Length Sequences,Consider the length-N sequence xn defined for
3、0nN-1 A time-reversal operation on xn will result in a length-N sequence defined for -(N-1)n0 A linear time-shift of xn by integer-valued M will result in a length-N sequence xn + M no longer defined for 0nN-1 A convolution sum of two length-N sequences defined for 0nN-1 will result in a sequence of
4、 length 2N-1 defined for 0n2N-2,Operations on Finite-Length Sequences,We need to define new type of time reversal, time-shifting and convolution operation, so that the resultant length-N sequences are also are in the range 0nN-1,1、Circular Time-Reversal Operation,See in textbook Section 2.3.1,Modulo
5、 Operation(取模运算),The time-reversal operation on a finite-length sequence is obtained by the modulo operation N= m modulo N where m and N is any integer, and 0,1,N-1 be a set of N positive integers r= N is called the residue(余数), which is an integer with a value between 0 and N-1 r=m+lN, where l is a
6、 positive or negative integer chosen to make m+lN an integer between 0 and N-1,Modulo Operation(取模运算),Example For N = 7 and m = 25, we have r=25+7l=25-7*3=4，Thus 7 =4 For N = 7 and m = -15, we get r=-15+7l=-15+7*3=6，Thus 7 =6,1、Circular Time-Reversal Operation,The circular time-reversal version yn o
7、f a length-N sequence xn defined for 0nN-1 is given by yn=xN Example Consider xn=x0, x1, x2, x3, x4 Its circular time-reversed version is given by yn=x5=x0, x4, x3, x2, x1,2、Circular Shift of a Sequence,See in Section 2.3.2 and 5.7,2、Circular Shift of a Sequence,This property is analogous to the tim
8、e-shifting property of the DTFT, but with a subtle difference Consider length-N sequences defined for 0nN1,2、Circular Shift of a Sequence,2、Circular Shift of a Sequence,A right circular shift by n0 is equivalent to a left circular shift by Nn0 sample periods.,2、Circular Shift of a Sequence,A circula
9、r shift by an integer number n0 greater than N is equivalent to a circular shift by N,Example: 6=1, x6=x6,2、Circular Shift of a Sequence,The length-N sequence is displayed on a circle at N equally spaced points The circular shift operation can be viewed as a clockwise or anti-clockwise rotation of t
10、he sequence by n0 sample spacings,Compare the shift and circular shift,shift,circularshift,周期延拓,shift,取主值区间0N-1,2、Circular Shift of a Sequence,2、Circular Shift of a Sequence,3、Circular Convolution,See in Section 5.4 and 5.7,3. Circular Convolution,Circular convolution is analogous to linear convolut
11、ion, but with a subtle difference Consider two length-N sequences, g(n) and h(n) respectively,3、Circular Convolution,3、Circular Convolution,3、Circular Convolution,Example Determine the 4-point circular convolution of the two length-4 sequences: gn=1 2 0 1, hn=2 2 1 1 as skecthed below,3、Circular Con
12、volution,The result is a length-4 sequence yCn From the above we observe,N,3、Circular Convolution,Likewise,3、Circular Convolution,yCn,(a) yc0,循环卷积过程图解,3、Circular Convolution,The circular convolution can also be computed using a DFT-based approach The N-point circular convolution can be written in ma
13、trix form as,3、Circular Convolution,Note: 1、The element in each row of the matrix are obtained by circularly rotating the elements of the previous row to the right by one position. Such a matrix is called a circulant matrix(轮换矩阵、 循环行列式矩阵) 2、使用矩阵形式计算循环卷积前，需要通过补零把参与循环卷积的两个输入序列扩充成相同长度，且此长度等于DFT的点数,3、Ci
14、rcular Convolution,Example Now let us extend the two length-4 sequences to length 7 by appending each with three zero-valued samples, i.e.,3、Circular Convolution,We next determine the 7-point circular convolution of gen and hen:,Matrix method:,3、Circular Convolution,As can be seen from the above tha
15、t yn is precisely the sequence yLn obtained by a linear convolution of gn and hn Try to think: What is the relation between the circular convolution and the linear convolution?,yCn,3. Circular Convolution,3、Circular Convolution,3、Circular Convolution,3、Circular Convolution,3、Circular Convolution,3、C
16、ircular Convolution,3、Circular Convolution,In this case, hence, the procedure of circular convolution is equivalent to that of linear convolution over the region of principle value Obviously, this conclusion always holds when the length of Circular Convolution is not less than 7 Summary Provided tha
17、t the length of Circular Convolution is not less than L+K1 where L and K are the lengths of the two sequences involved, the procedure of circular convolution is equivalent to that of linear convolution,if : aliasing,if : not aliasing,the condition that the circular convolution to be equivalent to th
18、e linear convolution is,Notes that, L+K-1 is equals to the length of linear convolution.,So, in order to perform a linear convolution using the IDFT of the product of the DFT of two sequences, we must choose a DFT size N satisfying the condition above.,时域周期延拓，周期为N,Example,Compute the linear convolut
19、ion of the two sequences x(n) and h(n), as well as the circular convolutions of x(n) and h(n) with different length N.,L=4,K=3,First, we compute the linear convolution of x(n) and h(n),then compute circular convolution of length N=4,4,then compute circular convolution of length N=6,6,then compute ci
20、rcular convolution of length N=7,7,from example above, we can see that,The circular convolution can equivalent to the linear convolution when,and if NL+K-1, there happens aliasing, for example N=4,periodic repitition with period 4,+,+,=,and then,there have L+K-1-N aliasing points at head of sequence
21、, 4+3-1-4=2 points in this example.,4、Classification of Finite-Length Sequences,See in textbook section 5.5,4、Classification of Finite-Length Sequences,Based on Conjugate Symmetry （see in Section 5.5.1） A complex DFT Xk can be expressed as a sum of a circular conjugate symmetric part Xcsk and a circ
22、ular conjugate anti-symmetric Xcak part Xk = Xcsk+ Xcak, 0 k N 1 Where Xcsk=( X k+X * N ) 0 k N-1 Xcak=( X k-X * N ) 0 k N-1,4、Classification of Finite-Length Sequences,Based on Conjugate Symmetry（see in Section 5.5.1） An N-point DFT Xk is said to be a circular conjugate-symmetric sequence if Xk= X*
23、N=X*N An N-point DFT Xk is said to be a circular conjugate-anti-symmetric sequence if Xk= -X*N=-X*N,4、Classification of Finite-Length Sequences,Based on Geometric Symmetry（see in Section 5.5.2） A length-N symmetry sequence x(n) satisfies the condition x(n) = x(N 1 n) A length-N antisymmetry sequence
24、 x(n) satisfies the condition x(n) = x(N 1 n),4、Classification of Finite-Length Sequences,5、DFT Symmetry Relations and DFT Theorems,See in textbook section 5.6 and 5.7,length L,length K,length L+K-1,N points,length N,Sampling ( N samples in a period),N,N points,6、Fourier-Domain Filtering,See in text
25、book section 5.8,6、Fourier-Domain Filtering,Often one is interested in removing the components of a finite-length discrete-time signal in one or more frequency bands.,IDTFT,Truncation,Truncation,7. Computation of the DFT of Real Sequences,See in textbook section 5.9,7. Computation of the DFT of Real
26、 Sequences,In most practical applications, sequences of interest are real In such cases, the symmetry properties of the DFT given in Table 5.2 can be exploited to make the DFT computations more efficient,7. Computation of the DFT of Real Sequences,N-Point DFTs of Two Real Sequences Using a Single N-
27、Point DFT 2N-Point DFTs of a Real Sequence Using a Single N-Point DFT,7.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT,7.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT,5.1,7.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT,7.1 N-Point DFTs of Two Real
28、 Sequences Using a Single N-Point DFT,7.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT,7.2 2N-Point DFT of a Real Sequence Using an N-Point DFT,7.2 2N-Point DFT of a Real Sequence Using an N-Point DFT,7.2 2N-Point DFT of a Real Sequence Using an N-Point DFT,7.1,8、Linear Convolution
29、Using the DFT,See in textbook section 5.10,8、Linear Convolution Using the DFT,Linear convolution is a key operation in many signal processing applications. Since a DFT can be efficiently implemented using FFT algorithms, it is of interest to develop methods for the implementation of linear convoluti
30、on using the DFT,8.1 Linear Convolution of Two Finite- Length Sequences,8.1 Linear Convolution of Two Finite- Length Sequences,8.2 Linear Convolution of a Finite Sequence with an Infinite Sequence,Overlap-Add Method Overlap-Save Method,8.2 Overlap-Add Method,8.2 Overlap-Add Method,8.2 Overlap-Add Me
31、thod,8.2 Overlap-Add Method,8.2 Overlap-Add Method,8.2 Overlap-Add Method,8.2 Overlap-Add Method,8.2 Overlap-Add Method,8.2 Overlap-Add Method,8.2 Overlap-Add Method,The above procedure is called the overlap add method since the results of the short linear convolutions overlap and the overlapped por
32、tions are added to get the correct final result. The function fftfilt can be used to implement the above method. Program 5_5 illustrates the use of fftfilt in the filtering of a noise-corrupted signal using a length-3 moving average filter (P.208),本章重点,DFT的定义、性质及其证明 循环卷积、循环卷积与线性卷积的关系 实序列的DFT 线性卷积的DFT实现 重叠相加法,Homework,Problems: 5.2，5.9，5.10, 5.20, 5.25，5.28, 5.43，5.45, 5.55,