Modulo-(2q − 3) Multiplication with Fully Modular Partial Product Generation and Reduction

Given the residue number systems that contain moduli of the form 2
^q
± 1 and 2
^q
± 3, it is desirable to employ delay-balanced adders and multipliers, in order to synchronize the operation of parallel residue channels. The required modulo-(2
^q
± 3) adders, with compatible speed with modulo- (2
^q
± 1) adders, already exist with parallel prefix architectures. However, the previously reported modulo-(2
^q
± 3) multipliers, in one way or another, produce the non-modular products of the residues at the outset and work towards yielding the final modular product. This seems to be the main source of incompatible performance with the existing modulo- (2
^q
± 1) fully modular multipliers. Therefore, as the first endeavor, we were motivated to design and implement efficient modulo-(2
^q
− 3) multipliers with fully modular partial product generation and reduction that are more compatible with their modulo- (2
^q
− 1) counterparts. However, unlike the case of modulo 2
^q
− 1, it turns out that the straightforward modulo-(2
^q
− 3) partial product reduction (e.g., via Wallace-tree reduction with greedy use of full adders and half adders) falls into an infinite loop of reduction stages. Therefore, we undertake a modified reduction algorithm that requires at most two reduction levels more than that of the modulo- (2
^q
− 1) case to converge. To ensure the correct operation of the algorithm and ease the design process, an in-house software program produces the exact composition of reduction cells in each level of partial product reduction. Analytical and synthesis-based evaluations of the proposed design, and the previous ones, exhibit better figures of merit, as regards the delay (≥ 24%), area-delay (≥ 6%) and energy (≥ 10%) measures.