Design Filter Using Iir Specific Cutoffs Etc

Infinite Impulse Response Filter

Wavelets in Chemistry

Mohamed N. Nounou , Bhavik R. Bakshi , in Data Handling in Science and Technology, 2000

IIR filtering

Infinite impulse response (IIR) filters are linear low pass filters which can be represented as

(9) ${\hat{\text{x}}}_{\text{t}}=\sum _{\text{i}=0}^{\infty }{\text{b}}_{\text{i}}{\text{x}}_{\text{t}-\text{i}}$

and also satisfy the condition shown in Eq. (7). The time horizon of the IIR filter is infinite, and therefore any filtered data point is represented as a weighted sum of all previous measurements. A more detailed discussion of FIR and IIR filters is presented in [20]. Exponentially weighted moving average (EWMA) is a popular IIR filter. An EWMA filter smoothes a measured data point by exponentially averaging that particular point with all previous measurements. Similar to the mean filter, the EWMA filter is a low pass filter that eliminates high frequency components in the measured signal. It is implemented recursively by taking a weighted average of the last measured data point and the previous smoothed one with their corresponding weights, αand (1 −α), respectively as,

(10) ${\hat{\text{x}}}_{\text{t}}=\alpha {\text{x}}_{\text{t}}+\left(1-\alpha \right){\hat{\text{x}}}_{\text{t}-1}$

The parameter, α, is an adjustable smoothing parameter lying between zero and unity, which defines the cut-off frequency above which features are eliminated. The weightings of the EWMA filter are shown in Fig. 3(b), which shows that the EWMA filter coefficients drop exponentially depending on the smoothing parameter, α, giving more importance to the more recent measurements. Higher values of α. drive the filter coefficients to drop faster which increases the cut-off frequency to keep higher frequency features, while smaller value of α slows the coefficients' exponential drop which lowers the cut-off frequency to eliminate features at lower frequencies.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0922348700800301

Circular Buffering

Nasser Kehtarnavaz , in Real-Time Digital Signal Processing, 2005

L5.1 Design of IIR Filter

A seventh-order bandpass IIR filter is used to act as the unknown system. The adaptive FIR is designed to adapt to the response of the IIR system. Considering a sampling frequency of 8 kHz, let the IIR filter have a passband from π/3 to 2π/3 (radians), with a stopband attenuation of 20dB. The design of the filter can be easily achieved with the MATLAB function 'yulewalk' [2]. The following MATLAB code may be used to obtain the coefficients of the filter:

It can be verified that the filter is working by deploying a simple composite signal. Using the MATLAB function 'filter', verify the design by observing that the frequency components of the composite signal falling in the stopband are removed. (See Figure 8-5 and Table 8-1.)

Figure 8-5. IIR filter response.

Table 8-1. IIR filter coefficients.

A's	B's
1.0000	0.1191
0.0179	0.0123
0.9409	−0.1813
0.0104	−0.0251
0.6601	0.1815
0.0342	0.0307
0.1129	−0.1194
0.0058	−0.0178

Note: Do not confuse A&B coefficients with the CPU A&B registers!

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780750678308500109

From Algorithms to Architectures

In Top-Down Digital VLSI Design, 2015

3.7 Equivalence transforms for recursive computations

A computation is said to be timewise recursive — or recursive for short — if it somehow depends on an earlier outcome from that very computation itself, a circumstance that gets reflected in the DDG by the presence of a feedback loop. Yet, recall that circular paths of weight zero have been disallowed to exclude the risk of race conditions. Put differently, circular paths do exist but each of them includes at least one latency register.

This section examines equivalence transforms that apply specifically to recursive computations. We will find that such transforms are not universal. This is why we address linear time-invariant, linear time-variant, and nonlinear computations separately.

3.7.1 The feedback bottleneck

Consider a linear time-invariant first-order recursive function

(3.47) $y(k)=ay(k-\text{1})+x(k)$

which, in the z domain, corresponds to transfer function

(3.48) $H(z)=\frac{Y(z)}{X(z)}=\frac{1}{1-a{z}^{-1}}$

The corresponding DDG is shown in fig.3.34a. Many examples for this and similar types of computations are found in IIR filters, DPCM ⁵⁴ data encoders, servo loops, etc.

Figure 3.34. Linear time-invariant first-order feedback loop. DDG (a) and isomorphic architecture with longest path highlighted (b).

Recursion demands that the result from the actual computation cycle be available no later than the next input sample. The longest path defined by all computations that are part of the loop must, therefore, not exceed one sampling interval. In the occurrence

(3.49) ${\displaystyle \sum _{loop}t=t_{reg}+t_{\ast }+t_{+}=t_{lp}\le T_{cp}}$

As long as this iteration bound is satisfied by the isomorphic architecture of fig.3.34b implemented using some available and affordable technology, there is no out-of-the-ordinary design problem. As an example, we could easily provide a sustained computation rate of 100 MHz if the three delay figures for the actual word width were of 0.5 ns, 5 ns, and 2 ns respectively.

When in search of some higher throughput, say 200 MHz, recursiveness becomes a real bottleneck since there is no obvious way to make use of replication or to insert pipeline registers without altering the overall transfer function and input-to-output mapping. Retiming does not help either as the weight along a circular path is always preserved. So the problem is

"How to allow more time for those computations that are part of the recursion loop?"

3.7.2 Unfolding of first-order loops

The key idea is to relax the timing constraint by inserting additional latency registers into the feedback loop while preserving the original transfer function. In other words, a tentative solution for a first-order loop must look like

(3.50) $H(z)=\frac{Y(z)}{X(z)}=\frac{N(z)}{1-a^p{z}^{-p}}$

where an unknown expression N (z) is here to compensate for the changes that are due to the new denominator 1 − a ^p z ^−p . Recalling the sum of geometric series we easily establish N(z) as

(3.51) $N(z)=\frac{1-a^p{z}^{-p}}{1-a{z}^{-1}}={\displaystyle \sum _{n=0}^{p-1}{a}^n{z}^{-n}}$

The new transfer function can then be completed to become

(3.52) $H(z)=\frac{{\displaystyle {\sum }_{n=0}^{p-1}{a}^n{z}^{-1}}}{1-a^p{z}^{-p}}$

and the new recursion in the time domain follows as

(3.53) $y(k)=a^{p}y(k-p)+{\displaystyle \sum _{n=0}^{p-1}{a}^{n}x(k-n)}$

The modified equations correspond to a cascade of two sections. A first section, represented by the numerator of (3.52), is a DDG that includes feedforward branches only. This section is amenable to pipelining as discussed in section 3.4.3. The denominator stands for the second section, a simple feedback loop which has been widened to include p unit delays rather than one as in (3.47).

Using retiming, the corresponding latency registers can be redistributed into the combinational logic for computing the loop operations such as to serve as pipeline registers there. Neglecting, for a moment, the limitations to pipelining found in section 3.4.3, throughput can in fact be multiplied by an arbitrary positive integer p through this unfolding technique, several variations of which are discussed in [74].

Unless p is prime, it is further possible to simplify the DDG — and hence the implementing circuit —by factoring the numerator into a product of simpler terms. Particularly elegant and efficient solutions exist when p is an integer power of 2 because of the lemma

(3.54) ${\displaystyle \sum _{n=0}^{p-1}{a}^n{z}^{-n}={\displaystyle \prod _{m=0}^{{\log }_{2}p-1}(a^{2m}{z}^{-2m}+1)}}p=2,4,8,16,\mathrm{...}$

The feedforward section can then be realized by cascading log₂ p subsections each of which consists of just one multiplication and one addition.

Example

The linear time-invariant first-order recursive function (3.47) takes on the following form after unfolding by a factor of p = 4

(3.55) $y(k)=a^4(k-4)+a^{3}x(k-3)+a^{2}x(k-2)+ax(k-1)+x(k)$

which corresponds to transfer function

(3.56) $H(z)=\frac{1+a{z}^{-1}+a^2{z}^{-2}+z^3{z}^{-3}}{1-a^4{z}^{-4}}$

Making use of (3.54) the numerator can be factorized into such as to obtain

(3.57) $H(z)=\frac{(1+a{z}^{-1})(1+a^2{z}^{-2})}{1-a^4{z}^{-4}}$

The DDG corresponding to this equation is shown in figure 3.35a. Note that the configuration is not only simple but also highly regular. Further improvements are obtained from pipelining in conjunction with retiming and shimming where necessary. The final architecture, shown in fig.3.35b, is equivalent except for latency. Incidentally, also note that threefold instantiation of one pipelined multiply-add building block favors further optimizations at lower levels of detail.

Figure 3.35. Linear time-invariant first-order feedback loop. DDG after unfolding by a factor of p = 4 (a) and high-performance architecture with pipelining and retiming on top (b).

Performance and cost analysis

In the occurrence of optimally efficient configurations, where p is an integer power of 2, a lower bound for total circuit size can be given as follows

