Area-efficient compressed look-up table implementation for semi-randomly accessible functions

Generating waveforms is a fundamental problem in signal processing applications. Low-latency calculation of a transcendental (i.e., non-algebraic) functions is an expensive operation, therefore many improvements have been proposed. A well-known method is to store all the pre-computed values in a piece of memory, called Look-Up Table (LUT), and directly send them as output. Although this is the fastest way of doing it, using a large memory is expensive in terms of both power and area. The state of the art methods present hybrid approaches that use efficient functions with smaller look-up tables. Usage of a LUT is indispensable. Moreover, the LUT method is the only practical option in cases where transcendental functions need to be computed in real-time. Therefore, LUT reduction is still an active research area. LUT based method is separated into two categories: Piecewise and Addition based LUT methods. Piecewise LUT method is also separated into two categories: approximation and interpolation method. Approximation method calculates nth order polynomial with minimum error. Coefficients of the polynomial expression are stored into LUT. Desired value is calculated using these coefficients in run-time. Product and summation blocks are used. Product determines critical path of the system. Interpolation method everything is same as approximation. However, simple interpolation polynomials, which is linear interpolation, can be calculated in run-time. Product and summation blocks are also necessary. Addition based LUT method only uses summation. Result is superposition of LUT elements. Disadvantages of this method is that it requires more memory space than previous methods. Our method is classified in this section. In this thesis, we propose a new look-up table (LUT) based logic architecture for implementation of transcendental functions, which is low-latency but area efficient. Our architecture improves on the LUT approach by storing not the function values but the differences of consecutive function values. Storing just the differences offers a significant reduction in LUT size, hence reducing hardware area. A simple function generator that generates a fixed sequence of values is quite straight-forward and can easily benefit from our idea. However, what is proposed here is beyond that. Our architecture allows a certain level of random access with little loss in speed-up. Such non-fixed function generators are useful in control systems. We demonstrate our idea through a 16-bit sine generator implemented on FPGA, where the LUT size reduction is 4x. Our novel method is called "compressed LUT" (cLUT) in this thesis. We compress the LUT by storing differences of consecutive values in cLUT instead of actual values of the function. As an example, instead of storing 16-bit values, we store 4-bit differences and then calculate actual function outputs from differences. Bit-width of difference depends on first derivative of the target function. If first derivative is higher, difference needs to more area. Hence, memory utilization closes direct LUT method. The cLUT method offers a significant reduction in memory for a compromise in the level of random access. This is acceptable since most applications require more or less consecutive access to a function as the independent variable of the function comes from a physical quantity that has some continuity. The method consists of three main modules, which are address generation, memory array, and data calculation. Memory array consists of delta number of cLUT, which stores the differences. Output is the value of the signal for the given index . The previously requested output is stored in the data calculation module and used to calculate current requested output. A random output can be selected in the range of . The necessary cLUT cells are selected by the address generator based on the requested. As a result, the output is calculated by a small amount of logic and sent out in a single clock cycle. The memory array consists of delta number of cLUTs. Pre-computed differential signal values are stored in cLUTs in a special way. Subsequent data is stored in the same addresses of the parallel cLUTs. This means that if the cell of first cLUT stores the signal data indexed by , cell consists of the data indexed by . Memories are read in parallel under the control of the address generation module. The address generation module calculates the required memory accesses according to input . A limited random access capability is supported, thanks to the address generation module. Input can be smaller or bigger than the previous as the number of memory. Address generation module is composed of two main parts, which are differential address calculation unit and memory address control unit. Differential address calculation unit keeps the previous address in a register and calculates intermediate results that will be used by address control unit and data selection unit. First, previous input is subtracted from the current input so that the differential address, which may be forward or backward, is calculated. The result of subtraction is interpreted as magnitude and sign. The vector, named as thermo, is shifted in the direction of sign as the amount of the Magnitude. Finally, thermo and the result of shift are XORed. Output of the XOR block is used to determine the cLUT selection. Shifting operation operates on thermo vector, whose size is . First , second , and last bits of thermo are always 0, while the third bits is the result of thermometer regulator block. Thermometer regulator block is used to handle the overflows that occur because of shifting operation. This block checks upper and lower side of thermo and selects the convenient thermo vector as given in Fig. 4. Memory address controller unit takes XOR outputs of differential address calculation unit and outputs necessary cLUT addresses. In order to calculate the next address of cLUTs, a conditional addition mechanism is designed. Addition is selected by the output of the differential address calculation unit and 1, -1 or 0 added to address register, which stores the previous address. For example, current address pointer points to any location of last memory bank and the desired value is 3 steps forward from the current pointer. In this situation, address pointer should be incremented by 1 because of the current pointer location. The address register and its update mechanism is shown in Fig. 7. Data selection unit selects and sums the outputs of the cLUTs using the XOR outputs of address calculation unit. As an example, consider a scenario that a random access is applied to 3 steps behind. Only outputs of 3 cLUTs will be summed. In this paper, we have presented a compressed look up table (cLUT) method for function generation, which provides a limited amount of random data access. A 16-bit addressable and 16-bit value sine function is implemented on Xilinx Spartan-6 FPGA using the proposed cLUT method. Memory requirement has been reduced, by the ratio of 75%, to 32kB from 128kB. The clock frequency achieved for this hardware is 87,4 MHz.