## Signal Operators

It will be convenient in the Fourier theorems of §7.4 to make use of the following signal operator definitions.

### Operator Notation

In this book, an operator is defined as a signal-valued function of a signal. Thus, for the space of length complex sequences, an operator is a mapping from to :

An example is the DFT operator:

The argument to an operator is always an entire signal. However, its output may be subscripted to obtain a specific sample, e.g.,

Some operators require one or more parameters affecting their definition. For example the shift operator (defined in §7.2.3 below) requires a shift amount :7.3

A time or frequency index, if present, will always be the last subscript. Thus, the signal is obtained from by shifting it samples. Note that operator notation is not standard in the field of digital signal processing. It can be regarded as being influenced by the field of computer science. In the Fourier theorems below, both operator and conventional signal-processing notations are provided. In the author's opinion, operator notation is consistently clearer, allowing powerful expressions to be written naturally in one line (e.g., see Eq.(7.8)), and it is much closer to how things look in a readable computer program (such as in the matlab language).

### Flip Operator

We define the flip operator by

 (7.1)

for all sample indices . By modulo indexing, is the same as . The operator reverses the order of samples through of a sequence, leaving sample 0 alone, as shown in Fig.7.1a. Thanks to modulo indexing, it can also be viewed as flipping'' the sequence about the time 0, as shown in Fig.7.1b. The interpretation of Fig.7.1b is usually the one we want, and the operator is usually thought of as time reversal'' when applied to a signal or frequency reversal'' when applied to a spectrum . figure[htbp]

### Shift Operator

The shift operator is defined by

and denotes the entire shifted signal. Note that since indexing is modulo , the shift is circular (or cyclic''). However, we normally use it to represent time delay by samples. We often use the shift operator in conjunction with zero padding (appending zeros to the signal , §7.2.7) in order to avoid the wrap-around'' associated with a circular shift.
Figure 7.2 illustrates successive one-sample delays of a periodic signal having first period given by .

#### Examples

• (an impulse delayed one sample).
• (a circular shift example).
• (another circular shift example).

### Convolution

The convolution of two signals and in may be denoted  '' and defined by

Note that this is circular convolution (or cyclic'' convolution).7.4 The importance of convolution in linear systems theory is discussed in §8.3. Cyclic convolution can be expressed in terms of previously defined operators as

where and . This expression suggests graphical convolution, discussed below in §7.2.4.

#### Commutativity of Convolution

Convolution (cyclic or acyclic) is commutative, i.e.,

Proof:

In the first step we made the change of summation variable , and in the second step, we made use of the fact that any sum over all terms is equivalent to a sum from 0 to .

#### Convolution as a Filtering Operation

In a convolution of two signals , where both and are signals of length (real or complex), we may interpret either or as a filter that operates on the other signal which is in turn interpreted as the filter's input signal''.7.5 Let denote a length signal that is interpreted as a filter. Then given any input signal , the filter output signal may be defined as the cyclic convolution of and :

Because the convolution is cyclic, with and chosen from the set of (periodically extended) vectors of length , is most precisely viewed as the impulse-train-response of the associated filter at time . Specifically, the impulse-train response is the response of the filter to the impulse-train signal , which, by periodic extension, is equal to

