<< Chapter < Page Chapter >> Page >

The convolution of a length N sequence with a length M sequence yields a length N + M - 1 output sequence. The calculation of non-cyclic convolution by using cyclic convolution requires modifying the signals byappending zeros to them. This will be developed later.

Properties of the dft

The properties of the DFT are extremely important in applying it to signal analysis and to interpreting it. The main properties are given hereusing the notation that the DFT of a length- N complex sequence x ( n ) is F { x ( n ) } = C ( k ) .

  1. Linear Operator: F { x ( n ) + y ( n ) } = F { x ( n ) } + F { y ( n ) }
  2. Unitary Operator: F - 1 = 1 N F T
  3. Periodic Spectrum: C ( k ) = C ( k + N )
  4. Periodic Extensions of x ( n ) : x ( n ) = x ( n + N )
  5. Properties of Even and Odd Parts: x ( n ) = u ( n ) + j v ( n ) and C ( k ) = A ( k ) + j B ( k )
    u v A B | C | θ
    even 0 even 0 even 0
    odd 0 0 odd even π / 2
    0 even 0 even even π / 2
    0 odd odd 0 even 0
  6. Cyclic Convolution: F { h ( n ) x ( n ) } = F { h ( n ) } F { x ( n ) }
  7. Multiplication: F { h ( n ) x ( n ) } = F { h ( n ) } F { x ( n ) }
  8. Parseval: n = 0 N - 1 | x ( n ) | 2 = 1 N k = 0 N - 1 | C ( k ) | 2
  9. Shift: F { x ( n - M ) } = C ( k ) e - j 2 π M k / N
  10. Modulate: F { x ( n ) e j 2 π K n / N } = C ( k - K )
  11. Down Sample or Decimate: F { x ( K n ) } = 1 K m = 0 K - 1 C ( k + L m ) where N = L K
  12. Up Sample or Stretch: If x s ( 2 n ) = x ( n ) for integer n and zero otherwise,then F { x s ( n ) } = C ( k ) , for k = 0 , 1 , 2 , . . . , 2 N - 1
  13. N Roots of Unity: ( W N k ) N = 1 for k = 0 , 1 , 2 , . . . , N - 1
  14. Orthogonality:
    k = 0 N - 1 e - j 2 π m k / N e j 2 π n k / N = N if n = m 0 if n m .
  15. Diagonalization of Convolution: If cyclic convolution is expressed as a matrix operation by y = Hx with H given by [link] , the DFT operator diagonalizes the convolution operator H , or F T HF = H d where H d is a diagonal matrix with the N values of the DFT of h ( n ) on the diagonal. This is a matrix statement of Property 6 . Note the columns of F are the N eigenvectors of H , independent of the values of h ( n ) .

One can show that any “kernel" of a transform that would support cyclic, length-N convolution must be the N roots of unity. This says the DFT isthe only transform over the complex number field that will support convolution. However, if one considers various finite fields or rings, aninteresting transform, called the Number Theoretic Transform, can be defined and used because the roots of unity are simply two raised to apowers which is a simple word shift for certain binary number representations [link] , [link] .

Examples of the dft

It is very important to develop insight and intuition into the DFT or spectral characteristics of various standard signals. A few DFT's ofstandard signals together with the above properties will give a fairlylarge set of results. They will also aid in quickly obtaining the DFT of new signals. The discrete-time impulse δ ( n ) is defined by

δ ( n ) = 1 when n = 0 0 otherwise

The discrete-time pulse M ( n ) is defined by

M ( n ) = 1 when n = 0 , 1 , , M - 1 0 otherwise

Several examples are:

  • D F T { δ ( n ) } = 1 , The DFT of an impulse is a constant.
  • D F T { 1 } = N δ ( k ) , The DFT of a constant is an impulse.
  • D F T { e j 2 π K n / N } = N δ ( k - K )
  • D F T { cos ( 2 π M n / N ) = N 2 [ δ ( k - M ) + δ ( k + M ) ]
  • D F T { M ( n ) } = sin ( π N M k ) sin ( π N k )

These examples together with the properties can generate a still larger set of interesting and enlightening examples. Matlab can be used toexperiment with these results and to gain insight and intuition.

The discrete-time fourier transform

In addition to finite length signals, there are many practical problems where we must be able to analyze and process essentially infinitely longsequences. For continuous-time signals, the Fourier series is used for finite length signals and the Fourier transform or integral is used forinfinitely long signals. For discrete-time signals, we have the DFT for finite length signals and we now present the discrete-time Fouriertransform (DTFT) for infinitely long signals or signals that are longer than we want to specify [link] . The DTFT can be developed as an extension of the DFT as N goes to infinity or the DTFT can be independently defined and then the DFT shown to be a special case of it.We will do the latter.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital signal processing and digital filter design (draft). OpenStax CNX. Nov 17, 2012 Download for free at http://cnx.org/content/col10598/1.6
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital signal processing and digital filter design (draft)' conversation and receive update notifications?

Ask