Electronics Guide

Fundamentals of FIR Filter Implementation

An FIR filter of length N is defined by its impulse response, the sequence of N coefficients commonly denoted h[0] through h[N − 1]. The output is the convolution of this impulse response with the input sequence: each output sample equals the sum of the products formed by multiplying the most recent N input samples by the corresponding coefficients,

y[n] = ∑_k=0^N−1 h[k] x[n − k]

where x[n − k] is the input delayed by k samples. Because each coefficient multiplies one delayed input, the transfer function is a polynomial whose coefficients are exactly the impulse response values:

H(z) = ∑_n=0^N−1 h[n] z⁻ⁿ = h[0] + h[1]z⁻¹ + … + h[N − 1]z^−(N−1)

The order of the filter is N − 1, one less than the number of taps, because the highest power of the delay operator appearing in the transfer function is z^−(N−1).

Written over a common denominator, the transfer function becomes a polynomial in z divided by z^N−1, so the filter's only poles are N − 1 poles at the origin of the z-plane, and poles at the origin contribute only delay. The absence of poles away from the origin is the structural reason FIR filters cannot become unstable: there is no feedback path through which an error or a quantized coefficient could drive the output to grow without bound.

The length of an FIR filter governs both the sharpness of the achievable frequency response and the computational cost. A longer impulse response permits narrower transition bands and deeper stopband attenuation, but each additional tap adds one multiplication and one addition per output sample along with one more delay element. The computational burden of FIR filtering, roughly proportional to filter length multiplied by sample rate, motivates both the symmetry exploitation and the multirate techniques described later.

Group delay, the negative derivative of the phase response with respect to frequency, τ(ω) = −dφ(ω)/dω, quantifies the time delay a filter imposes on each frequency component. When this delay is constant across frequency, the filter exhibits linear phase and introduces no phase distortion. For a linear-phase FIR filter of length N, the group delay equals (N − 1)/2 samples, a fixed latency that designers must account for in real-time and feedback systems. A 101-tap linear-phase filter running at 48 kHz, for example, delays every component by 50 samples, about 1.04 ms. When N is even the delay is a half-integer number of samples, which matters when a filtered signal must be realigned with an unfiltered one.

Direct Form

The direct form is the most immediate realization of the convolution sum, mapping the defining equation onto hardware or code without rearrangement. A chain of N − 1 delay elements holds the most recent input samples; each delayed sample is multiplied by its corresponding coefficient, and the products are summed to form the output. This structure is frequently called a tapped delay line or, in some communities, a transversal filter, because the signal is tapped at successive points along the delay chain.

The signal flow is easy to follow: the input enters the delay line, and at each sample instant the contents of the line are multiplied by the coefficient set and accumulated. The direct form requires N multipliers, N − 1 adders, and N − 1 storage registers for a length-N filter. Its correspondence to the impulse response is exact, so the coefficient values can be read directly from the design without transformation.

In software running on a digital signal processor, the direct form maps naturally onto the multiply-accumulate instruction that such processors execute in a single cycle. A loop steps through the coefficients and delayed samples, accumulating the running sum in a wide accumulator register. Circular addressing of the delay buffer avoids the cost of physically shifting samples, letting the processor advance a pointer instead of moving data.

The principal drawback of the direct form appears in high-speed hardware. The chain of adders that sums the products forms a long combinational path from the first product to the final output, and this path lengthens as the filter grows. Because the critical path limits the maximum clock frequency, the direct form can constrain throughput in long filters unless the adder tree is pipelined or the structure is transposed, as the next section describes.

Transposed Direct Form

The transposed direct form follows from applying the transposition theorem to the direct form. Reversing the direction of every signal path, exchanging the input and output nodes, and converting branch points into summing junctions yields a structure with an identical impulse response but a different internal organization. In the transposed form, the single input sample fans out to all the multipliers simultaneously, and the products are injected into a chain of adders interleaved with the delay registers.

This rearrangement shortens the critical path. Rather than a single sample propagating through a long cascade of adders within one sample period, each multiplier output enters its own adder, and the partial sums advance one stage along the delay chain at every sample instant. Because a register breaks the path between successive adders, the longest combinational path spans only one multiplier and one adder, independent of filter length. The transposed form therefore sustains higher clock rates and is the preferred structure for high-throughput hardware FIR filters.

