The presented work uses code compression to improve the design efficiency of an embedded system. In particular, we present a method and architecture for compressing the so-called Look-up Tables that are necessary for the de-compression process. No other work has yet focused on minimizing the Look-up Tables that, as we show, have a significant impact on the total overhead of a hardware-based decompression scheme. We introduce a novel and very efficient hardware-supported approach based on  Canonical Huffman Coding . Using the  Lin-Kernighan  algorithm we reduce the  Look-up Table  size by up to 45%. As a result, we achieve all-over compression ratios as low as 45% (already including the overhead of the  Look-up Tables ). Thereby, our scheme is entirely orthogonal to approaches that take particularities of a certain instruction set architecture into account, meaning that compression could be further improved. Factoring in the orthogonality, our scheme is the basis for not-yet-achieved efficiency in hardware-supported compression schemes. We have conducted evaluations using a representative set (in terms of size and application domain) of applications and have applied it to three major embedded processor architectures, namely  ARM ,  MIPS  and  PowerPC . The hardware evaluation shows no performance penalty.
['Talal Bonny', 'Joerg Henkel']
Using Lin-Kernighan algorithm for look-up table compression to improve code density