Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

Codes on graphs: normal realizations

G. David Forney

Published Jan 1, 2001• 628 citations
Publisher

Abstract

A generalized state realization of the Wiberg (1996) 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 (1981) 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.

DOI
10.1109/18.910573

Related papers

Codes and Decoding on General Graphs

Niclas Wiberg

Iterative decoding techniques have become a viable alternative for constructing high performance coding systems. In particular, the recent success of turbo codes indicates that performance close to the Shannon limit may be achieved. In this thesis, it is showed that many iterative decoding algorithms are special cases of two generic algorithms, the min-sum and sum-product algorithms, which also include non-iterative algorithms such as Viterbi decoding. The min-sum and sum-product algorithms are developed and presented as generalized trellis algorithms, where the time axis of the trellis is replaced by an arbitrary graph, the "Tanner graph". With cycle-free Tanner graphs, the resulting decoding algorithms (e.g., Viterbi decoding) are maximum-likelihood but suffer from an exponentially increasing complexity. Iterative decoding occurs when the Tanner graph has cycles (e.g., turbo codes); the resulting algorithms are in general suboptimal, but significant complexity reductions are possible compared to the cycle-free case. Several performance estimates for iterative decoding are developed, including a generalization of the union bound used with Viterbi decoding and a characterization of errors that are uncorrectable after infinitely many decoding iterations.

•Jan 1, 1996•869 citations

Tanner graphs for group block codes and lattices: construction and complexity

Amir H. Banihashemi, Frank R. Kschischang

We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.

IEEE Transactions on Information Theory•Jan 1, 2001•24 citations

On Decoding of Reed-Muller Codes Using a Local Graph Search

Mikhail Kamenev

We present a novel iterative decoding algorithm for Reed-Muller (RM) codes, which takes advantage of a graph representation of the code. Vertices of the considered graph correspond to codewords, with two vertices being connected by an edge if and only if the Hamming distance between the corresponding codewords equals the minimum distance of the code. The algorithm uses a greedy local search to find a node optimizing a metric, e.g. the correlation between the received vector and the corresponding codeword. In addition, the cyclic redundancy check can be used to terminate the search as soon as a valid codeword is found, leading to an improvement in the average computational complexity of the algorithm. Simulation results for both binary symmetric channel and additive white Gaussian noise channel show that the presented decoder approaches the performance of maximum likelihood decoding for RM codes of length less than 1024 and for the second-order RM codes of length less than 4096. Moreover, it is demonstrated that the considered decoding approach outperforms state-of-the-art decoding algorithms of RM codes with similar computational complexity for a wide range of block lengths and rates.

arXiv:2009.04338•IEEE Transactions on Communications•Apr 11, 2021•13 citations

On Factor Graphs and the Fourier Transform

Yongyi Mao, Frank R. Kschischang

We introduce the concept of convolutional factor graphs, which represent convolutional factorizations of multivariate functions, just as conventional (multiplicative) factor graphs represent multiplicative factorizations. Convolutional and multiplicative factor graphs arise as natural Fourier transform duals. In coding theory applications, algebraic duality of group codes is essentially an instance of Fourier transform duality. Convolutional factor graphs arise when a code is represented as a sum of subcodes, just as conventional multiplicative factor graphs arise when a code is represented as an intersection of supercodes. With auxiliary variables, convolutional factor graphs give rise to "syndrome realizations" of codes, just as multiplicative factor graphs with auxiliary variables give rise to "state realizations." We introduce normal and co-normal extensions of a multivariate function, which essentially allow a given function to be represented with either a multiplicative or a convolutional factorization, as is convenient. We use these function extensions to derive a number of duality relationships among the corresponding factor graphs, and use these relationships to obtain the duality properties of Forney graphs as a special case.

IEEE Transactions on Information Theory•Apr 25, 2005•38 citations

Conditionally Cycle-Free Graphical Models for Coset Codes

Thomas R. Halford, K.M. Chugg, Marcus T. Urie

Conditionally cycle-free graphical models (i.e., cyclic graphical models which become cycle-free after conditioning on a subset of the hidden variables) are constructed for coset codes. Following the description of a general construction procedure, examples of a number of families of codes-including first-order Reed-Muller (RM) and the Delsarte-Goethals codes - are provided for which the proposed procedure yields optimal soft-in soft-out (SISO) decoding algorithms that are less complex than the best known trellis-based algorithms. In the case of the first-order RM codes, which have a recursive coset construction, the optimal SISO decoding algorithm that results when the proposed construction is applied repeatedly is denoted recursive coset representation (RCR) decoding. Connections are made between RCR decoding and existing algorithms that exploit fast Hadamard transforms. Finally, the utility of the proposed decoding algorithms are supported by a practically motivated application: the construction of serially concatenated codes that have high rates and low error floors. Extended Hamming codes are proposed as outer codes in such constructions with efficient decoding employing the SISO algorithms developed herein.

IEEE Transactions on Information Theory•Jan 1, 2012•0 citations

An efficient decoding algorithm for cycle-free convolutional codes and its applications

Jing Li, Krishna R. Narayanan, C.N. Georghlades

