On the lower bound to the vlsi complexity of number conversion from weighted to residue representation

Computing structures based on residue number systems (RNS), which are useful in special applications as signal processing, where speed is a goal, are well suitable for VLSI implementations, because of their features of modularity and regularity. However, a bottleneck to the efficiency can be represented by the process of data converting forth and back between the usual positional (weighted) representation and the residue representation. Some authors have considered the problem of designing optimal VLSI representation converters, but unfortunately the complexity of the proposed solutions strongly depends on the characteristics of the residue system, namely the number and the size of moduli. In this work a lower bound AT?2=?(n?2) for the conversion from positional to residue is derived according to the VLSI complexity theory, and existent solutions for the same problem are briefly revisited in the light of such bound. Moreover, a structure is proposed, which works optimally independently of RNS parameters, according to a pipeline scheme. Such a structure can be implemented both with VLSI technology and with discrete components; the latter solution has been applied outlining a specific size design, based on the use of look-up tables.