PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Alia G., Martinelli E. On the lower bound to the VLSI complexity of number conversion from weighted to residue representation. In: IEEE Transactions on Computers, vol. 42 (8) pp. 962 - 967. IEEE, 1993.
 
 
Abstract
(English)
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 Oon the characteristics of the residue system, namely the number and size of the moduli. In this paper a lower bound ATΔ2 = Ω ( nΔ2 ) 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 or 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 or 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. lndex Terms- Area-time complexity, pipeline processing
Subject Area-time complexity
Pipeline processing
Positional-to-residue conversion
Residue number system
Table look-up
VLSI


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional