1.3 Fundamentals of Digital Signal Processing

The fundamentals of digital signal processing consist of the description of digital signals—in the context of this book we use digital audio signals—as a sequence of numbers with appropriate number representation and the description of digital systems, which are described by software algorithms to calculate an output sequence of numbers from an input sequence of numbers. The visual representation of digital systems is achieved by functional block diagram representations or signal flow graphs. We will focus on some simple basics as an introduction to the notation and refer the reader to the literature for an introduction to digital signal processing [ME93, Orf96, Zöl05, MSY98, Mit01].

1.3.1 Digital Signals

The digital signal representation of an analog audio signal as a sequence of numbers is achieved by an analog-to-digital converter (ADC). The ADC performs sampling of the amplitudes of the analog signal x(t) on an equidistant grid along the horizontal time axis and quantization of the amplitudes to fixed samples represented by numbers x(n) along the vertical amplitude axis (see Fig. 1.11). The samples are shown as vertical lines with dots on the top. The analog signal x(t) denotes the signal amplitude over continuous time t in micro seconds. Following the ADC, the digital (discrete time and quantized amplitude) signal is a sequence (stream) of samples x(n) represented by numbers over the discrete time index n. The time distance between two consecutive samples is termed sampling interval T (sampling period) and the reciprocal is the sampling frequency fS = 1/T (sampling rate). The sampling frequency reflects the number of samples per second in Hertz (Hz). According to the sampling theorem, it has to be chosen as twice the highest frequency fmax (signal bandwidth) contained in the analog signal, namely fS > 2 · fmax. If we are forced to use a fixed sampling frequency fS, we have to make sure that our input signal to be sampled has a bandwidth according to fmax = fS /2. If not, we have to reject higher frequencies by filtering with a lowpass filter which only passes all frequencies up to fmax. The digital signal is then passed to a DAFX box (digital system), which in this example performs a simple multiplication of each sample by 0.5 to deliver the output signal y(n) = 0.5 · x(n). This signal y(n) is then forwarded to a digital-to-analog converter DAC, which reconstructs the analog signal y(t). The output signal y(t) has half the amplitude of the input signal x(t).

Figure 1.12 shows some digital signals to demonstrate different graphical representations (see M-file 1.1). The upper part shows 8000 samples, the middle part the first 1000 samples and the lower part shows the first 100 samples out of a digital audio signal. Only if the number of samples inside a figure is sufficiently low, will the line with dot graphical representation be used for a digital signal.

Two different vertical scale formats for digital audio signals are shown in Figure 1.13. The quantization of the amplitudes to fixed numbers in the range −32768 … 32767 is based on a 16-bit representation of the sample amplitudes which allows 216 quantized values in the range −215 … 215 − 1. For a general w-bit representation the number range is −2w−1 … 2w−1 − 1. This representation is called the integer number representation. If we divide all integer numbers by the maximum absolute value, for example 32768, we come to the normalized vertical scale in Figure 1.13, which is in the range −1 … 1 − Q, where Q is the quantization step size. It and can be calculated by Q = 2−(w−1), which leads to Q = 3.0518 × 10−5 for w = 16. Figure 1.13 also displays the horizontal scale formats, namely the continuous-time axis, the discrete-time axis and the normalized discrete-time axis, which will be used normally. After this narrow description we can define a digital signal as a discrete-time and discrete-amplitude signal, which is formed by sampling an analog signal and by quantization of the amplitude onto a fixed number of amplitude values. The digital signal is represented by a sequence of numbers x(n). Reconstruction of analog signals can be performed by DACs. Further details of ADCs and DACs and the related theory can be found in the literature. For our discussion of digital audio effects this short introduction to digital signals is sufficient.

Signal processing algorithms usually process signals by either block processing or sample-by-sample processing. Examples for digital audio effects are presented in [Arf98]. For block processing, samples are first collected in a memory buffer and then processed each time the buffer is completely filled with new data. Examples of such algorithms are fast Fourier transforms (FFTs) for spectra computations and fast convolution. In sample processing algorithms, each input sample is processed on a sample-by-sample basis.

A basic algorithm for weighting of a sound x(n) (see Figure 1.11) by a constant factor a demonstrates a sample-by-sample processing (see M-file 1.2). The input signal is represented by a vector of numbers [x(1), x(2),…, x(length(x))].

1.3.2 Spectrum Analysis of Digital Signals

