Which codes have cycle-free Tanner graphs?
Authors:
- A. TrachtenbergATA. Trachtenberg
- A. VardyAVA. Vardy
- 1 September 1999
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 45 (6) , 2173-2181
Abstract
If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n2). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n,k,d) linear code of rate R=k/n that can be represented by a Tanner graph without cycles. We prove that if R⩾0.5 then d⩽2, while if R<0.5 then C is obtained from a code of rate ⩾0.5 and distance ⩽2 by simply repeating certain symbols. In the latter case, we prove that d⩽[n/k+1]+[n+1/k+1]<2/R. Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future researchKeywords
This publication has 17 references indexed in Scilit:
- Factor graphs and the sum-product algorithmIEEE Transactions on Information Theory, 2001
- Linear-time encodable and decodable error-correcting codesIEEE Transactions on Information Theory, 1996
- Near optimum error correcting coding and decoding: turbo-codesIEEE Transactions on Communications, 1996
- Codes and iterative decoding on general graphsEuropean Transactions on Telecommunications, 1995
- Neural networks, error-correcting codes, and polynomials over the binary n-cubeIEEE Transactions on Information Theory, 1989
- A recursive approach to low complexity codesIEEE Transactions on Information Theory, 1981
- Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)IEEE Transactions on Information Theory, 1974
- Graph theoretic error-correcting codesIEEE Transactions on Information Theory, 1968
- Cut-set matrices and linear codes (Corresp.)IEEE Transactions on Information Theory, 1965
- Low-density parity-check codesIEEE Transactions on Information Theory, 1962