Coding theorems for the nonsynchronized channel

Capacity and error bounds are derived for a memoryless binary symmetric channel with the receiver having no a priori information as to the starting time of the code words. The channel capacity is the same as the capacity of the synchronized channel. For all rates below capacity, the minimum probability of error for the nonsynchronized channel decreases exponentially with the code-block length. For rates near channel capacity, the exponent in the upper bound on the probability of error for the nonsynchronized channel is the same as the corresponding exponent for the synchronized channel. For low rates, the largest exponent obtained for the nonsynchronized channel with conventional block coding is inferior to the exponent obtained for the synchronized channel. Stronger results are obtained for a new form of coding that allows for a Markov dependency between successive code words. Bounds on the minimum probability of error are obtained for unconstrained binary codes and for several classes of parity-check codes and are used to obtain asymptotic distance properties for various classes of binary codes. At certain rates there exist codes whose minimum distance, in the comma-free sense, is not only greater than one, but is proportional to the block length.