(3.58) $A(p)\ge ({\log }_{2}p+1)A_f+p({\log }_{2}p+1)A_{reg}$

In the above example, we count three times the original arithmetic logic plus 14 extra (nonfunctional) registers. In return for an almost fourfold throughput, this is finally not too bad.

Analogously to what was found for pipelining in section 3.4.3, the speedup of loop unfolding tends to diminish while the difficulties of balancing delays within the combinational logic tend to grow when unfolding is pushed too far, p » 1.

A hidden cost factor associated with loop unfolding is due to finite precision arithmetics. For the sake of economy, datapaths are designed to do with minimum acceptable word widths, which implies that output and intermediate results get rounded or truncated somewhere in the process. In the above example, for instance, addition would typically handle only part of the bits that emanate from multiplication. Now, the larger number of roundoff operations that participate in the unfolded loop with respect to the initial configuration leads to more quantization errors, a handicap which must be offset by using somewhat wider data words [75].

Loop unfolding greatly inflates the amount of energy dissipated in the processing of one data item because of the extra feedforward computations and the many latency registers added to the unfolded circuitry. More on the positive side, the shortened longest path may bring many recursive computations into the reach of a relatively slow but power-efficient technology or may allow for a lower supply voltage.

The idea of loop unfolding demonstrated on a linear time-invariant first-order recursion can be extended into various directions, and this is the subject of the forthcoming three subsections.

3.7.3 Higher-order loops

Instead of unfolding loops of arbitrary order directly, we make use of a common technique from digital filter design that consists in factoring a higher-order transfer function into a product of second- and first-order terms. The resulting DDG takes the form of cascaded second- and first-order sections. High-speed IIR filters of arbitrary order can be constructed by pipelining the cascade so obtained. As an added benefit, cascade structures are known to be less sensitive to quantization of coefficients and signals than direct forms. We will, therefore, limit the discussion to second-order recursive functions here

(3.59) $y(k)=ay(k-\text{1})+by(k-\text{2})+x(k)$

which correspond to the DDG depicted in fig.3.36. The equivalent in the z domain is

Figure 3.36. Linear time-invariant second-order feedback loop. DDG (a) and isomorphic architecture with longest paths highlighted (b).

(3.60) $H(z)=\frac{Y(z)}{X(z)}=\frac{1}{1-a{z}^{-1}-b{z}^{-2}}$

After multiplying numerator and denominator by a factor of (1+az ⁻¹-bz ⁻²) the transfer function becomes

(3.61) $H(z)=\frac{1+a{z}^{-1}-b{z}^{-2}}{1-(a^2+2b)z^{-2}+b^2{z}^{-4}}$

which matches the requirements for loop unfolding by a factor of p = 2.

Analogously we obtain for p = 4

