Documents
Poster
Guided Blocks WOM codes
- Citation Author(s):
- Submitted by:
- Dana Shapira
- Last updated:
- 1 March 2021 - 8:31am
- Document Type:
- Poster
- Document Year:
- 2021
- Event:
- Presenters:
- Shmuel T. Klein
- Categories:
- Keywords:
- Log in to post comments
A binary Write Once Memory (wom) device is a storage mechanism in which a 0-bit can be overwritten much more easily than a 1-bit. A famous example is the flash memory technology, where $0 \rightarrow 1$ transitions are allowed, but $1\rightarrow 0$ transitions require a costly erase procedure and are therefore prohibited. A {\sc wom} code is a coding scheme that permits multiple writes to the {\sc wom} without violating the {\sc wom} rule.
The properties of {\sc wom}
attracted attention even before flash memory was invented.
Rivest and Shamir [ Ronald L. Rivest and Adi Shamir. How to reuse a ‘write-once’ memory. Information and Control, 55(1-3):1–19, 1982.] proposed an elegant {\sc wom} code that uses 3 bits to write two rounds of any combination of 2 bits. As alternative, {\it context sensitive\/} rewriting codes have been considered [Gilad Baruch, Shmuel T. Klein, and Dana Shapira. New approaches for context sensitive flash codes. Implementation and Application of Automata, CIAA 2019, 45–57, 2019],
in which the new information stored in the second round utilizes certain portions of the output of the first round for unambiguous reuse. Some of these encodings are based on Fibonacci Codes, whose primary relevant property is that they contain no adjacent {\tt 1}-bits, except as suffixes of all of their codewords.
The present work introduces a new paradigm of \textit{Guided-Blocks} rewriting codes, in which after any previous use of the storage, most simply the direct binary encoding being used in the first round, a second writing round is enabled by fitting fixed-size blocks of bits into the used storage, using a flagging mechanism to mark appropriate positions that grant a fit to be possible.
Different possible manipulations over the block to be fitted are presented, increasing the probability of finding a fitting position earlier.
Experimental results show that the efficiency of the Guided Block approach may outperform that of state-of-the-art {\sc wom} codes, especially on highly imbalanced data\-sets, in which the probability for a 1-bit is much smaller than that of a 0-bit or vice versa. An example could be {\sc mnist}, a database of handwritten digits that is commonly used in the Machine Learning and Computer Vision communities, with an average probability of about 0.11 for the appearance of a 1-bit. Moreover, the technique can be applied to transform any rewriting code for $i$ writing rounds, for any $i\ge 1$, into an enhanced rewriting code for $i+1$ rounds.