Fast division in the residue number system 2n + 1, 2n, 2n-1 based on shortcut mixed radix conversion. (May 2020) - Torabi, Zeinab; Jaberipur, Ghassem; Belghadr, Armin
Highlights: Division is one of the most complicated operations in the residue number systems. The straightforward reverse/divide/forward (RDF) method is a costly and slow mile-stone solution, while there is not any better solution than RDF in the relevant literature. The proposed new RNS approximate and exact dividers partially uses a mixed radix reverse converter and two parallel 2 n -bit dividers. The proposed dividers consume 14–36% less delay than the RDF. Abstract: Unlike the parallelism residue number systems (RNS) provide for addition and multiplication, RNS division is often performed via a straightforward RDF (i.e., reverse conversion, binary division, and forward-conversion) scheme. Given the lack of any faster-than-RDF RNS divider, we designed one for the popular moduli set 2 n + 1, 2 n, 2 n − 1, via mixed radix representation of the operands and two parallel 2 n -bit dividers (vs. the 3 n -bit counterpart required by the RDF). However, the ensued RNS integer quotient could be off the correct result by ± 1, which is tolerated in many approximate arithmetic processes. Nevertheless, we obtain the accurate quotient via additional hardware (i.e., six parallel n -bit comparators). Our experimental results, for n = 8(16), as compared to RDF, show 33%(36%) less delay, 3%(12%) less energy, and 35%(43%) less energy-delay product in case of the minimal-error approximate divider and 14%(21%) less delay in case of the exact implementation, at the cost of additional area consumption and power dissipation.