Title :
Area-Time Optimal Fast Implementation of Several Functions in a VLSI Model
Author :
Wada, Kouichi ; Hagihara, Ken´ichi ; Tokura, Nobuki
Author_Institution :
Faculty of Engineering Science, Department of Information and Computer Sciences, Osaka University
fDate :
5/1/1984 12:00:00 AM
Abstract :
Area and computation time are considered to be important measures with which VLSI circuits are evaluated. In this paper, the area-time complexity for nontrivial n-input m-output Boolean functions, such as a decoder and an encoder, is studied with a model similar to Brent-Kung´s model. A lower bound on area-time-product (ATαaα.≥1) for these functions is shown: for example, ATα= ω(2n. nα-l) for an n-input 2V-output decoder, and ATα= ω( n . logα-1n) for an n-input ⌈log n⌉-output encoder. The results shown in this paper are complementary to those by Brent-Kung or Thompson, and are useful for a class of functions of rather simple structures, e.g., a priority encoder, a comparator, and symmetric functions.
Keywords :
Area efficient layout; Boolean circuit complexity; VLSI model; area-time complexity; priority encoder; Area measurement; Argon; Binary trees; Boolean functions; Decoding; Discrete Fourier transforms; Input variables; Integrated circuit technology; Time measurement; Very large scale integration; Area efficient layout; Boolean circuit complexity; VLSI model; area-time complexity; priority encoder;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1984.1676463