(3.62) $H(z)=\frac{(1+a{z}^{-1}b{z}^{-2})(1+(a^2+2b)z^{-2}+b^2{z}^{-4}}{1-({(a^2+2b)}^2-2b^2)z^{-4}+b^4{z}^{-8}}$

Example

Figure 3.37 shows a DDG and a block diagram that implement the second order recursion (3.62). Except for finite precision effects, the transfer function remains exactly the same as in (3.59), but the arithmetic operations inside the loop can now be carried out in four rather than one computation period. The same pipelined hardware block is instantiated three times.

Figure 3.37. Linear time-invariant second-order feedback loop. DDG after unfolding by a factor of p = 4 (a) and high-performance architecture with pipelining and retiming on top (b).

A high-speed fourth-order ARMA ⁵⁵ filter chip that includes two sections similar to fig.3.37b has been reported back in 1992 [76]. Pipelined multiply-add units have been designed as combinations of consecutive carry-save and carry-ripple adders. The circuit, fabricated in a 0.9   μm CMOS technology, has been measured to run at a clock frequency of 85 MHz and spits out one sample per clock cycle, so Γ = 1. Overall computation rate roughly is 1.5 Gop/s. ⁵⁶ The authors write that one to two extra data bits had to be added in the unfolded datapath to maintain similar roundoff and quantization characteristics as in the initial configuration. Circuit size is approximately 20 kGE. At full speed the chip dissipates 2.2 W from a 5 V supply. While performance and power data are obsolete today, loop unfolding allows to push out the need for fast but costly fabrication technologies such as GaAs, then and now.

Performance and cost analysis

When compared to the first-order case, the number of pipeline registers per subsection is doubled while the other figures remain unchanged. Hence, size estimation yields

(3.63) $A(p)\ge ({\log }_{2}p+1)A_f+(2p({\log }_{2}p+1))A_{reg}$

3.7.4 Time-variant loops

Here, the feedback coefficient a is no longer constant but varies as a function of time a(k)

(3.64) $y(k)=a(k)y(k-\text{1})+x(k)$

The unfolded recursions are derived in the time domain. Substituting y(k − 1)in (3.64) yields

(3.65) $y(k)=a(k)a(k\text{-1})y(k\text{-2})+a(k)x(k\text{-1})+x(k)$

which computes y(k) from y(k − 2) directly, so the unfolding factor is p = 2. Repeating this operation leads to a configuration with p = 3 where

(3.66) $y(k)=a(k)a(k\text{-1})a(k\text{-2})y(k\text{-3})+a(k)a(k\text{-1})x(k\text{-2})+a(k)x(k\text{-1})+x(k)$

and once more to p = 4

(3.67) $\begin{array}{ll}y(k)\hfill & =a(k)a(k-\text{1})a(k-\text{2})a(k-\text{3})y(k-\text{4})+\hfill \\ \hfill & +a(k)a(k-\text{1})a(k-\text{2})x(k-\text{3})+a(k)a(k-\text{1})x(k-\text{2})+a(k)x(k-\text{1})+x(k)\hfill \end{array}$

As for the time-invariant case, the process of unfolding can be continued to widen the recursive loop by an arbitrary positive integer p as expressed by

(3.68) $y(k)=({\displaystyle \prod _{n=0}^{p-1}a(k-n)).y(k-p)+\left({\displaystyle \sum _{n=1}^{p-1}({\displaystyle \prod _{m=0}^{n-1}a(k-m))\cdot x(k-n)}}\right)}+x(k)$

However, because precomputation is not applicable here, all necessary coefficient terms must be calculated on-line, which requires extra hardware. Depending on how the terms of (3.68) are combined, various DDGs can be obtained. One of them derived from (3.67) is depicted in fig.3.38.

Figure 3.38. Linear time-variant first-order feedback loop. DDG after unfolding by a factor of p = 4.

Performance and cost analysis

The count of adders and multipliers is proportional to the number of subsections p. Each subsection requires approximately 2p pipeline registers as both multipliers must be pipelined. Together with shimming registers, many of which are needed in this configuration due to the numerous parallel branches, roughly 4p ² registers are needed.

3.7.5 Nonlinear or general loops

A nonlinear difference equation implies that the principle of superposition does not hold. The most general case of a first-order recursion is described by

(3.69) $y(k)=f(y(k\text{-1}),x(k))$

and can be unfolded an arbitrary number of times. For simplicity we will limit our discussion to a single unfolding step, i.e. to p = 2 where

(3.70) $y(k)=f(f(y(k\text{-2}),x(k\text{-1})),x(k))$

The associated DDG of fig.3.39c shows that loop unfolding per se does not relax the original timing constraint, the only difference is that one can afford two cycles for two operations f instead of one cycle for one operation. As confirmed by fig.3.39d, there is no room for any meaningful retiming in this case.

Figure 3.39. Architectural alternatives for nonlinear time-variant first-order feedback loops. Original DDG (a) and isomorphic architecture (b), DDG after unfolding by a factor of p = 2 (c), same DDG with retiming added on top (d). DDG reorganized for an associative function f (e), pertaining architecture after pipelining and retiming (f), DDG with the two functional blocks for f combined into f " (g), pertaining architecture after pipelining and retiming (h).

Yet, the unfolded recursion can serve as a starting point for more useful reorganizations. Assume function f is known to be associative. Following an associativity transform the DDG is redrawn as shown in fig.3.39e. The computation so becomes amenable to pipelining and retiming, see fig.3.39f, which cuts the longest path in half when compared to the original architecture of fig.3.39b. Even more speedup can be obtained from higher unfolding degrees, the price to pay is multiplied circuit size and extra latency, though. In summary, architecture, performance, and cost figures resemble those found for linear computations.

The situation is definitely more difficult when f is not associative. Still, it is occasionally possible to relax the loop constraint to some extent by playing a trick. Reconsider fig.3.39c and think of the two occurrences of f being combined into an aggregate computation

(3.71) $y(k)=f"(y(k\text{-2}),x(k\text{-1}),x(k))$

as sketched in fig.3.39g. If that aggregate computation can be made to require less than twice as much time as the original computation, then the bottleneck gets somewhat alleviated. This is because it should then be possible to insert a pipeline register into the datapath unit for f" so that the maximum path length in either of the two stages becomes shorter than the longest delay in a datapath that computes f alone.

(3.72) $t_{lp{f}^{″}}=\max (t_{lp{f}_1^{″}},t_{lp{f}_2^{″}})<t_{lpf}$

More methods for speeding up general time-variant first-order feedback loops are examined in [77]. One technique, referred to as expansion or look-ahead, is closely related to aggregate computation. The idea is to process two or more samples in each recursive step so that an integer multiple of the sampling interval becomes available for carrying out the necessary computations. In other terms, the recursive computation is carried out at a lower pace but on wider data words. This approach should be considered when the combinational logic is not amenable to pipelining, for example because it is implemented as table lookup in a ROM. The limiting factor is that the size of the lookup table (LUT) tends to increase dramatically.

Yet another approach, termed concurrent block technique, groups the incoming data stream into blocks of several samples and makes the processing of these blocks independent from each other. While data processing within the blocks remains sequential, it so becomes possible to process the different blocks concurrently.

The unified algebraic transformation approach promoted in [78] combines both universal and algebraic transforms to make the longest path independent of problem size in computations such as recursive filtering, recursive least squares algorithm, and singular value decomposition.

Any of the various architectural transforms that helps to successfully introduce a higher degree of parallel processing into recursive computations takes advantage of algorithmic properties such as linearity, associativity, fixed coefficients, limited word width, or of a small set of register states. If none of these applies, we can't help but agree with the authors of [77].

Observation 3.9

When the state size is large and the recurrence is not a closed-form function of specific classes, our methods for generating a high degree of concurrency cannot be applied.

Example

Cryptology provides us with a vivid example for the implications of nonlinear nonanalytical feedback loops. Consider a block cipher that works in electronic code book (ECB) mode as depicted in fig.3.41a. The algorithm implements a combinational function y(k)=c(x(k),u(k))where u(k) denotes the key and k the block number or time index. However complex function c, there is no fundamental obstacle to pipelining or to replication in the datapath.

Figure 3.41. DDGs for three block ciphering modes. Combinational operation in ECB mode (a) vs. time-variant nonlinear feedback loop in CBC mode (b), and CBC-8 operation b (c).

Unfortunately, ECB is cryptologically weak as two identical blocks of plaintext result in two identical blocks of ciphertext because y(k) = y(m) if x(k) = x(m) and u(k) = u(m). If a plaintext to be encrypted contains sufficient repetition, the ciphertext necessarily carries and betrays patterns from the original plaintext. Fig.3.40 nicely illustrates this phenomenon.

Figure 3.40. A computer graphics image in clear text, ciphered in ECB mode, and ciphered in CBC-1 mode (from left to right, Tux by Larry Ewing).

To prevent this from happening, block ciphers are typically used with feedback. In cipher block chaining (CBC) mode, the ciphertext gets added to the plaintext before encryption takes place, see fig.3.41b. The improved cipher algorithm so becomes y(k) = c(x(k) ⊕ y(k − 1), u(k)) and is sometimes referred to as CBC-1 mode because y(k − 1) is being used for feedback.

From an architectural point of view, however, this first-order recursion is awkward because it offers little room for reorganizing the computation. This is particularly true in ciphering applications where the nonlinear functions involved are chosen to be complex, labyrinthine, and certainly not analytical. The fact that word width (block size) is on the order of 64 or 128 bit makes everything worse. Inserting pipeline registers into the computational unit for c does not help since this would alter algorithm and ciphertext. Throughput in CBC mode is thus limited to a fraction of what is obtained in ECB mode. ⁵⁷

3.7.6 Pipeline interleaving, not quite an equivalence transform

It has repeatedly been noted in this section that any attempt to insert an extra register into a feedback loop with the idea of pipelining the datapath destroys the equivalence between original and pipelined computations unless its effect is somehow compensated. After all, circuits c and b of fig.3.41 behave differently. Although this may appear a futile question, let us ask

"What happens if we do just that to a first-order recursion?"

Adding an extra latency register to (3.69) results in the DDG of fig.3.42a and yields

Figure 3.42. Pipeline interleaving. DDG of nonlinear time-variant first-order feedback loop with one extra register inserted (a) and isomorphic architecture (b). Interpretation as two interleaved data streams each of which gets processed exactly as specified by the original nonlinear first-order recursion of fig. 3.39a (c,d).

(3.73) $y(k)=f(y(k\text{-2}),x(k))$

Observe that all indices are even in this equation. As k increments with time k = 0, 1, 2, 3, … indices do in fact alternate between even and odd values. It thus becomes possible to restate the ensuing input-to-output mapping as two separate recursions with no interaction between "even" data items x(k = 0, 2, 4, …, 2n, …) and "odd" items x(k = 1, 3, 5, …, 2n + 1, …).

(3.74) $y(\text{2}n)=f(y(\text{2}n\text{-2}),x(\text{2}n))$

(3.75) $y(\text{2}n+\text{1})=f(y(\text{2}n\text{-1}),x(\text{2}n+\text{1}))$

This pair of equations says that the original data processing recursion of (3.69) now gets applied to two separate data streams as depicted in fig.3.42c. From a more general perspective, it is indeed possible to cut the combinational delay in any first-order feedback loop down to $\frac{1}{p}$ by inserting p − 1 pipelining registers, yet the computation then falls apart into the processing of p interleaved but otherwise independent data streams. More often than not this is undesirable. However, practical applications exist where it is possible to take advantage of this effect.

Examples

Cipher block chaining (CBC) implements the recursion y(k) = c(x(k) ⊕) y(k − 1), u(k)) What counts from a cryptographic point of view is that patterns from the plaintext do not show up in the ciphertext. Whether this is obtained from feeding back the immediately preceding block of ciphertext y(k − 1) (CBC-1 mode) or some prior block y(k − p) where 2 ≤ p ∈ ℕ (CBC-p mode) is of minor importance. Some cryptochips, therefore, provide a fast but nonstandard CBC-8 mode in addition to the regular CBC-1 mode, see fig.3.41c. In the occurrence of the IDEA chip described in [79], maximum throughout is 176 Mbit/s both in pipelined ECB mode and in pipeline-interleaved CBC-8 mode as compared to just 22 Mbit/s in nonpipelined CBC-1.

Fig.3.43 shows a high-level block diagram of a sphere decoder, a key subfunction in a MIMO OFDM (orthogonal frequency division multiplex) receiver. Sphere decoding is essentially a sophisticated tree-traversal algorithm that achieves close-to-minimum error rate performance at a lower average search complexity than an exhaustive search. Pipelining the computation in search of throughput is not an option because of the (nonlinear) first-order recursion. Instead, the facts that (a) OFDM operates on many subcarriers at a time (typically 48 to 108) and that (b) each such subcarrier poses an independent tree-search problem, make sphere decoding an ideal candidate for pipeline interleaving. This and many other refinements to sphere decoding have been reported in [80] from which fig.3.44 has been taken.

Figure 3.43. Sphere decoder. The dashed arrows point to the extra circuitry required to handle three individual subcarriers in an interleaved fashion (simplified).

Figure 3.44. The beneficial impact of pipeline interleaving on area and throughput of a sphere decoder circuit.

(diagram courtesy of Dr. Markus Wenk)

For a much simpler example, consider some image processing algorithm where rows of pixels are dealt with independently from each other. Rather than scanning the image row by row, pixels from p successive rows are entered one by one in a cyclic manner before the process is repeated with the next column, and so on. All processing can so be carried out using a single pipelined datapath of p stages [81].

Pipeline interleaving does obviously not qualify as an equivalence transform. Still, it yields useful architectures for any recursive computation — including nonlinear ones — provided that data items arrive as separate time-multiplexed streams that are to be processed independently from each other, or can be arranged to do so. From this perspective, pipeline interleaving is easily recognized as a clever and efficient combination of time sharing with pipelining.

3.7.7 Digest

•

When in search of high performance for recursive computations, reformulating a high-order system as a cascade of smaller-order sections in order to make the system amenable to coarse grain pipelining should be considered first. As a by-product, the reduced orders of the individual recursion loops offer additional speedup potential.

•

Throughput of low-order recursive computations can be significantly improved by loop unfolding in combination with fine grain pipelining. This may bring computations into the reach of static CMOS technology that would otherwise ask for faster but also more expensive alternatives such as SiGe, BiCMOS, or GaAs.

•

Whether the inflated latency is acceptable or not depends on the application. Also, the rapid growth of overall circuit size tends to limit economically practical unfolding degrees to fairly low values, say p = 2…8, especially when the system is a time-variant one.

•

The larger number of roundoff operations resulting from loop unfolding must be compensated for by using longer word widths, which increases the cost of loop unfolding beyond the sole proliferation of computational units and intermediate registers.

•

Nonlinear feedback loops are, in general, not amenable to throughput multiplication by applying unfolding techniques. A notable exception exists when the loop function is associative.

