Effects of Practical Assumptions in Area Complexity of VLSI Computation

Kenichi HAGIHARA  Kouichi WADA  Nobuki TOKURA  

IEICE TRANSACTIONS (1976-1990)   Vol.E66   No.12   pp.709-716
Publication Date: 1983/12/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Digital Circuits

Full Text: PDF(623.2KB)>>
Buy this Article

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.