VLSI STRUCTURES FOR BIT-SERIAL MODULAR MULTIPLICATION USING BASIS CONVERSION

This paper proposes design techniques for the efficient VLSI implement ation of bit-serial multiplication over a modulus. These techniques re duce multiplication into simple cyclic shifts, where the number repres entation of the data is chosen appropriately. This representation will , in general, be highly redundant, implying a relatively poor throughp ut for the multiplier. It is then shown how, by splitting the multipli er into two pipelined multipliers, the throughput of the unit can be i ncreased, whilst still retaining a cyclic-shift implementation. The sp lit multiplier requires a mid-computation basis conversion, and the tw o number representations, used within the unit, are only moderately re dundant. Thus, high-throughput, bit-serial multipliers are achieved, w ith most of the complexity contained within systolic basis converter m odules. The multipliers are applicable to the VLSI implementation of h igh-throughput, signal processing operations performed over finite fie lds, in particular, transform and filter operations.