Data synchronization with timing.

An important aspect of communications that has been overlooked by information theory pertains to the encoding and decoding of the time indices of the transmitted data, which is necessary in most situations where conventional data synchronization is needed. In this dissertation, a theory of data synchronization with timing (sync-timing) is developed, which deals with codes that enable the decoder to synchronize with the encoder and produce estimates of the time indices of the decoded data. The first part of this dissertation proposes and analyzes several kinds of fixed-rate sync-timing codes encoding binary data, that produce estimates of the time indices modulo the timing span, T, of the code. Analysis is on the basis of the maximum attainable timing span for a given coding rate R and permissible resynchronization delay D. Relatively simple codes are found to asymptotically attain the maximum timing span among such codes, which grows exponentially with delay, with exponent D(1 - R). Periodic prefix-synchronized (PPS) codes are a family of sync-timing codes characterized by a set of p distinct synchronizing markers of length m and codewords of length n. The second part of this dissertation studies (p, m, n) PPS codes with small values of p. A generating function method is developed which enables one to find the maximum rate of a (2, m, n) PPS code with a given pair of markers. An asymptotic analysis shows that for sufficiently large n, the marker pair (00...0,11...1) or (01010...,10101...) maximizes the rate among all (2, m, n) codes. This is used to show that for sufficiently large delays, p = 2 codes offer twice the timing span of p = 1 codes, at roughly the same rates and delays. The final part of this dissertation initiates a theory of sync-timing for variable-rate codes. A family of variable-rate sync-timing codes, called variable-rate cascaded (VRC) codes, is constructed and analyzed in terms of the performance measures of rate, delay and timing span. This analysis shows that the timing span of VRC codes can also grow exponentially with delay, and the rate of exponential growth is the same as that for fixed-rate sync-timing codes.PhDApplied SciencesElectrical engineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/127845/2/3029358.pd