UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-85-244.pdf
Oskicat catalog record
Conditions of Use

Archive Home Page

A Minimum-Area Circuit for l-Selection

Authors:
Duris, Pavol
Sykora, Ondrej
Thompson, Clark D.
Vrto, Imrich
Technical Report Identifier: CSD-85-244
June 13, 1985
CSD-85-244.pdf

Abstract: We prove tight upper and lower bounds on the area of semielective, when-oblivious VLSI circuits for the problem of l-selection. The area required to select the l-th smallest of n k-bit numbers is found to be heavily dependent on the relative sizes of l, k, and n. When l < 2^k, the minimal area is A = 0mega((min{n , l(k - logl)}). When l >= 2^k, A = Omega(2^k (logl - k + 1)).