This rearrangement also shapes the filter's finite-precision behavior. Rather than forming each output in a single accumulator, the transposed form distributes the summation across the internal delay registers, which hold running partial sums. The register at the far end of the chain holds a single product, while the one nearest the output holds a sum of N − 1 products whose magnitude can approach the full output range. In a fixed-point implementation each register must therefore be wide enough, with guard bits where needed, to prevent overflow, and a hardware design can taper the widths along the chain. The shorter critical path costs no latency: the current input still reaches the output through h[0] in the same sample period, because the transposed form moves the direct form's registers rather than adding new ones. Its costs are the wider internal registers and the broadcast of the input.

That broadcast is the other consideration for the transposed form: the input node must drive all N multipliers. In very long filters this high fan-out can introduce loading and routing challenges in hardware, sometimes requiring buffering of the input distribution network. Adaptive filters raise a further subtlety. Because each register holds partial sums formed with the coefficients in force when their products were computed, a coefficient update phases in over the next N − 1 outputs rather than taking effect at once. Despite these limitations, the dramatically shorter critical path makes the transposed form the standard choice when sample rate, rather than gate count, is the binding constraint.

Linear-Phase Realizations

The defining advantage of FIR filters over IIR filters is the ability to achieve exactly linear phase, and this property follows directly from symmetry in the impulse response. Two symmetry conditions give linear phase: symmetric coefficients, h[n] = h[N − 1 − n], and antisymmetric ones, h[n] = −h[N − 1 − n]. In the symmetric case the frequency response factors into a real amplitude function A(ω) and a pure delay:

H(e^jω) = A(ω) e^{−jω(N−1)/2}

The sign changes of A(ω) add jumps of 180 degrees at the zeros of the response, but between them the phase falls linearly with frequency at a rate of (N − 1)/2 samples, the group delay given above. The antisymmetric case multiplies the response by j as well, adding a constant 90 degrees to the same linear phase. The four canonical types of linear-phase FIR filter correspond to the two symmetry conditions combined with even or odd filter length.

Symmetry permits a structural economy that directly halves the number of multipliers. Because coefficients at mirror-image positions are equal in magnitude, the two corresponding delayed samples can be added together before the single shared multiplication, rather than multiplied separately and summed afterward. For even N the convolution sum becomes

y[n] = ∑_k=0^N/2−1 h[k] (x[n − k] + x[n − N + 1 + k])

so a symmetric filter of length N requires N/2 multipliers when N is even and (N + 1)/2 when N is odd, instead of N. The number of additions does not change, since for even N the N/2 pre-additions and N/2 − 1 accumulations total N − 1, as in the direct form. The saving is therefore significant in both hardware area and software cycles, since multiplication is typically the most expensive operation, and its main arithmetic cost is that each pre-added sum needs one more bit than a single sample.

The folded direct form realizes this economy. The delay line is conceptually folded about its center so that each pair of symmetric taps meets at a single adder, whose sum then feeds the shared coefficient multiplier. For odd-length symmetric filters the center tap, which has no mirror partner, retains its own multiplier. Antisymmetric filters use subtraction rather than addition at the folding junctions, reflecting the sign reversal between mirrored coefficients. In an odd-length antisymmetric filter the center coefficient must equal its own negative and is therefore zero, leaving (N − 1)/2 multipliers.

The four linear-phase types differ in the zeros their symmetry forces, and those zeros dictate the responses each can implement. Type I, symmetric with odd length, forces none and can realize lowpass, highpass, bandpass, and bandstop responses alike. Type II, symmetric with even length, forces a zero at the Nyquist frequency, z = −1, so it cannot realize a highpass or bandstop response. Both antisymmetric types force a zero at zero frequency, z = 1, and Type III, antisymmetric with odd length, forces a second zero at the Nyquist frequency. Their built-in 90-degree phase offset makes the antisymmetric types the natural basis for differentiators and Hilbert transformers: Type IV, antisymmetric with even length, suits a full-band differentiator, whose gain must keep rising up to the Nyquist frequency, while Type III suits a Hilbert transformer, whose response may fall away at both band edges.

Cascade Form

The cascade form realizes an FIR filter as a series connection of shorter sections, typically second-order, by factoring the transfer function polynomial into the product of lower-degree polynomials. Each second-order section implements a pair of zeros, and chaining the sections reconstructs the full set of zeros that defines the filter's frequency response. This structure parallels the cascade decomposition used for IIR filters, though the absence of poles removes the stability concerns that dominate the recursive case.

