Chapter 5

Fourier Analysis for Discrete-Time Signals and Systems

Chapter Objectives

• Learn the use of discrete-time Fourier series for representing periodic signals using orthogonal basis functions.
• Learn the discrete-time Fourier transform (DTFT) for non-periodic signals as an extension of discrete-time Fourier series for periodic signals.
• Study properties of the DTFT. Understand energy and power spectral density concepts.
• Explore frequency-domain characteristics of DTLTI systems. Understand the system function concept.
• Learn the use of frequency-domain analysis methods for solving signal-system interaction problems with periodic and non-periodic input signals.
• Understand the fundamentals of the discrete Fourier transform (DFT) and fast Fourier transform (FFT). Learn how to compute linear convolution using the DFT.

5.1 Introduction

In Chapter 1 and Chapter 3 we have developed techniques for analyzing discrete-time signals and systems from a time-domain perspective. A discrete-time signal can be modeled as a function of the sample index. A DTLTI system can be represented by means of a constant-coefficient linear difference equation, or alternatively by means of an impulse response. The output signal of a DTLTI system can be determined by solving the corresponding difference equation or by using the convolution operation.

In this chapter frequency-domain analysis methods are developed for discrete-time signals and systems. Section 5.2 focuses on analyzing periodic discrete-time signals in terms of their frequency content. Discrete-time Fourier series (DTFS) is presented as the counterpart of the exponential Fourier series (EFS) studied in Chapter 4 for continuous-time signals. Frequency-domain analysis methods for non-periodic discrete-time signals are presented in Section 5.3 through the use of the discrete-time Fourier transform (DTFT). Energy and power spectral density concepts for discrete-time signals are introduced in Section 5.4. Section 5.5, Section 5.6 and Section 5.7 cover the application of frequency-domain analysis methods to the analysis of DTLTI systems. Section 5.8 introduces the discrete Fourier transform (DFT) and the fast Fourier transform (FFT).

5.2 Analysis of Periodic Discrete-Time Signals

In Section 4.2 of Chapter 4 we have focused on expressing continuous-time periodic signals as weighted sums of sinusoidal or complex exponential basis functions. It is also possible to express a discrete-time periodic signal in a similar manner, as a linear combination of discrete-time periodic basis functions. In this section we will explore one such periodic expansion referred to as the discrete-time Fourier series (DTFS). In the process we will discover interesting similarities and differences between DTFS and its continuous-time counterpart, the exponential Fourier series (EFS) that was discussed in Section 4.2. One fundamental difference is regarding the number of series terms needed. We observed in Chapter 4 that a continuous-time periodic signal may have an infinite range of frequencies, and therefore may require an infinite number of harmonically related basis functions. In contrast, discrete-time periodic signals contain a finite range of angular frequencies, and will therefore require a finite number of harmonically related basis functions. We will see in later parts of this section that a discrete-time signal with a period of N samples will require at most N basis functions.

5.2.1 Discrete-Time Fourier Series (DTFS)

Consider a discrete-time signal $\tilde{x}\left[n\right]$ periodic with a period of N samples, that is, $\tilde{x}\left[n\right]=\tilde{x}[n+N]$ for all n. As in Chapter 4 periodic signals will be distinguished through the use of the tilde (˜) character over the name of the signal. We would like to explore the possibility of writing $\tilde{x}\left[n\right]$ as a linear combination of complex exponential basis functions in the form

$$\begin{array}{cc}{\varphi }_k\left[n\right]=e^{j{\Omega }_{k}n}& \left(5.1\right)\end{array}$$

using a series expansion

$$\begin{array}{cc}\tilde{x}\left[n\right]={\displaystyle \sum _k{\tilde{c}}_k{\varphi }_k\left[n\right]}={\displaystyle \sum _k{\tilde{c}}_k{e}^{j{\Omega }_{k}n}}& \left(5.2\right)\end{array}$$

Two important questions need to be answered:

1. How should the angular frequencies Ωk be chosen?
2. How many basis functions are needed? In other words, what should be the limits of the summation index k in Eqn. (5.2)?

Intuitively, since the period of $\tilde{x}\left[n\right]$ is N samples long, the basis functions used in constructing the signal must also be periodic with N. Therefore we require

$$\begin{array}{cc}{\varphi }_k\left[n+N\right]={\varphi }_k\left[n\right]& \left(5.3\right)\end{array}$$

for all n. Substituting Eqn. (5.1) into Eqn. (5.3) leads to

$$\begin{array}{cc}{e}^{j{\Omega }_k\left(n+N\right)}=e^{j{\Omega }_{k}n}& \left(5.4\right)\end{array}$$

For Eqn. (5.4) to be satisfied we need ejΩkN = 1, and consequently ΩkN = 2πk. The angular frequency of the basis function φk[n] must be

$$\begin{array}{cc}{\Omega }_k=\frac{2\pi k}{N}& \left(5.5\right)\end{array}$$

leading to the set of basis functions

$$\begin{array}{cc}{\varphi }_k\left[n\right]=e^{j\left(2\pi /N\right)kn}& \left(5.6\right)\end{array}$$

Using φk[n] found, the series expansion of the signal $\tilde{x}\left[n\right]$ is in the form

$$\begin{array}{cc}\tilde{x}\left[n\right]={\displaystyle \sum _k{\tilde{c}}_k{e}^{j\left(2\pi /N\right)kn}}& \left(5.7\right)\end{array}$$

To address the second question, it can easily be shown that only the first N basis functions φ0[n],φ1[n],...,φN−1[n] are unique; all other basis functions, i.e., the ones obtained for k < 0 or k ≥ N, are duplicates of the basis functions in this set. To see why this is the case, let us write φk+N [n]:

$$\begin{array}{cc}{\varphi }_{k+N}\left[n\right]=e^{j\left(2\pi /N\right)\left(k+N\right)n}& \left(5.8\right)\end{array}$$

Factoring Eqn. (5.8) into two exponential terms and realizing that ej2πn = 1 for all integers n we obtain

$$\begin{array}{cc}{\varphi }_{k+N}\left[n\right]=e^{j\left(2\pi /N\right)kn}{e}^{j2\pi n}=e^{j\left(2\pi /N\right)kn}={\varphi }_k\left[n\right]& \left(5.9\right)\end{array}$$

Since φk+N[n] is equal to φk[n], we only need to include N terms in the summation of Eqn. (5.7).

As a specific example, if the period of the signal $\tilde{x}\left[n\right]$ is N = 5, then the only basis functions that are unique would be

$$\begin{array}{ccc}{\varphi }_k\left[n\right]& \text{for}& k=0,1,2,3,4\end{array}$$

Increasing the summation index k beyond k = 4 would not create any additional unique terms since φ5[n] = φ0[n], φ6[n]= φ1[n], and so on.

Eqn. (5.10) is referred to as the discrete-time Fourier series (DTFS) expansion of the periodic signal $\tilde{x}\left[n\right]$. The coefficients ${\tilde{c}}_k$ used in the summation of Eqn. (5.10) are the DTFS coefficients of the signal $\tilde{x}\left[n\right]$.

Example 5.1: DTFS for a discrete-time sinusoidal signal

Determine the DTFS representation of the signal $\tilde{x}\left[n\right]=\cos \left(\sqrt{2}\pi n\right)$.

Solution: The angular frequency of the signal is

$${\Omega }_0=\sqrt{2}\pi t\text{ rad}$$

and it corresponds to the normalized frequency

$$F_0=\frac{{\Omega }_0}{2\pi }=\frac{1}{\sqrt{2}}$$

Since normalized frequency F0 is an irrational number, the signal specified is not periodic (refer to the discussion in Section 1.4.4 of Chapter 1). Therefore it cannot be represented in series form using periodic basis functions. It can still be analyzed in the frequency domain, however, using the discrete-time Fourier transform (DTFT) which will be explored in Section 5.3.

Example 5.2: DTFS for a discrete-time sinusoidal signal revisited

Determine the DTFS representation of the signal $\tilde{x}\left[n\right]=\cos \left(0.2\pi n\right)$.

Solution: The angular frequency of the signal is

$${\Omega }_0=0.2\pi \text{ rad}$$

and the corresponding normalized frequency is

$$F_0=\frac{{\Omega }_0}{2\pi }=\frac{1}{10}$$

Based on the normalized frequency, the signal is periodic with a period of N = 1/F0 = 10 samples. A general formula for obtaining the DTFS coefficients will be derived later in this section. For the purpose of this example, however, we will take a shortcut afforded by the sinusoidal nature of the signal $\tilde{x}\left[n\right]$, and express it using Euler’s formula:

$$\begin{array}{lll}\tilde{x}[n]\hfill & =\frac{1}{2}{e}^{j0.2\pi n}+\frac{1}{2}{e}^{-j0.2\pi n}\hfill & \hfill \\ \hfill & =\frac{1}{2}{e}^{j(2\pi /10)n}+\frac{1}{2}{e}^{-j(2\pi /10)n}\hfill & (5.11)\hfill \end{array}$$

The two complex exponential terms in Eqn. (5.11) correspond to φ1[n] and φ−1[n], therefore their coefficients must be ${\tilde{c}}_1$ and ${\tilde{c}}_{-1}$, respectively. As a result we have

$$\begin{array}{cccc}{\tilde{c}}_1=\frac{1}{2},& \text{and}& {\tilde{c}}_{-1}=\frac{1}{2}& \left(5.12\right)\end{array}$$

As discussed in the previous section we would like to see the series coefficients ${\tilde{c}}_k$ in the index range k = 0,...,N − 1 where N is the period. In this case we need to obtain ${\tilde{c}}_k$ for k = 0,..., 9. The basis functions have the property

$${\varphi }_k\left[n\right]={\varphi }_{k+N}\left[n\right]$$

The term φ−1[n] in Eqn. (5.11) can be written as

$$\begin{array}{lll}{\varphi }_{-1}[n]\hfill & =e^{-j(2\pi /10)n}\hfill & \hfill \\ \hfill & =e^{-j(2\pi /10)n}{e}^{j2\pi n}\hfill & \hfill \\ \hfill & =e^{j(18\pi /10)n}={\varphi }_9[n]\hfill & (5.13)\hfill \end{array}$$

Eqn. (5.11) becomes

$$\begin{array}{ll}\tilde{x}[n]\hfill & =\cos (0.2\pi n)\hfill \\ \hfill & =\frac{1}{2}{e}^{j(2\pi /10)n}+\frac{1}{2}{e}^{j(18\pi /10)n}\hfill \\ \hfill & ={\tilde{c}}_1{e}^{j(2\pi /10)n}+{\tilde{c}}_9{e}^{j(18\pi /10)n}\hfill \end{array}$$

DTFS coefficients are

$${\tilde{c}}_k=\{\begin{array}{ll}\frac{1}{2},\hfill & k=1\text{ or }k=9\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

The signal $\tilde{x}\left[n\right]$ and its DTFS spectrum ${\tilde{c}}_k$ are shown in Fig. 5.1.

Software resources:

ex_5_2.m

Example 5.3: DTFS for a multi-tone signal

Determine the DTFS coefficients for the signal

$$\tilde{x}\left[n\right]=1+\cos \left(0.2\pi n\right)+2\sin \left(0.3\pi n\right)$$

Solution: The two angular frequencies Ω1 = 0.2π and Ω2 = 0.3π radians correspond to normalized frequencies F1 = 0.1 and F2 = 0.15 respectively. The normalized fundamental frequency of $\tilde{x}\left[n\right]$ is F0 = 0.05, and it corresponds to a period of N = 20 samples. Using this value of N, the angular frequencies of the two sinusoidal terms of $\tilde{x}\left[n\right]$ are

$${\Omega }_1=2{\Omega }_0=\frac{2\pi }{20}\left(2\right)$$

and

$${\Omega }_2=3{\Omega }_0=\frac{2\pi }{20}\left(3\right)$$

We will use Euler’s formula to write $\tilde{x}\left[n\right]$ in the form

$$\begin{array}{ll}\tilde{x}\left[n\right]& =1+\frac{1}{2}{e}^{j\left(2\pi /20\right)2n}+\frac{1}{2}{e}^{-j\left(2\pi /20\right)2n}+\frac{1}{j}{e}^{j\left(2\pi /20\right)3n}-\frac{1}{j}{e}^{-j\left(2\pi /20\right)3n}\\ & =1+\frac{1}{2}{\varphi }_2\left[n\right]+\frac{1}{3}{\varphi }_{-2}\left[n\right]+\frac{1}{j}{\varphi }_3\left[n\right]-\frac{1}{j}{\varphi }_{-3}\left[n\right]\\ & =1+\frac{1}{2}{\varphi }_2\left[n\right]+\frac{1}{2}{\varphi }_{-2}\left[n\right]+e^{-j\pi /2}{\varphi }_3\left[n\right]-e^{j\pi /2}{\varphi }_{-3}\left[n\right]\end{array}$$

The DTFS coefficients are

$$\begin{array}{ll}{\tilde{c}}_0=1& \\ {\tilde{c}}_2=\frac{1}{2},& {\tilde{c}}_{-2}=\frac{1}{2}\\ {\tilde{c}}_3=e^{-j\pi /2},& {\tilde{c}}_{-3}=e^{j\pi /2}\end{array}$$

We know from the periodicity of the DTFS representation that

$$\begin{array}{cccc}{\tilde{c}}_{-2}={\tilde{c}}_{18}& \text{and}& {\tilde{c}}_{-3}={\tilde{c}}_{17}& \left(5.14\right)\end{array}$$

The signal $\tilde{x}\left[n\right]$ and its DTFS spectrum ${\tilde{c}}_k$ are shown in Fig. 5.2.

Software resources:

ex_5_3.m

Finding DTFS coefficients

In Examples 5.2 and 5.3 the DTFS coefficients for discrete-time sinusoidal signals were easily determined since the use of Euler’s formula gave us the ability to express those signals in a form very similar to the DTFS expansion given by Eqn. (5.7). In order to determine the DTFS coefficients for a general discrete-time signal we will take advantage of the orthogonality of the basis function set {φk[n], k = 0,...,N − 1}. It can be shown that (see Appendix D)

$$\begin{array}{cc}{\displaystyle \sum _{n=0}^{N-1}{e}^{j\left(2\pi /N\right)\left(m-k\right)n}}=\{\begin{array}{ll}N,\hfill & \left(m-k\right)=rN,r\text{ integer}\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}& \left(5.15\right)\end{array}$$

The DTFS coefficients are computed from Eqn. (5.18) as

$$\begin{array}{lll}\tilde{c}=\frac{1}{N}{\displaystyle \sum _{n=0}^{N-1}\tilde{x}\left[n\right]e^{-j\left(2\pi /N\right)kn}},& k=0,\mathrm{...},N-1& \left(5.19\right)\end{array}$$

In Eqn. (5.19) the DTFS coefficients are computed for the index range k = 0,...,N − 1 since those are the only coefficient indices that are needed in the DTFS expansion in Eqn. (5.10). If we were to use Eqn. (5.19) outside the specified index range we would discover that

$$\begin{array}{ll}{\tilde{c}}_k+rN={\tilde{c}}_k& \left(5.20\right)\end{array}$$

for all integers r. The DTFS coefficients evaluated outside the range k = 0,...,N − 1 exhibit periodic behavior with period N. This was evident in Examples 5.2 and 5.3 as well. The development so far can be summarized as follows:

Note that the coefficients ${\tilde{c}}_k$ are computed for all indices k in Eqn. (5.22), however, only the ones in the range k = 0,...,N − 1 are needed in constructing the signal $\tilde{x}\left[n\right]$ in Eqn. (5.21). Due to the periodic nature of the DTFS coefficients ${\tilde{c}}_k$, the summation in the synthesis equation can be started at any arbitrary index, provided that the summation includes exactly N terms. In other words, Eqn. (5.21) can be written in the alternative form

$$\begin{array}{lll}\tilde{x}\left[n\right]={\displaystyle \sum _{k=N_0}^{N_0+N-1}{\tilde{c}}_k{e}^{j\left(2\pi /N\right)kn},}& \text{all }n& \left(5.23\right)\end{array}$$

Example 5.4: Finding DTFS representation

Consider the periodic signal $\tilde{x}\left[n\right]$ defined as

$$\begin{array}{llll}\tilde{x}\left[n\right]=n& \text{for }n=0,1,2,3,4& \text{and}& \tilde{x}\left[n+5\right]=\tilde{x}\left[n\right]\end{array}$$

and shown in Fig. 5.3. Determine the DTFS coefficients for $\tilde{x}\left[n\right]$. Afterwards, verify the synthesis equation in Eqn. (5.21).

Solution: Using the analysis equation given by Eqn. (5.22) the DTFS coefficients are

$$\begin{array}{lll}{\tilde{c}}_k& =\frac{1}{5}{\displaystyle \sum _{n=0}^4\tilde{x}\left[n\right]e^{-j\left(2\pi /5\right)kn}}& \\ & =\frac{1}{5}{e}^{-j2\pi k/5}+\frac{2}{5}{e}^{-j4\pi k/5}+\frac{3}{5}{e}^{-j6\pi k/5}+\frac{4}{5}{e}^{-j8\pi k/5}& \left(5.24\right)\end{array}$$

Evaluating Eqn. (5.24) for k = 0,..., 4 we get

$$\begin{array}{l}{\tilde{c}}_0=2\\ {\tilde{c}}_1=-0.5+j0.6882\\ {\tilde{c}}_2=-0.5+j0.1625\\ {\tilde{c}}_3=-0.5-j0.1625\\ {\tilde{c}}_4=-0.5-j0.6882\end{array}$$

The signal $\tilde{x}\left[n\right]$ can be constructed from DTFS coefficients as

$$\begin{array}{ll}\tilde{x}[n]\hfill & ={\tilde{c}}_0+{\tilde{c}}_1{e}^{j2\pi n/5}+{\tilde{c}}_2{e}^{j4\pi n/5}+{\tilde{c}}_4{e}^{j8\pi n/5}\hfill \\ \hfill & =2+(-0.5+j0.6882)e^{j2\pi n/5}+(-0.5+j0.1625)e^{j4\pi n/5}\hfill \\ \hfill & +(-0.5-j0.1625)e^{j6\pi n/5}+(-0.5-j0.6882)e^{j8\pi n/5}\hfill \end{array}$$

Software resources:

ex_5_4a.m

ex_5_4b.m

Example 5.5: DTFS for discrete-time pulse train

Consider the periodic pulse train $\tilde{x}\left[n\right]$ defined by

$$\tilde{x}\left[n\right]=\{\begin{array}{ll}\begin{array}{ll}1,& -L\le n\le L\\ 0,& L<n<N-L\end{array}& \text{and }\tilde{x}\left[n+N\right]=\tilde{x}\left[n\right]\end{array}$$

where N > 2L + 1 as shown in Fig. 5.4. Determine the DTFS coefficients of the signal $\tilde{x}\left[n\right]$ in terms of L and N.

Solution: Using Eqn. (5.22) the DTFS coefficients are

$${\tilde{c}}_k=\frac{1}{N}{\displaystyle \sum _{n=-L}^L\left(1\right)e^{-j\left(2\pi /N\right)kn}}$$

The closed form expression for a finite-length geometric series is (see Appendix C for derivation)

$$\begin{array}{ll}\text{Eqn}\text{. }\left(C.13\right):& {\displaystyle \sum _{n=L_1}^{L_2}{a}^n=\frac{a^{L_1}-a^{L_2+1}}{1-a}}\end{array}$$

Using Eqn. (C.13) with a = e−j(2π/N)k, L1 = −L and L2 = L, the closed form expression for ${\tilde{c}}_k$ is

$$\begin{array}{ll}{\tilde{c}}_k=\frac{1}{N}\frac{e^{j\left(2\pi /N\right)Lk}-e^{-j\left(2\pi /N\right)\left(L+1\right)k}}{1-e^{-j\left(2\pi /N\right)k}}& \left(5.25\right)\end{array}$$

In order to get symmetric complex exponentials in Eqn. (5.25) we will multiply both the numerator and the denominator of the fraction on the right side of the equal sign with ejπk/N resulting in

$$\begin{array}{ll}{\tilde{c}}_k=\frac{1}{N}\frac{e^{j\left(2\pi /N\right)\left(L+1/2\right)k}-e^{-j\left(2\pi /N\right)\left(L+1/2\right)k}}{e^{j\left(2\pi /N\right)\left(k/2\right)}-e^{-j\left(2\pi /N\right)\left(k/2\right)}}& \left(5.26\right)\end{array}$$

which, using Euler’s formula, can be simplified to

$$\begin{array}{ll}{\tilde{c}}_k=\frac{\sin \left(\frac{\pi k}{N}\left(2L+1\right)\right)}{N\sin \left(\frac{\pi k}{N}\right)},& k=0,\mathrm{...},N-1\end{array}$$

The coefficient ${\tilde{c}}_0$ needs special attention. Using L’Hospital’s rule we obtain

$${\tilde{c}}_0=\frac{2L+1}{N}$$

The DTFS representation of the signal $\tilde{x}\left[n\right]$ is

$$\tilde{x}\left[n\right]={\displaystyle \sum _{k=0}^{N-1}\left[\frac{\sin \left(\frac{\pi k}{N}\left(2L+1\right)\right)}{N\sin \left(\frac{\pi k}{N}\right)}\right]}{e}^{j\left(2\pi /N\right)kn}$$

The DTFS coefficients are graphed in Fig. 5.5 for N = 40 and L = 3, 5, and 7.

Software resources:

ex_5_5.m

5.2.2 Properties of the DTFS

In this section we will summarize a few important properties of the DTFS representation of a periodic signal. To keep the notation compact, we will denote the relationship between the periodic signal $\tilde{x}\left[n\right]$ and its DTFS coefficients ${\tilde{c}}_k$ as

$$\begin{array}{ll}\tilde{x}\left[n\right]\stackrel{\text{DTFS}}{\leftrightarrow }{\tilde{c}}_k& \left(5.27\right)\end{array}$$

Periodicity

DTFS coefficients are periodic with the same period N as the signal $\tilde{x}\left[n\right]$.

Periodicity of DTFS coefficients follows easily from the analysis equation given by Eqn. (5.22).

Linearity

Linearity property is easily proven starting with the synthesis equation in Eqn. (5.21).

Time shifting

Time shifting the signal $\tilde{x}\left[n\right]$ causes the DTFS coefficients to be multiplied by a complex exponential function.

Consistency check: Let the signal be time shifted by exactly one period, that is, m = N. We know that $\tilde{x}\left[n-N\right]=\tilde{x}\left[n\right]$ due to the periodicity of $\tilde{x}\left[n\right]$. The exponential function on the right side of Eqn. (5.30) would be e−j(2π/N)kN = 1, and the DTFS coefficients remain unchanged, as expected.

Symmetry of DTFS coefficients

Conjugate symmetry and conjugate antisymmetry properties were defined for discrete-time signals in Section 1.4.6 of Chapter 1. Same definitions apply to DTFS coefficients as well. A conjugate symmetric set of coefficients satisfy

$$\begin{array}{ll}{\tilde{c}}_k^{*}={\tilde{c}}_{-k}& \left(5.31\right)\end{array}$$

for all k. Similarly, the coefficients form a conjugate antisymmetric set if they satisfy

$$\begin{array}{ll}{\tilde{c}}_k^{*}=-{\tilde{c}}_{-k}& \left(5.32\right)\end{array}$$

for all k. For a signal $\tilde{x}\left[n\right]$ which is periodic with N samples it is customary to use the DTFS coefficients in the index range k = 0,...,N − 1. The definitions in Equation (5.31) and Equation (5.32) can be adjusted in terms of their indices using the periodicity of the DTFS coefficients. Since ${\tilde{c}}_{-k}={\tilde{c}}_{N-k}$, a conjugate symmetric set of DTFS coefficients have the property

$$\begin{array}{lll}{\tilde{c}}_k^{*}={\tilde{c}}_{N-k},& k=0,\mathrm{...},N-1& \left(5.33\right)\end{array}$$

Similarly, a conjugate antisymmetric set of DTFS coefficients have the property

$$\begin{array}{lll}{\tilde{c}}_k^{*}=-{\tilde{c}}_{N-k},& k=0,\mathrm{...},N-1& \left(5.34\right)\end{array}$$

If the signal $\tilde{x}\left[n\right]$ is real-valued, it can be shown that its DTFS coefficients form a conjugate symmetric set. Conversely, if the signal $\tilde{x}\left[n\right]$ is purely imaginary, its DTFS coefficients form a conjugate antisymmetric set.

Polar form of DTFS coefficients

DTFS coefficients can be written in polar form as

$$\begin{array}{ll}{\tilde{c}}_k=\left|{\tilde{c}}_k\right|e^{j{\overline{\theta }}_k}& \left(5.37\right)\end{array}$$

If the set $\left\{{\tilde{c}}_k\right\}$ is conjugate symmetric, the relationship in Eqn. (5.33) leads to

$$\begin{array}{ll}\left|{\tilde{c}}_k\right|e^{-j{\overline{\theta }}_k}=\left|{\tilde{c}}_{N-k}\right|e^{j{\overline{\theta }}_{N-k}}& \left(5.38\right)\end{array}$$

using the polar form of the coefficients. The consequences of Eqn. (5.38) are obtained by equating the magnitudes and the phases on both sides.

It was established in Eqn. (5.35) that the DTFS coefficients of a real-valued $\tilde{x}\left[n\right]$ are conjugate symmetric. Based on the results in Equation (5.39) and Equation (5.40) the magnitude spectrum is an even function of k, and the phase spectrum is an odd function of k.

Similarly, if the set $\left\{{\tilde{c}}_k\right\}$ is conjugate antisymmetric, the relationship in Eqn. (5.34) reflects on polar form of ${\tilde{c}}_k$ as

$$\begin{array}{ll}\left|{\tilde{c}}_k\right|e^{-j{\overline{\theta }}_k}=-\left|{\tilde{c}}_{N-k}\right|e^{j{\overline{\theta }}_{N-k}}& \left(5.41\right)\end{array}$$

The negative sign on the right side of Eqn. (5.41) needs to be incorporated into the phase since we could not write $\left|{\tilde{c}}_k\right|=-\left|{\tilde{c}}_{N-k}\right|$ (recall that magnitude must to be non-negative). Using e∓jπ = −1, Eqn. (5.41) becomes

$$\begin{array}{lll}\left|{\tilde{c}}_k\right|e^{-j{\overline{\theta }}_k}& =\left|{\tilde{c}}_{N-k}\right|e^{j{\overline{\theta }}_{N-k}}{e}^{\mp j\pi }& \\ & =\left|{\tilde{c}}_{N-k}\right|e^{j\left({\overline{\theta }}_{N-k\mp \pi }\right)}& \left(5.42\right)\end{array}$$

The consequences of Eqn. (5.42) are summarized below.

A purely imaginary signal $\tilde{x}\left[n\right]$ leads to a set of DTFS coefficients with conjugate antisymmetry. The corresponding magnitude spectrum is an even function of k as suggested by Eqn. (5.43). The phase spectrum is neither even nor odd.

Example 5.6: Symmetry of DTFS coefficients

Recall the real-valued periodic signal $\tilde{x}\left[n\right]$ of Example 5.4 shown in Fig. 5.3. Its DTFS coefficients were found as

$$\begin{array}{l}{\tilde{c}}_0=2\\ {\tilde{c}}_1=-0.5+j0.6882\\ {\tilde{c}}_2=-0.5+j0.1625\\ {\tilde{c}}_3=-0.5-j0.1625\\ {\tilde{c}}_4=-0.5-j0.6882\end{array}$$

It can easily be verified that coefficients form a conjugate symmetric set. With N = 5 we have

$$\begin{array}{lll}k=1& \Rightarrow & {\tilde{c}}_1^{*}={\tilde{c}}_4\\ k=2& \Rightarrow & {\tilde{c}}_2^{*}={\tilde{c}}_3\end{array}$$

DTFS spectra of even and odd signals

If the real-valued signal $\tilde{x}\left[n\right]$ is an even function of index n, the resulting DTFS spectrum ${\tilde{c}}_k$ is real-valued for all k.

$$\begin{array}{llll}\tilde{x}\left[n\right]=\tilde{x}\left[n\right],\text{all }n& \text{implies that}& \mathrm{Im}\left\{{\tilde{c}}_k\right\}=0,\text{ all }k& \left(5.45\right)\end{array}$$

Conversely it can also be proven that, if the real-valued signal $\tilde{x}\left[n\right]$ has odd-symmetry, the resulting DTFS spectrum is purely imaginary.

$$\begin{array}{llll}\tilde{x}\left[n\right]=-\tilde{x}\left[n\right],\text{all }n& \text{implies that}& \mathrm{Re}\left\{{\tilde{c}}_k\right\}=0,\text{ all }k& \left(5.46\right)\end{array}$$

Example 5.7: DTFS symmetry for periodic waveform

Explore the symmetry properties of the periodic waveform $\tilde{x}\left[n\right]$ shown in Fig. 5.6. One period of $\tilde{x}\left[n\right]$ has the sample amplitudes

$$\tilde{x}\left[n\right]=\left\{\mathrm{...},\underset{\stackrel{\uparrow }{n=0}}{0},\frac{1}{2},1,\frac{3}{4},0,-\frac{3}{4},-1,-\frac{1}{2},\mathrm{...}\right\}$$

Solution: The DTFS coefficients for $\tilde{x}\left[n\right]$ are computed as

$${\tilde{c}}_k={\displaystyle \sum _{n=0}^7\tilde{x}\left[n\right]e^{-j\left(2\pi /8\right)kn}}$$

and are listed for k = 0,..., 8 in Table 5.1 along with magnitudes and phase values for each. Symmetry properties can be easily observed. The signal is real-valued, therefore the DTFS spectrum is conjugate symmetric:

$$\begin{array}{lll}k=1& \Rightarrow & {\tilde{c}}_1^{*}={\tilde{c}}_7\\ k=2& \Rightarrow & {\tilde{c}}_2^{*}={\tilde{c}}_6\\ k=3& \Rightarrow & {\tilde{c}}_3^{*}={\tilde{c}}_5\end{array}$$

Furthermore, the odd symmetry of $\tilde{x}\left[n\right]$ causes coefficients to be purely imaginary:

$$\begin{array}{ll}\mathrm{Re}\left\{{\tilde{c}}_k\right\}=0& k=0,\mathrm{...},7\end{array}$$

In terms of the magnitude values we have

$$\begin{array}{lll}k=1& \Rightarrow & \left|{\tilde{c}}_1\right|=\left|{\tilde{c}}_7\right|\\ k=2& \Rightarrow & \left|{\tilde{c}}_2\right|=\left|{\tilde{c}}_6\right|\\ k=2& \Rightarrow & \left|{\tilde{c}}_3\right|=\left|{\tilde{c}}_5\right|\end{array}$$

For the phase angles the following relationships hold:

$$\begin{array}{lll}k=1& \Rightarrow & {\tilde{\theta }}_1=-{\tilde{\theta }}_7\\ k=2& \Rightarrow & {\tilde{\theta }}_2=-{\tilde{\theta }}_6\\ k=2& \Rightarrow & {\tilde{\theta }}_3=-{\tilde{\theta }}_5\end{array}$$

The phase values for ${\tilde{\theta }}_0$ and ${\tilde{\theta }}_4$ are insignificant since the corresponding magnitude values $\left|{\tilde{c}}_0\right|$ and $\left|{\tilde{c}}_4\right|$ are equal to zero.

Software resources:

ex_5_7.m

Periodic convolution

Consider the convolution of two discrete-time signals defined by Eqn. (3.128) and repeated here for convenience:

$$\begin{array}{ll}\text{Eqn}\text{.}\left(3.128\right):& y\left[n\right]=x\left[n\right]*h\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }x\left[k\right]h\left[n-k\right]}\end{array}$$