The spectrum of a signal shows the distribution of energy over the frequency range. The upper part of Figure 1.14 shows the spectrum of a short time slot of an analog audio signal. The frequencies range up to 20 kHz. The sampling and quantization of the analog signal with sampling frequency of fS = 40 kHz leads to a corresponding digital signal. The spectrum of the digital signal of the same time slot is shown in the lower part of Figure 1.14. The sampling operation leads to a replication of the baseband spectrum of the analog signal [Orf96]. The frequency contents from 0 Hz up to 20 kHz of the analog signal now also appear from 40 kHz up to 60 kHz and the folded version of it from 40 kHz down to 20 kHz. The replication of this first image of the baseband spectrum at 40 kHz will now also appear at integer multiples of the sampling frequency of fS = 40 kHz. But notice that the spectrum of the digital signal from 0 up to 20 kHz shows exactly the same shape as the spectrum of the analog signal. The reconstruction of the analog signal out of the digital signal is achieved by simply lowpass filtering the digital signal, rejecting frequencies higher than fS /2 = 20 kHz. If we consider the spectrum of the digital signal in the lower part of Fig. 1.14 and reject all frequencies higher than 20 kHz, we come back to the spectrum of the analog signal in the upper part of the figure.

Discrete Fourier Transform

The spectrum of a digital signal can be computed by the discrete Fourier transform (DFT) which is given by

1.1

The fast version of the above formula is called the fast Fourier transform (FFT). The FFT takes N consecutive samples out of the signal x(n) and performs a mathematical operation to yield N samples X(k) of the spectrum of the signal. Figure 1.15 demonstrates the results of a 16-point FFT applied to 16 samples of a cosine signal. The result is normalized by N according to X=abs(fft(x,N))/N;.

The N samples X(k) = XR(k) + jXI(k) are complex-valued with a real part XR(k) and an imaginary part XI(k) from which one can compute the absolute value

1.2

which is the magnitude spectrum, and the phase

1.3

which is the phase spectrum. Figure 1.15 also shows that the FFT algorithm leads to N equidistant frequency points which give N samples of the spectrum of the signal starting from 0 Hz in steps of up to . These frequency points are given by , where k is running from 0, 1, 2, …, N − 1. The magnitude spectrum |X(f)| is often plotted over a logarithmic amplitude scale according to which gives 0 dB for a sinusoid of maximum amplitude ±1. This normalization is equivalent to . Figure 1.16 shows this representation of the example from Fig. 1.15. Images of the baseband spectrum occur at the sampling frequency fS and multiples of fS. Therefore we see the original frequency at 5 kHz and in the first image spectrum the folded frequency fS − fcosine = 40 000 Hz − 5000 Hz = 35 000 Hz.

Inverse Discrete Fourier Transform (IDFT)

Whilst the DFT is used as the transform from the discrete-time domain to the discrete-frequency domain for spectrum analysis, the inverse discrete Fourier transform (IDFT) allows the transform from the discrete-frequency domain to the discrete-time domain. The IDFT algorithm is given by

1.4

The fast version of the IDFT is called the inverse Fast Fourier transform (IFFT). Taking N complex-valued numbers with the property X(k) = X*(N − k) in the frequency domain and then performing the IFFT gives N discrete-time samples x(n), which are real-valued.

Frequency Resolution: Zero-padding and Window Functions

To increase the frequency resolution for spectrum analysis we simply take more samples for the FFT algorithm. Typical numbers for the FFT resolution are N = 256, 512, 1024, 2048, 4096 and 8192. If we are only interested in computing the spectrum of 64 samples and would like to increase the frequency resolution from fS/64 to fS/1024, we have to extend the sequence of 64 audio samples by adding zero samples up to the length 1024 and then perform an 1024-point FFT. This technique is called zero-padding and is illustrated in Figure 1.17 and by M-file 1.3. The upper left part shows the original sequence of eight samples and the upper right part shows the corresponding eight-point FFT result. The lower left part illustrates the adding of eight zero samples to the original eight-sample sequence up to the length N = 16. The lower right part illustrates the magnitude spectrum |X(k)| resulting from the 16-point FFT of the zero-padded sequence of length N = 16. Notice the increase in frequency resolution between the eight-point and 16-point FFT. Between each frequency bin of the upper spectrum a new frequency bin in the lower spectrum is calculated. Bins k = 0, 2, 4, 6, 8, 10, 12, 14 of the 16-point FFT correspond to bins k = 0, 1, 2, 3, 4, 5, 6, 7 of the eight-point FFT. These N frequency bins cover the frequency range from 0 Hz up to .

