On the poset structure of floating codes

Flash memory is a non-volatile, non-mechanical data storage technology that stores data by trapping charge and can be reused by freeing the trapped charge with an internal erase operation. When flash memory cells are erased, there is a considerable negative impact on the longevity and performance of the device. To defer and minimize these erasures, a floating code is able to store variable updates as cell increments. A (n, q, k) floating code uses an array of n cells with q levels to store k binary variables. In this paper, we investigate the poset (partially ordered sets) structures derived from the various states of the n cells and k variables. These posets have fundamentally different structures that makes designing floating codes a challenge, most notably their structure of their vertex covers. Based on the poset structure, we present a new floating code for l = 2 and arbitrary q, k and n ∈ {k, k+1}, or arbitrary n, q and k = 2 that is optimal for single cell increments and has a deficiency of O(qk), the best possible deficiency. We present an algorithm for constructing the floating code and prove that the algorithm produces a valid floating code.