| TR#: | CS0925 |
| Class: | CS |
| Title: | Which Codes Have Cycle-Free Tanner Graphs? |
| Authors: | Tuvi Etzion, Ari Trachtenberg, Alexander Vardy |
| 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.
To the list of the CS technical reports of 1997
To the main CS technical reports page