Information Theoretic Perspectives on Synchronization

We study the information theoretic limits of communication over asynchronous discrete memoryless channels. The transmitter starts sending a block codeword of length N at a time v uniformly distributed within the interval [1, 2, ..., L]. We assume that the receiver knows L but not v. We give a scaling law of L with respect to N for which reliable communication can be achieved. Specifically, we propose a communication scheme with the property that, unless the asynchrony level L grows at least as e^NC, where C denotes the capacity of the synchronized channel, arbitrary low error probability can be achieved. If L grows sub-exponentially in N, the capacity is the same as that of the ordinary synchronized channel. Further, we provide a lower bound to the error probability given a certain channel, codebook, and asynchrony level. This bound together with our scheme shows that, in certain cases, the condition L les e^NC(1-delta) for any delta > 0 is an asymptotic necessary and sufficient condition for reliable communication. Finally we extend our analysis to a simple scenario where communication is carried over a Gaussian channel with antipodal signaling +radicP and -radicP. We show that a necessary condition on the amount of power needed in order to guarantee reliable communication is that P must scale as 1/NlogL when L rarr infin