Factoring the polynomial requires finding its roots, the zeros of the transfer function, and grouping them into real-coefficient sections. Complex zeros, which occur in conjugate pairs for a real impulse response, combine into second-order sections with real coefficients. Real zeros pair with one another or stand alone in first-order sections. Linear-phase filters add a mirror-image pattern about the unit circle: a symmetric or antisymmetric coefficient set is, apart from sign, its own reversal, so every zero is matched by one at its reciprocal. A complex zero off the unit circle therefore brings three companions, its conjugate and the reciprocals of both, and the four together form a symmetric fourth-order section. A conjugate pair on the unit circle, or a real zero and its reciprocal, forms a symmetric second-order section, and a zero at z = 1 or z = −1 a first-order one. Grouping the zeros this way keeps every section linear-phase, and with it the whole cascade.

The cascade form can improve coefficient sensitivity for filters with sharp frequency-response features. In a long direct-form filter, quantizing a single coefficient perturbs every zero of the transfer function, because all the zeros are encoded jointly in the coefficient set. In the cascade form, each section's coefficients determine only that section's zeros, so quantization error remains localized and the displacement of any zero depends only on the precision of its own section. Stopband nulls benefit most. A section 1 − 2cos θ z⁻¹ + z⁻², which places a conjugate pair of zeros on the unit circle at angle θ, keeps them exactly on the circle after quantization: its outer coefficients are exactly 1, so the product of its two zeros stays 1, and quantizing the middle coefficient only slides the null to a nearby frequency.

These benefits carry costs that limit the use of the cascade form in routine FIR design. Factoring a high-order polynomial into accurate second-order sections is itself a numerically delicate computation, and the cascade requires intermediate scaling between sections to control dynamic range. For most FIR applications the direct or transposed forms suffice, and the cascade form is reserved for cases where coefficient sensitivity in a critical, sharply tuned response justifies the additional complexity.

Lattice Structures

Lattice structures realize FIR filters through a cascade of stages parameterized by reflection coefficients rather than by the impulse response values directly. Each stage m propagates a pair of signals, conventionally termed the forward and backward prediction errors f_m[n] and g_m[n], and cross-couples them through a single reflection coefficient k_m:

f_m[n] = f_m−1[n] + k_mg_m−1[n − 1]

g_m[n] = k_mf_m−1[n] + g_m−1[n − 1]

Both signals start as the input, f₀[n] = g₀[n] = x[n], and the forward output of the last stage is the filter output. Adding stages raises the filter order, and a lattice of m stages realizes a polynomial A_m(z) of order m whose leading coefficient is 1, so a general filter needs one more multiplier for its overall gain h[0]. Each stage extends the previous polynomial by the step-up recursion

a_m[i] = a_m−1[i] + k_ma_m−1[m − i]

which makes the last coefficient a_m[m] equal to k_m. Running the recursion backward recovers the reflection coefficients from a set of direct-form coefficients, one stage at a time:

a_m−1[i] = (a_m[i] − k_ma_m[m − i]) / (1 − k_m²)

This step-down recursion explains why the standard lattice cannot realize a linear-phase filter. Normalized so that h[0] = 1, a symmetric or antisymmetric coefficient set has a last coefficient of ±1, so its final reflection coefficient is ±1 and the recursion divides by zero at its first step. Specially derived lattice variants exist for linear-phase filters, but the folded direct form is the usual choice.

The lattice form arises naturally from linear prediction and the theory of autoregressive signal modeling, where the reflection coefficients carry direct physical and statistical meaning. In speech processing, for example, the reflection coefficients of a lattice predictor correspond, in the lossless acoustic-tube model of the vocal tract, to the reflection of acoustic waves at the junctions between tube sections of different cross-sectional area, giving the structure an interpretation grounded in the physics of sound production.

A valuable property of the FIR lattice is that it produces the prediction-error filters of every order from one through the full order simultaneously, available at the successive stage outputs. When the lattice whitens the signal its coefficients were computed from, each stage lowers the prediction-error power by a factor of 1 − k_m², so the successive outputs show how much each added order improves the prediction. This order-recursive character suits applications that must adapt the filter length or that exploit predictors of several orders at once. Adaptive algorithms can adjust the reflection coefficients stage by stage, and the modular structure accommodates changes in order without reworking the entire filter.

