文档介绍：The Role of Distributed Arithmetic in
FPGA-based Signal Processing
Introduction
Distributed Arithmetic (DA) plays a key role in embedding DSP functions in the Xilinx 4000 family of
FPGA devices. In this document the DA algorithm is derived and examples are offered that illustrate its
effectiveness in producing gate-efficient designs.
Distributed Arithmetic Revisited
Distributed Arithmetic, along with Modulo Arithmetic, putation algorithms that perform
multiplication with look-up table based schemes. Both stirred some interest over two decades ago but have
languished ever since. Indeed, DA specifically targets the sum of products (sometimes referred to as the
vector dot product) computation that covers many of the important DSP filtering and frequency
transforming functions. Ironically, many DSP designers have never heard of this algorithm. Inspired by the
potential of the Xilinx FPGA look-up table architecture, the DA algorithm was resurrected in the early 90’s
and shown to produce very efficient filter designs [1].
The derivation of the DA algorithm is extremely simple but its applications are extremely broad. The
mathematics includes a mix of boolean and ordinary algebra and require no prior preparation - even for the
logic designer.
[1] Mintzer, L. “FIR filters with the Xilinx FPGA “ FPGA ’92 ACM/SIGDA Workshop on FPGAs
pp. 129-134
Distributed Arithmetic at a Glance
The arithmetic sum of products that defines the response of linear, time-works can be
expressed as:
K
equ. 1 y(n) = ∑ Ak xk(n)
k=1
where:
y(n) = response work at time n.
xk(n) = kth input variable at time n.
Ak = weighting factor of kth input variable that is constant for all n, and so it remains time-invariant.
In filtering applications the constants, Ak , are the filter coefficients and the variables, xk , are the prior
samples of a single data source (for example, an analog to digital converter). In frequency transforming -
whether the discrete Fourier or the fa