Frame alignment and communication under strong asynchronism

We consider asynchronous communication over point-to-point discrete memoryless channels without feedback. The transmitter starts sending one block codeword at an instant that is uniformly distributed within a certain time period, which represents the level of asynchronism between the transmitter and the receiver. The receiver, by means of a sequential decoder, must isolate the message without knowing when the codeword transmission starts but being cognizant of the asynchronism level. We are interested in quick detection and isolation of the sent message, particularly in the regime where the asynchronism level is exponentially larger than the codeword length, which we refer to as 'strong asynchronism'. This model of sparse communication might represent, for instance, the situation of a sensor that remains idle most of the time and, only occasionally, transmits information to a remote base station which needs to quickly take action. Because of the limited amount of energy the sensor possesses, assuming the same cost per transmitted symbol, it is of interest to consider minimum size codewords given the asynchronism level. The first result is an asymptotic characterization of the largest asynchronism level, in terms of the codeword length, for which reliable communication can be achieved: vanishing error probability can be guaranteed as the codeword length N tends to infinity while the asynchronism level grows as e^Nα if and only if α does not exceed the synchronization threshold, a constant that admits a simple closed form expression, and is at least as large as the capacity of the synchronized channel. The second result is the characterization of a set of achievable strictly positive rates in the regime where the asynchronism level is exponential in the codeword length, and where the rate is defined with respect to the expected (random) delay between the time information starts being emitted until the time the receiver makes a decision. Interestingly, this achievability result is obtained by a coding strategy whose decoder not only operates asynchronously, but has also an almost universal decision rule, in the sense that it is almost independent of the channel statistics. As an application of the first result we consider antipodal signaling over a Gaussian additive channel and derive a simple necessary condition between blocklength, asynchronism level, and SNR for achieving reliable communication. Finally we note that the communcation model we study can be seen as a complement to the insertion, deletion, and substitution channel model introduced by Dobrushin in 1967. The chief difference is that this channel models timing uncertainty that result from the channel, whereas our setting models timing uncertainty caused by the users (or by a bursty source of information).