•

Pipeline interleaving is highly efficient for accelerating recursive computations because it does not depend on any specific properties of the operations involved. Yet, as it modifies the input-to-output mapping, it is not an option unless the application admits that multiple data streams undergo the same processing independently from each other.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128007303000034

Architecture

Sarah L. Harris , David Money Harris , in Digital Design and Computer Architecture, 2016

6.7.2 DSP Instructions

Digital signal processors (DSPs) are designed to efficiently handle signal processing algorithms such as the Fast Fourier Transform (FFT) and Finite/Infinite Impulse Response filters (FIR/IIR). Common applications include audio and video encoding and decoding, motor control, and speech recognition. ARM provides a number of DSP instructions for these purposes. DSP instructions include multiply, add, and multiply-accumulate (MAC)—multiply and add the result to a running sum: sum = sum + src1 × src2. MAC is a distinguishing feature separating DSP instruction sets from regular instruction sets. It is very commonly used in DSP algorithms and doubles the performance relative to separate multiply and add instructions. However, MAC requires specifying an extra register to hold the running sum.

The Fast Fourier Transform (FFT), the most common DSP algorithm, is both complicated and performance-critical. The DSP instructions in computer architectures are intended to perform efficient FFTs, especially on 16-bit fractional data.

The basic multiply instructions, listed in Appendix B, are part of ARMv4. ARMv5TE added the saturating math instructions and packed and fractional multiplies to support DSP algorithms.

DSP instructions often operate on short (16-bit) data representing samples read from a sensor by an analog-to-digital converter. However, the intermediate results are held to greater precision (e.g., 32 or 64 bits) or saturated to prevent overflow. In saturated arithmetic, results larger than the most positive number are treated as the most positive, and results smaller than the most negative are treated as the most negative. For example, in 32-bit arithmetic, results greater than 2³¹ – 1 saturate at 2³¹ – 1, and results less than −2³¹ saturate at −2³¹. Common DSP data types are given in Table 6.15. Two's complement numbers are indicated as having one sign bit. The 16-, 32-, and 64-bit types are also known as half, single, and double precision, not to be confused with single and double-precision floating-point numbers. For efficiency, two half-precision numbers are packed in a single 32-bit word.

Table 6.15. DSP data types

Type	Sign Bit	Integer Bits	Fractional Bits
short	1	15	0
unsigned short	0	16	0
long	1	31	0
unsigned long	0	32	0
long long	1	63	0
unsigned long long	0	64	0
Q15	1	0	15
Q31	1	0	31

The integer types come in signed and unsigned flavors with the sign bit in the msb. Fractional types (Q15 and Q31) represent a signed fractional number; for example, Q31 spans the range [−1, 1–2⁻³¹] with a step of 2⁻³¹ between consecutive numbers. These types are not defined in the C standard but are supported by some libraries. Q31 can be converted to Q15 by truncation or rounding. In truncation, the Q15 result is just the upper half. In rounding, 0x00008000 is added to the Q31 value and then the result is truncated. When a computation involves many steps, rounding is useful because it avoids accumulating multiple small truncation errors into a significant error.

Saturated arithmetic is an important way to gracefully degrade accuracy in DSP algorithms. Commonly, single-precision arithmetic is sufficient to handle most inputs, but pathological cases can overflow the single-precision range. An overflow causes an abrupt sign change to a radically wrong answer, which may appear to the user as a click in an audio stream or a strangely colored pixel in a video stream. Going to double-precision arithmetic prevents overflow but degrades performance and increases power consumption in the typical case. Saturated arithmetic clips the overflow at the maximum or minimum value, which is usually close to the desired value and causes little inaccuracy.

ARM added a Q flag to the status registers to indicate that overflow or saturation has occurred in DSP instructions. For applications where accuracy is critical, the program can clear the Q flag before a computation, do the computation in single-precision, and check the Q flag afterward. If it is set, overflow occurred and the computation can be repeated in double precision if necessary.

Addition and subtraction are performed identically no matter which format is used. However, multiplication depends on the type. For example, with 16-bit numbers, the number 0xFFFF is interpreted as 65535 for unsigned short, −1 for short, and −2⁻¹⁵ for Q15 numbers. Hence, 0xFFFF ×0 xFFFF has a very different value for each representation (4,294,836,225; 1; and 2⁻³⁰, respectively). This leads to different instructions for signed and unsigned multiplication.

A Q15 number A can be viewed as a ×2 ⁻¹⁵, where a is its interpretation in the range [−2¹⁵, 2¹⁵−1] as a signed 16-bit number. Hence, the product of two Q15 numbers is:

$A\times B=a\times b\times 2^{-30}=2\times a\times b\times 2^{-31}$

This means that to multiply two Q15 numbers and get a Q31 result, do ordinary signed multiplication and then double the product. The product can then be truncated or rounded to put it back into Q15 format if necessary.

The rich assortment of multiply and multiply-accumulate instructions are summarized in Table 6.16. MACs require up to four registers: RdHi, RdLo, Rn, and Rm. For double-precision operations, RdHi and RdLo hold the most and least significant 32 bits, respectively. For example, UMLAL RdLo, RdHi, Rn, Rm computes {RdHi, RdLo} = {RdHi, RdLo} +Rn × Rm. Half-precision multiplies come in various flavors denoted in braces to choose the operands from the top or bottom half of the word, and in dual forms where both the top and bottom halves are multiplied. MACs involving half-precision inputs and a single-precision accumulator (SMLA*, SMLAW*, SMUAD, SMUSD, SMLAD, SMLSD) will set the Q flag if the accumulator overflows. The most significant word (MSW) multiplies also come in forms with an R suffix that round rather than truncate.

Table 6.16. Multiply and multiply-accumulate instructions

Instruction	Function	Description
Ordinary 32-bit multiplication works for both signed and unsigned
MUL	32 = 32 × 32	Multiply
MLA	32 = 32 + 32 × 32	Multiply-accumulate
MLS	32 = 32 − 32 × 32	Multiply-subtract
unsigned long long = unsigned long × unsigned long
UMULL	64 = 32 × 32	Unsigned multiply long
UMLAL	64 = 64 + 32 × 32	Unsigned multiply-accumulate long
UMAAL	64 = 32 + 32 × 32 + 32	Unsigned multiply-accumulate-add long
long long = long × long
SMULL	64 = 32 × 32	Signed multiply long
SMLAL	64 = 64 + 32 × 32	Signed multiply-accumulate long
Packed arithmetic: short × short
SMUL{BB/BT/TB/TT}	32 = 16 × 16	Signed multiply {bottom/top}
SMLA{BB/BT/TB/TT}	32 = 32 + 16 × 16	Signed multiply-accumulate {bottom/top}
SMLAL{BB/BT/TB/TT}	64 = 64 + 16 × 16	Signed multiply-accumulate long {bottom/top}
Fractional multiplication (Q31 / Q15)
SMULW{B/T}	32 = (32 × 16) >> 16	Signed multiply word-halfword {bottom/top}
SMLAW{B/T}	32 = 32 + (32 × 16) >> 16	Signed multiply-add word-halfword {bottom/top}
SMMUL{R}	32 = (32 × 32) >> 32	Signed MSW multiply {round}
SMMLA{R}	32 = 32 + (32 × 32) >> 32	Signed MSW multiply-accumulate {round}
SMMLS{R}	32 = 32 − (32 × 32) >> 32	Signed MSW multiply-subtract {round}
long or long long = short × short + short × short
SMUAD	32 = 16 × 16 + 16 × 16	Signed dual multiply-add
SMUSD	32 = 16 × 16 − 16 × 16	Signed dual multiply-subtract
SMLAD	32 = 32 + 16 × 16 + 16 × 16	Signed multiply-accumulate dual
SMLSD	32 = 32 + 16 × 16 − 16 × 16	Signed multiply-subtract dual
SMLALD	64 = 64 + 16 × 16 + 16 × 16	Signed multiply-accumulate long dual
SMLSLD	64 = 64 + 16 × 16 − 16 × 16	Signed multiply-subtract long dual

The DSP instructions also include saturated add (QADD) and subtract (QSUB) of 32-bit words that saturate the results instead of overflowing. They also include QDADD and QDSUB, which double the second operand before adding/subtracting it to/from the first with saturation; we will shortly find these valuable in fractional MACs. They set the Q flag if saturation occurs.

Finally, the DSP instructions include LDRD and STRD that load and store an even/odd pair of registers in a 64-bit memory double word. These instructions increase the efficiency of moving double-precision values between memory and registers.

Table 6.17 summarizes how to use the DSP instructions to multiply or MAC various types of data. The examples assume halfword data is in the bottom half of a register and that the top half is zero; use the T flavor of SMUL when the data is in the top instead. The result is stored in R2, or in {R3, R2} for double-precision. Fractional operations (Q15/Q31) double the result using saturated adds to prevent overflow when multiplying −1 × −1.