The leakage effect occurs due to cutting out N samples from the signal. This effect is shown in the upper part of Figure 1.18 and demonstrated by the corresponding M-file 1.4. The cosine spectrum is smeared around the frequency. We can reduce the leakage effect by selecting a window function like Blackman window and Hamming window

1.5

1.6

and weighting the N audio samples by the window function. This weighting is performed according to with 0 ≤ n ≤ N − 1 and then an FFT of the weighted signal is performed. The cosine weighted by a window and the corresponding spectrum is shown in the middle part of Figure 1.18. The lower part of Figure 1.18 shows a segment of an audio signal weighted by the Blackman window and the corresponding spectrum via a FFT. Figure 1.19 shows further simple examples for the reduction of the leakage effect and can be generated by the M-file 1.5.

Spectrogram: Time-frequency Representation

A special time-frequency representation is the spectrogram which gives an estimate of the short-time, time-localized frequency content of the signal. To obtain the spectrogram the signal is split into segments of length N, which are multiplied by a window and an FFT is performed (see Figure 1.20). To increase the time-localization of the short-time spectra an overlap of the weighted segments can be used. A special visual representation of the short-time spectra is the spectrogram in Figure 1.21. Time increases linearly across the horizontal axis and frequency increases across the vertical axis. So each vertical line represents the absolute value |X(f)| over frequency by a grey-scale value (see Figure 1.21). Only frequencies up to half the sampling frequency are shown. The calculation of the spectrogram from a signal can be performed by the MATLAB function B = specgram(x,nFFT,Fs,window,nOverlap).

Another time-frequency representation of the short-time Fourier transforms of a signal x(n) is the waterfall representation in Figure 1.22, which can be produced by M-file 1.6 that calls the waterfall computation algorithm given by M-file 1.7.

1.3.3 Digital Systems

A digital system is represented by an algorithm which uses the input signal x(n) as a sequence (stream) of numbers and performs mathematical operations upon the input signal such as additions, multiplications and delay operations. The result of the algorithm is a sequence of numbers or the output signal y(n). Systems which do not change their behavior over time and fulfill the superposition property [Orf96] are called linear time-invariant (LTI) systems. The input/output relations for a LTI digital system describe time-domain relations which are based on the following terms and definitions:

• Unit impulse, impulse response and discrete convolution;
• Algorithms and signal flow graphs.

For each of these definitions an equivalent description in the frequency domain exists, which will be introduced later.

Unit Impulse, Impulse Response and Discrete Convolution

• Test signal: a very useful test signal for digital systems is the unit impulse

  1.7

  which is equal to one for n = 0 and zero elsewhere (see Figure 1.23).

• Impulse response: if we apply a unit-impulse function to a digital LTI system, the digital system will lead to an output signal y(n) = h(n), which is called the impulse response h(n) of the digital system. The digital LTI system is completely described by the impulse response, which is pointed out by the label h(n) inside the box, as shown in Figure 1.23.
• Discrete convolution: if we know the impulse response h(n) of a digital system, we can calculate the output signal y(n) from a freely chosen input signal x(n) by the discrete convolution formula given by

  1.8

  which is often abbreviated by the second term y(n) = x(n) * h(n). This discrete sum formula (1.8) represents an input–output relation for a digital system in the time domain. The computation of the convolution sum formula (1.8) can be achieved by the MATLAB function y=conv(x,h).

Algorithms and Signal Flow Graphs

The above given discrete convolution formula shows the mathematical operations which have to be performed to obtain the output signal y(n) for a given input signal x(n). In the following we will introduce a visual representation called a signal flow graph which represents the mathematical input/output relations in a graphical block diagram. We discuss some example algorithms to show that we only need three graphical representations for the multiplication of signals by coefficients, delay and summation of signals.

• A delay of the input signal by two sampling intervals is given by the algorithm

  1.9

  and is represented by the block diagram in Figure 1.24.

• A weighting of the input signal by a coefficient a is given by the algorithm

  1.10

  and represented by a block diagram in Figure 1.25.

• The addition of two input signals is given by the algorithm

  1.11

  and represented by a block diagram in Figure 1.26.

• The combination of the above algorithms leads to the weighted sum over several input samples, which is given by the algorithm

  1.12

  and represented by a block diagram in Fig. 1.27.

Transfer Function and Frequency Response