Thus, is the period of the impulse-train in samples--there is an impulse'' (a ') every samples. Neglecting the assumed periodic extension of all signals in , we may refer to more simply as the impulse signal, and as the impulse response (as opposed to impulse-train response). In contrast, for the DTFTB.1), in which the discrete-time axis is infinitely long, the impulse signal is defined as

and no periodic extension arises. As discussed below (§7.2.7), one may embed acyclic convolution within a larger cyclic convolution. In this way, real-world systems may be simulated using fast DFT convolutions (see Appendix A for more on fast convolution algorithms). Note that only linear, time-invariant (LTI) filters can be completely represented by their impulse response (the filter output in response to an impulse at time 0). The convolution representation of LTI digital filters is fully discussed in Book II [68] of the music signal processing book series (in which this is Book I).

#### Convolution Example 1: Smoothing a Rectangular Pulse

 Filter input signal . Filter impulse response . Filter output signal .

Figure 7.3 illustrates convolution of

with

to get

 (7.2)

as graphed in Fig.7.3(c). In this case, can be viewed as a moving three-point average'' filter. Note how the corners of the rectangular pulse are smoothed'' by the three-point filter. Also note that the pulse is smeared to the right'' (forward in time) because the filter impulse response starts at time zero. Such a filter is said to be causal (see [68] for details). By shifting the impulse response left one sample to get

(in which case ), we obtain a noncausal filter which is symmetric about time zero so that the input signal is smoothed in place'' with no added delay (imagine Fig.7.3(c) shifted left one sample, in which case the input pulse edges align with the midpoint of the rise and fall in the output signal).

#### Convolution Example 2: ADSR Envelope

 Filter input signal . Filter impulse response . Filter output signal .

In this example, the input signal is a sequence of two rectangular pulses, creating a piecewise constant function, depicted in Fig.7.4(a). The filter impulse response, shown in Fig.7.4(b), is a truncated exponential.7.6 In this example, is again a causal smoothing-filter impulse response, and we could call it a moving weighted average'', in which the weighting is exponential into the past. The discontinuous steps in the input become exponential asymptotes'' in the output which are approached exponentially. The overall appearance of the output signal resembles what is called an attack, decay, release, and sustain envelope, or ADSR envelope for short. In a practical ADSR envelope, the time-constants for attack, decay, and release may be set independently. In this example, there is only one time constant, that of . The two constant levels in the input signal may be called the attack level and the sustain level, respectively. Thus, the envelope approaches the attack level at the attack rate (where the rate'' may be defined as the reciprocal of the time constant), it next approaches the sustain level at the decay rate'', and finally, it approaches zero at the release rate''. These envelope parameters are commonly used in analog synthesizers and their digital descendants, so-called virtual analog synthesizers. Such an ADSR envelope is typically used to multiply the output of a waveform oscillator such as a sawtooth or pulse-train oscillator. For more on virtual analog synthesis, see, for example, [78,77].

#### Convolution Example 3: Matched Filtering

Figure 7.5 illustrates convolution of

to get

 (7.3)

For example, could be a rectangularly windowed signal, zero-padded by a factor of 2,'' where the signal happened to be dc (all s). For the convolution, we need

which is the same as . When , we say that is a matched filter for .7.7 In this case, is matched to look for a dc component,'' and also zero-padded by a factor of . The zero-padding serves to simulate acyclic convolution using circular convolution. Note from Eq.(7.3) that the maximum is obtained in the convolution output at time 0. This peak (the largest possible if all input signals are limited to in magnitude), indicates the matched filter has found'' the dc signal starting at time 0. This peak would persist in the presence of some amount of noise and/or interference from other signals. Thus, matched filtering is useful for detecting known signals in the presence of noise and/or interference [34].

#### Graphical Convolution

As mentioned above, cyclic convolution can be written as

where and . It is instructive to interpret this expression graphically, as depicted in Fig.7.5 above. The convolution result at time is the inner product of and , or . For the next time instant, , we shift one sample to the right and repeat the inner product operation to obtain , and so on. To capture the cyclic nature of the convolution, and can be imagined plotted on a cylinder. Thus, Fig.7.5 shows the cylinder after being cut'' along the vertical line between and and unrolled'' to lay flat.

#### Polynomial Multiplication

Note that when you multiply two polynomials together, their coefficients are convolved. To see this, let denote the th-order polynomial

with coefficients , and let denote the th-order polynomial

with coefficients . Then we have [1]

Denoting by

we have that the th coefficient can be expressed as

where and are doubly infinite sequences, defined as zero for and , respectively.

#### Multiplication of Decimal Numbers

Since decimal numbers are implicitly just polynomials in the powers of 10, e.g.,

it follows that multiplying two numbers convolves their digits. The only twist is that, unlike normal polynomial multiplication, we have carries. That is, when a convolution result (output digit) exceeds 10, we subtract 10 from the result and add 1 to the digit in the next higher place.

### Correlation

The correlation operator for two signals and in is defined as

We may interpret the correlation operator as

which is times the coefficient of projection onto of advanced by samples (shifted circularly to the left by samples). The time shift is called the correlation lag, and is called a lagged product. Applications of correlation are discussed in §8.4.

### Stretch Operator

Unlike all previous operators, the operator maps a length signal to a length signal, where and are integers. We use '' instead of '' as the time index to underscore this fact.
A stretch by factor is defined by

Thus, to stretch a signal by the factor , insert zeros between each pair of samples. An example of a stretch by factor three is shown in Fig.7.6. The example is

The stretch operator is used to describe and analyze upsampling, that is, increasing the sampling rate by an integer factor. A stretch by followed by lowpass filtering to the frequency band implements ideal bandlimited interpolation (introduced in Appendix D).

Zero padding consists of extending a signal (or spectrum) with zeros. It maps a length signal to a length signal, but need not divide .
Definition:

 (7.4)

where , with for odd, and for even. For example,

In this example, the first sample corresponds to time 0, and five zeros have been inserted between the samples corresponding to times and . Figure 7.7 illustrates zero padding from length out to length . Note that and could be replaced by and in the figure caption.
Note that we have unified the time-domain and frequency-domain definitions of zero-padding by interpreting the original time axis as indexing positive-time samples from 0 to (for even), and negative times in the interval .7.8 Furthermore, we require when is even, while odd requires no such restriction. In practice, we often prefer to interpret time-domain samples as extending from 0 to , i.e., with no negative-time samples. For this case, we define causal zero padding'' as described below.

### Causal (Periodic) Signals

A signal may be defined as causal when for all negative-time'' samples (e.g., for when is even). Thus, the signal is causal while is not. For causal signals, zero-padding is equivalent to simply appending zeros to the original signal. For example,

Therefore, when we simply append zeros to the end of signal, we call it causal zero padding.

In practice, a signal is often an -sample frame of data taken from some longer signal, and its true starting time can be anything. In such cases, it is common to treat the start-time of the frame as zero, with no negative-time samples. In other words, represents an -sample signal-segment that is translated in time to start at time 0. In this case (no negative-time samples in the frame), it is proper to zero-pad by simply appending zeros at the end of the frame. Thus, we define e.g.,

Causal zero-padding should not be used on a spectrum of a real signal because, as we will see in §7.4.3 below, the magnitude spectrum of every real signal is symmetric about frequency zero. For the same reason, we cannot simply append zeros in the time domain when the signal frame is considered to include negative-time samples, as in zero-centered FFT processing'' (discussed in Book IV [70]). Nevertheless, in practice, appending zeros is perhaps the most common form of zero-padding. It is implemented automatically, for example, by the matlab function fft(x,N) when the FFT size N exceeds the length of the signal vector x. In summary, we have defined two types of zero-padding that arise in practice, which we may term causal'' and zero-centered'' (or zero-phase'', or even periodic''). The zero-centered case is the more natural with respect to the mathematics of the DFT, so it is taken as the official'' definition of ZEROPAD(). In both cases, however, when properly used, we will have the basic Fourier theorem7.4.12 below) stating that zero-padding in the time domain corresponds to ideal bandlimited interpolation in the frequency domain, and vice versa.