Table 6.17. Multiply and MAC code for various data types

First Operand (R0)	Second Operand (R1)	Product (R3/R2)	Multiply	MAC
short	short	short	SMULBB R2, R0, R1	SMLABB R2, R0, R1
			LDR R3, =0x0000FFFF	LDR R3, =0x0000FFFF
			AND R2, R3, R2	AND R2, R3, R2
short	short	long	SMULBB R2, R0, R1	SMLABB R2, R0, R1, R2
short	short	long long	MOV R2, #0	SMLALBB R2, R3, R0, R1
			MOV R3, #0
			SMLALBB R2, R3, R0, R1
long	short	long	SMULWB R2, R0, R1	SMLAWB R2, R0, R1, R2
long	long	long	MUL R2, R0, R1	MLA R2, R0, R1, R2
long	long	long long	SMULL R2, R3, R0, R1	SMLAL R2, R3, R0, R1
unsigned short	unsigned short	unsigned short	MUL R2, R0, R1	MLA R2, R0, R1, R2
			LDR R3, =0x0000FFFF	LDR R3, =0x0000FFFF
			AND R2, R3, R2	AND R2, R3, R2
unsigned short	unsigned short	unsigned long	MUL R2, R0, R1	MLA R2, R0, R1, R2
unsigned long	unsigned short	unsigned long	MUL R2, R0, R1	MLA R2, R0, R1, R2
unsigned long	unsigned long	unsigned long	MUL R2, R0, R1	MLA R2, R0, R1, R2
unsigned long	unsigned long	unsigned long long	UMULL R2, R3, R0, R1	UMLAL R2, R3, R0, R1
Q15	Q15	Q15	SMULBB R2, R0, R1	SMLABB R2, R0, R1, R2
			QADD R2, R2, R2	SSAT R2, 16, R2
			LSR R2, R2, #16
Q15	Q15	Q31	SMULBB R2, R0, R1	SMULBB R3, R0, R1
			QADD R2, R2, R2	QDADD R2, R2, R3
Q31	Q15	Q31	SMULWB R2, R0, R1	SMULWB R3, R0, R1
			QADD R2, R2, R2	QDADD R2, R2, R3
Q31	Q31	Q31	SMMUL R2, R0, R1	SMMUL R3, R0, R1
			QADD R2, R2, R2	QDADD R2, R2, R3

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128000564000066

Discrete-Time Signals and Systems

Luis F. Chaparro , in Signals and Systems using MATLAB, 2011

8.22 IIR versus FIR Systems

A significant difference between IIR and FIR discrete-time systems is stability. Consider an IIR filter with the difference equation

$\begin{array}{l}\hfill y_1\left[n\right]=x\left[n\right]-0.5y_1\left[n-1\right]\end{array}$

where x[n] is the input and y ₁[n] is the output. Then consider an FIR filter

$\begin{array}{l}\hfill y_2\left[n\right]=x\left[n\right]+0.5x\left[n-1\right]+3x\left[n-2\right]+x\left[n-5\right]\end{array}$

where x[n] is the input and y ₂[n] is the output.

(a)

Since to check the stability of these filters we need their impulse responses, find the impulse responses h ₁[n] corresponding to the IIR filter by recursion, and h ₂[n] corresponding to the FIR filter.

(b)

Use the impulse response h ₁[n] to check the stability of the IIR filter.

(c)

Use the impulse response h ₂[n] to check the stability of the FIR filter.

(d)

Since the impulse response of a FIR filter has a finite number of nonzero terms, would it be correct to say that FIR filters are always stable? Explain.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747167000120

Filtering and sampling

In Digital Video and HD (Second Edition), 2012

Infinite impulse response (IIR) filters

The digital filters described so far have been members of the FIR class. A second class of digital filter is characterized by having a potentially infinite impulse response (IIR). An IIR (or recursive) filter computes a weighted sum of input samples – as is the case in an FIR filter – but adds to this a weighted sum of previous output samples.

What a signal processing engineer calls an IIR filter is known in the finance and statistics communities as autoregressive moving average (ARMA)

A simple IIR is sketched in Figure 20.22: The input sample is weighted by ¼, and the previous output is weighted by ¾. These weighted values are summed to form the filter result. The filter result is then fed back to become an input to the computation of the next sample. The impulse response jumps rapidly upon the onset of the input impulse, and tails off over many samples. This is a simple one-tap lowpass filter; its time-domain response closely resembles an analog RC lowpass filter. A highpass filter is formed by taking the difference of the input sample from the previously stored filter result.

Figure 20.22. An IIR (&quot;recursive&quot;) filter computesa weighted sum of input samples (here, just 0.25 times the current sample), and adds to this a weighted sum of previous result samples. Every IIR filter exhibits nonlinear phase response.

In an IIR filter having just one tap, the designer's ability to tailor frequency response is severely limited. An IIR filter can be extended by storing several previous filter results, and adding (or subtracting) a fraction of each to a fraction of the current input sample. In such a multitap IIR filter, a fine degree of control can be exercised over frequency response using just a handful of taps. Just three or four taps in an IIR filter can achieve frequency response that might take 20 taps in an FIR filter.

However, there's a catch: In an IIR filter, both attenuation and delay depend upon frequency. In the terminology of the previous section, an IIR filter exhibits nonlinear phase. Typically, low-frequency signals are delayed more than high-frequency signals. As I have explained, variation of delay as a function of frequency is potentially a very serious problem in video.

An IIR filter cannot have exactly linear phase, although a complex IIR filter can be designed to have arbitrarily small phase error. Because IIR filters usually have poor phase response, they are not ordinarily used in video. (A notable exception is the use of field- and frame-based IIR filters in temporal noise reduction, where the delay element comprises a field or frame of storage.)

Compensation of undesired phase response in a filter is known as equalization. This is unrelated to the equalization pulses that form part of sync.

Owing to the dependence of an IIR filter's result upon its previous results, an IIR filter is necessarily recursive. However, certain recursive filters have finite impulse response, so a recursive filter does not necessarily have infinite impulse response.

The terms nonrecursive and recursive are best used to describe filter implementation structures.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123919267500205

Fourier Analysis of Discrete-Time Signals and Systems

Luis F. Chaparro , in Signals and Systems using MATLAB, 2011

10.28 DFT and IIR Filters—MATLAB

A definite advantage of the FFT is that it reduces considerably the computation in the convolution sum. Thus, if x[n], 0 ≤ n ≤ N − 1 is the input of an FIR filter with impulse response h[n], 0 ≤ n ≤ M − 1, their convolution sum $y\left[n\right]=\left[x\ast h\right]\left[n\right]$ will be of length M + N − 1. Now if X[k] and H[k] are the DFTs (computed by the FFT) of x[n] and h[n], and if Y[k] = X[k]H[k] is the DFT of the convolution sum of length bigger or equal to M + N − 1, then to be able to multiply the FFTs X[k] and H[k] they both should be of the same length as Y[k] (i.e., bigger or equal to M + N − 1). Consider what happens when the filter is an IIR that possibly has an impulse response of very large length. Let

$y\left[n\right]-1.755y\left[n-1\right]+0.81y\left[n-2\right]=x\left[n\right]+0.5x\left[n-1\right]$

be the difference equation representing an IIR filter with input x[n] and output y[n]. Assume the initial conditions are zero, and the input is $x\left[n\right]=u\left[n\right]-u\left[n-50\right]$ . Use MATLAB to obtain your results.

(a)

Compute using filter the first 40 values of the impulse response h[n] and use them to approximate it (call it $ĥ\left[n\right]$ ). Compute the filter output $ŷ\left[n\right]$ using the FFT as indicated above. In this case, we are approximating the IIR filter by an FIR filter of length 40. Plot the input and the output. Use FFTs of length 128.

(b)

Suppose now that we do not want to approximate h[n], so consider the following procedure. Find the transfer function of the IIR filter, say H(z) = B(z)/A(z), and if X(z) is the Z-transform of the input, then

$Y(z)=\frac{B(z)X(z)}{A(z)}$

Compute as before the FFT for x[n], of length 128 (call it X[k]) and compute the 128 length of the coefficients of B(z) and A(z) to obtain DFTs B[k] and A[k]. Multiplying X[k] by B[k] and dividing by A[k], all of length 128, results in a sequence of length 128 that should correspond to Y[k], the DFT of y[n]. Compute the inverse FFT to get y[n].

(c)

Use filter to solve the difference equation and obtain y[n] for $x\left[n\right]=u\left[n\right]-u\left[n-50\right]$ . If this is the exact solution, calculate the error with respect to the other responses in (a) and (b)?

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747167000144

Lab Project Examples

Nasser Kehtarnavaz , in Real-Time Digital Signal Processing, 2005

Project 2 Cascade IIR Filter Implementation

