Electronics Guide

Direct Form I Structure

The direct form I FIR filter consists of a tapped delay line followed by coefficient multipliers and a summing tree or chain. For an N-tap filter, N − 1 delay elements hold the most recent input samples, N multipliers apply the filter coefficients, and an adder combines the products to produce the output. Each sample period, a new input sample enters the delay line, the oldest sample exits, and the convolution sum is computed.

The delay line implementation significantly impacts performance and resource utilization. A shift register approach physically moves data through cascaded registers at each clock cycle, requiring N − 1 write operations per sample. Circular buffer implementations instead use a pointer that advances through a fixed memory, avoiding data movement but requiring address computation. The choice depends on the implementation technology, with shift registers favoring FPGAs and circular buffers favoring processors with addressing hardware.

The coefficient multipliers dominate resource utilization in most direct form implementations. Each multiplier must compute the product of a sample (typically 12 to 24 bits) with a coefficient (commonly 16 to 18 bits in hardware, to fit the 18-bit multiplier inputs of many FPGA DSP blocks, and often wider in software), requiring significant silicon area or computational cycles. For fixed-coefficient filters, the multipliers can be optimized for the specific coefficient values, potentially reducing complexity compared to general-purpose multipliers.

The accumulation of multiplier outputs presents its own challenges. A simple sequential addition chain introduces significant latency and limits clock frequency. Tree structures reduce latency to logarithmic in the number of taps but increase routing complexity. Pipelined adder trees achieve high throughput by inserting registers between adder stages, trading latency for clock speed. The accumulator word width must accommodate the worst-case sum without overflow. Summing N full-precision products of B_x-bit samples and B_h-bit coefficients needs at most B_x + B_h + log₂(N) bits, with the logarithm rounded up: no more than 38 bits for a 64-tap filter with 16-bit samples and coefficients. Because the output magnitude can never exceed the largest input magnitude times the sum of the coefficient magnitudes, a bound based on that sum is often a few bits tighter.

Direct Form II and FIR Filters

Direct form II is a canonical structure defined for recursive (IIR) filters, where it minimizes the number of delay elements by sharing a single delay line between the feedforward (numerator) and feedback (denominator) sections. A pure FIR filter has no feedback path and therefore no denominator, so this delay-sharing optimization has nothing to share. For this reason, a genuine direct form II FIR filter is structurally identical to direct form I; the term carries no distinct meaning in the all-zero case, and FIR realizations are normally described simply as direct form versus transposed (or transposed direct) form.

This distinction matters because the literature occasionally uses "direct form II" loosely to refer to the transposed direct form, which is a genuinely different FIR structure rather than the IIR canonical form. The two should not be conflated. The transposed direct form reverses the signal flow of direct form I, multiplying the current input by every coefficient simultaneously and accumulating the products through a chain of delays. It is the principal high-speed alternative to direct form I and is treated in detail in the next section.

The practical consequence is that an FIR designer chooses between direct form and transposed direct form, not between direct form I and direct form II. The transposed direct form shortens the critical path to a single multiplier and adder, while direct form I keeps delay-line word widths at the input precision. The dedicated treatment that follows compares these two forms directly, including their timing, precision, and adaptation characteristics.

Linear Phase Exploitation

FIR filters with symmetric coefficients, those designed for linear phase response, offer significant optimization opportunities. When coefficients satisfy h[k] = h[N − 1 − k], pairs of multiplications involve identical coefficients applied to different samples. By adding the corresponding input samples before multiplication, the number of multiplications reduces by nearly half.

An N-tap symmetric filter needs only N/2 multipliers instead of N when N is even, and (N + 1)/2 when N is odd. The architecture first adds pairs of samples from opposite ends of the delay line, then multiplies these sums by the shared coefficients. For odd-length filters, the center coefficient multiplies a single sample without pairing. This optimization approximately halves the multiplier count without affecting the filter response.

The pre-addition of sample pairs requires careful attention to word width. The sum of two samples requires one additional bit compared to individual samples, which propagates through the multiplication and accumulation stages. The overall savings in multipliers generally outweigh the modest increase in adder width, making symmetric exploitation nearly universal in linear phase FIR implementations.

Antisymmetric filters, where h[k] = −h[N − 1 − k], enjoy similar optimization through subtraction rather than addition of sample pairs. These filters, used for differentiators and Hilbert transformers, achieve the same multiplier reduction with minor architectural modifications. For odd N the center coefficient of an antisymmetric filter must equal its own negative and is therefore zero, so only (N − 1)/2 multipliers remain.

Pipelining and Retiming

Pipelining inserts registers into the combinational paths of a filter, breaking long paths into shorter segments that can operate at higher clock frequencies. For direct form FIR filters, pipeline registers are typically placed after multipliers and between adder stages. The number of pipeline stages determines both the maximum clock frequency and the filter latency.

