COVERING PROPERTIES OF CONVOLUTIONAL-CODES AND ASSOCIATED LATTICES

The paper describes Markov methods for analyzing the expected and wors t case performance of sequence-based methods of quantization, We suppo se that the quantization algorithm is dynamic programming, where the c urrent step depends on a vector of path metrics, which we call a metri c function, Our principal objective is a concise representation of the se metric functions and the possible trajectories of the, dynamic prog ramming algorithm, We shall consider quantization of equiprobable bina ry data using a convolutional code, Here the additive group of the cod e splits the set of metric functions into a finite collection of subse ts, The subsets form the vertices of a directed graph, where edges are labeled by aggregate incremental increases in mean squared error (mse ), Paths in this graph correspond both to trajectories of the Viterbi algorithm, and to cosets of the code, For the rate 1/2 convolutional c ode [1 + D-2, 1 + D + D-2], this graph has only nine vertices, In this case it is particularly simple to calculate per dimension expected an d worst case mse, and performance is slightly better than the binary [ 24, 12] Golay code, Our methods also apply to quantization of arbitrar y symmetric probability distributions on [0, 1] using convolutional co des, For the uniform distribution on [0, 1], the expected mse is the s econd moment of the ''Voronoi region'' of an infinite-dimensional latt ice determined by the convolutional code, It may also be interpreted a s an increase in the reliability of a transmission scheme obtained by nonequiprobable signaling, For certain convolutional codes we obtain a formula for expected mse that depends only on the distribution of dif ferences for a single pair of path metrics.