Zero padding in the time domain is used extensively in practice to compute heavily interpolated spectra by taking the DFT of the zero-padded signal. Such spectral interpolation is ideal when the original signal is time limited (nonzero only over some finite duration spanned by the orignal samples). Note that the time-limited assumption directly contradicts our usual assumption of periodic extension. As mentioned in §6.7, the interpolation of a periodic signal's spectrum from its harmonics is always zero; that is, there is no spectral energy, in principle, between the harmonics of a periodic signal, and a periodic signal cannot be time-limited unless it is the zero signal. On the other hand, the interpolation of a time-limited signal's spectrum is nonzero almost everywhere between the original spectral samples. Thus, zero-padding is often used when analyzing data from a non-periodic signal in blocks, and each block, or frame, is treated as a finite-duration signal which can be zero-padded on either side with any number of zeros. In summary, the use of zero-padding corresponds to the time-limited assumption for the data frame, and more zero-padding yields denser interpolation of the frequency samples around the unit circle. Sometimes people will say that zero-padding in the time domain yields higher spectral resolution in the frequency domain. However, signal processing practitioners should not say that, because resolution'' in signal processing refers to the ability to resolve'' closely spaced features in a spectrum analysis (see Book IV [70] for details). The usual way to increase spectral resolution is to take a longer DFT without zero padding--i.e., look at more data. In the field of graphics, the term resolution refers to pixel density, so the common terminology confusion is reasonable. However, remember that in signal processing, zero-padding in one domain corresponds to a higher interpolation-density in the other domain--not a higher resolution.