Retiming redistributes existing registers within a circuit to balance path delays without changing functionality or adding latency. Applied to FIR filters, retiming can move registers from the delay line into the adder chain, shortening the critical path without adding registers. Automatic retiming tools can optimize register placement for maximum clock frequency, though manual analysis often achieves better results for regular structures like FIR filters.

The latency introduced by pipelining must be considered in system design. A fully pipelined N-tap filter with P pipeline stages introduces a latency of P clock cycles beyond the inherent filter delay. For real-time systems with tight latency constraints, the designer must balance throughput improvements against the additional delay.

Both operations are defined on cut-sets of the datapath graph, sets of edges whose removal splits the graph in two. Feed-forward cut-set pipelining places one new register on every edge of a cut-set whose edges all cross in the same direction, adding one stage of latency. Cut-set retiming instead adds registers to the edges crossing one way and removes the same number from the edges crossing the other way, leaving the latency unchanged.

Which transformation applies to a direct form filter depends on the direction of its adder chain. If the chain runs back toward the input end, each cut between adjacent taps crosses the delay line one way and the adder chain the other, and retiming every such cut moves each delay-line register into the adder chain, yielding the transposed form described in the next section. If the chain runs the same way as the delay line, the cuts are feed-forward, and pipelining every one of them gives the systolic form, with two registers per tap on the sample path and one on the partial-sum path. The regularity of FIR structures makes them particularly amenable to both transformations.

Structure and Operation

In the transposed form, each filter coefficient multiplies the current input sample, producing N products simultaneously for an N-tap filter. These products feed into a cascade of adders, with delay elements between stages. The first product enters the cascade directly, while subsequent stages receive new products plus delayed sums from previous stages. The final stage output is the filter result.

The signal flow processes data in the opposite direction from direct form. Where direct form delays input samples and sums weighted current values, transposed form delays partial sums and adds weighted input values. Mathematically, both produce identical outputs, as they implement the same convolution equation with rearranged computation order.

The critical timing path in transposed form contains just one multiplier and one adder, significantly shorter than the multi-adder path potentially present in direct form accumulation. This inherent pipelining makes transposed form attractive for high-frequency implementations without explicit pipeline register insertion. The structure naturally achieves throughput that direct form would require multiple pipeline stages to match.

Each delay element in the transposed structure holds a partial sum rather than an input sample. These partial sums accumulate products from multiple input samples, requiring word widths adequate to prevent overflow. The accumulation grows progressively through the chain, with early stages needing fewer bits than later stages. Tapered word widths can reduce register resources while maintaining accuracy.

Broadcast Input Distribution

The transposed form broadcasts the input sample to all coefficient multipliers simultaneously. This high fanout can limit clock frequency if the input distribution network introduces significant delay. Careful physical design and potential registering of the broadcast signal ensure that input distribution does not become the critical path.

Modern FPGAs and ASICs include dedicated routing resources that efficiently distribute high-fanout signals. Clock networks, designed for similar broadcast requirements, provide a model for input distribution in transposed form filters. Leveraging these resources enables high-frequency operation despite the inherent fanout requirements.

Because every multiplier sees the same input sample, all the products for that sample are formed together, but they reach the output at different times: the product formed with coefficient h[k] emerges k samples later. This matters for adaptive filters. When the coefficients change, the partial sums already in the registers were formed with the old values, so an update phases in over the next N − 1 outputs instead of taking effect at once. The direct form re-forms every product from stored samples for each output and applies a new coefficient set immediately. An adaptive filter built on the transposed form for its speed must tolerate this mixed-coefficient transient, which behaves much like additional delay in the adaptation loop.

Comparison with Direct Form

The transposed form offers inherently higher clock frequencies due to its shorter critical path. Without explicit pipelining, transposed form typically operates faster than direct form. This advantage is most pronounced for filters with many taps, where direct form accumulation paths become increasingly long.

Resource utilization differs subtly between forms. Both require the same number of multipliers and delay elements, but the delay element contents differ in word width. Direct form delays store input samples at input precision, while transposed form delays store partial sums requiring extended precision. For filters with high precision requirements, this difference can make transposed form more resource-intensive.

Symmetric coefficient exploitation takes a different shape in the transposed form. Because every multiplier sees the same input sample, the two taps of a symmetric pair produce identical products, so one multiplier can feed both of the pair's adders. The multiplier count halves without the direct form's pre-adders or the extra bit they require; the cost is that each shared product must be routed to two points along the adder chain.

Initial state and reset behavior also differ. Both forms hold N − 1 words of state, and either can be cleared by a reset or flushed by feeding N − 1 zero samples. The direct form's state, however, is a plain history of past inputs, which can be saved and preloaded, for example to continue filtering a block from a stored context. The transposed form's state is a set of partial sums that depend on the coefficients as well as the data.

Systolic Array Principles

A systolic array consists of identical processing elements (PEs) connected in a regular pattern, typically linear or two-dimensional. Data flows through the array in synchronized waves, with each PE performing a simple operation on data it receives and passing results to neighbors. The regular structure and local connectivity enable efficient implementation and high-speed operation.