This summation would obviously fail to converge if both signals x[n] and h[n] happen to be periodic with periods of N. For such a case, a periodic convolution operator can be defined as

$$\begin{array}{lll}\tilde{y}\left[n\right]=\tilde{x}\left[n\right]\otimes \tilde{h}\left[n\right]={\displaystyle \sum _{k=0}^{N-1}\tilde{x}\left[k\right]\tilde{h}\left[n-k\right],}& \text{all }n& \left(5.47\right)\end{array}$$

Eqn. (5.47) is essentially an adaptation of the convolution sum to periodic signals where the limits of the summation are modified to cover only one period (we are assuming that both $\tilde{x}\left[n\right]$ and $\tilde{h}\left[n\right]$ have the same period N). It can be shown that (see Problem 5.7) the periodic convolution of two signals $\tilde{x}\left[n\right]$ and $\tilde{h}\left[n\right]$ that are both periodic with N is also periodic with the same period.

Example 5.8: Periodic convolution

Two signals $\tilde{x}\left[n\right]$ and $\tilde{h}\left[n\right]$, each periodic with N = 5 samples, are shown in Fig. 5.7(a) and (b). Determine the periodic convolution

$$\begin{array}{ll}\tilde{y}\left[n\right]=\tilde{x}\left[n\right]\otimes \tilde{h}\left[n\right]& \left(5.48\right)\end{array}$$

Solution: Sample amplitudes for one period are

$$\tilde{x}\left[n\right]=\left\{\mathrm{...},\underset{\stackrel{\uparrow }{n=0}}{0},1,2,3,4,\mathrm{...}\right\}$$

and

$$\tilde{h}\left[n\right]=\left\{\mathrm{...},\underset{\stackrel{\uparrow }{n=0}}{3},3,-3,-2,-1,\mathrm{...}\right\}$$

The periodic convolution is given by

$$\tilde{y}\left[n\right]={\displaystyle \sum _{k=0}^4\tilde{x}\left[k\right]\tilde{h}\left[n-k\right]}$$

To start, let n = 0. The terms $\tilde{x}\left[k\right]$ and $\tilde{h}\left[0-k\right]$ are shown in Fig. 5.8. The main period of each signal is indicated with sample amplitudes colored blue. The shaded area contains the terms included in the summation for periodic convolution. The sample $\tilde{y}\left[0\right]$ is computed as

$$\begin{array}{ll}\tilde{y}[0]\hfill & =\tilde{x}[0]\tilde{h}[0]+\tilde{x}[1]\tilde{h}[4]+\tilde{x}[2]\tilde{h}[3]+\tilde{x}[3]\tilde{h}[2]+\tilde{x}[4]\tilde{h}[1]\hfill \\ \hfill & =(0)(3)+(1)(-1)+(2)(-3)+(3)(-3)+(4)(4)=-2\hfill \end{array}$$

Next we will set n = 1. The terms $\tilde{x}\left[k\right]$ and $\tilde{h}\left[1-k\right]$ are shown in Fig. 5.9.

The sample $\tilde{y}\left[1\right]$ is computed as

$$\begin{array}{ll}\tilde{y}[1]\hfill & =\tilde{x}[0]\tilde{h}[1]+\tilde{x}[1]\tilde{h}[0]+\tilde{x}[2]\tilde{h}[4]+\tilde{x}[3]\tilde{h}[3]+\tilde{x}[4]\tilde{h}[2]\hfill \\ \hfill & =(0)(3)+(1)(3)+(2)(-1)+(3)(-2)+(4)(-3)=-17\hfill \end{array}$$

Finally, for n = 2 the terms involved in the summation are shown in Fig. 5.10.

The sample $\tilde{y}\left[2\right]$ is computed as

$$\begin{array}{ll}\tilde{y}[2]\hfill & =\tilde{x}[0]\tilde{h}[2]+\tilde{x}[1]\tilde{h}[1]+\tilde{x}[2]\tilde{h}[0]+\tilde{x}[3]\tilde{h}[4]+\tilde{x}[4]\tilde{h}[3]\hfill \\ \hfill & =(0)(-3)+(1)(3)+(2)(3)+(3)(-1)+(4)(-2)=-2\hfill \end{array}$$

Continuing in this fashion, it can be shown that $\tilde{y}\left[3\right]=8$ and $\tilde{y}\left[4\right]=13$. Thus, one period of the signal $\tilde{y}\left[n\right]$ is

$$\tilde{y}\left[n\right]=\left\{\mathrm{...},-2,-17,-2,8,13,\mathrm{...}\right\}$$

The signal $\tilde{y}\left[n\right]$ is shown in Fig. 5.11.

The periodic convolution property of the discrete-time Fourier series can be stated as follows:

Example 5.9: Periodic convolution

Refer to the signals $\tilde{x}\left[n\right]$, $\tilde{h}\left[n\right]$and ˜y[n] of Example 5.8. The DTFS coefficients of $\tilde{x}\left[n\right]$ were determined in Example 5.4. Find the DTFS coefficients of $\tilde{h}\left[n\right]$ and $\tilde{y}\left[n\right]$. Afterwards verify that the convolution property given by Eqn. (5.49) holds.

Solution: Let ${\tilde{c}}_k$, ${\tilde{d}}_k$ and ${\tilde{e}}_k$ represent the DTFS coefficients of $\tilde{x}\left[n\right]$, $\tilde{h}\left[n\right]$ and $\tilde{y}\left[n\right]$ respectively. Table 5.2 lists the DTFS coefficients for the three signals. It can easily be verified that

$$\begin{array}{ll}{\tilde{e}}_k=5{\tilde{c}}_k{\tilde{d}}_k,& k=0,\mathrm{...},4\end{array}$$

Software resources:

ex_5_9.m

5.3 Analysis of Non-Periodic Discrete-Time Signals

In the previous section we have focused on representing periodic discrete-time signals using complex exponential basis functions. The end result was the discrete-time Fourier series (DTFS) that allowed a signal periodic with a period of N samples to be constructed using N harmonically related exponential basis functions. In this section we extend the DTFS concept for use in non-periodic signals.

5.3.1 Discrete-time Fourier transform (DTFT)

In the derivation of the Fourier transform for non-periodic discrete-time signals we will take an approach similar to that employed in Chapter 4. Recall that in Section 4.3.1 a non-periodic continuous-time signal was viewed as a limit case of a periodic continuous-time signal, and the Fourier transform was derived from the exponential Fourier series. The resulting development is not a mathematically rigorous derivation of the Fourier transform, but it is intuitive. Let us begin by considering a non-periodic discrete-time signal x[n] as shown in Fig. 5.12.

Initially we will assume that x[n] is finite-length with its significant samples confined into the range −M ≤ n ≤ M of the index, that is, x[n]= 0 for n< −M and for n>M. A periodic extension $\tilde{x}\left[n\right]$ can be constructed by taking x[n] as one period in −M ≤ n ≤ M, and repeating it at intervals of 2M + 1 samples.

$$\begin{array}{ll}\tilde{x}\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }x\left[n+k\left(2M+1\right)\right]}& \left(5.56\right)\end{array}$$

This is illustrated in Fig. 5.13.

The periodic extension $\tilde{x}\left[n\right]$ can be expressed in terms of its DTFS coefficients. Using Eqn. (5.21) with N = 2M + 1 we obtain

$$\begin{array}{ll}\tilde{x}\left[n\right]={\displaystyle \sum _{k=0}^{2M}{\tilde{c}}_k{e}^{j\left(2\pi /2M+1\right)kn}}={\displaystyle \sum _{k=-M}^M{\tilde{c}}_k{e}^{j\left(2\pi /2M+1\right)kn}}& \left(5.57\right)\end{array}$$

The coefficients are computed through the use of Eqn. (5.22) as

$$\begin{array}{lll}{\tilde{c}}_k=\frac{1}{2M+1}{\displaystyle \sum _{n=-M}^M\tilde{x}\left[n\right]e^{-j\left(2\pi /2M+1\right)kn},}& k=-M,\mathrm{...},M& \left(5.58\right)\end{array}$$

Fundamental angular frequency is

$${\Omega }_0=\frac{2\pi }{2M+1}\text{radians}\text{.}$$

The k-th DTFS coefficient is associated with the angular frequency Ωk = kΩ0 = 2πk/ (2M + 1). The set of DTFS coefficients span the range of discrete frequencies

$$\begin{array}{lll}{\Omega }_k:& \frac{-2M}{2M+1}\pi ,\mathrm{...},0,\mathrm{...},\frac{2M}{2M+1}\pi & \left(5.59\right)\end{array}$$

It is worth noting that the set of coefficients in Eqn. (5.59) are roughly in the interval (−π, π), just slightly short of either end of the interval. Realizing that $\tilde{x}[n]=x\left[n\right]$ within the range −M ≤ n ≤ M, Eqn. (5.58) can be written using x[n] instead of $\tilde{x}\left[n\right]$ to yield

$$\begin{array}{lll}{\tilde{c}}_k=\frac{1}{2M+1}{\displaystyle \sum _{n=-M}^{M}x\left[n\right]e^{-j\left(2\pi /\left(2M+1\right)\right)kn}},& k=-M,\mathrm{...},M& \left(5.60\right)\end{array}$$

If we were to stretch out the period of the signal by increasing the value of M, then $\tilde{x}\left[n\right]$ would start to resemble x[n] more and more. Other effects of increasing M would be an increase in the coefficient count and a decrease in the magnitudes of the coefficients ${\tilde{c}}_k$ due to the 1/(2M + 1) factor in front of the summation. Let us multiply both sides of Eqn. (5.60) by 2M + 1 to obtain

$$\begin{array}{ll}\left(2M+1\right){\tilde{c}}_k={\displaystyle \sum _{n=-M}^{M}x\left[n\right]e^{-j\left(2\pi /\left(2M+1\right)\right)kn}}& \left(5.61\right)\end{array}$$

As M becomes very large, the fundamental angular frequency Ω0 becomes very small, and the spectral lines get closer to each other in the frequency domain, resembling a continuous transform.

$$\begin{array}{llll}M\to \infty & \text{implies that}& {\Omega }_0=\frac{2\pi }{2M+1}\to \Delta \Omega \text{ and }k\Delta \Omega \to \Omega & \left(5.62\right)\end{array}$$

In Eqn. (5.62) we have switched the notation from Ω0 to ΔΩ due to the infinitesimal nature of the fundamental angular frequency. In the limit we have

$$\begin{array}{ll}\underset{M\to \infty }{\lim }\left[\tilde{x}\left[n\right]\right]=x\left[n\right]& \left(5.63\right)\end{array}$$

in the time domain. Using the substitutions 2πk/(2M +1) → Ω and $\left(2M+1\right){\tilde{c}}_k\to X\left(\Omega \right)$ Eqn. (5.61) becomes

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{n=-\infty }^{\infty }x\left[n\right]e^{-j\Omega n}}& \left(5.64\right)\end{array}$$

The result in Eqn. (5.64) is referred to as the discrete-time Fourier transform (DTFT) of the signal x[n]. In deriving this result we assumed a finite-length signal x[n], the samples of which are confined into the range −M ≤ n ≤ M, and then took the limit as M →∞. Would Eqn. (5.64) still be valid for an infinite-length x[n]? The answer is yes, provided that the summation in Eqn. (5.64) converges.

Next we will try to develop some insight about the meaning of the transform X (Ω). Let us apply the limit operation to the periodic extension signal $\tilde{x}\left[n\right]$ defined in Eqn. (5.57).

$$\begin{array}{ll}x\left[n\right]=\underset{M\to \infty }{\lim }\left[\tilde{x}\left[n\right]\right]=\underset{M\to \infty }{\lim }\left[{\displaystyle \sum _{k=-M}^M{\tilde{c}}_k{e}^{j\left(2\pi /\left(2M+1\right)\right)kn}}\right]& \left(5.65\right)\end{array}$$

For large M we have from Eqn. (5.62)

$$\begin{array}{ll}\frac{\left(2M+1\right)\Delta \Omega }{2\pi }\to 1& \left(5.66\right)\end{array}$$

Using this result in Eqn. (5.65) leads to

$$\begin{array}{ll}x\left[n\right]=\underset{M\to \infty }{\lim }\left[{\displaystyle \sum _{k=-M}^M\left(2M+1\right){\tilde{c}}_k{e}^{jk\Delta \Omega n}\frac{\Delta \Omega }{2\pi }}\right]& \left(5.67\right)\end{array}$$

In the limit we have

$$\begin{array}{lll}\left(2M+1\right){\tilde{c}}_k\to X\left(\Omega \right),& k\Delta \Omega \to \Omega \text{ and }\Delta \Omega \to d\Omega & \left(5.68\right)\end{array}$$

Furthermore, the summation turns into an integral to yield

$$\begin{array}{ll}x\left[n\right]=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }X\left(\Omega \right)e^{j\Omega n}d\Omega }& \left(5.69\right)\end{array}$$

This result explains how the transform X (Ω) can be used for constructing the signal x[n]. We can interpret the integral in Eqn. (5.69) as a continuous sum of complex exponentials at harmonic frequencies that are infinitesimally close to each other.

In summary, we have derived a transform relationship between x[n] and X (Ω) through the following equations:

Often we will use the Fourier transform operator F and its inverse F−1 in a shorthand notation as

$$\begin{array}{ll}X\left(\Omega \right)=F\left\{x\left[n\right]\right\}& \left(5.72\right)\end{array}$$

for the forward transform, and

$$\begin{array}{ll}x\left[n\right]=F^{-1}\left\{X\left[\Omega \right]\right\}& \left(5.73\right)\end{array}$$

for the inverse transform. Sometimes we will use an even more compact notation to express the relationship between x[n] and X(Ω) by

$$\begin{array}{ll}x\left[n\right]\stackrel{F}{\leftrightarrow }X\left(\Omega \right)& \left(5.74\right)\end{array}$$

In general, the Fourier transform, as computed by Eqn. (5.71), is a complex function of Ω. It can be written in Cartesian form as

$$\begin{array}{ll}X\left(\Omega \right)=X_r\left(\Omega \right)+j{X}_i\left(\Omega \right)& \left(5.75\right)\end{array}$$

or in polar form as

$$\begin{array}{ll}X\left(\Omega \right)=\left|X\left(\Omega \right)\right|e^{j\measuredangle X\left(\Omega \right)}& \left(5.76\right)\end{array}$$

5.3.2 Developing further insight

In this section we will build on the idea of obtaining the DTFT as the limit case of DTFS coefficients when the signal period is made very large. Consider a discrete-time pulse with 7 unit-amplitude samples as shown in Fig. 5.14.

The analytical definition of x[n] is

$$\begin{array}{ll}x\left[n\right]=\{\begin{array}{ll}1,\hfill & n=-3,\mathrm{...},3\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}& \left(5.77\right)\end{array}$$

Let the signal $\tilde{x}\left[n\right]$ be defined as the periodic extension of x[n] with a period of 2M + 1 samples so that

$$\begin{array}{ll}\tilde{x}\left[n\right]={\displaystyle \sum _{r=-\infty }^{\infty }x\left[n+r\left(2M+1\right)\right]}& \left(5.78\right)\end{array}$$

as shown in Fig. 5.15.

