A construction of non-binary WOM codes based on integer programming
Yoju Fujino, Tadashi Wadayama · International Symposium on Information Theory and its Applications · 2016
In this paper, we propose a construction of non-binary WOM (Write-Once-Memory) codes for q-level WOM storages based on integer programming. The WOM codes discussed in this paper are fixed rate (n, q, M, t∗)-WOM codes where messages in an alphabet of size M can be sequentially written in n-cells at least t∗-times. The proposed construction has the two features. First, it possesses a systematic method to determine the encoding regions needed to construct the codes. Second, the proposed construction includes a labeling method for cell states by using integer programming. The novel WOM codes with n = 2 and M = 8 constructed by the proposed construction achieve the number of writes t∗ that meets the known upper bound in the range 4 ≤ q ≤ 8. They are thus optimal in terms of the number of writes t∗. One of advantages of the proposed construction is flexibility. It can be used for high dimensional cases as well. For example, the new (n = 3,q = 7,M = 7,t∗ = 8)-WOM code provides larger t∗ than that of the known (3, 7, 7, 7)-WOM code.