Key characteristics of systolic arrays include modularity, where the same PE design replicates throughout the array; locality, where each PE communicates only with immediate neighbors; and pipelining, where data continuously flows through the array without global synchronization. These properties enable scaling to large array sizes while maintaining timing closure.

For FIR filtering, systolic arrays can process one sample per clock cycle regardless of filter length, achieving throughput limited only by clock frequency rather than computational resources. The parallelism is inherent in the architecture, not requiring explicit parallelization of the algorithm.

Weight-Stationary Systolic FIR

In the weight-stationary systolic architecture, filter coefficients remain fixed in the processing elements while input samples flow through the array. Each PE contains one coefficient value and performs a multiply-accumulate operation: multiplying its coefficient by the arriving sample and adding to the accumulated result from the previous PE.

Input samples enter the array one per clock cycle at the first PE and propagate through the array, visiting each coefficient in sequence. Partial sums flow in the same direction, accumulating products as they pass through successive PEs. For each partial sum to meet the right sample at every PE, the two streams must move at different speeds: a common arrangement gives the sample path two registers per PE and the partial-sum path one. The final PE outputs the complete filter result for each input sample.

Each partial sum takes about N clock cycles to traverse an N-tap array, so the output appears with a latency of roughly the filter length. However, new samples enter every clock cycle, maintaining throughput of one sample per clock. The array holds N outputs in progress simultaneously, each at a different stage of accumulation.

Coefficient updates require loading new values into all PEs, a process that may interrupt continuous filtering. For adaptive filters requiring frequent coefficient changes, the weight-stationary architecture may need additional mechanisms for background coefficient loading. The architecture is most suitable for fixed-coefficient filters or those with infrequent adaptation.

Output-Stationary Systolic FIR

The output-stationary systolic architecture keeps each output sample's partial sum stationary in a single processing element while the operands flow past it. In a common variant, the current input sample is broadcast to all PEs while the coefficients circulate through the array, advancing one position per clock cycle; each PE then multiply-accumulates the broadcast sample with whichever coefficient is presented to it that cycle. Every PE is thus responsible for one output sample rather than one coefficient, and once all of its contributing products have accumulated it holds a complete result, which is read out as the next output begins to form.

This architecture inverts the data flow pattern of weight-stationary design. Rather than samples flowing through the array, samples arrive everywhere simultaneously while results accumulate locally. The broadcast requirement limits scalability but simplifies the accumulation structure.

The chief advantage of keeping each partial sum local is energy efficiency: an output is written out only once, when its accumulation completes, rather than being read and rewritten as it moves along a partial-sum chain. This makes output-stationary dataflow attractive where memory and register-file traffic dominate power. The trade-off is the cost of supplying every processing element with the correct operand on every cycle, which the broadcast network must sustain.

The broadcast input distribution represents the main scaling challenge. High fanout to many PEs can limit clock frequency and consume routing resources. Hybrid approaches distribute input through a tree structure, balancing broadcast efficiency against pure output-stationary operation.

Two-Dimensional Systolic Arrays

Two-dimensional systolic arrays extend the linear concept to process multiple data streams or implement multiple filters simultaneously. Samples can flow in one dimension while coefficients or partial results flow in another, enabling complex filtering operations within a single array structure.

One application of 2D systolic arrays is parallel filtering of multiple input channels. Each row of PEs implements one filter while columns handle different channels. The regular structure efficiently utilizes FPGA or ASIC resources while achieving throughput proportional to array size.

Matrix-vector multiplication, which generalizes FIR filtering, maps naturally to 2D systolic arrays. This formulation enables efficient implementation of multiple filters with different coefficients operating on the same input, as required in filter bank applications. The 2D structure processes all filters simultaneously, accepting one input sample per clock cycle.

The interconnect complexity of 2D arrays can challenge physical implementation. Regular mesh connections between neighboring PEs must handle the required data widths while meeting timing constraints. Modern FPGAs provide dedicated cascade connections between adjacent DSP blocks within a column, which suit one dimension of such an array; the other dimension relies on general-purpose routing.

Systolic Array Efficiency

Systolic arrays achieve high computational efficiency by keeping all PEs active on every clock cycle. Unlike sequential implementations where hardware utilization varies with algorithm phase, systolic arrays maintain constant utilization once the pipeline fills. This efficiency translates to superior throughput per unit of hardware resources.

Power consumption in systolic arrays benefits from local data movement. Rather than global buses transferring data across the chip, systolic architectures move data only between adjacent PEs. This locality reduces capacitive loading and switching activity, improving energy efficiency compared to architectures with longer data paths.

The regular structure of systolic arrays simplifies timing analysis and physical design. Identical paths between PEs enable straightforward timing closure, while the repetitive layout can leverage array-based placement tools. These characteristics reduce design effort and improve design quality compared to irregular architectures.