One period of $\tilde{x}\left[n\right]$ extends from n = −M to n = M for a total of 2M + 1 samples. The general expression for DTFS coefficients can be found by adapting the result obtained in Example 5.5 to the signal $\tilde{x}\left[n\right]$ with L = 3 and N = 2M + 1:

$$\begin{array}{ll}{\tilde{c}}_k=\frac{\sin \left(7k{\Omega }_0/2\right)}{\left(2M+1\right)\sin \left(k{\Omega }_0/2\right)}& \left(5.79\right)\end{array}$$

The parameter Ω0 is the fundamental angular frequency given by

$$\begin{array}{ll}{\Omega }_0=\frac{2\pi }{2M+1}\text{ rad}\text{.}& \left(5.80\right)\end{array}$$

Let us multiply both sides of Eqn. (5.79) by (2M + 1) and write the scaled DTFS coefficients as

$$\begin{array}{ll}\left(2M+1\right){\tilde{c}}_k=\frac{\sin \left(7k{\Omega }_0/2\right)}{\sin \left(k{\Omega }_0/2\right)}& \left(5.81\right)\end{array}$$

Let M = 8 corresponding to a period length of 2M + 1 = 17. The scaled DTFS coefficients are shown in Fig. 5.16(a) for the index range k = −8,..., 8. In addition, the outline (or the envelope) of the scaled DTFS coefficients is also shown.

In Fig. 5.16(a) the leftmost coefficient has the index k = −8, and is associated with the angular frequency −8Ω0 = −16π/17. Similarly, the rightmost coefficient is at k = 8, and is associated with the angular frequency 8Ω0 = 16π/17. Fig. 5.16(b) shows the same coefficients and envelope as functions of the angular frequency Ω instead of the integer index k.

It is interesting to check the locations for the zero crossings of the envelope. The first positive zero crossing of the envelope occurs at the index value

$$\begin{array}{llll}\frac{7k{\Omega }_0}{2}=\pi & \Rightarrow & k=\frac{2\pi }{7{\Omega }_0}=\frac{2M+1}{7}& \left(5.82\right)\end{array}$$

which may or may not be an integer. For M = 8 the first positive zero crossing is at index value k = 17/7= 2.43 as shown in Fig. 5.16(a). This corresponds to the angular frequency (17/7) Ω0 = 2π/7 radians, independent of the value of M.

If we increase the period M, the following changes occur in the scaled DTFS spectrum:

1. The number of DTFS coefficients increases since the total number of unique DTFS coefficients is the same as the period length of $\tilde{x}\left[n\right]$ which, in this case, is 2M + 1.
2. The fundamental angular frequency decreases since it is inversely proportional to the period of $\tilde{x}\left[n\right]$. The spectral lines in Fig. 5.16(b) move in closer to each other.
3. The leftmost and the rightmost spectral lines get closer to ±π since they are ±MΩ0 = ±2Mπ/(2M +1).
4. As M →∞ the fundamental angular frequency becomes infinitesimally small, and the spectral lines come together to form a continuous transform.

We can conclude from the foregoing development that, as the period becomes infinitely large, spectral lines of the DTFS representation of $\tilde{x}\left[n\right]$ converge to a continuous function of Ω to form the DTFT of x[n]. Taking the limit of Eqn. (5.81) we get

$$\begin{array}{ll}X\left(\Omega \right)=\underset{M\to \infty }{\lim }\left[\left(2M+1\right){\tilde{c}}_k\right]=\frac{\sin \left(7\Omega /2\right)}{\sin \left(\Omega /2\right)}& \left(5.83\right)\end{array}$$

We will also obtain this result in Example 5.12 through direct application of the DTFT equation.

5.3.3 Existence of the DTFT

A mathematically thorough treatment of the conditions for the existence of the DTFT is beyond the scope of this text. It will suffice to say, however, that the question of existence is a simple one for the types of signals we encounter in engineering practice. A sufficient condition for the convergence of Eqn. (5.71) is that the signal x[n] be absolute summable, that is,

$$\begin{array}{ll}{\displaystyle \sum _{n=-\infty }^{\infty }\left|x\left[n\right]\right|<\infty }& \left(5.84\right)\end{array}$$

Alternatively, it is also sufficient for the signal x[n] to be square-summable:

$$\begin{array}{ll}{\displaystyle \sum _{n=-\infty }^{\infty }{\left|x\left[n\right]\right|}^2<\infty }& \left(5.85\right)\end{array}$$

In addition, we will see in the next section that some signals that do not satisfy either condition may still have a DTFT if we are willing to resort to the use of singularity functions in the transform.

5.3.4 DTFT of some signals

In this section we present examples of determining the DTFT for a variety of discrete-time signals.

Example 5.10: DTFT of right-sided exponential signal

Determine the DTFT of the signal x[n]= αn u[n] as shown in Fig. 5.18. Assume |α| < 1.

Solution: The use of the DTFT analysis equation given by Eqn. (5.71) yields

$$X\left(\Omega \right)={\displaystyle \sum _{n=-\infty }^{\infty }{\alpha }^{n}u\left[n\right]e^{-j\Omega n}}$$

The factor u[n] causes terms of the summation for n< 0 to equal zero. Consequently, we can start the summation at n = 0 and drop the term u[n] to write

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{n=0}^{\infty }{\alpha }^n{e}^{-j\Omega n}}=\frac{1}{1-\alpha e^{-j\Omega }}& \left(5.86\right)\end{array}$$

provided that |α| < 1. In obtaining the result in Eqn. (5.86) we have used the closed form of the sum of infinite-length geometric series (see Appendix C). The magnitude of the transform is

$$\left|X\left(\Omega \right)\right|=\frac{1}{\left|1-\alpha e^{-j\Omega }\right|}=\frac{1}{\sqrt{1+{\alpha }^2-2\alpha \cos \left(\Omega \right)}}$$

The phase of the transform is found as the difference of the phases of numerator and denominator of the result in Eqn. (5.86):

$$\measuredangle X\left(\Omega \right)=0-\measuredangle \left(1-\alpha e^{-j\Omega }\right)=-{\tan }^{-1}\left[\frac{\alpha \sin \left(\Omega \right)}{1-\alpha \cos \left(\Omega \right)}\right]$$

The magnitude and the phase of the transform are shown in Fig. 5.19(a) and (b) for the case α = 0.4.

Software resources:

ex_5_10.m

Example 5.11: DTFT of unit-impulse signal

Determine the DTFT of the unit-impulse signal x[n] = δ[n].

Solution: Direct application of Eqn. (5.71) yields

$$\begin{array}{ll}F\left\{\delta \left[n\right]\right\}={\displaystyle \sum _{n=-\infty }^{\infty }\delta \left[n\right]e^{-j\Omega n}}& \left(5.87\right)\end{array}$$

Using the sifting property of the impulse function, Eqn. (5.87) reduces to

$$\begin{array}{ll}F\left\{\delta \left[n\right]\right\}=1,\text{ all }\Omega & \left(5.88\right)\end{array}$$

Example 5.12: DTFT for discrete-time pulse

Determine the DTFT of the discrete-time pulse signal x[n] given by

$$x\left[n\right]=\{\begin{array}{ll}1,& -L\le n\le L\\ 0,& \text{otherwise}\end{array}$$

Solution: Using Eqn. (5.71) the transform is

$$X\left(\Omega \right)={\displaystyle \sum _{n=-L}^L\left(1\right)e^{-j\Omega n}}$$

The closed form expression for a finite-length geometric series is (see Appendix C for derivation)

$$\begin{array}{ll}\text{Eqn}\text{. }\left(\text{C}.13\right):& {\displaystyle \sum _{n=L_1}^{L_2}{a}^n=\frac{a^{L_1}-a^{L_2+1}}{1-a}}\end{array}$$

Using Eqn. (C.13) with a = e−jΩ, L1 = −L and L2 = L, the closed form expression for X (Ω) is

$$\begin{array}{ll}X\left(\Omega \right)=\frac{e^{j\Omega L}-e^{-j\Omega \left(L+1\right)}}{1-e^{-j\Omega }}& \left(5.89\right)\end{array}$$

In order to get symmetric complex exponentials in Eqn. (5.89) we will multiply both the numerator and the denominator of the fraction on the right side of the equal sign with ejΩ/2. The result is

$$X\left(\Omega \right)=\frac{e^{j\Omega \left(L+1/2\right)}-e^{-j\Omega \left(L+1/2\right)}}{e^{j\Omega /2}-e^{-j\Omega /2}}$$

which, using Euler’s formula, can be simplified to

$$X\left(\Omega \right)=\frac{\sin \left(\frac{\Omega }{2}\left(2L+1\right)\right)}{\sin \left(\frac{\Omega }{2}\right)}$$

The value of the transform at Ω = 0 must be resolved through the use of L’Hospital’s rule:

$$X\left(0\right)=2L+1$$

The transform X (Ω) is graphed in Fig. 5.20 for L = 3, 4, 5.

Software resources:

ex_5_12.m

Example 5.13: Inverse DTFT of rectangular spectrum

Determine the inverse DTFT of the transform X (Ω) defined in the angular frequency range −π< Ω <π by

$$X\left(\Omega \right)=\{\begin{array}{ll}1,\hfill & -{\Omega }_c<\Omega <{\Omega }_c\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

Solution: To be a valid transform, X(Ω) must be 2π-periodic, therefore we need X(Ω) = X(Ω + 2π). The resulting transform is shown in Fig. 5.21.

The inverse x[n] is found by application of the DTFT synthesis equation given by Eqn. (5.70).

$$\begin{array}{ll}x\left[n\right]=\frac{1}{2\pi }{\displaystyle {\int }_{-{\Omega }_0}^{{\Omega }_0}\left(1\right)e^{j\Omega n}d\Omega =\frac{\sin \left({\Omega }_{c}n\right)}{\pi n}}& \left(5.90\right)\end{array}$$

It should be noted that the expression found in Eqn. (5.90) for the signal x[n] is for all n; therefore, x[n] is non-causal. For convenience let us use the normalized frequency Fc related to the angular frequency Ωc by

$${\Omega }_c=2\pi F_c$$

and the signal x[n] becomes

$$x\left[n\right]=2F_c\sin c\left(2F_{c}n\right)$$

The result is shown in Fig. 5.22 for the case Fc = 1/9. Zero crossings of the sinc function in Eqn. (5.91) are spaced 1/(2Fc) apart which has the non-integer value of 4.5 in this case. Therefore, the envelope of the signal x[n] crosses the axis at the midpoint of the samples for n = 4 and n = 5.

Software resources:

ex_5_13.m

Example 5.14: Inverse DTFT of the unit-impulse function

Find the signal the DTFT of which is X(Ω) = δ(Ω) in the range −π< Ω <π.

Solution: To be a valid DTFT, the transform X(Ω) must be 2π-periodic. Therefore, the full expression for X(Ω) must be

$$X\left(\Omega \right)={\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -2\pi m\right)}$$

as shown in Fig. 5.23.

The inverse transform is

$$x\left[n\right]=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }\delta \left(\Omega \right)e^{j\Omega n}d\Omega }$$

Using the sifting property of the impulse function we get

$$\begin{array}{ll}x\left[n\right]=\frac{1}{2\pi },& \text{all }n\end{array}$$

Thus we have the DTFT pair

$$\begin{array}{ll}\frac{1}{2\pi }\stackrel{F}{\leftrightarrow }{\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -2\pi m\right)}& \left(5.91\right)\end{array}$$

An important observation is in order: A signal that has constant amplitude for all index values is a power signal; it is neither absolute summable nor square summable. Strictly speaking, its DTFT does not converge. The transform relationship found in Eqn. (5.91) is a compromise made possible by our willingness to allow the use of singularity functions in X (Ω). Nevertheless, it is a useful relationship since it can be used in solving problems in the frequency domain.

Multiplying both sides of the relationship in Eqn. (5.91) by 2π results in

$$\begin{array}{ll}F\left\{1\right\}=2\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -2\pi m\right)}& \left(5.92\right)\end{array}$$

which is illustrated in Fig. 5.24. This relationship is fundamental, and will be explored further in the next example.

Example 5.15: Inverse DTFT of impulse function revisited

Consider again the DTFT transform pair found in Eqn. (5.92) of Example 5.14. The unit-amplitude signal x[n] = 1 can be thought of as the limit of the rectangular pulse signal explored in Example 5.12. Let

$$\begin{array}{lll}x\left[n\right]=1,\text{ all }n& \text{and}& \omega \left[n\right]\{\begin{array}{ll}1,\hfill & -L\le n\le L\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}\end{array}$$

so that

$$x\left[n\right]=\underset{L\to \infty }{\lim }\left[\omega \left[n\right]\right]$$

Adapting from Example 5.12, the transform of w[n] is

$$W\left(\Omega \right)=\frac{\sin \left(\frac{\Omega }{2}\left(2L+1\right)\right)}{\sin \left(\frac{\Omega }{2}\right)}$$

and the transform of x[n] was found in Example 5.14 to be

$$X\left(\Omega \right)=2\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -2\pi m\right)}$$

Intuitively we would expect W(Ω) to resemble X(Ω) more and more closely as L is increased. Fig. 5.25 shows the transform W (Ω) for L = 10, 20, and 50. Observe the transition from W (Ω) to X (Ω) as L is increased.

Software resources:

ex_5_15.m

5.3.5 Properties of the DTFT

In this section we will explore some of the fundamental properties of the DTFT. As in the case of the Fourier transform for continuous-time signals, careful use of DTFT properties simplifies the solution of many types of problems.

Periodicity

Periodicity of the DTFT is a direct consequence of the analysis equation given by Eqn. (5.71).

Linearity

DTFT is a linear transform.

Time shifting

The consequence of shifting, or delaying, a signal in time is multiplication of its DTFT by a complex exponential function of angular frequency.

Example 5.16: DTFT of a time-shifted signal

Determine the DTFT of the signal x[n] = e−α(n−1) u[n − 1] as shown in Fig. 5.26. (Assume |α| < 1).

Solution: The transform of a right-sided exponential signal was determined in Example 5.10.

As a result we have the transform pair

$$e^{-\alpha n}u\left[n\right]\stackrel{F}{\leftrightarrow }\frac{1}{1-\alpha e^{-j\Omega }}$$

Applying the time shifting property of the DTFT given by Eqn. (5.96) with m = 1 leads to the result

$$X\left(\Omega \right)=F\left\{e^{-\alpha \left(n-1\right)}u\left[n-1\right]\right\}=\frac{e^{-j\Omega }}{1-\alpha e^{-j\Omega }}$$

Since |e−jΩ| = 1, the magnitude of X(Ω) is the same as that obtained in Example 5.10. Time shifting a signal does not change the magnitude of its transform.

$$\left|X\left(\Omega \right)\right|=\frac{1}{\sqrt{1+{\alpha }^2-2\alpha \cos \left(\Omega \right)}}$$

The magnitude |X (Ω)| is shown in Fig. 5.27(a) for α = 0.4. The phase of X(Ω) is found by first determining the phase angles of the numerator and the denominator, and then subtracting the latter from the former. In Example 5.10 the numerator of the transform was a constant equal to unity; in this case it is a complex exponential. Therefore

$$\begin{array}{lll}\measuredangle X(\Omega )\hfill & =\measuredangle (e^{-j\Omega })-\measuredangle (1-\alpha e^{-j\Omega })\hfill & \hfill \\ \hfill & =-\Omega -{\tan }^{-1}[\frac{\alpha \sin (\Omega )}{1-\alpha \cos (\Omega )}]\hfill & (5.100)\hfill \end{array}$$

Thus, the phase of the transform differs from that obtained in Example 5.10 by −Ω, a ramp with a slope of −1. The phase, as computed by Eqn. (5.100), is shown in Fig. 5.27(b). In graphing the phase of the transform it is customary to fit phase values to in the range (−π, π) radians. Fig. 5.27(c) depicts the phase of the transform in the more traditional form.

Software resources:

ex_5_16.m

Time reversal

Time reversal of the signal causes angular frequency reversal of the transform. This property will be useful when we consider symmetry properties of the DTFT.

Example 5.17: DTFT of two-sided exponential signal

Determine the DTFT of the signal x[n] = α|n| with |α| < 1.

Solution: The signal x[n] can be written as

$$x\left[n\right]=\{\begin{array}{ll}{\alpha }^n,& n\ge 0\\ {\alpha }^{-n},& n<0\end{array}$$

It can also be expressed as

$$x\left[n\right]=x_1\left[n\right]+x_2\left[n\right]$$

where x1[n] is a causal signal and x2[n] is an anti-causal signal defined as

$$\begin{array}{lll}{x}_1\left[n\right]={\alpha }^{n}u\left[n\right]& \text{and}& x_2\left[n\right]={\alpha }^{-n}u\left[-n-1\right]\end{array}$$

This is illustrated in Fig. 5.28.

Based on the linearity property of the DTFT, the transform of x[n] is the sum of the transforms of x1[n] and x2[n].

$$X\left(\Omega \right)=X_1\left(\Omega \right)+X_2\left(\Omega \right)$$

For the transform of x1 = αnu[n] we will make use of the result obtained in Example 5.10.

$$X_1\left(\Omega \right)=\frac{1}{1-\alpha e^{-j\Omega }}$$

Time shifting and time reversal properties of the DTFT will be used for obtaining the transform of x2[n]. Let a new signal g[n] be defined as a scaled and time-shifted version of x1[n]:

$$g\left[n\right]=\alpha x_1\left[n-1\right]=\alpha \left({\alpha }^{n-1}u\left[n-1\right]\right)={\alpha }^{n}u\left[n-1\right]$$

Using the time shifting property, the transform of g[n] is

$$G\left(\Omega \right)=\alpha X\left(\Omega \right)e^{-j\Omega }=\frac{\alpha e^{-j\Omega }}{1-\alpha e^{-j\Omega }}$$

The signal x2[n] is a time reversed version of g[n], that is,

$$x_2\left[n\right]=g\left[-n\right]$$

Applying the time reversal property, the transform of x2[n] is found as

$$x_2\left[n\right]=G\left(-\Omega \right)=\frac{\alpha e^{j\Omega }}{1-\alpha e^{j\Omega }}$$

Finally, X (Ω) is found by adding the two transforms:

$$\begin{array}{lll}X(\Omega )\hfill & =\frac{1}{1-\alpha e^{-j\Omega }}+\frac{\alpha e^{j\Omega }}{1-\alpha e^{j\Omega }}\hfill & \hfill \\ \hfill & =\frac{1-{\alpha }^2}{1-2\alpha \cos (\Omega )+{\alpha }^2}\hfill & (5.105)\hfill \end{array}$$

The transform X(Ω) obtained in Eqn. (5.105) is real-valued, and is shown in Fig. 5.29 for α = 0.4.

Software resources:

ex_5_17.m

Conjugation property

Conjugation of the signal causes both conjugation and angular frequency reversal of the transform. This property will also be useful when we consider symmetry properties of the DTFT.

Symmetry of the DTFT

If the signal x[n] is real-valued, it can be shown that its DTFT is conjugate symmetric. Conversely, if the signal x[n] is purely imaginary, its transform is conjugate antisymmetric.

Cartesian and polar forms of the transform

A complex transform X(Ω) can be written in polar form as

$$\begin{array}{ll}X\left(\Omega \right)=\left|X\left(\Omega \right)\right|e^{j\Theta \left(\Omega \right)}& \left(5.115\right)\end{array}$$

and in Cartesian form as

$$\begin{array}{ll}X\left(\Omega \right)=X_r\left(\Omega \right)+j{X}_i\left(\Omega \right)& \left(5.116\right)\end{array}$$

Case 1: If X (Ω) is conjugate symmetric, the relationship in Eqn. (5.109) can be written as

$$\begin{array}{ll}\left|X\left(-\Omega \right)\right|e^{j\Theta \left(-\Omega \right)}=\left|X\left(\Omega \right)\right|e^{-j\Theta \left(\Omega \right)}& \left(5.117\right)\end{array}$$

using the polar form of the transform, and

$$\begin{array}{ll}{X}_r\left(-\Omega \right)+j{X}_i\left(-\Omega \right)=X_r\left(\Omega \right)-j{X}_i\left(\Omega \right)& \left(5.118\right)\end{array}$$

using its Cartesian form. The consequences of Equation (5.117) Equation (5.118) can be obtained by equating the magnitudes and the phases on both sides of Eqn. (5.117) and by equating real and imaginary part on both sides of Eqn. (5.118). The results are summarized below:

The transform of a real-valued x[n] is conjugate symmetric. For such a transform, the magnitude is an even function of Ω, and the phase is an odd function. Furthermore, the real part of the transform has even symmetry, and its imaginary part has odd symmetry.

Case 2: If X(Ω) is conjugate antisymmetric, the polar form of X(Ω) has the property

$$\begin{array}{ll}\left|X\left(-\Omega \right)\right|e^{j\Theta \left(-\Omega \right)}=-\left|X\left(\Omega \right)\right|e^{-j\Theta \left(\Omega \right)}& \left(5.123\right)\end{array}$$

The negative sign on the right side of Eqn. (5.123) needs to be incorporated into the phase since we could not write |X(−Ω)| = −|X(Ω)| (recall that magnitude needs to be a non-negative function for all Ω). Using e∓jπ = −1, Eqn. (5.123) can be written as

$$\begin{array}{lll}|X(-\Omega )|e^{j\Theta (-\Omega )}\hfill & =|X(\Omega )|e^{-j\Theta (\Omega )}{e}^{\mp j\pi }\hfill & \hfill \\ \hfill & =|X(\Omega )|e^{-j[\Theta (\Omega )\mp \pi ]}\hfill & (5.124)\hfill \end{array}$$

Conjugate antisymmetry property of the transform can also be expressed in Cartesian form as

$$\begin{array}{ll}{X}_r\left(-\Omega \right)+j{X}_i\left(-\Omega \right)=-X_r\left(\Omega \right)+j{X}_i\left(\Omega \right)& \left(5.125\right)\end{array}$$

The consequences of Equation (5.124) and Equation (5.125) are given below.

We know that a purely-imaginary signal leads to a DTFT that is conjugate antisymmetric. For such a transform the magnitude is still an even function of Ω as suggested by Eqn. (5.126). The phase is neither even nor odd. The real part is an odd function of Ω, and the imaginary part is an even function.

Transforms of even and odd signals

If the real-valued signal x[n] is an even function of time, the resulting transform X(Ω) is real-valued for all Ω.

$$\begin{array}{llll}x\left[-n\right]=x\left[n\right],\text{ all }n& \text{implies that}& \mathrm{Im}\left\{X\left(\Omega \right)\right\}=0,\text{ all }\Omega & \left(5.130\right)\end{array}$$

Conversely it can also be proven that, if the real-valued signal x[n] has odd-symmetry, the resulting transform is purely imaginary. This can be stated mathematically as follows:

Conjugating a purely imaginary transform is equivalent to negating it, so an alternative method of expressing the relationship in Eqn. (5.134) is

$$\begin{array}{ll}{X}^{*}\left(\Omega \right)=-X\left(\Omega \right)& \left(5.135\right)\end{array}$$

Proof of Eqn. (5.135) is similar to the procedure used above for proving Eqn. (5.130) (see Problem 5.14 at the end of this chapter).

Frequency shifting

Modulation property

Modulation property is an interesting consequence of the frequency shifting property combined with the linearity of the Fourier transform. Multiplication of a signal by a cosine waveform causes its spectrum to be shifted in both directions by the angular frequency of the cosine waveform, and to be scaled by $\frac{1}{2}$. Multiplication of the signal by a sine waveform causes a similar effect with an added phase shift of −π/2 radians for positive frequencies and π/2 radians for negative frequencies.

Differentiation in the frequency domain

Example 5.18: Use of differentiation in frequency property

Determine the DTFT of the signal x[n] = ne−αn u[n] shown in Fig. 5.30. Assume |α| < 1.

Solution: In Example 5.10 we have established the following transform pair:

$$e^{-\alpha n}u\left[n\right]\stackrel{F}{\leftrightarrow }\frac{1}{1-\alpha e^{-j\Omega }}$$

Applying the differentiation in frequency property of the DTFT leads to

$$n{e}^{-\alpha n}u\left[n\right]\stackrel{F}{\leftrightarrow }j\frac{d}{d\Omega }\left[\frac{1}{1-\alpha e^{-j\Omega }}\right]$$

Differentiation is carried out easily:

$$\begin{array}{ll}\frac{d}{d\Omega }[\frac{1}{1-\alpha e^{-j\Omega }}]\hfill & =\frac{d}{d\Omega }[{(1-\alpha e^{-j\Omega })}^{-1}]\hfill \\ \hfill & =-{(1-\alpha e^{-j\Omega })}^{-2}(j\alpha e^{-j\Omega })\hfill \end{array}$$

and the transform we seek is

$$X\left(\Omega \right)=\frac{\alpha e^{-j\Omega }}{{\left(1-\alpha e^{-j\Omega }\right)}^2}$$

The magnitude and the phase of the transform X(Ω) are shown in Fig. 5.31(a) and (b) for the case α = 0.4.

Software resources:

ex_5_18.m

Convolution property

Convolving two signals in the time domain corresponds to multiplying the corresponding transforms in the frequency domain.

Example 5.19: Convolution using the DTFT

Two signals are given as

$$\begin{array}{lll}h\left[n\right]={\left(\frac{2}{3}\right)}^{n}u\left(n\right)& \text{and}& x\left(n\right)={\left(\frac{3}{4}\right)}^{n}u\left(n\right)\end{array}$$

Determine the convolution y[n] = h[n] * x[n] of these two signals using the DTFT.

Solution: Transforms of H(Ω) and X(Ω) can easily be found using the result obtained in Example 5.10:

$$\begin{array}{ll}H\left(\Omega \right)=\frac{1}{1-\frac{2}{3}{e}^{-j\Omega }},& X\left(\Omega \right)=\frac{1}{1-\frac{3}{4}{e}^{-j\Omega }}\end{array}$$

Using the convolution property, the transform of y[n] is

$$\begin{array}{lll}Y(\Omega )\hfill & =H(\Omega )X(\Omega )\hfill & \hfill \\ \hfill & =\frac{1}{(1-\frac{2}{3}{e}^{-j\Omega })(1-\frac{3}{4}{e}^{-j\Omega })}\hfill & (5.153)\hfill \end{array}$$

The transform Y(Ω) found in Eqn. (5.153) can be written in the form

$$Y\left(\Omega \right)=\frac{-8}{1-\frac{2}{3}{e}^{-j\Omega }}+\frac{9}{1-\frac{3}{4}{e}^{-j\Omega }}$$

The convolution result y[n] is the inverse DTFT of Y(Ω) which can be obtained using the linearity property of the transform:

$$y\left(n\right)=-8{\left(\frac{2}{3}\right)}^{n}u\left[n\right]+9{\left(\frac{3}{4}\right)}^{n}u\left[n\right]$$

Solution of problems of this type will be more practical through the use of z-transform in Chapter 8.

Software resources:

ex_5_19.m

Multiplication of two signals

The DTFT of the product of two signals x1[n] and x2[n] is equal the 2π-periodic convolution of the individual transforms X1(Ω) and X2(Ω).

Table 5.3 contains a summary of key properties of the DTFT. Table 5.4 lists some of the fundamental DTFT pairs.

5.3.6 Applying DTFT to periodic signals

In previous sections of this chapter we have distinguished between two types of discrete-time signals: periodic and non-periodic. For periodic discrete-time signals we have the DTFS as an analysis and problem solving tool; for non-periodic discrete-time signals the DTFT serves a similar purpose. This arrangement will serve us adequately in cases where we work with one type of signal or the other. There may be times, however, when we need to mix periodic and non-periodic signals within one system. For example, in amplitude modulation, a non-periodic signal may be multiplied with a periodic signal, and we may need to analyze the resulting product in the frequency domain. Alternately, a periodic signal may be used as input to a system the impulse response of which is non-periodic. In these types of scenarios it would be convenient to find a way to use the DTFT for periodic signals as well. We have seen in Example 5.14 that a DTFT can be found for a constant-amplitude signal that does not satisfy the existence conditions, as long as we are willing to accept singularity functions in the transform. The next two examples will expand on this idea. Afterwards we will develop a technique for converting the DTFS of any periodic discrete-time signal to a DTFT.

Example 5.20: DTFT of complex exponential signal

Determine the transform of the complex exponential signal x[n] = ejΩ0n with −π < Ω0 < π.

Solution: The transform of the constant unit-amplitude signal was found in Example 5.14 to be

$$F\left(1\right)=2\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -2\pi m\right)}$$

