Pseudocodeword-free criterion for codes with cycle-free Tanner graph

DOI10.1007/S10623-018-0476-3MaRDI QIDQ1801093zbMATH OpenOpenAlexWikidataFDO

Authors Wittawat Kositwattanarerk

Publication date 26 October 2018

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.06648

zbMATH Keywords

low-density parity-check (LDPC) codepseudocodewordsiterative decodinglinear programming decodingTanner graphs

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check (LDPC) codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.

Recommendations

• Which codes have cycle-free Tanner graphs?
• Which Codes Have$4$-Cycle-Free Tanner Graphs?
• scientific article; zbMATH DE number 1714650
• Iterative Decoding of Linear Block Codes: A Parity-Check Orthogonalization Approach
• scientific article; zbMATH DE number 1714662

Cites work

• A Decomposition Theory for Binary Linear Codes
• Analysis of Connections Between Pseudocodewords
• Characterizations of pseudo-codewords of (low-density) parity-check codes
• Construction of Regular and Irregular LDPC Codes: Geometry Decomposition and Masking
• Decomposition of regular matroids
• Design of capacity-approaching irregular low-density parity-check codes
• Factor graphs and the sum-product algorithm
• Lifting the Fundamental Cone and Enumerating the Pseudocodewords of a Parity-Check Code
• Low-density parity-check codes based on finite geometries: a rediscovery and new results
• Minimum Pseudoweight and Minimum Pseudocodewords of LDPC Codes
• On the Pseudocodeword Redundancy of Binary Linear Codes
• On the cycle polytope of a binary matroid
• Pseudocodewords of Tanner Graphs
• Using Linear Programming to Decode Binary Linear Codes
• Which codes have cycle-free Tanner graphs?

Cited in

(4)

• Which codes have cycle-free Tanner graphs?
• Characterizations of pseudo-codewords of (low-density) parity-check codes
• scientific article; zbMATH DE number 1714650 (Why is no real title available?)
• Which Codes Have$4$-Cycle-Free Tanner Graphs?

Describes a project that uses

Uses Software

• LDPC

This page was built for publication: Pseudocodeword-free criterion for codes with cycle-free Tanner graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801093)