Optimizing Residue Number Reverse Converters through Bitwise Arithmetic on FPGAs

As a promising number representation method to provide inspiring operational performance, the Residue Number System (RNS) has been widely applied in many key applications for data pocessing. However, a highly-efficient and general-purpose reverse converter, which is the key component in an RNS system, is still less to be seen, due to the costly and complex operators that require large amounts of computing resources and a long latency to accomplish. In this paper, we are targeting at reverse converters that are highly efficient and can support general moduli sets. We first propose optimizing methods based on the bit wise arithmetic to improve the performance of general reverse converters such as CRT and New CRT. The methods are capable of replacing expensive operations such as additions and multiplications with bit wise operations. We also optimize the performance of specific reverse converter through condition reduction and pre-calculation methods. Furthermore, we develop a user controlled FPGA design generator that can produce optimized reverse converter designs for a number of different moduli sets. Compared with the existing optimized converter designs, our proposed methods can further reduce the latency and resource consumption by 54.2% to 84.6% and 65% to 88.5% respectively.