Using this result along with the frequency shifting property of the DTFT given by Eqn. (5.136), the transform of the complex exponential signal is

$$\begin{array}{ll}F\left\{e^{j{\Omega }_{0}n}\right\}=2\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -2\pi m\right)}& \left(5.160\right)\end{array}$$

This is illustrated in Fig. 5.32.

Example 5.21: DTFT of sinusoidal signal

Determine the transform of the sinusoidal signal x[n] = cos(Ω0n) with −π < Ω0 < π.

Solution: The transform of the constant unit-amplitude signal was found in Example 5.14 to be

$$F\left\{1\right\}=2\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -2\pi m\right)}$$

Using this result along with the modulation property of the DTFT given by Eqn. (5.138), the transform of the sinusoidal signal is

$$\begin{array}{ll}F\left\{\cos \left({\Omega }_{0}n\right)\right\}=\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -{\Omega }_0-2\pi m\right)+\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega +{\Omega }_0-2\pi m\right)}}& \left(5.161\right)\end{array}$$

Let $\tilde{X}\left(\Omega \right)$ represent the part of the transform in the range −π < Ω < π.

$$\begin{array}{ll}\tilde{X}\left(\Omega \right)=\pi \delta \left(\Omega -{\Omega }_0\right)+\pi \delta \left(\Omega +{\Omega }_0\right)& \left(5.162\right)\end{array}$$

The DTFT can now be expressed as

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{m=-\infty }^{\infty }\tilde{X}\left(\Omega -2\pi m\right)}& \left(5.163\right)\end{array}$$

This is illustrated in Fig. 5.33.

In Examples 5.20 and 5.21 we were able to obtain the DTFT of two periodic signals, namely a complex exponential signal and a sinusoidal signal. The idea can be generalized to apply to any periodic discrete-time signal. The DTFS synthesis equation for a periodic signal $\tilde{x}\left[n\right]$ was given by Eqn. (5.21) which is repeated here for convenience:

$$\begin{array}{lll}\text{Eqn}\text{. }\left(5.21\right):& \tilde{x}\left[n\right]={\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k{e}^{j\left(2\pi /N\right)kn}},& \text{all }n\end{array}$$

If we were to attempt to find the DTFT of the signal $\tilde{x}\left[n\right]$ by direct application of the DTFT analysis equation given by Eqn. (5.71) we would need to evaluate

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{n=-\infty }^{\infty }\tilde{x}\left[n\right]e^{-j\Omega n}}& \left(5.164\right)\end{array}$$

Substituting Eqn. (5.21) into Eqn. (5.164) leads to

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{n=-\infty }^{\infty }\left[{\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k{e}^{j\left(2\pi /N\right)kn}}\right]e^{-j\Omega n}}& \left(5.165\right)\end{array}$$

Interchanging the order of the two summations in Eqn. (5.165) and rearranging terms we obtain

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k\left[{\displaystyle \sum _{n=-\infty }^{\infty }{e}^{j\left(2\pi /N\right)kn}}{e}^{-j\Omega n}\right]}& \left(5.166\right)\end{array}$$

In Eqn. (5.166) the expression in square brackets is the DTFT of the signal ej(2π/N)kn. Using the result obtained in Example 5.20, and remembering that 2π/N = Ω0 is the fundamental angular frequency for the periodic signal $\tilde{x}\left[n\right]$, we get

$$\begin{array}{lll}{\displaystyle \sum _{n=-\infty }^{\infty }{e}^{j\left(2\pi /N\right)kn}{e}^{-j\Omega n}}& =2\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -\frac{2\pi k}{N}-2\pi m\right)}& \\ & =2\pi {\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -k{\Omega }_0-2\pi m\right)}& \left(5.167\right)\end{array}$$

and

$$\begin{array}{ll}X\left(\Omega \right)=2\pi {\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k}{\displaystyle \sum _{m=-\infty }^{\infty }\delta \left(\Omega -k{\Omega }_0-2\pi m\right)}& \left(5.168\right)\end{array}$$

The part of the transform in the range 0 < Ω < 2π is found by setting m = 0 in Eqn. (5.168):

$$\begin{array}{ll}\tilde{X}\left(\Omega \right)=2\pi {\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k\delta \left(\Omega -k{\Omega }_0\right)}& \left(5.169\right)\end{array}$$

Thus, $\tilde{X}\left(\Omega \right)$ for a periodic discrete-time signal is obtained by converting each DTFS coefficient ${\tilde{c}}_k$ to an impulse with area equal to 2π${\tilde{c}}_k$ and placing it at angular frequency Ω = kΩ0. The DTFT for the signal is then obtained as

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{m=-\infty }^{\infty }\overline{X}\left(\Omega -2\pi m\right)}& \left(5.170\right)\end{array}$$

This process is illustrated in Fig. 5.34.

Note: In Eqn. (5.162) of Example 5.21 we have used $\overline{X}\left(\Omega \right)$ to represent the part of the transform in the range −π < Ω < π. On the other hand, in Eqn. (5.169) above, $\overline{X}\left(\Omega \right)$ was used as the part of the transform in the range 0 < Ω < 2π. This should not cause any confusion. In general, $\overline{X}\left(\Omega \right)$ represents one period of the 2π-periodic transform, and the starting value of Ω is not important.

Example 5.22: DTFT of the periodic signal of Example 5.4

Determine the DTFT of the signal x[n] used in Example 5.4 and shown in Fig. 5.3.

Solution: We will first write the transform in the interval 0 < Ω < 2π.

$$\overline{X}\left(\Omega \right)=2\pi \left[{\tilde{c}}_0\delta \left(\Omega \right)+{\tilde{c}}_1\delta \left(\Omega -{\Omega }_0\right)+{\tilde{c}}_2\delta \left(\Omega -2{\Omega }_0\right)+{\tilde{c}}_3\delta \left(\Omega -3{\Omega }_0\right)+{\tilde{c}}_4\delta \left(\Omega -4{\Omega }_0\right)\right]$$

The period of the signal $\tilde{x}\left[n\right]$ is N = 5, therefore the fundamental angular frequency is Ω0 = 2π/5. Using the values of DTFS coefficients found in Example 5.4 we obtain

$$\begin{array}{l}\overline{X}\left(\Omega \right)\hfill \\ =12.566\delta \left(\Omega \right)+\left(-3.142-j4.324\right)\delta \left(\Omega -2\pi /5\right)\hfill \\ \hfill & +\left(-3.142-j1.021\right)\delta \left(\Omega -4\pi /5\right)\hfill \\ \hfill & +\left(-3.142+j1.021\right)\delta \left(\Omega -6\pi /5\right)\hfill \\ \hfill & +\left(-3.142+j4.324\right)\delta \left(\Omega -8\pi /5\right)\hfill & \left(5.171\right)\end{array}$$

The complete transform X (Ω) is found by periodically extending $\overline{X}\left(\Omega \right)$.

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{m=-\infty }^{\infty }\left[12.566\delta \left(\Omega -2\pi m\right)+\left(-3.142-j4.324\right)\delta \left(\Omega -2\pi /5-2\pi m\right)+\left(-3.142-j1.021\right)\delta \left(\Omega -4\pi /5-2\pi m\right)+\left(-3.142+j1.021\right)\delta \left(\Omega -6\pi /5-2\pi m\right)+\left(-3.142+j1.021\right)\delta \left(\Omega -8\pi /5-2\pi m\right)\right]}& \left(5.172\right)\end{array}$$

5.4 Energy and Power in the Frequency Domain

Parseval’s theorem and its application to the development of energy and power spectral density concepts were discussed for continuous-time signals in Section 4.4 of Chapter 4. In this section we will discuss Parseval’s theorem for periodic and non-periodic discrete-time signals, and introduce the corresponding energy and power spectral density concepts.

5.4.1 Parseval’s theorem

The left side of Eqn. (5.173) represents the normalized average power in a periodic signal which was derived in Chapter 1 Eqn. (1.187). The left side of Eqn. (5.174) represents the normalized signal energy as derived in Eqn. (1.180). The relationships given by Equation (5.173) and Equation (5.174) relate signal energy or signal power to the frequency-domain representation of the signal. They are two forms of Parseval’s theorem.

5.4.2 Energy and power spectral density

The two statements of Parseval’s theorem given by Equation (5.173) and Equation (5.174) lead us to the following conclusions:

1. In Eqn. (5.173) the left side corresponds to the normalized average power of the periodic signal $\tilde{x}\left[n\right]$, and therefore the summation on the right side must also represent normalized average power. The term ${\left|{\tilde{c}}_k\right|}^2$ corresponds to the power of the signal component at angular frequency Ω = kΩ0. (Remember that Ω0 = 2π/N.) Let us construct a new function Sx (Ω) as follows:

   $$\begin{array}{ll}{S}_x\left(\Omega \right)={\displaystyle \sum _{k=\infty }^{\infty }2\pi {\left|{\tilde{c}}_k\right|}^2\delta \left(\Omega -k{\Omega }_0\right)}& \left(5.181\right)\end{array}$$

   The function Sx (Ω) consists of impulses placed at angular frequencies kΩ0 as illustrated in Fig. 5.35. Since the DTFS coefficients are periodic with period N, the function Sx(Ω) is 2π-periodic.

   Figure 5.35

   

   The function Sx (Ω) constructed using the DTFS coefficents of the signal $\tilde{x}\left[n\right]$.

   Integrating Sx (Ω) over an interval of 2π radians leads to

   $$\begin{array}{ll}{\displaystyle {\int }_0^{2\pi }{S}_x\left(\Omega \right)d\Omega }={\displaystyle {\int }_0^{2\pi }\left[{\displaystyle \sum _{k=-\infty }^{\infty }2\pi {\left|{\tilde{c}}_k\right|}^2\delta \left(\Omega -k{\Omega }_9\right)}\right]d\Omega }& \left(5.182\right)\end{array}$$

   Interchanging the order of integration and summation in Eqn. (5.182) and rearranging terms we obtain

   $$\begin{array}{ll}{\displaystyle {\int }_0^{2\pi }{S}_x\left(\Omega \right)d\Omega }=2\pi {\displaystyle \sum _{k=-\infty }^{\infty }{\left|{\tilde{c}}_k\right|}^2\left[{\displaystyle {\int }_0^{2\pi }\delta \left(\Omega -k{\Omega }_0\right)d\Omega }\right]}& \left(5.183\right)\end{array}$$

   Recall that Ω0 = 2π/N. Using the sifting property of the impulse function, the integral between square brackets in Eqn. (5.183) is evaluated as

   $$\begin{array}{ll}{\displaystyle {\int }_0^{2\pi }\delta \left(\Omega -k{\Omega }_0\right)}d\Omega =\{\begin{array}{ll}1,\hfill & k=0,\mathrm{...},N-1\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}& \left(5.184\right)\end{array}$$

   and Eqn. (5.183) becomes

   $$\begin{array}{ll}{\displaystyle {\int }_0^{2\pi }{S}_x\left(\Omega \right)d\Omega =2\pi {\displaystyle \sum _{k=0}^{N-1}{\left|{\tilde{c}}_k\right|}^2}}& \left(5.185\right)\end{array}$$

   The normalized average power of the signal $\tilde{x}\left[n\right]$ is therefore found as

   $$\begin{array}{ll}{P}_x={\displaystyle \sum _{k=0}^{N-1}{\left|{\tilde{c}}_k\right|}^2=\frac{1}{2\pi }{\displaystyle {\int }_0^{2\pi }{S}_x\left(\Omega \right)d\Omega }}& \left(5.186\right)\end{array}$$

   Consequently, the function Sx (Ω) is the power spectral density of the signal $\tilde{x}\left[n\right]$. Since Sx (Ω) is 2π-periodic, the integral in Eqn. (5.186) can be started at any value of Ω as long as it covers a span of 2π radians. It is usually more convenient to write the integral in Eqn. (5.186) to start at −π.

   $$\begin{array}{ll}{P}_x=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }{S}_x\left(\Omega \right)d\Omega }& \left(5.187\right)\end{array}$$

   As an interesting by-product of Eqn. (5.186), the normalized average power of $\tilde{x}\left[n\right]$ that is within a specific angular frequency range can be determined by integrating Sx (Ω) over that range. For example, the power contained at angular frequencies in the range (−Ω0, Ω0) is

   $$\begin{array}{ll}{P}_x\text{ in }\left(-{\Omega }_0,{\Omega }_0\right)=\frac{1}{2\pi }{\displaystyle {\int }_{-{\Omega }_0}^{{\Omega }_0}{S}_x\left(\Omega \right)d\Omega }& \left(5.188\right)\end{array}$$

2. In Eqn. (5.174) the left side is the normalized signal energy for the signal x[n], and the right side must be the same. The integrand |X (Ω)|2 is therefore the energy spectral density of the signal x[n]. Let the function Gx (Ω) be defined as

   $$\begin{array}{ll}{G}_x\left(\Omega \right)={\left|X\left(\Omega \right)\right|}^2& \left(5.189\right)\end{array}$$

   Substituting Eqn. (5.189) into Eqn. (5.174), the normalized energy in the signal x[n] can be expressed as

   $$\begin{array}{ll}{E}_x={\displaystyle \sum _{n=-\infty }^{\infty }{\left|\tilde{x}\left[n\right]\right|}^2}=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }G\left(\Omega \right)d\Omega }& \left(5.190\right)\end{array}$$

   The energy contained at angular frequencies in the range (−Ω0, Ω0) is found by integrating Gx (Ω) in the frequency range of interest:

   $$\begin{array}{ll}{E}_x\text{ in }\left(-{\Omega }_0,{\Omega }_0\right)=\frac{1}{2\pi }{\displaystyle {\int }_{-{\Omega }_0}^{{\Omega }_0}{G}_x\left(\Omega \right)d\Omega }\hfill & \left(5.191\right)\hfill \end{array}$$

3. In Eqn. (5.174) we have expressed Parseval’s theorem for an energy signal, and used it to lead to the derivation of the energy spectral density in Eqn. (5.189). We know that some non-periodic signals are power signals, therefore their energy cannot be computed. The example of one such signal is the unit-step function. The power of a non-periodic signal was defined in Eqn. (1.188) in Chapter 1 which will be repeated here:

   $$\begin{array}{ll}\text{Eqn}\text{. }\left(1.188\right):\hfill & P_x=\underset{M\to \infty }{\lim }\left[\frac{1}{2M+1}{\displaystyle \sum _{n=-M}^M{\left|x\left[n\right]\right|}^2}\right]\hfill \end{array}$$

   In order to write the counterpart of Eqn. (5.174) for a power signal, we will first define a truncated version of x[n] as

   $$\begin{array}{ll}{x}_T\left[n\right]=\{\begin{array}{ll}x\left[n\right],\hfill & -M\le n\le M\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}& \left(5.192\right)\end{array}$$

   Let XT (Ω) be the DTFT of the truncated signal xT [n]:

   $$\begin{array}{ll}{X}_T\left(\Omega \right)=F\left\{x_T\left[n\right]\right\}={\displaystyle \sum _{n=-M}^M{x}_T\left[n\right]e^{-j\Omega n}}& \left(5.193\right)\end{array}$$

   Now Eqn. (5.174) can be written in terms of the truncated signal and its transform as

   $$\begin{array}{ll}{\displaystyle \sum _{n=-M}^M{\left|x_T\left[n\right]\right|}^2}=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }{\left|X_T\left(\Omega \right)\right|}^{2}d\Omega }& \left(5.194\right)\end{array}$$

   Scaling both sides of Eqn. (5.194) by (2M + 1) and taking the limit as M becomes infinitely large, we obtain

   $$\begin{array}{ll}\underset{M\to \infty }{\lim }\left[\frac{1}{2M+1}{\displaystyle \sum _{n=-M}^M{\left|x_T\left[n\right]\right|}^2}\right]=\underset{M\to \infty }{\lim }\left[\frac{1}{2\pi \left(2M+1\right)}{\displaystyle {\int }_{-\pi }^{\pi }{\left|X_T\left(\Omega \right)\right|}^{2}d\Omega }\right]& \left(5.195\right)\end{array}$$

   The left side of Eqn. (5.195) is the average normalized power in a non-periodic signal as we have established in Eqn. (1.188). Therefore, the power spectral density of x[n] is

   $$\begin{array}{ll}{S}_x\left(\Omega \right)=\underset{M\to \infty }{\lim }\left[\frac{1}{2M+1}{\left|X_T\left(\Omega \right)\right|}^2\right]& \left(5.196\right)\end{array}$$

Example 5.23: Normalized average power for waveform of Example 5.7

Consider again the periodic waveform used in Example 5.7 and shown in Fig. 5.6. Using the DTFS coefficients found in Example 5.7, verify Parseval’s theorem. Also determine the percentage of signal power in the angular frequency range −π/3 < Ω0 <π/3.

Solution: The average power computed from the signal is

$$\begin{array}{ll}{P}_x\hfill & =\frac{1}{8}{\displaystyle \sum }_{n=0}^7|\tilde{x}[n]{|}^2\hfill \\ \hfill & =\frac{1}{8}[0+{(\frac{1}{2})}^2+{(1)}^2+{(\frac{3}{4})}^2+{(-1)}^2+{(-\frac{1}{2})}^2]\hfill \\ \hfill & =0.4531\hfill \end{array}$$

Using the DTFS coefficients in Table 5.1 yields

$$\begin{array}{ll}{\displaystyle \sum }_{k=0}^7|{\tilde{c}}_k{|}^2\hfill & =0+{(0.4170)}^2+{(0.0625)}^2+{(0.0290)}^2+0+{(0.0290)}^2+{(0.0625)}^2+{(0.4710)}^2\hfill \\ \hfill & =0.4531\hfill \end{array}$$

As expected, the value found from DTFS coefficients matches that found from the signal. One period of the power spectral density Sx (Ω) is

$$S_x\left(\Omega \right)=0.0017\pi \delta \left(\Omega +3\pi /4\right)+0.0078\pi \delta \left(\Omega +\pi /2\right)+0.4436\pi \delta \left(\Omega +\pi /4\right)+0.4436\pi \delta \left(\Omega -\pi /4\right)+0.0078\pi \delta \left(\Omega -\pi /2\right)+0.0017\pi \delta \left(\Omega -3\pi /4\right)$$

The power in the angular frequency range of interest is

