Optimal-Partition Based code compression for embedded processor

Memory is one of the most restricted resources in embedded system. Code compression techniques address this issue by reducing the code size of programs. Huffman coding is the most common used coding method. But during the process of generating symbols from instruction, an experience-based partition way is usually used, which may cause information redundancy. This paper presents an optimal-partition based code compression (OPCC) method. Markov tree model is used to extract correlation between bits in instruction. A clustering algorithm is proposed to cluster bits with higher correlation into symbols. Experimental results show that this method could improve the average compression ratio by 4.1%. The decoder part is validated in Altera CycloneII FPGA.