Fast division in the residue number system {2n + 1, 2n, 2n-1} based on shortcut mixed radix conversion. (May 2020)

• Record Type: Journal Article
• Authors: Torabi, Zeinab; Jaberipur, Ghassem; Belghadr, Armin
• Is Part Of: Computers & electrical engineering. Volume 83(2020)
• Publication Date: 2020-05
• Subjects: Residue number system -- Approximate RNS division -- Mixed radix conversion -- Vlsi design; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2020.106571
• Languages: English
• ISSNs: 0045-7906

Abstract

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.