The lattice form also has attractive finite-wordlength properties. A lattice whose reflection coefficients all satisfy |k_m| < 1 realizes a minimum-phase filter, with every zero inside the unit circle, and a quantized coefficient that stays within that range cannot destroy the property. This is the FIR counterpart of the stability guarantee that the same condition gives a recursive all-pole lattice. The two-multiplier lattice does not, however, balance its internal signal levels by itself: each stage can raise the peak signal magnitude by up to a factor of 1 + |k_m|, so a fixed-point lattice needs scaling like any other structure. The balanced internal levels often credited to lattice filters belong to the normalized lattice described for IIR filter structures, which spends four multiplications per stage. The arithmetic cost is higher in any case. A lattice for an N-tap filter has N − 1 stages and performs 2(N − 1) multiplications, plus one for the gain, and 2(N − 1) additions per output sample, against N multiplications and N − 1 additions for the direct form. The lattice is therefore favored where its adaptive and order-recursive properties justify the additional computation, rather than as a general-purpose realization.

Polyphase Decomposition and Multirate Processing

Polyphase decomposition reorganizes an FIR filter into a set of parallel subfilters, each operating on a different phase of the input sequence. The impulse response is partitioned by splitting its coefficients into subsequences according to their position modulo the rate-change factor M: the kth polyphase component collects h[k], h[k + M], h[k + 2M], and so on, forming a subfilter about N/M taps long. Reassembling the components reproduces the original filter,

H(z) = ∑_k=0^M−1 z^−k E_k(z^M)

where E_k(z) is the transfer function of the kth component. Evaluating a component at z^M spreads its coefficients M samples apart, and the factor z^−k restores its offset. The decomposition changes nothing in the response, but it exposes a structure that maps efficiently onto multirate systems.

The decisive benefit of the polyphase form appears in decimation and interpolation, the operations that reduce or increase a signal's sample rate. A decimator filters a signal and then discards samples to lower the rate; an interpolator inserts zero samples to raise the rate and then filters to remove the resulting spectral images. Performing the filtering at the higher rate and then discarding or inserting samples wastes computation, because many of the multiplications either produce results that are thrown away or operate on inserted zeros.

The polyphase identities eliminate this waste by exchanging the order of filtering and rate change. In a polyphase decimator by M, each component runs at the output rate on every Mth input sample, so the filter computes only the output samples that survive the downsampling: N multiplications per output rather than N per input sample. In a polyphase interpolator, the subfilters compute outputs only from the genuine input samples, never multiplying by the inserted zeros. The arithmetic rate of the filter consequently drops in proportion to the rate-change factor, a saving that makes high-ratio sample-rate conversion practical.

Polyphase structures underpin the filter banks and multirate cascades that pervade modern signal processing. Sample-rate converters between audio standards, the channelizers that separate a wideband signal into many narrowband channels in communications receivers, and the analysis and synthesis banks of subband coders all rely on polyphase decomposition to keep their computational cost within practical bounds. The technique also enables efficient fractional sample-rate changes by combining interpolation and decimation factors. Converting 44.1 kHz audio to 48 kHz, for example, is a rational change of 160/147, interpolation by 160 followed by decimation by 147, and a polyphase converter computes each output directly from the one subfilter it needs, never running at the intermediate rate of 7.056 MHz.

Symmetry Exploitation

Beyond the linear-phase folding already described, FIR implementations exploit several forms of structure in the coefficient set to reduce arithmetic cost. The dominant case remains coefficient symmetry, which halves the multiplier count by adding mirror-image samples before a single shared multiplication. The saving carries over to the transposed form, where the two taps of a symmetric pair see the same input sample and can share one multiplier without a pre-adder, and, with more bookkeeping, to polyphase realizations: the polyphase components of a symmetric filter form mirror-image pairs, so samples from two branches can be pre-added before a shared multiplication.

Certain specialized FIR filters possess additional structure that permits multiplications to be avoided altogether. A half-band filter, used heavily in two-to-one rate conversion, has every other coefficient equal to zero apart from the center tap, so nearly half of the taps require no computation, and the center tap is normally exactly 1/2, a shift rather than a multiplication. Combining this property with linear-phase symmetry reduces the effective multiplier count to roughly a quarter of the filter length. A 23-tap half-band filter, for example, has 12 non-zero coefficients besides the center tap, and symmetry pairs them into 6 distinct values, so it needs 6 multiplications per output where a general 23-tap filter needs 23. That economy makes half-band filters the standard building block for the power-of-two rate changes common in audio, communications, and image processing.

