For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Effects of Practical Assumptions in Area Complexity of VLSI Computation
Kenichi HAGIHARA Kouichi WADA Nobuki TOKURA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1983/12/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Digital Circuits
Full Text: PDF(623.2KB)>>
Brent, Kung and Thompson have presented suitable VLSI models, and discussed area-time and/or area complexities of various computations such as discrete Fourier transform and multiplication. Although the VLSI models by Brent-Kung and Thompson are suitable for analyzing VLSI circuits theoretically, their models are not yet sufficiently practical from the viewpoint of the current VLSI technology. In this paper, effects of the practical assumptions such as the boundary layout assumption and a restricted location assumption on bounds of the area complexity are discussed, and some technique for obtaining the area lower bounds of combinational circuits is presented on a VLSI model with the boundary layout assumption. To obtain the area lower bounds, a relationship between locations of I/O ports on the boundary of a combinational circuit and it's area is derived. By using the result, we show that a combination circuit to compute the addition or the multiplication requires area proportional to a square of the input bit size, if some I/O port locations are specified. Also we show that combinational circuits to compute the multiplication, the division and the sorting require area proportional to a square of the input bit size, independently of the I/O port locations. These lower bounds are best possible for the multiplication and the division, and are optimal within a logarithmic factor for the sorting.