Scalability is inherent in systolic design. Adding more PEs increases filter length or parallel channels without architectural changes. The same PE design works for small and large arrays, enabling design reuse across product families with different performance requirements.

Fundamental Concept

Consider the inner product of coefficient vector h with input vector x, the fundamental FIR computation. Expressing each input sample in binary as a sum of weighted bits, the inner product becomes a sum of inner products of the coefficient vector with single-bit vectors. Each single-bit inner product selects certain coefficients (those corresponding to 1 bits) for summation.

For N coefficients and B-bit input samples, there are 2^N possible single-bit inner products, corresponding to all possible combinations of which coefficients to include. By precomputing these sums and storing them in a lookup table, the inner product reduces to B table lookups (one per bit position) and a weighted sum of the lookup results.

The lookup table address is formed by collecting one bit from each input sample. For bit position b, the address concatenates the bth bit of all N samples, forming an N-bit address that indexes into the 2^N-entry table. The table output is the sum of coefficients corresponding to 1 bits in the address.

The weighted accumulation of lookup results accounts for the binary weights of each bit position. Results from higher-order bits contribute more heavily than lower-order bits, with bit position b weighted by 2^b, except that the sign bit of a two's complement number carries negative weight. For B-bit samples the output is therefore

y = −2^B−1 T_B−1 + ∑_b=0^B−2 2^b T_b

where T_b, the table entry addressed by bit slice b, is the sum of the coefficients whose samples have a 1 in bit position b. In serial form this accumulation usually proceeds from the least significant bit (LSB) to the most significant bit (MSB), the order in which bit-serial data arrives, so the sign-bit term comes last.

Serial Distributed Arithmetic

The serial distributed arithmetic architecture processes one bit position per clock cycle, requiring B cycles to complete one filter output. Each cycle, a new table lookup occurs using the current bit slice across all input samples, and the result is shifted and accumulated with previous partial results.

With the bits arriving LSB first, the accumulator is shifted right by one place (halved) before each new lookup result is added, so every earlier, less significant contribution is scaled down by one more factor of two; equivalently, each new result can be shifted left by its bit position before it is added. The final lookup, taken on the sign bits, is subtracted rather than added, accounting for the negative weight of the sign bit. After B cycles the right-shifting accumulator holds the inner product scaled by 2^−(B−1), which corresponds to treating the samples as fractions, and the bits shifted out are kept if full precision is needed. An MSB-first design instead doubles the accumulator before each addition, and the sign-bit term it subtracts then comes first.

Resource utilization in serial DA includes one lookup table of 2^N entries, N shift registers that present the sample bits, and one accumulator with shift capability. The lookup table size grows exponentially with filter length, potentially becoming impractical for long filters. Table partitioning techniques address this limitation by decomposing the filter into smaller sections, each with its own table.

Throughput of serial DA is limited to one output per B clock cycles, well below the one output per clock of a fully parallel direct form. This trade-off favors applications where the sample rate is relatively low, the filter is short enough for reasonable table sizes, and multiplier resources are scarce or expensive. Audio processing often fits these criteria well.

Parallel Distributed Arithmetic

Parallel DA performs all bit position lookups simultaneously, producing filter outputs in a single clock cycle. This requires B parallel lookup tables, each addressed by a different bit slice of the input samples. The results are weighted by their bit positions and summed to produce the final output.

The weighted summation in parallel DA uses a combination of shifters and an adder tree. Each lookup result shifts left by its bit position (0 for the LSB through B − 1 for the MSB) before entering the adder tree. The sign bit path includes negation before addition. The complete structure produces throughput equal to one sample per clock cycle.

Resource requirements multiply compared to serial DA: B tables of 2^N entries each, plus the shifting and addition logic. This substantial resource investment is justified when high throughput is essential and multipliers are the limiting resource. FPGAs, whose logic is itself built from small lookup tables and which also provide block RAM, make parallel DA practical for short filters or partitioned tables.

Hybrid serial-parallel implementations offer intermediate trade-offs. Processing K bits per cycle requires K copies of the table and B/K cycles per output, with K chosen to divide B. For 16-bit samples, K = 2 needs two tables and eight cycles per output, and K = 4 needs four tables and four cycles. The designer can select K to balance throughput requirements against available memory resources.

Table Partitioning

For filters with many taps, the 2^N table size becomes prohibitive. Partitioning the filter into smaller groups addresses this limitation by using multiple smaller tables whose results are summed. For a 64-tap filter partitioned into 8 groups of 8 taps each, eight 256-entry tables replace one impractical 2⁶⁴-entry table.

Partitioning introduces additional adders to sum the partial results from each table. The total computation becomes P table lookups plus P − 1 additions per bit position, where P is the number of partitions; the 64-tap example needs eight lookups and seven additions. The additional additions represent modest overhead compared to the dramatic table size reduction.