$$\begin{array}{ll}{P}_x in (-\pi /3,\pi /3)\hfill & =\frac{1}{2\pi }\underset{-\pi /3}{\overset{\pi /3}{{\displaystyle \int }}}{S}_x(\Omega )d\Omega \hfill \\ \hfill & =\frac{1}{2\pi }(0.4436\pi +0.4436\pi )\hfill \\ \hfill & =0.4436\hfill \end{array}$$

The ratio of the power in −π/3 < Ω0 <π/3 to the total signal power is

$$\frac{P_x\text{ in }\left(-\pi /3,\pi /3\right)}{P_x}=\frac{0.4436}{0.4531}=0.979$$

It appears that 97.9 percent of the power of the signal is in the frequency range −π/3 < Ω0 <π/3.

Software resources:

ex_5_23.m

Example 5.24: Power spectral density of a discrete-time sinusoid

Find the power spectral density of the signal

$$\tilde{x}\left[n\right]=3\cos \left(0.2\pi n\right)$$

Solution: Using Euler’s formula, the signal can be written as

$$\tilde{x}\left[n\right]=\frac{3}{2}{e}^{-j0.2\pi n}+\frac{3}{2}{e}^{j0.2\pi n}$$

The normalized frequency of the sinusoidal signal is F0 = 0.1 corresponding to a period length of N = 10 samples. Non-zero DTFS coefficients for k = 0,..., 9 are

$${\tilde{c}}_1={\tilde{c}}_9=\frac{3}{2}$$

Using Eqn. (5.181), the power spectral density is

$$S_x\left(\Omega \right)={\displaystyle \sum _{r=-\infty }^{\infty }\left[\frac{9\pi }{2}\delta \left(\Omega -0.2\pi -2\pi r\right)+\frac{9\pi }{2}\delta \left(\Omega -1.8\pi -2\pi r\right)\right]}$$

which is shown in Fig. 5.36.

The power in the sinusoidal signal is computed from the power spectral density as

$$P_x=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }{S}_x\left(\Omega \right)d\Omega }=\frac{1}{2\pi }\left(\frac{9\pi }{2}+\frac{9\pi }{2}\right)=\frac{9}{2}$$

Example 5.25: Energy spectral density of a discrete-time pulse

Determine the energy spectral density of the rectangular pulse

$$x\left[n\right]=\{\begin{array}{ll}1,\hfill & n=-5,\mathrm{...},5\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

Also compute the energy of the signal in the frequency interval −π/10 < Ω <π/10.

Solution: Using the general result obtained in Example 5.12 with L = 5, the DTFT of the signal x[n] is

$$X\left(\Omega \right)=\frac{\sin \left(\frac{11\Omega }{2}\right)}{\sin \left(\frac{\Omega }{2}\right)}$$

The energy spectral density for x[n] is found as

$$G_x\left(\Omega \right)={\left|X\left(\Omega \right)\right|}^2=\frac{{\sin }^2\left(\frac{11\Omega }{2}\right)}{{\sin }^2\left(\frac{\Omega }{2}\right)}$$

which is shown in Fig. 5.37.

The energy of the signal within the frequency interval −π/10 < Ω <π/10 is computed as

$$E_x\text{ in }\left(\pi /10,\pi /10\right)=\frac{1}{2\pi }{\displaystyle {\int }_{-\pi /10}^{\pi /10}{G}_x\left(\Omega \right)d\Omega }$$

which is proportional to the shaded area under G (Ω) in Fig. 5.38.

Direct evaluation of the integral in Eqn. (5.197) is difficult; however, the result can be obtained by numerical approximation of the integral, and is

$$E_x\text{ in }\left(\pi /10,\pi /10\right)\approx 8.9309$$

Software resources:

ex_5_25.m

Energy or power in a frequency range

Signal power or signal energy that is within a finite range of frequencies is found through the use of Equation (5.188) and Equation (5.191) respectively. An interesting interpretation of the result in Eqn. (5.188) is that, for the case of a power signal, the power of x[n] in the frequency range −Ω0 < Ω < Ω0 is the same as the power of the output signal of a system with system function

$$\begin{array}{ll}H\left(\Omega \right)=\{\begin{array}{ll}1,\hfill & \left|\Omega \right|<{\Omega }_0\hfill \\ 0,\hfill & {\Omega }_0<\left|\Omega \right|<\pi \hfill \end{array}& \left(5.197\right)\end{array}$$

driven by the signal x[n]. Similarly, for the case of an energy signal, the energy of x[n] in the frequency range −Ω0 < Ω < Ω0 is the same as the energy of the output signal of a system with the system function in Eqn. (5.197) driven by the signal x[n]. These relationships are illustrated in Fig. 5.39(a) and (b).

5.4.3 Autocorrelation

The energy spectral density Gx (Ω) or the power spectral density Sx (Ω) for a signal can be computed through direct application of the corresponding equations derived in Section 5.4.2; namely Eqn. (5.189) for an energy signal, and either Eqn. (5.181) or Eqn. (5.196) for a power signal, depending on its type. In some circumstances it is also possible to compute either function from the knowledge of the autocorrelation function which will be defined in this section. Let x[n] be a real-valued signal.

Even though we refer to rxx[m] as a function, we will often treat it as if it is a discrete-time signal, albeit one that uses a different index, m, from the signal x[n] for which it is computed. The index m simply corresponds to the time shift between the two copies of x[n] used in the definitions of Equation (5.198) through Equation (5.200).

The definition of the autocorrelation function for a periodic signal $\tilde{x}\left[n\right]$ can be used in a similar manner in determining the power spectral density of the signal.

A relationship similar to the one expressed by Eqn. (5.210) applies to random processes that are wide-sense stationary, and is known as the Wiener-Khinchin theorem. It is one of the fundamental theorems of random signal processing.

Example 5.26: Power spectral density of a discrete-time sinusoid revisited

Consider again the discrete-time sinusoidal signal

$$\tilde{x}\left[n\right]=3\cos \left(0.2\pi n\right)$$

the power spectral density of which was determined in Example 5.24. Determine the autocorrelation function ${\tilde{r}}_{xx}\left[m\right]$ for this signal, and then find the power spectral density Sx (Ω) from the autocorrelation function.

Solution: The period of $\tilde{x}\left[n\right]$ is N = 10 samples. Using the definition of the autocorrelation function for a periodic signal

$$\begin{array}{lll}{\tilde{x}}_{xx}[m]\hfill & =\frac{1}{10}{\displaystyle \sum }_{n=0}^9\tilde{x}[n]\tilde{x}[n+m]\hfill & \hfill \\ \hfill & =\frac{1}{10}{\displaystyle \sum }_{n=0}^9[3\cos (0.2\pi n)][3\cos (0.2\pi [n+m])]\hfill & (5.217)\hfill \end{array}$$

Through the use of the appropriate trigonometric identity, the result in Eqn. (5.217) is simplified to

$$\begin{array}{lll}{\tilde{r}}_{xx}[m]\hfill & =\frac{1}{10}{\displaystyle \sum }_{n=0}^9[\frac{9}{2}\cos (0.4\pi n+0.2\pi m)+\frac{9}{2}\cos (0.2\pi m)]\hfill & \hfill \\ \hfill & =\frac{9}{20}{\displaystyle \sum }_{n=0}^9\cos (0.4\pi n+0.2\pi m)+\frac{9}{20}{\displaystyle \sum }_{n=0}^9\cos (0.2\pi m)\hfill & (5.218)\hfill \end{array}$$

In Eqn. (5.218) the first summation is equal to zero since its term cos (0.4πn +0.2πm) is periodic with a period of five samples, and the summation is over two full periods. The second summation yields

$$\begin{array}{ll}{\tilde{r}}_{xx}[m]\hfill & =\frac{9}{20}{\displaystyle \sum }_{n=0}^9\cos (0.2\pi m)\hfill \\ \hfill & =\frac{9}{20}\cos (0.2\pi m){\displaystyle \sum }_{n=0}^9(1)\hfill \\ \hfill & =\frac{9}{2}\cos (0.2\pi m)\hfill \end{array}$$

for the autocorrelation function. The power spectral density is found as the DTFT of the autocorrelation function. Application of the DTFT was discussed in Section 5.3.6. Using the technique developed in that section (specifically see Example 5.21) the transform is found as

$$\begin{array}{ll}{S}_x(\Omega )\hfill & =F\{{\tilde{r}}_{xx}[m]\}=F\{\frac{9}{2}\cos (0.2\pi m)\}\hfill \\ \hfill & ={\displaystyle \sum }_{r=-\infty }^{\infty }[\frac{9\pi }{2}\delta (\Omega +0.2\pi -2\pi r)+\frac{9\pi }{2}\delta (\Omega -0.2\pi -2\pi r)]\hfill \end{array}$$

which matches the answer found earlier in Example 5.24.

Software resources:

ex_5_26.m

Properties of the autocorrelation function

The autocorrelation function as defined by Equation (5.198), Equation (5.199) and Equation (5.200) has a number of important properties that will be summarized here:

1. rxx[0] ≥ |rxx[m]| for all m.

   To see why this is the case, we will consider the non-negative function (x[n] ∓ x[n + m])2.

   The time average of this function must also be non-negative, therefore

   $$\langle {\left(x\left[n\right]\mp x\left[n+m\right]\right)}^2\rangle \ge 0$$

   or equivalently

   $$\langle x^2\left[n\right]\rangle \mp 2\langle x\left[n\right]x\left[n+m\right]\rangle +\langle x^2\left[n+m\right]\rangle \ge 0$$

   which implies that

   $$r_{xx}\left[0\right]\mp 2r_{xx}\left[m\right]+r_{xx}\left[0\right]\ge 0$$

   which is the same as property 1.

2. rxx[−m] = rxx[m] for all m, that is, the autocorrelation function has even symmetry. Recall that the autocorrelation function is the inverse Fourier transform of either the energy spectral density or the power spectral density. Since Gx (Ω) and Sx (Ω) are purely real, rxx[m] must be an even function of m.

3. If the signal $\tilde{x}\left[n\right]$ is periodic with period N, then its autocorrelation function ${\tilde{r}}_{xx}\left[m\right]$ is also periodic with the same period. This property easily follows from the time-average based definition of the autocorrelation function given by Eqn. (5.199).

5.5 System Function Concept

In time-domain analysis of systems in Chapter 3 two distinct description forms were used for DTLTI systems:

1. A linear constant-coefficient difference equation that describes the relationship between the input and the output signals
2. An impulse response which can be used with the convolution operation for determining the response of the system to an arbitrary input signal

In this section, the concept of system function will be introduced as the third method for describing the characteristics of a system.

Recall that the impulse response is only meaningful for a system that is both linear and time-invariant (since the convolution operator could not be used otherwise). It follows that the system function concept is valid for linear and time-invariant systems only. In general, H (Ω) is a complex function of Ω, and can be written in polar form as

$$\begin{array}{ll}H\left(\Omega \right)=\left|H\left(\Omega \right)\right|e^{j\Theta \left(\Omega \right)}& \left(5.220\right)\end{array}$$

Obtaining the system function from the difference equation

In finding a system function for a DTLTI system described by means of a difference equation, two properties of the DTFT will be useful: the convolution property and the time shifting property.

1. Since the output signal is computed as the convolution of the impulse response and the input signal, that is, y[n] = h[n] * x[n], the corresponding relationship in the frequency domain is Y (Ω) = H (Ω) X (Ω). Consequently, the system function is equal to the ratio of the output transform to the input transform:

   $$\begin{array}{ll}H\left(\Omega \right)=\frac{Y\left(\Omega \right)}{X\left(\Omega \right)}& \left(5.221\right)\end{array}$$

2. Using the time shifting property, transforms of the individual terms in the difference equation are found as

   $$\begin{array}{lll}y\left[n-m\right]\stackrel{F}{\leftrightarrow }{e}^{-j\Omega m}Y\left(\Omega \right)& m=0,1,\mathrm{...}& \left(5.222\right)\end{array}$$

   and

   $$\begin{array}{lll}x\left[n-m\right]\stackrel{F}{\leftrightarrow }{e}^{-j\Omega m}X\left(\Omega \right)& m=0,1,\mathrm{...}& \left(5.223\right)\end{array}$$

The system function is obtained from the difference equation by first transforming both sides of the difference equation through the use of Equation (5.222) and Equation (5.223), and then using Eqn. (5.221).

Example 5.27: Finding the system function from the difference equation

Determine the system function for a DTLTI system described by the difference equation

$$y\left[n\right]-0.9y\left[n-1\right]+0.36y\left[n-2\right]=x\left[n\right]-0.2x\left[n-1\right]$$

Solution: Taking the DTFT of both sides of the difference equation we obtain

$$Y\left(\Omega \right)-0.9e^{-j\Omega }Y\left(\Omega \right)+0.36e^{-j2\Omega }Y\left(\Omega \right)=X\left(\Omega \right)-0.2e^{-j\Omega }X\left(\Omega \right)$$

which can be written as

$$\left[1-0.9e^{-j\Omega }+0.36e^{-j2\Omega }\right]Y\left(\Omega \right)=\left[1-0.2e^{-j\Omega }\right]X\left(\Omega \right)$$

The system function is found through the use of Eqn. (5.221)

$$H\left(\Omega \right)=\frac{Y\left(\Omega \right)}{X\left(\Omega \right)}=\frac{1-0.2e^{-j\Omega }}{1-0.9e^{-j\Omega }+0.36e^{-j2\Omega }}$$

The magnitude and the phase of the system function are shown in Fig. 5.40.

Software resources:

ex_5_27.m

Example 5.28: System function for length-N moving average filter

Recall the length-N moving average filter with the difference equation

$$y\left[n\right]=\frac{1}{N}{\displaystyle \sum _{k=0}^{N-1}x\left[n-k\right]}$$

Determine the system function. Graph its magnitude and phase as functions of Ω.

Solution: Taking the DTFT of both sides of the difference equation we obtain

$$Y\left[\Omega \right]=\frac{1}{N}{\displaystyle \sum _{k=0}^{N-1}{e}^{-j\Omega k}X\left[\Omega \right]}$$

from which the system function is found as

$$\begin{array}{ll}H\left(\Omega \right)=\frac{Y\left(\Omega \right)}{X\left(\Omega \right)}=\frac{1}{N}{\displaystyle \sum _{k=0}^{N-1}{e}^{-j\Omega k}}& \left(5.224\right)\end{array}$$

The expression in Eqn. (5.224) can be put into closed form as

$$H\left(\Omega \right)=\frac{1-e^{-j\Omega N}}{1-e^{-j\Omega }}$$

As the first step in expressing H (Ω) in polar complex form, we will factor out e−jΩN/2 from the numerator and e−jΩ/2 from the denominator to obtain

$$\begin{array}{ll}H(\Omega )\hfill & =\frac{e^{-j\Omega N/2}(e^{j\Omega N/2}-e^{-j\Omega N/2})}{e^{-j\Omega /2}(e^{j\Omega /2}-e^{-j\Omega /2})}\hfill \\ \hfill & =\frac{\sin (\Omega N/2)}{\sin (\Omega /2)}{e}^{j\Omega (N-1)/2}\hfill \end{array}$$

The magnitude and the phase of the system function are shown in Fig. 5.41 for N = 4.

Software resources:

ex_5_28.m

5.6 DTLTI Systems with Periodic Input Signals

In earlier sections of this chapter we have explored the use of the discrete-time Fourier series (DTFS) for representing periodic discrete-time signals. It was shown that a periodic discrete-time signal can be expressed using complex exponential basis functions in the form

$$\begin{array}{lll}\text{Eqn}\text{. }\left(5.21\right)& \tilde{x}\left[n\right]={\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k{e}^{j\left(2\pi /N\right)kn}}& \text{for all }n\end{array}$$

If a periodic signal is used as input to a DTLTI system, the use of the superposition property allows the response of the system to be determined as a linear combination of its responses to individual basis functions

$${\varphi }_k\left[n\right]=e^{j\left(2\pi /N\right)kn}$$

5.6.1 Response of a DTLTI system to complex exponential signal

Consider a DTLTI system with impulse response h[n], driven by a complex exponential input signal

$$\begin{array}{ll}\tilde{x}\left[n\right]=e^{j{\Omega }_{0}n}& \left(5.225\right)\end{array}$$

The response y[n] of the system is found through the use of the convolution relationship that was derived in Section 3.7.2 of Chapter 3.

$$\begin{array}{lll}y(h)\hfill & =h[n]*\tilde{x}[n]\hfill & \hfill \\ \hfill & ={\displaystyle \sum }_{k=-\infty }^{\infty }h[k]\tilde{x}[n-k]\hfill & (5.226)\hfill \end{array}$$

For a DTLTI system driven by a complex exponential input signal, we have the following important relationship:

1. The response of a DTLTI system to a complex exponential input signal is a complex exponential output signal with the same angular frequency Ω0.
2. The effect of the system on the complex exponential input signal is to
   1. Scale its amplitude by an amount equal to the magnitude of the system function at Ω = Ω0
   2. Shift its phase by an amount equal to the phase of the system function at Ω = Ω0

5.6.2 Response of a DTLTI system to sinusoidal signal

Let the input signal to the DTLTI system under consideration be a sinusoidal signal in the form

$$\begin{array}{ll}\tilde{x}\left[n\right]=\cos \left({\Omega }_{0}n\right)& \left(5.231\right)\end{array}$$

The response of the system in this case will be determined by making use of the results of the previous section.

For a DTLTI system driven by a cosine input signal, we have the following important relationship:

1. When a DTLTI system is driven by single-tone input signal at angular frequency Ω0, its output signal is also a single-tone signal at the same angular frequency.
2. The effect of the system on the input signal is to
   1. Scale its amplitude by an amount equal to the magnitude of the system function at Ω = Ω0
   2. Shift its phase by an amount equal to the phase of the system function at Ω = Ω0

Example 5.29: Steady-state response of DTLTI system to sinusoidal input

Consider a DTLTI system characterized by the difference equation

$$y\left[n\right]-0.9y\left[n-1\right]+0.36y\left[n-2\right]=x\left[n\right]-0.2x\left[n-1\right]$$

The system function for this system was determined in Example 5.27 to be

$$H\left(\Omega \right)=\frac{Y\left(\Omega \right)}{X\left(\Omega \right)}=\frac{1-0.2e^{-j\Omega }}{1-0.9e^{-j\Omega }+0.36e^{-j2\Omega }}$$

Find the response of the system to the sinusoidal input signal

$$\tilde{x}\left[n\right]=5\cos \left(\frac{\pi n}{5}\right)$$

Solution: Evaluating the system function at the angular frequency Ω0 = π/5 yields

$$H\left(\pi /5\right)=\frac{1-0.2e^{-j\pi /5}}{1-0.9e^{-j\pi /5}+0.36e^{-j2\pi /5}}=1.8890-j0.6133$$

which can be written in polar form as

$$H\left(\pi /5\right)=\left|H\left(\pi /5\right)\right|e^{j\Theta \left(\pi /5\right)}=1.9861e^{-j0.3139}$$

The magnitude and the phase of the system function are shown in Fig. 5.42. The values of magnitude and phase at the angular frequency of interest are marked on the graphs.

The steady-state response of the system to the specified input signal $\tilde{x}\left[n\right]$ is

$$\begin{array}{ll}\tilde{y}[n]\hfill & =5|H(\pi /5)|\cos (\frac{\pi n}{5}+\Theta (\pi /5))\hfill \\ \hfill & =9.9305\cos (\frac{\pi n}{5}-0.3139)\hfill \end{array}$$

Software resources:

ex_5_29.m

5.6.3 Response of a DTLTI system to periodic input signal

Using the development in the previous sections, we are now ready to consider the use of a general periodic signal $\tilde{x}\left[n\right]$ as input to a DTLTI system. Using the DTFS representation of the signal, the response of the system is

$$\begin{array}{ll}\text{Sys}\left\{\tilde{x}\left[n\right]\right\}=\text{Sys}\left\{{\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k{e}^{j\left(2\pi /N\right)kn}}\right\}& \left(5.237\right)\end{array}$$

Let us use the linearity of the system to write the response as

$$\begin{array}{ll}\text{Sys}\left\{\tilde{x}\left[n\right]\right\}={\displaystyle \sum _{k=0}^{N-1}\text{Sys}\left\{{\tilde{c}}_k{e}^{j\left(2\pi /N\right)kn}\right\}}={\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_k\text{Sys}\left\{e^{j\left(2\pi /N\right)kn}\right\}}& \left(5.238\right)\end{array}$$

Based on Eqn. (5.230) the response of the system to an exponential basis function at frequency Ω = 2πk/N is given by

$$\begin{array}{ll}\text{Sys}\left\{e^{j\left(2\pi /N\right)kn}\right\}=e^{j\left(2\pi /N\right)kn}H\left(\frac{2\pi k}{N}\right)& \left(5.239\right)\end{array}$$

Using Eqn. (5.239) in Eqn. (5.238), the response of the system to $\tilde{x}\left[n\right]$ is found as

$$\begin{array}{ll}\text{Sys}\left\{\tilde{x}\left[n\right]\right\}={\displaystyle \sum _{k=0}^{N-1}{\tilde{c}}_{k}H\left(\frac{2\pi k}{N}\right)e^{j\left(2\pi /N\right)kn}}& \left(5.240\right)\end{array}$$

Two important observations should be made based on Eqn. (5.240):

1. For a DTLTI system driven by an input signal $\tilde{x}\left[n\right]$ with period N, the output signal is also periodic with the same period.
2. If the DTFS coefficients of the input signal are $\left\{{\tilde{c}}_k;k=1,\mathrm{...},N-1\right\}$ then the DTFS coefficients of the output signal are $\left\{{\tilde{d}}_k;k=1,\mathrm{...},N-1\right\}$ such that

$$\begin{array}{lll}{\tilde{d}}_k={\tilde{c}}_{k}H\left(\frac{2\pi k}{N}\right),& k=0,\mathrm{...},N-1& \left(5.241\right)\end{array}$$

Example 5.30: Response of DTLTI system to discrete-time sawtooth signal

Let the discrete-time sawtooth signal used in Example 5.4 and shown again in Fig. 5.43 be applied to the system with system function

Find the steady-state response of the system.

Solution: The DTFS coefficients for $\tilde{x}\left[n\right]$ were determined in Example 5.4, and are repeated below:

$$\begin{array}{l}{\tilde{c}}_0=2\\ {\tilde{c}}_1=-0.5+j0.6882\\ {\tilde{c}}_2=-0.5+j0.1625\\ {\tilde{c}}_3=-0.5-j0.1625\\ {\tilde{c}}_4=-0.5-j0.6882\end{array}$$

Evaluating the system function at angular frequencies

$$\begin{array}{ll}{\Omega }_k=\frac{2\pi k}{5},& k=0,1,2,3,4\end{array}$$

we obtain

$$\begin{array}{ll}H(0)\hfill & =1.7391\hfill \\ H(\frac{2\pi }{5})\hfill & =0.8767-j0.8701\hfill \\ H(\frac{4\pi }{5})\hfill & =0.5406-j0.1922\hfill \\ H(\frac{6\pi }{5})\hfill & =0.5406+j0.1922\hfill \\ H(\frac{8\pi }{5})\hfill & =0.8767+j0.8701\hfill \end{array}$$

The DTFS coefficients for the output signal are found using Eqn. (5.241):

$$\begin{array}{l}{\tilde{d}}_0={\tilde{c}}_{0}H\left(0\right)=\left(2\right)\left(1.7391\right)=3.4783\\ {\tilde{d}}_1={\tilde{c}}_{1}H\left(\frac{2\pi }{5}\right)=\left(-0.5000+j0.6882\right)\left(0.8767-j0.8701\right)=0.1604+j1.0384\\ {\tilde{d}}_2={\tilde{c}}_{2}H\left(\frac{4\pi }{5}\right)=\left(-0.5000+j0.1625\right)\left(0.5406-j0.1922\right)=-0.2391+j0.1839\\ {\tilde{d}}_3={\tilde{c}}_{3}H\left(\frac{6\pi }{5}\right)=\left(-0.5000-j0.1625\right)\left(0.5406+j0.1922\right)=-0.2391-j0.1839\\ {\tilde{d}}_4={\tilde{c}}_{4}H\left(\frac{8\pi }{5}\right)=\left(-0.5000-j0.6882\right)\left(0.8767+j0.8701\right)=0.1604-j1.0384\end{array}$$

The output signal y[n] can now be constructed using the DTFS coefficients $\left\{{\tilde{d}}_k;k=0,1,2,3,4\right\}$:

$$\begin{array}{ll}\tilde{y}[n]\hfill & ={\displaystyle \sum }_{k=0}^4{\tilde{d}}_k{e}^{j(2\pi /N)kn}\hfill \\ \hfill & =3.4783+(0.1604+j1.0384)e^{j2\pi n/5}+(-0.2391+j0.1839)e^{j4\pi n/5}\hfill \\ \hfill & +(-0.2391-j0.1839)e^{j6\pi n/5}+(0.1604-j1.0384)e^{j8\pi n/5}\hfill \end{array}$$

and is shown in Fig. 5.44.

Software resources:

ex_5_30.m

5.7 DTLTI Systems with Non-Periodic Input Signals

Let us consider the case of using a non-periodic signal x[n] as input to a DTLTI system. It was established in Section 3.7.2 of Chapter 3 that the output of a DTLTI system is equal to the convolution of the input signal with the impulse response, that is

$$\begin{array}{lll}y[n]\hfill & =h[n]*x[n]\hfill & \hfill \\ \hfill & ={\displaystyle \sum }_{k=-\infty }^{\infty }h[k]x[n-k]\hfill & (5.242)\hfill \end{array}$$

Let us assume that

1. The system is stable ensuring that H (Ω) converges.
2. The DTFT of the input signal also converges.

We have seen in Section 5.3.5 of this chapter that the DTFT of the convolution of two signals is equal to the product of individual transforms:

Writing each transform involved in Eqn. (5.243) in polar form using its magnitude and phase we obtain the corresponding relationships:

5.8 Discrete Fourier Transform

In previous sections of this chapter we have studied the discrete-time Fourier series (DTFS) for periodic discrete-time signals, and the discrete-time Fourier transform (DTFT) for non-periodic discrete-time signals. The result of DTFT analysis of a discrete-time signal x[n] is a transform X (Ω) which, if it exists, is a 2π-periodic function of the continuous variable Ω. Storing the DTFT of a signal on a digital computer is impractical because of the continuous nature of Ω. On the other hand, the DTFS representation of a signal $\tilde{x}\left[n\right]$ that is periodic with N samples is a set of coefficients ${\tilde{c}}_k$ that is also periodic with N. While this combination would certainly be suitable for computer implementation and storage, it is only for periodic signals. We often deal with signals that are not necessarily periodic.

In the analysis of non-periodic discrete-time signals, sometimes it is desirable to have a transform that is also discrete. This can be accomplished through the use of the discrete Fourier transform (DFT) provided that the signal under consideration is finite-length.

Consider a signal x[n] the meaningful samples of which are limited to the index range n = 0,...,N − 1, that is,

$$x\left[n\right]=0\text{ for }n<0\text{ or }\ge N$$

We will refer to x[n] as a length-N signal since it has N non-trivial samples. An easy method of representing x[n] with a transform that is also length-N would be as follows:

1. Consider x[n] as one period of a periodic signal $\tilde{x}\left[n\right]$ defined as

   $$\begin{array}{ll}\tilde{x}\left[n\right]={\displaystyle \sum _{m=-\infty }^{\infty }x\left[n-mN\right]}& \left(5.246\right)\end{array}$$

   We will refer to $\tilde{x}\left[n\right]$ as the periodic extension of x[n].

2. Determine the DTFS coefficients ${\tilde{c}}_k$ for the periodic extension $\tilde{x}\left[n\right]$ obtained from x[n] through Eqn. (5.246):

   $$\begin{array}{ll}\tilde{x}\left[n\right]\stackrel{\text{DTFS}}{\leftrightarrow }{\tilde{c}}_k& \left(5.247\right)\end{array}$$

3. DTFS coefficients of $\tilde{x}\left[n\right]$ form a set that is also periodic with N. Let us extract just one period {ck; k = 0,...,N − 1} from the DTFS coefficients {${\tilde{c}}_k$;all k}:

   $$\begin{array}{ll}{c}_k=\{\begin{array}{ll}{\tilde{c}}_k,\hfill & k=0,\mathrm{...},N-1\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}& \left(5.248\right)\end{array}$$

This gives us the ability to represent the signal x[n] with the set of coefficients ck for k = 0,...,N − 1. The coefficients can be obtained from the signal using the three steps outlined above. Conversely, the signal can be reconstructed from the coefficients by simply reversing the order of the steps.

The discrete Fourier transform (DFT) will be defined by slightly modifying the idea presented above. The forward transform is

$$\begin{array}{lll}X\left[k\right]={\displaystyle \sum _{n=0}^{N-1}x\left[n\right]e^{-j\left(2\pi /N\right)kn}},& k=0,\mathrm{...},N-1& \left(5.249\right)\end{array}$$

The length-N signal x[n] leads to the length-N transform X[k]. Compare Eqn. (5.249) with DTFS analysis equation given by Eqn. (5.22). The only difference is the scale factor 1/N:

$$\begin{array}{lll}X\left[k\right]=N{c}_k,& k=0,\mathrm{...},N-1& \left(5.250\right)\end{array}$$

It is also possible to obtain the signal x[n] from the transform X[k] using the inverse DFT relationship

$$\begin{array}{lll}x\left[n\right]=\frac{1}{N}{\displaystyle \sum _{k=0}^{N-1}X\left[k\right]e^{j\left(2\pi /N\right)kn}},& n=0,\mathrm{...},N-1& \left(5.251\right)\end{array}$$

The notation can be made a bit more compact by defining wN as

$$\begin{array}{ll}{\omega }_N=e^{-j\left(2\pi /N\right)}& \left(5.252\right)\end{array}$$

Using wN the forward DFT equation becomes

$$\begin{array}{lll}X\left[k\right]={\displaystyle \sum _{n=0}^{N-1}x\left[n\right]{\omega }_N^{kn}},& k=0,\mathrm{...},N-1& \left(5.253\right)\end{array}$$

and the inverse DFT is found as

$$\begin{array}{lll}x\left[n\right]=\frac{1}{N}{\displaystyle \sum _{k=0}^{N-1}X\left[k\right]{\omega }_N^{-kn}},& n=0,\mathrm{...},N-1& \left(5.254\right)\end{array}$$

Notationally the DFT relationship between a signal and its transform can be represented as

$$x\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }X\left[k\right]$$

or as

$$\begin{array}{l}X\left[k\right]=\text{DFT}\left\{x\left[n\right]\right\}\\ x\left[n\right]={\text{DFT}}^{-1}\left\{X\left[k\right]\right\}\end{array}$$

The analysis and the synthesis equations for the DFT can be summarized as follows:

The DFT is a very popular tool in a wide variety of engineering applications for a number of reasons:

1. The signal x[n] and its DFT X[k] each have N samples, making the discrete Fourier transform practical for computer implementation. N samples of the signal can be replaced in memory with N samples of the transform without losing any information. It does not matter whether we store the signal or the transform since one can always be obtained from the other.
2. Fast and efficient algorithms, known as fast Fourier transforms (FFTs), are available for the computation of the DFT.
3. DFT can be used for approximating other forms of Fourier series and transforms for both continuous-time and discrete-time systems. It can also be used for fast convolution in filtering applications.
4. Dedicated processors are available for fast and efficient computation of the DFT with minimal or no programming needed.

Example 5.31: DFT of simple signal

Determine the DFT of the signal

$$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},-1,2\right\}$$

