AMAZON multi-meters discounts AMAZON oscilloscope discounts
In this section we present two implementations used to build computation ally efficient, linear phase, finite impulse response (FIR) filters. We discuss these special FIR filters now because their behavior will be easier to under stand using the z-transform concepts introduced in the last section.
The first filter type presented is called frequency sampling filters. They are in that special class of linear phase finite impulse response (FIR) filters built with recursive structures (using feedback). The Section 1 material is a bit advanced for DS13 beginners, but it deserves study for two reasons. First, these filters can be very efficient (minimized computational workload) for narrow band lowpass filtering applications; and second, understanding their operation and design reinforces much of the DSP theory covered in previous sections.
Section 2 discusses interpolated lowpass FIR filters. These filters, implemented with non-recursive structures (no feedback), cascade multiple FIR filters to reduce computational workload. Their implementation is an innovative approach where more than one unit time delay separates the multipliers in a traditional tapped delay line structure.
The common thread among these two filter types is they're lean mean filtering machines. They wring every last drop of computational efficiency from a guaranteed stable, linear phase filter. In many lowpass filtering applications these FIR filter types can attain greatly reduced computational work loads compared to the traditional Parks-McClellan-designed FIR filters discussed in Section 5.
1. FREQUENCY SAMPLING FILTERS: THE LOST ART
This section describes a class of digital filters, called frequency sampling filters, used to implement linear-phase FIR filter designs. Although frequency sampling filters were developed over 35 years ago, the advent of the powerful Parks-McClellan non-recursive FIR filter design method has driven them to near obscurity. In the 1970s, frequency sampling filter implementations lost favor to the point where their coverage in today's DSP classrooms and text books ranges from very brief to nonexistent. However, we'll show how frequency sampling filters remain more computationally efficient than Parks McClellan-designed filters for certain applications where the desired pass band width is less than roughly one fifth the sample rate. The purpose of this material is to introduce the DSP practitioner to the structure, performance, and design of frequency sampling filters; and to present a detailed comparison between a proposed high-performance frequency sampling filter implementation and its non-recursive FIR filter equivalent. In addition, we'll clarify and expand the literature of frequency sampling filters concerning the practical issues of phase linearity, filter stability, gain normalization, and computational workload using design examples.
Frequency sampling filters were founded upon the fact that the traditional N-tap non-recursive (direct convolution) FIR filter in FIG. 1(a) can be implemented as a comb filter in cascade with a bank of N complex resonators as shown in FIG. 1(b). We call the filter in FIG. 1(b) a general frequency sampling filter (FSF), and its equivalence to the non-recursive FIR filter has been verified. While the h(k) coefficients, where 0 < k < N-1, of N-tap non-recursive FIR filters are typically real-valued, in general they can be complex. That's the initial assumption made in equating the two filters in FIG. 1. The H(k) gain factors, the discrete Fourier transform of the h(k) time domain coefficients, are in the general case complex values represented by I H(k) I e^jθ(k) .
The basis of FSF design is the definition of a desired FIR filter frequency response in the form of H(k) frequency-domain samples, whose magnitudes are depicted as dots in FIG. 2. Next, those complex H(k) sample values as used as gain factors following the resonators in the FSF structure (block diagram). If you haven't seen it before, please don't be intimidated by this apparently complicated FSF structure. We'll soon understand every part of it, and how those parts work together.
Later we'll develop the math to determine the interpolated (actual) frequency magnitude response I H(e^jw) I of an FSF shown by the continuous curve in FIG. 2. In this figure, the frequency axis labeling convention is a normalized angle measured in IC radians with the depicted co frequency range covering 0 to 21( radians, corresponding to a cyclic frequency range of 0 to f, where f, is the sample rate in Hz.
FIG. 1 FIR filters: (a) N-tap non-recursive: (b) equivalent N-section
frequency sampling filter.
FIG. 2 Defining a desired filter response by frequency sampling.
To avoid confusion, we remind the reader there is a popular non-recursive FIR filter design technique known as the frequency sampling design method described in the DSP literature. That design scheme begins (in a manner similar to an FSF design) with the definition of desired H(k) frequency response samples, then an inverse discrete Fourier transform is performed on those samples to obtain a time-domain impulse response sequence that's used as the h(k) coefficients in the non-recursive N-tap FIR structure of FIG. 1(a). In the FSF design method described here, the desired frequency domain H(k) sample values are the coefficients used in the FSF structure of FIG. 1(b), which is typically called the frequency sampling implementation of an FIR filter.
Although more complicated than non-recursive FIR filters, FSFs deserve study because in many narrowband filtering situations they can implement a linear-phase FIR filter at a reduced computational workload relative to an N-tap nonrecursive FIR filter. The computation reduction occurs because, while all of the h(k) coefficients are used in the nonrecursive FIR filter implementation, most of the H(k) values will be zero-valued, corresponding to the stopband, and need not be implemented. To understand the function and benefits of FSFs, we start by considering the behavior of the comb filter and then review the performance of a single digital resonator.
1.1 A Comb Filter and Complex Digital Resonator in Cascade
A single section of a complex FSF is a comb filter followed by a single complex digital resonator as shown in FIG. 3.
The 1/N gain factor following a resonator in FIG. 1(b) is omitted, for simplicity, from the single-section complex FSF. (The effect of including the 1 /N factor will be discussed later.) To understand the single-section FSF's operation, we first review the characteristics of the nonrecursive comb filter whose time-domain difference equation is
v(n) = x(n) - x(n-N) (eqn. 1)
with its output equal to the input sequence minus the input delayed by N samples. The comb filter's z-domain transfer function is
(eqn. 2)
FIG. 3 A single section of a complex FSF.
The frequency response of a comb filter, derived in Appendix G, Section I, is
(eqn. 3)
with a magnitude response of IH_comb (e^j0)) I = 2 I sin(omega N/ 2) I whose maximum value is 2. It's meaningful to view the comb filter's time-domain impulse response and frequency-domain magnitude response shown in FIG. 4 for N = 8. The magnitude response makes it clear why the term "comb" is used.
Equation (eqn. 2) leads to a key feature of this comb filter: its transfer function has N periodically spaced zeros around the z-plane's unit circle shown in FIG. 4(c). Each of those zeros, located at z(k) = e^j2K pi /N , where k = 0, 1, 2, . . N-1, corresponds to a magnitude null in FIG. 4(b), where the normalized frequency axis is labeled from -7E to +TE radians. Those z(k) values are the N roots of unity when we set Eq. (eqn. 2) equal to zero yielding z(k)N = (e^j 2 pi k/N)N = 1.
We can combine the magnitude response (on a linear scale) and z-plane information in the three-dimensional z-plane depiction shown in FIG. 5, where we see the intersection of the I H_comb (z) I surface and the unit circle.
Breaking the curve at the z = -1 point, and laying it flat, corresponds to the magnitude curve in FIG. 4(b).
FIG. 4 Time and frequency-domain characteristics of an N = 8 comb filter.
To preview where we're going, soon we'll build an FSF by cascading the comb filter with a digital resonator having a transfer function pole lying on top of one of the comb's z-plane zeros, resulting in a linear-phase bandpass filter. With this thought in mind, let's characterize the digital resonator in FIG. 3.
FIG. 5 The z-plane frequency magnitude response of the N = 8 comb filter.
The complex resonator's time-domain difference equation is y(n) = v(n) + eioer y(n-1),
(eqn. 4)
where the angle wr , -Tt (Or it determines the resonant frequency of our resonator. We show this by considering the resonator's z-domain transfer function
(eqn. 5)
and the resonator's complex time-domain impulse response, for co, rc/4, in FIG. 6.
FIG. 6 Single complex digital resonator impulse response with ωr =
π/4
FIG. 7 Time and frequency-domain characteristics of a single complex
digital resonator with ωr = π/4 .
The ωr = π/4 resonator's impulse response is a complex sinusoid, the real part (a cosine sequence) of which is plotted in FIG. 7(a), and can be considered infinite in duration. (The imaginary part of the impulse response is, as we would expect, a sinewave sequence.) The frequency magnitude response is very narrow and centered at ca r . The resonator's H(z) has a single zero at z = 0, but what concerns us most is its pole, at z = (Or, on the unit circle at an angle of (or as shown in FIG. 7(c). We can think of the resonator as an infinite impulse response (IIR) filter that's conditionally stable because its pole is neither inside nor outside the unit circle.
FIG. 8 Time and frequency-domain characteristics of a single-section
complex FSF where N = 32, k = 2, and H(2) = 1.
We now analyze the single-section complex FSF in FIG. 3. The z-domain transfer function of this FSF is the product of the individual transfer functions and H(k), or
(eqn. 6)
If we restrict the resonator's resonant frequency cor to be 27ck/N , where k = 0,1,2, . . NA, then the resonator's z-domain pole will be located atop one of the comb's zeros and we'll have an FSF transfer function of
(eqn. 7)
where the subscript "ss" in Eq. (eqn. 7) means a single-section complex FSF. We can understand a single-section FSF by reviewing its time and frequency domain behavior for N = 32, k = 2, and H(2) = 1 shown in FIG. 8.
FIG. 8 is rich in information. We see that the complex FSF's impulse response is a truncated complex sinusoid whose real part is shown in FIG. 8(a). The positive impulse from the comb filter started the resonator oscillation at zero time. Then at just the right sample, N = 32 samples later-which is k = 2 cycles of the sinusoid-the negative impulse from the comb arrives at the resonator to cancel all further oscillation. The frequency magnitude response, being the Fourier transform of the truncated sinusoidal impulse response, takes the form of a sin(x)/x-like function. In the z-plane plot of FIG. 8, the resonator's pole is indeed located atop the comb filter's k = 2 zero on the unit circle canceling the frequency magnitude response null at 2 pi k/N = pi/8 radians. (Let's remind ourselves that a normalized angular frequency of 2 pi k/N radians corresponds to a cyclic frequency of k fs / N where f, is the sample rate in Hz. Thus the filter in FIG. 8 resonates at/5 /16 Hz.) We can determine the FSF's interpolated frequency response by evaluating the H(z) transfer function on the unit circle. Substituting 01 for z in H 5 (z) in Eq. (eqn. 7), we obtain an Hss (e^jw) frequency response of
(eqn. 8)
Evaluating I Hss (eiw) I over the frequency range of < w < it yields the curve in FIG. 8(b). Our single-section FSF has linear phase because the cilafiv term in Eq. (eqn. 8) is a fixed phase angle based on constants N and k, the angle of H(k) is fixed, and the e^-jw(N-1)/2 phase term is a linear function of frequency (w). As derived in Sect. G, Section 2, the maximum magnitude response of a single-section complex FSF is N when I H(k)I = 1. We illustrate this fact in FIG. 9.
1.2 Multi-section Complex FSFs
FIG. 9 The z-plane frequency magnitude response of a single-section
com plex FSF with N = 32 and k = 2
FIG. 10 Three-section N = 32 complex FSF: (a) desired frequency magnitude
response; (b) implementation.
In order to build useful FSFs we use multiple resonator sections, as indicated in FIG. 1(b), to provide bandpass FIR filtering. For example, let's build a three-section complex bandpass FSF by establishing the parameters of N = 32 with the non-zero frequency samples H(2), H(3), and H(4). The desired frequency magnitude response is shown in FIG. 10(a) with the bandpass FSF structure provided in FIG. 10(b). Exploring this scenario, recall that the z-domain transfer function of parallel filters is the sum of the individual transfer functions. So, the transfer function of an N-section complex FSF from Eq. (eqn. 7) is
(eqn. 9)
where the subscript "cplx" means a complex multi-section FSF. Let's pause for a moment to understand Eq. (eqn. 9). The first factor on the right side represents a comb filter, and the comb is in cascade (multiplication) with the sum of ratio terms. The summation of the ratios (each ratio is a resonator) means those resonators are connected in parallel. Recall from Section 6.8.1 that the combined transfer function of filters connected in parallel is the sum of the individual transfer functions. It's important to be comfortable with the form of Eq. (eqn. 9) because we'll be seeing many similar expressions in the material to come.
So a comb filter is driving a bank of resonators. For an N = 32 complex FSF we could have up to 32 resonators, but in practice only a few resonators are needed for narrowband filters. In FIG. 10, we used only three resonators. That's the beauty of FSFs: most of the H(k) gain values in Eq. (eqn. 9) are zero-valued and those resonators are not implemented, keeping the FSF computationally efficient.
Using the same steps as in Sect. G, Section 2, we can write the frequency response of a multi-section complex FSF, such as in FIG. 10, as
(eqn. 10)
The designer of a multisection complex FSF can achieve any desired filter phase response by specifying the o(k) phase angle value of each non-zero complex H(k) = I H(k) I ei°(k) gain factor. However, to build a linear-phase complex FSF, the designer must: (a) specify the o(k) phase values to be a linear function of frequency, and (b) define the o(k) phase sequence so its slope is -(N-1)/2. This second condition forces the FSF to have a positive time delay of (N-1)/2 samples, as would the N-tap nonrecursive FIR filter in FIG. 1(a). The following expressions for o(k), with N being even, satisfy those two conditions.
(eqn. 11)
(eqn. 11")
(eqn. 12)
Two example linear-phase 125(k) sequences, for N 19 and N = 20, are shown in FIG. 11. The o(0) , 0 values set the phase to be zero at zero Hz, and the ø(N/2) 0, at the cyclic frequency of f,/2 in FIG. 11(h), ensures a symmetrical time-domain impulse response.
Assigning the appropriate phase for the non-zero 11(k) gain factors is, however, only half the story in building a multisection FSF. There's good news to be told. Examination of the frequency response Eq. (eqn. 10) shows us a simple way to achieve phase linearity in practice. Substituting I H(k)I with o(k) defined by Eq. (eqn. 11) above, for H(k) in Eq. (eqn. .10) provides the expression for the frequency response of an even-N multi-section linear-phase complex FSF,
(eqn. 13)
where the subscript "Ip" indicates linear-phase.
FIG. 11 Linear-phase of H(k) for a single-section FSF: (a) with N =
19; (b) N= 20.
Equation (eqn. 13) is not as complicated as it looks. It merely says that the total FSF frequency response is the sum of individual resonators' sin(x)/x-like frequency responses. The first term within the brackets represents the resonator centered at k = N/2 (f,/2). The first summation is the positive-frequency resonators and the second summation represents the negative-frequency resonators.
FIG. 12 Comparison of the magnitude and phase responses, and phase
difference, between the k = 3 and the k = 4 FSFs, when N = 32.
The (-1)k terms in the numerators of Eq. (eqn. 13) deserve our attention be cause they are an alternating sequence of plus and minus ones. Thus a single section frequency response will be 180 deg. out of phase relative to its neighboring section. That is, the outputs of neighboring single-section FSFs will have a fixed TC radians phase difference over the passband common to both filters as shown in FIG. 12. (The occurrence of the (-1)k factors in Eq. (eqn. 13) is established in Sect. G, Section 3.)
FIG. 13 Simplified N = 32 three-section linear-phase complex bandpass
FSF: (a) implementation; (b) frequency response.
The effect of those (-1)k factors is profound, and not emphasized nearly enough in the literature of FSFs. Rather than defining each non-zero complex H(k) gain factor with their linearly increasing phase angles ø(k), we can build a linear-phase multisection FSF by using just the I H(k) I magnitude values and incorporating the alternating signs for those real-valued gain factors. In addition, if the non-zero I H(k) I gain factors are all equal to one, we avoid FIG. 10's gain factor multiplications altogether, as shown in FIG. 13(a). The unity-valued I H(k) I gain factors and the alternating-signed summation allows the complex gain multiplies in FIG. 10(b) to be replaced by simple adds and subtracts as in FIG. 13(a). We add the even-k and sub tract the odd-k resonator outputs. FIG. 13(6) confirms the linear phase, with phase discontinuities at the magnitude nulls, of these multisection complex FSFs. The transfer function of the simplified complex linear phase FSF is
(eqn. 14)
(We didn't use the "Ip" subscript in Eq. (eqn. 14) because, from here on out, all our complex FSFs will be linear phase.)
1.3 Ensuring FSF Stability
So far we've discussed complex FSFs with pole/zero cancellation on the unit circle. However, in practice, exact cancellation requires infinite-precision arithmetic. Real-world binary word quantization errors in the FSF's coefficients can make the filter poles lie outside the unit circle. The result would be an unstable filter, whose impulse response is no longer finite in duration, which must be avoided. (This is a beautiful example of the time-honored phrase, "In theory, there's no difference between theory and practice. In practice, sometimes the theory doesn't work.") Even if a pole is located only very slightly outside the unit circle, roundoff noise will grow as time increases, corrupting the output samples of the filter. We prevent this problem by moving the comb filter's zeros and the resonators' poles just inside the unit circle, as depicted in FIG. 14(a). Now the zeros and a pole are located on a circle of radius r, where the damping factor r is just slightly less than 1.
We call r the damping factor because a single-stage FSF impulse response becomes a damped sinusoid. For example, the real part of the impulse response of a single-stage complex FSF, where N = 32, k = 2, H(2) = 2, and r = 0.95, is shown in FIG. 14(b). Compare that impulse response to FIG. 8(a). The structure of a single-section FSF with zeros and a pole inside the unit circle is shown in FIG. 14(c).
FIG. 14 Ensuring FSF stability: (a) poles and zeros are inside the
unit circle; (b) real part of a stable single-section FSF impulse response;
(c) FSF structure.
The comb filter's feedforward coefficient is -rN because the new z domain transfer function of this comb filter is
(eqn. 15)
with the N zeros for this comb being located at
z r,i (k) = reihr -kiN, where k = 0,1, 2, . . N-1.
Those zr, i (k) values are the N roots of rN when we set Eq. (eqn. 15) equal to zero, yielding zr, i (k)N (rdlak /N)N rN. The z-domain transfer function of the resonator in FIG. 14(b), with its pole located at a radius of r, at an angle of
(eqn. 16)
leading us to the transfer function of a guaranteed-stable single-section complex FSF of
(eqn. 17)
whose implementation is shown in FIG. 14(c). The subscript "gs,ss" means a guaranteed-stable single-section FSF. The z-domain transfer function of a guaranteed-stable N-section complex FSF is
(eqn. 18)
where the subscript "gs,cplx" means a guaranteed-stable complex multi-section FSF. The frequency response of a guaranteed-stable multi-section complex FSF (derived in Section G, Section 4) is
(eqn. 19)
If we modify the bandpass FSF structure in FIG. 43(a) to force the zeros and poles inside the unit circle, we have the structure shown in FIG. 15(a). The frequency-domain effects of zeros and poles inside the unit circle are significant, as can be seen in FIG. 15(b) for the two cases where r = 0.95 and r = 0.9999.
FIG. 15 Guaranteed-stable N = 32 three-section linear-phase complex
bandpass FSF: (a) implementation; (b) frequency response for two values
of damping factor r.
FIG. 15(b) shows how a value of r = 0.95 badly corrupts our complex bandpass FSF performance; the stop band attenuation is degraded, and significant phase nonlinearity is apparent. Damping factor r values less than unity cause phase nonlinearity because the filter is in a nonreciprocal zero condition. Recall a key characteristic of FIR filters: to maintain linear phase, any z-plane zero located inside the unit circle at z = z (k), where z (k) is not equal to 0, must be accompanied by a zero at a reciprocal location, namely Z = 1/z r<1 (k) outside the unit circle. We do not satisfy this condition here, leading to phase nonlinearity. (The reader should have anticipated nonlinear phase due to the asymmetrical impulse response in FIG. 14(b).) The closer we can place the zeros to the unit circle, the more linear the phase response. So the recommendation is to define r to be as close to unity as your bi nary number format allows[4]. If integer arithmetic is used, set r = where B is the number of bits used to represent a filter coefficient magnitude.
Another stabilization method worth considering is decrementing the largest component (either real or imaginary) of a resonator's e^j2 pi k/N feedback coefficient by one least significant bit. This technique can be applied selectively to problematic resonators and is effective in combating instability due to rounding errors which result in finite-precision ePiricIN coefficients having magnitudes greater than unity.
Thus far we're reviewed FSFs with complex coefficients and frequency magnitude responses not symmetrical about zero Hz. Next we explore FSFs with real-only coefficients having conjugate-symmetric frequency magnitude and phase responses.
FIG. 16 Guaranteed-stable. even-N, Type-I real FSF: (a) structure;
(b) using real-only resonator coefficients.
1.4 Multisection Real-Valued FSFs
We can obtain real-FSF structures (real-valued coefficients) by forcing our complex N-section FSF, where N is even, to have conjugate poles, by ensuring all non-zero H(k) gain factors are accompanied by conjugate H(N-k) gain factors, so that H(N-k) = H*(k). That is, we can build real-valued FSFs if we use conjugate pole pairs located at angles of ±27tk/N radians. The transfer function of such an FSF is
(eqn. 20)
where the subscript "gs,real" means a guaranteed-stable real-valued multisection FSF, and ek is the desired phase angle of the kth section. Eq. (eqn. 20) defines the structure of a Type-I real FSF to be as shown in FIG. 16(a), requiring five multiplies per resonator output sample. The implementation of a real pole-pair resonator, using real-only arithmetic, is shown in FIG. 16(b). Of course, for lowpass FSFs the stage associated with the H(N /2) gain factor in FIG. 16 would not be implemented, and for bandpass FSFs neither stage associated with the H(0) and H(N/2) gain factors would be implemented. The behavior of a single-section Type-I real FSF with N 32, k 3, H(3) = 1, r = 0.99999, and oi = 0 is provided in FIG. 17.
FIG. 17 Time and frequency-domain characteristics of a single-section
Type-I FSF when N = 32, k = 3, 1-1(3) --- 1, r = 0.99999, and (1)3 -= 0,
An alternate version of the Type-I FSF, with a simplified resonator struc ture, can be developed by setting all ek values equal to zero and moving the gain factor of 2 inside the resonators. Next we incorporate the alternating signs in the final summation, as shown in FIG. 18 to achieve linear phase just as we did to arrive at the linear-phase multisection complex FSF in FIG. 13(a) by adding the even-k and subtracting the odd-k resonator outputs.
The "±" symbol in FIG. 18(a) warns us that when N is even, k = (N /2)-1 can be odd or even.
If the non-zero I H(k) I gain factors are unity, this Type-II real FSF re quires only three multiplies per section output sample. When a resonator's multiply by 2 can be performed by a hardware binary arithmetic left shift, only two multiplies are needed per output sample. The transfer function of this real-valued FSF is
(eqn. 21)
FIG. 18 Linear-phase, even-N, Type-II real FSF: (a) structure; (b)
real-only resonator implementation.
Neither the Type-1 or the Type-II FSF have exactly linear phase. While the phase nonlinearity is relatively small, their passband group delays can have a peak-to-peak fluctuation of up to two sample periods (2/fs) when used in multisection applications. This phase nonlinearity is unavoidable because those FSFs have isolated zeros located at z = rcos(2 pi k/N), when theta_k = 0, as shown in FIG. 17(c). Because the isolated zeros inside the unit circle have no accompanying reciprocal zeros located outside the unit circle at z I /ircos(2 pi k/N)1, sadly, this causes phase nonlinearity.
While the Type-I and -II FSFs are the most common types described in the literature of FSFs, their inability to yield exact linear phase has not received sufficient attention or analysis. In the next section we take steps to ob tain linear phase by repositioning the isolated zero.
1.5 Linear-Phase Multisection Real-Valued FSFs
We can achieve exact real-FSF phase linearity by modifying the Type-I real FSF resonator's feedforward coefficients, in FIG. 16(b), moving the isolated zero on top of the comb filter's zero located at z = r. We do this by set- ting ok = irk/N. The numerator of the transfer function of one section of the real FSF, from Eq. (eqn. 20), is cos(0k )-rcos(01 ,-2rtic/N)z • I. If we set this expression equal to zero, and let ok = nk/N, we find the shifted isolated zero location z„ is cos(ok )-rcos(ok-27a/N)z„ = cos(ick/N)-rcos(nk/N-2Trk/N)z„- I 0
...or ...
Substituting nk/N for ok in Eq. (eqn. 20) yields the transfer function of a linear-phase Type-III real FSF as
(eqn. 22)
The implementation of the linear-phase Type-III real FSF is shown in FIG. 19, requiring four multiplies per section output sample.
Notice that the H(N /2), L/2, section is absent in FIG. 19(a). We justify this as follows: the even-N Type-I, -Il, & -III real FSF sections have impulse responses comprising N non-zero samples. As such, their k = N/2 sections' impulse responses, comprising even-length sequences of alternating plus and minus ones, are not symmetrical. This asymmetry would corrupt the exact linear phase should a k = N/2 section be included. Consequently, as with even-length non-recursive FIR filters, even-N Type-1, -Il, & -III real FSFs cannot be used to implement linear-phase highpass filters.
FIG. 19 Even-N, linear-phase, Type-III real FSF: (a) structure; (b)
real-only resonator implementation.
FIG. 20 Interpolated frequency-domain response of a Type-III FSF having
eight sections with N = 32: (a) magnitude response; b) phase response; (c)
group delay compared with an equivalent Type-II FSF.
FIG. 20 shows the frequency-domain performance of an eight-section Type-III FSF for N = 32, where the eight sections begin at DC (0 k 7). FIG. 20(c) provides a group delay comparison between the Type-I11 FSF and an equivalent eight-section Type-II FSF showing the improved Type-III phase linearity having a constant group delay of (N-1)/2 samples over the passband.
1.6 Where We've Been and Where We're Going with FSFs
We've reviewed the structure and behavior of a complex FSF whose complex resonator stages had poles residing atop the zeros of a comb filter, resulting in a recursive FIR filter. Next, to ensure filter implementation stability, we forced the pole/zero locations to be just inside the unit circle. We examined a guaranteed-stable even-N Type-1 real FSF having resonators with conjugate pole pairs resulting in an FSF with real-valued coefficients. Next, we modified the Type-I real FSF structure yielding the more computationally efficient but only moderately linear-phase Type-II real FSF. Finally, we modified the coefficients of the Type-I real FSF, and added post-resonator gain factors resulting in the exact linear-phase Type-III real FSF. During this development, we realized that the even-N Type-I, -II, and -III real FSFs cannot be used to implement linear-phase highpass filters.
In the remainder of this section we introduce a proposed resonator structure that provides superior filtering properties compared to the Type-I, -II, & -III resonators. Next we'll examine the use of non-zero transition band filter sections to improve overall FSF passband ripple and stopband attenuation, followed by a discussion of several issues regarding modeling and de signing FSFs. We'll compare the performance of real FSFs to their equivalent Parks-McClellan-designed N-tap non-recursive FIR filters. Finally, a detailed FSF design procedure is presented.
FIG. 21 Type-IV resonator: (a) original structure; (b), simplified
version.
1.7 An Efficient Real-Valued FSF
There are many real-valued resonators that can be used in FSFs, but of particular interest to us is the Type-1V resonator presented in FIG. 21(a). This resonator deserves attention because it:
• is guaranteed-stable,
• exhibits highly linear phase,
• uses real-valued coefficients,
• is computationally efficient,
• can implement highpass FIR filters, and
• yields stopband attenuation performance superior to the Type-I, -II, and -III FSFs.
From here on in, the Type IV will be our FSF of choice.
Cascading Type-IV resonators with a comb filter provides a Type-IV real-only FSF with a transfer function of
(eqn. 23)
where N is even. (Note, when N is odd, k = N/2 is not an integer and the I H(N /2)1 term does not exist.) As derived in Appendix G, Section 6, the Type-IV FSF frequency response is
(eqn. 24)
The even-N frequency and resonance magnitude responses for a single Type-IV FSF section are
(eqn. 25)
(eqn. 26)
Its resonant magnitude gains at k = 0 (DC), and k = N/2 (f5 /2), are
(eqn. 27)
To reduce the number of resonator multiply operations, it is tempting to combine the dual -r2 factors in FIG. 21(a) to simplify the Type-IV resonator as shown in FIG. 21(b). However, a modification reducing both the number of multiply and addition operations is to implement the (1--r2v2 ) term in the numerator of Eq. (eqn. 23) as a second-order comb filter as shown in FIG. 22(a)[5]. This transforms the Type-IV resonator to that shown in FIG. 22(b). The H(0)1/2 and 1 H(N /2)1/2 gain factors compensate for the gain of 2N for a Type-1V resonator in Eq. (eqn. 27).
FIG. 22 Type-IV, even-N, real FSF: (a) structure; (b) its modified
resonator.
Table 1 Summary of Even-N Real FSF Properties
The "±" symbols in FIG. 22(a) remind us, again, when N is even, k = N/2 could be odd or even. This FSF has the very agreeable characteristic of having an impulse response whose length is N+1 samples. Thus, unlike the Type-I, -II, and -III FSFs, an even-N Type-1V FSF's k N/2 section impulse response (alternating ±1s) is symmetrical, and Type-IV FSFs can be used to build linear-phase highpass filters. When N is odd, the k = N/2 section is absent in FIG. 22, and the odd-N Type-IV transfer function is identical to Eq. (eqn. 23), with the summation's upper limit being (N-1)/2 instead of N/2.
We've covered a lot of ground thus far. Table 1 summarizes what we've discussed concerning real-valued FSFs. The table lists the average pass band group delay measured in sample periods, the number of multiplies and additions necessary per output sample for a single FSF section, and a few re marks regarding the behavior of the various real FSFs. The section gains at their resonant frequencies, assuming the desired I H(01 gain factors are unity, is N for all four of the real-valued FSFs.
1.8 Modeling FSFs
We derived several different H(ein frequency response equations here, not so much to use them for modeling FSF performance, but to examine them in order to help define the structure of our FSF block diagrams. For example, it was analyzing the properties of HType_ iv(ei) that motivated the use of the 1/2 gain factors in the Type-IV FSF structure.
When modeling the FSFs, fortunately it's not necessary to write code to calculate frequency-domain responses using the various H(eiw) equations pro vided here. All that's necessary is code to compute the time-domain impulse response of the FSF being modeled, pad the impulse response with enough zeros so the padded sequence is 10-20 times the length of the original, per form a discrete Fourier transform (DFT) on the padded sequence, and plot the resulting interpolated frequency-domain magnitude and phase. Of course, forcing your padded sequence length to be an integer power of two enables the use of the efficient FFT to calculate frequency-domain responses. Alternatively, many commercial signal processing software packages have built-in functions to calculate filter frequency response curves based solely on the filter's transfer function coefficients.
FIG. 23 Seven-section, N = 32, Type-IV FSF: (a) desired frequency response;
(b) actual performance; (c) using one transition sample; (d) improved stopband
attenuation.
1.9 Improving Performance with Transition Band Coefficients
We can increase FSF stopband attenuation if we carefully define I i(k) I magnitude samples in the transition region, between the passband and stopband.
For example, consider a lowpass Type-IV FSF having seven sections of unity gain, with N -= 32 whose desired performance is shown in FIG. 23(a), and whose interpolated (actual) frequency magnitude response is provided in FIG. 23(b). The assignment of a transition magnitude sample, coefficient T1 whose value is between 0 and 1 as in FIG. 23(c), reduces the abruptness in the transition region between the passband and the stopband of our desired magnitude response. Setting T1 = 0.389 results in reduced passband ripple and the improved stopband sidelobe suppression shown in FIG. 23(d). The price we pay for the improved performance is the computational cost of an additional FSF section and increased width of the transition region.
Assigning a coefficient value of T1 = 0.389 was not arbitrary or magic.
Measuring the maximum stopband sidelobe level for various values of 0 Ti 5_ 1 reveals the existence of an optimum value for T1 . FIG. 24 shows that the maximum stopband sidelobe level is minimized when T1 = 0.389. The minimum sidelobe level of -46 dB (when T1 = 0.389) corresponds to the height of the maximum stopband sidelobe in FIG. 23(d). This venerable and well known method of employing a transition region coefficient to re duce passband ripple and minimize stopband sidelobe levels also applies to bandpass FSF design where the transition sample is used just before and just after the filter's passband unity-magnitude | H(k) | samples.
Further stopband sidelobe level suppression is possible if two transition coefficients, T1 and T2, are used such that 0 T2 T1 5_ 1. (Note: for lowpass filters, if T1 is the | H(k)| sample, then T2 is the |H(k+1)| sample.) Each additional transition coefficient used improves the stopband attenuation by approximately 25 dB. However, finding the optimum values for the T coefficients is a daunting task. Optimum transition region coefficient values depend on the number of unity-gain FSF sections, the value of N, and the number of coefficients used. Unfortunately, there's no closed form equation available to calculate optimum transition coefficient values; we must search for them empirically.
FIG. 24 Maximum stopband sidelobe level as a function of the transition
region coefficient value for a seven-section Type-IV real FSF when N. 32.
If one coefficient (T1 ) is used, finding its optimum value can be considered a one-dimensional search. If two coefficients are used, the search be comes two dimensional, and so on. Fortunately, descriptions of linear algebra search technique are available , and commercial mathematical software packages have built-in optimization functions to facilitate this computationally intensive search. For the Type-1/11 FSFs, tables of optimum transition region coefficients for various N, and number of FSF sections used, have been pub lished11 1, with a subset of those tables provided as an appendix in a text bookt21. For the higher performance Type-1V FSF, tables of optimum coefficient values have been compiled by this author and provided in Appendix H. With this good news in mind, shortly we'll look at a real-world FSF de sign example to appreciate the benefits of FSFs.
Fig. 25 Four possible orientations of comb filter zeros near the unit
circle
1.10 Alternate FSF Structures
With the primary comb filter in FIG. 22 having a feed forward coefficient of -rN, its even-N transfer function zeros are equally spaced around and inside the unit circle, as shown in FIG. 4(c) and FIG. 25(a), so the k = 1 zero is at an angle of 2n/N radians. In this Case 1, if N is odd the comb's zeros are spaced as shown in FIG. 25(b). An alternate situation, Case 11, exists when the comb filter's feedforward coefficient is +rN. In this mode, an even-N comb filter's zeros are rotated counterclockwise on the unit circle by rc/N radians as shown in FIG. 25(c) where the comb's k = 1 zero is at an angle of an/N radians[5]. The k = U zeros are shown as solid dots.
The structure of a Case II FSF is identical to that of a Case I FS.F. How ever, the Case II resonators' coefficients must be altered to rotate the poles by n/N radians to ensure pole/zero cancellation. As such, the transfer function of a Case II, even-N, Type-IV FSF is
(eqn. 28)
Because a Case II FSF cannot have a pole or a zero at z = 1 (DC), these FSFs are unable to implement lowpass filters. Table 2 lists the filtering capabilities of the various Case I and Case II Type-IV FSFs.
Their inability to implement lowpass filtering limits the utility of Case II FSFs, but their resonator's shifted center frequencies do provide some additional flexibility in defining the cutoff frequencies of bandpass and highpass filters. The remainder of this material considers only the Case I Type-IV FSFs.
Table 2 Type-IV FSF Modes of Operation
FIG. 26 Comparison of the Kaiser window, frequency sampling, and Parks
McClellan designed FIR filters.
1.11 The Merits of FSFs
During the formative years of FIR filter theory (early 1970s) a computer pro gram was made available for designing non-recursive FIR filters using the Parks-McClellan (PM) method. This filter design technique provided complete control in defining desired passband ripple, stopband attenuation, and transition region width. (FIR filters designed using the PM method are often called optimal FIR, Remez Exchange, Chebyshev approximation, or equi-ripple filters.) Many of the early descriptions of the PM design method included a graphical comparison of various lowpass FIR filter design methods similar to that redrawn in FIG. 26. In this figure, a given filter's normalized (to impulse response length N, and the sample rate 4) transition band width is plotted as a function of its minimum stopband attenuation.
(Passband peak-to-peak ripple values, measured in dB, are provided numerically within the figure.)
Because the normalized transition bandwidth measure D in FIG. 26 is roughly independent of N, this diagram is considered to be a valid performance comparison of the three FIR filter design methods. For a given pass band ripple and stopband attenuation, the PM-designed FIR filter could exhibit the most narrow transition bandwidth, thus the highest performance filter. The wide dissemination of FIG. 26 justifiably biased filter designers toward the PM design method. (During his discussion of FIG. 26, one author boldly declared "The smaller is D, the better is the filter."[10]) Given its flexibility, improved performance, and ease of use, the PM method quickly became the predominant FIR filter design technique. Consequently, in the 1970s FSF implementations lost favor to the point where they're rarely mentioned in today's DSP classrooms or textbooks.
However, from a computational workload standpoint, FIG. 26 is like modern swimwear: what it shows is important; what it does not show is vital. That design comparison does not account for those situations where both frequency sampling and PM filters meet the filter performance requirements, but the frequency sampling implementation is more computationally efficient. The following FIR filter design example illustrates this issue and shows why FSFs should be included in our bag of FIR filter design tools.
1.12 Type-IV FSF Example
Consider the design of a linear-phase lowpass FIR filter with the cutoff frequency being 0.05 times the sample rate f s . The stopband must begin at 0.095 times f„ maximum passband ripple is 0.3 dB peak to peak, and the minim urn stopband attenuation must be 65 dB. If we designed a six-section Type-IV FSF with N 62 and r = 0.99999, its frequency-domain performance satisfies our requirements and is the solid curve in FIG. 27(a).
FIG. 27 An N = 62, six-section Type-IV real FSF (solid) versus a 60-tap PM-de signed filter (dashed): (a) frequency magnitude response: (b) pass band response detail.
FIG. 28 Structure of the N . 62, six-section, lowpass Type-IV FSF with two transition region coefficients.
For this FSF, two transition region coefficients of I H(4) I = T1 = 0.589921, and I H(5) I = T2 0.104964 were used. Included in FIG. 27(a), the dashed curve, is the magnitude response of a PM-designed 60-tap nonrecursive FIR filter. Both filters meet the performance requirements and have linear phase.
The structure of the Type-IV FSF is provided in FIG. 28. A PM-designed filter implemented using a folded nonrecursive FIR structure, exploiting its impulse response symmetry to halve the number of multipliers, requires 30 multiplies and 59 adds per output sample. We see the computational savings of the Type-IV FSF which requires only 17 multiplies and 19 adds per output sample. (Note, the FSF's Mk) gain factors are all zero for 6 k 31.)
1.13 When to Use an FSF
FIG. 29 Computational workload comparison between even-N lowpass Type-IV FSFs and nonrecursive PM FIR filters: (a) only multiplications considered; (b) multiplications and additions considered. (No 1IN gain factor used.)
In this section we answer the burning question, When is it smarter (more computationally efficient) to use a Type-IV FSF instead of a I'M-designed FIR filter? The computational workload of a PM-designed FIR filter is directly related to the length of its time-domain impulse response, which in turn is inversely proportional to the filter transition bandwidth. The more narrow the transition bandwidth, the greater the non-recursive FIR filter's computational workload measured in arithmetic operations per output sample. On the other hand, the computational workload of an FSF is roughly proportional to its passband width. The more FSF sections needed for wider bandwidths and the more transition region coefficients used, the higher the FSF's computational workload.
So in comparing the computational workload of FSFs to PM-designed FIR filters, both transition bandwidth and passband width must be considered.
FIG. 29 provides a computational comparison between even-N Type-IV FSFs and I'M-designed nonrecursive lowpass FIR filters. The curves represent desired filter performance parameters where a Type-IV FSF and a PM designed filter have approximately equal computational workloads per output sample. (The bandwidth values in the figure axis are normalized to the sample rate, so for example a frequency value of 0.1 equals L/10.) If the desired FIR filter transition region width and passband width combination (a point) lies beneath the curves in FIG. -29, then a Type-IV FSF is computationally more efficient than a PM-designed filter. FIG. 29(a) is a comparison accounting only for multiply operations. For filter implementations where multiplies and adds require equal processor clock cycles, FIG. 29(6) provides the appropriate comparison. The solitary black dot in the figure indicates the comparison-curves location for the above FIG. 27 Type-IV FSF filter example. (A Type-IV FSF design example using the curves in FIG. 29 will be presented later.)
The assumptions made in creating FIG. 29 are that an even-N Type-IV FSF, damping factor r = 0.99999, and no 1/N gain scaling from FIG. 1(b) is used. The I'M filter implementation used in the comparison assumes a symmetrical impulse response, an M-tap folded structure requiring M/2 multiplies, and M-1 additions. The performance criteria levied on the PM filter are typical Type-IV FSF properties (when floating-point coefficients are used) given in Table 3.
The Type-IV resonators have a gain of N, so the subsequent gain of the FSF in FIG. 28 is N. For FSF implementations using floating point numbers, this gain may not be a major design issue. in filters implemented with fixed point numbers, the gain of N could cause overflow errors, and a gain reduction by a scaling factor of 1/N may be necessary. Occasionally, in the literature, a 1/N scaling factor is shown as a single multiply just prior to an FSF's comb filter. This scale factor implementation is likely to cause an intolerable increase in the input signal quantization noise. A more practical approach is to apply the 1/N scaling at the output of each FSF section, prior to the final summation, as indicated in FIG. 1(b). Thus every FSF resonator output is multiplied by a non-unity value, increasing the computational workload of the FSF. In this situation, the computational comparison between even-N Type-IV FSFs and PM filters becomes as shown in FIG. 30. Of course, if N is an integer power of two, some hardware implementations may enable resonator output 1/N scaling with hard-wired binary arithmetic right shifts to avoid explicit multiply operations. In this situation, the computational workload comparison in FIG. 29 applies.
Table 3 Typical Even-N Type-IV FSF Properties
FIG. 30 Computational workload comparison between even-N lowpass Type-IV
FSFs, with resonator output 1 /N scaling included, and non-recursive PM
FIR filters: (a) only multiplications considered; (b) multiplications and
additions considered.
As of this writing, programmable-DSP chips typically cannot take ad vantage of the folded FIR filter structure assumed in the creation of FIGs 29 and 30. In this case, an M-tap direct convolution FIR filter has the disadvantage that it must perform the full M multiplies per output sample.
However, DSP chips have the advantage of zero-overhead looping and single clock-cycle multiply and accumulate (MAC) capabilities making them more efficient for direct convolution FIR filtering than for filtering using the recursive FSF structures. Thus, a DSP chip implementation's disadvantage of more necessary computations and its advantage of faster execution of those computations roughly cancel each other. With those thoughts in mind, we're safe to use FIGs 29 and 30 as guides in deciding whether to use a Type-IV FSF or a PM-designed FIR filter in a programmable DSP chip filtering application.
Finally we conclude, from the last two figures, that Type-IV FSFs are more computationally efficient than 'PM-designed HR filters in lowpass applications where the passband is less than approximately f,/5 and the transition bandwidth is less than roughly L/8.
FIG. 31 Typical Type-IV lowpass FSF stopband attenuation performance
as a function of transition bandwidth.
1.14 Designing FSFs
The design of a practical Type-IV FSF comprises three stages: (1) determine if an FSF can meet the desired filter performance requirements, (2) determine if a candidate FSF is more, or less, computationally efficient than an equivalent PM-designed filter, and (3) design the FSF and verify its performance. To aid in the first stage of the design, FIG. 31 shows the typical minimum stop band attenuation of Type-IV FSFs, as a function of transition bandwidth, for various numbers of transition region coefficients. (Various values for N, and typical passband ripple performance, are given within FIG. 31 as general reference parameters.) In designing an FSF, we find the value N to be a function of the desired filter transition bandwidth. The number of FSF sections required is deter mined by both N and the desired filter bandwidth. Specifically, given a linear phase FIR filter's desired passband width, passband ripple, transition bandwidth, and minimum stopband attenuation, the design of a linear-phase lowpass Type-IV FSF proceeds as follows:
1. Using FIG. 31, determine which performance band in the figure satisfies the desired minimum stopband attenuation. This step defines the number of transition coefficients necessary to meet stopband attenuation requirements.
2. Ensure that your desired transition bandwidth value resides within the chosen shaded band. (If the transition bandwidth value lies to the right of a shaded band, a PM-designed filter will be more computationally efficient than a Type-IV FSF and the FSF design proceeds no further.)
3. Determine if the typical passband ripple performance, provided in FIG. 31, for the candidate shaded band is acceptable. If so, a Type-IV FSF can meet the desired lowpass filter performance requirements. If not, a PM design should be investigated.
4. Based on arithmetic implementation priorities, determine the appropriate computational workload comparison chart to be used from FIG. 29 or FIG. 30 in determining if an FSF is more efficient than a PM designed nonrecursive filter.
5. Using the desired filter's transition bandwidth and passband width as coordinates of a point on the selected computational workload comparison chart, determine if that point lies beneath the appropriate curve. If so, an FSF can meet the filter performance requirements with fewer computations per filter output sample than a PM-designed filter. (If the transition bandwidth/passband point lies above the appropriate curve, a PM design should be investigated and the FSF design proceeds no further.)
6. Assuming the designer has reached this step of the evaluation process, the design of a Type-1V FSF proceeds by selecting the filter order N. The value of N depends on the desired transition bandwidth and the number of transition coefficients from step 1 and, when the transition bandwidth is normalized to f„ can be estimated using
(eqn. 29)
7. The required number of unity-gain FSF sections, integer M, is roughly proportional to the desired normalized double-sided passband width divided by the FSF's frequency resolution (fs /N), and is estimated using 2N(passband width)
(eqn. 30)
8. Given the initial integer values for N and M, find the appropriate optimized transition coefficient gain values from the compiled tables in Appendix H. If the tables do not contain optimized coefficients for the given N and M values, the designer may calculate approximate coefficients by linear interpolation of the tabulated values. Alternatively, an optimization software program may be used to find optimized transition coefficients.
9. Using the values for N, M, and the optimized transition coefficients, determine the interpolated (actual) frequency response of the filter as a M (eqn. 30) function those filter parameters. This frequency response can be obtained by evaluating Eq. (eqn. 24). More conveniently, the frequency response can be determined with a commercial signal processing software package to perform the DFT of the FSF's impulse response sequence, or by using the transfer function coefficients in Eq. (eqn. 23).
10. Next the fun begins, as the values for N and M are modified slightly, and steps 8 and 9 are repeated, as the design process converges to a mini mum value of M to minimize the computational workload, and optimized transition coefficients maximizing stopband attenuation.
11. When optimized filter parameters are obtained, they are used in an Type-IV FSF implementation, as in FIG. 28.
12. The final FSF design step is to sit back and enjoy a job well done.
The Type-IV FSF example presented in FIGs 27 and 7-28 provides an illustration of the above steps 6 and 7. The initial design estimates for N and M are
[…]
Repeated iterations of steps 8-11 converged to the parameters of N = 62 and M 6 that satisfy the desired filter performance specifications.
1.15 FSF Summary
We've introduced the structure, performance, and design of frequency sampling FIR filters. Special emphasis was given to the practical issues of phase linearity, stability, and computational workload of these filters. In addition, we presented a detailed comparison between the high-performance Type-IV FSF and its non-recursive FIR equivalent. Performance curves were presented to help the designer choose between a Type-IV FSF and a Parks McClellan-designed FIR filter for a given narrowband linear-phase filtering application. We found that:
• Type-IV FSFs are more computationally efficient, for certain stopband attenuation levels, than Parks-McClellan-designed non-recursive FIR filters in low pass (or highpass) applications where the passband is less than f,/5 and the transition bandwidth is less than fs /8. (See FIGs 29 and 7-30.)
• FSFs are modular. Their components (sections) are computationally identical and well understood;
• tables of optimum transition region coefficients, used to improve Type-IV FSF performance, can be generated; and
• although FSFs use recursive structures, they can be designed to be guaranteed stable, and have linear phase.
2. INTERPOLATED LOWPASS FIR FILTERS
In this section we cover another class of digital filters called interpolated FIR filters, used to build narrowband lowpass FIR filters that can be more computationally efficient than traditional Parks-McClellan-designed FIR filters. Interpolated FIR fillers can reduce traditional narrowband lowpass FIR filter computational workloads by more than 80 percent. In their description, we'll introduce interpolated FIR filters with a simple example, discuss how filter parameter selection is made, provide filter performance curves, and go through a simple lowpass filter design example showing their computational savings over traditional FIR filters.
Interpolated FIR (IFIR) filters are based upon the behavior of an N-tap non-recursive linear-phase FIR filter when each of its single-unit delays are re placed with M-unit delays, with the expansion factor M being an integer, as shown in FIG. 32(a). lithe h p(k) impulse response of a 9-tap FIR filter is that shown in FIG. 32(b), the impulse response of an expanded FIR filter, where for example M = 3, is the h, h (k) in FIG. 32(c). The M-unit delays result in the zero-valued samples, the white dots, in the hsh (k) impulse response.
Our variable k is merely an integer time-domain index' where 0 k 5_ N-1. To define our terminology, we'll call the original FIR filter the prototype filter- that's why we used the subscript "p" in hp(k)-and we'll call the filter with expanded delays the shaping sub-filter. Soon we'll see why this terminology is sensible.
FIG. 32 Filter relationships: (a) shaping FIR filter with M-unit delays
between the taps; (b) impulse response of a prototype FIR filter: (c) impulse
response of an expanded-delay shaping FIR filter with M = 3.
We can express a prototype FIR filter's z-domain transfer function as
(eqn. 31)
where N is the length of h1,. The transfer function of a general shaping FIR filter, with z in Eq. (eqn. 31) replaced with zTM, is
(eqn. 32)
If the number of coefficients in the prototype filter is Np, the shaping filter has N nonzero coefficients and an expanded impulse response length of
(eqn. 33)
Later we'll see how Ksh has an important effect on the implementation of IFIR filters.
The frequency-domain effect of those M-unit delays is shown in FIG. 33. As we should expect, an M-fold expansion of the time-domain filter impulse response causes an M-fold compression (and repetition) of the frequency-domain I Hp (f) I magnitude response as in FIG. 33(b). The frequency axis of these curves is normalized to 4, with fs being the input signal sample rate. For example, the normalized frequency feass is equivalent to a cyclic frequency of fpassfs Hz. Those repetitive passbands in I lish (f) I centered about integer multiples of 1/M (fs /M Hz) are called images, and on them we now focus our attention.
FIG. 33 IFIR filter magnitudes responses: (a) the prototype fitter;
(b) shaping subfilter: (c) image-reject subfilter; (d) final IFIR filter,
If we follow the shaping subfilter with a lowpass image-reject subfilter, FIG. 33(c), whose task is to attenuate the image passbands, we can realize a multistage filter whose frequency response is shown in FIG. 33(d). The resultant I Hifir (f) I frequency magnitude response is, of course, the product
(eqn. 34)
The structure of the cascaded subfilters is the so-called IFIR filter shown in FIG. 34(a), with its interpolated impulse response given in FIG. 34(b). If the original desired lowpass filter's passband width is f 1 its stop band begins at f 0. and the transition region width is /*trims = f st „ - f pa „, then the prototype subfilter's normalized frequency parameters are defined as
(eqn. 35), (eqn. 35'), (eqn. 35")
(eqn. 36), (eqn. 36')
FIG. 34 Lowpass interpolated FIR filter: (a) cascade structure; (b)
resultant impulse response.
The stopband attenuations of the prototype filter and image-reject sub filter are identical and set equal to the desired IFIR filter stopband attenuation. The word "interpolated" in the acronym IFIR is used because the image-reject subfilter interpolates the zero-valued samples in the shaping subfilter's h sh (k) impulse response making the overall IFIR filter's impulse response, hifir (k) in FIG. 34(b), nearly equivalent to a traditional Ksh-length nonrecursive FIR filter. (Did you notice hifir (k) is an interpolated version of the h (k) in FIG. 32(b)?) Some authors emphasize this attribute by referring to the image-reject subfilter as an interpolator. The sample rate remains un changed within an IFIR filter, so no actual signal interpolation takes place.
To give you an incentive to continue reading, the following example shows the terrific computational advantage of using IFIR filters. Consider the design of a desired linear-phase FIR filter whose normalized passband width is f pass = 0.1, its passband ripple is 0.1 dB, the transition region width is Aran5 = 0.02, and the stopband attenuation is 60 dB. (The passband ripple is a peak-peak specification measured in dB.) With an expansion factor of M = 3, the I Hio (f) I frequency magnitude response of the prototype filter is shown in FIG. 35(a). The normalized frequency axis for these curves is such that a value of 0.5 on the abscissa represents the cyclic frequency 4/2 Hz, half the sample rate. The frequency response of the shaping subfilter, for M = 3, is pro vided in FIG. 35(b), with an image passband centered about (1 1M) Hz.
FIG. 35 Example lowpass IFIR filter magnitudes responses: (a) the prototype
filter; (b) shaping subfilter; (c) image-reject subfilter; (d) final IFIR
filter.
The response of the image-reject subfilter is the solid curve in FIG. 35(c), with the response of the overall IFIR filter provided in FIG. 35(d). Satisfying the original desired filter specifications in FIG. 35(d)
would require a traditional single-stage FIR filter with Ntfir = 137 taps, where the "tfir" subscript means traditional FIR. In our IFIR filter, the shaping and the image-reject subfilters require N p = 45 and Nir = 25 taps respectively, for a • - N - N.
% computation reduction = 100 N
(eqn. 37)
total of Nifir = 70 taps. We can define the percent reduction in computational workload of an [FIR filter, over a traditional FIR filter, as As such, the above example IFIR filter has achieved a computational work load reduction, over a traditional FIR filter, of
(eqn. 37')
FIG. 35 shows how the transition region width (the shape) of Hifir (DI is determined by the transition region width of I FI,h (f) I, and this justifies the decision to call h(k) the "shaping" subfilter.
2.1 Choosing the Optimum Expansion Factor M
The expansion factor M deserves our attention because it can have a pro found effect on the computational efficiency of IFIR filters. To show this, had we used M = 2 in our FIG. -35 example we would have realized an IFIR filter described by the M = 2 column in Table 4, in which case the computation reduction over a conventional FIR filter is 43%. With M 2, a reduced amount of frequency-domain compression occurred in Hsh(f), which man dated more taps in hsh(k) than needed in the M = 3 case.
Now had M = 4 been used, the computation reduction would only be 8% as shown in Table 4. This is because the H sh ( f) passband images would be so close together that a high-performance (increased number of taps)
image-reject subfilter would be required. As so often happens in signal processing designs, there is a trade-off to be made. We would like to use a large value for M to compress the sh( fY s transition region width as much as possible, but a large M reduces the transition region width of the image-reject sub filter which increases the number of taps in hir(k) and its computational workload. In our FIG. 35 IFIR filter example, an expansion factor of M = 3 is optimum because it yields the greatest computation reduction over a traditional single-stage nonrecursive FIR filter.
As indicated in FIG. 33(b), the maximum M is the largest integer satisfying 1/M-f 0 stop ensuring no passband image overlap. This yields stp ' an upper bound on M of max=
(eqn. 38)
where LxJ indicates truncation of x to art integer. Thus the acceptable expansion factors are integers in the range 2 M M... Evaluating Eq. (eqn. 38) for the FIG. 35 IFIR filter example yields 1 Mmax 2(0.1 + 0.02) justifying the range of M used in Table 4.
(eqn. 38')
Table 4 IFIR Filter Computation Reduction vs. M
2.2 Estimating the Number of FIR Filter Taps
To estimate the computation reduction of IFIR filters, an algorithm is needed to compute the number of taps, N, in a traditional nonrecursive FIR filter. Several authors have proposed empirical relationships for estimating N for traditional nonrecursive FIR filters based on passband ripple, stopband attenuation, and transition region width. A particularly simple expression for N, giving results consistent with other estimates for passband ripple values near 0.1 dB, is
(eqn. 39)
where Atten is the stopband attenuation measured in dB, ancifp.,„ and f, _ top are the normalized frequencies in FIG. 33(d)[171. Likewise, CE-;'e number of taps in t pe and image-reject subfilters can be estimated using
(eqn. 39')
(eqn. 39")
2.3 Modeling IFIR Filter Performance
As it turns out, IFIR filter computational workload reduction depends on the expansion factor M, the passband width, and transition region width of the desired IFIR filter. To show this, we substitute the expressions from Eq. (eqn. 39)
into Eq. (eqn. 37) and write. (eqn. 40)
Equation (eqn. 40) is plotted in FIG. 36(a), for a passband width of one tenth the sample rate (f S = 0.1) showing the percent computation reduction p 1G afforded by an 1FIR filter: vs. transition region width for expansion factors of 2, 3, and 4. Focusing on FIG. 36(a), we see when the transition region width is large (say, f, ) , = 0.07). The IFIR filter's passband plus transition region width is so wide, relative to the passband width, that only an expansion factor of M = 2 will avoid passband image overlap.
FIG. 36 IFIR filter performance versus transition region width for
fpass = 0.1: (a) percent computation reduction; (b) optimum expansion factors.
FIG. 37 IFIR filter performance vs. transition region width for fpass
= 0.05: (a) percent computation reduction; (b) optimum expansion factors.
At smaller transition region widths, expansion factors of 3 and 4 are possible. For example, over the transition region width range of roughly 0.005 to 0.028, an expansion factor of M = 3 provides greater computation reduction than using M = 2. The optimum (greatest percent computation reduction) expansion factor, as a function of transition region width, is shown in FIG. 36(b). The black dots in FIG. 36 represent the FIG. 35 IFIR filter ex ample with a transition region width of ftr„,,, = 0.02.
To see how the percent computation reduction of IFIR filters vary with the desired passband width, FIG. 37 shows IFIR filter performance when the desired passband width is 5% of the sample rate (f 0.05). The numbers on the curves in FIG. 37(a) are the expansion factors.
The optimum M values vs. transition region width are presented in FIG. 37(b). The curves in FIG. 37(a) illustrate, as the first ratio within the brackets of Eq. (eqn. 40) indicates, that when the transition region width approaches zero, the percent computation reduction approaches 100(M-1)/M. We continue describing the efficiency of IFIR filters by considering the bold curve in FIG. 38(a), which is the maximum percent computation reduction as a function of transition region width for the f , 0.1 IFIR filter described for FIG. 36(a). The bold curve is plotted or 'a logarithmic frequency axis, to show maximum percent computation reduction over a wider transition region width range, in FIG. 38(b).
FIG. 38 Maximum percent computation reduction versus transition region
width for fposs = 0.1: (a) plotted on a linear axis: (b) using a logarithmic
axis.
FIG. 39 IFIR filter performance versus transition region width for
various pass band widths: (a) maximum percent computation reduction; (b)
optimum expansion factors.
Next, we duplicate the FIG. 38(b) curve in FIG. 39(a), and include the maximum percent computation reduction vs. transition region width curves for five other IFIR filters having different passband widths showing how significant computation reduction can be achieved by using lowpass IFIR filters. The optimum expansion factors, used to compute the curves in FIG. 39(a), are shown in FIG. 39(b). To keep the lower portion of FIG. 39(b) from being too cluttered, curve fitting was performed to convert the stairstep curves to smooth curves. Shortly we'll see how the curves in FIG. 39(h) are used in an IFIR filter design example.
2.4 IFIR Filter Implementation Issues
The computation reduction of IFIR filters is based on the assumption that they are implemented as two separate subfilters, as in FIG. 34. We have resisted the temptation to combine the two subfilters into a single filter whose coefficients are the convolution of the subfilters' impulse responses. Such a maneuver would eliminate the zero-valued coefficients of the shaping subfilter, and we'd lose all computation reduction.
The curves in FIG. 39(h) indicate an important implementation issue when using IFIR filters. With decreasing IFIR filter passband width, larger expansion factors, M, can be used. When using programmable DSP chips, larger values of M require that a larger block of hardware data memory, in the form of a circular buffer, be allocated to hold a sufficient number of input x(n) samples for the shaping subfilter. The size of this data memory must be equal to Ksh, as indicated in Eq. (eqn. 33). Some authors refer to this data memory allocation requirement, to accommodate ail the stuffed zeros in the h1.1(k) impulse response, as a disadvantage of IFIR filters. This is a mis leading viewpoint because, as it turns out, the Ksh length of h,h (k) is only few percent larger than the length of the impulse response of a traditional FIR filter having the same performance as an [FIR filter. So, from a data storage standpoint, the price we pay to use IFIR filters is a slight increase in the memory of size to accommodate Ksh, plus the data memory of size Kir needed for the image-reject subfilter. In practice, for narrowband lowpass IFIR filters, Kir is typically less than 10% of K611 . The Ksh-sized data memory allocation, for the shaping subfilter, is not necessary in field programmable gate array (FPGA) [FIR filter implementations because FPGA area is not a strong function of the expansion factor M118].
When implementing an [FIR filter with a programmable DSP chip, the filter's computation reduction gain can only be realized if the chip's architecture enables zero-overhead looping through the circular data memory using an increment equal to the expansion factor M. That looping capability ensures that only the nonzero-valued coefficients of h811 (k) are used in the shaping sub filter computations.
In practice, the shaping and image-reject sub-filters should be implemented with a folded non-recursive FIR structure, exploiting their impulse response symmetry, to reduce the number of necessary multiplications by a factor of two. Using a folded structure does not alter the performance curves provided in FIG. 39. Regarding an IFIR filter's implementation in fixed-point hardware, its sensitivity to coefficient quantization errors is no greater than the errors exhibited by traditional FIR filters.
2.5 IFIR Filter Design Example
The design of practical lowpass IFIR filters is straightforward, and comprises four steps:
1. Define the desired lowpass filter performance requirements.
2. Determine a candidate value for the expansion factor M.
3. Design and evaluate the shaping and image-reject subfilters.
4. Investigate IFIR performance for alternate expansion factors near the initial M value.
As a design example, refer to FIG. 33(d) and assume we want to build a lowpass [FIR filter with f pass = 0.02, a peak-to-peak passband ripple of 0.5 dB, a transition region bandwidth of ftra ,„ = 0.01 (thus f= 0.03), and stop 50 dB of stopband attenuation. First, we find the ftrans = 0.01 point on the abscissa of FIG. 39(b) and follow it up to the point where it intersects the 0.02 curve. This intersection indicates we should start our design with an expansion factor of M 7. (The same intersection point in FIG. 39(a) suggests we can achieve a computational workload reduction of roughly 80%.) With M = 7, and applying Eq. (eqn. 35), we use our favorite traditional FIR filter design software to design a linear-phase prototype FIR filter with the following parameters: fp_ pass = M(0.02) = 0.14, passband ripple = (0.5)/2 dB = 0.25 dB, fp_stop = M(0.03) = 0.21, and stopband attenuation = 50 dB.
(Notice how we used our cascaded filters' passband ripple rule of thumb from Section 6.8.1 to specify the prototype filter's passband ripple to be half our final desired ripple. We'll do the same for the image-reject subfilter.) Such a prototype FIR filter will have N = 33 taps and, from Eq. (eqn. 33), when expanded by M = 7 the shaping subfilter will have an impulse response length of Km, = 225 samples.
Next, using Eq. (eqn. 36) we design a image-reject subfilter having the following parameters: Ar-pass –fpass = 0.02, passband ripple = (0.5) 12 dB = 0.25 dB, Ar-stop 1/M -fstop = 1/7-0.03 -= 0.113, and...
This image-reject subfilter will have Ni , = 27 taps, and when cascaded with the shaping subfilter will yield an IFIR filter requiring 60 multiplications per filter output sample. The frequency response of the IFIR filter is shown in Fig ure 7-40(a), with passband response detail provided in FIG. 40(b). A traditional FIR filter satisfying our design example specifications would require approximately Ntfi r = 240 taps. Because the IFIR filter requires only 60 multiplications per output sample, using Eq. (eqn. 37), we have realized a computational workload reduction of 75%. The final IFIR filter design step is to sit back and enjoy a job well done.
Further modeling of our design example for alternate expansion factors yields the IFIR filter performance results in Table 5. There we see how the M expansion factors of 5 through 8 provide very similar computational reductions and Ksh -sized data storage requirements for the shaping subfilter.
IFIR filters are suitable whenever narrowband lowpass linear-phase filtering is required, for example the filtering prior to decimation for narrow band channel selection within wireless communications receivers, or in digital television. IFIR filters are essential components in sharp-transition wideband passband response detail.
frequency-response masking FIR filters. In addition, IFIR filters can also he employed in narrowband two-dimensional filtering applications.
Additional, and more complicated, IFIR design methods have been de scribed in the literature. Improved computational workload reduction, on the order of 30-40% beyond that presented here, has been reported using an intricate design scheme when the FIG. .34 image-reject subfilter is replaced with multiple stages of filtering.
FIG. 40 IIR filter design example magnitudes responses: (a) full response;
(b) passband response detail.
Table 5 Design Example Computation Reduction vs. M
To conclude our linear-phase narrowband IFIR filter material, we reiterate: they can achieve significant computational workload reduction (as large as 90%) relative to traditional non recursive FIR filters, at the cost of less than a 10% increase in hardware data memory requirements. Happily, IFIR implementation is a straightforward cascade of filters designed using readily avail able traditional FIR filter design software.
REFERENCES
[1] Rabiner, L., et al, "An Approach to the Approximation Problem for Non-recursive Digital Filters," IEEE Trans. Audio Electroacoust., Vol. AU-18, June 1970, pp. 83-106.
[2] Proakis. J. and Manolakis, D. Digital Signal Processing-Principles, Algorithms, and Applications, Third Edition, Prentice Hall, Upper Saddle River, New Jersey, 1996, pp. 506-507.
[3] Taylor, F. and Mellott, J. Hands-On Digital Signal Processing, McGraw-Hill, New York, 1998, pp. 325-331.
[4] Rader, C. and Gold, B. "Digital Filter Design Techniques in the Frequency Domain," Proceedings of the IEEE, Vol. 55, February 1967, pp. 149-171.
[5] Rabiner, L. and Schafer, R. "Recursive and Nonrecursive Realizations of Digital Filters De signed by Frequency Sampling Techniques," IEEE Trans. Audio Electroacoust., Vol. AU-19, September 1971, pp. 200-207.
[6] Gold, B. and Jordan, K. "A Direct Search Procedure for Designing Finite Duration Impulse Response Filters," IEEE Trans. Audio Electroacoust., Vol. AU-17, March 1969, pp. 33-36.
[7] Rabiner, L. and Gold, B. Theory and Application of Digital Signal Processing, Prentice Hall, Upper Saddle River, New Jersey, 1975, pp. 105-112.
[8] Roraba ugh, C. DSP Primer, McGraw-Hill, New York, 1999.
[9] Parks, T. and McClellan, J. "A Program for the Design of Linear Phase Finite Impulse Response Digital Filters," IEEE Trans. Audio Electroacoust., Vol. AU-20, August 1972, pp. 195-199.
[10] Herrmann, O. "Design of Non-recursive Digital Filters with Linear Phase," Electron. Lett., Vol. 6, May 28, 1970, pp. 328-329.
[11] Rabiner, L. "Techniques for Designing Finite-Duration-Impulse-Response Digital Filters," IEEE Trans. on Communication Technology, Vol. COM-19, April 1971, pp. 188-195.
[12] Ingle, V. and Proakis, J. Digital Signal Processing Using MATLAB, Brooks/Cole Publishing, Pacific Grove, CA, 2000, pp. 202-208.
[13] Mitra, S. K., et al, "Interpolated Finite Impulse Response Filters," IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-32, June 1984, pp. 563-570.
[14] Vaidyanathan, P. Multirate Systems and Filter Banks, Prentice Hall, Englewood Cliffs, New Jersey, 1993.
[15] Crochiere, R. and Rabiner, L. "Interpolation and Decimation of Digital Signals-A Tutorial Review," Proceedings of the IEEE, Vol. 69, No. 3, March 1981, pp. 300-331.
[16] Kaiser, J. "Non-recursive Digital Filter Design Using lo-sinh Window Function," Proc. 7974 IEEE Int. Symp. Circuits Systems, April 1974, pp. 20-23.
17. Harris, F. "Digital Signal Processing for Digital Modems," DSP World Spring Design Conference, Santa Clara, CA, April 1999.
[18] Dick, C. "Implementing Area Optimized Narrow-band FIR Filters Using Xilinx FPGAs," SP1E International Symposium on Voice, Video and Data Communications, Boston, Massachusetts, pp. 227-238, Nov. 1998.
[19] Lim, Y. "Frequency-Response Masking Approach for the Synthesis of Sharp Linear Phase Digital Filters," IEEE Trans. Circuits Syst., Vol. 33, April 1986, pp. 357-364.
[20] Yang, R., et al, "A New Structure of Sharp Transition FIR Filters Using Frequency Response Masking," IEEE Trans. Circuits Syst., Vol. 35, August 1988, pp. 955-966.
[21] Saramaki, T., et al, "Design of Computationally Efficient Interpolated FIR Filters," IEEE Trans. Circuits Syst., Vol. 35, January 1988, pp. 70-88.
Related Articles -- Top of Page -- Home