Optimal partition size balances table size against adder overhead. Very small partitions use minimal memory but require many additions. Very large partitions minimize additions but may exceed available memory. Analysis for specific target architectures determines the optimal partition size.

Symmetric coefficient filters offer partitioning advantages. By adding symmetric sample pairs before table lookup, an N-tap symmetric filter needs table inputs for only N/2 taps when N is even, or (N + 1)/2 when N is odd. This effectively halves the apparent filter length, reducing table requirements or enabling larger partitions, at the cost of one extra bit in each pre-added sum and so one extra cycle in serial DA.

Offset Binary Coding

Offset binary coding (OBC), set out in Stanley White's tutorial review of distributed arithmetic in IEEE ASSP Magazine in July 1989, halves the lookup table. It rewrites each two's complement sample as half the difference between the sample and its own negation, x = [x − (−x)] / 2. Since −x is the bitwise complement of x plus one in the least significant place, every bit position of that difference carries a digit of +1 or −1 rather than 1 or 0, and a single constant term absorbs the extra least significant one.

With every digit equal to +1 or −1, the table entry for a bit slice is half a signed sum of all N coefficients, and complementing every address bit exactly negates the entry. The table is therefore antisymmetric, and only half of it, 2^N−1 entries, need be stored. The bit of one chosen sample decides whether the stored value is added or subtracted, and the other N − 1 bits, complemented or not according to that bit, form the address.

The rest of the arithmetic keeps its form. The sign-bit term still carries negative weight, and the constant term, minus half the sum of the coefficients at the weight of the least significant bit, depends only on the coefficients. It is computed once and preloaded into the accumulator, adding no work at run time.

The price of the halved table is an accumulator adder that can also subtract, plus a few gates on the table address. Combined with partitioning, the saving applies to every partition's table. A simpler alternative, converting each sample to ordinary offset binary by inverting its sign bit, turns it into an unsigned number offset by 2^B−1. That removes the sign-bit subtraction at the cost of a constant correction, but leaves the table at full size.

CSD Fundamentals

Any integer can be represented in CSD form with digits that are never adjacent when non-zero. This property arises from the recoding rule that converts binary sequences like "011" to "101" in signed digit form (meaning 1, 0, −1 for digit values). The recoding never increases the number of non-zero digits and often reduces it substantially.

For long words the fraction of non-zero CSD digits approaches one-third, compared to one-half for standard binary. Averaged over all 16-bit values, CSD needs between 5 and 6 non-zero digits against 8 set bits in plain binary. A product whose multiplier has w non-zero digits takes w − 1 additions or subtractions, so CSD reduces the additions needed to implement coefficient multiplication.

The CSD form of any number is unique, unlike other signed digit representations, and no signed-digit form of the number has fewer non-zero digits, a minimality George Reitwiesner established in 1960. This uniqueness simplifies tools and analysis, as there is exactly one CSD encoding for each coefficient value. Conversion algorithms efficiently transform binary or decimal coefficients to CSD form.

For FIR implementation, each coefficient multiplication becomes a sequence of shift-and-add operations corresponding to the non-zero CSD digits. A digit value of +1 at position k contributes (input shifted left by k); a digit value of −1 contributes the negative of this shifted value. Summing all non-zero digit contributions yields the product.

Multiplierless Architectures

CSD enables FIR filters without dedicated multipliers, using only shifters and adders. Each coefficient multiplication decomposes into additions of shifted input values, determined by the CSD representation. The regular structure of FIR filtering provides opportunities to share intermediate shift-and-add operations across coefficients.

Consider a coefficient with CSD representation having non-zero digits at positions 0, 3, and 7. The multiplication is (input) + (input shifted left 3) + (input shifted left 7). With proper sign handling for −1 digits, any coefficient multiplication reduces to a small number of additions of power-of-two multiples of the input.

Adder graphs represent the network of additions required to implement all coefficient multiplications. Graph optimization techniques search for adder graphs that compute all required constant multiplications with as few adders as possible, sharing intermediate results. A coefficient set with common factors or similar CSD patterns benefits most from such optimization.

The complexity of multiplierless FIR implementation depends on the coefficient values. Coefficients with sparse CSD representation (few non-zero digits) require fewer additions. Filter design can incorporate CSD-friendliness as an optimization criterion, selecting coefficients that meet frequency specifications while minimizing implementation complexity.

Common Subexpression Elimination

Multiple coefficients may share common shift-and-add computations, enabling reuse of intermediate results. Common subexpression elimination (CSE) identifies these shared operations and computes them once for use by multiple coefficients. This optimization can dramatically reduce the total adder count.

For example, if two coefficients both require (input + input shifted left 2), this common subexpression can be computed once and reused. The optimization extends to complex patterns involving multiple levels of addition and subtraction, potentially spanning many coefficients.

Algorithms for CSE in constant multiplication range from simple pattern matching to sophisticated graph optimization. Optimal CSE is computationally difficult for large coefficient sets, but heuristic algorithms find good solutions in practical run times. Commercial and academic tools automate CSE for practical filter implementations.