### Ideal Spectral Interpolation

Using Fourier theorems, we will be able to show (§7.4.12) that zero padding in the time domain gives exact bandlimited interpolation in the frequency domain.7.9In other words, for truly time-limited signals , taking the DFT of the entire nonzero portion of extended by zeros yields exact interpolation of the complex spectrum--not an approximation (ignoring computational round-off error in the DFT itself). Because the fast Fourier transform (FFT) is so efficient, zero-padding followed by an FFT is a highly practical method for interpolating spectra of finite-duration signals, and is used extensively in practice. Before we can interpolate a spectrum, we must be clear on what a spectrum'' really is. As discussed in Chapter 6, the spectrum of a signal at frequency is defined as a complex number computed using the inner product

That is, is the unnormalized coefficient of projection of onto the sinusoid at frequency . When , for , we obtain the special set of spectral samples known as the DFT. For other values of , we obtain spectral points in between the DFT samples. Interpolating DFT samples should give the same result. It is straightforward to show that this ideal form of interpolation is what we call bandlimited interpolation, as discussed further in Appendix D and in Book IV [70] of this series.

### Interpolation Operator

The interpolation operator interpolates a signal by an integer factor using bandlimited interpolation. For frequency-domain signals , , we may write spectral interpolation as follows:

Since is initially only defined over the roots of unity in the plane, while is defined over roots of unity, we define for by ideal bandlimited interpolation (specifically time-limited spectral interpolation in this case). For time-domain signals , exact interpolation is similarly bandlimited interpolation, as derived in Appendix D.

### Repeat Operator

Like the and operators, the operator maps a length signal to a length signal:
Definition: The repeat times operator is defined for any by

where , and indexing of is modulo (periodic extension). Thus, the operator simply repeats its input signal times.7.10 An example of is shown in Fig.7.8. The example is

A frequency-domain example is shown in Fig.7.9. Figure 7.9a shows the original spectrum , Fig.7.9b shows the same spectrum plotted over the unit circle in the plane, and Fig.7.9c shows . The point (dc) is on the right-rear face of the enclosing box. Note that when viewed as centered about , is a somewhat triangularly shaped'' spectrum. We see three copies of this shape in .
The repeat operator is used to state the Fourier theorem

where is defined in §7.2.6. That is, when you stretch a signal by the factor (inserting zeros between the original samples), its spectrum is repeated times around the unit circle. The simple proof is given on page .

### Downsampling Operator

Downsampling by (also called decimation by ) is defined for as taking every th sample, starting with sample zero:

The operator maps a length signal down to a length signal. It is the inverse of the operator (but not vice versa), i.e.,

The stretch and downsampling operations do not commute because they are linear time-varying operators. They can be modeled using time-varying switches controlled by the sample index .
The following example of is illustrated in Fig.7.10:

Note that the term downsampling'' may also refer to the more elaborate process of sampling-rate conversion to a lower sampling rate, in which a signal's sampling rate is lowered by resampling using bandlimited interpolation. To distinguish these cases, we can call this bandlimited downsampling, because a lowpass-filter is needed, in general, prior to downsampling so that aliasing is avoided. This topic is address in Appendix D. Early sampling-rate converters were in fact implemented using the operation, followed by an appropriate lowpass filter, followed by , in order to implement a sampling-rate conversion by the factor .