Here, we have used the FDATool of MATLAB to obtain the coefficients of the filter. The quantization of the coefficients alters the frequency response, as shown in Figure 11-1. With the second-order cascade filter implementation, the sensitivity to coefficient quantization is significantly reduced. The interested reader is referred to [1] for theoretical details. The frequency response of the second-order cascade implementation is shown in Figure 11-2, and the quantized filter coefficients in Q-15 and single-precision formats are listed in Table 11-1 for each section.

Figure 11-1. Effect of quantization for a single section on (a) magnitude response (b) pole/zero plot.

Figure 11-2. Effect of quantization for second-order cascade filter on (a) magnitude response (b) pole/zero plot.

Table 11-1. Coefficients of cascaded second-order filters.

Quantized Coefficients in Q-15	Designed Coefficients
——-Section 1——-
Numerator
0x7FFF (0.999969482421875)	1.000000000000000000
0x7FFF (0.999969482421875)	1.631899318476804000
0x7FFF (0.999969482421875)	1.000000000000000400
Denominator
0x7FFF (0.999969482421875)	1.000000000000000000
OxCCOl (−0.406250000000000)	−0.406240975551636410
0x07CA (0.060852050781250)	0.060839816716921374
——-Section 2——-
Numerator
0x7FFF (0.999969482421875)	1.000000000000000000
0x1905 (0.195465087890625)	0.195463825774149170
0x7FFF (0.999969482421875)	1.000000000000001800
Denominator
0x7FFF (0.999969482421875)	1.000000000000000000
0xB177 (−0.613586425781250)	−0.613596465553117860
0xlE9C (0.239135742187500)	0.239148166557621610
——-Section 3——-
Numerator
0x7FFF (0.999969482421875)	1.000000000000000000
0xB439 (−0.592041015625000)	−0.592045778337563780
0x7FFF (0.999969482421875)	0.999999999999997780
Denominator
0x7FFF (0.999969482421875)	1.000000000000000000
0x8C7E (−0.902435302734375)	−0.902432041178152230
0x4104 (0.507934570312500)	0.507920458903674770
——-Section 4——-
Numerator
0x7FFF (0.999969482421875)	1.000000000000000000
0x8FC3 (−0.876892089843750)	−0.876905411177924200
0x7FFF (0.999969482421875)	0.999999999999998780
Denominator
0x7FFF (0.999969482421875)	1.000000000000000000
0x8000 (−1.000000000000000)	−1.180266034077308100
0x68B4 (0.817993164062500)	0.818001830217691680
Scale Value = 0x019A (0.0125407)

The quantized coefficients are first stated in floating-point format, and then converted into Q-15 format. This conversion needs to be done before enabling the interrupt service routine. In the interrupt service routine, serialPortRcvISR, the gain factor is multiplied with the input to avoid possible overflows followed by four sections of the IIR filter. Each section of the IIR filter simply consists of dot-products and buffering. The output from a previous section becomes the input of a following section. The accuracy of the Q-format representation, Qnum in the code, and the maximum positive number corresponding to the current representation, MAX_POS, for example, 0x7FFF for Q-15 format, should be changed for other Q-format representations.

The code is rewritten in assembly. Each IIR filter section is replaced with an assembly function, which is called by the following code line:

The above function call loads the current input, previous outputs, and filter coefficients, and calculates the dot-products corresponding to the numerator and denominator. The numerator sum is subtracted from the denominator sum for the final output. The assembly code for doing so is given below:

The number of cycles corresponding to one section of the IIR filter is shown in Table 11-2 for different builds. As can be seen from this table, the C implementation provides a faster outcome as compared with the assembly version, and the linear assembly version provides a slower outcome as compared with the assembly version. The main reason for this is that there are too few repetitions, 3 at most, of the loop. The C code is already fully optimized by using assembly intrinsics and not using any loop structure, while the linear assembly and the assembly are implemented with loop structures. The difference between optimized C and hand-optimized assembly is due to the fact that calling assembly function in C incorporates several procedures such as passing arguments from C to assembly, storing return address, branching to assembly routine, returning output value, and branching back from assembly routine. As the number of repetition increases, the efficiency of the linear assembly and hand-optimized assembly as compared with the C version becomes more noticeable.

Table 11-2. Number of cycles for different builds.

Build type	Number of cycles
C without optimization (none/-o3)	38/27
Linear assembly (none/-o3)	152/183
Simple assembly	132
Hand-optimized assembly	51

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780750678308500134

Introduction to the Design of Discrete Filters

Luis F. Chaparro , in Signals and Systems using MATLAB, 2011

11.2.2 IIR and FIR Discrete Filters

■

A discrete filter with transfer function

(11.7) $H(z)=\frac{B(z)}{A(z)}=\frac{{\displaystyle {\sum }_{m=0}^{M-1}{b}_m{z}^{-m}}}{1+{\displaystyle {\sum }_{k=1}^{N-1}{a}_k{z}^{-k}}}={\displaystyle \sum _{n=0}^{\infty }h}[n]z^{-n}$

is called infinite-impulse response or IIR since its impulse response h[n] typically has infinite length. It is also called recursive because if the input of the filter H(z) is x[n] and y[n] is its output, the input–output relationship is given by the difference equation

(11.8) $y[n]=-{\displaystyle \sum _{k=1}^{N-1}{a}_k}y[n-k]+{\displaystyle \sum _{m=0}^{M-1}{b}_m}x[n-m]$

where the output recurs on previous outputs (i.e., the output is fed back).

■

The transfer function of a finite-impulse response or FIR filter is

(11.9) $H(z)=B(z)={\displaystyle \sum _{m=0}^{M-1}{b}_m}{z}^{-m}$

Its impulse response is $h\left[n\right]=b_n,n=0,\dots ,M-1$ , and zero elsewhere, thus of finite length. This filter is called nonrecursive given that the input–output relationship is given by

(11.10) $y[n]={\displaystyle \sum _{m=0}^M{b}_m}x[n-m]=(b*x)[n]$

or the convolution sum of the filter coefficients (or impulse response) and the input.

For practical reasons, these filters are causal (i.e., h[n] = 0 for n < 0) and bounded-input bounded-output (BIBO) stable (i.e., all the poles of H(z) must be inside the unit circle). This guarantees that the filter can be implemented and used in real-time processing, and that the output remains bounded when the input is bounded.

Remarks

■

Calling the IIR filters recursive is more appropriate. It is possible to have a filter with a rational transfer function that does not have an infinite-length impulse response. However, it is traditional to refer to these filters as IIR.

■

When comparing the IIR and the FIR filters, neither has a definite advantage:

■

IIR filters are implemented more efficiently than FIR filters in terms of number of operations and required storage (having similar frequency responses, an IIR filter has fewer coefficients than an FIR filter).

■

The implementation of an IIR filter using the difference equation resulting from its transfer function is simple and computationally efficient, but FIR filters can be implemented using the Fast Fourier Transform (FFT) algorithm, which is computationally very efficient.

■

Since the transfer function of any FIR filter only has poles at the origin of the z-plane, FIR filters are always BIBO stable, but for an IIR filter we need to check that the poles of its transfer function (i.e., zeros of A(z)) are inside the unit circle if the design procedure does not guarantee stability.

■

FIR filters can be designed to have linear phase, while IIR filters usually have nonlinear phase, but approximately linear phase in the passband region.

Example 11.1

The phase of IIR filters is always nonlinear. Although it is possible to design FIR filters with linear phase, not all FIR filters have linear phase. As we will see, symmetry conditions on the impulse response of FIR filters are needed to have linear phase. Consider the following two filters with input–output equations

(a)

$y[n]=0.5y[n-1]+x[n]$

(b)

$y[n]=\frac{1}{3}\left(x[n-1]+x[n]+x[n+1]\right)$

where x[n] is the input and y[n] is the output. Use MATLAB to compute and plot the magnitude and the phase response of each of these filters.

Solution

The transfer functions of the given filters are:

(a)

$H_1(z)=\frac{1}{1-0.5z^{-1}}$

(b)

$H_2(z)=\frac{1}{3}[z^{-1}+1+z]=\frac{1+z+z^2}{3z}=\frac{(z-1e^{j2.09})(z-1e^{-j2.09})}{3z}$

Thus, the first is an IIR filter and the second is an FIR filter (notice that this filter is noncausal as it requires future values of the input to compute the present output). The phase responses of these filters are clearly nonlinear. The transfer function H ₂(z) has zeros on the unit circle $z=1e^{\pm j2.09}$ , making the phase of this filter not continuous and so it cannot be unwrapped. Figure 11.4 shows the magnitude and the phase responses of the filters H ₁(z) and H ₂(z).

Figure 11.4. Magnitude and phase responses of an IIR filter with a transfer function of (a) $H_1(z)=1∕(1-0.5z^{-1})$ , and of an FIR filter with a transfer function of (b) $H_2(z)=(z-1e^{j2.09})(z-1e^{-j2.09})∕3z$ . Notice the phase responses are nonlinear.

Example 11.2

A simple model for the multipath effect in the channel of a wireless system is

