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

DOI10.1007/S10623-018-0476-3zbMATH Open1442.94063arXiv1706.06648OpenAlexW2675590473WikidataQ130113729 ScholiaQ130113729MaRDI QIDQ1801093FDOQ1801093

Authors: Wittawat Kositwattanarerk 

Publication date: 26 October 2018

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Which codes have cycle-free Tanner graphs?
• Title not available (Why is that?)
• Characterizations of pseudo-codewords of (low-density) parity-check codes
• Which Codes Have$4$-Cycle-Free Tanner Graphs?

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)