So far our description of digital systems has been based on the time-domain relationship between the input and output signals. We noticed that the input and output signals and the impulse response of the digital system are given in the discrete time domain. In a similar way to the frequency-domain description of digital signals by their spectra given in the previous subsection we can have a frequency-domain description of the digital system which is represented by the impulse response h(n). The frequency-domain behavior of a digital system reflects its ability to pass, reject and enhance certain frequencies included in the input signal spectrum. The common terms for the frequency-domain behavior are the transfer function H(z) and the frequency response H(f) of the digital system. Both can be obtained by two mathematical transforms applied to the impulse response h(n).

The first transform is the Z-Transform

1.13

applied to the signal x(n) and the second transform is the discrete-time Fourier transform

1.14

1.15

applied to the signal x(n). Both are related by the substitution z ↔ ejω. If we apply the Z-transform to the impulse response h(n) of a digital system according to

1.16

we denote H(z) as the transfer function. The transfer function is of special interest as it relates the Z-transforms of input signal and output signal of the described system by

1.17

If we apply the discrete-time Fourier transform to the impulse response h(n) we get

1.18

Substituting (1.15) we define the frequency response of the digital system by

1.19

Causal and Stable Systems

A realizable digital system has to fulfill the following two conditions:

• Causality: a discrete-time system is causal, if the output signal y(n) = 0 for n < 0 for a given input signal x(n) = 0 for n < 0. This means that the system cannot react to an input before the input is applied to the system.
• Stability: a digital system is stable if

  1.20

  holds. The sum over the absolute values of h(n) has to be less than a fixed number M2 < ∞.

The stability implies that the transfer function (Z-transform of impulse response) and the frequency response (discrete-time Fourier transform of impulse response) of a digital system are related by the substitution z ↔ ejω. Realizable digital systems have to be causal and stable systems. Some Z-transforms and their discrete-time Fourier transforms of a signal x(n) are given in Table 1.4.

Table 1.4 Z-transforms and discrete-time Fourier transforms of x(n)

Signal	Z-transform	Discrete-time Fourier transform
x(n)	X(z)	X(ejω)
x(n − M)	z−M · X(z)	e−jωM · X(ejω)
δ(n)	1	1
δ(n − M)	z−M	e−jωM

IIR and FIR Systems

IIR systems: A system with an infinite impulse response h(n) is called an IIR system. From the block diagram in Figure 1.28 we can read the difference equation

1.21

The output signal y(n) is fed back through delay elements and a weighted sum of these delayed outputs is summed up to the input signal x(n). Such a feedback system is also called a recursive system. The Z-transform of (1.21) yields

1.22

1.23

and solving for Y(z)/X(z) gives transfer function

1.24

Figure 1.29 shows a special signal flow graph representation, where adders, multipliers and delay operators are replaced by weighted graphs.

If the input delay line is extended up to N − 1 delay elements and the output delay line up to M delay elements according to Figure 1.30, we can write for the difference equation

1.25

the Z-transform of the difference equation

1.26

and the resulting transfer function

1.27

The block processing approach for the IIR filter algorithm can be performed with the MATLAB/Octave function y = filter(b, a, x), where b and a are vectors with the filter coefficients as above and x contains the input signal.

A sample-by-sample processing approach for a second-order IIR filter algorithm is demonstrated by M-file 1.8.

Computation of the frequency response based on the coefficients of the transfer function can be made with the MATLAB/Octave function freqz(b, a), while the poles and zeros can be determined with zplane(b, a).

FIR systems: A system with a finite impulse response h(n) is called an FIR system. From the block diagram in Figure 1.31 we can read the difference equation

1.28

The input signal x(n) is fed forward through delay elements and a weighted sum of these delayed inputs is summed up to the input signal y(n). Such a feed-forward system is also called a non-recursive system. The Z-transform of (1.28) yields

1.29

1.30

and solving for Y(z)/X(z) gives transfer function

1.31

A general FIR system in Figure 1.32 consists of a feed-forward delay line with N − 1 delay elements and has the difference equation

1.32

The finite impulse response is given by

1.33

which shows that each impulse of h(n) is represented by a weighted and shifted unit impulse. The Z-transform of the impulse response leads to the transfer function

1.34

The time-domain algorithms for FIR systems are the same as those for IIR systems with the exception that the recursive part is missing. The previously introduced M-files for IIR systems can be used with the appropriate coefficients for FIR block processing or sample-by-sample processing.

The computation of the frequency response H(f) = |H(f)| · ej∠H(f) (|H(f)| magnitude response, φ = ∠H(f) phase response) from the Z-transform of an FIR impulse response according to (1.34) is shown in Figure 1.33 and is calculated by the following M-file 1.9.