$\begin{array}{lll}\hfill y\left[n\right]=x\left[n\right]-\alpha x\left[n-N_0\right]\alpha =0.8,N_0=11& & \hfill \end{array}$

That is, the output y[n] is a combination of the input x[n] and of a delayed and attenuated version of the input. Determine the transfer function of the filter that gives the above input–output equation. Use MATLAB to plot its magnitude and phase. If the phase is nonlinear, how would you recover the input x[n] (which is the message)? Let the input be $x\left[n\right]=2+\cos \left(\pi n∕4\right)+\cos \left(\pi n\right)$ . In practice, the delay N ₀ and the attenuation α are not known at the receiver and need to be estimated. What would happen if the delay is estimated to be 12 and the attenuation 0.79?

Solution

The transfer function of the filter with input x[n] and output y[n] is

$\begin{array}{r}H\left(z\right)=\frac{Y\left(z\right)}{X\left(z\right)}=1-0.8z^{-11}=\frac{z^{11}-0.8}{z^{11}}\end{array}$

with a pole of z = 0 of multiplicity 11, and zeros the roots of $z^{11}-0.8=0$ , or

$\begin{array}{lll}\hfill z_k={\left(0.8\right)}^{1∕11}{e}^{j2\pi k∕11}k=0,\dots ,10& & \hfill \end{array}$

Using the freqz function to plot its magnitude and phase responses (see Figure 11.5), we find that the phase is nonlinear, and as such the output of H(z), y[n], will not be a delayed version of the input. To recover the input, we use an inverse filter G(z) such that cascaded with H(z) the overall filter is an all-pass filter (i.e., H(z)G(z) = 1). Thus,

$\begin{array}{lll}\hfill G\left(z\right)=\frac{z^{11}}{z^{11}-0.8}& & \hfill \end{array}$

Figure 11.5. (a) Poles and zeros and frequency response of the FIR comb filter $H(z)=(z^{11}-0.8)∕z^{11}$ , and (b) the estimated inverse IIR comb filter $G(z)=z^{12}∕(z^{12}-0.79)$ . (c) The message $x\left[n\right]=2+\cos \left(\pi n∕4\right)+$ $\cos \left(\pi n\right)$ , the output y[n] of channel H(z), and the output z[n] of the estimated inverse filter G(z).

The poles and zeros and the magnitude and the phase responses of H(z) are shown in Figure 11.5(a). The filters with transfer functions H(z) and G(z) are called comb filters given the shape of their magnitude responses.

If the delay is estimated to be 11 and the attenuation 0.8, the input signal x[n] (the message) is recovered exactly; however, if we have slight variations on these values the message might not be recovered. When the delay is estimated to be 12 and the attenuation 0.79, the inverse filter is

$\begin{array}{lll}\hfill G\left(z\right)=\frac{z^{12}}{z^{12}-0.79}& & \hfill \\ \hfill & & \hfill \end{array}$

having the poles, zeros, and magnitude and phase responses shown in Figure 11.5(b). In Figure 11.5(c), the effect of these changes are illustrated. The output of the inverse filter z[n] does not resemble the sent signal x[n]. The signal y[n] is the output of the channel with a transfer function H(z).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747167000156

Subband Coding

Khalid Sayood , in Introduction to Data Compression (Fourth Edition), 2012

14.3 Filters

A system that isolates certain frequency components is called a filter. The analogy here with mechanical filters such as coffee filters is obvious. A coffee filter or a filter in a water purification system blocks coarse particles and allows only the finer-grained components of the input to pass through. The analogy is not complete, however, because mechanical filters always block the coarser components of the input, while the filters we are discussing can selectively let through or block any range of frequencies. Filters that only let through components below a certain frequency $f_0$ are called low-pass filters; filters that block all frequency components below a certain value $f_0$ are called high-pass filters. The frequency $f_0$ is called the cutoff frequency. Filters that let through components that have frequency content above some frequency $f_1$ but below frequency $f_2$ are called band-pass filters.

One way to characterize filters is by their magnitude transfer function—the ratio of the magnitude of the input and output of the filter as a function of frequency. In Figure   14.4 we show the magnitude transfer function for an ideal low-pass filter and a more realistic low-pass filter, both with a cutoff frequency of $f_0$ . In the ideal case, all components of the input signal with frequencies below $f_0$ are unaffected except for a constant amount of amplification. All frequencies above $f_0$ are blocked. In other words, the cutoff is sharp. In the case of the more realistic filter, the cutoff is more gradual. Also, the amplification for the components with frequency less than $f_0$ is not constant, and components with frequencies above $f_0$ are not totally blocked. This phenomenon is referred to as ripple in the passband and stopband.

Figure 14.4. Ideal and realistic low-pass filter characteristics.

The filters we will discuss are digital filters, which operate on a sequence of numbers that are usually samples of a continuously varying signal. We discussed sampling in Chapter 12. For those of you who skipped that chapter, let us take a brief look at the sampling operation.

How often does a signal have to be sampled in order to reconstruct the signal from the samples? If one signal changes more rapidly than another, it is reasonable to assume that we would need to sample the more rapidly varying signal more often than the slowly varying signal in order to achieve an accurate representation. In fact, it can be shown mathematically that if the highest frequency component of a signal is $f_0$ , then we need to sample the signal at more than $2f_0$ times per second. This result is known as the Nyquist theorem or Nyquist rule after Harry Nyquist, a famous mathematician from Bell Laboratories. His pioneering work laid the groundwork for much of digital communication. The Nyquist rule can also be extended to signals that only have frequency components between two frequencies $f_1$ and $f_2$ . If $f_1$ and $f_2$ satisfy certain criteria, then we can show that in order to recover the signal exactly, we need to sample the signal at a rate of at least $2(f_2-f_1)$ samples per second [134].

What would happen if we violated the Nyquist rule and sampled at less than twice the highest frequency? In Chapter 12 we showed that it would be impossible to recover the original signal from the sample. Components with frequencies higher than half the sampling rate show up at lower frequencies. This process is called aliasing. In order to prevent aliasing, most systems that require sampling will contain an "anti-aliasing filter" that restricts the input to the sampler to be less than half the sampling frequency. If the signal contains components at more than half the sampling frequency, we will introduce distortion by filtering out these components. However, the distortion due to aliasing is generally more severe than the distortion we introduce due to filtering.

Digital filtering involves taking a weighted sum of current and past inputs to the filter and, in some cases, the past outputs of the filter. The general form of the input-output relationships of the filter is given by

(8) $y_n={\displaystyle \sum _{i=0}^N}{a}_i{x}_{n-i}+{\displaystyle \sum _{i=1}^M}{b}_i{y}_{n-i}$

where the sequence $\{x_n\}$ is the input to the filter, the sequence $\{y_n\}$ is the output from the filter, and the values $\{a_i\}$ and $\{b_i\}$ are called the filter coefficients.

If the input sequence is a single 1 followed by all 0s, the output sequence is called the impulse response of the filter. Notice that if the $b_i$ are all 0, then the impulse response will die out after $N$ samples. These filters are called finite impulse response (FIR) filters. The number $N$ is sometimes called the number of taps in the filter. If any of the $b_i$ have nonzero values, the impulse response can, in theory, continue forever. Filters with nonzero values for some of the $b_i$ are called infinite impulse response (IIR) filters.

Example 14.3.1

Suppose we have a filter with $a_0=1.25$ and $a_1=0.5$ . If the input sequence $\{x_n\}$ is given by

