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

Information technology newsletter

Research on decoding algorithm for convolutional codes based on factor graphs

GE Wan-cheng

Published Jan 1, 2006• 0 citations
OpenAlex

Abstract

A factor graph is a bipartite graph which expresses that how a global function of several variables is divided into a product of local functions.Taking together factor graphs with the sum-product algorithm represents a powerful tool for many communication engineers.This paper proposes a new decoding algorithm,which applies factor graphs and the sum-product algorithm to the decoding of communication systems.With help of simulation,the optimal number of the updates can be determined.

Related papers

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

Message-Passing Algorithm

Bane Vasic, Erozan M. Kurtas

A growing interest in the theory and application of iterative decoding algorithms was ignited by the impressive bit-error rate performance of the turbo-decoding algorithm demonstrated by Berrou et al. [3]. In the last several years, the turbo decoding algorithm has been generalized and mathematically formulated using a graph-theoretic approach. Such iterative decoding algorithms operate by “messagepassing” in graphs associated with codes and hence, they are referred to as the message-passing algorithms. The theory of codes on graphs has helped to improve the error performance of low-complexity decoding schemes. Also, it has opened new research avenues for investigating alternative suboptimal decoding schemes. One of the key results in the theory of codes on graphs comes from Kschischang et al. [8,9]. They generalized the concept of codes on graphs by introducing the idea of general functions on graphs. They derived a general distributed marginalization algorithm for function described by factor graphs. The theory of factor graphs and the sum-product algorithm generalizes a variety of algorithms developed in computer science and engineering. The belief propagation algorithm, developed by Pearl [14], operating on Bayesian networks is an instance of the sum-product algorithm operating on an appropriate factor graph.

CRC Press eBooks•Nov 9, 2004•2 citations

Codes on graphs

This chapter introduces a new code description. We first develop a graphical representation for the factorization of a function of several variables into a product of functions of a lower number of variables. This representation allows us to derive efficient algorithms for computing the marginals of the original function with respect to any one of its variables. Given a function describing membership in a code C . its marginalization leads to a method for decoding C . Thus, graphical representations of codes provide a natural setting for the description of symbol-by-symbol decoding techniques, much as the code trellis is a natural setting for the description of maximum-likelihood decoding using the Viterbi algorithm. This chapter is centered on these representations of codes and on a general procedure (the sum-product algorithm) for their decoding. The importance of the theory presented here lies in the fact that all known codes that approach capacity and are practically decodable admit a simple graphical representation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Kluwer Academic Publishers eBooks•Jul 5, 2006•0 citations

A note on a decoding algorithm of codes on graphs with small loops

N. Kobayashi, Tomoko K. MATSUSHIMA, Shigeichi Hirasawa

The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.

IEEE Information Theory Workshop (ITW)•Jan 1, 2005•1 citation

Constructing and Decoding of LDPC Codes Based on Factor Graphs

Liang Zhao

Low Density Parity Check(LDPC) Codes are a kind of linear block codes approaching Shannon limit. They can be constructed either with spare parity-check matrix or with factor graphs. According to various constructing methods of the codes,several decoding algorithms have been proposed so far. In this paper the constructing method of LDPC codes based on factor graph is introduced at the beginning, then the sum-product decoding algorithm(SPA) is analyzed. Finally the decoding process of LDPC based on SPA algorithm is discussed.

Telecommunication Engineering•Jan 1, 2004•0 citations

Codes defined on graphs

Frank R. Kschischang

Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.

IEEE Communications Magazine•Aug 1, 2003•62 citations
A factor graph is a bipartite graph which expresses that how a global function of several variables is divided into a product of local functions.Taking together factor graphs with the sum-product algorithm represents a powerful tool for many communication engineers.This paper proposes a new decoding algorithm,which applies factor graphs and the sum-product algorithm to the decoding of communication systems.With help of simulation,the optimal number of the updates can be determined.
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.
A growing interest in the theory and application of iterative decoding algorithms was ignited by the impressive bit-error rate performance of the turbo-decoding algorithm demonstrated by Berrou et al. [3]. In the last several years, the turbo decoding algorithm has been generalized and mathematically formulated using a graph-theoretic approach. Such iterative decoding algorithms operate by “messagepassing” in graphs associated with codes and hence, they are referred to as the message-passing algorithms. The theory of codes on graphs has helped to improve the error performance of low-complexity decoding schemes. Also, it has opened new research avenues for investigating alternative suboptimal decoding schemes. One of the key results in the theory of codes on graphs comes from Kschischang et al. [8,9]. They generalized the concept of codes on graphs by introducing the idea of general functions on graphs. They derived a general distributed marginalization algorithm for function described by factor graphs. The theory of factor graphs and the sum-product algorithm generalizes a variety of algorithms developed in computer science and engineering. The belief propagation algorithm, developed by Pearl [14], operating on Bayesian networks is an instance of the sum-product algorithm operating on an appropriate factor graph.
This chapter introduces a new code description. We first develop a graphical representation for the factorization of a function of several variables into a product of functions of a lower number of variables. This representation allows us to derive efficient algorithms for computing the marginals of the original function with respect to any one of its variables. Given a function describing membership in a code C . its marginalization leads to a method for decoding C . Thus, graphical representations of codes provide a natural setting for the description of symbol-by-symbol decoding techniques, much as the code trellis is a natural setting for the description of maximum-likelihood decoding using the Viterbi algorithm. This chapter is centered on these representations of codes and on a general procedure (the sum-product algorithm) for their decoding. The importance of the theory presented here lies in the fact that all known codes that approach capacity and are practically decodable admit a simple graphical representation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. For a binary erasure channel (BEC), the performance with this method goes up clearly.
Low Density Parity Check(LDPC) Codes are a kind of linear block codes approaching Shannon limit. They can be constructed either with spare parity-check matrix or with factor graphs. According to various constructing methods of the codes,several decoding algorithms have been proposed so far. In this paper the constructing method of LDPC codes based on factor graph is introduced at the beginning, then the sum-product decoding algorithm(SPA) is analyzed. Finally the decoding process of LDPC based on SPA algorithm is discussed.
Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.