## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 401-418 |

Number of pages | 18 |

Journal | SIAM Journal on Applied Mathematics |

Volume | 35 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 1978 |