Efficient compression of hardware lookup tables cuts storage needs
Lossless Compression of Lookup Tables for Hardware Applications
Hardware Architecture
Summary
Storing large lookup tables in hardware like FPGAs can use a lot of space, which is a problem for small devices. The authors propose CompressedLUT, a way to shrink these tables without losing any data, using clever steps to find patterns and compress effectively. They also designed a simple hardware decoder that is fast and takes up little space. Their tests show it works well for mathematical functions and certain neural networks. The software to do this is publicly available.
What this means in practice
- •For embedded system designers: Store large constant-value tables in tiny hardware without increasing chip size, enabling more complex functions on edge devices.
- •For digital signal processing engineers: Implement compact nonlinear function evaluation in hardware, saving resources while maintaining precision.
Authors
Alireza Khataei, Kia Bazargan
Abstract
Large lookup tables are widely used in hardware to store constant-valued arrays for applications ranging from elementary mathematical operations, such as constant-coefficient multiplication and nonlinear function evaluation, to emerging machine learning models, including table-based neural networks (NNs) and Kolmogorov-Arnold networks (KANs). However, storing extensive tables of constant values can lead to excessive hardware costs in resource-constrained edge devices such as FPGAs. In this paper, we propose CompressedLUT, a lossless compression scheme and its decoder hardware architecture for the efficient storage and retrieval of arbitrary data in hardware. Our method combines decomposition, self-similarities, higher-bit compression, and multilevel compression techniques to maximize table size savings without accuracy loss. Its hardware decoder primarily uses addition, arithmetic right shift, and several small lookup tables, ensuring low area and high throughput. We evaluated CompressedLUT on FPGAs by implementing multiple nonlinear functions, constant-coefficient multipliers (CCMs), and KANs at 12-bit resolution. CompressedLUT is available as an open-source tool.