Performance Evaluation of a Novel Direct Table Lookup Method and Architecture with Application to 16-bit Integer Functions
L. Li, Alex Fit-Florea, Mitchell Aaron Thornton, David Matula · 2006
We describe several integer function properties which in combination allow direct lookup tables to be reduced in size and structure to simpler lookup trees. Our principal result is a novel table lookup method based on a mapping of a lookup tree to a row-by-column ROM with pre and post processing logic substantially reducing the table size. Our lookup architecture allows common 16-bit integer functions such as multiplicative inverse, square, and the discrete log to be realized with table size of order 2-8 Kbytes, in comparison to the 128 Kbyte size of an arbitrary 16-bits-in 16-bits-out function table. The lookup methodology is illustrated with specific development of the 16-bit integer discrete-log function. Implementation for both unnormalized and normalized indices are synthesized into standard cell netlists and performance and area results are given that demonstrate their effectiveness.