Multiset and set decipherable codes (Q5948786): Difference between revisions

Unique decipherable (UD) codes use different sequences of codewords to carry different information. In multiset decipherability (MSD), the order in which the codewords appears is irrelevant, whereas in set decipherability (SD), the order and multiplicity of words is irrelevant. Work of \textit{A. Lempel} [IEEE Trans. Inf. Theory 32, 714-716 (1986; Zbl 0619.94019)] and \textit{F. Guzmán} [A complete list of small proper MSD and SD codes (submitted)] shows that UD, MSD, and SD coincide for two-word codes. The first author has considered this question for three-word codes in [\textit{F. Blanchet-Sadri}, IEEE Trans. Inf. Theory 47, 1745-1757 (2001)], where he shows that UD, MSD, and SD coincide under certain conditions. Here, the authors show that UD, MSD, and SD cannot coincide for \(n\geq 4\) by providing a construction for an \(n\)-word SD code that is not MSD. Furthermore, they show that no SD code contains a full UD code as a proper subcode.