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 International Symposium on Information Theory (ISIT)

Acyclic Tanner graphs and two-level decoding of linear block codes

Morteza Esmaeili, Amir Keyvan Khandani

Published Nov 27, 2002• 2 citations
Publisher

Abstract

For a linear block code C, the Wagner rule together with a subcode having an acyclic Tanner graph are applied to decode C in a two-level soft-decoding technique.
DOI
10.1109/isit.1998.708677

Related papers

Soft-decision decoding of block codes: a factor-graph approach (無線通信システム)

Y. Wei, Kambiz Homayounfar

電子情報通信学会技術研究報告. RCS, 無線通信システム•Feb 25, 2009•0 citations

Acyclic Tanner graphs and maximum-likelihood decoding of linear block codes

Morteza Esmaeili, Amir Keyvan Khandani

The maximum-likelihood decoding of linear block codes by Wagner rule decoding is discussed. In this approach, the Wagner rule decoding, which has been primarily applied to single parity check codes, is employed on acyclic Tanner graphs. Accordingly, a coset decoding equipped with Wagner rule decoding is applied to the decoding of a code C having a Tanner graph with cycles. A subcode C1 of C with acyclic Tanner graph is chosen as the base subcode. All cosets of C1 have the same Tanner graph and are distinguished by their values of parity nodes in the graph. The acyclic Tanner graph of C1, together with a trellis representation of the space of the parity sequences, represent the code C. This graphical representation provides a unified and systematic approach to search for an efficient method for the maximum-likelihood decoding of a given linear block code. It is shown that the proposed method covers the most efficient techniques known for the decoding of some important block codes, including the hexacode H6, extended Golay codes, Reed–Muller codes, Hamming code and (32, 16, 8) quadratic residue codes. The generalisation to the decoding of lattices is briefly explained.

IEE Proceedings - Communications•Jan 1, 2000•8 citations

Soft-Decision Decoding of Block Codes -- A Factor-Graph Approach

Wei Yongmei, Kambiz Homayounfar

IEICE Technical Report; IEICE Tech. Rep.•Feb 25, 2009•0 citations

On the pless-construction and ML decoding of the (48, 24, 12) quadratic residue code

Morteza Esmaeili, Thomas Aaron Gulliver, Amir Keyvan Khandani

We present a method for maximum likelihood decoding of the (48,24,12) quadratic residue code. This method is based on projecting the code onto a subcode with an acyclic Tanner graph, and representing the set of coset leaders by a trellis diagram. This results in a two level coset decoding which can be considered a systematic generalization of the Wagner rule. We show that unlike the (24,12,8) Golay code, the (48,24,12) code does not have a Pless-construction which has been an open question in the literature. It is determined that the highest minimum distance of a (48,24) binary code having a Pless (1986) construction is 10, and up to equivalence there are three such codes.

IEEE Transactions on Information Theory•May 29, 2003•4 citations

On the structure of the binary (18,9,6) linear code

Morteza Esmaeili

Let E/sub m/ denote the binary (m, m-1, 2) even weight code and /spl ominus/ the Kronecker product operation. A linear code of length m/spl times/t containing E/sub m//spl ominus/(t,1,t) can be decoded efficiently using a Tanner graph and a trellis diagram together with the Wagner decoding algorithm. Thus, it is important to determine whether a given code contains such a subcode. We show that the (18,9,6) binary quadratic residue code does not contain E/sub 6//spl ominus/(3,1,3). The maximum minimum distance of such a code is 5.

IEEE Information Theory Workshop (ITW)•Mar 1, 2004•0 citations

Bit-optimal decoding of codes whose Tanner graphs are trees

Emina Soljanin, Elke Offer

Discrete Applied Mathematics•May 1, 2003•0 citations
The maximum-likelihood decoding of linear block codes by Wagner rule decoding is discussed. In this approach, the Wagner rule decoding, which has been primarily applied to single parity check codes, is employed on acyclic Tanner graphs. Accordingly, a coset decoding equipped with Wagner rule decoding is applied to the decoding of a code C having a Tanner graph with cycles. A subcode C1 of C with acyclic Tanner graph is chosen as the base subcode. All cosets of C1 have the same Tanner graph and are distinguished by their values of parity nodes in the graph. The acyclic Tanner graph of C1, together with a trellis representation of the space of the parity sequences, represent the code C. This graphical representation provides a unified and systematic approach to search for an efficient method for the maximum-likelihood decoding of a given linear block code. It is shown that the proposed method covers the most efficient techniques known for the decoding of some important block codes, including the hexacode H6, extended Golay codes, Reed–Muller codes, Hamming code and (32, 16, 8) quadratic residue codes. The generalisation to the decoding of lattices is briefly explained.
We present a method for maximum likelihood decoding of the (48,24,12) quadratic residue code. This method is based on projecting the code onto a subcode with an acyclic Tanner graph, and representing the set of coset leaders by a trellis diagram. This results in a two level coset decoding which can be considered a systematic generalization of the Wagner rule. We show that unlike the (24,12,8) Golay code, the (48,24,12) code does not have a Pless-construction which has been an open question in the literature. It is determined that the highest minimum distance of a (48,24) binary code having a Pless (1986) construction is 10, and up to equivalence there are three such codes.
Let E/sub m/ denote the binary (m, m-1, 2) even weight code and /spl ominus/ the Kronecker product operation. A linear code of length m/spl times/t containing E/sub m//spl ominus/(t,1,t) can be decoded efficiently using a Tanner graph and a trellis diagram together with the Wagner decoding algorithm. Thus, it is important to determine whether a given code contains such a subcode. We show that the (18,9,6) binary quadratic residue code does not contain E/sub 6//spl ominus/(3,1,3). The maximum minimum distance of such a code is 5.