The benefits of CSE are most pronounced for filters with many taps and coefficients with similar magnitudes. High-precision coefficients with many non-zero CSD digits provide more opportunities for sharing than low-precision coefficients with few non-zero digits.

CSD versus Other Representations

CSD is one of several signed digit representations used for constant multiplication. A minimum signed digit (MSD) representation is any signed-digit form with the fewest possible non-zero digits. CSD is always one of them, singled out by its non-adjacency rule, and no MSD form has fewer non-zero digits than CSD, but a number often has several MSD forms. The number 45 has five, among them its CSD form 1 0 −1 0 −1 0 1 (64 − 16 − 4 + 1) and its plain binary form 101101. That freedom is useful: choosing among the MSD forms of each coefficient, rather than taking the single CSD form, gives common subexpression elimination more patterns to match.

A minimum digit count is also not the same as a minimum adder count. Built digit by digit, multiplication by 45 takes three additions in either form, but factoring it as 5 × 9 takes two: form 5x as x + 4x, then 45x as 5x + 8 × 5x. Advanced optimization therefore works on adder graphs for the entire coefficient set rather than on the digit pattern of each coefficient alone.

Comparison with standard binary representation highlights CSD advantages. Binary representations of coefficients with many consecutive 1 bits are particularly inefficient; CSD converts these to sparser representations with alternating signs. For example, binary "0111" becomes CSD "1001" (meaning 1, 0, 0, −1), reducing from three non-zero digits to two.

Implementation complexity of CSD arithmetic is similar to binary arithmetic. Subtraction replaces addition for −1 digits, but the operations have identical timing and resource requirements in most implementations. The reduction in operation count directly translates to resource and power savings.

Polyphase Components

A polyphase decomposition of an N-tap FIR filter with M phases creates M subfilters, each containing N/M coefficients (assuming N is divisible by M). The subfilters, called polyphase components, contain the original coefficients subsampled by factor M with different starting positions.

Mathematically, if h[n] represents the original impulse response, the kth polyphase component contains coefficients h[k], h[k + M], h[k + 2M], and so on. Spreading each component's coefficients back out M samples apart, delaying the kth by k samples, and summing the M results reproduces the original impulse response exactly.

The decomposition exposes parallelism inherent in the filter structure. Each polyphase component operates on a decimated version of the input, processing every Mth sample. All M components can operate simultaneously on different subsets of the input samples, enabling parallel implementation.

For analysis, the Z-transforms of the polyphase components relate to the original filter transfer function through the identity

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

where E_k(z) is the Z-transform of the kth polyphase component. Evaluating a component at z^M spreads its coefficients M samples apart, and the factor z^−k delays it by k samples, so the identity restates the interleaving described above. This mathematical framework enables systematic derivation of polyphase structures for various filtering configurations.

Decimation Filters

Decimation by factor M requires an anti-aliasing lowpass filter followed by downsampling. A direct implementation computes a filter output for every input sample, then discards M − 1 out of every M, wasting computation on results that are thrown away. Polyphase restructuring computes only the retained outputs, reducing the arithmetic by a factor of M: N multiplications per output rather than N per input sample.

The polyphase decimation filter splits the input into M streams, each holding every Mth sample from a different starting offset, and filters the kth stream with the kth polyphase component. Every branch runs at the output rate, and every retained output is the sum of all M branch outputs, because each output depends on input samples from every phase.

Implementation typically uses an input commutator that hands each arriving sample to the next branch in turn, so only one branch receives new data at any input instant, even though all M contribute to each output. In software the commutator becomes a single circular buffer read with phase-dependent offsets.

Because each branch has M input sample periods in which to form its contribution, the N multiplications per output can be spread across M clock cycles at the input rate. A design clocked at the input rate therefore needs only about N/M multipliers, roughly 1/M of the hardware of a direct implementation, while sustaining the same input rate.

Interpolation Filters

Interpolation by factor L inserts L − 1 zeros between successive input samples, then lowpass filters to remove spectral images. Direct implementation of the filter multiplies many coefficients by the inserted zeros, wasting computation. Polyphase restructuring avoids these zero-multiplications, reducing computation by factor L.

The polyphase interpolation filter decomposes into L subfilters, each producing one of the L output samples per input sample. Each subfilter operates at the input rate on the original (non-zero-inserted) samples, computing outputs that interleave to form the complete interpolated sequence.

The coefficient assignment to polyphase components follows from the positions of non-zero input samples relative to each output. For output position k, the relevant coefficients are those at positions k, k + L, k + 2L, and so on in the original filter, which form the kth polyphase component.

Implementation can parallel-compute all L outputs simultaneously for maximum throughput, or time-multiplex a single subfilter structure across the L phases for minimum hardware. The choice depends on throughput requirements and available resources. Either approach eliminates zero-multiplication entirely.

Parallel Processing Applications

