The Discrete Fourier Transform The description of signals in terms of their sinusoidal frequency content has proven to be as powerful and informative for discrete-time signals as it has for continuous-time signals. It is also probably the most powerful computational tool we will use. We now develop the basic discrete-time methods starting with the discrete Fourier transform (DFT) applied to finite length signals, followed by the discrete-time Fourier transform (DTFT) for infinitely long signals, and ending with the z-transform which uses the powerful tools of complex variable theory.

Definition of the DFT It is assumed that the signal x ( n ) to be analyzed is a sequence of N real or complex values which are a function of the integer variable n . The DFT of x ( n ) , also called the spectrum of x ( n ) , is a length N sequence of complex numbers denoted C ( k ) and defined by C ( k ) = ∑ n = 0 N − 1 x ( n ) e − j 2 π N n k using the usual engineering notation: j = − 1 . The inverse transform (IDFT) which retrieves x ( n ) from C ( k ) is given by x ( n ) = 1 N ∑ k = 0 N − 1 C ( k ) e j 2 π N n k which is easily verified by substitution into (1). Indeed, this verification will require using the orthogonality of the basis function of the DFT which is ∑ k = 0 N − 1 e − j 2 π N m k e j 2 π N n k = { N if n = m 0 if n ≠ m . The exponential basis functions, e − j 2 π N k , for k ∈ { 0 , N − 1 } , are the N values of the N th roots of unity (the N zeros of the polynomial ( s − 1 ) N ). This property is what connects the DFT to convolution and allows efficient algorithms for calculation to be developed . They are used so often that the following notation is defined by W N = e − j 2 π N with the subscript being omitted if the sequence length is obvious from context. Using this notation, the DFT becomes C ( k ) = ∑ n = 0 N − 1 x ( n ) W N n k One should notice that with the finite summation of the DFT, there is no question of convergence or of the ability to interchange the order of summation. No ``delta functions'' are needed and the N transform values can be calculated exactly (within the accuracy of the computer or calculator used) from the N signal values with a finite number of arithmetic operations.

Matrix Formulation of the DFT There are several advantages to using a matrix formulation of the DFT. This is given by writing () or () in matrix operator form as [ C 0 C 1 C 2 ⋮ C N − 1 ] = [ W 0 W 0 W 0 ⋯ W 0 W 0 W 1 W 2 W 0 W 2 W 4 ⋮ ⋮ W 0 ⋯ W ( N − 1 ) ( N − 1 ) ] [ x 0 x 1 x 2 ⋮ x N − 1 ] or C = F x . The orthogonality of the basis function in () shows up in this matrix formulation by the columns of F being orthogonal to each other as are the rows. This means that F T F = k I , where k is a scalar constant, and, therefore, F T = k F − 1 . This is called a unitary operator. The definition of the DFT in () emphasizes the fact that each of the N DFT values are the sum of N products. The matrix formulation in () has two interpretations. Each k -th DFT term is the inner product of two vectors, k -th row of F and x ; or, the DFT vector, C is a weighted sum of the N columns of F with weights being the elements of the signal vector x . A third view of the DFT is the operator view which is simply the single matrix equation (). It is instructive at this point to write a computer program to calculate the DFT of a signal. In Matlab , there is a pre-programmed function to calculate the DFT, but that hides the scalar operations. One should program the transform in the scalar interpretive language of Matlab or some other lower level language such as FORTRAN, C, BASIC, Pascal, etc. This will illustrate how many multiplications and additions and trigonometric evaluations are required and how much memory is needed. Do not use a complex data type which also hides arithmetic, but use Euler's relations e j x = cos ( x ) + j sin ( x ) to explicitly calculate the real and imaginary part of C ( k ) . If Matlab is available, first program the DFT using only scalar operations. It will require two nested loops and will run rather slowly because the execution of loops is interpreted. Next, program it using vector inner products to calculate each C ( k ) which will require only one loop and will run faster. Finally, program it using a single matrix multiplication requiring no loops and running much faster. Check the memory requirements of the three approaches. The DFT and IDFT are a completely well-defined, legitimate transform pair with a sound theoretical basis that do not need to be derived from or interpreted as an approximation to the continuous-time Fourier series or integral. The discrete-time and continuous-time transforms and other tools are related and have parallel properties, but neither depends on the other. The notation used here is consistent with most of the literature and with the standards given in . The independent index variable n of the signal x ( n ) is an integer, but it is usually interpreted as time or, occasionally, as distance. The independent index variable k of the DFT C ( k ) is also an integer, but it is generally considered as frequency. The DFT is called the spectrum of the signal and the magnitude of the complex valued DFT is called the magnitude of that spectrum and the angle or argument is called the phase.

Extensions of x(n) Although the finite length signal x ( n ) is defined only over the interval { 0 ≤ n ≤ ( N − 1 ) } , the IDFT of C ( k ) can be evaluated outside this interval to give well defined values. Indeed, this process gives the periodic property 4. There are two ways of formulating this phenomenon. One is to periodically extend x ( n ) to − ∞ and + ∞ and work with this new signal. A second more general way is evaluate all indices n and k modulo N . Rather than considering the periodic extension of x ( n ) on the line of integers, the finite length line is formed into a circle or a line around a cylinder so that after counting to N − 1 , the next number is zero, not a periodic replication of it. The periodic extension is easier to visualize initially and is more commonly used for the definition of the DFT, but the evaluation of the indices by residue reduction modulo N is a more general definition and can be better utilized to develop efficient algorithms for calculating the DFT . Since the indices are evaluated only over the basic interval, any values could be assigned x ( n ) outside that interval. The periodic extension is the choice most consistent with the other properties of the transform, however, it could be assigned to zero . An interesting possibility is to artificially create a length 2 N sequence by appending x ( − n ) to the end of x ( n ) . This would remove the discontinuities of periodic extensions of this new length 2 N signal and perhaps give a more accurate measure of the frequency content of the signal with no artifacts caused by ``end effects". Indeed, this modification of the DFT gives what is called the discrete cosine transform (DCT) . We will assume the implicit periodic extensions to x ( n ) with no special notation unless this characteristic is important, then we will use the notation x ˜ ( n ) .

Convolution Convolution is an important operation in signal processing that is in some ways more complicated in discrete-time signal processing than in continuous-time signal processing and in other ways easier. The basic input-output relation for a discrete-time system is given by so-called linear or non-cyclic convolution defined and denoted by y ( n ) = ∑ m = − ∞ ∞ h ( m ) x ( n − m ) = h ( n ) * x ( n ) where x ( n ) is the perhaps infinitely long input discrete-time signal, h ( n ) is the perhaps infinitely long impulse response of the system, and y ( n ) is the output. The DFT is, however, intimately related to cyclic convolution, not non-cyclic convolution. Cyclic convolution is defined and denoted by y ˜ ( n ) = ∑ m = 0 N − 1 h ˜ ( m ) x ˜ ( n − m ) = h ( n ) ∘ x ( n ) where either all of the indices or independent integer variables are evaluated modulo N or all of the signals are periodically extended outside their length N domains. This cyclic (sometimes called circular) convolution can be expressed as a matrix operation by converting the signal h ( n ) into a matrix operator as H = [ h 0 h L − 1 h L − 2 ⋯ h 1 h 1 h 0 h L − 1 h 2 h 1 h 0 ⋮ ⋮ h L − 1 ⋯ h 0 ] , The cyclic convolution can then be written in matrix notation as Y = H X where X and Y are column matrices or vectors of the input and output values respectively. Because non-cyclic convolution is often what you want to do and cyclic convolution is what is related to the powerful DFT, we want to develop a way of doing non-cyclic convolution by doing cyclic convolution. 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 by appending zeros to them. This will be developed later.

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 of standard signals together with the above properties will give a fairly large 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 to experiment with these results and to gain insight and intuition.