Chapter 5 The Discrete-time Fourier Transform and \(z\)-transform

Transform based analysis of discrete-time signals and systems is an essential part of DSP, primarily because it provides an essential alternate view of the properties of signals and systems. These transforms enable us to not only spot interesting properties of these signals, but also predict their behaviour when different signals and systems interact with each other. This chapter will focus on LTI systems and their transform analysis using the DTFT and \(z\)-transforms.

5.1 The discrete-time Fourier transform

As we have seen in the previous chapter, the complex exponential is an eigenfunction of LTI systems. That is, if the input \(e^{j\omega_0 n}\) is given to an LTI system, the output is just a scaled version of the same. In fact, thie output is the DTFT. To establish the existence of a finite value of the DTFT, the output would have to be well defined for every value of \(\omega_0 \in [-\pi, \pi)\). To establish a condition for this, notice that the signal \(e^{j\omega_0 n}\) is a signal that is bounded (its absolute value is always \(1\)). Therefore, whenever it is convolved with a stable LTI system, the output will always be bounded. What is the implication? The output of a stable system is always bounded when the input is a complex exponential. In other words, if a signal \(h[n]\) is absolutely summable, that is a sufficient condition for us to define the DTFT. Thus, for absolutely summable signals, we have

\[\begin{equation} H(e^{j\omega}) = \sum_{n = -\infty}^\infty h[n]e^{-j\omega n} \end{equation}\]

Note that absolute summability is only a sufficient but not necessary condition. So, the DTFT can be defined for some signals that are not absolutely summable as well, such as \(\cos \omega_0 n\), \(u[n]\) etc., although they generally involve the use of impulses.

One important property to note is that the DTFT is periodic, and has period \(2 \pi\). This has a direct connection with the sampling theorem, as explained in this video:

5.1.1 The notion of frequency

One aspect that is interesting in digital signals is that the notion of frequency is different from that in continuous-time. The frequency \(\omega\) is a number between \(-\pi\) and \(\pi\). The reason for this becomes clear by understanding the frequency as a concept of variation of consecutive values.

import plot_helper
import pylab as p
N = 5
n = p.r_[-N:N+1]
x = (-1.0)**n
plot_helper.stemplot(n, x, title=r'$x[n] = (-1)^n$', filename='minus_one_p_n.svg')
The alternating sequence.

Figure 5.1: The alternating sequence.

If we observe the \((-1)^n\) sequence, we see that it is a periodic sequence whose value alternates for every value of \(n\). Any other sequence would not have a faster rate of variation. In fact, you can observe this easily by seeing that \((-1)^n = e^{j\pi n}\). Similarly, the all ones sequence is the periodic sequence that has zero frequency, as \(e^{j 0 n} = 1\).

An intuition on why this holds can be understood by thinking about it in terms of sampling. If we sample a signal at \(f_s\) samples per second, Nyquist sampling theorem indicates that the range of frequencies that can be represented in the digital domain is limited to be between \([-f_s / 2, f_s / 2]\). Thus, observing it pictorially, the way you did in the case of sampling, would make things clear.

5.1.2 Properties of the DTFT

The properties of the Discrete-time Fourier transform can be seen from (Oppenheim, Buck, and Schafer 2001), but the key properties are summarized in the video below.

One key property is the convolution property, that basically implies that the DTFT of the convolution of two time-domain sequences is the product of the respective signals’ DTFTs. This is something that would come in very handy when solving problems and gaining intuitions on system properties.

5.2 The \(z\)-transform

Much like the Laplace transform in continuous-time systems, the \(z\) transform is a generalization of the DTFT, and is able to capture the property of a larger class of signals. Take, for example, \(2^n u[n]\), or even \(u[n]\), for that matter. These signals do not have DTFTs. However, the \(z\)-transform exists for these signals. The definition is:

\[\begin{equation} X(z) = \sum_{n = -\infty}^\infty x[n] z^{-n}, |z| \in \text{ROC} \end{equation}\]

The importance of the ROC becomes evident with a simple example. Consider the sequence \(x_1[n] = a^n u[n]\). Substituting in the above formula, we get the following:

\[\begin{equation} X_1(z) = 1 + az^{-1} + a^2z^{-2} + a^3z^{-3} + \ldots \end{equation}\]

The above summation converges only when \(|az^{-1}| < 1\). That is, the ROC is \(|z| > |a|\). Then, we get

\[\begin{equation} X_1(z) = \frac{1}{1 - az^{-1}}, |z| > |a| \end{equation}\]

Now, if we repeat the above exercise for \(x_2[n] -a^n u[-n - 1]\), we get

