Optimal Sequential Frame Synchronization

Simple item page
dc.creatorChandar, Venkat
dc.creatorTchamkerten, Aslan
dc.creatorWornell, Gregory
dc.date2007-08-21
dc.date.accessioned2026-07-07T08:24:54Z
dc.date.available2026-07-07T08:24:54Z
dc.descriptionWe consider the `one-shot frame synchronization problem' where a decoder wants to locate a sync pattern at the output of a channel on the basis of sequential observations. We assume that the sync pattern of length N starts being emitted at a random time within some interval of size A, that characterizes the asynchronism level between the transmitter and the receiver. We show that a sequential decoder can optimally locate the sync pattern, i.e., exactly, without delay, and with probability approaching one as N tends to infinity, if and only if the asynchronism level grows as O(exp(N*k)), with k below the `synchronization threshold,' a constant that admits a simple expression depending on the channel. This constant is the same as the one that characterizes the limit for reliable asynchronous communication, as was recently reported by the authors. If k exceeds the synchronization threshold, any decoder, sequential or non-sequential, locates the sync pattern with an error that tends to one as N tends to infinity. Hence, a sequential decoder can locate a sync pattern as well as the (non-sequential) maximum likelihood decoder that operates on the basis of output sequences of maximum length A+N-1, but with much fewer observations.
dc.description6 pages
dc.identifierhttps://arxiv.org/abs/0708.2911
dc.identifierhttp://arxiv.org/abs/0708.2911
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/136498
dc.subjectInformation Theory
dc.subjectH.1.1
dc.titleOptimal Sequential Frame Synchronization
dc.typetext

Files

Collections

arXiv