Optimal Sequential Frame Synchronization

We consider the ldquoone-shot frame synchronization problem,rdquo where a decoder wants to locate a sync pattern at the output of a memoryless channel on the basis of sequential observations. The sync pattern of length N starts being emitted at a random time within some interval of size A, where A characterizes the asynchronism level. We show that a sequential decoder can optimally locate the sync pattern, i.e., exactly, without delay, and with probability approaching one as N rarr infin, if the asynchronism level grows as O(eNalpha), with alpha below the synchronization threshold, a constant that admits a simple expression depending on the channel. If alpha exceeds the synchronization threshold, any decoder, sequential or nonsequential, locates the sync pattern with an error that tends to one as Nrarr infin. Hence, a sequential decoder can locate a sync pattern as well as the (nonsequential) maximum-likelihood decoder that operates on the basis of output sequences of maximum length A+N-1, but with far fewer observations.