Optimal Sequential Frame Synchronization
Venkat Chandar, Aslan Tchamkerten, Gregory W. Wornell · IEEE Transactions on Information Theory · 2008
We consider the “one-shot frame synchronization problem,” 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 \rightarrow \infty$, if the asynchronism level grows as$O(e^{N\alpha})$, with$\alpha$below thesynchronization 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$N\rightarrow \infty$. 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.