A fast VLSI conversion between binary and residue systems

Residue Number Systems (RNS) have proved to be very attractive because of the parallel nature of their arithmetic. They appear particularly suited for special purpose hardware implementations as signal processing and digital filtering. However, one of the problems to deal with when considering arithmetic units based on RNS is the conversion of data from the weighted system to the residue number system and vice versa. In fact, the double conversion is the major overhead which would offset the advantage of high speed in the lack of a suitable algorithm and a well designed implementation. The problem of converting integers to and from residue systems has already been considered in an attempt to optimize the area-time complexity. In this article a new solution is given, providing two similar structures for the two conversions. The main design goals are a higher speed and a layout comparable, at least along the input data side, with data stream width. In this way such structures are suitable for being embedded in layouts of complex RNS-based systems, where the conversion stages can be inserted in data paths, without modifying the complexity along the orthogonal direction.