Definition of the DFT

It is assumed that the signal x(n)x(n) to be analyzed is a sequence of NN real or complex values which are a function of the integer variable nn. The DFT of x(n)x(n), also called the spectrum of x(n)x(n), is a length NN sequence of complex numbers denoted C(k)C(k) and defined by

using the usual engineering notation: j=-1j=-1. The inverse transform (IDFT) which retrieves x(n)x(n) from C(k)C(k) is given by

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

The exponential basis functions, e-j2πNke-j2πNk, for k∈{0,N-1}k∈{0,N-1}, are the NN values of the NNth roots of unity (the N zeros of the polynomial (s-1)N(s-1)N). This property is what connects the DFT to convolution and allows efficient algorithms for calculation to be developed Entry 4. They are used so often that the following notation is defined by

with the subscript being omitted if the sequence length is obvious from context. Using this notation, the DFT becomes

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 NN transform values can be calculated exactly (within the accuracy of the computer or calculator used) from the NN 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 (Equation 1) or (Equation 5) in matrix operator form as

or

The orthogonality of the basis function in (Equation 1) shows up in this matrix formulation by the columns of FF being orthogonal to each other as are the rows. This means that FTF=kIFTF=kI, where kk is a scalar constant, and, therefore, FT=kF-1FT=kF-1. This is called a unitary operator.

The definition of the DFT in (Equation 1) emphasizes the fact that each of the NN DFT values are the sum of NN products. The matrix formulation in (Equation 6) has two interpretations. Each kk-th DFT term is the inner product of two vectors, kk-th row of FF and xx; or, the DFT vector, CC is a weighted sum of the NN columns of FF with weights being the elements of the signal vector xx. A third view of the DFT is the operator view which is simply the single matrix equation (Equation 7).

It is instructive at this point to write a computer program to calculate the DFT of a signal. In Matlab Entry 18, 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

to explicitly calculate the real and imaginary part of C(k)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)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 Entry 9. The independent index variable nn of the signal x(n)x(n) is an integer, but it is usually interpreted as time or, occasionally, as distance. The independent index variable kk of the DFT C(k)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

Although the finite length signal x(n)x(n) is defined only over the interval {0≤n≤(N-1)}{0≤n≤(N-1)}, the IDFT of C(k)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)x(n) to -∞-∞ and +∞+∞ and work with this new signal. A second more general way is evaluate all indices nn and kk modulo NN. Rather than considering the periodic extension of x(n)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-1N-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 NN is a more general definition and can be better utilized to develop efficient algorithms for calculating the DFT Entry 4.

Since the indices are evaluated only over the basic interval, any values could be assigned x(n)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 Entry 20. An interesting possibility is to artificially create a length 2N2N sequence by appending x(-n)x(-n) to the end of x(n)x(n). This would remove the discontinuities of periodic extensions of this new length 2N2N 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) Entry 15. We will assume the implicit periodic extensions to x(n)x(n) with no special notation unless this characteristic is important, then we will use the notation x˜(n)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

where x(n)x(n) is the perhaps infinitely long input discrete-time signal, h(n)h(n) is the perhaps infinitely long impulse response of the system, and y(n)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

where either all of the indices or independent integer variables are evaluated modulo NN or all of the signals are periodically extended outside their length NN domains.

This cyclic (sometimes called circular) convolution can be expressed as a matrix operation by converting the signal h(n)h(n) into a matrix operator as

The cyclic convolution can then be written in matrix notation as

where XX and YY 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 NN sequence with a length MM sequence yields a length N+M-1N+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.

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 here using the notation that the DFT of a length-NN complex sequence x(n)x(n) is F{x(n)}=C(k)F{x(n)}=C(k).

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 is the only transform over the complex number field that will support convolution. However, if one considers various finite fields or rings, an interesting transform, called the Number Theoretic Transform, can be defined and used because the roots of unity are simply two raised to a powers which is a simple word shift for certain binary number representations Entry 1, Entry 2.

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)δ(n) is defined by