The paper describes Markov methods for analyzing the expected and worst case performance of sequence-based methods of quantization. We suppose that the quantization algorithm is dynamic programming, where the current step depends on a vector of path metrics, which we call a metric function. Our principal objective is a concise representation of these metric functions and the possible trajectories of the dynamic programming algorithm. We shall consider quantization of equiprobable binary data using a convolutional code. Here the additive group of the code splits the set of metric functions into a finite collection of subsets. 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 code [1+D/sup 2/, 1+D+D/sup 2/], this graph has only nine vertices. In this case it is particularly simple to calculate per dimension expected and worst case MSE, and performance is slightly better than the binary [24, 12] Golay code. Our methods also apply to quantization of arbitrary symmetric probability distributions on [0, 1] using convolutional codes. For the uniform distribution on [0, 1], the expected MSE is the second moment of the "Voronoi region" of an infinite-dimensional lattice determined by the convolutional code. It may also be interpreted as 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 differences for a single pair of path metrics.
展开▼
机译：本文介绍了用于分析基于序列的量化方法的预期和最坏情况性能的马尔可夫方法。我们假设量化算法是动态编程，其中当前步骤取决于路径度量的矢量，我们称其为度量函数。我们的主要目标是对这些度量函数以及动态规划算法的可能轨迹的简明表示。我们将考虑使用卷积码对等概率二进制数据进行量化。在这里，代码的可加组将度量函数集划分为子集的有限集合。这些子集形成一个有向图的顶点，其中的边由均方误差（MSE）的合计增量式增长标记。该图中的路径既对应于维特比算法的轨迹，也对应于代码的同集。对于比率1/2卷积码[1 + D / sup 2 /，1 + D + D / sup 2 /]，此图只有9个顶点。在这种情况下，按预期的尺寸和最坏情况的MSE计算特别简单，并且性能比二进制[24，12] Golay代码稍好。我们的方法还适用于使用卷积码对[0，1]上的任意对称概率分布进行量化。对于[0，1]上的均匀分布，预期的MSE是由卷积码确定的无限维晶格的“ Voronoi区域”的第二矩。也可以解释为通过非等概率信令获得的传输方案的可靠性的提高。对于某些卷积码，我们获得了预期的MSE公式，该公式仅取决于一对路径度量对的差异分布。
展开▼
