Low Complexity Converter for the Moduli Set {2^n+1,2^n-1,2^n} in Two-Part Residue Number System

Abstract

Residue Number System is a kind of numerical systems that uses the remainder of division in several different moduli. Conversion of a number to smaller ones and carrying out parallel calculations on these numbers will increase the speed of the arithmetic operations in this system. However, the main factor that affects performance of system is hardware complexity of reverse converter. Reverse converters convert the resulted remainders to the conventional number system. In this paper an area efficient reverse converter is proposed for moduli set {2^n+1,2^n-1,2^n} based on two-part RNS and mixed radix conversion algorithm. Selecting appropriate order of modulus and using well-known lemmas, leads to reduce the complexity of the proposed converter comparing to previous designs. To have an accurate comparison, both unit gate model and simulation in Xilinx 13.1 FPGA are used in this paper. The results of comparison indicate that the novel proposed reverse converter has improved the time complexity and area, while having almost same delay.