\[\begin{equation} X_2(z) = -a^{-1}z - a^{-2}z^2 - a^{-3}z^3 - \ldots \end{equation}\]

The above summation converges only for \(|a^{-1}z| < 1\), that is, the ROC is \(|z| < |a|\), and simplifying yields

\[\begin{equation} X_2(z) = \frac{1}{1 - az^{-1}}, |z| < |a| \end{equation}\]

It is clear that the right-sided sequence \(x_1[n]\) and the left-sided sequence \(x_2[n]\) have the same expression as their \(z\)-transform. However, the ROC establishes the precise sequence that they correspond to. Therefore, in general, the \(z\)-transform is unspecified if the ROC is not specified.

5.2.1 Properties of the ROC

The ROC has some distinctive properties that are useful to keep in mind when dealing with \(z\)-transforms. In particular, remember the following:

  1. The ROC is always of the form \(0 \leq r_R < |z| < r_L \leq \infty\), where \(r_R, r_L\) are positive real numbers, and \(r_L\) can also be \(\infty\).

  2. Left-sided sequences have ROCs of the form \(|z| < |a|\).

  3. Right-sided sequences have ROCs of the form \(|z| > |a|\).

  4. The ROCs are always contiguous regions and never interesections of disjoint regions.

5.2.2 Inverting \(z\)-transforms