### Alias Operator

Aliasing occurs when a signal is undersampled. If the signal sampling rate is too low, we get frequency-domain aliasing. The topic of aliasing normally arises in the context of sampling a continuous-time signal. The sampling theorem (Appendix D) says that we will have no aliasing due to sampling as long as the sampling rate is higher than twice the highest frequency present in the signal being sampled. In this chapter, we are considering only discrete-time signals, in order to keep the math as simple as possible. Aliasing in this context occurs when a discrete-time signal is downsampled to reduce its sampling rate. You can think of continuous-time sampling as the limiting case for which the starting sampling rate is infinity. An example of aliasing is shown in Fig.7.11. In the figure, the high-frequency sinusoid is indistinguishable from the lower-frequency sinusoid due to aliasing. We say the higher frequency aliases to the lower frequency.
Undersampling in the frequency domain gives rise to time-domain aliasing. If time or frequency is not specified, the term aliasing'' normally means frequency-domain aliasing (due to undersampling in the time domain). The aliasing operator for -sample signals is defined by

Like the operator, the operator maps a length signal down to a length signal. A way to think of it is to partition the original samples into blocks of length , with the first block extending from sample 0 to sample , the second block from to , etc. Then just add up the blocks. This process is called aliasing. If the original signal is a time signal, it is called time-domain aliasing; if it is a spectrum, we call it frequency-domain aliasing, or just aliasing. Note that aliasing is not invertible in general. Once the blocks are added together, it is usually not possible to recover the original blocks. Example:

The alias operator is used to state the Fourier theorem7.4.11)

That is, when you downsample a signal by the factor , its spectrum is aliased by the factor .
Figure 7.12 shows the result of applied to from Figure 7.9c. Imagine the spectrum of Fig.7.12a as being plotted on a piece of paper rolled to form a cylinder, with the edges of the paper meeting at (upper right corner of Fig.7.12a). Then the operation can be simulated by rerolling the cylinder of paper to cut its circumference in half. That is, reroll it so that at every point, two sheets of paper are in contact at all points on the new, narrower cylinder. Now, simply add the values on the two overlapping sheets together, and you have the of the original spectrum on the unit circle. To alias by , we would shrink the cylinder further until the paper edges again line up, giving three layers of paper in the cylinder, and so on. Figure 7.12b shows what is plotted on the first circular wrap of the cylinder of paper, and Fig.7.12c shows what is on the second wrap. These are overlaid in Fig.7.12d and added together in Fig.7.12e. Finally, Figure 7.12f shows both the addition and the overlay of the two components. We say that the second component (Fig.7.12c) aliases'' to new frequency components, while the first component (Fig.7.12b) is considered to be at its original frequencies. If the unit circle of Fig.7.12a covers frequencies 0 to , all other unit circles (Fig.7.12b-c) cover frequencies 0 to . In general, aliasing by the factor corresponds to a sampling-rate reduction by the factor . To prevent aliasing when reducing the sampling rate, an anti-aliasing lowpass filter is generally used. The lowpass filter attenuates all signal components at frequencies outside the interval so that all frequency components which would alias are first removed. Conceptually, in the frequency domain, the unit circle is reduced by to a unit circle half the original size, where the two halves are summed. The inverse of aliasing is then repeating'' which should be understood as increasing the unit circle circumference using periodic extension'' to generate more spectrum'' for the larger unit circle. In the time domain, on the other hand, downsampling is the inverse of the stretch operator. We may interchange time'' and `frequency'' and repeat these remarks. All of these relationships are precise only for integer stretch/downsampling/aliasing/repeat factors; in continuous time and frequency, the restriction to integer factors is removed, and we obtain the (simpler) scaling theorem (proved in §C.2).
Next Section:
Even and Odd Functions
Previous Section:
The DFT and its Inverse Restated