Technical Report CS0925

TR#:CS0925
Class:CS
Title: Which Codes Have Cycle-Free Tanner Graphs?
Authors: Tuvi Etzion, Ari Trachtenberg, Alexander Vardy
PDFNot Available
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(n^2)$. 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 \geq 0.5$ then $d \leq 2$, while if $R < 0.5$ then $C$ is obtained from a code of rate $\geq 0.5$ and distance $\leq 2$ by simply repeating certain symbols. In the latter case, we show that $d \leq 2/R$. More precisly, we prove that $d \leq 2 \lfloor n/(k+1) \rfloor$ unless $(k+1)|(n+1)$, and $d \leq 2m-1$ if $n+1=m(k+1)$ for integer $m$. Furthermore, we show by means of an explicit construction that this bound on the minimum distance of $C$ is tight for all values of $n$ and $k$. We also prove that binary codes which have cycle-free Tanner graphs belong to the calss graph-theoretic codes, known as cut-set codes of a graph.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1997/CS/CS0925), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1997
To the main CS technical reports page

Computer science department, Technion