Page 519 - DSP Integrated Circuits

504 Chapter 11 Processing Elements

where *j& is the kth bit in KI. By interchanging the order of the two summations we get

which can be written

where

F is a function of N binary variables, the ith variable being the kth bit in th<
data Xi. Since F& can take on only a finite number of values, 2^, it can be compute<
and stored in a look-up table. This table can be implemented using a ROM (read
5
only memory). Using Homers method for evaluating a polynomial for x = 0.5
Equation (11.47) can be rewritten

Figure 11.39 shows a block diagram for computing an inner product according
to Equation (11.49). Since the output is divided by 2, by the inherent shift, the cir-
cuit is called a shift-accumulator [20, 35].
Inputs, x\, X2,..., XN are
shifted bit-serially out from the
shift registers with the least sig-
nificant bit first. Bits x^ are used
as an address to the ROM storing
the look-up table.
Computation of the inner
product starts by adding Fyfd-±
to the initially cleared accumula-
tor register, REG. In the next
clock cycle, outputs from the shift
registers address F^ d_2, which is
added to the value in the accu- Figure 11.39 Block diagram for distributed
arithmetic
mulator register. After W^_i
clock cycles, FQ is subtracted
from the value in the accumula-
tor register. The computational

5
- William Homer, 1819. In fact, this method was first derived by Isaac Newton in 1711.