Lossless look-up table compression for hardware implementation of transcendental functions

Abstract

Look-Up Table (LUT) implementation of transcendental functions often offers lower latency compared to algebraic implementations at the expense of significant area penalty. MultiPartite table method (MP) can circumvent the area problem by breaking up the implementation into multiple smaller LUTs. However, even these smaller LUTs may be big in high accuracy MP designs. Lossless LUT compression can be applied to one or more of these LUTs to further improve area and even timing in some cases. The state-of-the-art 2T-TIV and 3T-TIV methods decompose the Table of Initial Values (TIV) of MP into a table of pivots and tables of differences from the pivots. Our technique, which we call Fully Random Access differential LUT (FR-dLUT), instead uses differences of consecutive elements and results in a smaller range of differences. We also propose a variant of FR-dLUT with variable length coding (Huffman) called FR-dLUTVL, which introduces don't cares into the difference tables and lets logic synthesis optimize them out. We implemented Verilog generators of MP for sine and exponential, where TIV is a conventional LUT as well as 2T-TIV, 3T-TIV, FR-dLUT, and FR-dLUT-VL. We synthesized the generated designs on FPGA and found that our techniques produce around 10% improvement in area and timing beyond the state-of-the-art in large bit widths.