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 modulari ty and regularity. However, the process of converting data back and fo rth between the usual positional (weighted) representation and the res idue representation can be a bottleneck to efficiency. Although soluti ons to the problem of designing optimal VLSI representation converters have been proposed in the literature, the complexity of such solution s is unfortunately strongly dependent on the characteristics of the re sidue system, namely the number and size of the moduli. In this paper a lower bound AT2 = OMEGA(n2) for the conversion from positional to re sidue representation is derived according to VLSI complexity theory, a nd existing solutions for the same problem are briefly revisited in th e light of such a bound. A VLSI system is proposed, one that operates according to a pipeline scheme and works asymptotically emulating an o ptimal structure, independently of RNS parameters. This solution has b een applied to a design of specific size (64 b input stream), and it h as been found that a single CMOS custom chip can implement the design with a throughput of one residue representation every 30-40 ns.