(9) $x_n=\left\{\begin{array}{cc}\hfill 1\hfill & \hfill n=0\hfill \\ \hfill 0\hfill & \hfill n\ne 0\hfill \end{array}\right.$

then the output is given by

$\begin{array}{cc}\hfill y_0=& a_0{x}_0+a_1{x}_{-1}=1.25\hfill \\ \hfill y_1=& a_0{x}_1+a_1{x}_0=0.5\hfill \\ \hfill y_n=& 0n<0\text{or}n>1\hfill \end{array}$

This output is called the impulse response of the filter. The impulse response sequence is usually represented by $\{h_n\}$ . Therefore, for this filter we would say that

(10) $h_n=\left\{\begin{array}{cc}\hfill 1.25\hfill & \hfill n=0\hfill \\ \hfill 0.5\hfill & \hfill n=1\hfill \\ \hfill 0\hfill & \hfill \text{otherwise}\hfill \end{array}\right.$

Notice that if we know the impulse response we also know the values of $a_i$ . Knowledge of the impulse response completely specifies the filter. Furthermore, because the impulse response goes to zero after a finite number of samples (two in this case), the filter is an FIR filter.

The filters we used in Example 14.2.1 are both two-tap FIR filters with impulse responses

(11) $h_n=\left\{\begin{array}{cc}\hfill \frac{1}{2}\hfill & \hfill n=0\hfill \\ \hfill \frac{1}{2}\hfill & \hfill n=1\hfill \\ \hfill 0\hfill & \hfill \text{otherwise}\hfill \end{array}\right.$

for the "averaging" or low-pass filter, and

(12) $h_n=\left\{\begin{array}{cc}\hfill \frac{1}{2}\hfill & \hfill n=0\hfill \\ \hfill -\frac{1}{2}\hfill & \hfill n=1\hfill \\ \hfill 0\hfill & \hfill \text{otherwise}\hfill \end{array}\right.$

for the "difference" or high-pass filter.

Now let's consider a different filter with $a_0=1$ and $b_1=0.9$ . For the same input as above, the output is given by

(13) $y_0=a_0{x}_0+b_1{y}_{-1}=1(1)+0.9(0)=1$

(14) $y_1=a_0{x}_1+b_1{y}_0=1(0)+0.9(1)=0.9$

(15) $y_2=a_0{x}_2+b_1{y}_1=1(0)+0.9(0.9)=0.81$

(16) $\begin{array}{cc}\hfill ⋮& ⋮\hfill \\ \hfill y_n=& (0.9{)}^n\hfill \end{array}$

The impulse response can be written more compactly as

(17) $h_n=\left\{\begin{array}{cc}\hfill 0\hfill & \hfill n<0\hfill \\ \hfill (0.9{)}^n\hfill & \hfill n⩾0\hfill \end{array}\right.$

Notice that the impulse response is nonzero for all $n⩾0$ , which makes this an IIR filter.   ♦

Although it is not as clear in the IIR case as it was in the FIR case, the impulse response completely specifies the filter. Once we know the impulse response of the filter, we know the relationship between the input and output of the filter. If $\{x_n\}$ and $\{y_n\}$ are the input and output, respectively, of a filter with impulse response $\{h_n{\}}_{n=0}^M$ , then $\{y_n\}$ can be obtained from $\{x_n\}$ and $\{h_n\}$ via the following relationship:

(18) $y_n={\displaystyle \sum _{k=0}^M}{h}_k{x}_{n-k}$

where $M$ is finite for an FIR filter and infinite for an IIR filter. The relationship shown in (18) is known as convolution and can be easily obtained through the use of the properties of linearity and shift invariance (see Problem 1 at the end of this chapter).

Because FIR filters are simply weighted averages, they are always stable. When we say a filter is stable we mean that as long as the input is bounded, the output will also be bounded. This is not true of IIR filters. Certain IIR filters can give an unbounded output even when the input is bounded.

Example 14.3.2

Consider a filter with $a_0=1$ and $b_1=2$ . Suppose the input sequence is a single 1 followed by 0s. Then the output is

(19) $y_0=a_0{x}_0+b_1{y}_{-1}=1(1)+2(0)=1$

(20) $y_1=a_0{x}_0+b_1{y}_0=1(0)+2(1)=2$

(21) $y_2=a_0{x}_1+b_1{y}_1=1(0)+2(2)=4$

(22) $\begin{array}{cc}\hfill ⋮& ⋮\hfill \\ \hfill y_n=& 2^n\hfill \end{array}$

Even though the input contained a single 1, the output at time $n=30$ is $2^{30}$ , or more than a billion!   ♦

Although IIR filters can become unstable, they can also provide better performance, in terms of sharper cutoffs and less ripple in the passband and stopband for a fewer number of coefficients.

The study of design and analysis of digital filters is a fascinating and important subject. We provide some of the details in Sections 14.5, 14.6, 14.7, 14.8. If you are not interested in these topics, you can take a more utilitarian approach and make use of the literature to select the necessary filters rather than design them. In the following section we briefly describe some of the families of filters used to generate the examples in this chapter. We also provide filter coefficients that you can use for experiment.

14.3.1 Some Filters Used in Subband Coding

The most frequently used filter banks in subband coding consist of a cascade of stages, where each stage consists of a low-pass filter and a high-pass filter, as shown in Figure   14.5. The most popular among these filters are the quadrature mirror filters (QMF), which were first proposed by Crosier, Esteban, and Galand [203]. These filters have the property that if the impulse response of the low-pass filter is given by $\{h_n\}$ , then the high-pass impulse response is given by $\{(-1{)}^n{h}_{N-1-n}\}$ . The quadrature mirror filters designed by Johnston [1,9] are widely used in a number of applications. The filter coefficients for 8-, 16-, and 32-tap filters are given in Tables   14.1, 14.2, 14.3. Notice that the filters are symmetric; that is,

Figure 14.5. An eight-band filter bank.

Table 14.1. Coefficients for the eight-tap Johnston low-pass filter.

$h_0\text{,}{h}_7$	0.00938715
$h_1\text{,}{h}_6$	0.06942827
$h_2\text{,}{h}_5$	−0.07065183
$h_3\text{,}{h}_4$	0.48998080

Table 14.2. Coefficients for the 16-tap Johnston low-pass filter.

$h_0\text{,}{h}_{15}$	0.002898163
$h_1\text{,}{h}_{14}$	−0.009972252
$h_2\text{,}{h}_{13}$	−0.001920936
$h_3\text{,}{h}_{12}$	0.03596853
$h_4\text{,}{h}_{11}$	−0.01611869
$h_5\text{,}{h}_{10}$	−0.09530234
$h_6\text{,}{h}_9$	0.1067987
$h_7\text{,}{h}_8$	0.4773469

Table 14.3. Coefficients for the 32-tap Johnston low-pass filter.

$h_0\text{,}{h}_{31}$	0.0022551390
$h_1\text{,}{h}_{30}$	−0.0039715520
$h_2\text{,}{h}_{29}$	−0.0019696720
$h_3\text{,}{h}_{28}$	0.0081819410
$h_4\text{,}{h}_{27}$	0.00084268330
$h_5\text{,}{h}_{26}$	−0.014228990
$h_6\text{,}{h}_{25}$	0.0020694700
$h_7\text{,}{h}_{24}$	0.022704150
$h_8\text{,}{h}_{23}$	−0.0079617310
$h_9\text{,}{h}_{22}$	−0.034964400
$h_{10}\text{,}{h}_{21}$	0.019472180
$h_{11}\text{,}{h}_{20}$	0.054812130
$h_{12}\text{,}{h}_{19}$	−0.044524230
$h_{13}\text{,}{h}_{18}$	−0.099338590
$h_{14}\text{,}{h}_{17}$	0.13297250
$h_{15}\text{,}{h}_{16}$	0.46367410

(23) $h_{N-1-n}=h_{n}n=0\text{,}1\text{,}\dots \text{,}\frac{N}{2}-1$

As we shall see later, the filters with fewer taps are less efficient in their decomposition than the filters with more taps. However, from Equation (18) we can see that the number of taps dictates the number of multiply-add operations necessary to generate the filter outputs. Thus, if we want to obtain more efficient decompositions, we do so by increasing the amount of computation.

Another popular set of filters are the Smith-Barnwell filters [205], some of which are shown in Tables   14.4 and 14.5.

Table 14.4. Coefficients for the eight-tap Smith-Barnwell low-pass filter.

$h_0$	0.0348975582178515
$h_1$	−0.01098301946252854
$h_2$	−0.06286453934951963
$h_3$	0.223907720892568
$h_4$	0.556856993531445
$h_5$	0.357976304997285
$h_6$	−0.02390027056113145
$h_7$	−0.07594096379188282

Table 14.5. Coefficients for the 16-tap Smith-Barnwell low-pass filter.

$h_0$	0.02193598203004352
$h_1$	0.001578616497663704
$h_2$	−0.06025449102875281
$h_3$	−0.0118906596205391
$h_4$	0.137537915636625
$h_5$	0.05745450056390939
$h_6$	−0.321670296165893
$h_7$	−0.528720271545339
$h_8$	−0.295779674500919
$h_9$	0.0002043110845170894
$h_{10}$	0.02906699789446796
$h_{11}$	−0.03533486088708146
$h_{12}$	−0.006821045322743358
$h_{13}$	0.02606678468264118
$h_{14}$	0.001033363491944126
$h_{15}$	−0.01435930957477529

These families of filters differ in a number of ways. For example, consider the Johnston eight-tap filter and the Smith-Barnwell eight-tap filter. The magnitude transfer functions for these two filters are plotted in Figure   14.6. Notice that the cutoff for the Smith-Barnwell filter is much sharper than the cutoff for the Johnston filter. This means that the separation provided by the eight-tap Johnston filter is not as good as that provided by the eight-tap Smith-Barnwell filter. We will see the effect of this when we look at image compression later in this chapter.

Figure 14.6. Magnitude transfer functions of the (a) eight-tap Johnston and (b) eight-tap Smith-Barnwell filters.

These filters are examples of some of the more popular filters. Many more filters exist in the literature, and more are being discovered.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124157965000144

Design Filter Using Iir Specific Cutoffs Etc

Source: https://www.sciencedirect.com/topics/computer-science/infinite-impulse-response-filter

Share this post