Polyphase decomposition enables parallel FIR processing beyond multirate applications. By decomposing a filter into M polyphase branches processing interleaved samples, the filter processes M samples per clock cycle while each branch operates at 1/M the sample rate. This parallelism increases throughput without requiring faster clock rates.

The straightforward parallel polyphase structure requires M instances of each of the M polyphase components, M² subfilters in all, processing M interleaved sample streams simultaneously. That is MN multiplications per block of M outputs, the same N per output as a single-rate filter. Sample routing at input distributes successive samples to different branches, while output routing combines the branch outputs in correct sequence.

Fast FIR algorithms reduce this cost by sharing subfilters between outputs. The two-parallel version splits the coefficients and the input into even and odd phases, H₀ and H₁, X₀ and X₁, and forms three subfilter products: H₀X₀, H₁X₁, and (H₀ + H₁)(X₀ + X₁). The even output is H₀X₀ plus H₁X₁ delayed by one block, and the odd output is the third product minus the first two. For even N, three subfilters of length N/2 replace four, cutting the multiplications per pair of outputs from 2N to 3N/2 at the price of a few extra adders.

This approach is valuable when single-rate implementations cannot meet throughput requirements within clock frequency constraints. Rather than pursuing aggressive timing optimization of a single datapath, the designer can use multiple moderate-speed datapaths operating in parallel.

Filter banks naturally exploit polyphase structure. Analysis filter banks decompose signals into frequency bands using modulated versions of a prototype filter, which shares a common polyphase representation. Efficient filter bank implementations compute the polyphase filtering once and combine results through a transform operation like DFT or DCT.

Folding Transformation

Folding transforms a parallel implementation into a serial or partially serial architecture by scheduling multiple operations from the original design onto shared hardware. The folding factor F determines how many original operations share each hardware instance. A folding factor of F reduces multipliers by a factor of F while reducing throughput by the same factor.

The folding transformation requires careful scheduling to ensure data dependencies are respected. Each operation must occur only after its input data is available, which may require additional delay elements to align data with scheduled operations. Systematic folding algorithms determine valid schedules and required delays.

Storage changes form under folding. Where the original design used a dedicated register for each delay element, the folded design often keeps the sample history in a small RAM or shift-register memory accessed in time-multiplexed fashion, with addressing determined by the folding schedule. The history itself cannot shrink, since every output still needs all N samples. Folding can also add registers: a result produced in one time slot but consumed in a later one must be held in between, and systematic folding computes the number of such delays for every edge of the datapath graph.

Folding is the inverse of unfolding, which replicates hardware so that one clock cycle processes several samples. Where unfolding increases hardware for higher throughput, folding decreases hardware and accepts lower throughput; retiming, by contrast, moves existing registers without changing the amount of hardware, and is often applied to a folded or unfolded design to shorten its critical path. The folded and unfolded architectures are functionally equivalent, differing only in their resource and throughput trade-offs.

Sequential Architecture

The most aggressive folding produces a fully sequential architecture with a single multiply-accumulate unit processing one tap per clock cycle. An N-tap filter produces one output every N clock cycles, achieving throughput of 1/N samples per clock. This minimum-hardware implementation is suitable for low-sample-rate applications where silicon area or power dominates over throughput.

The sequential architecture consists of a single multiplier, an accumulator, coefficient memory, and sample memory. Each clock cycle, one sample and one coefficient are read from their respective memories, multiplied, and accumulated. After N cycles, the accumulator contains the filter output, which is then captured and the accumulator reset for the next output.

Control logic sequences through the N tap positions, generating memory addresses for samples and coefficients. The sample memory operates as a circular buffer, with appropriate pointer management to access samples in the correct order. Coefficient memory is typically ROM for fixed filters or RAM for adaptive filters.

The sequential architecture minimizes multiplier hardware but moves the burden to memory. Every output requires N sample reads and N coefficient reads, one of each per clock cycle, where a parallel implementation holds all its samples and coefficients in registers wired directly to its multipliers. Memory access patterns are regular and predictable, enabling efficient implementation.

Semi-Parallel Architectures

Intermediate folding factors produce semi-parallel architectures balancing resource utilization against throughput. For a folding factor F applied to an N-tap filter, the architecture uses N/F multipliers and produces one output every F clock cycles. Semi-parallel architectures offer flexible resource/throughput trade-offs.

The semi-parallel structure groups taps into N/F sections, with one multiplier handling each section. Within a section, F taps time-multiplex onto the shared multiplier over F clock cycles. Partial sums from each section accumulate to produce the final output.

Register allocation in semi-parallel architectures requires analysis of data lifetimes and access patterns. Some registers hold sample values across multiple clock cycles while multiplexing occurs; others hold partial sums during the F-cycle computation period. Optimal register allocation minimizes total storage while meeting all data flow requirements.