This paper proposes an efficient graph-based sum-product algorithm for decoding 1/(1+D/sup n/) code, whose Tanner (1981) graph is cycle-free. A rigorous proof is given which shows the proposed algorithm is equivalent to the MAP decoding implementing the BCJR algorithm, but with a lower complexity magnitude. The paper presents an explicit example which confirms the claim that the sum-product algorithm is optimal on cycle-free graphs. A parallel realization is then discussed and shown to resemble low density parity check (LDPC) decoding. The paper further proposes a min-sum algorithm which is equivalent to the max-log-MAP algorithm. Prospective applications which can take advantage of the proposed decoding algorithms are discussed and simulations are provided.

Globecom•Nov 13, 2002•11 citations
A generalized state realization of the Wiberg (1996) 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 (1981) 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.
Iterative decoding techniques have become a viable alternative for constructing high performance coding systems. In particular, the recent success of turbo codes indicates that performance close to the Shannon limit may be achieved. In this thesis, it is showed that many iterative decoding algorithms are special cases of two generic algorithms, the min-sum and sum-product algorithms, which also include non-iterative algorithms such as Viterbi decoding. The min-sum and sum-product algorithms are developed and presented as generalized trellis algorithms, where the time axis of the trellis is replaced by an arbitrary graph, the "Tanner graph". With cycle-free Tanner graphs, the resulting decoding algorithms (e.g., Viterbi decoding) are maximum-likelihood but suffer from an exponentially increasing complexity. Iterative decoding occurs when the Tanner graph has cycles (e.g., turbo codes); the resulting algorithms are in general suboptimal, but significant complexity reductions are possible compared to the cycle-free case. Several performance estimates for iterative decoding are developed, including a generalization of the union bound used with Viterbi decoding and a characterization of errors that are uncorrectable after infinitely many decoding iterations.
We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.
We present a novel iterative decoding algorithm for Reed-Muller (RM) codes, which takes advantage of a graph representation of the code. Vertices of the considered graph correspond to codewords, with two vertices being connected by an edge if and only if the Hamming distance between the corresponding codewords equals the minimum distance of the code. The algorithm uses a greedy local search to find a node optimizing a metric, e.g. the correlation between the received vector and the corresponding codeword. In addition, the cyclic redundancy check can be used to terminate the search as soon as a valid codeword is found, leading to an improvement in the average computational complexity of the algorithm. Simulation results for both binary symmetric channel and additive white Gaussian noise channel show that the presented decoder approaches the performance of maximum likelihood decoding for RM codes of length less than 1024 and for the second-order RM codes of length less than 4096. Moreover, it is demonstrated that the considered decoding approach outperforms state-of-the-art decoding algorithms of RM codes with similar computational complexity for a wide range of block lengths and rates.
We introduce the concept of convolutional factor graphs, which represent convolutional factorizations of multivariate functions, just as conventional (multiplicative) factor graphs represent multiplicative factorizations. Convolutional and multiplicative factor graphs arise as natural Fourier transform duals. In coding theory applications, algebraic duality of group codes is essentially an instance of Fourier transform duality. Convolutional factor graphs arise when a code is represented as a sum of subcodes, just as conventional multiplicative factor graphs arise when a code is represented as an intersection of supercodes. With auxiliary variables, convolutional factor graphs give rise to "syndrome realizations" of codes, just as multiplicative factor graphs with auxiliary variables give rise to "state realizations." We introduce normal and co-normal extensions of a multivariate function, which essentially allow a given function to be represented with either a multiplicative or a convolutional factorization, as is convenient. We use these function extensions to derive a number of duality relationships among the corresponding factor graphs, and use these relationships to obtain the duality properties of Forney graphs as a special case.
Conditionally cycle-free graphical models (i.e., cyclic graphical models which become cycle-free after conditioning on a subset of the hidden variables) are constructed for coset codes. Following the description of a general construction procedure, examples of a number of families of codes-including first-order Reed-Muller (RM) and the Delsarte-Goethals codes - are provided for which the proposed procedure yields optimal soft-in soft-out (SISO) decoding algorithms that are less complex than the best known trellis-based algorithms. In the case of the first-order RM codes, which have a recursive coset construction, the optimal SISO decoding algorithm that results when the proposed construction is applied repeatedly is denoted recursive coset representation (RCR) decoding. Connections are made between RCR decoding and existing algorithms that exploit fast Hadamard transforms. Finally, the utility of the proposed decoding algorithms are supported by a practically motivated application: the construction of serially concatenated codes that have high rates and low error floors. Extended Hamming codes are proposed as outer codes in such constructions with efficient decoding employing the SISO algorithms developed herein.
This paper proposes an efficient graph-based sum-product algorithm for decoding 1/(1+D/sup n/) code, whose Tanner (1981) graph is cycle-free. A rigorous proof is given which shows the proposed algorithm is equivalent to the MAP decoding implementing the BCJR algorithm, but with a lower complexity magnitude. The paper presents an explicit example which confirms the claim that the sum-product algorithm is optimal on cycle-free graphs. A parallel realization is then discussed and shown to resemble low density parity check (LDPC) decoding. The paper further proposes a min-sum algorithm which is equivalent to the max-log-MAP algorithm. Prospective applications which can take advantage of the proposed decoding algorithms are discussed and simulations are provided.