Module Hardcaml_circuits.Rac

ROM-accumulator.

Evaluate a0.x0 + a1.x1 + ... + an.xn where the ai are constants, using distributed arithmetic. The architecture uses a rom and add/shift circuit and requires no multipliers.

The ROM-accumulator extends the idea of multiplication by adding and shifting. a0.x0 can be the calculated by testing each bit of x and adding a to the shifted accumulator. Similarly a0.x0 + a1.x1 can be calculated by forming an address vector from each successive bit, b, of x0 and x1, i.e.:

[x1.[b]; x0.[b]]

A pre-calculated rom stores all possibile additions of a0 and a1

[ 0; a0; a1; a0+a1 ]

Given n coefficients the required rom will be of size 2^n.

The address is looked up in the rom and added to (or subtracted from) the shifted accumulator.