When data must satisfy constraints upon writing

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 words with this property as being Hamming connected. Hamming connected constrained codes 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 constraints.