On the Lower Bound to the VLSI Complexity of Number Conversion from Weighted to Residue Representation

Computing structures based on residue number systems (RNS), useful in special applications such as signal processing where speed is a goal, are highly suitable for VLSI implementations because of their modularity and regularity. However, the process of converting data back and forth between the usual positional (weighted) representation and the residue representation can be a bottleneck to efficiency. Although solutions to the problem of designing optimal VLSI representation converters have been proposed in the literature, the complexity of such solutions is unfortunately strongly dependent on the characteristics of the residue system, namely the number and size of the moduli. In this paper a lower bound AT2= Q(n2) for the conversion from positional to residue representation is derived according to VLSI complexity theory, and existing solutions for the same problem are briefly revisited in the light of such a bound. A VLSI system is proposed, one that operates according to a pipeline scheme and works asymptotically emulating an optimal structure, independently of RNS parameters. This solution has been applied to a design of specific size (64 b input stream), and it has been found that a single CMOS custom chip can implement the design with a throughput of one residue representation every 30-40 ns. Area-time complexity, pipeline processing, positional-to-residue conversion, residue number systems, table look-up, VLSI. © 1993 IEEE