An Efficient Non-Linear Cost Compression Algorithm for Multi Level Cell Memory

This paper defines a non-linear cost compression problem, proposes an efficient algorithm, and applies it to a real application of multi level cell memory to minimize energy consumption and latency. The non-linear cost compression problem extends the traditional cost compression problem to allow a non-linear cost function of symbol frequencies, while it is a weighted linear combination of symbol frequencies in the cost compression problem. In order to solve the non-linear cost compression problem efficiently, we propose an encoding symbol frequency based approach. We first compute frequencies of encoding symbols to minimize a cost function. To achieve the computed frequencies of a cost-compressed message, we deploy existing size-decompression algorithms. The proposed algorithm is optimal and as fast as the existing size compression algorithms. Our experimental results show that it reduces the energy consumption and latency by 70 percent for a text file in multi level cell memory. Furthermore, it increases the lifetime of endurance limited memory.