Optimal frame synchronization over a finite state Markov channel

We study a problem of sequential frame detection over a finite state Markov channel (FSMC). We consider an asynchronous framework where a sync frame of length N symbols is transmitted uniformly over a large interval of known size A slots. In this setup, we study the scaling needed of the sync frame length N with the asynchronism interval length A for error-free frame synchronization. We study the problem when channel state information (CSI) is known at the transmitter and the receiver, and compute a synchronization threshold, α, that relates the average sync frame length N and A as N > log2(A)/α for asymptotic frame synchronization. Our discussion includes the description of a variable length and adaptive code word for FSMC that achieves the optimal delay performance.