DFT Properties Chapter 5B Part B Circular Shift of a Sequence ●●● ●●● ●●● Circular Convolution Finite-Length Discrete Fourier Transform Computation of the DFT of Real Sequences Discrete Transforms Properties Linear Convolution Using the DFT DFT Properties 1.Circular Shift of a Sequence 1.Circular Shift of a Sequence Like the DTFT,the DFT also satisfies a This property is analogous to the time-shifting Ifx(n)is such a sequence,then for any non- number of properties that are useful in signal property of the DTFT,but with a subtle zero arbitrary integer,the shifted sequence processing applications difference x(n=x(m-n。) Some of these properties are essentially Consider length-N sequences defined identical to those of the DTFT,while some is no longer defined for the range 0≤n≤W-l others are somewhat different 0≤n≤N-1 We thus need to define another type of a shift A summary of the DFT properties are given in The sample values of such sequences are that will always keep the shifted sequence in table 5.3 on page 200 equal to zero for values of n<0 and n the range0≤n≤N-I 4
Chapter 5B Finite-Length Discrete Transforms Part B Discrete Fourier Transform Properties 3 DFT Properties Circular Shift of a Sequence Circular Shift of a Sequence Circular Convolution Computation of the DFT of Real Sequences Computation of the DFT of Real Sequences Linear Convolution Using the DFT 4 DFT Properties Like the DTFT, the DFT also satisfies a number of properties that are useful in signal processing applications Some of these properties are essentially identical to those of the DTFT, while some others are somewhat different A summary of the DFT properties are given in table 5.3 on page 200 5 1. Circular Shift of a Sequence This property is analogous to the time-shifting property of the DTFT, but with a subtle difference Consider length-N sequences defined 0İn İNˉ1 The sample values of such sequences are equal to zero for values of n < 0 and nıN 6 1. Circular Shift of a Sequence If x(n) is such a sequence, then for any nonzero arbitrary integer, the shifted sequence x1(n)=x1(nˉn0) is no longer defined for the range 0İn İNˉ1 We thus need to define another type of a shift that will always keep the shifted sequence in the range 0İn İN ˉ 1
1.Circular Shift of a Sequence 1.Circular Shift of a Sequence 1.Circular Shift of a Sequence The desired shift,called the circular shifi,is Illustration of the concept of a circular shift As can be seen from the previous figure,a defined using a modulo operation: right circular shift by no is equivalent to a left x.(m)=x(m-）) circular shift by N-o sample periods. A circular shift by an integer number n For n0 (right circular shifi),the above greater than N is equivalent to a circular shift equation implies by (no)s 34 02345 0.23 x(m)= Jx(n-o,form≤n≤N-1 xN+n-%),for0≤n< d -2.)-《+.)x(a-4=x《+2) 1.Circular Shift of a Sequence 1.Circular Shift of a Sequence 2.Circular Convolution DFT of the circular shift sequence r)=)m Circular convolution is analogous to linear y(n)=x(n+m）x)Rx(《n+m）x】 =w艺) convolution,but with a subtle difference Y()=DFT[v(m)] Comparison of linear convolution with circular 厚o-o+宫o) convolution =觉a+m)(o时 Consider two length-N sequences,g(n)and h(n) respectively -雪e ∑x(《)x)w g空)购✉时广X国倒 12
7 1. Circular Shift of a Sequence The desired shift, called the circular shift circular shift, is defined using a modulo operation: For n0>0 (right circular shift right circular shift), the above equation implies c ( ) 0 N xn x n n 0 0 0 0 ( ), for 1 ( ) ( ), for 0 c xn n n n N x n x Nnn nn 8 1. Circular Shift of a Sequence Illustration of the concept of a circular shift Illustration of the concept of a circular shift x(n) 6 6 xn xn 1 5 6 6 xn xn 4 2 9 1. Circular Shift of a Sequence As can be seen from the previous figure, a right circular shift by n0 is equivalent to a left circular shift by Nˉn0 sample periods. A circular shift by an integer number n0 greater than N is equivalent to a circular shift by 0 N n 10 1. Circular Shift of a Sequence DFT of the circular shift sequence DFT of the circular shift sequence 1 0 1 0 ( ) N N N N kn N N N n N kn N N n yn x n m R n m Y k DFT y n x n m R nW xnm W 11 1. Circular Shift of a Sequence ' 1 ' ' 1 ' ' 111 '0 '0 ' 1 ' ' 0 1 ' 0 ' ' (.) (.) (.) ' ' N m kn m N N n m N m km kn N N N n m N m Nm km N n n nN N km kn N N N n N km kn km N NN n Yk x n W W xn W W W xn W W xn W W X k 12 2. Circular Convolution Circular convolution is analogous to linear convolution, but with a subtle difference Comparison of linear convolution with circular convolution Consider two length-N sequences, g(n) and h(n) respectively
2.Circular Convolution 2.Circular Convolution 2.Circular Convolution linear convolutioncircular convolution To develop a convolution-like operation Since the operation defined involves two Length of 2W-1 to be specified resulting in a length-N sequence y (n),we length-N sequences,it is often referred to as an convolution need to define a circular time-reversal,and N-point circular convolution,denoted as Convolution Formulas 方a=2gmMa-m d间=是xmha-】 then apply a circular time-shift. ynFg(n)h(n) Resulting operation,called a circular Convolution comvolution,is defined by The circular convolution is commutative,i.e. 四 Signs ⊙0r◆ gm)@h(n=(m)©g(m Condition of yc(n)= ∑gm)h(n-m）)b0≤n≤N-l equivalence 4 2.Circular Convolution 2.Circular Convolution 2.Circular Convolution Example 1 Length of Circular Comvolution is 4 Step 2:Perform Circular time-shift operation Step 3:Perform multiplication and summation of seguences over the region of 0m for 02 and n=3 respectively 99 1201 2112 229H Step 1:Perform Circular time-reversal operation on -3-2-10123 (m)(or g(m)) y(0)=242+0+2=6 y(1=244+0+1=7 Rd(-)211马 Bue0-m虎m22110 3出 1201 3-2H0123 1122 Green创-m〉，Ram1221) y21+4+0+1=8 3=1+2+0+2a5 These seven samples are enough to calculate the Pupk3-m8m112斗 circular convolution because of the periodicity of DFT 10
13 2. Circular Convolution ? Condition of equivalence or Convolution Signs Convolution Formulas 2Nˉ1 to be specified Length of convolution linear convolution circular convolution 1 0 () ( ) N C N m y n gmh n m 1 0 () ( )( ) N L m y n g mhn m N 14 2. Circular Convolution To develop a convolution-like operation resulting in a length-N sequence yC(n), we need to define a circular time circular time-reversal reversal, and then apply a circular time a circular time-shift. Resulting operation, called a circular circular convolution, is defined by 1 0 () ( ) , 0 1 N C N m y n gmh n m n N 15 2. Circular Convolution Since the operation defined involves two length-N sequences, it is often referred to as an N-point circular convolution, denoted as yC(n)=g(n) h(n) The circular convolution is commutative, i.e. g(n) h(n)=h(n) g(n) N N N 16 2. Circular Convolution Example 1 Length of Circular Convolution is 4 g(n) h(n) Step 1: Perform Circular time-reversal operation on h(m) (or g(m)) 4 h m ( ) These seven samples are enough to calculate the circular convolution because of the periodicity of DFT 17 2. Circular Convolution Step 2: Perform Circular time-shift operation Red {2 1 1 2} 4 4 h m Rm ( ) () Blue {2 2 1 1} 4 4 h m Rm (1 ) ( ) Green {1 2 2 1} 4 4 h m Rm (2 ) ( ) Purple {1 1 2 2} 4 4 h m Rm (3 ) ( ) 18 2. Circular Convolution Step 3: Perform multiplication and summation of sequences over the region of 0İmİ3 for n=0,n=1,n=2 and n=3 respectively y(0)= 1 2 0 1 2 1 1 2 2+2+0+2= 6 y(1)= 1 2 0 1 2 2 1 1 2+4+0+1= 7 y(2)= 1 2 0 1 1 2 2 1 1+4+0+1= 6 y(3)= 1 2 0 1 1 1 2 2 1+2+0+2= 5
2.Circular Convolution 2.Circular Convolution 2.Circular Convolution In this case,hence,the procedure of circular Example 2 Length of Circular Comvolution is 7 convolution is equivalent to that of linear convolution In order to develop the 7-point circular convolution over the region of principle value 8ahee88e6eoe0ionc8o1n878y Obviously,this conclusion always holds when the length of Circular Convolution is not less than 7 appending each with 3 zero-valued samples,i.e. Perform Circular time-reversal operation on h(m) Summary g(n).0≤ns3 g.(m)= These three samples are Provided that the length of Circular Convolution is not involved in not less than N+M-1 where N and M are the lengths h(n)= 「hm),0sns3 the circular of the two sequences involved,the procedure of 0,4sn≤6 convolution gm L operation circular convolution is equivalent to that of linear convolution 3.Classification of Finite-Length 3.Classification of Finite-Length 4.Computation of the Sequences Sequences DFT of Real Sequences i(n) Based on Conjugate Symmetry It has been discussed in Ch.2 In most practical applications,sequences of Based on Geometric Symmetry interest are real A length-N symmetry sequence x(n)satisfies In such cases,the symmetry properties of the the conditionx(n)=x(N-1-n) DFT given in Table 5.2 can be exploited to make the DFT computations more efficient A length-N antisymmetry sequence x(n) satisfies the condition x(m)=-xN-1-)
19 2. Circular Convolution Example 2 Length of Circular Convolution is 7 In order to develop the 7-point circular convolution on the sequences in the former example, we extended these two sequences to length 7 by appending each with 3 zero-valued samples, i.e. ( ), 0 3 ( ) 0, 4 6 e gn n g n n ( ), 0 3 ( ) 0, 4 6 e hn n h n n 20 2. Circular Convolution ge(n) he(n) Perform Circular time-reversal operation on he(m) 7 ( ) e h m ge(m) These three samples are not involved in the circular convolution operation 21 2. 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 that the length of Circular Convolution is not less than N+Mˉ1 where N and M are the lengths of the two sequences involved, the procedure of circular convolution is equivalent to that of linear convolution 22 3. Classification of Finite-Length Sequences Based on Conjugate Symmetry It has been discussed in Ch.2 Based on Geometric Symmetry A length-N symmetry symmetry sequence x(n) satisfies the condition A length-N antisymmetry antisymmetry sequence x(n) satisfies the condition x() ( 1 ) n xN n x() ( 1 ) n xN n 23 3. Classification of Finite-Length Sequences h n( ) n 0 1 2 4 5 7 6 3 8 Center of symmetry h n( ) n 0 1 2 7 4 5 6 8 3 Center of symmetry h n( ) n 0 1 2 4 7 5 3 6 Center of symmetry h n( ) n 0 1 2 4 7 5 6 3 Center of symmetry Type 1 N=9 Type 4 N=8 Type 3 N=9 Type 2 N=8 24 4. Computation of the DFT of Real 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
4.Computation of the 4.1 N-Point DFTs of Two Real 4.1 N-Point DFTs of Two Real DFT of Real Sequences Sequences Using a Single N-Point DFT Sequences Using a Single N-Point DFT Let g(n)and h(n)be two length-N real sequences with G(k)and H(k)denoting their Let X(k)denote the N-point DFT of x(n) N-Point DFTs of Two Real Sequences Using respective N-point DFTs Then,from Table 5.1 we arrive at a Single N-Point DFT These two N-point DFTs can be computed 2N-Point DFTs of a Real Sequence Using a efficiently using a single N-point DFT a=X因+X(-4,y Single N-Point DFT Define a complex length-N sequence =号-r-.》 x(n)=g(n)+j h(n) .Note that .Hence,g(n)=Re(x(n)}and h(n)=Im (x(n)) X(《-k)w)=X(《W-k)w) 4.1 N-Point DFTs of Two Real 4.1 N-Point DFTs of Two Real 4.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT Sequences Using a Single N-Point DFT Sequences Using a Single N-Point DFT Example We can work out the 4-point DFT of x(n) Therefore We compute the 4-point DFTs of the two real sequences g(n)and h(n)given below X}={4+j62-22} {G)={41-可j-21+乃 {gm)}={12013,{hm)》={2211 From the above H}={61-j01+奶 X*}={4-j62-2-j2 .Then (x(n)=(g(n))+j(h(n))is given by 。Hence {xm)}={1+22+2j1+i》 X(N-k))}=4-j6-2j-22马
25 4. Computation of the DFT of Real Sequences N-Point DFTs of Two Real Sequences Using of Two Real Sequences Using a Single a Single N-Point DFT 2N-Point DFTs of a Real Sequence Using a of a Real Sequence Using a Single N-Point DFT 26 4.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT Let g(n) and h(n) be two length-N real sequences with G(k) and H(k) denoting their respective N-point DFTs These two N-point DFTs can be computed efficiently using a single N-point DFT Define a complex length-N sequence x(n)˙g(n)ˇj h(n) Hence, g(n)=Re{x(n)} and h(n)=Im{x(n)} 27 4.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT Let X(k) denote the N-point DFT of x(n) Then, from Table 5.1 we arrive at Note that * * 1 () () ( ) 2 1 () () ( ) 2 N N Gk X k X k Hk Xk X k j * * ( )( ) N N X k X Nk 28 4.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT Example Example We compute the 4-point DFTs of the two real sequences g(n) and h(n) given below {g(n)}={1 2 0 1}, {h(n)}={2 2 1 1} Then {x(n)}˙{g(n)}ˇj{h(n)} is given by {x(n)}={1+j2 2+j2 j 1+j} 29 4.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT We can work out the 4-point DFT of x(n) {X(k)}={4+j6 2 –2 j2} From the above {X*(k)}={4–j6 2 –2 –j2} Hence * { ( )} {4 6 2 2 2} N X Nk j j 30 4.1 N-Point DFTs of Two Real Sequences Using a Single N-Point DFT Therefore {G(k)}={4 1–j –2 1+j} {H(k)}={6 1–j 0 1+j}
4.2 2N-Point DFT of 4.2 2N-Point DFT of 4.2 2N-Point DFT of a Real Sequence Using an N-Point DFT a Real Sequence Using an N-Point DFT a Real Sequence Using an N-Point DFT ●Let(m）be a length-2 Vreal sequence with an P=是gwmg+2mg,0sk≤2N- 2N-point DFT V(k) -空ow =0 Define two length-N real sequences g(n)and h(n)as follows: 、v2nw签+Z2切+1)w i.e. V(k)=G()x)+WH(k),)0≤k≤2N-1 gn)=(2m),hMn)=(2t1)0≤n≤N-1 Let G(k)and H(k)denote their respective N 0 where the DFTs of G(k)and H(k)can be point DFTs computed by means of the method discussed in ∑3ow+w】 ∑hmw,0≤ks2N- 4.1 5.Linear Convolution 5.1 Linear Convolution of Two Finite- 5.1 Linear Convolution of Two Finite- Using the DFT Length Sequences Length Sequences Linear convolution is a key operation in many Let g(n)and h(n)be two finite-length ·Then signal processing applications. sequences of length N and M,respectively yz(n)=g(m）图nFg(m)⊙hm Since a DFT can be efficiently implemented 。Denote L=W4M-l The corresponding implementation scheme is using FFT algorithms,it is of interest to Define two length-L sequences illustrated below develop methods for the implementation of linear convolution using the DFT. &.(n)- Jg(m,0≤n≤N-1 0. N≤n≤L-1 hn,0≤n≤M-1 h.(m)= Length-(N+M-I) 0,M≤n≤L-1 1场
31 4.2 2N-Point DFT of a Real Sequence Using an N-Point DFT Let v(n) be a length-2N real sequence with an 2N-point DFT V(k) Define two length-N real sequences g(n) and h(n) as follows: g(n)=v(2n), h(n)=v(2n+1) 0İnİNˉ1 Let G(k) and H(k) denote their respective N point DFTs 32 4.2 2N-Point DFT of a Real Sequence Using an N-Point DFT 2 1 2 0 1 1 2 (2 1) 2 2 0 0 1 1 2 0 0 1 1 2 0 0 () () (2 ) (2 1) () () () () ,0 2 1 N nk N n N N nk n k N N n n N N nk nk k N NN n n N N nk k nk NN N n n V k vnW v nW v n W g nW hnW W g nW W hnW k N 33 4.2 2N-Point DFT of a Real Sequence Using an N-Point DFT 2 () ( ) ( ) 0 2 1 k Vk G k W H k k N N N N 1 1 2 0 0 () () () ,0 2 1 N N nk k nk NN N n n V k g nW W hnW k N i.e. where the DFTs of G(k) and H(k) can be computed by means of the method discussed in 4.1 34 5. 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 convolution using the DFT. 35 5.1 Linear Convolution of Two FiniteLength Sequences Let g(n) and h(n) be two finite-length sequences of length N and M, respectively Denote L=N+Mˉ1 Define two length-L sequences ( ), 0 1 ( ) 0, 1 e gn n N g n N n L ( ), 0 1 ( ) 0, 1 e hn n M h n MnL 36 5.1 Linear Convolution of Two FiniteLength Sequences Then yL(n)=g(n) h(n)=g(n) h(n) The corresponding implementation scheme is illustrated below N h (N+Mˉ1) - point IDFT g(n) Length N h(n) Length M (N+Mˉ1) - point DFT Zero-padding with Mˉ1 Zeros ge(n) yL(n) (N+Mˉ1) - point DFT Zero-padding with Nˉ1 Zeros he(n) Length-(N+Mˉ1)
5.2 Linear Convolution of a Finite-Length Sequence with an Infinite-Length Sequence 5.2 Overlap-Add Method 5.2 Overlap-Add Method .We next consider the DFT-based We first segment x(n),assumed to be a causal Thus we can write implementation of sequence here without (any)loss of generality. into a set of contiguous finite-length (n)=Kn)x(n)=y.(n-mN) ym)=∑h(Oxn-D=m)exn) subsequences of length Neach: where x(m)=∑x.(n-mW) yn=n)图x.(m where h(n)is a finite-length sequence of length Mand x(n)is an infinite length (or a where Since h(m)is of length Mand x (n)is of length finite length sequence whose length is much x(n+mW),0≤n≤N-1 N,the linear convolution y (n=h(n)x(m) x.()= greater than M) 9 otherwise is of length N+M-1 5.2 Overlap-Add Method 5.2 Overlap-Add Method 5.2 Overlap-Add Method As a result,the desired linear convolution There is one more subtlety to take care of ●The second short convolution y(m=n)®x(n yn=h(n)x(n)has been broken up into a before we can implement is also of length N+M-1 but is defined for sum of infinite number of short-length linear N≤n≤2W+M-2 convolutions of length N+M-1 each: )=∑yn-mN) =0 ●◆There is an overlap of M-1 samples y(n=h(n)x.(n) using the DFT-based approach between these two short linear convolutions Each of these short convolutions can be Now the first convolution in the above sum, Likewise,the third short convolution implemented using the DFT-based method yo(m)=h(m)xo(n)is of length N+M-1 and is y2(n=h(m)x(n),is also of length N+M-1 discussed earlier,where the DFTs (and the defined for0≤nsN+M-2 but is defined for2W≤n≤3W+M-2 IDFT)are computed on the basis of(N+M-1) points 42
37 5.2 Linear Convolution of a Finite-Length Sequence with an Infinite-Length Sequence We next consider the DFT-based implementation of where h(n) is a finite-length sequence of length M and x(n) is an infinite length (or a finite length sequence whose length is much greater than M) 1 0 ( ) () ( ) M l yn hl xn l = h(n) x(n) 38 5.2 Overlap-Add Method We first segment x(n), assumed to be a causal sequence here without (any) loss of generality, into a set of contiguous finite-length subsequences of length N each: where 0 () ( ) m m x n x n mN ( ), 0 1 ( ) 0, otherwise m x n mN n N x n 39 5.2 Overlap-Add Method Thus we can write where Since h(n) is of length M and xm(n) is of length N, the linear convolution is of length N+Mˉ1 0 ( ) m m y n mN y(n)= h(n) x(n) ym(n)= h(n) xm (n) ym(n)= h(n) xm(n) 40 5.2 Overlap-Add Method As a result, the desired linear convolution has been broken up into a sum of infinite number of short-length linear convolutions of length N+Mˉ1 each: Each of these short convolutions can be implemented using the DFT-based method discussed earlier, where the DFTs (and the IDFT) are computed on the basis of (N+Mˉ1) points y(n)= h(n) x(n) ym(n)= h(n) xm (n) 41 5.2 Overlap-Add Method There is one more subtlety to take care of before we can implement using the DFT-based approach Now the first convolution in the above sum, is of length N+Mˉ1 and is defined for 0İnİN+Mˉ2 0 () ( ) m m y n y n mN y0(n)= h(n) x0(n) 42 5.2 Overlap-Add Method The second short convolution is also of length N+Mˉ1 but is defined for Nİnİ2N+Mˉ2 There is an overlap of Mˉ1 samples between these two short linear convolutions Likewise, the third short convolution , is also of length N+Mˉ1 but is defined for 2Nİnİ3N+Mˉ2 y1(n)= h(n) x1(n) y2(n)= h(n) x2(n)
5.2 Overlap-Add Method 5.2 Overlap-Add Method 5.2 Overlap-Add Method Thus there is an overlap of M-1 samples between /i(m)®x,(m)and h(m)®x(m In general,there will be an overlap of M-1 samples between the samples of the short convolutionsh(n)x(n)and h(m)x,(n) 909090- This process is illustrated in the figure on the next slide for M=5 and N=7. m- 回 片a-Hy以m10 5.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 portions 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
43 5.2 Overlap-Add Method Thus there is an overlap of Mˉ1 samples between and In general, there will be an overlap of Mˉ1 samples between the samples of the short convolutions and This process is illustrated in the figure on the next slide for M = 5 and N = 7. h(n) x1(n) h(n) x2(n) h(n) xr-1(n) h(n) xr(n) 44 5.2 Overlap-Add Method 45 5.2 Overlap-Add Method y0(n) y0(n)+y1(n-7) y1(n-7) y1(n-7)+y2(n-14) 46 5.2 Overlap-Add Method The above procedure is called the overlap add overlap add method since the results of the short linear convolutions overlap and the overlapped portions 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 moving average filter