Error-correcting WOM-codes

A problem raised by R.L. Rivest and A. Shamir (1982), namely, constructing write-once-memory (WOM) codes capable of error correction, is considered. The authors call a (n,m,t)-WOM code a scheme that allows t successive writings of m arbitrary bits (i.e., one message among 2^m) on a WOM of size n. WOM codes have been studied from an information-theoretic viewpoint by J.K. Wolf et al. (1984) and constructed using classical coding theory by G.D. Cohen et al. (1986, 1987) (for example, with parameters, (23,11,3), (2^m-1,m,2^m-2+2^m-4+1)). The authors adapt those methods in order to solve the problem raised by Rivest. Large classes of easily decodable single-error-correcting WOM codes are obtained.