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}