Semi-parallel architectures particularly suit FPGA implementation where DSP blocks (multipliers) are the constrained resource. By folding to match available DSP blocks, the designer maximizes filter capability within the FPGA's resources. The flexibility of programmable logic easily accommodates the control logic for various folding factors.

Memory-Based Architectures

Memory-based FIR architectures store both samples and coefficients in RAM, using memory bandwidth rather than dedicated multipliers as the primary resource. These architectures suit platforms with abundant memory but limited multiplier availability, including some microprocessors and specialized digital signal processors.

A simple memory-based architecture uses dual-port RAM: one port reads samples while the other reads coefficients. A single multiply-accumulate unit processes the streams, producing one output per N clock cycles. Memory bandwidth of two reads per cycle supports this computation without contention.

Multi-bank memory organizations increase parallelism. With K sample memory banks and K coefficient memory banks, K multiply-accumulate operations occur each cycle. The N taps distribute across K processors, each handling N/K taps, reducing the output computation time to N/K cycles.

Address generation for memory-based architectures manages circular buffer access and coefficient sequencing. Dedicated address generation units or specialized addressing modes in DSP processors efficiently compute the required addresses. The regular access patterns of FIR filtering are well-matched to hardware address generators.

Throughput Considerations

Systolic arrays and fully parallel transposed structures process one sample per clock cycle regardless of filter length, and parallel polyphase structures go further, processing several samples per clock cycle. These architectures suit applications like radar processing, software-defined radio, and high-speed communications where sample rates exceed hundreds of megasamples per second.

Semi-parallel and folded architectures scale throughput with available hardware. The designer can match throughput to requirements by selecting an appropriate folding factor. These architectures are ideal when throughput requirements are known and resources should not be over-provisioned.

Sequential architectures offer minimum throughput at minimum hardware cost. Applications with sample rates of kilohertz to low megahertz often find sequential implementations adequate. Audio processing, sensor interfaces, and control systems frequently use sequential FIR architectures.

Distributed arithmetic throughput depends on the serial versus parallel implementation choice. Parallel DA achieves one sample per clock; serial DA requires B cycles for B-bit inputs. The architecture's throughput can be tuned through the degree of bit-parallelism implemented.

Resource Considerations

Multiplier count is often the primary resource concern. Systolic and parallel direct forms require N multipliers for an N-tap filter. Symmetric filters reduce this to N/2, or (N + 1)/2 for odd N. Folded architectures reduce multipliers by the folding factor. Distributed arithmetic and CSD-based designs eliminate dedicated multipliers entirely.

Memory requirements vary significantly across architectures. DA requires lookup tables growing exponentially with partition size. Memory-based folded architectures need RAM for samples and coefficients. Systolic and direct form structures use distributed register storage proportional to filter length.

Adder resources are substantial in CSD-based and DA implementations. CSD requires adders for each non-zero digit across all coefficients, though common subexpression elimination reduces this count. DA requires adders for accumulating lookup table outputs and combining partitioned results.

Control complexity increases with folding and time-multiplexing. Sequential and semi-parallel architectures need counters, address generators, and sequencing logic absent from purely parallel implementations. This overhead is modest but should be considered in resource accounting.

Power Considerations

Dynamic power consumption relates to switching activity, which depends on architecture and data characteristics. Architectures with shorter data paths and local communication patterns, like systolic arrays, tend toward lower power than those requiring global data distribution.

DA architectures avoid multiplier power by substituting memory accesses. Memory power consumption depends on access frequency and memory technology. For some implementations, DA achieves significant power savings; for others, the memory power may exceed the saved multiplier power.

Folded architectures can reduce power through resource reduction, but increased clock rate for equivalent throughput may offset savings. Analysis must consider both static (leakage) and dynamic (switching) power contributions across the complete architecture.

Clock gating and power gating opportunities exist in architectures with conditional operation. Folded architectures with partial activity can gate unused resources. Adaptive filters might gate coefficient update logic during steady-state operation. Exploiting these opportunities requires careful architectural design.

Platform Considerations

FPGA implementations benefit from architectures matching the available resources. Modern FPGAs include DSP blocks optimized for multiply-accumulate operations, making direct form and semi-parallel architectures natural fits. Lookup-table logic and block RAM suit DA implementations. The specific FPGA family's resource mix guides architecture selection.

ASIC implementations can optimize any architecture to the application requirements. Custom multipliers, memories, and datapaths achieve higher performance and lower power than general-purpose building blocks. The ASIC's performance and cost requirements determine the appropriate parallelism level.

Software implementations on general-purpose processors favor architectures matching the instruction set and memory hierarchy. SIMD instructions accelerate parallel operations across multiple samples or coefficients. Cache-friendly access patterns improve memory system efficiency. Processor-specific optimization may favor different architectures on different targets.

DSP processors with specialized instructions for filtering often implement direct form or transposed structures efficiently. Circular addressing modes support delay line management. Multiply-accumulate instructions directly implement the core FIR operation. Software for these processors typically uses straightforward direct form implementations.