You want to compute a dot product: y = Σ cᵢ·xᵢ for N fixed coefficients cᵢ and N variable inputs xᵢ. The textbook answer is N multipliers and an adder tree. On an FPGA in 1985, multipliers cost 500+ LUTs each. On a modern FPGA with limited DSP blocks, you still don't want to burn one per tap in a 128-tap filter. Distributed arithmetic (DA) eliminates the multipliers entirely by pre-computing every possible partial sum and storing it in a LUT.

The trick: rewrite the sum bit-serially. If each xᵢ is a B-bit signed number, write xᵢ = Σ xᵢ,ⱼ·2ʲ (where xᵢ,ⱼ is the j-th bit). Substitute:

y = Σⱼ 2ʲ · (Σᵢ cᵢ·xᵢ,ⱼ)

The inner sum Σᵢ cᵢ·xᵢ,ⱼ depends only on the j-th bit of each input — an N-bit address into a table with 2ᴺ entries. That table stores every possible weighted sum of the coefficients. Feed it the j-th bit slice from all N inputs, get back a partial sum, shift-add it into an accumulator, repeat for B bit slices. B cycles per dot product, zero multipliers.

Concrete example: A 4-tap FIR with coefficients {3, -1, 5, 2}. The DA LUT has 2⁴ = 16 entries. Address 0b1010 (x₀ and x₂ contribute) returns 3 + 5 = 8. Address 0b1111 returns 3 - 1 + 5 + 2 = 9. For 12-bit inputs, one dot product takes 12 cycles, consuming one 16-entry ROM, one shift-adder, and one accumulator — no multiplier at all. Xilinx's SRL16 shift register (which uses the same LUT hardware in shift mode) makes DA filters land shockingly cheap in Spartan-class parts.

The scaling problem: The LUT is 2ᴺ entries. For N = 4 taps, 16 entries — trivial. For N = 16 taps, 65 536 entries — dead. The standard fix is partitioning: split 16 taps into four 4-tap sub-filters, each with its own 16-entry LUT, then sum the four LUT outputs before the shift-accumulator. Cost grows as N/K · 2ᴷ instead of 2ᴺ.

Rule of thumb: DA beats DSP-block multipliers when (a) coefficients are fixed at synthesis time, (b) you have plenty of LUT/BRAM but few DSP48s, and (c) the throughput requirement tolerates B cycles per sample. For a 12-bit, 16-tap filter partitioned into 4×4, expect roughly 4 LUTs + 1 adder tree + 1 shift-accumulator versus 16 DSP blocks — a big win on small FPGAs, a wash on big ones.

The deeper lesson: any linear function of binary inputs can be tabulated. DA is what happens when you notice that "multiply by a constant" is really "select a precomputed value from a table indexed by input bits."