13.7    DISTRIBUTED ARITHMETIC

Distributed arithmetic is used to design bit-level architectures for vector-vector multiplications. In distributed arithmetic, each word in the vectors is represented as a binary number, the multiplications are reordered and mixed such that the arithmetic becomes “distributed” through the structure. Distributed arithmetic is commonly used for implementation of convolution operations and discrete cosine transforms (DCT) commonly used in video compression systems [17],[18].

13.7.1    Conventional Distributed Arithmetic

Consider an inner product between 2 length-N vectors C and X:

image

where {ci}’s are M-bit constants and {xi}’s are coded as W-bit 2’s complement numbers

image

Substituting (13.21) in (13.20),

image

Define

image

Then,

image

Therefore, by interchanging the summing order of i and j, the initial multiplications in (13.20) are now distributed to another computation pattern [19], [20].

Since the term Cj depends on the xi,j values and has only 2N possible values, it is possible ...

Get VLSI Digital Signal Processing Systems: Design and Implementation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.