research-article

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

Authors:

G. Alia,

E. MartinelliAuthors Info & Claims

IEEE Transactions on Computers, Volume 42, Issue 8

Pages 962 - 967

https://doi.org/10.1109/12.238486

Published: 01 August 1993 Publication History

Publisher Site

Abstract

A lower bound AT/sup 2/= Omega (n/sup 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 reviewed 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 residue number system 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.

References

[1]

{1} R. M. Capocelli and R. Giancarlo, "Efficient VLSI networks for converting an integer from binary to residue numbers and vice versa," IEEE Trans. Circuits Syst., vol. CAS-35, no. 11, pp. 1425-1430, 1988.

Google Scholar

[2]

{2} G. Alia and E. Martinelli, "A VLSI structure for x(modm) operation," J. VLSI Signal Processing, vol. 1, pp. 257-264, 1990.

Digital Library

Google Scholar

[3]

{3} G. Alia and E. Martinelli, "VLSI binary-residue converters for pipelined processing," Comput. J., vol. 33, no. 5, pp. 473-475, 1990.

Crossref

Google Scholar

[4]

{4} C. D. Thompson, "A complexity theory for VLSI," Ph.D. dissertation, Dept. of Comput. Science, Carnegie-Mellon University, Rept. CMU-CS-80-140, 1980.

Digital Library

Google Scholar

[5]

{5} N. S. Szabo and R. J. Tanaka, Residue Arithmetic and its Applications to Computer Technology. New York: McGraw-Hill, 1967.

Google Scholar

[6]

{6} G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 4th ed. London: Oxford, 1975.

Google Scholar

[7]

{7} G. Bilardi and F. P. Preparata, "Area-time lower-bound techniques with applications to sorting," Algorithmica, vol. 1, 1986.

Digital Library

Google Scholar

[8]

{8} K. Mehlhorn, "AT<sup>2</sup>-optimal VLSI integer division and integer square rooting," Integration, vol. 2, pp. 163-167, 1984.

Crossref

Google Scholar

[9]

{9} K. Mehlhorn and F. P. Preparata, "Area-time optimal VLSI integer multiplier with minimum computation time," Inform. Contr., vol. 58, pp. 137-156, 1983.

Digital Library

Google Scholar

[10]

{10} G. Alia and E. Martinelli, "A VLSI module m multiplier," IEEE Trans. Comput., vol. C-40, no. 7, pp. 873-878, 1991.

Digital Library

Google Scholar

[11]

{11} R. P. Brent and H. T. Kung, "A regular layout for parallel adders," IEEE Trans. Comput., vol. C-31, no. 3, pp. 260-264, 1982.

Google Scholar

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

Recommendations

A VLSI Modulo m Multiplier

A novel method to compute the exact digits of the modulo m product of integers is proposed, and a modulo m multiply structure is defined. Such a structure can be implemented by means of a few fast VLSI binary multipliers, and a response time of about ...
Area-Time Optimal Adder Design

A systematic method of implementing a VLSI parallel adder is presented. A family of adders based on a modular design is defined. The design uses three types of component cells, which are implemented in static CMOS. The adder design is formulated as a ...
Accelerated Two-Level Carry-Skip Adders-A Type of Very Fast Adders

This paper describes a new type of carry-skip adder, which can be faster than the conventional two-level carry-skip adders. A way to design optimum adders of this new type is described. In optimum adders of this type, the sizes of the sections of bit ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 42, Issue 8

August 1993

133 pages

ISSN:0018-9340

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 August 1993

Author Tags

Qualifiers

Research-article

Recommendations

A VLSI Modulo m Multiplier

Area-Time Optimal Adder Design

Accelerated Two-Level Carry-Skip Adders-A Type of Very Fast Adders

Comments

Published In

Publisher

Publication History

Author Tags

Qualifiers

Other Metrics

Article Metrics

Other Metrics

Abstract

References

Recommendations

A VLSI Modulo m Multiplier

Area-Time Optimal Adder Design

Accelerated Two-Level Carry-Skip Adders-A Type of Very Fast Adders

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations