When Data Must Satisfy Constraints Upon WritingShare
- Author(s): Ordentlich, Erik; Roth, Ron M.
- HP Laboratories
- Keyword(s): coding
Abstract: We initiate a study of constrained codes in which any codeword can be transformed into any other codeword by a sequence of single symbol changes such that the intermediate words (after each symbol change) all satisfy the underlying constraint. We shall refer to a set of constrained sequences with this property as being Hamming connected. Hamming connected constrained systems might be useful for encoding data in storage media when a constraint must be met upon writing data, as might be the case in some emerging storage technologies. The stated property would permit overwriting encoded data without violating the constraint during intermediate writes. We study the Hamming connectedness of (d, k) run-length limited constraints and a few other special cases. We also consider the decidability of Hamming connectedness for finite memory contraints.
- External Posting Date: February 21, 2014 [Fulltext]. Approved for External Publication
- Internal Posting Date: February 21, 2014 [Fulltext]