When coefficients can be chosen as sums of a small number of signed powers of two, the multiplications reduce to shifts and additions, eliminating general-purpose multipliers entirely. Canonical signed digit (CSD) encoding, which uses the digits 1, 0, and −1 and never places two non-zero digits side by side, minimizes the number of such terms, and a coefficient with w non-zero digits costs w − 1 additions or subtractions. The coefficient 7/16, binary 0.0111, has three non-zero bits and would take two additions, but its CSD form 1/2 − 1/16 takes a single subtraction of two shifted copies of the input. Such representations are valuable in custom hardware and low-power designs, where multiplierless FIR filters trade a modest increase in adder count and a slight perturbation of the frequency response for a substantial reduction in silicon area and energy. Design procedures jointly optimize the coefficient values and their power-of-two encoding to meet the response specification under the multiplierless constraint.

Exploiting symmetry and sparsity interacts with the choice of structure and with fixed-point design. Folding for symmetry changes the order of additions and therefore the points at which intermediate results must be scaled to prevent overflow, while multiplierless designs fix the coefficient values to a quantized grid that the wordlength analysis must respect. Effective implementations consider these structural economies together with the finite-precision concerns examined next.

Fixed-Point Considerations

Although FIR filters cannot become unstable, their accuracy in fixed-point arithmetic depends on careful management of coefficient precision, signal scaling, and rounding. Coefficient quantization rounds each ideal coefficient to the nearest value representable in the chosen wordlength, perturbing the frequency response. The perturbation typically manifests as a rise in the stopband floor and small ripples in the passband, because the displaced zeros no longer fall exactly where the design placed them. Quantizing a symmetric coefficient set symmetrically at least preserves linear phase, since the quantized coefficients remain symmetric. Longer wordlengths reduce the error, and the required precision scales with the severity of the stopband specification.

Signal scaling prevents the accumulating sum from exceeding the representable range. Because the output of an FIR filter is a sum of N products, its magnitude can substantially exceed that of any single input sample. If X_max is the largest input magnitude, the worst case is bounded by the sum of the absolute values of the coefficients:

|y[n]| ≤ X_max ∑_k=0^N−1 |h[k]|

When the sum exceeds 1, its base-2 logarithm, rounded up, gives the number of extra integer bits the output needs to hold the worst case. Designers scale either the coefficients or the input so that this worst-case sum, or a less conservative statistical estimate of it, remains within the numeric range, trading headroom against the signal-to-quantization-noise ratio.

Rounding and truncation introduce noise when products or sums are reduced to the available wordlength. Under the usual model of independent rounding errors, each rounding to a step q adds an error of variance q²/12, so rounding every one of the N products before accumulation gives an output noise variance of Nq²/12. A practical and widely used strategy instead accumulates all products at full precision in a wide accumulator and rounds only the final result, confining quantization to a single step at the output. That leaves q²/12, lower by 10 log₁₀(N) dB, which is 20 dB for a 100-tap filter. Digital signal processors support this directly by providing accumulators with guard bits that hold the extended-precision sum without overflow during the multiply-accumulate sequence. Many 16-bit fixed-point processors, for example, provide 40-bit accumulators: 32 bits hold a full 16-by-16-bit product, and the 8 guard bits above them allow 256 full-scale products to be summed without overflow.

The non-recursive structure of FIR filters gives them a decisive advantage in finite-precision behavior. With no feedback path, quantization errors from each multiplication contribute independently to the output and cannot be recirculated and amplified, so FIR filters are free of the limit cycles and noise feedback that complicate IIR implementation. The output noise is simply the sum of the independent rounding errors, which makes its level straightforward to predict and bound. This predictability, together with guaranteed stability and exact linear phase, accounts for the preference for FIR filters wherever their higher computational cost can be afforded.

Summary

FIR filter structures realize the same convolution through different arrangements of multipliers, adders, and delay elements, each suited to particular goals. The direct form maps the convolution sum onto multiply-accumulate hardware most transparently, while the transposed form shortens the critical path for high-throughput implementations. Linear-phase realizations exploit coefficient symmetry to halve the multiplier count and to guarantee the constant group delay that distinguishes FIR filters from their recursive counterparts. Cascade structures localize the effect of coefficient quantization, lattice structures serve adaptive and order-recursive applications, and polyphase decomposition makes multirate decimation and interpolation efficient by computing only the samples that are actually used.

The choice among these structures balances computational cost, throughput, and numerical accuracy against the demands of the target platform and the symmetry of the coefficient set. Because FIR filters carry no feedback, they remain unconditionally stable and free of limit cycles, and their fixed-point design reduces to controlling coefficient precision, signal scaling, and a single well-placed rounding step. These properties, combined with the structural economies that symmetry and multirate decomposition provide, make FIR filters a dependable foundation for linear-phase filtering throughout signal processing, communications, audio, and instrumentation.

Related Topics