Solution: The discrete Fourier transform is

$$\begin{array}{ll}X[k]\hfill & =e^{-j(2\pi /3)k(0)}-e^{-j(2\pi /3)k(1)}+2e^{-j(2\pi /3)k(2)}\hfill \\ \hfill & =1-e^{-j2\pi k/3}+2e^{-j4\pi k/3}\hfill \end{array}$$

We will evaluate this result for k = 1, 2, 3:

$$\begin{array}{l}X\left[0\right]=1-1+2=2\\ X\left[1\right]=1-e^{-j2\pi /3}+2e^{-j4\pi /3}=0.5+j2.5981\\ X\left[2\right]=1-e^{-j4\pi k/3}+2e^{-j8\pi k/3}=0.5-j2.5981\end{array}$$

Example 5.32: DFT of discrete-time pulse

Determine the DFT of the discrete-time pulse signal

$$\begin{array}{ll}x[n]\hfill & =u[n]-u[n-10]\hfill \\ \hfill & =\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,1,1,1,1,1,1,1\}\hfill \end{array}$$

Solution: The discrete Fourier transform is

$$\begin{array}{ll}X\left[k\right]={\displaystyle \sum _{n=0}^9{e}^{-j\left(2\pi /10\right)kn}},& k=0,\mathrm{...},9\end{array}$$

which can be put into closed form using the finite-length geometric series formula (see Appendix C)

$$\begin{array}{ll}X\left[k\right]=\frac{1-e^{-j2\pi k}}{1-e^{-j2\pi k/10}}=\{\begin{array}{ll}10,& n=0\\ 0,& k=1,\mathrm{...},9\end{array}& \left(5.257\right)\end{array}$$

Note that L’Hospital’s rule was used for determining the value X[0]. The signal x[n] and its DFT are shown in Fig. 5.45.

5.8.1 Relationship of the DFT to the DTFT

Consider again a length-N signal x[n]. The DTFT of such a signal, defined by Eqn. (5.71), can be written as

$$\begin{array}{ll}X\left(\Omega \right)={\displaystyle \sum _{n=0}^{N-1}x\left[n\right]e^{-j\Omega n}}& \left(5.258\right)\end{array}$$

where the summation limits have been adjusted to account for the fact that the only significant samples of x[n] are in the interval n = 0,...,N − 1. A comparison of Eqn. (5.258) with Eqn. (5.71) reveals the simple relationship between the DTFT and the DFT:

It is obvious from Eqn. (5.259) that, for a length-N signal, the DFT is very similar to the DTFT with one fundamental difference: In the DTFT, the transform is computed at every value of Ω in the range 0 ≤ Ω < 2π. In the DFT, however, the same is computed only at frequencies that are integer multiples of 2π/N. In a way, looking at the DFT is similar to looking at the DTFT placed behind a picket fence with N equally spaced openings. This is referred to as the picket-fence effect. We will elaborate on this relationship further in the next example.

Example 5.33: DFT of a discrete-time pulse revisited

Consider again the discrete-time pulse that was used in Example 5.32.

$$x\left[n\right]=u\left[n\right]-u\left[n-10\right]$$

The DFT of this pulse was determined in Example 5.32 and shown graphically in Fig. 5.45(b). The DTFT of x[n] is

$$X\left(\Omega \right)={\displaystyle \sum _{n=0}^9{e}^{-j\Omega n}}$$

and it can easily be put into a closed form as

$$X\left(\Omega \right)=\frac{\sin \left(5\Omega \right)}{\sin \left(0.5\Omega \right)}{e}^{-j4.5\Omega }$$

Recall from earlier discussion (see Eqn. (5.259)) that the transform sample with index k corresponds to the angular frequency Ωk = 2πk/N. If we want to graph the DTFT and the DFT on the same frequency axis, we need to place the DFT samples using an angular frequency spacing of 2π/N radians. Fig. 5.46 shows both the DTFT and the DFT of the signal x[n], and reveals why we obtained such a trivial looking result in Eqn. (5.257) for the DFT.

For k = 1,..., 9, the locations of the transform samples in X[k] coincide with the zero crossings of the DTFT. This is the so-called picket-fence effect. It is as though we are looking at the DTFT of the signal x[n] through a picket fence that has narrow openings spaced 2π/N radians apart. In this case we see mostly the zero crossings of the DTFT and miss the detail between them.

The DFT as given by Eqn. (5.257) is still a complete transform, and the signal x[n] can be obtained from it using the inverse DFT equation given by Eqn. (5.256).

Software resources:

ex_5_33.m

5.8.2 Zero padding

Even though the DFT computed in Examples 5.32 and 5.33 is a complete and accurate representation of signal x[n], from a visual perspective it does not show much. Sometimes we would like more visual detail than provided by the DFT result. Continuing with the picket-fence analogy, we may want to observe the DTFT through a more dense picket fence with more openings in a 2π-radian range of the angular frequency. This can be accomplished by zero-padding the original signal, that is, by extending it with zero-amplitude samples before computing the DFT.

Consider again the length-N signal x[n]. Let us define a length-(N + M) signal q[n] as follows:

$$\begin{array}{ll}q\left[n\right]=\{\begin{array}{ll}x\left[n\right],\hfill & n=0,\mathrm{...},N-1\hfill \\ 0,\hfill & n=N,\mathrm{...},N+M-1\hfill \end{array}& \left(5.260\right)\end{array}$$

The DFT of the newly defined signal q[n] is

$$\begin{array}{ll}Q\left[k\right]={\displaystyle \sum _{n=0}^{N+M-1}q\left[n\right]e^{-j2\pi kn/\left(N+M\right)}}& \left(5.261\right)\end{array}$$

$$\begin{array}{ll}={\displaystyle \sum _{n=0}^{N-1}x\left[n\right]e^{-j2\pi kn/\left(N+M\right)}}& \left(5.262\right)\end{array}$$

Comparing Eqn. (5.261) with Eqn. (5.258) we conclude that

$$\begin{array}{ll}Q\left(k\right)=X\left(\Omega \right){|}_{\Omega =2\pi k/\left(N+M\right)}& \left(5.263\right)\end{array}$$

Thus, Q[k] corresponds to observing the DTFT of x[n] through a picket fence with openings spaced 2π/(N + M) radians apart as opposed to 2π/N radians apart. The number of zeros to be appended to the end of the original signal can be chosen to obtain any desired angular frequency spacing.

Example 5.34: Zero padding the discrete-time pulse

Consider again the length-10 discrete-time pulse used in Example 5.33. Create a new signal q[n] by zero-padding it to 20 samples, and compare the 20-point DFT of q[n] to the DTFT of x[n].

Solution: The new signal q[n] is

$$q\left[n\right]=\{\begin{array}{ll}1,\hfill & n=0,\mathrm{...},9\hfill \\ 0,\hfill & n=10,\mathrm{...},19\hfill \end{array}$$

The 20-point DFT of q[n] is

$$\begin{array}{ll}Q\left[k\right]={\displaystyle \sum _{n=0}^{19}q\left[n\right]e^{-j2\pi nk/20}}& \left(5.264\right)\end{array}$$

Since q[n] = 1 for n = 0,..., 9 and q[n] = 0 for n = 10,..., 19, Eqn. (5.264) can be written as

$$\begin{array}{ll}Q\left[k\right]={\displaystyle \sum _{n=0}^9{e}^{-j2\pi nk/20}}=\frac{1-e^{-j\pi k}}{1-e^{-j2\pi k/20}},& k=0,\mathrm{...},19\end{array}$$

Q[k] is graphed in Fig. 5.47 along with the DTFT X (Ω). Compare the figure to Fig. 5.33. Notice how 10 new transform samples appear between the 10 transform samples that were there previously. This is equivalent to obtaining new points between existing ones through some form of interpolation. After zero-padding, the angular frequency spacing between the transform samples is Ωk = 2π/20.

Software resources:

ex_5_34.m

5.8.3 Properties of the DFT

Important properties of the DFT will be summarized in this section. It will become apparent in that process that the properties of the DFT are similar to those of DTFS and DTFT with one significant difference: Any shifts in the time domain or the transform domain are circular shifts rather than linear shifts. Also, any time reversals used in conjunction with the DFT are circular time reversals rather than linear ones. Therefore, the concepts of circular shift and circular time reversal will be introduced here in preparation for the discussion of DFT properties.

In the derivation leading to forward and inverse DFT relationships in Equation (5.255) and Equation (5.256) for a length-N signal x[n] we have relied on the DTFS representation of the periodic extension signal $\tilde{x}\left[n\right]$. Let us consider the following scenario:

1. Obtain periodic extension $\tilde{x}\left[n\right]$ from x[n] using Eqn. (5.246).
2. Apply a time shift to $\tilde{x}\left[n\right]$ to obtain $\tilde{x}\left[n-m\right]$. The amount of the time shift may be positive or negative.
3. Obtain an length-N signal g[n] by extracting the main period of $\tilde{x}\left[n-m\right]$.

   $$\begin{array}{ll}g\left[n\right]=\{\begin{array}{ll}\tilde{x}\left[n-m\right],& n=0,\mathrm{...},N-1\\ 0,& \text{Otherwise}\end{array}& \left(5.265\right)\end{array}$$

The resulting signal g[n] is a circularly shifted version of x[n], that is

$$\begin{array}{ll}g\left[n\right]=x{\left[n-m\right]}_{\text{mod }N}& \left(5.266\right)\end{array}$$

The term

$$\begin{array}{ll}x{\left[n-m\right]}_{\mathrm{mod}N}& \left(5.267\right)\end{array}$$

on the right side of Eqn. (5.266) uses modulo indexing. The signal x[n] has meaningful samples only for n = 0,...,N − 1. The index n − m for a particular set of n and m values may or may not be in this range. Modulo N value of the index is found by adding integer multiples of N to the index until the result is within the range n = 0,...,N − 1. A few examples are given below:

$$\begin{array}{lll}x{\left[-3\right]}_{\text{mod }8}=x\left[5\right]\hfill & x{\left[12\right]}_{\text{mod 10}}=x\left[2\right]\hfill & x{\left[-7\right]}_{\text{mod 25}}=x\left[18\right]\hfill \\ x{\left[16\right]}_{\text{mod 16}}=x\left[0\right]\hfill & x{\left[-3\right]}_{\text{mod 4}}=x\left[1\right]\hfill & x{\left[95\right]}_{\mathrm{mod}\text{ 38}}=x\left[19\right]\hfill \end{array}$$

The process that led to Eqn. (5.266) is illustrated in Figure 5.48 and Figure 5.49 for an example length-8 signal.

For the example we are considering in Figure 5.48 and Figure 5.49 imagine a picture frame that fits samples 0,..., 7. Right shifting the signal by two samples causes two samples to leave the frame from the right edge and re-enter from the left edge, as shown in Fig. 5.48. Left shifting the signal has the opposite effect. Samples leave the frame from the left edge and re-enter from the right edge, as shown in Fig. 5.49. Fig. 5.50 further illustrates the concept of circular shifting.

For the time reversal operation consider the following steps:

1. Obtain periodic extension $\tilde{x}\left[n\right]$ from x[n] using Eqn. (5.246).
2. Apply the time reversal operation to $\tilde{x}\left[n\right]$ to obtain $\tilde{x}\left[\mathrm{–n}\right]$.
3. Obtain an length-N signal g[n] by extracting the main period of $\tilde{x}\left[\mathrm{–n}\right]$.

$$\begin{array}{ll}g\left[n\right]=\{\begin{array}{ll}\tilde{x}\left[-n\right],& n=0,\mathrm{...},N-1\\ 0,& \text{otherwise}\end{array}& \left(5.268\right)\end{array}$$

The resulting signal g[n] is a circularly time reversed version of x[n], that is

$$\begin{array}{ll}g\left[n\right]=x{\left[-n\right]}_{\mathrm{mod}N}& \left(5.269\right)\end{array}$$

The process that led to Eqn. (5.269) is illustrated in Fig. 5.51 for an example length-8 signal.

For DFT-related operations the definitions of conjugate symmetry properties also need to be adjusted so that they utilize circular time reversals. A length-8 signal x[n] is circularly conjugate symmetric if it satisfies

$$\begin{array}{ll}{x}^{*}\left[n\right]=x{\left[-n\right]}_{\mathrm{mod}N}& \left(5.270\right)\end{array}$$

or circularly conjugate antisymmetric if it satisfies

$$\begin{array}{ll}{x}^{*}\left[n\right]=-x{\left[-n\right]}_{\mathrm{mod}N}& \left(5.271\right)\end{array}$$

A signal that satisfies neither Eqn. (5.270) nor Eqn. (5.271) can still be decomposed into two components such that one is circularly conjugate symmetric and the other is circularly conjugate antisymmetric. The conjugate symmetric component is computed as

$$\begin{array}{ll}{x}_E\left[n\right]=\frac{x\left[n\right]+x^{*}{\left[-n\right]}_{\mathrm{mod}N}}{2}& \left(5.272\right)\end{array}$$

and the conjugate antisymmetric component is computed as

$$\begin{array}{ll}{x}_O\left[n\right]=\frac{x\left[n\right]-x^{*}{\left[-n\right]}_{\mathrm{mod}N}}{2}& \left(5.273\right)\end{array}$$

respectively, so that

$$\begin{array}{ll}x\left[n\right]=x_E\left[n\right]+x_O\left[n\right]& \left(5.274\right)\end{array}$$

We are now ready to explore the properties of the DFT. All properties listed in this section assume length-N signals and transforms.

Linearity

Linearity property is easily proven starting with the forward DFT equation in Eqn. (5.255).

Time shifting

Circular shifting of the signal x[n] causes the DFT to be multiplied by a complex exponential function.

Consistency check: Let the signal be circularly shifted by exactly one period, that is, m = N. We know that

$$x{\left[n-N\right]}_{\mathrm{mod}N}=x\left[n\right]$$

In this case the exponential function on the right side of Eqn. (5.276) would be e−j(2π/N)kN = 1, and the transform remains unchanged, as expected.

Example 5.35: Gaining insight into the time shifting property of DFT

Let a signal x[n] be given by

$$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{a},b,c,d\right\}$$

where a, b, c, d represent arbitrary signal amplitudes. Write X[k], the DFT of x[n], in terms of the parameters a, b, c, d. Afterwards construct the transform

$$G\left[k\right]=e^{-2\pi k/4}X\left[k\right]$$

and determine the signal g[n] to which it corresponds.

Solution: The DFT of x[n] is

$$\begin{array}{ll}X\left[k\right]=a+b{e}^{-j\pi k/2}+c{e}^{-j\pi k}+d^{-j3\pi k/2}& \left(5.277\right)\end{array}$$

The transform G[k] is obtained as

$$G\left[k\right]=e^{-2\pi k/4}X\left[k\right]=a{e}^{-j\pi k/2}+b{e}^{-j\pi k}+c{e}^{-j3\pi k/2}+d{e}^{-j2\pi k}$$

Realizing that e−j2πk = 1 for any integer value of k, Eqn. (5.278) can be written as

$$\begin{array}{ll}G\left[k\right]=d+a{e}^{-j\pi k/2}+b{e}^{-j\pi k}+c{e}^{-j3\pi k/2}& \left(5.278\right)\end{array}$$

Comparing Eqn. (5.278) with Eqn. (5.277) we conclude that G[k] is the DFT of the signal

$$g\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{d},a,b,c\right\}$$

which is a circularly shifted version of x[n], that is,

$$g\left[n\right]=x{\left[n-1\right]}_{\mathrm{mod}4}$$

Time reversal

Example 5.36: Gaining insight into the time reversal property of DFT

Consider again the signal x[n] used in Example 5.35:

$$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{a},b,c,d\right\}$$

The transform X[k] = DFT {x[n]} was derived in Eqn. (5.277). Construct the transform

$$G\left[k\right]=X{\left[-k\right]}_{\mathrm{mod}4}$$

and determine the signal g[n] to which it corresponds.

Solution: Writing X[k] for each value of the index k we get

$$\begin{array}{l}X\left[0\right]=a+b+c+d\\ X\left[1\right]=\left(a-c\right)-j\left(b-d\right)\\ X\left[2\right]=a-b+c-d\\ X\left[3\right]=\left(a-c\right)+j\left(b-d\right)\end{array}$$

The transform G[k] is a circularly time reversed version of X[k]. Its samples are

$$\begin{array}{l}G\left[0\right]=X\left[0\right]=a+b+c+d\\ G\left[1\right]=X\left[1\right]=\left(a-c\right)-j\left(d-b\right)\\ G\left[2\right]=X\left[2\right]=a-b+c-d\\ G\left[3\right]=X\left[3\right]=\left(a-c\right)+j\left(d-b\right)\end{array}$$

Comparing G[k] with X[k] we conclude that the expressions for G[0] through G[3] can be obtained from those for X[0] through X[3] by simply swapping the roles of the parameters b and d. Consequently the signal g[n] is

$$g\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{a},d,c,b\right\}$$

which is a circularly reversed version of x[n], that is,

$$g\left[n\right]=x{\left[-n\right]}_{\mathrm{mod}4}$$

Conjugation property

Symmetry of the DFT

If the signal x[n] is real-valued, it can be shown that its DFT is circularly conjugate symmetric. Conversely, if the signal x[n] is purely imaginary, its transform is circularly conjugate antisymmetric. When we discuss symmetry properties in the context of the DFT we will always imply circular symmetry. If the signal x[n] is conjugate symmetric, its DFT is purely real. In contrast, the DFT of a conjugate antisymmetric signal is purely imaginary.

Consider a length-N signal x[n] that is complex-valued. In Cartesian complex form x[n] can be written as

$$x\left[n\right]=x_r\left[n\right]+j{x}_i\left[n\right]$$

Let the discrete Fourier transform X[k] of the signal x[n] be written in terms of its conjugate symmetric and conjugate antisymmetric components as

$$X\left[k\right]=X_E\left[k\right]+X_O\left[k\right]$$

The transform relationship between x[n] and X[k] is

$$x_r\left[n\right]+j{x}_i\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }{X}_E\left[k\right]+X_O\left[k\right]$$

