An efficient tree architecture for modulo 2(n)+1 multiplication

Module 2(n) + 1 multiplication plays an important role in the Fermat number transform and residue number systems; the diminished-1 representation of numbers has been found most suitable for representing the elements of the rings. Existing algorithms for module (2(n) + 1) multiplication either use recursive module (2(n) + 1) addition, or a regular binary multiplication integrated with the module reduction operation. Although most often adopted for large n, this latter approach requires conversions between the diminished-1 and binary representations. In this paper we propose a parallel fine-grained architecture, based on a Wallace tree, for module (2(n) + 1) multiplication which does not require any conversions; the use of a Wallace tree considerably improves the speed of the multiplier. This new architecture exhibits an extremely modular structure with associated VLSI implementation advantages. The critical path delay and the hardware requirements of the new multiplier are similar to that of a corresponding n x n bit binary multiplier.