In genereal, inverting \(z\)-transforms requires integration over contours, and we will not be covering this approach in our course. Instead, we will consider the following approaches:

  1. By inspection: Since many common \(z\)-transforms have common forms, we can directly invert them by inspection. For example, if you are given the \(z\)-transform \(1 / (1 - 0.5z^{-1}\) and \(|z| > |a|\), then we can directly use the general form to write the inverse as \((0.5)^n u[n]\).

  2. Partial fractions: When we have forms like \(1 / (1 - az^{-1})(1 - bz^{-1})\), one can do a partial fraction expansion to get it to a simpler form, and then we can invert it by inspection.

  3. Power series expansion: For sequences that admit a power series expansion, the power series can directly provide the sequence inverse. For example:

\[\begin{equation} X(z) = \log (1 + az^{-1}) = az^{-1} - \frac{a^2z^{-2}}{2} + \frac{a^3z^{-3}}{3} + \ldots = \sum_{n = 1}^\infty \frac{(-1)^{n+1}}{n}z^{-n} \end{equation}\]

5.2.3 Properties of \(z\)-transforms

The common properties of \(z\)-transforms are similar to that of DTFTs, with some subtle differences. These can be summarized as:

  1. Linearity: If the \(z\)-transform of \(x[n]\) and \(y[n]\) are, respectively \(X(z)\) and \(Y(z)\), then the \(z\)-transform of \(\alpha x[n] + \beta y[n]\) for any two complex numbers is \(\alpha X(z) + \beta Y(z)\). This can directly be observed from the linearity property in the \(z\)-transform summation. The ROC is at least the intersections of the ROCs of \(X(z)\) and \(Y(z)\).

  2. Time shifting: Since the \(z\)-transform of \(\delta[n - n_0]\) is \(z^{-n_0}\) for every integer value, if the \(z\)-transform of \(x[n]\) is \(X(z)\), then the \(z\)-transform of \(x[n - n_0]\) is \(z^{-n_0} X(z)\). The ROC remains unchanged.

  3. Exponential multiplication: Multiplying a sequence \(x[n]\) with a complex exponential, such as \(z_0^n\), would result in the \(z\)-transform being converted to the new \(z\)-transform \(X(z / z_0)\), and the ROC is scaled by a factor of \(|z_0|\).

  4. Differentiation: If we differentiate the \(z\)-transform and multiply by \(-z\), then we get the \(z\)-transform of the sequence that is multiplied by \(n\). That is, if \(x[n]\) has a \(z\)-transform of \(X(z)\), then \(nx[n]\) would have a \(z\)-transform of \(-z dX(z) / dz\). The ROC is at least the ROC of the original \(z\)-transform.

  5. Conjugation: If \(X(z)\) is the \(z\)-transform of \(x[n]\), then \(x^*[n]\) has \(z\)-transform \(X^*( z^* )\), with the same ROC.

  6. Time reversal: If \(x[n]\) has \(z\)-transform \(X(z)\), then \(x[-n]\) has \(z\)-transform \(X(1/z)\), with the ROC taking the reciprocal values of the original ROCs.

  7. Convolution: As discussed earlier, if \(x[n]\) and \(y[n]\) have \(z\)-transforms \(X(z)\) and \(Y(z)\) respectively, then the sequence \(x[n] * y[n]\) has \(z\)-transform \(X(z)Y(z)\), with the ROC being at least the intersection of the ROCs of the original sequences.

5.2.4 Some common examples and connection with DTFTs

5.3 Application of DTFT: Ideal low-pass filters and fractional delays

To gain some more insights into DTFTs, we will now look at two examples. The first one we will consider is the ideal low-pass filter. The ideal low-pass filter with a cut-off frequency of \(\omega_c\) can be defined as the periodic extension of

\[ H(e^{j\omega}) = \begin{cases} 1 &\mbox{if } |\omega| < \omega_c \\ 0 & \mbox{if } \omega_c \leq |\omega| < \pi \\ \end{cases} \]

Always remember that there is a \(2\pi\) periodic extension of the above sequence. If you use the inverse DTFT formula, we end up with the sequence

\[ h[n] = \frac{\sin \omega_c n}{\pi n} \]

Notice that, for \(n = 0\), the value is defined to be \(h[0] = \omega_c / \pi\). Notice that this is an infinite length sequence, and realizing this filter as an LCCDE is not possible. Given that this is the case, the ideal LPF is not practically realizable. Having said that, we will still try to analyze this system. Here is one way:

import numpy as np
import pylab
from scipy.signal import freqz

omega_c = np.pi / 2
N = 100
n = np.arange(-N, N + 1)
h = omega_c / np.pi * np.sinc(omega_c * n /np.pi)
[W, H] = freqz(h, worN=4096)

pylab.rc('text', usetex=True)
pylab.rc('font', size=16)
pylab.rc('axes', labelsize=16)
pylab.rc('legend', fontsize=12)
pylab.plot(W, 20*np.log10(np.abs(H)))
pylab.grid(True)
pylab.xlabel(r'$\omega$')
pylab.ylabel('$|H(e^{j\omega})|$ (dB)')
pylab.axis([0, np.pi, -50, 3])
pylab.savefig('lpf1.svg')
The magnitude response of a truncated LPF.

Figure 5.2: The magnitude response of a truncated LPF.

Notice in the above that there is a significant ripple. This ripple can be attributed to the truncation of the ideal LPF. This operation, called windowing, causes a convolution of the ideal LPF DTFT with that of the window. The following video describes this in detail:

A similar, and useful, application, is that of the fractional delay. Consider the DTFT \(H(e^{j\omega}) = e^{-j\omega \alpha}\), where \(\alpha\) is a real number. In this case, if \(\alpha\) is an integer, then the sequence that this DTFT corresponds to is \(\delta[n - \alpha]\). However, this becomes interesting when \(\alpha\) is not an integer. In this case, using the DTFT formula yields:

\[ h[n] = \frac{\sin(\pi (n - \alpha))}{\pi(n - \alpha)}. \]

The above sequence can easily be recognized as a sinc that is sampled at non-integer points. What is interesting is that, by not sampling exactly at integer locations, ALL the sinc points start coming into the picture. This looks puzzling initially, but will become clear if you observe the following video:

If you view the discrete-time signal \(\delta[n]\) as just being reconstructed to a sinc, then convolving with the sequence that corresponds to \(H(e^{j\omega}) = e^{-j\omega \alpha}\) results in resampling the sinc at different points. More here:

5.4 Group delay and linear phase

The concept of group delay helps understand the amount of delay that the envelope of a signal is subjected to. This would become clear using an example.

import numpy as np
import pylab
from scipy.signal import freqz

n = np.arange(-20, 21)
g = np.exp(-n**2 / 400)

M = 30
h = np.ones(M) / M
y = np.convolve(h, g)

pylab.figure()
pylab.rc('text', usetex=True)
pylab.rc('font', size=16)
pylab.rc('axes', labelsize=16)
pylab.rc('legend', fontsize=12)
pylab.plot(n, g, 'r-', label=r'$x[n]$')
n = np.arange(-20, 21 + M - 1)
pylab.plot(n, y, 'b-', label=r'$y[n]$')
pylab.grid(True)
pylab.xlabel(r'$n$')
pylab.ylabel('$x[n], y[n]$')
pylab.legend()
pylab.savefig('gaussian1.svg')
Filtering the signal using the 30-length rectangular pulse delays the resulting sequence precisely by 15 points.

Figure 5.3: Filtering the signal using the 30-length rectangular pulse delays the resulting sequence precisely by 15 points.

In the above example, a Gaussian pulse is filtered using a 30 length rectangular window. We observe that that resulting pulse has its peak delayed by around 15 units (14.5 to be precise). Why is this the case? This can be understood using the group delay definition. We can define the group delay of the filter \(h[n]\), whose DTFT is \(H(e^{j\omega})\) as \(\frac{d\angle H(e^{j\omega})}{d\omega}\). For the 30 length rectangular window, you can find that this works out to \(14.5\). You can clearly see that the signal gets delayed and slightly modified, but looks largely undistorted.

In general, the group delay depends on the frequency \(\omega\), which is why different components of signals can get delayed by different amounts. As an example, consider \(h[n] = \delta[n] + 0.5\delta[n - 1]\). In this case, \(\angle H(e^{j\omega})\) works out to \(\tan^{-1} \frac{0.5\sin \omega}{1 + 0.5\cos \omega}\). In this case, the group delay changes with \(\omega\). This can be seen from the plot below.

import numpy as np
import pylab
from scipy.signal import freqz

n = np.arange(-20, 21)
g = np.exp(-n**2 / 400)

M = 30
h = np.ones(M) / M
h[M//2:] = h[M//2:] / 2
y = np.convolve(h, g)

pylab.figure()
pylab.rc('text', usetex=True)
pylab.rc('font', size=16)
pylab.rc('axes', labelsize=16)
pylab.rc('legend', fontsize=12)
pylab.plot(n, g, 'r-', label=r'$x[n]$')
n = np.arange(-20, 21 + M - 1)
pylab.plot(n, y, 'b-', label=r'$y[n]$')
pylab.grid(True)
pylab.xlabel(r'$n$')
pylab.ylabel('$x[n], y[n]$')
pylab.legend()
pylab.savefig('gaussian2.svg')
Filtering the signal using a different pulse causes the resulting sequence to exhibit some distortion.

Figure 5.4: Filtering the signal using a different pulse causes the resulting sequence to exhibit some distortion.

Thus, in general, the non-linearity of the group delay causes distortion of the signal, since different frequencies are delayed by different amounts, and the modifications are not as you would ideally expect, as in the case of just the magnitude response.

However, there are certain constraints that can be imposed on the impulse response of the filter to obtain a constant group delay, thereby minimizing the undesired distortion. They are specified by the following types:

  1. Type-1 linear phase FIR filter: A filter is said to be a Type-1 FIR filter if its impulse response is defined for \(n = 0, 1, 2, \ldots M\), where \(M\) is an even number, and \(h[n] = h[M - n]\). This ensures that the filter has constant group delay. This can be proved very easily:

    \[\begin{equation} H(e^{j\omega}) = h[0] + h[1]e^{-j\omega} + h[2]e^{-j2\omega} \ldots h[M]e^{-jM\omega} \end{equation}\]

    The above can be simplified easily to:

    \[\begin{equation} H(e^{j\omega}) = e^{j\omega M /2}(2h[0] \cos (M \omega / 2) + 2h[1] \cos ((M - 1) \omega / 2) + \ldots + h[M/2]) \end{equation}\]

    It can be seen very clearly that the group delay of the filter for all \(\omega\) is \((M - 1) / 2\), since the part in the bracket is real, and thus, contributes only a phase of \(0\) or \(\pi\), depending on the sign. This is a useful constraint that we will look at again in the context of filter design.

  2. Type-2 linear phase FIR filter: A filter is said to be a Type-2 FIR filter if its impulse response is defined for \(n = 0, 1, 2, \ldots M\), where \(M\) is an odd number, and \(h[n] = h[M - n]\). This is similar to the previous one, except that he filter has an even number of coefficients.

  3. Type-3 linear phase FIR filter: A filter is said to be a Type-3 FIR filter if its impulse response is defined for \(n = 0, 1, 2, \ldots M\), where \(M\) is an even number, and \(h[n] = -h[M - n]\). This is similar to Type-1, except that the impulse response is anti-symmetric around the middle.

  4. Type-4 linear phase FIR filter: A filter is said to be a Type-4 FIR filter if its impulse response is defined for \(n = 0, 1, 2, \ldots M\), where \(M\) is an odd number, and \(h[n] = -h[M - n]\). This is similar to Type-2, except that the impulse response is anti-symmetric around the middle.

One common aspect that you can see in the above is that there is an inherent symmetry, and that is leading to the linear phase condition. In fact, for both Type-1 and Type-3 filters, shifting them to the left would make them symmetric (or anti-symmetric) about zero, thereby leading to the situation that the DTFT is purely real or imaginary, causing the group delay to be \(0\). For the Type-2 and Type-4 filters, a fractional shift to the left would be needed, but there is symmetry there as well. This can be verified by writing out the DTFT and verifying it for yourself.

References

Oppenheim, Alan V, John R Buck, and Ronald W Schafer. 2001. Discrete-Time Signal Processing. Vol. 3. Upper Saddle River, NJ: Prentice Hall.