Cascade Integrator Comb Filters
Digital filters are formed by a standard set of resources, memory or delays, summing junctions, multipliers, and resamplers. Architectures that combine these resources build a variety of filtering systems. When faced with two or more contending filtering architectures to solve a given problem, we compare their relative cost as well as their relative performance. In the early days of digital signal processing (DSP) the number of multiplies and data transfers per data sample were standard cost measures. Another comparative cost is sensitivity to finite precision coefficients and required register and accumulator widths. A delight to application specific integrated circuit (ASIC) designers, and to a lesser extent field programmable gate array (FPGA) designers, is a class of filters that does not require multipliers, requires few data transfers, and further exhibits an easy to derive relationship between filter specifications and accumulator widths. These filters are variants of a structure based on the sliding average filter. This chapter presents these filters and discusses their performance under finite arithmetic.
11.1 A Multiply-free Filter
A filter with a rectangle-shaped impulse response is called a boxcar or a sliding average filter. It is a simple FIR filter with unit-valued coefficients that performs a filtering task without multiplies. The quality of the filtering is actually not very good since the spectral response of the boxcar filter, as shown in (11.1) and illustrated in Figure 11.1, exhibits only 13-dB attenuation. The simplicity of one form of implementation is so attractive we are drawn to this filter even though the filtering performance is not very good. We will simply have to find a way to improve its performance.
Figure 11.1 Boxcar Filter Impulse Response and Frequency Response
The FIR filter implementation of the boxcar filter is shown in Figure 11.2.
Figure 11.2 FIR Filter Implementation of Boxcar Filter
Conceptually, the filter computes an output as follows: An input arrives, and the data in the register shifts one place to the right to accommodate the new arrival. The filter forms the sum of the contents of the registers and outputs this sum. This is shown in (11.2).
The process is repeated upon the arrival of each new input sample. If we think about it, this is not a very efficient implementation of the filter. When the new input arrives, the shift to the right of the register contents discards the sample that had arrived M-samples ago to make room for the latest input sample. The new output sum differs from the previous sum by the addition of the new data point and the removal of the M-sample old data point. A recursive form of the boxcar filter can be implemented by altering the previous sum by the known difference. This form of the sum is shown in (11.3).
This form of the filter is known as the CIC. The block diagram of this filter is shown in Figure 11.3. The integrator is the "I" in the name CIC, and it is easily identified as the recursive accumulator. By default, the M-units of delay and the subtraction preceding the integrator must be the comb filter, the second "C" in the name CIC. This section has a simple impulse response a 1 at time index 0 followed by a 1 at time index M. The Z-transform of this impulse response is shown in (11.4). The reason this filter is called a comb filter can be traced to its frequency response, which as shown in (11.5) is a sinusoid. The magnitude response of the filter, shown in Figure 11.4, has the appearance of a rectified sine wave with M-periodic zeros spanning the frequency axis. The periodic zeros remind us of the teeth of a comb, hence the name, comb filter.
Figure 11.3 Cascade Integrator Comb Filter
Figure 11.4 Frequency Response of 10-tap Comb Filter
Notice from Figure 11.3 that in this form of the filter only two summations are required to form the filter output while in the direct implementation, indicated in Figure 11.2, M-additions are required to form the filter output. This is valid for any M. We are thus able to replace 100 adds with 2 adds if we implement the boxcar filter as a CIC filter. Both implementations require the same amount of memory but modifications yet to come will reduce the memory required for the CIC.
An alternate derivation of the CIC structure is available from the Z-transform of the boxcar filter's impulse response. This is shown in (11.6), which we recognize as the first M-terms of the geometric series as shown in (11.7).
The closed form of this series is shown in (11.8).
Equation (11.8) can be cast as a polynomial in Z as in (11.9).
In this form of the Z-transform we can easily see that the zeros, the numerator roots, are uniformly distributed around the unit circle at the M-roots of unity and that the zero at z = 1 is canceled by the pole, a denominator root, at the same location. This pole zero cancellation is certainly valid in the ratio of polynomial representation of the filter but may not be in the following partition.
Returning to (11.8) we perform a questionable step and then examine the consequences of that maneuver. We treat the numerator and denominator of (11.8) as if they reside in different filters. Normally we are free to do this; what we have to question here is are we able to separate the numerator and denominator when they contain canceling roots? Technically we cannot place canceling roots in separate filters. I once had a student get angry with me for separating them. We will shortly see why we are not permitted do so and then find a work around. The separated form of the filter is shown in (11.10).
An obvious, but as just mentioned perhaps incorrect, conclusion to be drawn from this partitioned form of the boxcar filter is that the filter can be implemented as the cascade of two filters, an integrator and a comb. This is the structure shown in Figure 11.3, a structure arrived at from a different perspective.
Figure 11.5 presents two filter structures that we now compare to the original boxcar filter. The two structures are reordered versions of the comb filter and the integrator. This reordering is standard fare for linear systems since linear time invariant systems commute. Shown by each of the three filters is its impulse response. The impulse response of the tapped delay line version of the boxcar is simple and obvious.
Figure 11.5 Structures and Associated Impulse Responses of Boxcar, of Cascade Comb and of Integrator, and Cascade Integrator and Comb
The impulse response of the comb and integrator cascade is formed in two phases. We first see the comb response, which is a sequence of two impulses separated by M-samples. The first impulse applied to the integrator circulates around the integrator, outputting the same unit valued samples. When the second impulse arrives at the integrator it cancels the circulating first impulse, and the integrator response goes to zero. The composite response of the cascade filters matches the response of the boxcar. No surprise yet!
The impulse response of the integrator and comb cascade is also formed in two phases. We first see the integrator response, which is a recirculating copy of the input impulse that is a step or DC response. This step is delivered directly to the output and matches the boxcar response. M samples into the response, and an M-unit delayed version of the output step arrives at the output summing junction where they subtract from the direct path output of the integrator and set each output sample to zero. This output sequence also matches the response of the boxcar filter. If an observer joined us now and examined only the input and output of this filter she would see zero input and zero output and might conclude that the filter is at rest, a standard attribute of a stable system. In fact it isn't; it is circulating the original input impulse in the integrator and delivering pairs of samples via the comb filter to sum to zero and give the impression the system is at rest. What we are witnessing is the effect of an internal state of the system, the integrator that is neither observable nor controllable from external ports. Remember that this state did not exist in the original boxcar filter, it is the denominator root canceled by a zero of the numerator.
Figure 11.6 presents the same filter structures we just examined but this time we compare their responses to an input step. Shown by each of the three filters is its step response. The step response of the tapped delay line version of the boxcar contains two distinct intervals. The first interval of length M is a ramping transient response that lasts until the filter is filled. The second interval is the steady state response to the step of constant level M.
Figure 11.6 Structures and Associated Step Responses of Boxcar, of Cascade Comb and of Integrator, and Cascade Integrator and Comb
The step response of the comb and integrator cascade is also formed in two phases. We first see the comb response, which is a square wave sequence of length M-samples. The square wave forms the transient ramp in the integrator. At the end of M-samples the comb response goes to zero and the integrator stops accumulating inputs. At this point the integrator output has reached steady state and circulates and outputs its constant level of M. The composite response of the cascade filters matches the response of the boxcar. Still no surprise yet!
The step response of the integrator and comb cascade is also formed in two phases. We first see the integrator response, which is a ramp sequence formed by integrating the input step. This ramp is delivered directly to the output as the start of the boxcar response. M samples into the response, an M-unit delayed version of the output ramp arrives at the output summing junction where they subtract from the direct path delivered by the integrator to form a constant difference of amplitude M for each output sample. This output sequence also matches the response of the boxcar filter. If an observer joined us now and examined only the input and output of this filter she would see a finite input and a finite output and conclude that the filter is stable, an alternate definition of a stable system. In fact it is not stable in this sense since the integrator is on the way to infinity. The difference between the ramp and the M-unit delayed ramp formed in the comb filter is a constant even as the ramp climbs without bound. Here again we are witnessing the effect of an internal state of the system that is neither observable nor controllable. Any finite state machine that tries to implement this structure is bound to overflow its accumulator.