Codes on graphs: Normal realizations
Codes on graphs: Normal realizations
复制标题
DOI：
10.1109/18.910573
复制
发表时间：
2001-02-01
影响因子：
2.5
通讯作者：
Forney, GD
中科院分区：
文献类型：
--
作者：
Forney, GD
如果符号变量的度数为 1，状态变量的度数为 2，则 Wiberg 类型的广义状态实现称为正规。这种实现的自然图形模型具有表示符号的叶边、表示状态的普通边和表示局部约束的顶点。这样的图可以通过任何版本的和积算法来解码。代码的任何状态实现都可以放入规范形式，而无需对相应的图或其解码复杂性进行本质改变，群或线性代码是由群或线性状态实现生成的。在无环图上，存在明确定义的最小规范实现，并且和积算法是精确的。然而，割集界表明，具有循环的图可能具有优越的性能-复杂性权衡，尽管和积算法是不精确且迭代的，并且最小实现没有明确定义。给出了 Reed-Muller (RM) 码的高效循环和无循环实现作为示例。适当定义的正常群实现的对偶生成对偶群码。对偶实现具有与原始实现相同的图拓扑，用其字符组替换符号和状态变量，并用其对偶替换原始局部约束。这一基本结果有许多应用，包括对偶状态空间、对偶最小网格、对偶到 Tanner 图、对偶输入/输出 (I/O) 系统以及对偶内核和图像表示。最后，可以使用对偶图对输入和输出进行适当的傅立叶变换来解码群码；这可以简化高速率代码的解码。
A generalized state realization of the Wiberg type is called normal if symbol variables have degree 1 and state variables have degree 2, A natural graphical model of such a realization has leaf edges representing symbols, ordinary edges representing states, and vertices representing local constraints. Such a graph can be decoded by any version of the sum-product algorithm. Any state realization of a code can be put into normal form without essential change in the corresponding graph or in its decoding complexity,Group or linear codes are generated by group or linear state realizations. On a cycle-free graph, there exists a well-defined minimal canonical realization, and the sum-product algorithm is exact. However, the Cut-Set Bound shows that graphs with cycles may have a superior performance-complexity tradeoff, although the sum-product algorithm is then inexact and iterative, and minimal realizations are not well-defined. Efficient cyclic and cycle-free realizations of Reed-Muller (RM) codes are given as examples.The dual of a normal group realization, appropriately defined, generates the dual group code. The dual realization has the same graph topology as the primal realization, replaces symbol and state variables by their character groups, and replaces primal local constraints by their duals. This fundamental result has many applications, including to dual state spaces, dual minimal trellises, duals to Tanner graphs, dual input/output (I/O) systems, and dual kernel and image representations. Finally, a group code may be decoded using the dual graph, with appropriate Fourier transforms of the inputs and outputs; this can simplify decoding of high-rate codes.