Abstract
The DTFT of a discrete-time signal is a continuous function of the frequency (\( \omega \)), and hence, the relation between \( X\left( {\text{e}^{{j}\omega } } \right) \) and \( x(n) \) is not a computationally convenient representation. However, it is possible to develop an alternative frequency representation called the discrete Fourier transform (DFT) for finite duration sequences. The DFT is a discrete-time sequence with equal spacing in frequency. We first obtain the discrete-time Fourier series (DTFS) expansion of a periodic sequence. Next, we define the DFT of a finite length sequence and consider its properties in detail. We also show that the DTFS represents the DFT of a finite length sequence. Further, evaluation of linear convolution using the DFT is discussed. Finally, some fast Fourier transform (FFT) algorithms for efficient computation of DFT are described.
Access provided by CONRICYT-eBooks. Download chapter PDF
Similar content being viewed by others
Keywords
- Discrete-time Fourier Series (DTFS)
- Linear Convolution
- Finite Length Sequence
- Circular Convolution
- Inverse Discrete Fourier Transform (IDFT)
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
The DTFT of a discrete-time signal is a continuous function of the frequency (\( \omega \)), and hence, the relation between \( x\left( {\text{e}^{{j}\omega } } \right) \) and \( x(n) \) is not a computationally convenient representation. However, it is possible to develop an alternative frequency representation called the discrete Fourier transform (DFT) for finite duration sequences. The DFT is a discrete-time sequence with equal spacing in frequency. We first obtain the discrete-time Fourier series (DTFS) expansion of a periodic sequence. Next, we define the DFT of a finite length sequence and consider its properties in detail. We also show that the DTFS represents the DFT of a finite length sequence. Further, evaluation of linear convolution using the DFT is discussed. Finally, some fast Fourier transform (FFT) algorithms for efficient computation of DFT are described.
4.1 The Discrete-Time Fourier Series
If a sequence x(n) is periodic with period N, then \( x\left( n \right) = x\left( {n + N} \right) \) for all n. In analogy with the Fourier series representation of a continuous periodic signal, we can look for a representation of x(n) in terms of the harmonics corresponding to the fundamental frequency of \( \left( {2\pi /N} \right). \) Hence, we may write x(n) in the form
It can easily be verified from Eq. (4.1a) that x(n) = x(n + N). Also, we know that there are only N distinct values for \( \text{e}^{{j}2\pi kn/N} \) corresponding to k = 0, 1, …, N − 1, these being 1, \( \text{e}^{{j}2\pi n/N} ,\; \ldots , \;\text{e}^{{{j}2\pi k\left( {N - 1} \right)/N}} . \) Hence, we may rewrite Eq. (4.1a) as
It should be noted that the summation could be taken over any N consecutive values of k. Equation (4.1b) is called the discrete-time Fourier series (DTFS) of the periodic sequence \( x\left( n \right) \) and \( a_{k} \) as the Fourier coefficients. We will now obtain the expression for the Fourier coefficients \( a_{k} \). It can easily be shown that \( \left\{ {\text{e}^{{j}2\pi kn/N} } \right\} \) is an orthogonal sequence satisfying the relation
Now, multiplying both sides of Eq. (4.1b) by \( \text{e}^{ - {j}2\pi ln/N} \) and summing over n between 0 and (N − 1), we get
Hence,
It is common to associate the factor (1/N) with \( x\left( n \right) \) rather than \( a_{k} \). This can be done by denoting \( Na_{k} \) by \( X\left( k \right) \); in such a case, we have
where the Fourier coefficients \( X\left( k \right) \) are given by
It is easily seen that \( X\left( {k + N} \right) = X\left( k \right) \) that is, the Fourier coefficient sequence \( X\left( k \right) \), is also periodic of period N. Hence, the spectrum of a signal x(n) that is periodic with period N is also a periodic sequence with the same period. It is also noted that since the Fourier series of a discrete periodic signal is a finite sequence, the series always converges and the Fourier series gives an exact alternate representation of the discrete sequence \( x\left( n \right). \)
4.1.1 Periodic Convolution
In the case of two periodic sequences \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) having the same period N, linear convolution as defined by Eq. (2.38) does not converge. Hence, we define a different form of convolution for periodic signals by the relation
The above convolution is called periodic convolution. It may be observed that \( y\left( n \right) = y\left( {n + N} \right) \), that is, the periodic convolution is itself periodic of period N.
Some important properties of the DTFS are given in Table 4.1. In this table, it is assumed that \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) are periodic sequences having the same period N. The proofs are omitted here, since they are similar to the ones that will be given in Sect. 4.3 for the corresponding properties of the DFT.
Example 4.1
Obtain the DTFS representation of the periodic sequence shown in Fig. 4.1.
Periodic sequence with period N = 5
Solution
The sequence is periodic with period N = 5. Using Eq. (4.5), the DTFS coefficients are computed as
Hence, from Eq. (4.4), the DTFS for x(n) is given by
Example 4.2
Find the Fourier coefficients in DTFS representation of the sequence \( x\left( n \right) = \sin \left( {\frac{5\pi }{4}} \right)n \).
Solution
It is clear that the sequence is periodic with period N = 8. We may rewrite \( x\left( n \right) \) in exponential form as
Hence, the Fourier coefficients are
4.2 The Discrete Fourier Transform
Consider a finite discrete sequence \( x\left( n \right), 0 \le n \le N - 1 \). It is known from Eq. (2.69) that the DTFT of the sequence \( x\left( n \right) \) is given by
where \( X\left( \omega \right) \) is a continuous function of ω in the range \( - \pi \) to \( \pi \) or 0–2 \( \pi . \) When X (ω) is computed at a finite number of values \( \omega_{k} \) that are uniformly spaced, we have
where \( \omega_{k} = \left( {2\pi k/M} \right) \). The number of frequency samples may take any value; however, it is chosen as equal N, the length of the discrete sequence \( x\left( n \right) \). Rewriting \( X\left( {\omega_{k} } \right) \) as \( X\left( k \right) \), the above equation can be written as
Equation (4.7) is called the discrete Fourier transform of the N-point sequence \( x\left( n \right) \). One of the main reasons as to why DFT is used to such a great extent is in view of the existence of fast and efficient algorithms for its computation. These algorithms are called fast Fourier transforms (FFTs). Later, in this chapter we consider two of the FFTs.
Given \( X\left( k \right) \), we now find an expression for \( x\left( n \right) \) in terms of \( X\left( k \right) \). For this purpose, we multiply both sides of Eq. (4.7) by \( e^{j2\pi lk/N} \) to get
Hence,
Using Eq. (4.2), we have
Substituting the above in Eq. (4.8), we get
or
The above equation is called the inverse discrete Fourier transform (IDFT). It is seen that \( X\left( k \right) \) as defined by Eq. (4.7) is periodic with a period N, since \( X\left( k \right) = X\left( {k + N} \right) \); that is, the IDFT operation results in a periodic sequence of which only the first N values corresponding to one period are evaluated. Also, from Eq. (4.9), we see that \( x\left( n \right) = x\left( {n + N} \right) \). In other words, we are replacing in effect the finite sequence \( x\left( n \right) \) by its periodic extension in all the operations that involve DFT and IDFT. In fact, if we now compare Eqs. (4.4) and (4.5) with Eqs. (4.9) and (4.7), we see that the DFT \( X\left( k \right) \) of a finite sequence of length N can be interpreted as the Fourier coefficient in the DFS expansion of its periodic extension \( \widetilde{x}\left( n \right) \).
If we now define
then the DFT and IDFT defined in Eqs. (4.7) and (4.9) can be rewritten as
and
For notational convenience, the above DFT and IDFT equations are denoted as
In the DFT expression, \( W_{N}^{nk} \;{\text{for}}\; 0 \le n,\; k \le N - 1 \), are called the twiddle factors of the DFT. The twiddle factors are periodic and define points on the unit circle in the complex plane. Also, they possess some interesting symmetry properties. Some basic properties of \( W_{N} \) are given below.
-
1.
\( W_{N}^{k} = W_{N}^{{\left( {k + N} \right)}} \)
-
2.
\( W_{N}^{N/4} = j \)
-
3.
\( W_{N}^{N/2} = - 1 \)
-
4.
\( W_{N}^{3N/4} = j \)
-
5.
\( W_{N}^{N/N} = 1 \)
-
6.
\( W_{N}^{kN} = 1 \)
-
7.
\( W_{N}^{kN + r} = W_{N}^{r} \)
-
8.
\( W_{N}^{k + N/2} = - W_{N}^{k} \)
-
9.
\( W_{N}^{2k} = W_{N/2}^{k} \)
-
10.
\( W_{N}^{*} = W_{N}^{ - 1} \)
Example 4.3
Find the twiddle factors for an eight-point DFT.
Solution
For N = 8, \( W_{8}^{k} = \text{e}^{ - {j}2\pi k/8} \). Hence, the twiddle factors are:
Example 4.4
Find the DFT of the sequence \( x(n) = \{ 1,0,1,0\} \).
Solution
Example 4.5
Determine the eight-point DFT of the sequence \( x(n) = \left\{ {1,1,1,1,0,0,1,1} \right\} \).
Solution
Example 4.6
Find the N-point DFT of the signal \( x(n) = b^{n} \).
Solution
Hence,
Example 4.7
A finite duration sequence of length N is given as
Determine the N-point DFT of this sequence.
Solution
Example 4.8
A finite duration sequence \( x\left( n \right) \) of length eight has the DFT \( X\left( k \right) \) as shown in Fig. 4.2. A new sequence \( y\left( n \right) \) of length 16 is defined by
DFT \( X\left( k \right) \) of \( x\left( n \right) \) of Example 4.8
Sketch the DFT \( Y\left( k \right) \) as a function of k.
Solution
The 16-point DFT of y(n) is
Since \( W_{N}^{2k} = W_{N/2}^{k} \), the above reduces to
Thus, the 16-point DFT \( Y\left( k \right) \) contains two copies of the eight-point DFT of \( x\left( n \right) \), and \( Y\left( k \right) \) has a period of 8. The DFT \( Y\left( k \right) \) as a function of k is shown in Fig. 4.3.
DFT \( Y\left( k \right) \) of \( y\left( n \right) \) of Example 4.8
4.2.1 Circular Operations on a Finite Length Sequence
-
Circular Shift
Consider a sequence x(n) of length N, \( 0 \le n \le N - 1 \). For such a sequence \( x\left( n \right) = 0 \) for \( n < 0 \) and \( n > N - 1 \). In such a case, if we shift the sequence by an arbitrary integer m, then the shifted sequence is no longer be defined in the range \( 0 \le n \le N - 1 \). In order to make sure that the shifted sequence always stays in the range \( 0 \le n \le N - 1 \), we define what is known as the circular shift, by the relation
where
This way, any integer n is related to the \( {\text{modulo}}\,N \) as
where \( \gamma \) is an integer and \( \left( n \right)_{N} \) is always such that \( 0 \le n \le N - 1 \). Consequently,
where \( + N \) is used if \( m > 0 \), and \( - N \) is used if \( m < 0 \).
The circular shift for m = 2 is illustrated in Fig. 4.4.
Illustration of circular shift
The sequence \( x_{c} \left( n \right) \) is related to \( x\left( n \right) \) by a circular shift of two samples. The samples of \( x_{c} \left( n \right) \) can be evaluated using \( x_{c} \left( n \right) = x\left( {n - m} \right)_{4} \). Hence,
-
Circular Time Reversal
For a length-N sequence x(n), \( 0 \le n \le N - 1 \), the circular time-reversal sequence is also of length-N sequence given by
-
Circular Convolution
Consider two sequences x(n) and h(n), each of length N. Then, the circular convolution of x(n) and h(n) is defined as the length-N sequence \( y_{c} \left( n \right) \) given by
It is often called as the N-point circular convolution and is denoted by
The circular convolution is also commutative like the linear convolution; that is,
Example 4.9
Find the circular convolution of the three-point sequences \( x\left( n \right) = \left\{ {1,3, - 4} \right\} \) and \( h\left( n \right) = \left\{ { - 2, 1, 2} \right\} \).
Solution
From Eq. (4.17), \( y_{c} \left( n \right) = \sum\nolimits_{m = 0}^{2} {x\left( m \right) h\left( {n - m} \right)_{3} } \).
Hence,
Thus, \( y_{c} \left( n \right) = \left( {0, - 13, - 3} \right) \).
It can also be verified that \( \sum\nolimits_{m = 0}^{2} {h\left( m \right)x\left( {n - m} \right)_{3} } \) leads to the same result, showing that the circular convolution operation is commutative.
-
Circular Correlation:
Consider two complex-valued sequences \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \), each of length N. Then, the circular correlation of \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) is defined as the N-point sequence
where \( x_{2}^{*} \left( n \right) \) is the complex conjugate of \( x_{2} \left( n \right). \)
4.3 Basic Properties of the Discrete Fourier Transform
In this section, we state and prove some properties of the DFT, which play an important role in digital signal processing applications. We will denote an N-point DFT pair x(n) and X(k) by the following notation
-
Linearity:
Consider a sequence \( a_{1} x_{1} \left( n \right) + a_{2} x_{2} \left( n \right) \) that is a linear combination of \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \), each sequence being of length N, where \( a_{1} \) and \( a_{2} \) are arbitrary constants. If the sequences are not of the same length, then the sequence with the lower length is augmented by zeros so that its length is now equal to that of the other sequence. In such a case,
Proof
By the definition of the DFT,
Hence, we can write
-
Time Reversal of a Sequence:
If x(n) and X(k) are an N-point DFT pair, then
Proof
Changing the index from n to m = N − n in the RHS of the above equation, we can rewrite it as
-
Circular Time Shifting:
The DFT of a circularly time-shifted sequence \( x\left( {n - m} \right)_{N} \) is given by \( W_{N}^{km} X\left( k \right) \), that is,
Proof
By the definition of DFT,
Since \( x\left( {n - m} \right)_{N} \; = x\left( {N - m + n} \right), \) we can write the above equation as
-
Circular Frequency Shifting:
If x(n) and X(k) are an N-point DFT pair, then
where \( X\left[ {\left( {k - m} \right)_{N} } \right] \) is a circularly frequency-shifted version of X(k).
Proof
-
Circular Convolution:
The DFT of the circular convolution of two length-N sequences is the product of their N-point DFTs, i.e.,
Proof
Let \( y_{c} \left( n \right) \) represent the circular convolution of the sequences x1(n) and x2(n), i.e.,
Then, the DFT of \( y_{c} \left( n \right) \) is
By interchanging the order of the summation, we obtain
Substituting \( \left( {n - l} \right) = m \), where m is integer with \( 0 \le m \le N - 1, \) we get
-
Circular Correlation:
The DFT of the circular correlation of two complex-valued N-point sequences \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) is given by \( X_{1} \left( k \right)X_{2}^{*} \left( k \right), \) i.e.,
Proof
From Eq. (4.20), we know that
Also, the circular convolution of two sequences \( x_{1} \left( m \right) \) and \( x_{2} \left( m \right) \) is given by
Comparing Eqs. (4.27a) and (4.27b), we see that \( r_{{x_{1} x_{2} }} \left( m \right) \) can be considered as the circular convolution of \( x_{1} \left( m \right) \) and \( x_{2}^{*} \left( { - m} \right)_{N} \). Hence, \( {\text{DFT}}\left[ {r_{{x_{1} x_{2} }} \left( m \right)} \right] = \left[ {{\text{DFT}}\left\{ {x_{1} \left( m \right)} \right\}} \right]\left[ {{\text{DFT}}\left\{ {x_{2}^{*} \left( { - m} \right)_{N} } \right\}} \right] \). It can be shown that (see Eq. (4.41)) \( {\text{DFT}}\{ x_{2}^{*} \left( { - m} \right)_{N} \} = X_{2}^{*} \left( k \right) \). Thus,
If \( x_{1} \left( n \right) = x_{2} \left( n \right) = x\left( n \right) \), then
-
Parseval’s Theorem:
If \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) are two complex-valued N-point sequences with DFTs \( X_{1} \left( k \right) \) and \( X_{2} \left( k \right) \), then
Proof
From Eq. (4.28), we have \( R_{{x_{1} x_{2} }} \left( k \right) = X_{1} \left( k \right) X_{2}^{*} \left( k \right) \). Hence,
Evaluating the above at \( m = 0 \) gives
Hence,
If \( x_{1} \left( n \right) = x_{2} \left( n \right) = x\left( n \right) \), then we have
The above expression gives a relationship between the energy in a finite duration sequence to the power in the frequency components.
-
Multiplication of two Sequences:
The DFT of the product of two sequences \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \), each of length N, is given by the circular convolution of their DFTs \( X_{1} \left( k \right) \) and \( X_{2} \left( k \right) \) divided by N, i.e.,
This property is dual of the circular convolution property and is left as an exercise for the student.
The above properties are summarized in Table 4.2.
4.4 Symmetry Relations of DFT
4.4.1 Symmetry Relations of DFT of Complex-Valued Sequences
Consider a complex-valued sequence x(n), which is expressed as
The DFT of x(n) is given by
If
then
and
Similarly, we can show that
and
Let us now consider a length-N complex conjugate sequence x*(n). Taking the complex conjugate on both sides of Eq. (4.11), we get
which can be rewritten as
Hence,
Therefore,
Now, we find the DFT of \( x^{*} \left( {\left( { - n} \right)_{N} } \right) \) as follows:
Replacing n by (N − n) in Eq. (4.38), we have
It is seen from Eq. (4.40a) and Eq. (4.40b) that
Since a complex sequence \( x\left( n \right) \) can be decomposed into a sum of its real and imaginary parts as
where
and
it can be easily shown that the DFTs of the real and imaginary parts of complex sequence are given by
and
A complex sequence \( x\left( n \right) \) can be represented as the sum of a circular conjugate symmetric sequence \( x_{e} \left( n \right) \) and a circular conjugate antisymmetric sequence \( x_{o} \left( n \right) \):
where
and
Then, the DFTs of \( x_{e} \left( n \right) \) and \( x_{0} \left( n \right) \) can be easily obtained, using Eq. (4.39), as
and
The symmetry properties of the DFT of a complex sequence are summarized in Table 4.3.
4.4.2 Symmetry Relations of DFT of Real-Valued Sequences
For a real-valued sequence \( x\left( n \right) \), \( x_{I} \left( n \right) = 0 \). Hence, from Eq. (4.34), we get
From symmetry,
Hence, we have the symmetry relation
Also, from Eqs. (4.36a), we have
Hence,
Thus,
Similarly, starting with Eqs. (4.36b), we can show that
From the above relations, we see that the magnitude of \( X\left( k \right) \) and \( X\left( {\left( { - k} \right)_{N} } \right) \) is equal and that the phase angle of \( X\left( k \right) \) is negative of that of the phase angle of \( X\left( {\left( { - k} \right)_{N} } \right) \), i.e.,
and
If \( x\left( n \right) \) is real and even, that is,
then, from Eq. (4.36a) and Eq. (4.36b), we see that \( X_{I} \left( k \right) = 0 \) and that the N-point DFT reduces to
Hence, the DFT of a real finite even sequence is itself real and even. Furthermore, the IDFT reduces to
If \( x\left( n \right) \) is real and odd, that is,
then, from Eq. (4.35a) and (4.35b), we see that \( X_{R} \left( k \right) = 0 \) and that the N-point DFT reduces to
Hence, the DFT of a real finite odd sequence is purely imaginary and odd. Furthermore, the IDFT reduces to
The symmetry relations of DFT of a real-valued sequence are summarized in Table 4.4.
4.4.3 DFTs of Two Real Sequences from a Single N-Point DFT
Equations (4.44a) and (4.44b) can be used to advantage in finding the DFTs of two real sequences of length N. Suppose \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) are two real N-point sequences with DFTs \( X_{1} \left( k \right) \) and \( X_{2} \left( k \right). \) Let us define a complex sequence \( x\left( n \right) \) by
Using Eqs. (4.44a) and (4.44b), we may write the DFTs of the two real sequences as
Example 4.10
Find the DFTs of the sequences \( x_{1} \left( n \right) = \left( {1, 2,0,1} \right) \) and \( x_{2} \left( n \right) = \left( {1,0,1,0} \right) \) using a single four-point DFT.
Solution
Hence,
Thus,
Hence,
Substituting the values of \( X\left( k \right) \) and \( X^{*} \left( {N - k} \right) \) in Eqs. (4.56a) and (4.56b), we get
4.5 Computation of Circular Convolution
4.5.1 Circulant Matrix Method
The circular convolution defined by Eq. (4.17) can be written in a matrix form as
The (N × N) matrix on the RHS of Eq. (4.57) is called the circular convolution matrix or circulant matrix and denoted by \( C_{x} \). It may be observed that the first column corresponds to the elements of the sequence \( x\left( n \right) \), and the rest of the columns are derived from the previous ones in a very simple way.
Example 4.11
Find the circular convolution of the sequences considered in Example 4.9, namely \( x\left( n \right) = \left( {1,3, - 4,} \right) \) and \( h\left( n \right) = \left( { - 2,1,2} \right). \)
Solution
The circular convolution matrix C x is given by
Then, the circular convolution of \( x\left( n \right) \) and \( h\left( n \right) \) is given by
Hence, \( y_{c} \left( n \right) = \left( {0, - 13,13} \right). \)
4.5.2 Graphical Method
Evaluation of the circular convolution sum at any sample n consists of the following operations:
-
(i)
The sequences \( x\left( n \right) \) and \( h\left( n \right) \) are marked on two concentric circles with one sequence on the inner circle in the clockwise direction and the other on the outer circle in a counter clockwise direction as various points, with equal spacing. For \( n = 0 \), \( y_{c} \left( 0 \right) \) is obtained by multiplying the two sequences point by point and summing the products.
-
(ii)
Keeping the outer circle stationary, rotate the inner in counterclockwise direction by one sample, multiply the two sequences point by point, and sum the products. This gives \( y_{c} \left( 1 \right) \).
-
(iii)
The procedure is continued to find \( y_{c} \left( n \right) \) for other values of \( n \).
The following example illustrates the above procedure:
Example 4.12
Find the circular convolution of the three-point sequences of Example 4.11 with \( x\left( n \right) = \left( {1,3, - 4} \right) \) and \( h\left( n \right) = \left( { - 2,1,2} \right) \).
Solution
Hence,
4.5.3 DFT Approach
We may obtain the circular convolution \( y_{c} \left( n \right) \) of two N-point sequences using the relation given by Eq. (4.25). We first compute the DFTs \( X_{1} \left( k \right) \) and \( X_{2} \left( k \right) \) of the two sequences and then multiply them to get \( Y_{c} \left( k \right) = X_{1} \left( k \right)X_{2} \left( k \right) \), the DFT of the circular convolution. We then perform the IDFT on \( Y_{c} \left( k \right) \) to obtain the circular convolution \( y_{c} \left( n \right) \). In the next section, we will see how this approach can be used to evaluate linear convolution of two sequences.
Example 4.13
Obtain the circular convolution of the sequences \( x_{1} \left( n \right) = \left( {1, 2,0,1} \right) \) and \( x_{2} \left( n \right) = \left( {1,0,1,0} \right) \) using the DFT approach.
Solution
We have already found the DFTs for these two sequences in Example 4.10. These are given by
Hence,
Using Eq. (4.12), we now compute the IDFT of the above to obtain the circular convolution \( y_{c} \left( n \right) \).
which gives
4.6 Linear Convolution Using DFT
Linear convolution is an important operation in signal processing applications since it can be used to obtain the response of a linear filter for arbitrary input, once the impulse response of the filter is known. There are efficient algorithms called fast Fourier transforms, two of which will be discussed in the next section, for practical implementation of an N-point DFT. Hence, it is of importance to find methods to implement the linear convolution using the DFT.
4.6.1 Linear Convolution of Two Finite Length Sequences
Consider two sequences \( x\left( n \right) \) and \( h\left( n \right) \) of lengths L1 and L2, respectively. The linear convolution of these two sequences is a sequence of length L1 + L2−1. Circular convolution cannot be directly used on these two sequences to achieve linear convolution. Now, to obtain linear convolution using circular convolution, we generate two new sequences \( x^{\prime}\left( n \right) \) and \( h^{\prime}\left( n \right) \), each of length L1 + L2−1 = L by padding \( x\left( n \right) \) with (L2 − 1) zeros and \( h\left( n \right) \) with (L1 − 1) zeros. Thus,
The linear convolution of \( x^{\prime}\left( n \right) \) and \( h^{\prime}\left( n \right) \) is given by
The above expression can be thought of as a circular convolution of the two padded sequences \( x^{\prime}\left( n \right) \) and \( h^{\prime}\left( n \right) \); hence, we can use any of the methods described in Sect. 4.5 to evaluate it.
Example 4.14
Find the linear convolution of the sequences \( x\left( n \right) = \left( {1,2,3,1} \right) \) and \( x\left( n \right) = \left( {1,1,1} \right). \)
Solution
The two sequences \( x\left( n \right) \) and \( h\left( n \right) \) are of lengths 4 and 3, respectively. By appropriately padding the two sequences by zeros, we obtain the padded sequences \( x^{\prime}\left( n \right) = \left( {1,2,3,1,0,0} \right) \) and \( h^{\prime}\left( n \right) = (1,1,1,0,0,0), \) each of length L = 6. We may now calculate the circular convolution \( y_{c} \left( n \right) \) of \( x^{\prime}\left( n \right) \) and \( h^{\prime}\left( n \right) \) using the circulant matrix Eq. (4.57)
Thus, \( y_{c} \left( n \right) = \left( {1,3,6,6,4,1} \right) \), and therefore, the linear convolution
Instead of using the circulant matrix, we could have used the DFT approach to find the circular convolution. In this case, we would first find the L = (L1 + L2−1)-point DFTs \( X^{\prime}\left( k \right) \) and \( H^{\prime}\left( k \right) \) of \( x^{\prime}\left( n \right) \) and \( h^{\prime}\left( n \right) \). Then, the L-point IDFT of the product \( X^{\prime}\left( k \right)H^{\prime}\left( k \right) \) would yield the linear convolution of \( x(n) \) and \( h(n) \).
The following MATLAB fragments illustrate as to how to obtain the linear convolution using the DFT:
For the above example,
-
x=[1 2 3 1 0 0]; % sequence \( x(n) \)
-
h=[1 1 1 0 0 0];% sequence \( h(n) \)
-
L=length(x)+length(h)-1;%length of convolution sequence
-
XE=fft(x,L); % DFT of sequence \( x(n) \) with zero padding
-
HE=fft(h,L); % DFT of sequence \( h(n) \) with zero padding
-
yl=ifft(XE.*HE); % linear convolution of sequences \( x(n) \) and \( h(n) \)
-
After execution of the above MATLAB commands, the linear convolution of \( x(n) \) and \( h(n) \) is given by
-
\( y_{l} (n) = x(n) * h(n) \)={1, 3, 6, 6, 4, 1}.
4.6.2 Linear Convolution of a Finite Length Sequence with a Long Duration Sequence
There are two methods for the evaluation of the linear convolution using the DFT, called the overlap-add and the overlap-save, when one sequence is of finite length and the other is of infinite length or much greater than the length of the finite length sequence.
-
(a)
Overlap-Add Method
Let \( x\left( n \right) \) be a sequence of long duration and \( h\left( n \right) \) of finite length \( L_{2} \). Let the sequence \( x\left( n \right) \) be divided into a set of subsequences, each having a finite length L, and let each subsequence be padded with L2−1 zeros to make its length equal to L + L2−1. Then, we have
Also, the sequence \( h\left( n \right) \) is padded with L − 1 zeros to form the sequence \( h^{\prime}\left( n \right) \). Each of the subsequences is now convolved with \( h^{\prime}\left( n \right) \) of length L + L2−1. Since each subsequence is terminated with L2 − 1 zeros, the last L2 − 1 points from each subsequence convolution output are to be overlapped and added to the first L2 − 1 points of the succeeding subsequence convolution output. Hence, this procedure is called the overlap-add method. The following example illustrates this method.
Example 4.15
If the impulse response of a filter is \( h(n) = \left\{ {1,0,1} \right\} \), find its output \( y(n) = x(n) * h(n) \) for the input sequence \( x(n) = \left\{ {3, - 1,0,1,2,1,0,1,2} \right\} \), by using overlap-add method.
Solution
Let each subblock of the data be of length 3. Since L2 = 3, two zeros are added to bring the length of each subblock to 5. Two zeros are added to \( h\left( n \right) \) so that \( h^{\prime}\left( n \right) \) is also of length 5. Hence, the sub sequences are
and
Then, the circular convolutions of the subsequences with \( h^{\prime}\left( n \right) \) are given by
Hence, the linear convolution of \( x\left( n \right) \) and \( h\left( n \right) \) is given by
The above process is illustrated in Fig. 4.5.
a Original signal \( x\left( n \right) \), b subblocks of \( x\left( n \right) \), c circular convolution of the subblocks of \( x\left( n \right) \) and \( h^{\prime}\left( n \right) \), and d linear convolution of \( x\left( n \right) \) and \( h\left( n \right) \)
The above procedure can be implemented by using the MATLAB command fftfilt.
\( {\text{h}} = \left[ {1\,\,0\,\,1\,\,0\,\,0} \right]; \)
\( {\text{x}} = \left[ {3\,\, - 1\,\,0\,\,1\,\,2\,\,1\,\,0\,\,1\,\,2\,\,0\,\,0} \right]; \)
\( {\text{y}} = {\text{fftfilt}}\left( {{\text{h}},{\text{x}}} \right); \)
Thus after the execution of the above MATLAB statements, we get \( y_{l} (n) \) as
-
(b)
Overlap-Save Method
In this method, the sequence \( x\left( n \right) \) is divided into a set of overlapping subsequences, each having a finite length L + L2−1. Each subsequence contains the last L2 − 1 samples of the previous subsequence, followed by the next L samples of \( x\left( n \right) \). The first L2 − 1 samples of the first subsequence are set to zero. Hence, the subsequences are
and so on. Now, the length of the sequence \( h\left( n \right) \) is increased to L + L2 − 1 by padding it with L − 1 zeros to form the sequence \( h^{\prime}\left( n \right) \). Then, each of the subsequences is convolved with \( h^{\prime}\left( n \right) \). The first L2 − 1 points of the circular convolution of each of the subsequences with \( h^{\prime}\left( n \right) \) do not agree with the linear convolution output of each subsequence with \( h^{\prime}\left( n \right) \) due to aliasing, and the remaining L points are in agreement with the linear convolution output. Hence, the first L2 − 1 points of the circular convolution of each subsequence with \( h^{\prime}\left( n \right) \) output are to be discarded and the remaining L points from each subsequence convolution output are to be abutted to obtain the linear convolution output of \( x\left( n \right) \) and \( h\left( n \right) \). The following example illustrates this method:
Example 4.16
Find the filter output \( y(n) = x(n) * h(n) \) for the input \( x\left( n \right) \) and the impulse response \( h\left( n \right) \) of Example 4.15.
Solution
The subsequences of \( x\left( n \right) \) are
and
Then, the circular convolution of the subsequences with h(n) is given by
Hence, the linear convolution of x(n) and h(n) is given by
This process is illustrated in Fig. 4.6a, b.
a Original input \( x\left( n \right) \) and subsections of \( x\left( n \right) \) and b circular convolution of subsections of \( x\left( n \right) \) and \( h^{\prime}\left( n \right), \) and the linear convolution of \( x\left( n \right) \) and \( h\left( n \right) \)
4.7 Fast Fourier Transform
It is evident from Eqs. (4.11) that a direct evaluation of each value of \( X\left( k \right) \) requires N complex multiplications and \( \left( {N - 1} \right) \) complex additions. As such, \( N^{2} \) complex multiplications and \( N\left( {N - 1} \right) \) complex additions are necessary for the computation of an N-point DFT. Consequently, for large \( N \), the computational complexity in terms of the arithmetic operations is high in direct evaluation of the DFT. Therefore, a number of efficient algorithms have been developed for the computation of the DFT. These efficient algorithms collectively have become known fast Fourier transforms. The FFT algorithms decompose successively the computation of the discrete Fourier transform of a sequence of length N into smaller and smaller discrete Fourier transforms. The two most basic FFT algorithms are the decimation-in-time and decimation-in frequency [1, 2], and these are considered in the following sections.
4.7.1 Decimation-in-Time FFT Algorithm with Radix-2
The decimation-in-time (DIT) is the process that decomposes the input sequence successively into smaller and smaller subsequences. Here, the radix-2 means the number of output points N can be expressed as a power of 2; that is, \( N = 2^{\nu } \), where ν is an integer. Let the input sequence be decomposed into an even sequence \( g_{1} \left( n \right) \) and an odd sequence \( g_{2} \left( n \right) \) as
We know from Eq. (4.11) that
Substituting Eqs. (4.62) and (4.63) in (4.64), we get
Using \( W_{N}^{2} = W_{N/2} \) in Eq. (4.65) yields
The RHS may be identified as the sum of two (N/2)-point DFTs, \( G_{1} \left( k \right) \) and \( G_{2} \left( k \right) \) of the even and odd sequences \( g_{1} \left( n \right) \) and \( g_{2} \left( n \right) \):
Hence, \( X\left( k \right) \) in Eq. (4.66) can be written as
Also, since \( G_{1} \left( k \right) \) and \( G_{2} \left( k \right) \) are periodic with a period of (\( N/2) \), \( G_{1} \left( {k + N/2} \right) = G_{1} \left( k \right) \) and \( G_{2} \left( {k + N/2} \right) = G_{2} \left( k \right) \), and the twiddle constant \( W_{N}^{k + N/2} = - W_{N}^{k} \). Hence, Eq. (4.69) can be written as
Repeating the process for each of the sequences \( g_{1} (n) \) and \( g_{2} (n) \), \( g_{1} (n) \) yields two \( \left( {N/4} \right) \)-point sequences
and \( g_{2} (n) \) yields
and their DFTs satisfy
This process can be continued until we are left with only two-point transforms. For example, for N = 4, Eqs. (4.70a) and (4.70b) become
Equation (4.73) can be represented by the flow graph as shown in Fig. 4.7. This is usually referred to as the butterfly diagram for four-point DFT. In the first stage, two 2-point DFTs and, in the second stage, one 4-point DFT are computed.
Decomposition of a four-point DFT using DIT
For N = 8, Eqs. (4.70a) and (4.70b) become
The computation of an eight-point DFT is performed in three stages as shown in Fig. 4.8.
Decomposition of an eight-point DFT using DIT
It is observed from the flow graph that in the first stage, four 2-point DFTs, in the second stage, two 4-point DFTs, and finally, in the third stage, one 8-point DFT are computed. Also, the number of complex multiplications carried out at each stage is equal to 4 = N/2, and the number of additions performed is N. Hence, the total number of complex multiplications and additions in computing all the 8 samples is 12 and 24, respectively. Following the same argument, it can be observed that in the general case of \( N = 2^{\nu } \), the number of stages of computation will be \( \nu = \log_{2} N \); hence, the total number of complex multiplications and additions needed in computing all the N DFT samples is \( \left( {N/2} \right)\log_{2} N \), and the number of complex additions is \( N\log_{2} N \).
Example 4.17
Find the four-point FFT of \( x(n) = \left\{ {1,0,1,1} \right\} \) using the decimation-in-time algorithm.
Solution
With N = 4, the two twiddle factors are
Since it is a four-point DFT, the DIT flow graph consists of two stages as shown in Fig. 4.9. The outputs of the first and second stages are computed as follows:
Decomposition of the four-point DFT of Example 4.17 using the DIT algorithm
-
Stage 1
where the sequence \( x_{1} \left( n \right) \) represents the intermediate output after the first stage and becomes the input to the second (final) stage.
-
Stage 2
Example 4.18
Consider an input data string of \( x\left( n \right) = \left( {0,1,2,3} \right) \). Draw the butterfly diagram of the FFT showing the input, intermediate outputs, and the final output to compute the DFT of \( x\left( n \right) \).
Solution
By computing the outputs of the first and second stages as was done in the previous example, the required butterfly diagram is shown in Fig. 4.10.
Decomposition of the four-point DFT of Example 4.18 using the DIT algorithm
Example 4.19
Find the eight-point FFT of \( x(n) = \left\{ {1,0,1,1,1,1,1,0} \right\} \) using the DIT algorithm.
Solution
With N = 8, the four twiddle factors are
Since it is an eight-point DFT with radix-2, the DIT flow graph consists of three stages as shown in Fig. 4.11. The outputs of the three stages are computed as follows:
Decomposition of the eight-point DFT of Example 4.19 using the DIT algorithm
-
Stage 1
where the sequence \( x_{1} \left( n \right) \) represents the intermediate output after the first stage and becomes the input to the second stage.
-
Stage 2
where the second-stage output sequence \( x_{2} \left( n \right) \) becomes the input sequence to the final stage.
-
Stage 3
Example 4.20
Find the 16-point FFT of the sequence \( x(n) = \left\{ {1,0,1,1,0,1,1,0,1,0,0,1,1,1,1,0} \right\} \) using the DIT algorithm.
Solution
With N = 16, eight twiddle factors need to be calculated; these are
Since it is a 16-point DFT with radix-2, the DIT flow graph consists of four stages as shown in Fig. 4.12. The outputs of the four stages are computed as follows:
Decomposition of the 16-point DFT of Example 4.20 using the DIT algorithm
-
Stage 1
where the sequence \( x_{1} \left( n \right) \) represents the intermediate output after the first iteration and becomes the input to the second stage.
-
Stage 2
where the intermediate second-stage output sequence \( x_{2} \left( n \right) \) becomes the input sequence to the next one.
-
Stage 3
where the intermediate third-stage output sequence \( x_{3} \left( n \right) \) becomes the input sequence to the final stage.
-
Stage 4
4.7.2 In-Place Computation
In the implementation of the DIT FFT algorithm, only one complex array of N storage registers is physically necessary, since the complex numbers resulting from the mth stage can be stored in the same registers that had stored the complex numbers resulting from the (m − 1)th stage, once the output variables of the mth stage have been determined from the output numbers of the (m − 1)th stage. This type of computation is referred to as in-place computation. Thus, for in-place computation in the DIT algorithm in which the DFT samples appear in the natural order (i.e., \( X\left( k \right) \), k = 0, 1, …, N − 1), the input sequence samples are to be stored in index bit-reversed order. If \( x\left( {b_{2} b_{1} b_{0} } \right) \) represents the sample \( x\left( n \right) \) in the index bit-reversed binary form, then the sample \( x\left( {b_{2} b_{1} b_{0} } \right) \) would appear in the location of the sample \( x\left( {b_{0} b_{1} b_{2} } \right) \) of the input sequence to the DIT algorithm. For an eight-point DFT, the bit-reversal process is shown in Table 4.5.
4.7.3 Decimation-in-Frequency FFT Algorithm with Radix-2
The basic idea in the decimation-in-time (DIT) algorithm was to decompose the input sequence successively into smaller and smaller subsequences. In the case of decimation-in-frequency (DIF) algorithm, we decompose the N-point DFT sequence \( X\left( k \right) \) successively into smaller and smaller subsequences. Consider an input sequence x(n), and divide it into two halves. Then, the DFT of x(n) can be written as
The above equation can be rewritten as
Since \( W_{N}^{Nk/2} = \left( { - 1} \right)^{k} \), Eq. (4.75b) becomes
Now, splitting \( X\left( k \right) \) into even-indexed and odd-indexed samples, Eq. (4.75c) can be written as consisting of two (N/2)-point DFTs for k = 0,1, …, (N/2)−1.
Let
Then, the even- and odd-indexed \( X\left( k \right) \)’s are found from the (N/2)-point transforms of \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) as
and
Repeating the process for each of the sequences \( x_{1} \left( n \right) \) and \( x_{2} \left( n \right) \) yields the two (N/4)-point sequences
and \( x_{2} (n) \) yields
Then, the even- and odd-indexed \( X\left( k \right) \)’s are found from the (N/4)-point transforms of \( x_{11} \left( n \right), x_{12} \left( n \right), x_{21} \left( n \right) \) and \( x_{22} \left( n \right) \) as
The process is to be continued until they reduce to two-point transforms.
For example, for N = 4, the two twiddle factors needed are \( W_{4}^{0} = 1 \) and \( W_{4}^{1} = - j \). The DIF flow graph for a four-point DFT contains two stages as shown in Fig. 4.13. The outputs of the two stages are computed as follows:
Decomposition of a four-point DFT using the DIF algorithm
-
Stage 1
where \( x_{1} \left( 0 \right),\;x_{1} \left( 1 \right),\;x_{1} \left( 2 \right) \) and \( x_{1} \left( 3 \right) \) represent the intermediate output sequence after the first stage, which become the input to the second stage.
-
Stage 2
For N = 8, the decomposition of an 8-point DFT into two 4-point DFTS with DIF algorithm is shown in Fig. 4.14.
Decomposition of an eight-point DFT using the DIF algorithm decimation-in-frequency
Example 4.21
Find the DFT of the sequence \( x\left( n \right) = \left( {1,2,3,4} \right) \) using the DIF algorithm.
Solution
The two twiddle factors needed are \( W_{4}^{0} = 1 \) and \( W_{4}^{1} = - j \).
The DIF flow graph for four-point DFT consists of two stages as shown in Fig. 4.15. The outputs of the two stages are computed as follows:
Flow graph for the four-point FFT of Example 4.21 using the DIF algorithm
-
Stage 1
where \( x_{1} \left( 0 \right),\;x_{1} \left( 1 \right),\;x_{1} \left( 2 \right) \) and \( x_{1} \left( 3 \right) \) represent the intermediate output sequence after the first stage, which become the input to the second stage.
-
Stage 2
Example 4.22
Find the DFT of a sequence \( x\left( n \right) = \left( {1,1,1,1,1,1,0,0} \right) \) using the DIF algorithm.
Solution
With N = 8, the four twiddle factors needed are
-
Stage 1
where \( x_{1} \left( 0 \right),x_{1} \left( 1 \right), \ldots ,x_{1} \left( 7 \right) \) represent the intermediate output sequence after the first stage, which become the input to the second stage.
-
Stage 2
where \( x_{2} \left( 0 \right),\;x_{2} \left( 1 \right),\; \ldots ,\;x_{2} \left( 7 \right) \) represent the intermediate output sequence after the second stage, which become the input to the final stage.
-
Stage 3
We now use the notation of X’s to represent the final output sequence. The values \( X\left( 0 \right), \;X\left( 1 \right),\; \ldots ,\;X\left( 7 \right) \) form the output sequence.
The DIF flow graph for eight-point DFT consists of three stages as shown in Fig. 4.16. The outputs of the three stages are computed in Fig. 4.16.
Flow graph of the eight-point FFT for the Example 4.22 using DIF algorithm
It should be noted that flow graph representing the DIF FFT may be considered as an in-place computation, just as in the case of the DIT FFT. Further, it should be noted that the input sequence \( x\left( n \right) \) is in order, while the output sequence \( X\left( k \right) \) is in bit-reversed order. The number of multiplications and additions for computing an N-point by DIF FFT is the same as in the case of the DIT FFT, namely \( \left( {N/2} \right)\log_{2} N \) and \( N\log_{2} N \), respectively.
It is worth pointing out that the flow graphs of DIT FFT and DIF FFT algorithms are transposes of one another.
4.7.4 Radix-4 DIF FFT Algorithm
If \( N = 2^{2\nu } \), then we can use radix-4 algorithms rather than radix-2 algorithms, and this gives us a reduction in the number of multiplications to be performed. Here, we will consider the radix-4 DIF algorithm. Radix-4 DIT algorithm can be developed in a way similar to that of the radix-2 DIT algorithm.
Consider a sequence \( x\left( n \right) \), and divide it into four parts so that the DFT of \( x\left( n \right) \) can be written as
The above equation can be rewritten as
Substituting
in the above equation, we get
Since the twiddle factor depends on N, the above relation is not N/4-point DFT. To represent it as an N/4-point DFT, the DFT sequence is divided into four N/4-point subsequences, \( X\left( {4k} \right) \), \( X\left( {4k + 1} \right) \), \( X\left( {4k + 2} \right) \) and \( X\left( {4k + 3} \right) \) for \( k = 0, 1, \ldots \left( {\frac{N}{4} - 1} \right) \). Thus, the DIF FFT with radix-4 can be represented as
The following example illustrates a 16-point radix-4 FFT using the DIF procedure.
Example 4.23
Find the DFT of a sequence \( x\left( n \right) = \left\{ {1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1} \right\} \) using the radix-4 DIF algorithm.
Solution
The twiddle factors for 16-point radix-4 FFT are
The outputs of the two stages are computed as follows:
-
Stage 1
-
Stage 2
The flow graph for the 16-point radix-4 DIF FFT is shown in Fig. 4.17. The (±) j and −1 are not shown in stage 2 for the four-point butterfly of the flow graph.
Sixteen-point DFT of Example 4.23 using radix-4 DIF algorithm
4.8 Comparison of Computational Complexity
As mentioned earlier, the number of complex multiplications required in the radix-2 FFT of an N-point sequence is \( \left( {N/2} \right)\log_{2} N \) while the number of complex additions needed is \( N\log_{2} N \).
In the radix-4 FFT of an N-point sequence, there are \( \log_{4} N = \left( {1/2} \right)\log_{2} N \) stages and (N/4) butterflies per stage. Each radix-4 butterfly requires three complex multiplications and eight complex additions. Thus, it requires \( \left( {3N/4} \right)\left( {1/2} \right)\log_{2} N = \left( {3N/8} \right)\log_{2} N \) complex multiplications and \( \left( {8N/4} \right)\left( {1/2} \right)\log_{2} N = N\log_{2} N \) complex additions.
A comparison of the computational complexity in terms of the number of complex multiplications needed to compute the DFT of an N-point sequence directly is compared to that required using radix-2 and radix-4 FFTs as given in Table 4.6.
4.9 DFT Computation Using the Goertzel Algorithm and the Chirp Transform
While the fast Fourier transform’s various incarnations have gained considerable popularity, careful selection of an appropriate algorithm for computing the DFT in practice need not be limited to choosing between these so-called fast implementations. In this section, it is focused on two other techniques, namely the Goertzel algorithm and the chirp transform for computing the DFT.
4.9.1 The Goertzel Algorithm
The Goertzel algorithm [3] uses the periodicity of the sequence \( W_{N}^{nk} \) to reduce the computational complexity. From the definition of DFT, it is known that
Equation (4.88a) can be rewritten as
If a sequence \( y_{k} \left( n \right) \) is defined as
implying that passing a signal \( x\left( n \right) \) through an LTI filter with impulse response \( h\left( n \right) = W_{N}^{ - nk} u\left( n \right) \) and evaluating the result, \( y_{k} \left( n \right) \) at n = N will give the corresponding N-point DFT coefficient \( X\left( k \right) = y_{k} \left( n \right) \).
Representing the filter by its z-transform, we obtain
having a pole on the unit circle at the frequency \( \omega_{k} = \frac{2\pi k}{N} \). Hence, the DFT can be computed by passing the block of input data into a parallel bank of N filters each filter having a pole at the frequency of the corresponding DFT. The DFT can be computed by using the following difference equation corresponding to the filter expressed by Eq. (4.89)
The inherent complex multiplications and addition in Eq. (4.90a) can be avoided by using the following two-pole filter having complex conjugate pole pairs equivalent to the filtering operation represented by Eq. (4.89).
where \( = H_{1k} \left( z \right)H_{2k} \left( z \right) \)
From \( H_{1k} \left( z \right) \) and \( H_{2k} \left( z \right) \), we obtain the following difference equations
with initial conditions \( v_{k} \left( { - 1} \right) = v_{k} \left( { - 2} \right) = 0 \).
The Goertzel algorithm evaluates X(k) at any M values of k instead of evaluating at all N values of k. Hence, it is more efficient than FFT [4] for computing DFT, when \( M \le \log_{2} \left( N \right) \).
Example 4.24
Considering the sequence \( x\left( n \right) = \left\{ {1,2,1,1} \right\} \), compute DFT coefficient X(1) and the corresponding spectral amplitude at the frequency bin k = 1 using the Goertzel algorithm.
Solution
We have k = 1, N = 4, \( x\left( 0 \right) = 1,\;x\left( 1 \right) = 2,\;x\left( 2 \right) = 1,\;x\left( 3 \right) = 1. \)
For n = 0, 1, …, 4
Then, \( X\left( 1 \right) = y_{1} \left( 4 \right) \quad \left| {X\left( 1 \right)} \right|^{2} = v_{1}^{2} \left( 4 \right) + v_{1}^{2} \left( 3 \right) \)
4.9.2 The Chirp Transform Algorithm
The chirp transform algorithm [5] is also based on expressing DFT as a convolution. As it can be used to compute the Fourier transform of any set of equally spaced samples on the unit circle, it is more flexible than the FFT.
If it is desired to compute the values of the z-transform of x(n) at a set of points {zk}, then,
Equation (4.92a) can be rewritten as
where
Equation (4.92b) can be rewritten as,
For the DFT computation, \( \omega_{0} = 0 , \;\Delta \omega = \frac{2\pi }{N} \) and M = N.
Hence, Eq. (4.92d) becomes
Using the identity
Equation (4.93b) can be written as
where
For notation convenience, replacing n by k and k by n in Eq. (4.93c), it can be rewritten as
Equation (4.94a) can also be expressed as
implying that \( X\left( {e^{{j\omega_{n} }} } \right) \) is the convolution of the sequence g(n) with the sequence \( W_{N}^{{\frac{{ - n^{2} }}{2}}} \), premultiplied by the sequence \( W_{N}^{{\frac{{n^{2} }}{2}}} \), and the chirp filter impulse response is
Thus, the block diagram of chirp transform system for DFT computation is shown in Fig. 4.18.
Block diagram of chirp transform system for DFT computation
4.10 Decimation-in-Time FFT Algorithm for a Composite Number
In the previous sections, we discussed FFT algorithms for radix-2 and radix-4 cases. However, it may not be possible in all cases to choose N to be a power of 2 or 4. We now consider the case where N is a composite number composed of a product of two factors \( n_{1} \) and \( n_{2} \), i.e., \( N = n_{1} n_{2} \), so that we can divide the sequence \( x\left( n \right) \) into \( n_{1} \) subsequences of length \( n_{2} \). Then, \( X\left( K \right) \) can be written as
The above equation can be rewritten as
Define
Then, \( X\left( k \right) \) can be expressed in terms of \( n_{1} \) DFTs of sequences of length \( n_{2} \) samples as
For illustration, consider computation of a 12-point DIT FFT (N = 12 = 3.4). The original sequence is divided into three sequences, each of length 4.
First sequence: \( x\left( 0 \right) x\left( 3 \right) x\left( 6 \right) x\left( 9 \right) \); second sequence: \( x\left( 1 \right)x\left( 4 \right)x\left( 7 \right)x\left( {10} \right); \)
Third sequence: \( x\left( 2 \right)x\left( 5 \right) x\left( 8 \right) x\left( {11} \right) \). Then, \( X\left( k \right) \) can be expressed as
The flow graph of the 12-point DFT is shown in Fig. 4.19.
Flow graph of a 12-point DIT FFT
4.11 The Inverse Discrete Fourier Transform
An FFT algorithm for computing the DFT can be effectively used to compute the inverse DFT. The inverse of an N-point DFT \( X(k) \) is given by
where \( W = \text{e}^{ - j2\pi /N} \). Multiplying both sides of the above expression by N and taking complex conjugates, we obtain
The RHS of Eq. (4.94) is the DFT of the sequence \( X^{*} \left( k \right) \) and can be rewritten as
Taking the complex conjugate on both sides of Eq. (4.96) and using the FFT for the computation of DFT yield
Hence,
The following example illustrates the IDFT computation using the DIT FFT algorithm:
Example 4.25
Find the eight-point IDFT using DIT algorithm.
Solution
Let the input be
Hence,
With N = 8, the four twiddle factors are
The flow diagram for the eight-point inverse DFT using the DIT algorithm is shown in Fig. 4.20.
Eight-point inverse DFT of Example 4.24 using the DIT algorithm
-
Stage 1
-
Stage 2
-
Stage 3
Therefore,
Hence,
4.12 Computation of DFT and IDFT Using MATLAB
The built-in MATLAB functions fft(x) and ifft(x) can be used for the computation of the DFT and the IDFT, respectively. The functions use computationally efficient FFT algorithms.
Example 4.26
Consider the input sequence \( x\left( n \right) = \left\{ {1,1,1,1,0,0,1,1} \right\} \) of Example 4.5. Compute the DFT using MATLAB.
Solution
Execution of fft(x) yields the DFT of \( x\left( n \right) \) as
which is equivalent to the DFT computed using the definition of DFT as in Example 4.3.
Example 4.27
Consider the input
of Example 4.24. Compute IDFT using MATLAB.
Solution
Execution of ifft(X) yields the IDFT of X as
which is the same as the result obtained in Example 4.24.
4.13 Application Examples
4.13.1 Detection of Signals Buried in Noise
One of the applications of the DFT-based spectral analysis is to detect the signals buried in noise. For example, consider a noisy signal with K sinusoidal components with unknown frequencies \( f_{1} ,f_{2} , \ldots ,f_{K} \) given by
where \( \eta (n) \) is additive white noise. The unknown frequencies \( f_{1} ,f_{2} , \ldots ,f_{K} \) can be detected by using DFT. For simulation, a signal with two (K = 2) sinusoidal components N = 1024 and the sampling frequency \( F_{\text{T}} = 1000\;{\text{Hz}} \) are assumed. The following MATLAB program is used to generate the noisy signal and to detect the unknown frequencies by applying the DFT on the generated noisy signal.
Program 4.1
Detection of signals buried in noise
-
clear;clc;
-
N = 1024;
-
K=2;
-
x =randn(1,N);% random noise generation
-
\( F_{T} = \)1000; % sampling frequency
-
T = 1/\( F_{T} \); % sampling time period
-
k=1:N;
-
f=(\( F_{T} \)/2)*rand(1,K); %random generation of unknown frequencies
-
for i=1:K
-
x=x+sin(2*pi*f(i)*k*T); % noisy signal with sinusoidal components
-
end
-
t = k*T;
-
figure(1),plot (t(1:N/8),x(1:N/8))
-
xlabel(′Time(sec)′);ylabel(′Magnitude′);
-
% Compute and plot power density spectrum
-
figure(2),
-
X= abs(fft(x));
-
S = X.^2/N;
-
f = linspace (0,(N-1)*Fs/N,N);
-
plot (f(1:N/2),S(1:N/2))
-
set(gca,′Xlim′,[0,Fs/2])
-
xlabel(′Frequency (Hz)′);
-
ylabel(′Power spectrum′)
-
% Finding frequencies
-
s = f_prompt (′Enter threshold for locating peaks′,0,max(S),.7*max(S));
-
for i = 1: N/2
-
if (S(i)>s)
-
fprintf (′f = %.0f Hz\n′,f(i))
-
end
-
end
For a random run of the above program, the noisy signal and its power spectral density are shown in Fig. 4.21a, b, respectively, and the two unknown frequencies are identified as \( f_{1} = 322\;{\text{Hz}} \) and \( f_{2} = 411\;{\text{Hz}} \).
a Noisy signal and b power spectrum density of the noisy signal
4.13.2 Denoising of a Speech Signal
The DFT can be applied to Fourier domain filtering which is equivalent to circular convolution of a sequence of finite length with an ideal impulse response of finite length. This approach is useful in denoising a signal for suppressing high-frequency noise from a low-frequency signal corrupted with noise. For purpose of illustration, we considered the speech signal ‘To take good care of yourself’ from sound file ‘goodcare.wav’. The following MATLAB program is used to read the speech signal from the wav file and to add noise to the speech signal and to reconstruct the original speech signal by performing circular convolution of the noisy speech signal with finite length impulse response.
%Program 4.2
Denoising using circular convolution
-
clear;clc;
-
[x,fs]=wavread(′goodcare.wav′);
-
wavplay(x,fs)% listen to original speech signal
-
no=0.075*randn(1,length(x));% noise generation
-
xn=x+no′;%add noise to original speech signal
-
wavplay(xn,fs)%listen to noisy speech signal
-
figure(1),plot(x);xlabel(′Number of samples′);ylabel(′Amplitude′);
-
figure(2),plot(xn);xlabel(′Number of samples′);ylabel(′Amplitude′);
-
h=ones(1,64)/64;y=fftfilt(h,xn);%perform denoising
-
wavplay(12*y,fs);% listen to recovered speech signal
-
figure(3),plot(12*y);xlabel(′Number of samples′);ylabel(′Amplitude′);
The speech signal, the noisy speech signal, and the recovered speech signal after denoising, obtained from the above MATLAB program, are shown in Figs. 4.22a–c, respectively. From these figures, it can be observed that the recovered speech signal after denoising is nearly same as the original signal.
a Speech signal, b noisy speech signal, and c recovered speech signal after denoising
4.13.3 DTMF Tone Detection Using Goertzel Algorithm
Dual-tone multifrequency (DTMF) signaling is widely used worldwide for voice communications in modern telephony to dial numbers and configure switch boards. It is also used in voice mail, electronic mail, and telephone banking.
DTMF signaling uses two tones to represent each key on the touch pad. There are 12 distinct tones. When any key is pressed, the tone of the column and the tone of the row are generated. As an example, pressing the ‘5’ button generates the tones 770 Hz and 1336 Hz. In this example, use the number 10 to represent the ‘*’ key and 11 to represent the ‘#’ key.
The frequencies were chosen to avoid harmonics: No frequency is a multiple of another, the difference between any two frequencies does not equal any of the frequencies, and the sum of any two frequencies does not equal any of the frequencies.
The industry standard frequency specifications for all the keys are listed in Fig. 4.23.
DTMF tone specifications
The DTMF signals for each button on telephone pad are shown in Fig. 4.24. The MATLAB program to generate the DTMF signals is listed in Program 4.3.
Time responses of each tone of the telephone pad
Program 4.3
-
%MATLAB program DTMF tones generation
-
clear all;clc;
-
Fs = 8000;N = 205;t=[0:1:204]/Fs;
-
lf=[697;770;852;941];hf=[1209;1336;1477];
-
ylf1=sin(2*pi*lf(1)*(0:N-1)/Fs);ylf2=sin(2*pi*lf(2)*(0:N-1)/Fs);
-
ylf3=sin(2*pi*lf(3)*(0:N-1)/Fs);ylf4=sin(2*pi*lf(4)*(0:N-1)/Fs);
-
yhf1=sin(2*pi*hf(1)*(0:N-1)/Fs);yhf2=sin(2*pi*hf(2)*(0:N-1)/Fs);
-
yhf3=sin(2*pi*hf(3)*(0:N-1)/Fs);
-
y1=ylf1+yhf1;y2=ylf1+yhf2;y3=ylf1+yhf3;y4=ylf2+yhf1;
-
y5=ylf2+yhf2;y6=ylf2+yhf3;y7=ylf3+yhf1;y8=ylf3+yhf2;
-
y9=ylf3+yhf3;ystar=ylf4+yhf1;y0=ylf4+yhf2;yhash=ylf4+yhf3;
-
figure(1)
-
subplot(2,2,1);plot(t,y1);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:1,[697,1209]′);
-
subplot(2,2,2);plot(t,y2);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:2,[697,1336]′);
-
subplot(2,2,3);plot(t,y3);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:3,[697,1477]′);
-
subplot(2,2,4);plot(t,y4);
-
xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:4,[770,1209]′);
-
figure(2)
-
subplot(2,2,1);plot(t,y5);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:5,[770,1336]′);
-
subplot(2,2,2);plot(t,y6);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:6,[770,1477]′);
-
subplot(2,2,3);plot(t,y7);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:7,[852,1209]′);
-
subplot(2,2,4);plot(t,y8);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:8,[852,1336]′);
-
figure(3)
-
subplot(2,2,1);plot(t,y9);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:9,[852,1477]′);
-
subplot(2,2,2);plot(t,ystar);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:*,[941,1209]′);
-
subplot(2,2,3);plot(t,y0);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:0,[941,1336]′);
-
subplot(2,2,4);plot(t,yhash);xlabel(′time (seconds)′)
-
ylabel(′Amplitude′);grid;title(′symbol:#,[941,1477]′);
-
DTMF tone detection
The DTMF detection relies on the Goertzel algorithm (Goertzel filter). The main purpose of using the Goertzel filters is to calculate the spectral value at the specified frequency index using the filtering method. Its advantage includes the reduction of the required computations and avoidance of complex algebra. The detection of frequencies using Goertzel algorithm contained in each tone of the telephone pad is shown in Fig. 4.25. The MATLAB program for the tones detection using the Goertzel algorithm is listed in Program 4.4.
DTMF tone detection using Goertzel algorithm
Program 4.4
-
clear all;clc;
-
Fs = 8000;N = 205;load DTMFdata
-
f = [697 770 852 941 1209 1336 1477];
-
freq_indices = round(f/Fs*N) + 1;
-
for tonechoice=1:12
-
tonedata=DTMFs(tonechoice,:);
-
dft_data(tonechoice,:) = goertzel(tonedata,freq_indices);
-
end
-
figure(1)
-
subplot(2,2,1);stem(f,abs(dft_data(1,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:1,[697,1209]′);
-
subplot(2,2,2);stem(f,abs(dft_data(2,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:2,[697,1336]′);
-
subplot(2,2,3);stem(f,abs(dft_data(3,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:3,[697,1477]′);
-
subplot(2,2,4);stem(f,abs(dft_data(4,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:4,[770,1209]′);
-
figure(2)
-
subplot(2,2,1);stem(f,abs(dft_data(5,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:5,[770,1336]′);
-
subplot(2,2,2);stem(f,abs(dft_data(6,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:6,[770,1477]′);
-
subplot(2,2,3);stem(f,abs(dft_data(7,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:7,[852,1209]′);
-
subplot(2,2,4);stem(f,abs(dft_data(8,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:8,[852,1336]′);
-
figure(3)
-
subplot(2,2,1);stem(f,abs(dft_data(9,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:9,[852,1477]′);
-
subplot (2,2,2);stem(f,abs(dft_data(10,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:*,[941,1209]′);
-
subplot (2,2,3);stem(f,abs(dft_data(11,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:0,[941,1336]′);
-
subplot (2,2,4);stem(f,abs(dft_data(12,:)));ax = gca;ax.XTick = f;
-
xlabel(′Frequency(Hz′)
-
ylabel(′DFT magnitudetude′);grid;title(′symbol:#,[941,1477]′);
4.14 Problems
-
1.
Determine the Fourier series representation for the following discrete-time signals:
-
(a)
\( x\left( n \right) = 3\sin \left( {\frac{\pi n}{4}} \right)\sin \left( {\frac{2\pi n}{5}} \right) \)
-
(b)
\( x\left( n \right) \) is periodic of period 8, and \( x\left( n \right) = n \) for \( 0 \le n \le 3 \), and \( x\left( n \right) = n \) for \( 4 \le n \le 7 \)
-
(a)
-
2.
Compute the eight-point DFT of \( \left( { - 1} \right)^{n} \)
-
3.
Find the four-point DFT of the following sequences
-
(i)
\( x\left( n \right) = \left\{ {1,2,1,1} \right\} \)
-
(ii)
\( x\left( n \right) = \sin \left( {n + 1} \right)\pi /4 \)
-
(iii)
\( x\left( n \right) = \left\{ {2, - 1,1, - 2} \right\}. \)
-
(i)
-
4.
Find eight-point DFT of the following sequences
-
(i)
\( x\left( n \right) = \left\{ {1,0,1,0,0,1,1,0} \right\} \)
-
(ii)
\( x\left( n \right) = \cos \left( {n + 1} \right)\pi /2 \)
-
(iii)
\( x\left( n \right) = \left\{ {1,1,0,0,1,0,1,1} \right\} \)
-
(i)
-
5.
Compute the eight-point DFT of the square-wave sequence:
$$ x\left( n \right) = \left\{ {\begin{array}{*{20}l} {2 } & {0 \le n \le \left( {N/2} \right)} \\ { - 2 } & {\left( {N/2} \right) \le n < N - 1} \\ \end{array} } \right. $$ -
6.
Find 16-point DFT of the following sequence:
$$ x\left( n \right) = \left\{ {\begin{array}{*{20}c} {1 } & {0 \le n \le 7} \\ {0 } & {7 < n < 15} \\ \end{array} } \right. $$ -
7.
Compute the eight-point circular convolution of
$$ x_{1} \left( n \right) = \left\{ {1,1,0,1,0,1,1,0} \right\}\, {\text{and}}\,x_{2} \left( n \right) = \sin \left( {3\pi /4} \right), 0 \le n \le 7. $$ -
8.
Find the output \( y\left( n \right) \) of a filter whose impulse response is \( h\left( n \right) = \left\{ {0,1,1} \right\} \) and the input signal is \( x\left( n \right) = \left\{ {1, - 2,0,1,0,2,1,2,2,1} \right\} \) using the overlap-add method.
-
9.
Using linear convolution, find \( y\left( n \right) = x\left( n \right)*h\left( n \right) \) for the sequences \( x\left( n \right) = \left( {2, - 3,1,2,1,1, - 1, - 3,1,2,1, - 1} \right) \) and \( h\left( n \right) = \left( {2,1} \right) \). Compare the result by solving the problem using overlap-save method.
-
10.
Compute the eight-point DFT of the following sequence using the radix-2 DIT algorithm for the following sequences:
-
(i)
\( x\left( n \right) = \left\{ {1,1, - 1,0,1,0,1, - 1} \right\} \)
-
(ii)
\( x\left( n \right) = \left\{ {1,2,1, - 1,2,1, - 1,1} \right\} \)
-
(iii)
\( x\left( n \right) = \left\{ {0.5,0,1,0.5,1,0,0.5,0.5} \right\} \)
-
(i)
-
11.
Compute the eight-point DFT of the sequence \( x\left( n \right) = \left\{ {1,1, - 1,0,1,0,1, - 1} \right\} \) using the DIF algorithm
-
12.
Find the 16-point DFT of the following sequence using radix-4 DIF algorithm.
$$ x\left( n \right) = \left\{ {1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,1} \right\} $$ -
13.
Compute DFT of the sequence \( x\left( n \right) = \left\{ {1,2,3,4} \right\} \) using the Goertzel algorithm
-
14.
Develop the FFT algorithm for the composite number 18, and show the flow graph.
-
15.
Find the IDFT of \( Y\left( k \right) = \left\{ {1,0,0,1} \right\} \).
-
16.
Compute the IDFT of the sequence \( X\left( k \right) = \left\{ {3,j,1 + 2j,1 - j,1 + 2j,1,0, - j} \right\} \) using (a) DIT algorithm and (b) DIF algorithm.
4.15 MATLAB Exercises
References
J.W. Cooley, P.A.W. Lewis, P.D. Welch, Historical notes on the fast Fourier transform. IEEE Trans. Audio Electroacoust. 55(10), 1675–1677 (1967)
J.W. Cooley, P.A.W. Lewis, P.D. Welch, Historical notes on the fast Fourier transform. Proc. IEEE 55(10), 1675–1677 (1967)
G. Goertzel, An algorithm for the evaluation of finite trignometric series. Am. Math Monthly 65, 34–35 (1958)
A.V. Oppenheim, R.W. Schafer, J.R. Buck, Discrete-Time Signal Processing, 2nd edn. (Prentice Hall, 1999)
L. Rabiner, R. Schafer, C. Rader, IEEE Trans. Audio Electroacoust. 17(2) (1969)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this chapter
Cite this chapter
Rao, K.D., Swamy, M.N.S. (2018). The Discrete Fourier Transform. In: Digital Signal Processing. Springer, Singapore. https://doi.org/10.1007/978-981-10-8081-4_4
Download citation
DOI: https://doi.org/10.1007/978-981-10-8081-4_4
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-8080-7
Online ISBN: 978-981-10-8081-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)