Area-Time Optimal Fast Implementation of Several Functions in a VLSI Model

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^α= ω(2ⁿ. 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.