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

arXiv:1706.06648 · Designs Codes and Cryptography

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

Wittawat Kositwattanarerk

Published Mar 23, 2018• 1 citation
arXivHTMLPDF
DOI
10.1007/s10623-018-0476-3

Related papers

On the Effective Weights of Pseudocodewords for Codes Defined on Graphs with Cycles

G. David Forney, R. Koetter, Frank R. Kschischang +1 more

The IMA volumes in mathematics and its applications•Jan 1, 2001•115 citations

Low density parity check lattices based on construction D' and cycle-free Tanner graphs.

Mohammad‐Reza Sadeghi, Daniel Panario

•Jan 1, 2003•8 citations

A Study on Removing Four-Cycle in Tanner Graph for Convolutional Codes(2)

Maekawa Naoki, Toshiyuki Shohon

Proceedings of the IEICE Engineering Sciences Society/NOLTA Society Conference•Aug 25, 2015•0 citations

Low density parity check lattices based on construction 𝐷′ and cycle-free Tanner graphs

Mohammad Ali Sadeghi, Daniel Panario

DIMACS series in discrete mathematics and theoretical computer science•Jul 19, 2005•3 citations

Which codes have cycle-free Tanner graphs?

T. Etzion, Ari Trachtenberg, Alexander Vardy

If a linear (n,k,d) code C has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes: we prove that d/spl les/max{2,2/R} for any linear code of rate R that can be represented by a cycle-free Tanner graph. Moreover, we explicitly construct codes that meet this bound with equality. We also show that all binary codes that have cycle-free Tanner graphs belong to the class of graph-theoretic cut-set codes. We conclude that the number of cycles in a Tanner graph must increase exponentially with the length n for asymptotically good codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•12 citations

Codes and Algorithms Based on Graphs

Richard E. Blahut

Cambridge University Press eBooks•Feb 6, 2003•0 citations
If a linear (n,k,d) code C has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes: we prove that d/spl les/max{2,2/R} for any linear code of rate R that can be represented by a cycle-free Tanner graph. Moreover, we explicitly construct codes that meet this bound with equality. We also show that all binary codes that have cycle-free Tanner graphs belong to the class of graph-theoretic cut-set codes. We conclude that the number of cycles in a Tanner graph must increase exponentially with the length n for asymptotically good codes.