# Technical Report CS0925

 TR#: CS0925 Class: CS Title: Which Codes Have Cycle-Free Tanner Graphs? Authors: Tuvi Etzion, Ari Trachtenberg, Alexander Vardy PDF Not 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. Copyright The 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.