Synchronization of binary messages
E. N. Gilbert · IEEE Transactions on Information Theory · 1960
When messages are transmitted as blocks of binary digits, means of locating the beginnings of blocks are provided to keep the receiver in synchronism with the transmitter. Ordinarily, one uses a special synchronizing symbol (which is really a third kind of digit, neither 0 nor 1) for this purpose. The Morse code letter space and the teletype start and stop pulses are examples. If a special synchronizing digit is not available, its function may be served by a short sequence of binary digitsPwhich is placed as a prefix to each block. The other digits must then be constrained to keep the sequencePfrom appearing within a block. If blocks ofNdigits (including the prefixP) are used, the prefix should be chosen to make large the numberG(N)of different blocks which satisfy the constraints. Lengthening the prefix decreases the number of "message digits" which remain in the block but also relaxes the constraints. Thus, for eachN, there corresponds some optimum length of prefix. For each prefixP, a generating function, a recurrence formula, and an asymptotic formula for largeNare found forG(N). Tables ofG(N)are given for all prefixes of four digits or fewer. Among all prefixesPof a given lengthA, the one for whichG(N)has the most rapid growth isP = 11 \cdots 1. However, for this choice ofP, the table of values ofG(N)starts with small values;11 \cdots 1does not become the bestA-digit prefix untilNis very large. At these values ofN, the(A + 1) -digit prefix11 \cdots 10is still better. The tables suggest that, for anyN, a best prefix can always be found in the form11 \cdots 10, for suitableA. TakingP = 11 \cdots 10andA = [\log_2 (N \log_2 e)]it is shown thatG(N)is roughly0.35N^{-1} X2^N. This result is near optimal since no choice ofPcan makeG(N)exceedN^{-1}2^N.