Periodic prefix-synchronized codes: A generating function approach

A generating function method is developed in order to select synchronization markers that maximize the timing span of period-2 periodic prefix-synchronized (PPS) sync-timing coding with small delay. Sync-timing codes are used in situations where conventional data synchronization is required, and data time stamps or time indices are also needed. A PPS code is a sync-timing code in which each encoded block of data is preceded by a synchronization marker, with the markers preceding successive blocks forming a periodic sequence with some period p. Since only PPS codes with small periods can have good rates at small delays, and since codes with p=1 are simply Gilbert´s prefix-synchronized codes which have been studied previously in the literature, this paper focuses on p=2 codes. The generating function method, which extends that used by Guibas and Odlyzko to analyze p=1 codes, enables one to find PPS codes with the largest possible timing span among codes with a given delay and rate. It is found that at low delays such optimized PPS codes offer significant advantages over cascaded and natural marker PPS codes. They also compare favorably with embedded-index codes. Finally, for asymptotically large delays, it is shown that the best p=2 PPS codes operate at approximately the same rate and delay, but twice the timing span, of the best p=1 codes.