We know from Equation (5.281) and Equation (5.282) that the DFT of a real signal must be conjugate symmetric, and the DFT of a purely imaginary signal must be conjugate antisymmetric. Therefore it follows that the following must be valid transform pairs:

$$\begin{array}{ll}{x}_r\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }{X}_E\left[k\right]& \left(5.285\right)\end{array}$$

$$\begin{array}{ll}j{x}_i\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }{X}_O\left[k\right]& \left(5.286\right)\end{array}$$

A similar argument can be made by writing the signal x[n] as the sum of a conjugate symmetric signal and a conjugate antisymmetric signal

$$x\left[n\right]=x_E\left[n\right]+x_O\left[n\right]$$

and writing the transform X[k] in Cartesian complex form

$$X\left[k\right]=X_r\left[k\right]+j{X}_i\left[k\right]$$

The transform relationship between the two is

$$x_E\left[n\right]+x_O\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }{X}_r\left[k\right]+j{X}_i\left[k\right]$$

which leads to the following transform pairs:

$$\begin{array}{ll}{x}_E\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }{X}_r\left[k\right]& \left(5.287\right)\end{array}$$

$$\begin{array}{ll}{x}_O\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }j{X}_i\left[k\right]& \left(5.288\right)\end{array}$$

Example 5.37: Using symmetry properties of the DFT

The DFT of a length-4 signal x[n] is given by

$$X\left[k\right]=\left\{\underset{\stackrel{\uparrow }{k=0}}{\left(2+j3\right)},\left(1+j5\right),\left(-2+j4\right),\left(-1-j3\right)\right\}$$

Without computung x[n] first, determine the DFT of xr[n], the real part of x[n].

Solution: We know from the symmetry properties of the DFT that the transform of the real part of x[n] is the conjugate symmetric part of X[k]:

$$\text{DFT}\left\{x_r\left[n\right]\right\}=X_E\left[k\right]=\frac{X\left[k\right]+X^{*}{\left[-k\right]}_{\mathrm{mod}N}}{2}$$

The complex conjugate of the time reversed transform is

$$X^{*}{\left[-k\right]}_{\mathrm{mod}4}=\left\{\left(\underset{\stackrel{\uparrow }{k=0}}{2-j3}\right),\left(-1+j3\right),\left(-2,-j4\right),\left(1-j5\right)\right\}$$

The conjugate symmetric component of X[k] is

$$X_E\left[k\right]=\left\{\underset{\stackrel{\uparrow }{k=0}}{2},j4,-2,-j4\right\}$$

The real part of x[n] can be found as the inverse transform of XE[k]:

$$x_r\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{0},-1,0,3\right\}$$

Example 5.38: Using symmetry properties of the DFT to increase efficiency

Consider the real-valued signals g[n] and h[n] specified as

$$\begin{array}{l}g\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{11},-2,7,9\right\}\\ h\left(n\right)=\left\{\underset{\stackrel{\uparrow }{n=0}}{6},14,-13,8\right\}\end{array}$$

Devise a method of obtaining the DFTs of g[h] and h[n] by computing only one 4-point DFT and utilizing symmetry properties.

Solution: Let us construct a complex signal x[n] as

$$\begin{array}{l}x\left[n\right]=g\left[n\right]+jh\left[n\right]\\ =\left\{\left(11\underset{\stackrel{\uparrow }{n=0}}{+}j6\right),\left(-2+j14\right),\left(7-j13\right),\left(9+j8\right)\right\}\end{array}$$

The 4-point XFT of x[n] is

$$X\left[k\right]=\left\{\left(25\underset{\stackrel{\uparrow }{k=0}}{+}j15\right),\left(10+j30\right),\left(11-j29\right),\left(-2+j8\right)\right\}$$

The conjugate symmetric component of X[k] is

$$X_E\left[k\right]=\frac{X\left[k\right]+X^{*}{\left[-k\right]}_{\mathrm{mod}4}}{2}=\left\{\underset{\underset{k=0}{\uparrow }}{25},\left(4+j11\right),11,\left(4-j11\right)\right\}$$

and its conjugate antisymmetric component is

$$X_O\left[k\right]=\frac{X\left[k\right]-X^{*}{\left[-k\right]}_{\mathrm{mod}4}}{2}=\left\{\underset{\underset{k=0}{\uparrow }}{j15},\left(6+j19\right),-j29,\left(-6+j19\right)\right\}$$

Based on the symmetry properties of the DFT we have DFT {g[n]} = XE[k] and DFT {jh[n]} = XO[k]. Therefore

$$G\left[k\right]=X_E\left[k\right]\left\{\underset{\stackrel{\uparrow }{k=0}}{25},\left(4+j11\right),11,\left(4-j11\right)\right\}$$

and

$$H\left[k\right]=-j{X}_O\left[k\right]=\left\{\underset{\stackrel{\uparrow }{k=0}}{15},\left(19-j6\right),-29,\left(19+j6\right)\right\}$$

It can easily be verified that G[k] and H[k] found above are indeed the DFTs of the two signals g[n] and h[n].

Software resources:

ex_5_38.m

Frequency shifting

Circular convolution

Periodic convolution of two periodic signals $\tilde{x}\left[n\right]$ and $\tilde{h}\left[n\right]$ was defined in Section 5.2.2, Eqn. (5.47). In this section we will define circular convolution for length-N signals in the context of the discrete Fourier transform. Let x[n] and h[n] be length-N signals. Consider the following set of steps:

1. Obtain periodic signals $\tilde{x}\left[n\right]$ and $\tilde{h}\left[n\right]$ as periodic extensions of x[n] and h[n]:

   $$\begin{array}{l}\tilde{x}\left[n\right]={\displaystyle \sum _{m=-\infty }^{\infty }x\left[n+mN\right]}\\ \tilde{h}\left[n\right]={\displaystyle \sum _{m=-\infty }^{\infty }h\left[n+mN\right]}\end{array}$$

2. Compute $\tilde{y}\left[n\right]$ as the periodic convolution of $\tilde{x}\left[n\right]$ and $\tilde{h}\left[n\right]$.

   $$\tilde{y}\left[n\right]=\tilde{x}\left[n\right]\otimes \tilde{h}\left[n\right]={\displaystyle \sum _{k=0}^{N-1}\tilde{x}\left[k\right]\tilde{h}\left[n-k\right]}$$

3. Let y[n] be the length-N signal that is equal to one period of $\tilde{y}\left[n\right]$:

   $$\begin{array}{ll}y\left[n\right]=\tilde{y}\left[n\right],& \text{for }n=0,\mathrm{...},N-1\end{array}$$

The signal y[n] is the circular convolution of x[n] and h[n]. It can be expressed in compact form as

$$\begin{array}{lll}y\left[n\right]=x\left[n\right]\otimes h\left[n\right]={\displaystyle \sum _{k=0}^{N-1}x\left[k\right]h{\left[n-k\right]}_{\mathrm{mod}N}},& n=0,\mathrm{...},N-1& \left(5.290\right)\end{array}$$

Example 5.39: Circular convolution of two signals

Determine the circular convolution of the length-5 signals

$$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},3,2,-4,6\right\}$$

and

$$h\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{5},4,3,2,1\right\}$$

using the definition of circular convolution given by Eqn. (5.290).

Solution: Adapting Eqn. (5.290) to length-5 signals we have

$$\begin{array}{ll}y\left[n\right]=x\left[n\right]\otimes h\left[n\right]={\displaystyle \sum _{k=0}^{4}x\left[k\right]h{\left[n-k\right]}_{\mathrm{mod}5}},& n=0,1,2,3,4\end{array}$$

Fig. 5.52 illustrates the steps involved in computing the circular convolution. The result is

$$y\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{24},31,33,5,27\right\}$$

The circular convolution property of the discrete Fourier transform can be stated as follows:

This is a very significant result in the use of the DFT for signal processing applications. The proof is straightforward using the periodic convolution property of the discrete-time Fourier series (DTFS), and will be given here.

Example 5.40: Circular convolution through DFT

Consider again the length-5 signals x[n] and h[n] of Example 5.39. The circular convolution

$$y\left[n\right]=x\left[n\right]\otimes h\left[n\right]$$

was determined in Example 5.39 in the time-domain. Verify the circular convolution property of the DFT using these signals.

Solution: Table 5.5 lists the DFT for the three signals. It can easily be verified that

$$Y\left[k\right]=X\left[k\right]H\left[k\right]$$

Software resources:

ex_5_40.m

If the circular convolution of two length-N signals is desired, the convolution property of the DFT provides an easy and practical method of computing it.

In most applications of signal processing, however, we are interested in computing the linear convolution of two signals rather than their circular convolution. The output signal of a DTLTI system is equal to the linear convolution of its impulse response with the input signal. The ability to use the DFT as a tool for the computation of linear convolution is very important due to the availability of fast and efficient algorithms for computing the DFT. Therefore, the following two questions need to be answered:

1. How is the circular convolution of two length-N signals related to their linear convolution?
2. What can be done to ensure that the circular convolution result obtained using the DFT method matches the linear convolution result?

The next example will address the first question.

Example 5.41: Linear vs. circular convolution

Consider again the length-5 signals x[n] and h[n] of Example 5.39.

$$\begin{array}{l}x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},3,2,-4,6\right\}\\ h\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{5},4,3,2,1\right\}\end{array}$$

The circular convolution of these two signals was determined in Example 5.39 as

$$\begin{array}{ll}y\left[n\right]=x\left[n\right]\otimes h\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{24},31,33,5,27\right\}& \left(5.297\right)\end{array}$$

The linear convolution of x[n] and h[n], computed using the convolution sum

$$y_l\left[n\right]={\displaystyle \sum _{k=-\infty }^{\infty }x\left[k\right]h\left[n-k\right]}$$

is found as

$$\begin{array}{ll}{y}_l\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{5},19,25,-1,27,19,12,8,6\right\}& \left(5.298\right)\end{array}$$

Note that in Eqn. (5.298) we have used the notation y [n] for linear convolution to differentiate it from the circular convolution result of Eqn. (5.297). The most obvious difference between the two results y[n] and y [n] is the length of each. The circular convolution result is 5 samples long, however the linear convolution result is 9 samples long. This is the first step toward explaining why the DFT method does not produce the linear convolution result. X[k] and H[k] are length-5 transforms, and the inverse DFT of their product yields a length-5 result for y[n].

How does yl [n] relate to y[n]? Imagine filling out a form that has 5 boxes for entering values, yet we have 9 values we must enter. We start from with the leftmost box and enter the first 5 of 9 values. At this point each box has a value in it, and we still have 4 more values not entered into any box. Suppose we decide to go back to the leftmost box, and start entering additional values into each box as needed. This is illustrated in Fig. 5.53 using the samples of the linear convolution result to fill the boxes.

Each sample of the circular convolution result is equal to the sum of values in the corresponding box. For example, y[0] = yl [0] + yl [5] and y[1] = yl [1] + yl [6]. If a box has a single value, the circular convolution result is identical to the linear convolution result for the corresponding n. For boxes that have multiple entries, the circular convolution result is a corrupted version of the linear convolution result.

Software resources:

ex_5_41.m

Generalizing the results of Example 5.41 the circular convolution of two signals can be expressed in terms of their linear convolution as

$$\begin{array}{ll}y\left[n\right]={\displaystyle \sum _{m=-\infty }^{\infty }{y}_l\left[n+mN\right]}& \left(5.299\right)\end{array}$$

If the circular convolution result is desired to be identical to the linear convolution result, the length of the circular convolution result must be sufficient to accommodate the number of samples expected from linear convolution. Using the analogy employed in Example 5.41, namely filling out a form with the results, there must be enough “boxes” to accommodate all samples of yl[k] without any overlaps. One method of achieving this is through zero-padding x[n] and h[n] before the computation of the DFT.

5.8.4 Using the DFT to approximate the EFS coefficients

EFS representation of a continuous-time signal xa (t) periodic with a period T0 was given in Eqn. (4.72) in Chapter 4 which is repeated below:

$$\begin{array}{ll}\text{Eqn}\text{. }\left(4.72\right)& c_k=\frac{1}{T_0}{\displaystyle {\int }_{t_0}^{t_0+T_0}{x}_a\left(t\right)e^{-jk{\omega }_{0}t}dt}\end{array}$$

One method of approximating the coefficients ck on a computer is by approximating the integral in Eqn. (4.72) using the rectangular approximation method. More sophisticated methods for approximating integrals exist, and are explained in detail in a number of excellent texts on numerical analysis. The rectangular approximation method is quite simple, and will be sufficient for our purposes.

Suppose we would like to approximate the following integral:

$$\begin{array}{ll}G={\displaystyle {\int }_0^{T_0}g\left(t\right)dt}& \left(5.300\right)\end{array}$$

Since integrating the function g (t) amounts to computing the area under the function, a simple approximation is

$$\begin{array}{ll}G\approx {\displaystyle \sum _{n=0}^{N-1}g\left(nT\right)T}& \left(5.301\right)\end{array}$$

We have used the sampling interval T = T0/N and assumed that N is sufficiently large for the approximation to be a good one. The area under the function g (t) is approximated using the areas of successive rectangles formed by the samples g (nT). This is depicted graphically in Fig. 5.54.

For the purpose of approximating Eqn. (4.72) let g (t) be chosen as

$$\begin{array}{ll}g\left(t\right)=\frac{1}{T_0}{x}_a\left(t\right)e^{-jk{\omega }_{0}t}& \left(5.302\right)\end{array}$$

so that the integral in Eqn. (4.72) is approximated as

$$\begin{array}{ll}{c}_k\approx \frac{1}{T_0}{\displaystyle \sum _{n=0}^{N-1}{x}_a\left(nT\right)e^{-jk{\omega }_{0}nT}T}& \left(5.303\right)\end{array}$$

Recalling that T0 = NT and ω0 = 2π/T0, and using the discrete-time signal x[n] = xa (nT), we have

$$\begin{array}{ll}{c}_k\approx \frac{1}{N}{\displaystyle \sum _{n=0}^{N-1}x\left(n\right)e^{-j\left(2\pi /N\right)kn}\frac{1}{N}X\left[k\right]}& \left(5.304\right)\end{array}$$

The EFS coefficients of a periodic signal can be approximated by sampling the signal at N equally spaced time instants over one period, computing the DFT of the resulting discrete-time signal x[n], and scaling the DFT result by 1/N. Some caveats are in order:

1. The number of samples over one period, N, should be sufficiently large. If we want to be more rigorous, the conditions of the Nyquist sampling theorem must be observed, and the sampling rate fs = 1/T should be at least twice the highest frequency in the periodic signal x (t).

2. Only the first half of the DFT values can be used as approximations for positive indexed coefficients, that is

   $$\begin{array}{ll}{c}_k\approx \frac{1}{N}X\left[k\right],k=0,\mathrm{...},\frac{N}{2}-1& \left(5.305\right)\end{array}$$

   with negative indexed coefficients obtained from the second half of the DFT by

   $$\begin{array}{ll}{c}_{-k}\approx \frac{1}{N}X\left[N-k\right],k=1,\mathrm{...},\frac{N}{2}& \left(5.306\right)\end{array}$$

3. If the conditions of the Nyquist sampling theorem cannot be satisfied in a strict sense (such as when we try to approximate the Fourier series of a pulse train which is not limited in terms of the highest frequency it contains), only the first few terms of each set in Equation (5.305) and Equation (5.306) should be used to keep the quality of the approximation acceptable.

5.8.5 Using the DFT to approximate the continuous Fourier transform

It is also possible to use the DFT for approximating the Fourier transform of a non-periodic continuous-time signal. For a signal xa (t) the Fourier transform was defined by Eqn. (4.127) in Chapter 4 which is repeated here:

$$\begin{array}{lll}\text{Eqn}\text{. }\left(4.127\right)& X_a\left(\omega \right)={\displaystyle {\int }_{-\infty }^{\infty }{x}_a\left(t\right)e^{-j\omega t}dt}& \left(5.307\right)\end{array}$$

Suppose xa (t) is a finite-length signal that is zero outside the interval 0 ≤ t ≤ t1. The integral in Eqn. (4.127) can be written as

$$\begin{array}{ll}{X}_a\left(\omega \right)={\displaystyle {\int }_0^{t_1}{x}_a\left(t\right)e^{-jwt}dt}& \left(5.308\right)\end{array}$$

The integral can be evaluated in an approximate sense using the rectangular approximation technique outlined in Eqn. (5.301) with

$$\begin{array}{ll}g\left(t\right)=x_a\left(t\right)e^{-j\omega t}& \left(5.309\right)\end{array}$$

The function g (t) needs to be sampled at N equally spaced time instants in the interval 0 ≤ t ≤ t1, and thus NT = t1. Rectangular rule approximation to the integral in Eqn. (5.308) is

$$\begin{array}{ll}{X}_a\left(\omega \right)\approx {\displaystyle \sum _{n=0}^{N-1}{x}_a\left(nT\right)e^{-j\omega nT}T}& \left(5.310\right)\end{array}$$

Using the discrete-time signal x[n] = xa (nT) and evaluating Eqn. (5.310) at a discrete set of frequencies

$$\begin{array}{ll}{\omega }_k=\frac{k{w}_s}{N}=\frac{2\pi k}{NT},& k=0,\mathrm{...},N-1\end{array}$$

where ωs is the sampling rate in rad/s, we obtain

$$\begin{array}{ll}{X}_a\left({\omega }_k\right)\approx T{\displaystyle \sum _{n=0}^{N-1}x\left[n\right]e^{-j\left(2\pi /N\right)kn}=TX\left[k\right]}& \left(5.311\right)\end{array}$$

The Fourier transform of a continuous-time signal can be approximated by sampling the signal at N equally spaced time instants, computing the DFT of the resulting discrete-time signal x[n], and scaling the DFT result by the sampling interval T. It is also possible to obtain the approximation for Xa (ω) at a more closely spaced set of frequencies than ωk = kωs/N by zero-padding x[n] prior to computing the DFT. Let

$${\overline{\omega }}_k=\frac{k{\omega }_s}{N+M}=\frac{2\pi k}{\left(N+M\right)T},k=0,\mathrm{...},N+M-1$$

where M is an integer. Using ${\overline{\omega }}_k$ in Eqn. (5.311) leads to

$$\begin{array}{ll}{X}_a\left({\overline{\omega }}_k\right)\approx T{\displaystyle \sum _{n=0}^{N-1}x\left[n\right]e^{-j2\pi kn\left(N+M\right)}}& \left(5.312\right)\end{array}$$

The summation on the right side of Eqn. (5.312) is the DFT of the signal x[n] zero-padded with M additional samples.

As noted in the discussion of the previous section, the conditions of the Nyquist sampling theorem apply to this case as well. Ideally we would have liked the sampling rate ωs to be at least twice the highest frequency of the signal the transform of which is being approximated. On the other hand, it can be shown that a time-limited signal contains an infinite range of frequencies, and strict adherence to the Nyquist sampling theorem is not even possible. Approximation errors are due to the aliasing that occurs in sampling a time-limited signal. For the approximation to be acceptable, we need to ensure that the effect of aliasing is negligible.

Based on the Nyquist sampling theorem, only the first half of the DFT samples in Equation (5.311) and Equation (5.312) should be used for approximating the transform Xa (ω) at positive frequencies in the range 0 ≤ ω < ωs/2. The second half of the DFT samples represent an approximation to the transform Xa (ω) in the negative frequency range −ωs/2 ≤ ω< 0.

5.9 Further Reading

[1] R.J. Beerends. Fourier and Laplace Transforms. Cambridge University Press, 2003.

[2] A. Boggess and F.J. Narcowich. A First Course in Wavelets with Fourier Analysis. Wiley, 2011.

[3] S.C. Chapra. Applied Numerical Methods with MATLAB for Engineers and Scientists. McGraw-Hill, 2008.

[4] S.C. Chapra and R.P. Canale. Numerical Methods for Engineers. McGraw-Hill, 2010.

[5] D.G. Manolakis and V.K. Ingle. Applied Digital Signal Processing: Theory and Practice. Cambridge University Press, 2011.

[6] A.V. Oppenheim and R.W. Schafer. Discrete-Time Signal Processing. Prentice Hall, 2010.

[7] L. Tan and J. Jiang. Digital Signal Processing: Fundamentals and Applications. Elsevier Science, 2013.

[8] J.S. Walker. Fast Fourier transforms. Studies in Advanced Mathematics. Taylor & Francis, 1996.

MATLAB Exercises

Problems

1. 5.1. Determine the DTFS representation of the signal $\tilde{x}\left[n\right]=\cos \left(0.3\pi n\right)$. Sketch the DTFS spectrum.

2. 5.2. Determine the DTFS representation of the signal $\tilde{x}\left[n\right]=1+\cos \left(0.24\pi n\right)+3\sin \left(0.56\pi n\right)$. Sketch the DTFS spectrum.

3. 5.3. Determine the DTFS coefficients for each of the periodic signals given in Fig. P.5.3.

   Figure P. 5.3

   

