AN EFFICIENT TREE ARCHITECTURE FOR MODULO 2(N)+1 MULTIPLICATION

Module 2(n) + 1 multiplication plays an important role in the Fermat n umber transform and residue number systems; the diminished-1 represent ation of numbers has been found most suitable for representing the ele ments of the rings. Existing algorithms for module (2(n) + 1) multipli cation either use recursive module (2(n) + 1) addition, or a regular b inary multiplication integrated with the module reduction operation. A lthough most often adopted for large n, this latter approach requires conversions between the diminished-1 and binary representations. In th is paper we propose a parallel fine-grained architecture, based on a W allace tree, for module (2(n) + 1) multiplication which does not requi re any conversions; the use of a Wallace tree considerably improves th e 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 multipli er are similar to that of a corresponding n x n bit binary multiplier.