L. J. Guibas, A. M. Odlyzko

Research output: Contribution to journalArticlepeer-review

63 Scopus citations


A prefix-synchronized code with prefix P of length p is a collection of strings whose first p characters equal P, but which have the property that P does not occur in any concatenation of codewords in any positions but those corresponding to initial segments of codewords. Given a block length N and the size q of the alphabet, it is desirable to find prefixes which maximize the size of the code. Gilbert conjectured that if q equals 2, some maximal prefix-synchronized codes have prefixes of the form 11. . . 10 for a suitable length p. It is shown here that this conjecture is true (at least for large N) for q equals 2, as well as q equals 3 and q equals 4, but that is false for q greater than equivalent to 5. It is also shown that the sizes of maximal prefix-synchronized codes exhibit some rather interesting oscillations as the block length increases. The proofs involve combinatorial arguments to establish closed form expressions for generating functions as well as extensive analysis of those generating functions.

Original languageEnglish (US)
Pages (from-to)401-418
Number of pages18
JournalSIAM Journal on Applied Mathematics
Issue number2
StatePublished - Jan 1 1978


Dive into the research topics of 'MAXIMAL PREFIX-SYNCHRONIZED CODES.'. Together they form a unique fingerprint.

Cite this