4. 5.4. Consider the periodic signal of Example 5.4. Let $\tilde{g}\left[n\right]$ be one sample delayed version of it, that is,

   $$\tilde{g}\left[n\right]=\tilde{x}\left[n-1\right]$$

   as shown in Fig. P.5.4.

   Figure P. 5.4

   

   1. Determine the DTFS coefficients of $\tilde{g}\left[n\right]$ directly from the DTFS analysis equation.
   2. Determine the DTFS coefficients of $\tilde{g}\left[n\right]$ by applying the time shifting property to the coefficients of $\tilde{x}\left[n\right]$ that were determined in Example 5.4.

5. 5.5. Verify that the DTFS coefficients found for the signals in Problem 5.3 satisfy the conjugate symmetry properties outlined in Section 5.2.2. Since the signals are real, DTFS spectra should be conjugate symmetric.

6. 5.6. Consider the periodic signal shown in Fig. P.5.4.

   1. Find even and odd components of $\tilde{g}\left[n\right]$ so that

      $$\tilde{g}\left[n\right]={\tilde{g}}_e\left[n\right]+{\tilde{g}}_0\left[n\right]$$

   2. Determine the DTFS coefficients of ${\tilde{g}}_e\left[n\right]$ and ${\tilde{g}}_0\left[n\right]$. Verify the symmetry properties outlined in Section 5.2.2. The spectrum of the even component should be real, and the spectrum of the odd component should be purely imaginary.

7. 5.7. Let $\tilde{x}\left[n\right]$ and $\tilde{h}\left[n\right]$ be both periodic with period N. Using the definition of periodic convolution given by Eqn. (5.49), show that the signal

   $$\tilde{y}\left[n\right]=\tilde{x}\left[n\right]\otimes \tilde{h}\left[n\right]$$

   is also periodic with period N.

8. 5.8. Consider the two periodic signals shown in Fig. P.5.8.

   Figure P. 5.8

   

   1. Compute the periodic convolution

      $$\tilde{y}\left[n\right]=\tilde{x}\left[n\right]\otimes \tilde{h}\left[n\right]$$

      of the two signals.

   2. Determine the DTFS coefficients of signals $\tilde{x}\left[n\right]$, $\tilde{h}\left[n\right]$ and $\tilde{y}\left[n\right]$. Verify that the periodic convolution property stated by Eqn. (5.49) holds.

9. 5.9. Repeat Problem 5.8 for the two signals shown in Fig. P.5.9.

   Figure P. 5.9

   

10. 5.10. Find the DTFT of each signal given below. For each, sketch the magnitude and the phase of the transform.

    1. x[n] = δ[n] + δ[n − 1]
    2. x[n] = δ[n] − δ[n − 1]
    3. $$x\left[n\right]=\{\begin{array}{ll}1,\hfill & n=0,1,2,3\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    4. $$x\left[n\right]=\{\begin{array}{ll}1,\hfill & n=-2,\mathrm{...},2\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    5. x[n] = (0.7)n u[n]
    6. x[n] = (0.7)n cos (0.2πn) u[n]

11. 5.11. Find the inverse DTFT of each transform specified below for −π ≤ Ω < π.

    1. $$X\left(\Omega \right)=\{\begin{array}{ll}1,\hfill & \left|\Omega \right|<0.2\pi \hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    2. $$X\left(\Omega \right)=\{\begin{array}{ll}1,\hfill & \left|\Omega \right|<0.4\pi \hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    3. $$X\left(\Omega \right)=\{\begin{array}{ll}0,\hfill & \left|\Omega \right|<0.2\pi \hfill \\ 1,\hfill & \text{otherwise}\hfill \end{array}$$
    4. $$X\left(\Omega \right)=\{\begin{array}{ll}1,\hfill & 0.1\pi <\left|\Omega \right|<0.2\pi \hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

12. 5.12. Use linearity and time shifting properties of the DTFT to find the transform of each signal given below.

    1. x[n] = (0.5)n u[n − 2]
    2. x[n] = (0.8)n (u[n] − u[n − 10])
    3. x[n] = (0.8)n (u[n + 5] − u[n − 5])

13. 5.13. Use linearity and time reversal properties of the DTFT to find the transform of the signals listed below:

    1. x[n] = (2)n u[−n − 1]
    2. x[n] = (1.25)n u[−n]
    3. x[n] = (0.8)|n|
    4. x[n] = (0.8)|n| (u[n + 5] + u[n − 5])

14. 5.14. Prove that the DTFT of a signal with odd symmetry is purely imaginary. In mathematical terms, if

    $$x\left[-n\right]=-x\left[n\right]$$

    then

    $$X^{*}\left(\Omega \right)=-X\left(\Omega \right)$$

15. 5.15. Signals listed below have even symmetry. Determine the DTFT of each, and graph the magnitude of the transform.

    1. $$x\left[n\right]=\{\begin{array}{ll}1,\hfill & n=0\hfill \\ 1/2,\hfill & n=\pm 1\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    2. $$x\left[n\right]=\{\begin{array}{ll}5-\left|n\right|,\hfill & \left|n\right|\le 4\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    3. $$x\left[n\right]=\{\begin{array}{ll}\cos \left(0.2\pi n\right),\hfill & n=-4,\mathrm{...},4\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

16. 5.16. Signals listed below have odd symmetry. For each signal determine the DTFT. Graph the magnitude and the phase of the transform.

    1. $$x\left[n\right]=\{\begin{array}{ll}-1/4,\hfill & n=-2\hfill \\ -1/2,\hfill & n=-1\hfill \\ 1/2,\hfill & n=1\hfill \\ 1/4,\hfill & n=2\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    2. $$x\left[n\right]=\{\begin{array}{ll}n,\hfill & n=-5,\mathrm{...},5\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$
    3. $$x\left[n\right]=\{\begin{array}{ll}\sin \left(0.2\pi n\right),\hfill & n=-4,\mathrm{...},4\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

17. 5.17. Determine the transforms of the signals listed below using the modulation property of the DTFT. Sketch the magnitude and the phase of the transform for each.

    1. x[n] = (0.7)n cos (0.2πn) u[n]
    2. x[n] = (0.7)n sin (0.2πn) u[n]
    3. x[n] = cos (πn/5) (u[n] − u[n − 10])

18. 5.18. Use the differentiation in frequency property of the DTFT to find the transforms of the signals listed below.

    1. x[n] = n (0.7)n u[n]
    2. x[n] = n (n + 1) (0.7)n u[n]
    3. x[n] = n (0.7)n (u[n] − u[n − 10])

19. 5.19. Two signals x[n] and h[n] are given by

    $$\begin{array}{lll}x\left[n\right]=u\left[n\right]-u\left[n-10\right]& \text{and}& h\left[n\right]={\left(0.8\right)}^{n}u\left[n\right]\end{array}$$

    1. Determine the DTFT for each signal.
    2. Let y[n] be the convolution of these two signals, that is, y[n] = x[n] * h[n]. Compute y[n] by direct application of the convolution sum.

    3. Determine the DTFT of y[n] by direct application of the DTFT analysis equation. Verify that it is equal to the product of the individual transforms of x[n] and h[n]:

       $$Y\left(\Omega \right)=X\left(\Omega \right)H\left(\Omega \right)$$

20. 5.20. Determine and sketch the DTFTs of the following periodic signals.

    1. x[n] = ej0.3πn
    2. x[n] = ej0.2πn + 3ej0.4πn
    3. x[n] = cos (πn/5)
    4. x[n] = 2 cos (πn/5) + 3 cos (2πn/5)

21. 5.21. Determine and sketch the power spectral density for each signal shown in Fig. P.5.3.

22. 5.22. Consider the periodic signal

    $$\begin{array}{lll}\tilde{x}\left[n\right]=\{\begin{array}{ll}1,\hfill & -L\le n\le L\hfill \\ 0,\hfill & L<n<N-L\hfill \end{array}& \text{and}& \tilde{x}\left[n+N\right]=\tilde{x}\left[n\right]\end{array}$$

    Recall that the DTFS representation of this signal was found in Example 5.5.

    1. Find the power spectral density Sx (Ω).
    2. Let N = 40 and L = 3. Determine what percentage of signal power is preserved if only three harmonics are kept and the others are discarded.
    3. Repeat part (b) with N = 40 and L = 6.

23. 5.23. A DTLTI system is characterized by the difference equation

    $$y\left[n\right]+y\left[n-1\right]+0.89y\left[n-2\right]=x\left[n\right]+2x\left[n-1\right]$$

    Determine the steady-state response of the system to the following input signals:

    1. x[n] = ej0.2πn
    2. x[n] = cos (0.2πn)
    3. x[n] = 2 sin (0.3πn)
    4. x[n] = 3 cos (0.1πn) − 5 sin (0.2πn)

    Hint: First find the system function H (Ω).

24. 5.24. Determine the steady-state response of a length-4 moving average filter to the following signals.

    1. x[n] = ej0.2πn
    2. x[n] = cos (0.2πn)
    3. x[n] = 2 sin (0.3πn)
    4. x[n] = 3 cos (0.1πn) − 5sin (0.2πn)

25. 5.25. A DTLTI system is characterized by the difference equation

    $$y\left[n\right]+y\left[n-1\right]+0.89y\left[n-2\right]=x\left[n\right]+2x\left[n-1\right]$$

    Using the technique outlined in Section 5.6.3 find the steady-state response of the system to each of the periodic signals shown in Fig. P.5.3.

26. 5.26. Compute the DFTs of the signals given below.

    1. $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,1\right\}$$
    2. $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,0,0\right\}$$
    3. $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,0,0,0,0\right\}$$

27. 5.27. Compute the DFTs of the signals given below. Simplify the results and show that each transform is purely real.

    1. $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,0,0,0,0,0,1\right\}$$
    2. $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,0,0,0,1,1\right\}$$
    3. $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,1,0,1,1,1\right\}$$

28. 5.28. It is possible to express the forward DFT in matrix form using the compact form of the DFT definition given by Eqn. (5.253). Given the signal x[n]; n = 0,...,N − 1 and its DFT X[k]; k = 0,...,N − 1, let the vectors x and X be defined as

    $$\begin{array}{ll}x=\left[\begin{array}{l}x\left[0\right]\\ x\left[1\right]\\ ⋮\\ x\left[N-1\right]\end{array}\right],& X=\left[\begin{array}{l}X\left[0\right]\\ X\left[1\right]\\ ⋮\\ X\left[N-1\right]\end{array}\right]\end{array}$$

    Show that the discrete Fourier transform can be computed as

    $$X=Wx$$

    Construct the N × N coefficient matrix W.

29. 5.29. For each finite-length signal listed below, find the specified circularly shifted version.

    1. $$\begin{array}{ll}x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{4},3,2,1\right\}& \text{find }x{\left[n-2\right]}_{\mathrm{mod}4}\end{array}$$
    2. $$\begin{array}{ll}x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,0,0\right\}& \text{find }x{\left[n-4\right]}_{\mathrm{mod}5}\end{array}$$
    3. $$\begin{array}{ll}x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},4,2,3,1,-2,-3,1\right\}& \text{find }x{\left[-n\right]}_{\mathrm{mod}8}\end{array}$$
    4. $$\begin{array}{ll}x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},4,2,3,1,-2,-3,1\right\}& \text{find }x{\left[-n+2\right]}_{\mathrm{mod}8}\end{array}$$

30. 5.30. Refer to Problem 5.29. Find the circularly conjugate symmetric and antisymmetric components xE[n] and xO[n] for each signal listed.

31. 5.31. Consider the finite-length signal

    $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,0,0\right\}$$

    1. Compute the 5-point DFT X[k] for k = 0,..., 4.
    2. Multiply the DFT found in part (a) with e−j2πk/5 to obtain the product

       $$\begin{array}{ll}R\left[k\right]=e^{-j2\pi k/5}X\left[k\right]& \text{for }k=0,\mathrm{...},4\end{array}$$

    3. Compute the signal r[n] as the inverse DFT of R[k] and compare it to the original signal x[n].
    4. Repeat parts (b) and (c) with

       $$\begin{array}{ll}S\left[k\right]=e^{-j4\pi k/5}X\left[k\right]& \text{for }k=0,\mathrm{...},4\end{array}$$

    5. Provide justification for the answers found using the properties of the DFT.

32. 5.32. Consider the finite-length signal

    $$x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{5},4,3,2,1\right\}$$

    1. Compute the 5-point DFT X[k] for k = 0,..., 4.
    2. Reverse the DFT found in part (a) to obtain a new transform R[k] as

       $$\begin{array}{ll}R\left[k\right]=X{\left[-k\right]}_{\mathrm{mod}5}& \text{for }k=0,\mathrm{...},4\end{array}$$

    3. Compute the signal r[n] as the inverse DFT of R[k] and compare it to the original signal x[n]. Justify the answer found using the properties of the DFT.

33. 5.33. The DFT of a length-6 signal x[n] is given by

    $$X\left[k\right]=\left\{\left(2\underset{\stackrel{\uparrow }{k=0}}{+}j3\right),\left(1+j5\right),\left(-2+j4\right),\left(-1-j3\right),\left(2\right),\left(3+j1\right)\right\}$$

    Without computing x[n] first, determine

    1. The DFT of xr[n], the real part of x[n]
    2. The DFT of xi[n], the imaginary part of x[n]

34. 5.34. Two signals x[n] and h[n] are given by

    $$\begin{array}{l}x\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{2},-3,4,1,6\right\}\\ h\left[n\right]=\left\{\underset{\stackrel{\uparrow }{n=0}}{1},1,1,0,0\right\}\end{array}$$

    1. Compute the circular convolution y[n] = x[n] ⊗ h[n] through direct application of the circular convolution sum.
    2. Compute the 5-point transforms X[k] and H[k].
    3. Compute Y [k] = X[k] H[k], and the obtain y[n] as the inverse DFT of Y [k]. Verify that the same result is obtained as in part (a).

35. 5.35. Refer to the signals x[n] and h[n] in Problem 5.34. Let X[k] and H[k] represent 7-point DFTs of these signals, and let Y [k] be their product, that is, Y [k] = X[k] H[k] for k = 0,..., 6. The signal y[n] is the inverse DFT of Y [k]. Determine y[n] without actually computing any DFTs.

36. 5.36.

    1. The DFT of a length-N signal is equal to its DTFT sampled at N equally spaced angular frequencies. In this problem we will explore the possibility of sampling a DTFT at fewer than N frequency values. Let X (Ω) be the DTFT of the length-12 signal

       $$x\left[n\right]=u\left[n\right]-u\left[n-12\right]$$

       Obtain S[k] by sampling the transform X (Ω) at 10 equally spaced frequencies, that is,

       $$\begin{array}{ll}S\left[k\right]=X\left(\frac{2\pi k}{10}\right),& k=0,\mathrm{...},9\end{array}$$

       Determine s[n], the inverse DFT of S[k].

    2. Consider the general case where x[n] may be an infinitely long signal, and its DTFT is

       $$X\left(\Omega \right)={\displaystyle \sum _{n=-\infty }^{\infty }x\left[n\right]e^{-j\Omega n}}$$

       S[k] is obtained by sampling X (Ω) at N equally spaced angular frequencies:

       $$\begin{array}{ll}S\left[k\right]=X\left(\frac{2\pi k}{N}\right),& k=0,\mathrm{...},N-1\end{array}$$

       s[n] is the length-N inverse DFT of S[k]. Show that s[n] is related to x[n] by

       $$\begin{array}{ll}s\left[n\right]={\displaystyle \sum _{r=-\infty }^{\infty }x\left[n+rN\right]},& n=0,\mathrm{...},N-1\end{array}$$

MATLAB Problems

1. 5.37. Consider the periodic signals $\tilde{x}\left[n\right]$ and $\tilde{g}\left[n\right]$ shown in Fig. P.5.37.

   Figure P. 5.37

   

   Write a MATLAB script to do the following:

   1. Compute the DTFS coefficients of each signal using the function ss_dtfs (..) developed in MATLAB Exercise 5.1.
   2. Compute the DTFS coefficients of $\tilde{g}\left[n\right]$ by multiplying the DTFS coefficients of $\tilde{x}\left[n\right]$ with the proper exponential sequence as dictated by the time shifting property.
   3. Compare the results found in parts (a) and (b).

2. 5.38. Consider again the periodic signals used in Problem 5.37 and shown in Fig. P.5.37. Both signals are real-valued. Consequently, their DTFS coefficients must satisfy the conjugate symmetry property as stated by Eqn. (5.35). Verify this with the values obtained in Problem 5.37.

3. 5.39. Refer to the periodic pulse train used in Example 5.5. Write a MATLAB script to compute and graph its DTFS spectrum. Use the script to obtain graphs for the following parameter configurations:

   1. N = 30 , L = 5
   2. N = 30 , L = 8
   3. N = 40 , L = 10
   4. N = 40 , L = 15

4. 5.40. Use the MATLAB script developed in Problem 5.39 to produce graphs that duplicate the three cases shown in Fig. 5.17 parts (a), (b) and (c).

5. 5.41. Refer to Problem 5.22.

   1. Let N = 40 and L = 3. Develop a script to compute and graph a finite-harmonic approximation to x[n] using three harmonics.
   2. Repeat part (a) using a signal with N = 40 and L = 6.

6. 5.42. Refer to Problem 5.24. Write a script to compute the response of the length-4 moving average filter to each of the the signals specified in the problem. Use the function ss_movavg4(..) that was developed in MATLAB Exercise 3.1 in Chapter 3. For each input signal compute the response for n = 0,..., 49. Compare the steady-state part of the response (in this case it will be after the first three samples) to the theoretical result obtained in Problem 5.24.

7. 5.43. Refer to Problem 5.25.

   1. Develop a script to iteratively solve the difference equation given. The system should be assumed initially relaxed, that is, y[−1] = y[−2] = 0.
   2. Find the response of the system to each of the input signals in Fig. P.5.3 for n = 0,..., 49.
   3. In each of the responses, disregard the samples for n = 0,..., 24, and compare samples n = 25,..., 49 to the theoretical steady-state response computed in Problem 5.25.

   Hint: You may wish to use the function ss_per (..) that was developed in MATLAB Exercise 1.7 for creating the periodic signals needed.

8. 5.44. Refer to Problem 5.28 in which the matrix form of the forward DFT equation was explored.

   1. Develop a MATLAB function ss_dftmat (..) to construct the coefficient matrix W needed in computing the DFT. Its syntax should be

      	W = ss_dftmat (N)

      where N is the size of the DFT to be computed.

   2. Use the function ss_dftmat (..) to compute the 10-point DFT of the discrete-time pulse signal

      $$x\left[n\right]=u\left[n\right]-u\left[n-10\right]$$

      using the matrix method. Compare the result to that obtained in Example 5.33.

   3. Use the function ss_dftmat (..) to compute the 20-point DFT of the discrete-time pulse signal through zero padding the vectorx. Compare the result to that obtained in Example 5.34.

9. 5.45. Write a script to approximate the EFS coefficients of the half-wave rectified sinusoidal signal $\tilde{x}\left(t\right)$ shown in Fig. P.5.45.

   Figure P. 5.45

   

   You may wish to use the function ss_efsapprox (..) developed in MATLAB Exercise 5.12. Sample the signal with a step size of T = 0.01 s to obtain 100 samples in one period. Obtain approximate values for the coefficients ck for k = −15,..., 15 and compare to the correct values obtained in Chapter 4, Example 4.10.

10. 5.46. Refer to Problem 5.36 in which the issue of sampling a DTFT was explored. Develop a MATLAB script to perform the following steps:

    1. Define an anonymous function to return the DTFT X (Ω) of the signal

       $$x\left[n\right]=\{\begin{array}{ll}n,\hfill & n=0,\mathrm{...},11\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

    2. Obtain S[k] by sampling the transform X (Ω) at 10 equally spaced frequencies, that is,

       $$\begin{array}{ll}S\left[k\right]=X\left(\frac{2\pi k}{10}\right),& k=0,\mathrm{...},9\end{array}$$

       Compute s[n] = DFT−1 {S[k]}, and create a stem plot.

    3. Repeat part (b) by evaluating the DTFT at 8 equally-spaced angular frequencies

       $$\begin{array}{ll}{\Omega }_k=\frac{2\pi k}{8}& k=0,\mathrm{...},7\end{array}$$

MATLAB Projects

1. 5.47. This problem is about increasing the efficiency of DFT computation by recognizing the symmetry properties of the DFT and using them to our advantage. Recall from the symmetry properties discussed in Section 5.8.3 that for a signal expressed in Cartesian complex form

   $$x\left[n\right]=x_r\left[n\right]+j{x}_i\left[n\right]$$

   and its transform expressed using circularly conjugate symmetric and antisymmetric components as

   $$X\left[k\right]=X_E\left[k\right]+X_O\left[k\right]$$

   the following relationships exist:

   $$\begin{array}{l}{x}_r\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }{X}_E\left[k\right]\\ j{x}_i\left[n\right]\stackrel{\text{DFT}}{\leftrightarrow }{X}_O\left[k\right]\end{array}$$

   Develop a MATLAB script to compute the DFTs of two real-valued length-N signals r[n] and s[n] with one call to the function fft (..) using the following approach:

   1. Construct a complex signal x[n] = r[n] + js[n].
   2. Compute the DFT of the complex signal x[n] using the function fft (..).
   3. Find the DFTs of the signals r[n] and s[n] by splitting the transform X[k] into its two components XE[k] and XO[k] and making the necessary adjustments. You may wish to use the function ss_crev (..) developed in MATLAB Exercise 5.8.

   Test your script using two 128-point signals with random amplitudes. (Use MATLAB function rand (..) to generate them.) Compare the transforms for R[k] and S[k] to results obtained by direct application of the function fft (..) to signals r[n] and s[n].

2. 5.48. One of the popular uses of the DFT is for analyzing the frequency spectrum of a continuous-time signal that has been sampled. The theory of sampling is covered in detail in Chapter 6. In this problem we will focus on computing and graphing the approximate spectrum of a recorded audio signal using the technique discussed in Section 5.8.5.

   Provided that a computer with a microphone and a sound processor is available, the following MATLAB code allows 3 seconds of audio signal to be recorded, and a vector “x” to be created with the recording:

   	hRec = audiorecorder;

   	disp (' Press a key to start recording '), pause ;

   	recordblocking (hRec, 3);

   	disp (' Finished recording '), x = getaudiodata(hRec);

   By default the analog signal xa (t) captured by the microphone and the sound device is sampled at the rate of 8000 times per second, corresponding to T = 125 s. For a 3-second recording the vector “x” contains 24000 samples that represent

   $$\begin{array}{ll}x\left[n\right]=x_a\left(\frac{n}{8000}\right),& n=0,\mathrm{...},23999\end{array}$$

   Develop a MATLAB script to perform the following steps to display the approximate spectrum of a speech signal xa (t):

   1. Extract 1024 samples of the vector x[n] into a new vector.

      $$\begin{array}{ll}r\left[n\right]=x\left[n+8000\right],& n=0,\mathrm{...},1023\end{array}$$

      We skip the first 8000 samples so that we do not get a blank period before the person begins to speak.

   2. Compute the DFT R[k] of the signal r[n]. Scale it as outlined in Section 5.8.5 so that it can be used for approximating the continuous Fourier transform of xa (t). Also create an approximate vector “f” of frequencies in Hz for use in graphing the approximate spectrum Xa (f).
   3. Compute and graph the decibel (dB) magnitude of the approximate spectrum as a function of frequency.
   4. Record your own voice and use it to test the script.