koetter_li_vontobel_walker_itw2004_final2.tex

%***************************************************************************
%***************************************************************************

%\documentclass{amsart}

\documentclass{article}
\usepackage{itw2004}
\usepackage{amssymb, amsthm, amsmath}

%\usepackage[notcite,notref]{showkeys}

\usepackage{epsfig,bbm}

\input psfig.sty

%***************************************************************************
%***************************************************************************

%% \setlength{\oddsidemargin}{0in}
%% \setlength{\evensidemargin}{0in}
%% \setlength{\textwidth}{6.5in}
%% \setlength{\topmargin}{0in}
%% \setlength{\headheight}{0in}
%% \setlength{\headsep}{.25in}
%% \setlength{\topskip}{0in}
%% \setlength{\textheight}{9in}
\setcounter{MaxMatrixCols}{14}

%***************************************************************************
% New Theorem Environments
%***************************************************************************

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

\theoremstyle{definition}  % Take this instead of \theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}



%***************************************************************************
% Abbreviations
%***************************************************************************

\def\F{{\mathbb{F}}}
\def\Z{{\mathbb{Z}}}
\def\N{{\mathbb{N}}}
\def\X{{\mathbf{X}}}
\def\V{{\mathbf{V}}}
\def\E{{\mathbf{E}}}
\def\cC{{\mathcal{C}}}
\def\cP{{\mathcal{P}}}
\def\del{{\partial}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rp}{\mathbb{R}_{+}}
\newcommand{\Rpp}{\mathbb{R}_{++}}
%% \newcommand{\matr}[1]{\mathbf{#1}}
\newcommand{\matr}[1]{#1}
\newcommand{\vect}[1]{\mathbf{#1}}
%% \newcommand{\set}[1]{\mathcal{#1}}
\newcommand{\set}[1]{#1}
%% \newcommand{\code}[1]{\mathcal{#1}}
\newcommand{\code}[1]{#1}
%% \newcommand{\graph}[1]{\mathsf{#1}}
\newcommand{\graph}[1]{#1}

\newcommand{\vb}{\vect{b}}
\newcommand{\vc}{\vect{c}}
\newcommand{\ve}{\vect{e}}
\newcommand{\vf}{\vect{f}}
\newcommand{\vn}{\vect{n}}
\newcommand{\vp}{\vect{p}}
\newcommand{\hvc}{\vect{\hat c}}
\newcommand{\tvc}{\vect{\widetilde c}}
\newcommand{\htvc}{\vect{\hat {\widetilde c}}}
\newcommand{\vu}{\vect{u}}
\newcommand{\vw}{\vect{w}}
\newcommand{\vi}{\vect{i}}
\newcommand{\vX}{\vect{X}}
\newcommand{\tvX}{\vect{\widetilde X}}
\newcommand{\vx}{\vect{x}}
\newcommand{\vxa}{\vect{x}^{\mathrm{a}}}
\newcommand{\vxb}{\vect{x}^{\mathrm{b}}}
\newcommand{\tvx}{\vect{\widetilde x}}
\newcommand{\vY}{\vect{Y}}
\newcommand{\tvY}{\vect{\widetilde Y}}
\newcommand{\vy}{\vect{y}}
\newcommand{\tvy}{\vect{\widetilde y}}
\newcommand{\vz}{\vect{z}}

\newcommand{\dirX}{\vec X}
\newcommand{\dirN}{\vec N}
\newcommand{\dirV}{\vec V}
\newcommand{\dirE}{\vec E}

\newcommand{\vlambda}{\boldsymbol{\lambda}}
\newcommand{\vomega}{\boldsymbol{\omega}}
\newcommand{\vnu}{\boldsymbol{\nu}}
\newcommand{\vzeta}{\boldsymbol{\zeta}}

\newcommand{\vzero}{\vect{0}}

\newcommand{\fp}[1]{\mathcal{#1}}
\newcommand{\pfp}[1]{\dot{\mathcal{#1}}}
\newcommand{\fc}[1]{\mathcal{#1}}
\newcommand{\pfc}[1]{\dot{\mathcal{#1}}}
\newcommand{\fph}[2]{\mathcal{#1}(\matr{#2})}
\newcommand{\pfph}[2]{\dot{\mathcal{#1}}(\matr{#2})}
%\newcommand{\fch}[2]{\mathcal{#1}(\matr{#2})}
\newcommand{\fch}[2]{{#1}(\matr{#2})}
\newcommand{\pfch}[2]{\dot{\mathcal{#1}}(\matr{#2})}


\newcommand{\dmin}{d_{\mathrm{min}}}
\newcommand{\wH}{w_{\mathrm{H}}}
\newcommand{\wps}{w_{\mathrm{p}}}
\newcommand{\wpsAWGNC}{w_{\mathrm{p}}^{\mathrm{AWGNC}}}
\newcommand{\wpsminAWGNC}{w_{\mathrm{p}, \mathrm{min}}^{\mathrm{AWGNC}}}
\newcommand{\wpsBSC}{w_{\mathrm{p}}^{\mathrm{BSC}}}
\newcommand{\wpsBEC}{w_{\mathrm{p}}^{\mathrm{BEC}}}
\newcommand{\wpsmin}{w_{\mathrm{p}}^{\mathrm{min}}}
\newcommand{\wpsminc}[1]{\wpsmin(\code{#1})}
\newcommand{\wpsminh}[1]{\wpsmin(\matr{#1})}

%% \newcommand{\matrunity}{\mathbbm{1}}

\newcommand{\matrunity}{I}

\newcommand{\conhull}{\operatorname{conhull}}
\newcommand{\boundary}{\del}

\newcommand{\Gcone}{\matr{G}_{\mathrm{cone}}}
\newcommand{\Hcone}{\matr{H}_{\mathrm{cone}}}

\newcommand{\tr}{\mathsf{T}}

\newcommand{\GF}[1]{\mathbb{F}_{#1}}

\newcommand{\defeq}{\triangleq}


%***************************************************************************
% Begin Document
%***************************************************************************

\begin{document}

%***************************************************************************

\topmargin = 0mm

%***************************************************************************

\itwtitle{Pseudo-Codewords of Cycle Codes via Zeta Functions%
  \footnote[0]{dummytext}}

%***************************************************************************

\itwauthor{Ralf Koetter\footnote{dummytext}}
{Coordinated Science Lab. \\
University of Illinois \\
Urbana, IL  61801 \\
{\tt koetter@uiuc.edu}
}

\itwsecondauthor{Wen-Ching W.\ Li\footnote{dummytext}}
{Department of Mathematics\\
Pennsylvania State University\\
University Park, PA 16802-6401\\
\tt{wli@math.psu.edu}
}

\itwthirdauthor{Pascal O.\ Vontobel\footnote{dummytext}}
{Coordinated Science Lab. \\
University of Illinois \\
Urbana, IL  61801 \\
\tt{vontobel@ifp.uiuc.edu}
}

\itwfourthauthor{Judy L.\ Walker\footnote{dummytext}}
{Department of Mathematics\\
University of Nebraska\\
Lincoln, NE  68588-0130\\
{\tt jwalker@math.unl.edu}
}

%***************************************************************************

\itwmaketitle

%***************************************************************************
 
\footnotetext[0]{This is essentially the paper that was presented at the IT
                 Workshop 2004, San Antonio, TX, USA. We replaced ``Newton
                 polytope'' by ``Newton polyhedron'' throughout the text and
                 corrected a slight unpreciseness in
                 Th.~\ref{theorem:pseudos:in:cycle:1}}

\footnotetext[1]{R.~Koetter's research was partially supported by NSF Grants
                 CCR 99-84515 and CCR 01-05719.}

\footnotetext[2]{W.-C.~W.~Li's research was partially supported by NSA Grant
                 MDA904-03-1-0069.}

\footnotetext[3]{P.~O.~Vontobel is now with the ECE Dept., University of
                 Wisconsin-Madison, USA, {\tt vontobel@ece.wisc.edu}; his
                 research was partially supported by NSF Grants CCR 99-84515
                 and CCR 01-05719.}

\footnotetext[4]{J.~L.~Walker's research was partially supported by NSF Grant
                 DMS 03-02024.}

%***************************************************************************

\begin{itwabstract} 
  Cycle codes are a special case of low-density parity-check (LDPC) codes and
  as such can be decoded using an iterative message-passing decoding algorithm
  on the associated Tanner graph. The existence of pseudo-codewords is known
  to cause the decoding algorithm to fail in certain instances. In this paper,
  we draw a connection between pseudo-codewords of cycle codes and the
  so-called edge zeta function of the associated normal graph and show how the
  Newton polyhedron of the zeta function equals the fundamental cone of the
  code, which plays a crucial role in characterizing the performance of
  iterative decoding algorithms.
\end{itwabstract}

%***************************************************************************

\begin{itwpaper}

%***************************************************************************

\vspace{-1mm}
%***************************************************************************

\itwsection{Introduction}

%***************************************************************************
\vspace{-1mm}

We are interested in characterizing the performance of a binary
low-density parity-check (LDPC) code $\code{C}$ used for the
transmission of information over a memoryless channel. Moreover, we
focus on the case that iterative decoding is performed at the receiver
end.

Let the code be described by a parity-check matrix $\matr{H}$. To a
matrix $H$ we can associate a bipartite graph, the so-called Tanner
graph $T \defeq T(\matr{H})$~\cite{Tanner:81}. % The common principle of
% iterative decoding algorithms is to pass messages along the edges of
% $T$.
As was realized in~\cite{Koetter:Vontobel:03:1}, an essential role in
the understanding of iterative decoding is played by the finite covers
of the Tanner graph $T$ and the codes defined by them. In fact, while
the main strength of iterative decoders, namely their low complexity,
results from the fact that they operate {\em locally} on the Tanner
graph, this very fact is also the source of the weakness of any
iterative decoding algorithm. The systemic problem is that by just
performing local operations the decoder cannot distinguish if it is
decoding on the Tanner graph $T$ or any of the finite covers. Thus,
codewords in a cover of $T$ will be interfering with the iterative
decoding process.  Consequently, in order to understand the behavior
of iterative decoders we will have to characterize the ``covering''
codes and their codewords.

The goal of this paper is to give a concise geometric and simple
description of these codes in finite covers of $T$.  In particular,
the geometric characterization will relate to a cone in Euclidean
space, the so-called fundamental cone~\cite{Koetter:Vontobel:03:1}.

%  As it happens, it is
% not really necessary to study all the codewords that live in all the finite
% covers~\cite{Koetter:Vontobel:03:1}: it turns out that this problem is
% equivalent to the much simpler problem of studying the vectors (more
% precisely, the pseudo-codewords) that lie in a certain cone called the
% fundamental cone.

We focus on a special class of LDPC codes, namely the class of cycle
codes. These codes are informally defined as LDPC codes where all bit
nodes  have degree two.\footnote{The reason for the
  name ``cycle codes'' will become clear in
  Sec.~\ref{sec:binary:linear:codes:1}.}

From a practical point of view cycle codes are somewhat marred by the
fact that their minimum distance grows (at best) logarithmically in
the block length (assuming fixed check-node degrees). Nevertheless,
their properties make them more amenable to analysis than general LDPC
codes.  In any case, cycle codes can be seen as an interesting object
of study from which results can (hopefully) be suitably generalized to
the more interesting class of LDPC codes where part or all of the bit
nodes have degree at least three.

The connections between iterative decoding and LDPC codes are probably best
understood for cycle codes. First of all, the fundamental cone can be related
concisely to the decoding behavior under iterative decoding, and secondly, as
we aim to show in this paper, the fundamental cone may be identified as the
Newton polyhedron of Hashimoto's edge zeta function \cite{Hashimoto:89:1}
associated to the normal graph (defined in
Sec.~\ref{sec:binary:linear:codes:1}) of the code.  For an early reference
about the performance of iterative decoding techniques in conjunction with
cycle codes see \cite[ch.6]{nicwi}.  In the case of general LDPC codes, the
relation of the fundamental cone to the exact characterization of the
iterative decoding behavior is more intricate. Nevertheless, even here the
fundamental cone gives an amazingly exact picture of the
behavior.\footnote{The behavior of the linear programming
decoder~\cite{Feldman:Karger:Wainwright:03:2} (for the most canonical
relaxation) is \emph{exactly} characterized by the fundamental cone in the
cycle code case \emph{and} in the non-cycle code case.}  While we here only
establish the connection between the fundamental cone and the edge zeta
function for cycle codes, we conjecture the existence of such a zeta function
for the case of general LDPC codes.


This paper is structured as follows: Sec.~\ref{sec:binary:linear:codes:1}
introduces the basics about Tanner graphs and normal graphs of binary linear
codes and Sec.~\ref{sec:fundamental:cone} discusses graph covers and the
fundamental cone associated with a code. The notion of an edge zeta function
of a graph will be introduced in Sec.~\ref{sec:zeta:functions:1} and
Sec.~\ref{sec:connection:fundamental:cone:zeta:function:1} discusses the main
result of this paper, namely the identification of the fundamental cone and
the Newton polyhedron in the case of cycle codes. Throughout the whole paper
we will use two running examples containing two different codes, namely Code A
and Code B: the first is \emph{not} a cycle code whereas the latter one is a
cycle code.

%***************************************************************************
%***************************************************************************

\itwsection{Binary Linear Codes and Their Graphs}

\label{sec:binary:linear:codes:1}

%***************************************************************************

\begin{definition}
  \label{def:undirected:graph:1}

  An \emph{undirected graph} $\graph{X} =
  \graph{X}(\set{V}(\graph{X}), \set{E}(\graph{X}))$ consists of a
  vertex-set $\set{V} \defeq \set{V}(\graph{X})$ and an edge-set
  $\set{E} \defeq \set{E}(\graph{X})$ where the elements of $\set{E}$
  are 2-subsets of $\set{V}$. We assume a fixed ordering on $E$ so
  that $E = \{e_1, \dots, e_n\}$, where $n \defeq n(X) \defeq |E|$. By
  a {\em graph} (without further qualifications) we will always mean an
  undirected graph. We will not allow self-loops or multiple
  edges. For $v \in V$, we write $\del(v)$ for the {\em neighborhood}
  of $v$, i.e., the collection of vertices of $X$ which are adjacent
  to $v$.
\end{definition}

%***************************************************************************

\begin{definition}
  \label{def:column:row:indices:1}
  
  Let\footnote{Note the following convention: a row index of
  $\matr{H}$ will be denoted by $j$ and a column index of $\matr{H}$
  will be denoted by $i$.}  $\matr{H} = (h_{ji})$ be the parity-check
  matrix of a binary linear code $\code{C}$. We let $\set{J} \defeq
  \set{J}(\matr{H})$ be the set of row indices of $\matr{H}$ and we
  let $\set{I} \defeq \set{I}(\matr{H})$ be the set of column indices
  of $\matr{H}$, respectively. For each $i \in \set{I}$, we let
  $\set{J}_i \defeq \set{J}_i(\matr{H}) \defeq \big\{ j \in \set{J} \
  | \ h_{ji} {=} 1 \big\}$. For each $j \in \set{J}$, we let
  $\set{I}_j \defeq \set{I}_j(\matr{H}) \defeq \big\{ i \in \set{I} \
  | \ h_{ji} {=} 1 \big\}$. Furthermore, for any $\set{I}' \subseteq
  \set{I}$ and any vector $\vx$ of length $|\set{I}|$, we let
  $\vx_{\set{I}'}$ be the vector that has only the entries of $\vx$
  whose indices are in $\set{I}'$. The Tanner graph~\cite{Tanner:81}
  (or factor graph~\cite{Kschischang:Frey:Loeliger:01}) associated to
  $\matr{H}$ will be called $\graph{T}(\matr{H})$: it consists of bit
  nodes $X_1, \ldots, X_{|\set{I}|}$, (parity-)check nodes $p_1,
  \ldots, p_{|\set{J}|}$, and edges between the two types of
  nodes. More precisely, bit node $i$ and check node $j$ are connected
  if and only if $h_{ji} = 1$. The degree of bit node $i$ is the
  number of adjacent check nodes in $\graph{T}(\matr{H})$ and is
  therefore equal to $|J_i(\matr{H})|$. The degree of check node $j$
  is the number of adjacent bit nodes in $\graph{T}(\matr{H})$ and is
  therefore equal to $|I_j(\matr{H})|$. We say that a vector $\vx \in
  \GF{2}^{|\set{I}|}$ is a configuration of the Tanner graph
  $\graph{T}(\matr{H})$ and we call $\vx \in \GF{2}^{|\set{I}|}$ a
  valid configuration if all the checks are fulfilled, i.e. $\sum_{i
  \in \set{I}} h_{ji} x_i = \sum_{i \in \set{I}_j} x_i = 0 \text{ (in
  $\GF{2}$)}$ for all $j \in \set{J}$. Obviously, the set of all valid
  configurations forms the linear binary code $\code{C}$.
\end{definition}

%***************************************************************************

\begin{definition}
  A binary linear code $\code{C}$ defined by a parity-check matrix
  $\matr{H}$ is called a cycle code if the associated Tanner graph
  $T(H)$ is $2$-regular in the bit nodes, i.e.~all bit nodes have
  degree $2$. This is equivalent to the condition that for all $i \in
  \set{I}(\matr{H})$ we have $|J_i(\matr{H})| = 2$. Such codes were
  studied e.g.~in~\cite{Hakimi:Bredeson:68:1}.
\end{definition}

%***************************************************************************

\begin{figure}
  \begin{center}
    \epsfig{figure=fg_cover1_2mod4.fig.eps,width=2.5in}
  \end{center}
  \caption{ (Code A) Left: Tanner graph $T(\matr{H})$ of the simple
           binary linear code in Ex.~\ref{ex:simple:code:1}. Right:
           Tanner graph of an example of an $M$-cover of
           $T(\matr{H})$.}
  \label{fig:simple:code:1}
\end{figure}

%***************************************************************************

\begin{example}[Code A]
  \label{ex:simple:code:1}

  Let $\code{C}$ be a binary $[4,2]$ code with parity-check matrix
  \begin{align*}
    \matr{H}
      &\defeq
         \begin{pmatrix}
           1 & 1 & 1 & 0 \\
           0 & 1 & 1 & 1
         \end{pmatrix}.
  \end{align*}
  Obviously, $\code{C} = \big\{ (0,0,0,0), (0,1,1,0), (1,0,1,1), (1,1,0,1)
  \big\}$, $\set{J} = \{ 1, 2 \}$, $\set{J}_1 = \{ 1 \}$, $\set{J}_2 = \{ 1, 2
  \}$, $\set{J}_3 = \{ 1, 2 \}$, $\set{J}_4 = \{ 2 \}$, $\set{I} = \{ 1, 2, 3,
  4 \}$, $\set{I}_1 = \{ 1, 2, 3 \}$, and $\set{I}_2 = \{ 2, 3, 4 \}$. The
  Tanner graph $\graph{T}(\matr{H})$ that is associated to $\matr{H}$ is shown
  in Fig.~\ref{fig:simple:code:1} (left); it can easily be seen that this
  is \emph{not} a cycle code.
\end{example}

%***************************************************************************

\begin{example}[Code B]
  \label{ex:simple:code:2}
 
  {\sloppy

  Let $\code{C}$ be a binary $[7,2]$ code with parity-check matrix
  \begin{align*}
    \matr{H}
      &\defeq
         \begin{pmatrix}
           1 & 1 & 0 & 0 & 0 & 0 & 0 \\
           0 & 1 & 1 & 1 & 0 & 0 & 0 \\
           1 & 0 & 1 & 0 & 0 & 0 & 0 \\
           0 & 0 & 0 & 1 & 1 & 0 & 1 \\
           0 & 0 & 0 & 0 & 1 & 1 & 0 \\
           0 & 0 & 0 & 0 & 0 & 1 & 1
         \end{pmatrix}.
  \end{align*}
  Obviously, $\code{C} = \big\{ (0,0,0,0,0,0,0), (1,1,1,0,0,0,0), (0,0,0,0,$
  $1,1,1), (1,1,1,0,1,1,1) \big\}$.\footnote{Note that the rank of $\matr{H}$
  is $5$ and not $6$: therefore the dimension of $\code{C}$ is $2$ and not
  $1$.} The Tanner graph $T(\matr{H})$ of $\code{C}$ is shown in
  Fig.~\ref{fig:simple:code:2} (left). As can easily be seen, all bit nodes
  have degree $2$ and so the code $\code{C}$ is a cycle code. From the Tanner
  graph $T(\matr{H})$ we can derive another graph $N(\matr{H})$ in the
  following way: replace each (degree-$2$) bit node and its adjacent edges by
  a single edge and label the new edge according to the labeling of the bit
  node in the Tanner graph.\footnote{We gave the label $N(\matr{H})$ because
  such a graph is also known as normal graph or Forney-style factor
  graph~\cite{Forney:01:1}.} For code $\code{C}$ we obtain the graph
  $N(\matr{H})$ shown in Fig.~\ref{fig:simple:code:2} (right). From this graph
  the notion of ``cycle code'' becomes clear: every codeword (i.e.~every valid
  configuration) corresponds to a simple cycle or a symmetric difference set of
  simple cycles in the normal graph. This will be made more precise in
  Sec.~\ref{sec:zeta:functions:1}.

  }
\end{example}

%***************************************************************************

\begin{figure}[t]
  \begin{center}
    \epsfig{figure=simple_code2.fig.eps, width=2.5in}
  \end{center}
  \caption{ (Code B) Left: Tanner graph $T(\matr{H})$ of the cycle code
           $\code{C}$ in Ex.~\ref{ex:simple:code:2}. Right: Normal graph
           $N(\matr{H})$ of the cycle code $\code{C}$ in
           Ex.~\ref{ex:simple:code:2}.}
  \label{fig:simple:code:2}
\end{figure}

%***************************************************************************

\begin{figure}
  \begin{center}
    \epsfig{figure=simple_code2_doublecover1_mod2.fig.eps,width=2.5in}
  \end{center}
  \caption{(Code B) Left: A double cover of the Tanner graph
           $T(\matr{H})$ in Fig.~\ref{fig:simple:code:2}
           (left). Right: The corresponding double cover of the normal
           graph $N(\matr{H})$ in Fig.~\ref{fig:simple:code:2}
           (right).}
  \label{fig:simple:code:2:cover:1}
\end{figure}


%***************************************************************************
%***************************************************************************

\itwsection{The Fundamental Cone}

\label{sec:fundamental:cone}

%***************************************************************************

The following definition introduces the  graph theoretic notion of a
``graph cover''.

%***************************************************************************

\begin{definition}
  \cite{Massey:77:1, Stark:Terras:96:1} An {\em unramified, finite cover}, or,
  simply, a {\em cover} of a graph $X$ is a graph $Y$ along with a surjective
  map $\pi:Y \to X$ which is a graph homomorphism, i.e., which takes adjacent
  vertices of $Y$ to adjacent vertices of $X$, such that for each vertex $x$
  of $X$ and each $y \in \pi^{-1}(x)$, the neighborhood $\del(y)$ of $y$ is
  mapped bijectively to $\del(x)$.  For a positive integer $M$, an {\em
  $M$-cover} of $X$ is an unramified finite cover $\pi:Y \to X$ such that for
  each vertex $x$ of $X$, $\pi^{-1}(x)$ contains exactly $M$ vertices of $Y$.
\end{definition}

%***************************************************************************

\begin{example}[Code A]
  \label{ex:simple:code:1:cover:1}

  We continue with Code A defined in Ex.~\ref{ex:simple:code:1}. Let
  $\graph{T} \defeq \graph{T}(\matr{H})$ be the Tanner graph corresponding to
  $\matr{H}$. An $M$-fold cover $\graph{\widetilde T}$ (as shown in
  Fig.~\ref{fig:simple:code:1} (right)) of $\graph{T}$ is specified by
  defining the permutations $\pi_{1,1}$, $\pi_{1,2}$, $\pi_{1,3}$
  (corresponding to the first row of $\matr{H}$) and the permutations
  $\pi_{2,2}$, $\pi_{2,3}$, $\pi_{2,4}$ (corresponding to the second row of
  $\matr{H}$).

  The parity-check matrix $\matr{\widetilde H}$ associated to one
  possible $3$-fold cover Tanner graph $\graph{\widetilde T}$ looks
  like
  \begin{align*}
    \matr{\widetilde H}
      &\defeq
         \left(
           \begin{array}{ccc|ccc|ccc|ccc}
             0 & 1 & 0  &  1 & 0 & 0  &  0 & 1 & 0  &  0 & 0 & 0 \\
             0 & 0 & 1  &  0 & 1 & 0  &  0 & 0 & 1  &  0 & 0 & 0 \\
             1 & 0 & 0  &  0 & 0 & 1  &  1 & 0 & 0  &  0 & 0 & 0 \\
             \hline
             0 & 0 & 0  &  0 & 0 & 1  &  0 & 0 & 1  &  1 & 0 & 0 \\
             0 & 0 & 0  &  1 & 0 & 0  &  1 & 0 & 0  &  0 & 1 & 0 \\
             0 & 0 & 0  &  0 & 1 & 0  &  0 & 1 & 0  &  0 & 0 & 1
           \end{array}
         \right) \\
       &= \begin{pmatrix}
           \matrunity_2 & \matrunity_0 & \matrunity_2 & \matr{0} \\
           \matr{0}     & \matrunity_1 & \matrunity_1 & \matrunity_0
         \end{pmatrix},
  \end{align*}
  where $\matrunity_s$ is a $3 \times 3$ identity matrix, cyclically
  shifted to the left by $s$ positions. This parity-check matrix
  defines a code $\code{\widetilde{C}}$: an example of a codeword of
  $\code{\widetilde{C}}$ is $\tvc = (1,1,0, \ 0,1,1, \ 0,1,1, \
  0,0,0)$.
\end{example}

%***************************************************************************

\begin{figure}
  \begin{center}
    \epsfig{figure=simple_code2_directed1.fig.eps,width=1.5in}
  \end{center}
  \caption{(Code B) A directed normal graph of the normal graph
           $N(\matr{H})$ in Fig.~\ref{fig:simple:code:2} (left).}
  \label{fig:simple:code:2:directed:1}
\end{figure}

%***************************************************************************

Other examples of a graph cover are shown in
Fig.~\ref{fig:simple:code:2:cover:1}: the left-hand side shows a double cover
Tanner graph of the Tanner graph in Fig.~\ref{fig:simple:code:2} (left) and
the right-hand side shows the corresponding double cover normal graph of the
normal graph in Fig.~\ref{fig:simple:code:2} (right). The following remark
formalizes Ex.~\ref{ex:simple:code:1:cover:1}.

%***************************************************************************

\begin{remark}\label{rmk:temp:1}
  Let $\code{C}$ be a binary code with parity-check matrix $\matr{H}$
  and Tanner graph $\graph{T} \defeq \graph{T}(\matr{H})$. Let
  $\set{J} \defeq \set{J}(\matr{H})$ and $\set{I}_j \defeq
  \set{I}_j(\matr{H})$. For a positive integer $M$, let
  $\graph{\widetilde T}$ be an arbitrary $M$-fold cover of $\graph{T}$
  and let $\code{\widetilde C}$ be the binary code described by
  $\graph{\widetilde T}$. Knowing the graph $\graph{T}$, the graph
  $\graph{\widetilde T}$ is completely specified by defining for all
  $j \in \set{J}$ and all $i \in \set{I}_j$ the permutations
  $\pi_{j,i}$ that map $[M] \defeq \{ 1, \ldots, M \}$ onto
  itself. The meaning of $\pi_{j,i}(m)$, $m \in [M]$ is the following:
  the $m^{\text{th}}$ copy of the check node $j$ is connected to the
  $\pi_{j,i}(m)^{\text{th}}$ copy of the $i^{\text{th}}$ bit.  It
  follows that $\tvc \in \code{\widetilde C}$ if and only if
  \begin{align*}
    \sum_{i \in \set{I}_j}
      \widetilde c_{i,\pi_{j,i}(m)}
      &= 0 \quad \text{(in $\GF{2}$)}
             \label{eq:remark:parity:check:equality:cover:code:1}
  \end{align*}
  for all $j \in \set{J}$ and all $m \in [M]$. The parity-check matrix
  $\matr{\widetilde H}$ that expresses this fact can be defined as
  follows. Let the entries of $\matr{\widetilde H}$ be indexed by $(j,m) \in
  \set{J} \times [M]$ and $(i,m') \in \set{I} \times [M]$.  Then
  \begin{align*}
    h_{(j,m),(i,m')}
      &\defeq
         \begin{cases}
           1 & \text{if $i \in \set{I}_j$ and $m' = \pi_{j,i}(m)$} \\
           0 & \text{otherwise}.
         \end{cases}
  \end{align*}
\end{remark}

%***************************************************************************

\begin{definition}
  \label{def:pseudo:codeword:1}
  
  \cite{Koetter:Vontobel:03:1} Let $\code{C}$ be a binary linear (base) code
  with parity-check matrix $\matr{H}$ and let $\graph{T} \defeq
  \graph{T}(\matr{H})$ be the corresponding Tanner graph. For any positive
  integer $M$, let $\graph{\widetilde T}$ be an $M$-fold cover of $\graph{T}$
  and let $\code{\widetilde C}$ be the binary code described by
  $\graph{\widetilde T}$. We will denote a codeword of $\code{\widetilde C}$
  by $\tvc$, where the $(i,m)$'s component of $\tvc$, i.e.~$\widetilde
  c_{i,m}$, denotes the value of the $m^{\text{th}}$ copy of the
  $i^{\text{th}}$ bit.
%%  By definition, $\widetilde c_{i,m} \in \{ 0, 1 \}$.
  
  The {\em pseudo-codeword} associated to $\tvc$ is the rational
  vector $\vomega(\tvc) \defeq \big( \omega_1(\tvc), \omega_2(\tvc), \ldots,
  \omega_n(\tvc) \big)$ with
  \begin{align*}
    \omega_i(\tvc)
      &\defeq
         \frac{1}{M}
           \sum_{m \in [M]}
             \widetilde c_{i,m},
  \end{align*}
  where the sum is taken in $\mathbb{R}$ (not in $\GF{2}$). We call the vector
  $M \cdot \vomega(\tvc)$ the \emph{unscaled} pseudo-codeword
  associated with $\tvc$. In fact, any multiple (by a positive scalar) of
  $\vomega(\tvc)$ will be called a pseudo-codeword associated with $\tvc$.
\end{definition}

Note that any codeword is also a pseudo-codeword.

%***************************************************************************

\begin{remark}
  Notice that a pseudo-codeword, as defined in
  Def.~\ref{def:pseudo:codeword:1}, has length $|\set{I}(\matr{H})|$, the same
  as the length of any codeword, whereas a codeword like $\tvc \in
  \code{\widetilde{C}}$ has length $M \cdot |\set{I}(\matr{H})|$, where $M$ is
  the degree of the corresponding cover Tanner graph.

%  We henceforth omit the
%  word ``normalized'' and simply use ``pseudo-codeword'' to mean both the
%  normalized and unnormalized notions, under the assumption that it should be
%  clear from context which notion is meant.
\end{remark}

%***************************************************************************

\begin{example}[Code A]
  \label{ex:simple:code:1:pseudo:codeword:1}

  We continue with Code A defined in Ex.~\ref{ex:simple:code:1}. We saw that
  $\tvc = (1,1,0, \ 0,1,1, \ 0,1,1, \ 0,0,0)$ was a codeword of the code
  $\code{\widetilde{C}}$. Applying Def.~\ref{def:pseudo:codeword:1} we see
  that the corresponding pseudo-codeword is $\vomega(\tvc) = (\frac{2}{3},
  \frac{2}{3}, \frac{2}{3}, 0)$ and that the corresponding unscaled
  pseudo-codeword is $3 \cdot \vomega(\tvc) = (2,2,2,0)$. Note that
  $\vomega(\tvc)$ cannot be written as a convex combination of the codewords
  in $\code{C}$.
\end{example}

%***************************************************************************

The influence of a pseudo-codeword on the decoding behavior under iterative
decoding can be measured by its pseudo-weight which is a function of the
pseudo-codeword and the channel used (see~\cite{Koetter:Vontobel:03:1} and
references therein). An important property of the pseudo-weight is its scaling
invariance, i.e.~scaling a pseudo-codeword by a positive scalar leaves
its pseudo-weight unchanged.

%***************************************************************************

%Here we only state the pseudo-weight in
%the case of the additive white Gaussian noise channel (AWGNC) case.

%\begin{definition}
%  \label{def:awgn:pseudo:weight:1}
%
%  \cite{Wiberg:96, Forney:Koetter:Kschischang:Reznik:01:1} Let $\vx \in
%  \Rp^n$. The AWGNC pseudoweight $\wpsAWGNC(\vx)$ of $\vx$ is defined to be
%  \begin{align*}
%    \wpsAWGNC(\vx)
%       &\defeq \frac{||\vx||_1^2}{||\vx||_2^2}.
%  \end{align*}
%  (In the case $\vx = \vect{0}$ the above fraction is understood to evaluate
%  to $\wps(\vx) = 0$.)
%\end{definition}

%***************************************************************************

%\begin{remark}
%  The pseudoweight as defined in Def.~\ref{def:awgn:pseudo:weight:1} is
%  invariant under scaling by a positive scalar, i.e., $\wpsAWGNC(\alpha \cdot
%  \vx) = \wpsAWGNC(\vx)$ for any $\alpha > 0$ and any $\vx \in
%  \Rp^n$. Moreover, if $\vx \in \{ 0, 1 \}^n$, then $||\vx||_1 = \wH(\vx)$ and
%  $||\vx||_2 = \sqrt{\wH(\vx)}$, where $\wH(\vx)$ is the Hamming weight of
%  $\vx$. It follows that $\wpsAWGNC(\vx) = ||\vx||_1^2/||\vx||_2^2 =
%  \wH(\vx)^2/\wH(\vx) = \wH(\vx)$.
%\end{remark}


%***************************************************************************

The fundamental cone that is given in the following definition will
be, along with the zeta functions of a graph, a main object of interest in
this paper.

%***************************************************************************

\begin{definition}
  \label{def:fundamental:cone:1}

  \cite{Koetter:Vontobel:03:1, Feldman:Karger:Wainwright:03:2} Let
  $\code{C}$ be an arbitrary binary linear code and let $\matr{H}$ be
  its parity-check matrix. We define the {\em fundamental cone}
  $\fch{K}{H}$ of $\matr{H}$ to be the set of vectors $\vomega \in
  \R^n$ that satisfy
  \begin{alignat*}{2}
    \forall i \in \set{I}:&&
        \quad
    \omega_i
      &\geq 0, \\
    \forall j \in \set{J}, \
      \forall i \in \set{I}_j:&&
        \quad
    \sum_{i' \in \set{I}_j \setminus \{ i \}}
      \omega_{i'}
      &\geq
        \omega_{i},
  \end{alignat*}
  where $\set{J} \defeq \set{J}(\matr{H})$, $\set{I} \defeq
  \set{I}(\matr{H})$, $\set{I}_j \defeq \set{I}_j(\matr{H})$.
\end{definition}

%***************************************************************************

\begin{example}[Code A]
  \label{ex:simple:code:1:fundamental:cone:1}

  We continue with Code A defined in Ex.~\ref{ex:simple:code:1}. The
  fundamental cone $\fch{K}{H}$ is the set
  \begin{align*}
    \fch{K}{H}
      = \{
           (\omega_1,\omega_2,&\omega_3,\omega_4) \in \R^4
           \big|\,
                 \omega_1 \geq 0,
                 \omega_2 \geq 0,
                 \omega_3 \geq 0,
                 \omega_4 \geq 0, \\
                 &- \omega_1 + \omega_2 + \omega_3 \geq 0, \ \ \
                 - \omega_2 + \omega_3 + \omega_4 \geq 0, \\
                 &+ \omega_1 - \omega_2 + \omega_3 \geq 0, \ \ \
                 + \omega_2 - \omega_3 + \omega_4 \geq 0, \\
                 &+ \omega_1 + \omega_2 - \omega_3 \geq 0, \ \ \
                 + \omega_2 + \omega_3 - \omega_4 \geq 0
         \}.  
  \end{align*}
\end{example}

%***************************************************************************

%\begin{example}
%%% [Cycle Code]
%  A cycle code $\code{C}$ is special in the sense that it can be described by
%  a parity-check matrix $\matr{H}$ having exactly two ones per column.
%\end{example}

%***************************************************************************

The next two lemmas
%Lemma~\ref{lemma:from:cover:codeword:to:pseudo:codeword:1} and
%Lemma~\ref{lemma:from:pseudo:codeword:to:cover:codeword:1}, 
establish that there is
a very tight connection between the fundamental cone of a code and codewords
that live in finite covers. More specifically, in one direction we prove that
the pseudo-codeword associated to any codeword in a cover of a Tanner graph
must lie within the fundamental polytope. In the other direction we prove that
to a given vector in the fundamental polytope we can find a cover with a
codeword in it whose (suitably scaled) pseudo-codeword is arbitrarily close to
the given vector.  

%% Although the proof of
%% Lemma~\ref{lemma:from:pseudo:codeword:to:cover:codeword:1} is rather
%% technical, the idea behind it is quite simple.

%***************************************************************************

\begin{lemma}
  \label{lemma:from:cover:codeword:to:pseudo:codeword:1}

  \cite{Koetter:Vontobel:03:1} Let $\code{C}$ be a binary linear code with
  parity-check matrix $\matr{H}$ and Tanner graph $\graph{T} =
  \graph{T}(\matr{H})$. For a positive integer $M$, let $\graph{\widetilde T}$
  be an arbitrary $M$-fold cover of $\graph{T}$ and let $\code{\widetilde C}$
  be the binary code described by $\graph{\widetilde T}$. If $\tvc \in
  \code{\widetilde C}$ then $\vomega(\tvc) \in \fch{K}{H}$.
\end{lemma}

%***************************************************************************

\begin{lemma}
  \label{lemma:from:pseudo:codeword:to:cover:codeword:1}

  \cite{Koetter:Vontobel:03:1} Let $\code{C}$ be a binary linear code with
  parity-check matrix $\matr{H}$ and Tanner graph $\graph{T} =
  \graph{T}(\matr{H})$. Let the vector $\vomega' \in \R^n$ satisfy $\vomega'
  \in \fch{K}{H}$. Then for any $\varepsilon > 0$, there is a positive integer
  $M$ such that there is a codeword $\tvc$ in a code $\code{\widetilde{C}}$
  defined by an $M$-fold cover $\graph{\widetilde T}$ of $\graph{T}$ such that
  $||\alpha \vomega(\tvc) - \vomega'||_2 < \varepsilon$ for some $\alpha >
  0$. 
%%(What norm is taken here is not really important.)
\end{lemma}

%***************************************************************************

Putting Lemmas~\ref{lemma:from:cover:codeword:to:pseudo:codeword:1}
and \ref{lemma:from:pseudo:codeword:to:cover:codeword:1} together, we
have: 

%***************************************************************************

\begin{theorem} Let $C$ be a binary linear code with parity-check matrix $H$
  and fundamental cone $\fch{K}{H}$.  Then the lines through the
  pseudo-codewords for $C$ are dense in $\fch{K}{H}$. \qed
\end{theorem}

%***************************************************************************

Moreover, we have
%% (proof omitted):

%***************************************************************************

\begin{theorem} 
  The point $\vomega = (\omega_1, \dots, \omega_{|\set{I}|}) \in K(H) \cap
  \Z^n$ is an unscaled pseudo-codeword if and only if $\sum_{i \in \set{I}}
  h_{ji} \omega_i = 0 \text{ (in $\GF{2}$)}$ for each $j \in \set{J}$.
\end{theorem}

%***************************************************************************

\begin{proof}This follows from 
  Lemma~\ref{lemma:from:pseudo:codeword:to:cover:codeword:1} and
  Corollary~\ref{cor:to:pseudos:in:cycle}.
\end{proof}





























%***************************************************************************
%***************************************************************************

\itwsection{Zeta Functions of Graphs}

\label{sec:zeta:functions:1}

%***************************************************************************

Before we can talk about zeta functions of graphs we need to say exactly what
we mean by a cycle in a graph.

\begin{definition}
  Let $X$ be an undirected graph as in Def.~\ref{def:undirected:graph:1}. A
  sequence $(e_{i_1}, \dots, e_{i_k})$ of edges of $X$ is a {\em cycle} on $X$
  if the edges $e_{i_j}$ can be directed so that $e_{i_s}$ terminates where
  $e_{i_{s+1}}$ begins for $1 \leq s \leq k-1$ and $e_{i_k}$ terminates where
  $e_{i_1}$ begins. The {\em characteristic vector} of the cycle $(e_{i_1},
  \dots, e_{i_k})$ on $X$ is the binary vector of length $n$ whose
  $t^\text{th}$ coordinate is 1 if and only if $e_t$ appears as some
  $e_{i_j}$. If 
%% each edge of the graph appears at most once in $(e_{i_1},
%%  \dots, e_{i_k})$ then we call it a \emph{simple cycle}.
  the cycle does not cross itself, i.e., if each vertex of $X$ is
  involved in at most two of the edges $e_{i_1}$, \dots, $e_{i_k}$,
  then we say the cycle is {\em simple}.
\end{definition}

%***************************************************************************

This definition relates as follows to the cycle codes introduced in
Sec.~\ref{sec:binary:linear:codes:1}:

%***************************************************************************

\begin{lemma}
  \label{lemma:cycle:code:1}

  Let $N \defeq N(\matr{H})$ be the normal graph of a binary cycle
  code $\code{C}$ with parity-check matrix $\matr{H}$. The
  characteristic vector of any simple cycle in $N$ is a valid
  configuration of $N$, i.e.~it is a codeword of $\code{C}$. Moreover,
  the symmetric difference of the characteristic vector of simple
  cycles in $N$ is also a valid configuration of $N$, i.e.~it is a
  codeword of $\code{C}$. On the other hand, to any codeword in
  $\code{C}$ corresponds the symmetric difference of simple cycles in
  $N$.
\end{lemma}

%***************************************************************************

\begin{proof}
  This follows from Euler's Theorem~\cite[Th.~1.2.26]{West:96:1}.
\end{proof}

%***************************************************************************

The code $\code{C}$ in Lemma~\ref{lemma:cycle:code:1} can also be seen
as spanned by the characteristic vectors of the simple cycles of $N$.
The length of $\code{C}$ equals $n(N)$, the number of edges in
$N$. Further, the minimum Hamming distance $\dmin$ of $\code{C}$ is
the length of the shortest cycle in $N$, i.e., the girth of $N$.
Also, the dimension of $\code{C}$ is the number of independent cycles
in $N$, i.e., the rank of the fundamental group of the underlying
topological space of $N$, i.e., $|E(N)| - |V(N)| + 1 = 1-\chi(N)$,
where $\chi(N)$ is the Euler characteristic of $N$.

%***************************************************************************

Let us turn back to graph-theoretic notions: the next important step
is to introduce a special class of cycles called ``primitive,
backtrackless and tailless cycles''.

%***************************************************************************

\begin{definition}\label{primitive:backtrackless:tailless:equivalence}
%%  Let $\Gamma = (e_{i_1}, \dots, e_{i_k})$ be a cycle in a graph $X$, so that
%%  $\Gamma$ is a closed path beginning with the edge $e_{i_1}$ and ending with
%%  the edge $e_{i_k}$. 
  Let $\Gamma = (e_{i_1}, \dots, e_{i_k})$ be a cycle in a graph
  $X$. We say $\Gamma$ is {\em backtrackless} if for no $s$ do we have
  $e_{i_s} = e_{i_{s+1}}$.  We say $\Gamma$ is {\em tailless} if
  $e_{i_1} \neq e_{i_k}$.  We say $\Gamma$ is {\em primitive} if there
  is no cycle $\Theta$ on $X$ such that $\Gamma = \Theta^r$ with $r
  \geq 2$, i.e., such that $\Gamma$ is obtained by following $\Theta$
  a total of $r$ times.  We say that the cycle $\Psi = (e_{j_1},
  \dots, e_{j_k})$ is {\em equivalent} to $\Gamma$ if there is some
  integer $t$ such that $e_{j_s} = e_{j_{(s+t)\ \operatorname{mod}\
  k}}$ for all $s$.
\end{definition}

%***************************************************************************

It is easy to check that any simple cycle is a primitive,
backtrackless and tailless cycle and that the notion of equivalence
given in Def.~\ref{primitive:backtrackless:tailless:equivalence}
defines an equivalence relation on primitive, backtrackless, tailless
cycles.

%***************************************************************************

\begin{example}[Code B]
  \label{ex:simple:code:2:cycles:1}

  Let us return to Code B defined in Ex.~\ref{ex:simple:code:2} and its
  normal graph shown in Fig.~\ref{fig:simple:code:2} (right); the edge with
  variable label $X_i$ will be called $e_i$. We see that the edge-sequences
  $(e_1,e_2,e_3)$ and $(e_5,e_6,e_7)$ are simple cycles: they correspond to
  the codewords $(1,1,1,0,0,0,0)$ and $(0,0,0,0,1,1,1)$, respectively, in
  $\code{C}$.

  In contrast to these two cycles, the cycles
  \begin{align*}
    \Gamma_1
      &= (e_1, e_2, e_4, e_5, e_6, e_7, e_4, e_3) \\
    \Gamma_2
      &= (e_3, e_4, e_7, e_6, e_5, e_4, e_2, e_1) \\
    \Gamma_3
      &= (e_1, e_2, e_4, e_5, e_6, e_7, e_5, e_6, e_7, e_4, e_3)
  \end{align*}
  are \emph{not} simple cycles; but they are inequivalent, backtrackless,
  tailless, primitive cycles. Indeed, we can obtain infinitely many
  inequivalent, backtrackless, tailless, primitive cycles on $N(\matr{H})$ by,
  for example, following the path $(e_1,e_2,e_4)$, then arbitrarily many
  copies of the loop $(e_5,e_6,e_7)$, and then $(e_4,e_3)$.
\end{example}

%***************************************************************************

The \emph{edge zeta function} of a graph is a way to enumerate all
inequivalent, primitive, backtrackless cycles and combinations thereof.

%***************************************************************************

\begin{definition}
  \label{def:edge:zeta:function:1}

  \cite{Hashimoto:89:1, Stark:Terras:96:1} Let $\Gamma$ be a path in a graph
  $X$ with edge-set $E$; write $\Gamma = (e_{i_1}, \dots, e_{i_k})$ to
  indicate that $\Gamma$ begins with the edge $e_{i_1}$ and ends with the edge
  $e_{i_k}$. The {\em monomial of $\Gamma$} is given by $g(\Gamma)
  \defeq u_{i_1}\cdots u_{i_k}$,
%\vspace{-6mm}
%  \begin{align*}
%    g(\Gamma)
%      &= u_{i_1} \cdots u_{i_k},
%  \end{align*}
  where the $u_i$'s are indeterminates. The {\em edge zeta function} of
  $X$ is defined to be the power series $\zeta_X(u_1, \dots, u_n) \in \Z[[u_1,
  \dots, u_n]]$ given by
\vspace{-1mm}
  \begin{align*}
    \zeta_X(u_1, \dots, u_n)
      &= \prod_{[\Gamma] \in A(X)}
           \big(
             1 - g(\Gamma)
           \big)^{-1},
  \end{align*}
  where $A(X)$ is the collection of equivalence classes of backtrackless,
  tailless, primitive cycles in $X$.
\end{definition}

%***************************************************************************

As Ex.~\ref{ex:simple:code:2:cycles:1} shows, the product in the definition of
the edge zeta function is, in general, infinite. However, it is true that the
edge zeta function is a rational function.  To see this, we first need a few
more definitions.

%***************************************************************************

\begin{definition}
  \label{def:directed:graph:1}

  \cite{Stark:Terras:96:1} Let $X = (V(X),E(X))$ be an undirected graph with
  edge set $E(X) = \{ e_1, \ldots, e_n \}$. A {\em directed graph} $\dirX =
  (\dirV(\dirX),\dirE(\dirX))$ derived from $X$ is a graph with vertex set
  $\dirV(\dirX) \defeq V(X)$ and edge set $\dirE(\dirX) \defeq \{f_1, \dots,
  f_{2n}\}$, where the (directed) edges $f_i$ and $f_{n+i}$ both correspond to
  the same edge $e_i \in E(X)$ but have opposite directions.
\end{definition}

%***************************************************************************

\begin{definition} \cite{Stark:Terras:96:1} Let $\dirX =
  (\dirV(\dirX),\dirE(\dirX))$ be a directed graph as defined in
  Def.~\ref{def:directed:graph:1}. The {\em directed edge matrix} of $\dirX$
  is the matrix $M(\dirX) = (m_{ij})$ where
  \begin{align*} 
    m_{ij}
      &= \begin{cases}
           1, & \text{if $f_i$ feeds into $f_j$ 
                      to form a backtrackless path} \\
           0, &\text{otherwise.}
         \end{cases}
  \end{align*}
\end{definition}

%***************************************************************************

%% \begin{definition} \cite{Stark:Terras:96:1} The {\em variable matrix} of
%%   an undirected graph $X$ with $n$ edges is the diagonal $2n\times 2n$ matrix
%% \vspace{-1mm}
%%   \begin{align*}
%%     U(X)
%%       &= \mathop{\text{diag}}(u_1, \dots, u_n, u_1, \dots, u_n).
%%   \end{align*}
%% \vspace{-1mm}
%% \end{definition}
%***************************************************************************
%% \vspace{-7mm}
\begin{example}[Code B]
  \label{ex:simple:code:2:directed:graph:1}

  Let us continue with Code B defined in Ex.~\ref{ex:simple:code:2}. The
  normal graph $N = N(\matr{H})$ of the code is shown in
  Fig.~\ref{fig:simple:code:2} (right); the edge with variable label $X_i$
  will be called $e_i$. The directed edges $f_1$ to $f_{14}$ of a directed
  version $\dirN$ of $N$ are chosen such that the edges $f_1$ to $f_7$ are as
  shown in Fig.~\ref{fig:simple:code:2:directed:1}.  Implicitly this figure
  also defines the edges $f_8$ to $f_{14}$; e.g., $f_{11}$ is the same as
  $f_4$ but directed from right to left. The directed edge matrix $M \defeq
  M(\dirN)$ of $\dirN$ is then the matrix { \small
  \begin{align*}
    M
      &= \left[
           \begin{array}{ccccccc|ccccccc}
             0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
             0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
             1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
             0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
             0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 
             0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
             0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 
             \hline
             0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 
             0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
             0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 
             0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 
             0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 
             0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 
             0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
           \end{array}
         \right].
  \end{align*}
  }%
%%   and the variable matrix of $N$ is simply
%%   \begin{align*}
%%     U
%%       &= \mathop{\text{diag}}(u_1, \dots, u_7, u_1, \dots, u_7).
%%   \end{align*}
\end{example}

%***************************************************************************

With these definitions, Stark and Terras \cite{Stark:Terras:96:1} prove:

%***************************************************************************

\begin{theorem}
  \cite{Stark:Terras:96:1} The edge zeta function $\zeta_X(u_1, \dots, u_n)$
  is a rational function. More precisely, for any directed graph $\dirX$ of
  $X$, we have
  \begin{align*}
    \zeta_X(u_1, \dots, u_n)^{-1}
      &= \det(I-UM(\dirX)) = \det(I-M(\dirX)U)
  \end{align*}
  where $I$ is the identity matrix of size $2n$ and $U =
  \mathop{\text{diag}}(u_1, \dots, u_n, u_1, \dots, u_n)$ is a
  diagonal matrix of indeterminants.
\end{theorem}

%***************************************************************************

\begin{example}[Code B]
  \label{ex:simple:code:2:edge:zeta:1}

  Let us continue with Code B defined in Ex.~\ref{ex:simple:code:2} and its
  normal graph $N \defeq N(\matr{H})$. By the above theorem and using $\dirN$
  from Ex.~\ref{ex:simple:code:2:directed:graph:1}, the edge zeta function
  $\zeta_N$ of our graph $N$ satisfies
  \begin{align*}
  \zeta_N&(u_1, \dots, u_7)^{-1}
     = \det(I_{14}-U M)
     = \det(I_{14}-M U)\\
    &= 1 - 2 u_1 u_2 u_3 + u_1^2 u_2^2 u_3^2 - 2 u_5 u_6 u_7
         + 4 u_1 u_2 u_3 u_5 u_6 u_7 \\
    & \phantom{spa} - 2 u_1^2 u_2^2 u_3^2 u_5 u_6 u_7
                    - 4 u_1 u_2 u_3 u_4^2 u_5 u_6 u_7 \\
    & \phantom{spa} + 4 u_1^2 u_2^2 u_3^2 u_4^2 u_5 u_6 u_7
                    + u_5^2 u_6^2 u_7^2
                    - 2 u_1 u_2 u_3 u_5^2 u_6^2 u_7^2 \\
    & \phantom{spa} + u_1^2 u_2^2 u_3^2 u_5^2 u_6^2 u_7^2
                    + 4 u_1 u_2 u_3 u_4^2 u_5^2 u_6^2 u_7^2 \\
    & \phantom{spa} - 4 u_1^2 u_2^2 u_3^2 u_4^2 u_5^2 u_6^2 u_7^2.
  \end{align*}
  Expanding out the Taylor series, we get the first several terms of
  $\zeta_N$:
  \begin{align*}
    \zeta_N&(u_1, \dots, u_7)
       = 1 + 2 u_1 u_2 u_3 + 3 u_1^2 u_2^2 u_3^2
           + 2 u_5 u_6 u_7 \\ 
      &\phantom{spa} + 4 u_1 u_2 u_3 u_5 u_6 u_7
                     + 6 u_1^2 u_2^2 u_3^2 u_5 u_6 u_7 \\ 
      &\phantom{spa} + 4 u_1 u_2 u_3 u_4^2 u_5 u_6 u_7
                     + 12 u_1^2 u_2^2 u_3^2 u_4^2 u_5 u_6 u_7 \\ 
      &\phantom{spa} + 3 u_5^2 u_6^2 u_7^2
                     + 6 u_1 u_2 u_3 u_5^2 u_6^2 u_7^2
                     + 9 u_1^2 u_2^2 u_3^2 u_5^2 u_6^2 u_7^2 \\ 
      &\phantom{spa} + 12 u_1 u_2 u_3 u_4^2 u_5^2 u_6^2 u_7^2
                     + 36 u_1^2 u_2^2 u_3^2 u_4^2 u_5^2 u_6^2 u_7^2
                     + \cdots.
  \end{align*}
\end{example}

%***************************************************************************
%***************************************************************************

\itwsection{Relating the Fundamental Cone 
            and the Zeta Function of a Cycle Code}

\label{sec:connection:fundamental:cone:zeta:function:1}

%***************************************************************************

The results of this chapter are based on the simple observations made in the
following example.

%***************************************************************************

\begin{example}[Code B]
  \label{ex:simple:code:2:connection:fundamental:cone:zeta:function:1}

  Let us continue with Code B defined in Ex.~\ref{ex:simple:code:2} and its
  Tanner graph $T \defeq T(\matr{H})$ as shown in Fig.~\ref{fig:simple:code:2}
  (left). We saw that any codeword corresponds one-to-one to a valid
  configuration in $T$.

  Consider now a double cover $\widetilde{T}$ of $T$ as shown in
  Fig.~\ref{fig:simple:code:2:cover:1} (left): the set of all valid
  configurations of $\widetilde{T}$ defines a code
  $\code{\widetilde{C}}$. Because of the properties of graph covers,
  the code $\code{\widetilde{C}}$ is again a cycle code and in the
  same manner as in Ex.~\ref{ex:simple:code:2} we deduce its normal
  graph $\widetilde{N}$. It is not hard to see that $\widetilde{N}$
  shown in Fig.~\ref{fig:simple:code:2:cover:1} (right) is a double
  cover of the normal graph $N \defeq N(\matr{H})$ shown in
  Fig.~\ref{fig:simple:code:2} (right).

%%   In the same way as codewords of $\code{C}$ correspond one-to-one to
%%   the symmetric difference set of simple cycles in $N$ (or one-to-one
%%   to a union of disjoint simple cycles in $N$), the codewords of
%%   $\code{\widetilde{C}}$ correspond one-to-one to the symmetric
%%   difference of simple cycles in $\widetilde{N}$ (or one-to-one to a
%%   union of disjoint simple cycles in $\widetilde{N}$).


  Just as the codewords of $\code{C}$ correspond bijectively to the
  vectors in the span of the characteristic vectors of the simple
  cycles in $N$, the codewords of $\code{\widetilde{C}}$ correspond
  bijectively to the vectors in the span of the characteristic vectors
  of the simple cycles in $\widetilde{N}$.

  An example of simple cycle in $\widetilde{N}$ is the
  edge-sequence\footnote{The edge with variable label $X'_i$ ($X''_i$)
  will be called $e'_i$ ($e''_i$).}
  \begin{align*}
    \widetilde{\Gamma}
      &= (e'_1, e'_2, e''_4, e''_5, e''_6, e'_7, e'_4, e'_3).
  \end{align*}
  After mapping it down to $N$ it reads
  \begin{align*}
    \pi(\widetilde{\Gamma})
      &= (e_1, e_2, e_4, e_5, e_6, e_7, e_4, e_3),
  \end{align*}
  which is a backtrackless and tailless cycle in $N$ which is not simple. Note
  that in general the image of a simple cycle is always backtrackless and
  tailless, but not necessarily simple or primitive. The cycle
  $\widetilde{\Gamma}$ corresponds to a codeword $\tvc$ and the mapped cycle
  $\pi(\widetilde{\Gamma})$ corresponds to the pseudo-codeword
  \begin{align*}
    \vomega(\tvc)
      &= \frac{1}{2}
           \cdot
           (1, 1, 1, 2, 1, 1, 1)
       = \left(
           \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, 1, 
           \frac{1}{2}, \frac{1}{2}, \frac{1}{2}
         \right).
  \end{align*}
\end{example}

With this example we can draw the following important conclusion about cycle
codes (which will be formalized in Th.~\ref{theorem:pseudos:in:cycle:1}):
listing the pseudo-codewords stemming from all the possible finite covers is
equivalent to listing all backtrackless and tailless cycles of the normal
graph and combinations thereof. But listing these cycles (in a certain way) is
exactly what the zeta function of the normal graph essentially does!

%\footnote{That the product in the zeta
%function definition goes only over the backtrackless and tailless cycles that
%are \emph{primitive} is no worry to us: we are anyway only interested in the
%pseudo-codeword up to a scale factor.}

%***************************************************************************

\begin{definition}
  The {\em exponent vector} of the monomial $u_1^{p_1}\dots u_n^{p_n}$ is the
  vector $(p_1, \dots, p_n) \in \N_0^n$ of the exponents of the monomial.
\end{definition}

%***************************************************************************

%\begin{definition}
%  \cite{Koetter:Vontobel:03:1} A vector $\vp = (p_1, \dots, p_n) \in \N^n$ is
%  called a {\em pseudo-codeword} for $C_X$ if the path on $X$ which uses the
%  edge $e_i$ a total of $p_i$ times becomes a codeword in the cycle code $C_Y$
%  of some cover $Y$ of $X$.
%\end{definition}

%***************************************************************************

\begin{example}[Code B]
  Continuing with Code B that was defined in Ex.~\ref{ex:simple:code:2} and
  the zeta function $\zeta_N$ of its normal graph $N \defeq N(\matr{H})$
  (cf.~Ex.~\ref{ex:simple:code:2:edge:zeta:1}), we see that the exponent
  vectors of the first several monomials appearing in $\zeta_N$ are
  (0,0,0,0,0,0,0), (1,1,1,0,0,0,0), (2,2,2,0,0,0,0), (0,0,0,0,1,1,1),
  (1,1,1,0,1,1,1), (2,2,2,0,1,1,1), (1,1,1,2,1,1,1), (2,2,2,2,1,1,1),
  (0,0,0,0,2,2,2), (1,1,1,0,2,2,2), (2,2,2,0,2,2,2), (1,1,1,2,2,2,2),
  (2,2,2,2,2,2,2), \dots. Note that most of these lie within the span of
  multiples of codewords in $\code{C}$; for example,
  \begin{align*}
    (1,1,1,0,2,2,2)
      &= (1,1,1,0,0,0,0) + 2(0,0,0,0,1,1,1).
  \end{align*} 
  The exceptions thus far are (1,1,1,2,1,1,1), (2,2,2,2,1,1,1),
  (1,1,1,2,2,2,2) and (2,2,2,2,2,2,2). The first of these exceptions is
  exactly the pseudo-codeword for $C$ given in
  Ex.~\ref{ex:simple:code:2:connection:fundamental:cone:zeta:function:1}, and
  the rest lie within the span of this pseudo-codeword along with multiples of
  codewords.
\end{example}

%***************************************************************************

These observations are made precise in the next theorem.

%***************************************************************************

\begin{theorem}
  \label{theorem:pseudos:in:cycle:1}

  Let $C$ be a cycle code defined by a parity-check matrix $\matr{H}$
  having normal graph $N \defeq N(\matr{H})$, let $n = n(N)$ be the
  number of edges of $N$, and let $\zeta_N(u_1, \dots, u_n)$ be the
  edge zeta function of $N$. Then the monomial $u_1^{p_1} \dots
  u_n^{p_n}$ has nonzero coefficient in $\zeta_N$ if and only if the
  corresponding exponent vector $(p_1, \dots, p_n)$ is an unscaled
  pseudo-codeword for $C$.
\end{theorem}

%***************************************************************************

\begin{proof}[Sketch of proof.]
  By Def.~\ref{def:edge:zeta:function:1}, the monomial $u_1^{p_1}\dots
  u_n^{p_n}$ appears with nonzero coefficient in $\zeta_N$ if and only if
  there are backtrackless, tailless, primitive cycles $\Gamma_1, \dots,
  \Gamma_m$ on $X$ such that
  \begin{align*}
    u_1^{p_1}\dots u_n^{p_n}
      &= g(\Gamma_1)^{q_1} \cdots g(\Gamma_m)^{q_m}
  \end{align*} 
  for some nonnegative integers $q_1, \dots, q_m$.  It is thus enough to prove
  that $\Gamma$ is a backtrackless, tailless cycle on $N$ if and only if
  $\Gamma = \pi(\widetilde \Gamma)$ for some simple cycle $\widetilde \Gamma$
  on some (finite, unramified) cover $\widetilde N$ of $N$, where $\pi:\
  \widetilde N \to N$ is the canonical surjection.

%  Here a cycle is called {\em simple} if in its expression as a sequence of
%  adjacent vertices, no vertices are repeated (except that the first and last
%  are necessarily the same).

  So, first suppose that $\pi:\ \widetilde N \to N$ is a cover of $N$
  and that $\widetilde \Gamma$ is a simple cycle on $\widetilde N$. We
  must show that $\pi(\widetilde \Gamma)$ is a backtrackless, tailless
  cycle on $N$. Suppose otherwise, namely, that $(x, y, x)$ is part of
  the vertex sequence of $\pi(\widetilde \Gamma')$ for some
  $\widetilde \Gamma'$ equivalent to $\widetilde \Gamma$. Then it
  comes from $(\widetilde u, \widetilde v, \widetilde w)$ in
  $\widetilde \Gamma'$. In particular, this means that $v$ is adjacent
  to two distinct vertices $\widetilde u$ and $\widetilde w$ in
  $\widetilde N$, both of which project to $x$. This cannot happen in
  a finite unramified cover. Thus $\pi(\widetilde \Gamma)$ is
  backtrackless and tailless.

  For the converse, we must show that given a backtrackless, tailless
  cycle $\Gamma$ on $N$, there is a cover $\pi:\ \widetilde N \to N$
  and a simple cycle $\widetilde \Gamma$ on $\widetilde N$ lifting
  $\Gamma$. This is done by induction on the length of $\Gamma$, with
  cycles of length $3$, which are necessarily simple, providing the
  base case. For a nonsimple cycle $\Gamma$ of length greater than
  $3$, the idea is to break off the first simple cycle $\Gamma_1$
  appearing within $\Gamma$. Then $\Gamma$ is equivalent to a
  composition of $\Gamma_1$ with some other cycle $\Gamma_2$ which has
  length less than that of $\Gamma$. If $\Gamma_2$ is backtrackless,
  then it has a lift to a simple cycle by induction hypothesis and one
  must explicitly show how to ``glue together'' this lift with the
  cycle $\Gamma_1$ to form a simple lifting of $\Gamma$. The case
  where $\Gamma_2$ has backtracking presents a bit more difficulty,
  but is handled similarly.
\end{proof}


%***************************************************************************

The following corollary is contained in the proof of
Th.~\ref{theorem:pseudos:in:cycle:1}.

%***************************************************************************

\begin{corollary}\label{cor:to:pseudos:in:cycle}

  Consider the same setup as in Th.~\ref{theorem:pseudos:in:cycle:1}. The
  vector $p = (p_1,...,p_n) \in \N^n$ is an unscaled pseudo-codeword for $C$
  if and only if there is a backtrackless tailless cycle in $X$ which uses the
  $i^{\text th}$ edge exactly $p_i$ times for $1 \le i \le n$. Moreover, the
  unscaled pseudo-codewords of $C$ are in one-to-one correspondence with the
  monomials appearing with nonzero coefficient in the edge zeta function
  $\zeta_N$ of $N$. Finally, the Newton polyhedron of $\zeta_N$ (i.e.~the
  polyhedron spanned by the exponents of the terms in the Taylor series of
  $\zeta_N$) equals the fundamental cone $\fch{K}{H}$ of the code $C$.
\end{corollary}

%***************************************************************************

%XXXXX Because the decoding algorithm acts locally on $G$, it does not
%``know'' whether it is acting on $G$ or on $\widetilde G$, and hence cannot
%distinguish between codewords and pseudo-codewords.  In other words, it
%is just as likely to get caught in a loop because it ``thinks'' it is
%converging to a pseudo-codeword as it is to converge to an actual
%codeword.

%XXXXX Our next goal is to interpret cycle codes as a special class of low
%density parity-check codes.  Towards that end, we need the following
%definition:

%***************************************************************************
%***************************************************************************

%\itwsection{Conclusions and Open Problems}

%\label{sec:conclusions:and:open:problems:1}

%***************************************************************************

%In this paper we have shown that in the case of cycle codes there is a tight
%connection between the fundamental cone and the zeta function associated to
%the normal graph representing the code. For general code we know the
%definition of the fundamental cone (see Def.~\ref{def:fundamental:cone:1}): is
%there a zeta function or a ``modified zeta function'' of some graph that is
%connected to this fundamental cone.





%***************************************************************************
% Bibliography
%***************************************************************************

%{\tiny
%  \bibliographystyle{ieeetr}
%  \bibliography{/home/vontobel/references/references}
%}

%***************************************************************************


\begin{itwreferences}

{\footnotesize

%\begin{thebibliography}{1}

\bibitem{Tanner:81}
R.~M. Tanner, ``A recursive approach to low-complexity codes,'' {\em IEEE
  Trans.\ on Inform.\ Theory}, vol.~IT--27, pp.~533--547, Sept. 1981.

\bibitem{Koetter:Vontobel:03:1}
R.~Koetter and P.~O. Vontobel, ``Graph covers and iterative decoding of
  finite-length codes,'' in {\em Proc.\ 3rd Intern.~Conf.~on Turbo Codes and
  Related Topics}, (Brest, France), pp.~75--82, Sept.~1--5 2003.
\newblock Available online under \verb+http://www.ifp.uiuc.edu/~vontobel+.

\bibitem{Feldman:Karger:Wainwright:03:2}
J.~Feldman, D.~R. Karger, and M.~J. Wainwright, ``{LP} decoding,'' in {\em
  Proc.\ 41st Allerton Conf.~on Communications, Control, and Computing},
  (Allerton House, Monticello, Illinois, USA), October 1--3 2003.
\newblock Available online under
  \verb+http://www.columbia.edu/~jf2189/pubs.html+.

\bibitem{nicwi} N. Wiberg, ``Codes and Decoding on General Graphs'', Link\"oping Studies in Science and Technology, 
Ph.D thesis No. 440, Link\"oping, Sweden.
\verb+http://www.it.isy.liu.se/+ \verb+publikationer/LIU-TEK-THESIS-440.pdf+.


\bibitem{Kschischang:Frey:Loeliger:01}
F.~R. Kschischang, B.~J. Frey, and H.-A. Loeliger, ``Factor graphs and the
  sum-product algorithm,'' {\em IEEE Trans.\ on Inform.\ Theory}, vol.~IT--47,
  no.~2, pp.~498--519, 2001.

\bibitem{Hakimi:Bredeson:68:1}
S.~L. Hakimi and J.~Bredeson, ``Graph-theoretic error correcting codes,'' {\em
  IEEE Trans.\ on Inform.\ Theory}, vol.~IT--14, no.~4, pp.~584--591, 1968.

\bibitem{Forney:01:1}
G.~D. {Forney, Jr.}, ``Codes on graphs: normal realizations,'' {\em IEEE
  Trans.\ on Inform.\ Theory}, vol.~47, no.~2, pp.~520--548, 2001.

\bibitem{Massey:77:1}
W.~S. Massey, {\em Algebraic Topology: an Introduction}.
\newblock New York: Springer-Verlag, 1977.
\newblock Reprint of the 1967 edition, Graduate Texts in Mathematics, Vol. 56.

\bibitem{Stark:Terras:96:1}
H.~M. Stark and A.~A. Terras, ``Zeta functions of finite graphs and
  coverings,'' {\em Adv. Math.}, vol.~121, no.~1, pp.~124--165, 1996.

\bibitem{West:96:1}
D.~B. West, {\em Introduction to graph theory}.
\newblock Upper Saddle River, NJ: Prentice Hall Inc., 1996.

\bibitem{Hashimoto:89:1}
K.~Hashimoto, ``Zeta functions of finite graphs and representations of
  {$p$}-adic groups,'' in {\em Automorphic forms and geometry of arithmetic
  varieties}, vol.~15 of {\em Adv. Stud. Pure Math.}, pp.~211--280, Boston, MA:
  Academic Press, 1989.

%\end{thebibliography}

}

\end{itwreferences}

%***************************************************************************

\end{itwpaper}

%***************************************************************************
% End of Document
%***************************************************************************


\end{document}
 




%***************************************************************************
% Old Stuff
%***************************************************************************


% For a graph $X$, the cycle code $C_X$ on $X$ is the code spanned by
% the characteristic vectors of the cycles in $X$.  As with most (all?)
% codes on graphs, one successful decoding algorithm for cycle codes is
% a so-called message-passing algorithm.  Recall that the decoding
% problem is described as follows: given any sequence of bits $\vy\in
% \F_2^n$ we must find the codeword that is closest to the sequence
% $\vy$, with respect to some given metric. (In practice, the distance
% between $\vy$ and $\vc$ is often measured as $\log P(\vy|\vc)$, but it
% is not a problem to think in terms of Hamming distance.)  Decoding is,
% in general, a very hard problem since, for practical reasons, a
% complexity is required that is polynomial in the length of the code.
% Message-passing algorithms operate by sending messages along the edges
% of the graph concerning the reliability of the bit on the
% corresponding edge.
% 
% More precisely, consider a vertex $v$ with incident edges $e_1$,
% $e_2$, \dots, $e_t$.  From the parity-check relation that has to be
% satisfied at $v$ we can compute an outgoing message along each edge by
% letting the outgoing message record what all the ``other'' bits incident
% to $v$ believe the bit in question should be. Messages are exchanged in
% the graph until global agreement is reached among the messages (or a
% timer exceeds a preset limit). 
% 
% The point here is that the algorithm combines {\em local} decisions in
% the graph into a {\em global} decision. A side-effect of the fact that
% we combine local operations is that the message-passing algorithm is
% not aware of the global structure of the graph. In other words, the
% algorithm does not know if the decoding happens in the original graph
% or in any cover of the graph. Moreover, it can be proved that these
% message-passing algorithms perform optimal decoding in the universal
% cover of the graph.  The received word $\vy$ is lifted to a received
% word in the universal cover by replicating received values every time
% we replicate an edge in the universal cover.  Since we know what the
% algorithm does in the universal cover, in principle, all we need to
% get a handle on are the codewords in the universal cover.
% 
% However, studying codewords in the universal cover of a graph is not
% feasible.  Instead, we study codewords appearing in quotients of the
% universal cover, i.e., codewords in cycle codes associated to finite
% unramified covers of the graph $X$.  Such vectors are called {\em
% pseudo-codewords}.  Our approach to studying pseudo-codewords is to
% show that they are intimately related to the {\em edge zeta function}
% of the graph $X$.
% 
% XXXXX In Section~\ref{sec:cycle:codes}, we formally define cycle codes,
% pseudo-codewords, and the edge zeta function.  We also prove that the
% pseudo-codewords are precisely the exponent vectors of the monomials appearing
% with nonzero coefficient in the Taylor series expansion of the edge zeta
% function.  Section~\ref{sec:ldpc:codes} explains the connection between
% cycle codes and low-density parity-check (LDPC) codes and then shows how, in
% certain cases, the pseudo-codewords of an LDPC code are given by the edge zeta
% function of an associated graph.  Finally, in
% Section~\ref{sec:fundamental:cone} we show how the Newton polytope of the
% zeta function (i.e., the polytope spanned by the exponents of the zeta
% function in power series form) plays a crucial role in characterizing
% performance of iterative decoding algorithms.
% 
% The following definition introduces undirected graphs which will be used
% throughout this paper.
% 
% XXXXX For cycle codes there is an interesting connection between the
% fundamental cone and the zeta function of the normal graph of the code.
% 
% XXXXX A fundamental question is now how to find all pseudo-codewords for
% $C_X$. This is answered using the {\em edge zeta function} of the graph $X$.

% XXXXX Say something about Code A and Code B; not a cycle code vs. cycle code.

% XXXXX Include $\wps$ stuff.



%***************************************************************************

% \begin{example}[Code B]
%   Then on the 2-cover of $X_0$ given in Fig.~\ref{fig:bowtie:cover:1}, the
%   path which uses the edges 1, 2, 4, 7, 6, 5, 4', 3 is a cycle. Thus, we see
%   that $(1,1,1,2,1,1,1)$ is a pseudo-codeword for $C_{X_0}$.
% \end{example}


%***************************************************************************

%% \begin{proof} By Definition~\ref{edgezetafunction}, the monomial
%%   $u_1^{p_1}\dots u_n^{p_n}$ appears with nonzero coefficient in
%%   $\zeta_X$ if and only if there are backtrackless, tailless, primitive
%%   cycles $C_1, \dots, C_m$ on $X$ such that
%% \begin{align*}
%% u_1^{p_1}\dots u_n^{p_n} = g(C_1)^{q_1} \dots g(C_m)^{q_m}
%% \end{align*} 
%% for some nonnegative integers $q_1, \dots, q_m$.  It is thus enough
%% to prove that $C$ is a backtrackless, tailless cycle on $X$ if and
%% only if $C = \pi(\cC)$ for some simple cycle $\cC$ on
%% some (finite, unramified) cover $Y$ of $X$, where $\pi:Y \to X$ is the
%% canonical surjection. Here a cycle is called {\em simple} if in its
%% expression as a sequence of adjacent vertices, no vertices are
%% repeated (except that the first and last are necessarily the same).

%% So, first suppose that $\pi:Y\to X$ is a cover of $X$ and that $\cC$
%% is a simple cycle on $Y$.  We must show that $\pi(\cC)$ is a
%% backtrackless, tailless cycle on $X$.  Suppose otherwise, namely, that
%% $(x, y, x)$ is part of the vertex sequence of $\pi(\cC')$ for some
%% $\cC'$ equivalent to $\cC$. Then it comes from $(u, v, w)$ in $\cC'$.
%% In particular, this means that $v$ is adjacent to two distinct
%% vertices $u$ and $w$ in $Y$, both of which project to $x$. This cannot
%% happen in a finite unramified cover. Thus $\pi(\cC)$ is backtrackless
%% and tailless.

%% For the converse, we must show that given a backtrackless, tailless
%% cycle $C$ on $X$, there is a (finite, unramified) cover $\pi:Y \to X$ and
%% a simple cycle $\cC$ on $Y$ lifting $C$.  We will do this by induction
%% on the length of $C$.  Notice that any backtrackless cycle has length
%% at least 3 and that there is nothing to prove if $C$ is simple as we
%% may take $Y = X$ and $\cC = C$.  Since every cycle of length $3$ is
%% simple, we have our base case for the induction.

%% Assume that every backtrackless, tailless cycle of length at most
%% $r-1$ on $X$ can be lifted to a simple cycle on some cover of $X$, and
%% suppose $C$ is a backtrackless, tailless cycle of length $r$ on $X$.
%% We write $C$ in terms of the vertices it uses:
%% \begin{align*}
%% C = (v_1, \dots, v_r, v_{r+1}=v_1).
%% \end{align*} 
%% If $C$ is simple, there is nothing to do.  Hence we assume that $C$
%% is not simple.

%% Let $i$ be the smallest index so that $v_i$ occurs among $v_1, \dots,
%% v_{i-1}$, and let $k$ be the unique index between $1$ and $i-1$ such
%% that $v_k=v_i$.  Note that $i \geq 4$ and $k \leq i-3$ since $C$ has
%% no backtracking.  The cycle
%% \begin{align*}
%% C_1 := (v_k, v_{k+1}, \dots, v_{i-1}, v_i=v_k)
%% \end{align*}
%% is simple.  Let 
%% \begin{align*}
%% C_2 := (v_1, \dots, v_k=v_i, v_{i+1}, \dots, v_r, v_{r+1}=v_1)
%% \end{align*}
%% be the cycle obtained by removing $C_1$ from $C$.  Clearly, $C_2$
%% has length less than $r$.  

%% Suppose $C_2$ is backtrackless. Then it is also tailless.  It will 
%% be convenient to consider the
%% cycle
%% \begin{align*}
%% C_2' = (v_i, v_{i+1}, \dots, v_{r+1}=v_1, v_2, \dots, v_{k-1}, v_k =
%% v_i)
%% \end{align*} 
%% which is equivalent to $C_2$.  Notice that $C$ is equivalent to the
%% cycle which starts by going from $v_{k-1}$ to $v_k$, follows all of
%% $C_1$ back to $v_k=v_i$, and then follows $C_2'$ back to $v_{k-1}$.
%% Clearly it is enough to provide a simple lifting of this equivalent
%% cycle.  Since $C_2'$ is backtrackless and tailless, by induction
%% hypothesis there is a cover $\pi':Y' \to X$ which contains a simple
%% lifting
%% \begin{align*}
%% \cC_2' = (w_i, w_{i+1}, \dots, w_{r+1}=w_1, w_2, \dots, w_{k-1}, w_k =
%% w_i)
%% \end{align*} 
%% of $C_2'$ with $\pi'(w_j) = v_j$ for each $j$.  Let $w'$ be the
%% neighbor of $w_i$ in $Y'$ with $\pi'(w') = v_{i-1}$, and let $Y$ be
%% the cover of $X$ created by taking the disjoint union of $X$ and $Y'$
%% with the edges $(v_{k-1},v_k)$, $(w_{k-1},w_k)$, $(v_{i-1},v_i)$, and
%% $(w',w_i)$ replaced by $(w_{k-1},v_k)$, $(v_{k-1},w_k)$,
%% $(v_{i-1},w_i)$, and $(w',v_i)$, respectively.  Now let $\cC$ be the
%% cycle on $Y$ which begins at $w_{k-1} \in Y'$, crosses to $X$ via the
%% edge $(w_{k-1}, v_k)$, follows $C_1$ in $X$ up to and including the
%% edge $(v_{i-2}, v_{i-1})$, uses the edge $(v_{i-1},w_i)$ to cross back
%% to $Y'$, and then follows $\cC_2'$ in $Y'$ to get back to $w_{k-1}$.
%% That is,
%% \begin{align*}
%% \cC = (w_{k-1}, v_k, v_{k+1}, \dots, v_{i-1}, w_i, w_{i+1}, \dots,
%% w_{k-1}).
%% \end{align*} 
%% Then $\cC$ is a simple cycle on $Y$ which lifts a cycle equivalent
%% to $C$.

%% On the other hand, suppose $C_2$ contains a backtrack.  Then it must
%% be $(v_{k-1}, v_k, v_{i+1})$ since $C$ is backtrackless.  Hence we
%% have $v_{k-1} = v_{i+1}$.  Let $l$ be the largest integer such that
%% $v_{k-j} = v_{i+j}$ for all $1 \leq j \leq l$. Here the indices are read
%% modulo $r$. Let $P$ be the path
%% \begin{align*}
%% P = (v_{k-l}, v_{k-l+1}, \dots, v_k)
%% \end{align*}
%% and write $-P$ for the path
%% \begin{align*}
%% -P = (v_k, v_{k-1}, \dots, v_{k-l}) = (v_i, v_{i+1}, \dots, v_{i+l})
%% \end{align*}
%% so that $-P$ is the path $P$ traced backwards.  Then $P$ is
%% backtrackless and tailless, and $C_2$ is equivalent to the cycle which
%% first follows $P$, then $-P$, then the cycle
%% \begin{align*}
%% C_2' = (v_{i+l}, \dots, v_{r+1}=v_1, \dots, v_{k-l-1},
%% v_{k-l}=v_{i+l}).
%% \end{align*} 
%% Note that $C$ is equivalent to the cycle which starts at $v_{k-l}$,
%% follows $P$ to $v_k$, follows all of $C_1$ back to $v_k$, follows $-P$
%% back to $v_{k-l} = v_{i+l}$, and then follows all of $C_2'$ back to
%% $v_{i+l}=v_{k-l}$.  Since $C_2'$ is backtrackless and tailless and has
%% length strictly smaller than $r$, our induction hypothesis applies.
%% Thus there is a cover $\pi':Y' \to X$ which contains a backtrackless,
%% tailless, simple lifting
%% \begin{align*}
%% \cC_2' = (w_{i+l}, \dots, w_{r+1}=w_1, \dots, w_{k-l-1},
%% w_{k-l}=w_{i+l})
%% \end{align*}
%% of $C_2'$, where $\pi'(w_j) = v_j$ for each $j$.  There is also a
%% cover $\phi:Z \to X$ containing a lifting
%% \begin{align*}
%% \cP = (q_{k-l}, q_{k-l+1}, \dots, q_k)
%% \end{align*} 
%% of $P$, where $\phi(q_j) = v_j$ for each $j$ and no two vertices on
%% $\cP$ are the same.  Let $\pi:Y \to X$ be the cover of $X$ created by
%% taking the disjoint union of $X$, $Y'$, and two copies of $Z$, labeled
%% by $\phi_1:Z(1)\to X$ and $\phi_2:Z(2)\to X$, but replacing various
%% edges as follows: We replace $(q_{k-1}(1), q_k(1))$ and $(v_{k-1},
%% v_k)$ with $(q_{k-1}(1), v_k)$ and $(v_{k-1}, q_k(1))$. We replace
%% $(v_{i-1}, v_i=v_k)$ and $(z(2), q_k(2))$ with $(v_{i-1}, q_k(2))$ and
%% $(z(2), v_i=v_k)$, where $z(2)$ is the neighbor of $q_k(2)$ in $Z(2)$
%% with $\phi_2(z(2)) = v_{i-1}$.  We replace $(q_{k-l}(2),
%% q_{k-l+1}(2))$ and $(w_{k-l},w)$ with $(q_{k-l}(2), w)$ and $(w_{k-l},
%% q_{k-l+1}(2))$, where $w$ is the neighbor of $w_{k-l}$ in $Y'$
%% satisfying $\pi'(w) = \phi_2(q_{k-l+1}(2)) = v_{k-l+1}$.  Finally, we
%% replace $(w_{k-l-1}, w_{k-l})$ and $(q(1), q_{k-l}(1))$ with
%% $(w_{k-l-1}, q_{k-l}(1))$ and $(q(1), w_{k-l})$, where $q(1)$ is the
%% neighbor of $q_{k-l}(1)$ in $Z(1)$ satisfying $\phi_1(q(1)) =
%% \pi(w_{k-l-1}) = v_{k-l-1}$.  Now let $\cC$ be the cycle in $Y$ which
%% begins at $q_{k-l}(1) \in \Z(1)$, follows the path $\cP(1)$ to
%% $q_{k-1}(1)$, uses the edge $(q_{k-1}(1), v_k)$ to cross to $X$,
%% follows $C_1$ in $X$ to $v_{i-1}$, uses the edge $(v_{i-1}, q_k(2))$
%% to cross to $Z(2)$, follows $-\cP$ to $q_{k-l+1}(2)$, uses the edge
%% $(q_{k-l+1}(2), w_{k-l})$ to cross to $Y'$, follows $\cC_2'$ to
%% $w_{k-l-1}$, and finally crosses back to $Z(1)$ via the edge
%% $(w_{k-l-1}, q_{k-l}(1))$.  That is,
%% \begin{align*}
%% \cC &= (q_{k-l}(1), q_{k-l+1}(1), \dots, q_{k-1}(1), v_k, v_{k+1},
%% \dots, \\ &\phantom{space} v_{i-1}, q_k(2), q_{k-1}(2), \dots,  q_{k-l+1}(2),
%% w_{k-l}=w_{i+l}, \\ &\phantom{space} w_{i+l+1}, \dots, w_{k-l-1}, q_{k-l}(1)).
%% \end{align*}
%% Then $\cC$ is a simple cycle on $Y$ which lifts a cycle equivalent to $C$.
%% \end{proof}


% We begin this section with a definition and brief discussion of LDPC
% codes. 
% 
% %***************************************************************************
% 
% \begin{definition}
%   Let $G$ be a bipartite graph with vertex set $U\cup V$ and edge set $E$.  We
%   will refer to $U$ as the {\em left vertices} and $V$ as the {\em right
%   vertices}.  Order the left vertices $u_1, \dots u_n$ and consider each as a
%   binary variable.  Consider each right vertex $v$ as the binary linear
%   function of the $u_i$'s given by
%   \begin{align*}
%   v(u_1, \dots, u_n)
%     &= \sum_{u_i \in \del(v)} u_i
%   \end{align*} 
%   where $\del(v)$ is, as before, the neighborhood of $v$, that is, the
%   collection of vertices $u_i$ such that $(u_i,v) \in E$.  The {\em
%   low-density parity-check (LDPC) code} $C_G$ on $G$ is the collection of
%   binary sequences $(c_1, \dots, c_n)$ such that $v(c_1, \dots, c_n) = 0$ for
%   each $v \in V$.  The graph $G$ is called a {\em Tanner graph} for the code
%   $C_G$.
% \end{definition}
% 
% %***************************************************************************
% 
% %% \begin{remark} Let us explain briefly the term ``low-density parity
% %%   check code''.  Let $G$ and $C_G$ be as above.  Let $H$ be the
% %% adjacency matrix of the bipartite graph $G$, so that $H = (h_{uv})$
% %% with rows and columns indexed by $U$ and $V$, respectively, where
% %% $h_{uv} = 1$ if and only if $(u,v) \in E$.  Then it is plain to see
% %% that $H$ is a parity-check matrix for $C$.  (We are using the phrase
% %% ``parity-check matrix'' a bit loosely here, for $H$ need not have full
% %% rank.  However, it is true that $c \in C$ if and only if $Hc^t = 0$.)
% %% This explains the use of the phrase ``parity-check code''.  As was the
% %% case for cycle codes, there is a decoding algorithm for $C_G$ which
% %% operates locally on the graph $G$ and which is most efficient when $G$
% %% has few edges, i.e., when $H$ is a sparse, or ``low-density'' matrix.
% %% Hence the term ``low-density parity-check code''.
% %% \end{remark}
% 
% %***************************************************************************
% 
% \begin{definition} Let $G$ be a bipartite graph and let $C_G$ be the
% associated LDPC code.  Let $\widetilde G$ be any (finite, unramified) cover
% of $G$ and $C_{\widetilde G}$ the LDPC code corresponding to $\widetilde G$.  A
% {\em pseudo-codeword} for $C_G$ is any codeword in $C_{\widetilde G}$.
% \end{definition}
% 
% %***************************************************************************
% 
% \begin{definition}
%   Let $X = (V,E)$ be a graph. The {\em associated bipartite graph} $G = G(X)$
%   is the bipartite graph with vertex set $E \cup V$ and edge set consisting of
%   all those pairs $(e,v)$ with $e \in E$ and $v \in V$ such that $e = (v,v')$
%   for some $v' \in V$.  We consider $E$ to be the left vertices of $G$ and $V$
%   to be the right vertices of $G$.
% \end{definition}
% 
% %***************************************************************************
% 
% \begin{example}
%   \label{ex:bowtie:LDPC}
% 
%   After labeling the edges and vertices of our favorite graph $X_0$, we obtain
%   the bipartite graph $G(X_0)$ on the right-hand side of
%   Fig.~\ref{fig:bowtie:bipartite:1}. Since the LDPC code associated to
%   $G(X_0)$ is the collection of vectors $(c_1, \dots, c_7)$ which satisfy
%   parity in the right vertices, we see that the LDPC code contains exactly
%   four vectors: (0,0,0,0,0,0,0), (1,1,1,0,0,0,0), (0,0,0,0,1,1,1), and
%   (1,1,1,0,1,1,1).
% \end{example}
% 
% %***************************************************************************
% 
% Notice that the LDPC code associated to $G(X_0)$ in
% Ex.~\ref{ex:bowtie:LDPC} is exactly the cycle code associated to
% $X_0$ found in Ex.~\ref{ex:favorite:graph}.  In general, we have:
% 
% %***************************************************************************
% 
% \begin{lemma}\label{ldpc=cycle} Let $X$ be a graph and $G = G(X)$ the
%   associated bipartite graph.  Then the cycle code associated to $X$
%   and the LDPC code associated to $G$ are identical.
% \end{lemma}
% 
% %***************************************************************************
% 
% %% \begin{proof} Write $C$ for the cycle code associated to $X$ and $D$
% %%   for the LDPC code associated to $G$.  Let $c = (c_1, \dots, c_n)$ be
% %%   a codeword in $C$.  We may assume that $c$ is a characteristic
% %%   vector for some simple cycle on $X$ since such vectors generate $C$.
% %%   Let $Y$ be the subgraph of $X$ formed by using only those edges
% %%   $e_i$ with $c_i=1$.  Then the simple cycle corresponding to the
% %%   codeword $c$ is an Euler circuit on $Y$, and so by Euler's theorem
% %%   the degree of every vertex in $Y$ is even, i.e., $v(c_1, \dots, c_n)
% %%   = 0$ for every $v \in V_Y \subset V_X$ where $V_Y$ and $V_X$ are the
% %%   vertex sets of $Y$ and $X$ respectively.  For $v \in V_X \setminus
% %%   V_Y$, we have $v(c) = 0$ trivially.  Hence $c \in D$.
% 
% %%   For the reverse containment, let $d$ be a codeword in $D$.  Let $Y$
% %%   be the subgraph of $X$ formed by using the edges $e_i$ with $d_i=1$.
% %%   Then since $v(d) = 0$ for every $v \in V_X$, there is an Euler
% %%   circuit on $Y$.  This gives a cycle on $X$ which uses exactly those
% %%   edges $e_i$ for which $d_i=1$.  Hence $d \in C$.
% %% \end{proof}
% 
% %***************************************************************************
% 
% Notice that for any graph $X$, the associated bipartite graph $G=G(X)$
% is {\em left 2-regular}, that is, every left vertex of $G$ has
% degree exactly 2.  Indeed, it is clear that an arbitrary bipartite
% graph $G$ is of the form $G=G(X)$ for some graph $X$ if and only if
% $G$ is left 2-regular. We call such a graph $X$ a {\em cycle graph}
% of $G$.
% 
% %***************************************************************************
% 
% %% Our goal is to describe pseudo-codewords of arbitrary LDPC codes, not
% %% just those which come from left 2-regular bipartite graphs.  To do
% %% this, we must first introduce the notion of hypergraphs.
% 
% %% \begin{definition} Fix an integer $s \geq 2$.  An (undirected) {\em
% %%   $s$-hypergraph} $X$ is a pair or sets $(V,E)$, where $E$ is a subset
% %%   of $V^{(s)}$, the collection of subsets of $V$ of size $s$.  The
% %%   elements of $V$ are called the {\em vertices} of $X$ and the
% %%   elements of $E$ are called the {\em hyperedges} of $X$.
% %% \end{definition}
% 
% %% Note that a $2$-hypergraph is simply a graph.
% 
% %% \begin{definition} Let $G$ be a left $s$-regular bipartite graph.
% %%   We define the {\em cycle hypergraph} $X$ of $G$ to be the
% %%   $s$-hypergraph whose vertex set $V$ is the set of right vertices of
% %%   $G$ and whose hyperedge set $E$ is given by
% %% \begin{align*}
% %% E = \{\del(u) \, | \, u \text{ is a left vertex of $G$}\}.
% %% \end{align*}
% %% \end{definition}
% 
% %% We wish to define and study the edge zeta function of a hypergraph and
% %% to show that the pseudo-codewords of an LDPC code associated to a left
% %% $s$-regular bipartite graph $G$ are in one-to-one correspondence with
% %% the monomials which appear with nonzero coefficient in the zeta
% %% function of the cycle hypergraph of $G$.  Towards this end, we must
% %% \begin{itemize}
% %% \item define what it means for a sequence of edges to be a path or a
% %%   cycle in a hypergraph (i.e. figure out what we want it to mean)
% %% \item define the cycle code of a hypergraph
% %% \item prove that the LDPC code associated to a left $s$-regular
% %%   bipartite graph is the same as the cycle code of the associated
% %%   $s$-hypergraph
% %% \item define the monomial of a path in a hypergraph
% %% \item define the edge zeta function (which probably means figuring out
% %%   what backtrackless, tailless, and primitive mean)
% %% \item prove that the pseudo-codewords of an LDPC code associated to a
% %%   left $s$-regular bipartite graph are in one-to-one correspondence
% %%   with the monomials which appear with nonzero coefficient in the edge
% %%   zeta function of the corresponding cycle hypergraph
% %% \end{itemize}
% 
% %% Then it would be nice if we could drop the hypothesis that our
% %% bipartite graph is left $s$-regular for some $s$.  I'm thinking that
% %% maybe we could do this by considering our bipartite graph as a union
% %% of subgraphs, each of which is left $s$-regular for some $s$.  Then
% %% we take the cycle hypergraph of each subgraph and maybe just add up
% %% the zeta functions?  I'm not sure......










%***************************************************************************

%Equivalently, to define $C_X$ we may first associate to each edge
%$e\in E$ a binary variable. Then a binary sequence is a codeword in
%$C_X$ if and only if the binary variables satisfy parity in each
%vertex.

%***************************************************************************

%\begin{example}
%  \label{ex:favorite:graph}
%
%  Let $X_0$ be the graph shown in Fig.~\ref{fig:bowtie:1}: Then the cycle code
%  on $X_0$ is the code \{(0,0,0,0,0,0,0), (1,1,1,0,0,0,0), (0,0,0,0,1,1,1),
%  (1,1,1,0,1,1,1)\}.
%\end{example}

%***************************************************************************


%***************************************************************************

%% One successful decoding algorithm for cycle codes is a so-called
%% message-passing algorithm.  
%% %% Recall that the decoding problem is
%% %% described as follows: Given any sequence of bits $\vy\in \F_2^n$ we
%% %% must find the codeword that is closest to the sequence $\vy$, with
%% %% respect to some given metric. (In practice, the distance between $\vy$
%% %% and $\vc$ is often measured as $\log P(\vy|\vc)$, but it is not a
%% %% problem to think in terms of Hamming distance.)  Decoding is, in
%% %% general, a very hard problem since, for practical reasons, a
%% %% complexity is required that is polynomial in the length of the code.
%% Message-passing algorithms operate by sending messages along the edges
%% of the graph concerning the reliability of the bit on the
%% corresponding edge.
%% %%
%% More precisely, consider a vertex $v$ with incident edges $e_1$,
%% $e_2$, \dots, $e_t$.  From the parity-check relation that has to be
%% satisfied at $v$ we can compute an outgoing message along each edge by
%% letting the outgoing message record what all the ``other'' bits incident
%% to $v$ believe the bit in question should be. Messages are exchanged in
%% the graph until global agreement is reached among the messages (or a
%% timer exceeds a preset limit). 

%% The point here is that the algorithm combines {\em local} decisions in
%% the graph into a {\em global} decision. A side-effect of the fact that
%% we combine local operations is that the message-passing algorithm is
%% not aware of the global structure of the graph. In other words, the
%% algorithm does not know if the decoding happens in the original graph
%% or in any cover of the graph. Moreover, it can be proved that these
%% message-passing algorithms perform optimal decoding in the universal
%% cover of the graph.  The received word $\vy$ is lifted to a received
%% word in the universal cover by replicating received values every time
%% we replicate an edge in the universal cover.  Since we know what the
%% algorithm does in the universal cover, in principle, all we need to
%% get a handle on are the codewords in the universal cover. This
%% motivates the following definitions.



%***************************************************************************

%  Here and in the following, we let $X$ be a graph with vertex set $V$ and
%  edge set $E \subset V\times V$. We write $n \defeq |E|$, and assume a fixed
%  ordering on $E$, so that $E = \{e_1, \dots, e_n\}$.  For $v \in V$, we write
%  $\del(v)$ for the {\em neighborhood} of $v$, i.e., the collection of
%  vertices of $X$ which are adjacent to $v$.








%***************************************************************************

%% \begin{definition}
%%   We let $\R$, $\Rp$, and $\Rpp$ be the set of real numbers, the set
%%   of non-negative real numbers, and the set of positive real numbers,
%%   respectively. For any positive integer $n$, we say that $\Rp^n$ and
%%   $\Rpp^n$ are the {\em non-negative} and {\em positive orthant},
%%   respectively, of $\R^n$.  In the following, all scalars, entries of
%%   vectors, and entries of matrices will be considered to be in $\R$,
%%   unless noted otherwise.  For any positive integer $M$, we write
%%   $[M]$ for the set of integers $\{1, \dots, M\}$.
%% \end{definition}



%***************************************************************************

%% \begin{figure}
%%   \begin{center}
%%     \epsfig{file=fg_cover1_2mod3.fig.eps}
%%     \quad\quad\quad\quad
%%     \epsfig{file=fg_cover1_2mod2.fig.eps}
%%   \end{center}
%%   \caption{Left: Tanner graph $\graph{T}$ of code in 
%%     Ex.~\ref{ex:simple:tanner:graph:1}. Right: $M$-fold Tanner graph cover
%%     $\graph{\widetilde T}$ of the Tanner graph $\graph{T}$.}
%%   \label{fig:simple:tanner:graph:1}
%% \end{figure}

%***************************************************************************











%***************************************************************************

%% \begin{proof}
%%   Let $\matr{\widetilde H}$ be the parity-check matrix of $\code{\widetilde
%%   C}$. Let the rows of $\matr{\widetilde H}$ be indexed by $(i,m) \in
%%   \set{J} \times [M]$. Fix a codeword $\tvc$ from
%%   $\code{\widetilde C}$. Because $\matr{\widetilde H} \cdot \tvc = \vect{0} \
%%   (\text{mod $2$})$, we must have for any $j \in \set{J}$, $i \in
%%   \set{I}_j$, and $m \in [M]$, that
%%   \begin{align}
%%     \sum_{i' \in \set{I}_j \setminus \{ i \}}
%%       \widetilde c_{i',\pi_{j,i'}(m)}
%%       &\geq
%%         \widetilde c_{i,\pi_{j,i}(m)}.
%%           \label{eq:fc:inequality:proof:1:1}
%%   \end{align}
%%   This can be seen as follows: if $\widetilde c_{i,\pi_{j,i}(m)} = 0$ then
%%   the inequality is trivially true whereas if $\widetilde
%%   c_{i,\pi_{j,i}(m)} = 1$ then it follows from
%%   (\ref{eq:remark:parity:check:equality:cover:code:1}) that among the
%%   set $\set{I}_j \setminus \{ i \}$ there is at least one $i'$ such
%%   that $\widetilde c_{i',\pi_{j,i'}(m)} = 1$. Summing
%%   (\ref{eq:fc:inequality:proof:1:1}) over $m \in [M]$ for a
%%   fixed $i \in \set{J}$ and $j \in \set{I}_j$ and dividing by $M$ we
%%   must have
%%   \begin{align}
%%     \frac{1}{M}
%%     \sum_{m \in [M]}
%%       \sum_{i' \in \set{I}_j \setminus \{ i \}}
%%         \widetilde c_{i',\pi_{j,i'}(m)}
%%       &\geq
%%         \frac{1}{M}
%%         \sum_{m \in [M]}
%%           \widetilde c_{i,\pi_{j,i}(m)}
%%   \end{align}
%%   or
%%   \begin{align}
%%     \sum_{i' \in \set{I}_j \setminus \{ i \}}
%%       \frac{1}{M}
%%       \sum_{m \in [M]}
%%         \widetilde c_{i',\pi_{j,i'}(m)}
%%       &\geq
%%         \frac{1}{M}
%%         \sum_{m \in [M]}
%%           \widetilde c_{i,\pi_{j,i}(m)}.
%%   \end{align}
%%   Using Def.~\ref{def:pseudo:codeword:1} and $\omega_i \defeq \omega_i(\tvc)$,
%%   this can be written as
%%   \begin{align}
%%     \sum_{i' \in \set{I}_j \setminus \{ i \}}
%%       \omega_{i'}
%%       &\geq
%%         \omega_{i},
%%   \end{align}
%%   which proves (\ref{eq:def:fc:condition:2}).
%%   Eq.~(\ref{eq:def:fc:condition:1}) follows trivially from the
%%   non-negativeness of the elements of $\tvc$. This proves the claim that
%%   $\vomega(\tvc) \in \fch{K}{H}$.
%% \end{proof}


%***************************************************************************

%% \begin{proof}
%%   Let the vector $\vnu \in \R^n$ have components $\nu_j \defeq 2 \lceil \beta
%%   \omega'_i \rceil$ for some $\beta > 0$. It is easy to see that if $\beta$ is
%%   chosen large enough, then there is an $\gamma > 0$ such that $||\gamma \vnu
%%   - \vomega'||_2 < \varepsilon$. We take such a $\beta$.
  
%%   In a first step we show that that $\vnu \in \fch{K}{H}$.
%%   Eq.~(\ref{eq:def:fc:condition:1}) is obviously fulfilled. The fact $\lceil a
%%   \rceil + \lceil b \rceil = \big\lceil \lceil a \rceil + \lceil b \rceil
%%   \big\rceil \geq \lceil a + b \rceil$ for $a, b \in \R$ helps us to prove
%%   (\ref{eq:def:fc:condition:2}). Indeed, we observe that
%%   \begin{align}
%%     \forall j \in \set{J}, \
%%       \forall i \in \set{I}_j:
%%         \quad
%%     \sum_{i' \in \set{I}_j \setminus \{ i \}}
%%       \omega'_{i'}
%%       &\geq
%%         \omega'_{i}
%%   \end{align}
%%   (which holds by the assumption in the lemma statement) implies
%%   \begin{align}
%%     \forall j \in \set{J}, \
%%       \forall i \in \set{I}_j:
%%         \quad
%%     \sum_{i' \in \set{I}_j \setminus \{ i \}}
%%       2
%%       \lceil
%%         \beta \omega'_{i'}
%%       \rceil
%%       &\geq
%%         2
%%         \lceil
%%           \beta \omega'_{i}
%%         \rceil.
%%   \end{align}
  
%%   Let $\set{J} \defeq \set{J}(\matr{H})$ and $\set{I}_j \defeq
%%   \set{I}_j(\matr{H})$. In a second step we will define an integer $M$ and
%%   permutations $\pi_{j,i}$ for all $j \in \set{J}$ and $i \in \set{I}_j$ such
%%   that we can exhibit a codeword $\tvc$ with $M \cdot \vomega(\tvc) =
%%   \vnu$. We use the following algorithm.
%%   \begin{itemize}
%%   \item For all $j \in \set{J}$ do 

%%     \begin{itemize}
      
%%     \item Let $m_j := 0$. Let ${\nu'_i}^{\langle 1 \rangle} := \nu_i$ for all
%%       $j \in \set{I}_j$.
      
%%     \item While $\max_{i \in \set{I}_j} {\nu'_i}^{\langle m_j + 1 \rangle} > 0$ do

%%       \begin{itemize}
    
%%       \item Let $m_j := m_j + 1$.
  
%%       \item Let $i_1$ be the largest $i \in \set{I}_j$ such that
%%         ${\nu'_{i_1}}^{\langle m_j \rangle} = \max_{i \in \set{I}_j}
%%         {\nu'_i}^{\langle m_j \rangle}$. Let $i_2$ be the smallest $i \in
%%         \set{I}_j$ such that ${\nu'_{i_2}}^{\langle m_j \rangle} = \min_{i}
%%         {\nu'_i}^{\langle m_j \rangle}$, where the minimum is taken over the
%%         set of all non-negative $\nu'_i$'s with $i \in \set{I}_j$.
        
%%       \item If $i_1 = i_2$ then halt. $(*)$
  
%%       \item Let $\pi_{j,i_1}(m_j) := {\nu'_{i_1}}^{\langle m_j \rangle}$ and
%%         $\pi_{j,i_2}(m_j) := {\nu'_{i_2}}^{\langle m_j \rangle}$.
        
%%       \item Let ${\nu'_{i_1}}^{\langle m_j+1 \rangle} := {\nu'_{i_1}}^{\langle
%%           m_j \rangle} - 1$ and ${\nu'_{i_2}}^{\langle m_j+1 \rangle} :=
%%         {\nu'_{i_2}}^{\langle m_j \rangle} - 1$. For all other $i \in
%%         \set{I}_j$ define ${\nu'_{i}}^{\langle m_j+1 \rangle} :=
%%         {\nu'_{i}}^{\langle m_j \rangle}$.  $(**)$

%%       \end{itemize}

%%     \end{itemize}
    
%%   \item Let $M := \max_{j \in \set{J}} m_j$ and assign some arbitrary
%%     \emph{valid} values to the $\pi_{j,i}(m)$'s to which we have not assigned
%%     a value yet.
    
%%   \item For $i \in \set{I}$, $m \in [1,M]$, let $\tvc_{i,m} := 1$ if $m \leq
%%     \nu_j$ and $\tvc_{i,m} := 0$ otherwise.

%%   \end{itemize}
%%   The vector $\tvc$ is obviously a codeword and fulfills $M \cdot
%%   \vomega(\tvc) = \vnu$ if we can show that the program terminates properly,
%%   i.e.~it does not halt at $(*)$. For the chosen vector $\vnu$ we indeed have
%%   $i_1 \neq i_2$ each time the inner loop is performed; this will be shown
%%   once we have proven two loop invariances of the inner loop.
  
%%   Let us analyze the interior of the ``For all $j \in \set{J}$ do'' loop.  So,
%%   let an $j \in \set{J}$ be fixed. For the inner loop, there are two loop
%%   invariances, i.e.~conditions that are fulfilled each time the inner loop is
%%   performed. The first concerns the even-ness of $\sum_{i \in \set{I}_j}
%%   {\nu'_i}^{\langle m_j \rangle}$ for each $m_j$, the second states that the
%%   ${\nu'_i}^{\langle m_j \rangle}$'s fulfill a ``fundamental cone codition''
%%   for each $m_j$.
  
%%   Let us focus on the first loop invariance which says that $\sum_{i \in
%%     \set{I}_j} {\nu'_i}^{\langle m_j \rangle}$ is even for each $m_j$. This is
%%   clearly the case for $m_j = 1$ because of setting $\nu_i \defeq 2 \lceil
%%   \beta \omega'_j \rceil$ at the beginning of the proof. (Note that other
%%   choices of $\nu_i$ could have guaranteed the even-ness of this above sum.)
%%   Now assume that the even-ness condition is fulfilled at loop index $m_j$.
%%   Because of step $(**)$ it is easy to see that the the even-ness condition is
%%   also fulfilled at loop index $m_j + 1$  (if that is performed at all).
  
%%   Now, let us turn to the second loop invariance which states that for each
%%   loop index $m_j$ we have:
%%   \begin{align}
%%     \begin{cases}
%%       \forall i \in \set{I}_j:
%%         \quad
%%           {\nu'_{i}}^{\langle m_j \rangle}
%%           &\geq 0 \\
%%       \forall i \in \set{I}_j:
%%         \quad
%%       \sum_{i' \in \set{I}_j \setminus \{ i \}}
%%         {\nu'_{i'}}^{\langle m_j \rangle}
%%         &\geq
%%           {\nu'_{i}}^{\langle m_j \rangle}.
%%     \end{cases}
%%           \label{eq:proof:loop:condition:1}
%%   \end{align}
%%   Because $\vnu$ is in the fundamental cone, it can easily be seen that this
%%   (\ref{eq:proof:loop:condition:1}) is fulfilled for loop counter $m_j = 1$.
%%   Now assume that (\ref{eq:proof:loop:condition:1}) is fulfilled for loop
%%   counter value $m_j$. 
%%   \begin{itemize}
    
%%   \item If ${\nu'_{i_1}}^{\langle m_j \rangle}$ is larger than any other
%%     ${\nu'_i}^{\langle m_j \rangle}$, $i \in \set{I}_j$, then it can easily be
%%     seen that (\ref{eq:proof:loop:condition:1}) is also fulfilled for loop
%%     counter value $m_j + 1$ (if that is performed at all).
    
%%   \item If ${\nu'_{i_1}}^{\langle m_j \rangle}$ has the same value as the
%%     second-largest $\nu'_i$, $i \in \set{I}_j$, then we have to be a bit more
%%     careful.
%%     \begin{itemize}
      
%%     \item If there are only two non-zero ${\nu'_{i}}^{\langle m_j \rangle}$'s,
%%       $j \in \set{I}_j$, then because of (\ref{eq:proof:loop:condition:1}) at
%%       loop index $m_j$ they must have the same value and obviously
%%       (\ref{eq:proof:loop:condition:1}) is also fulfilled for loop counter
%%       value $m_j + 1$ (if that is performed at all).
      
%%     \item If there are only three non-zero ${\nu'_{i}}^{\langle m_j
%%         \rangle}$'s, $i \in \set{I}_j$, we define $i''$ to be the
%%       ``remaining'' index, i.e.~$i'' \in \set{I}_j$ where $i'' \neq i_1$, $i''
%%       \neq i_2$ and $\nu'_{i''} > 0$. Then the quantity
%%       ${\nu'_{i''}}^{\langle m_j+1 \rangle} = {\nu'_{i''}}^{\langle m_j
%%         \rangle}$ is by one larger than ${\nu'_{i_1}}^{\langle m_j+1
%%         \rangle}$. Condition (\ref{eq:proof:loop:condition:1}) is also
%%       fulfilled for loop counter value $m_j + 1$ (if that is performed at all)
%%       if ${\nu'_{i_2}}^{\langle m_j+1 \rangle}$ is at least $1$. This is
%%       always the case, i.e.~${\nu'_{i_2}}^{\langle m_j+1 \rangle} = 0$ is not
%%       possible because this would imply that $\sum_{i \in \set{I}_j}
%%       {\nu'_i}^{\langle m_j+1 \rangle} = {\nu'_{i_1}}^{\langle m_j+1 \rangle}
%%       + {\nu'_{i''}}^{\langle m_j+1 \rangle} = 2 {\nu'_{i''}}^{\langle m_j+1
%%         \rangle} - 1$ is an odd number, a contradition to the first loop
%%       invariance.
      
%%     \item If there are at least four non-zero ${\nu'_{i}}^{\langle m_j
%%         \rangle}$'s, $i \in \set{I}_j$, then it can easily be seen that
%%       (\ref{eq:proof:loop:condition:1}) is also fulfilled for loop counter
%%       value $m_j + 1$ (if that is performed at all).

%%     \end{itemize}

%%   \end{itemize}
%%   Together, these two loop invariances show that for each $m_j$ there are
%%   always at least two non-zero members among the ${\nu'_{i}}^{\langle m_j
%%     \rangle}$'s, $i \in \set{I}_j$; this proves that $i_1 \neq i_2$ each time
%%   the innter loop is performed.
  
%%   Putting our results together, we found a $\gamma > 0$ and $\vnu$ such that
%%   $||\gamma \vnu - \vomega'||_2 < \varepsilon$ and a $\tvc$ such that $M \cdot
%%   \vomega(\tvc) = \vnu$. But this proves that $||\alpha \vomega(\tvc) -
%%   \vomega'||_2 < \varepsilon$ for $\alpha \defeq \gamma M$.
%% \end{proof}


%***************************************************************************

%% XXXXX New stuff.

%% Let $\langle \,\cdot\, , \,\cdot\, \rangle$ denote the standard inner
%% product. 

%% \begin{definition}[See e.g.~\cite{Boyd:Vandenberghe:04:1}]
%%   A set $K$ is called a {\em cone} if for every $\vx \in K$ and
%%   $\theta \geq 0$ we have $\theta \vx \in K$. A point of the form
%%   $\theta_1 \vx^{(1)} + \cdots + \theta_k \vx^{(k)}$ with $\theta_1
%%   \geq 0, \ldots, \theta_k \geq 0$ is called a {\em conic combination}
%%   of $\vx^{(1)}, \ldots, \vx^{(k)}$. The {\em conic hull}
%%   $\conhull(E)$ of a set $E$ is the set of all conic combinations of
%%   points in $E$. Obviously, $\conhull(E)$ is also the smallest cone
%%   that contains $E$.
%% \end{definition}

%% \begin{definition}[Proper cone, see e.g.~\cite{Boyd:Vandenberghe:04:1}]
%%   A cone $K \subseteq \R^n$ is called a {\em proper cone} if it
%%   satisfies the following: $K$ is convex, $K$ is closed, $K$ is solid
%%   (i.e.~it has nonempty interior), and $K$ is pointed (i.e., it
%%   contains no line or, equivalently, if $\vx \in K and -\vx \in K, then
%%   \vx = \vect{0}$).
%% \end{definition}

%% \begin{definition}[Dual cone, see e.g.~\cite{Boyd:Vandenberghe:04:1}]
%%   Let $K$ be a cone. Its {\em dual cone} $K^{*}$ is defined to be the
%%   set
%%   \begin{align*}
%%     K^{*}
%%       &\defeq
%%          \big\{
%%            \vy \, | \, \langle \vx, \vy \rangle \geq 0 \ \forall \vx \in K
%%          \big\}.
%%   \end{align*}
%% \end{definition}

%% \begin{remark} It can easily be seen that if $K$ is a proper cone then
%% $K^{*}$ is also a proper cone and $K^{**} = K$ (i.e.~the dual of the
%% dual cone is the original cone again).
%% \end{remark}

%% There are two standard ways of describing a proper cone, we will call
%% them the image and the kernel representation, respectively. Note the
%% similarity of the image representation with the generator-matrix
%% description of a linear code and the similarity of the kernel
%% representation with the parity-check-matrix description of a linear
%% code.

%% \begin{definition}[Image representation of a cone]
%%   \label{def:image:representation:of:cone:1}
%%   If a cone $K$ is described by
%%   \begin{align*}
%%     K
%%       &\defeq \conhull(E)
%%        = \left\{
%%            \left.
%%              \sum_{\ve \in E}
%%                \theta_{\ve} \ve
%%            \, 
%%            \right|
%%            \,
%%            \theta_{\ve} \geq 0 \ \forall \ve \in E
%%          \right\},
%%   \end{align*}
%%   where $E$ is some (finite or infinite) set of vectors from $\R^n$,
%%   then we say that this is an {\em image representation} of $K$.
%% \end{definition}

%% We can easily detect if an element of $E$ is \emph{not} necessary in order to
%% describe $K$: an $\ve \in E$ is \emph{not} necessary if it can be written as a
%% conic combination of the other vectors in $E$. On the other hand, the set $\{
%% \theta \ve \, | \, \theta \geq 0 \}$ corresponds to an edge of the cone $K$ if
%% and only if $\ve \in E$ \emph{cannot} be written as a conic combination of the
%% other vectors in $E$.

%% \begin{remark}
%%   Let us briefly explain why we said that the cone description in
%%   Definition~\ref{def:image:representation:of:cone:1} is an ``image
%%   representation''. For simplicity, assume that the set $E$ is finite
%%   with $E = \{ \ve^{(1)}, \ldots, \ve^{(k)} \}$. Let $\phi:\ \R^k \to
%%   \R^n$ be the linear map given by $\phi: \vu \mapsto \vu \Gcone$,
%%   where $\Gcone$ is a $k \times n$ matrix with $\ell$-th row the
%%   vector $\ve^{(\ell)}$.  The cone $K$ can then be seen as the image
%%   of $\R_+^k$ under $\phi$:
%%   \begin{align*}
%%     K
%%       &= \phi(\R_+^k).
%%   \end{align*}
%% \end{remark}

%% \begin{definition}[Kernel representation]
%%   \label{def:kernel:representation:of:cone:1}
%%   If a cone $K$ is described by
%%   \begin{align*}
%%     K
%%       &= \bigcap_{\vn \in N}
%%            \big\{
%%              \vx \in \R^n
%%              \, | \, \langle \vx, \vn \rangle \geq 0 
%%            \big\}
%%        = \big\{
%%            \vx \in \R^n
%%            \, | \, \langle \vx, \vn \rangle \geq 0 
%%            \ \forall \vn \in N
%%          \big\}.
%%   \end{align*}
%%   where $N$ is some (finite or infinite) set of vectors from $\R^n$,
%%   then we say that this is a {\em kernel representation} of $K$. (The
%%   way we defined the cone, the vectors $\vn \in N$ point towards the
%%   interior of the cone $K$. Of course $K$ could have be defined such
%%   that $\vn \in N$ point towards the exterior of the cone $K$.)
%% \end{definition}

%% We can easily detect if an element of $N$ is \emph{not} necessary in
%% order to describe $K$: an $\vn \in N$ is \emph{not} necessary if it
%% can be written as a conic combination of the other vectors in $N$. On
%% the other hand, the set $\big\{ \vx \in \R^n \, | \, \langle \vx, \vn
%% \rangle = 0 \big\}$ for some fixed $\vn \in N$ includes a face of the
%% cone $K$ if and only if $\vn$ is \emph{not} a conic combination of the
%% other vectors in $N$.

%% \begin{remark}
%%   Let us briefly explain why we said that the cone description in
%%   Definition~\ref{def:kernel:representation:of:cone:1} is a ``kernel
%%   representation''. For simplicity, assume that the set $N$ is finite
%%   with $N = \{ \vn^{(1)}, \ldots, \vn^{(m)} \}$. Let $\psi:\ \R^n \to
%%   \R^m:\ \vx \mapsto \vx \Hcone^\tr$ be a linear map where $\Hcone$ is
%%   an $m \times n$-matrix where the $\ell$-th row is the vector
%%   $\vn^{(\ell)}$. The cone $K$ can then be seen as the preimage
%%   (generalized kernel) of $\R_+^m$ under $\psi$:
%%   \begin{align*}
%%     K
%%       &= \psi^{-1}(\R_+^m).
%%   \end{align*}
%% \end{remark}

%% The cones that will be of interest to us are proper cones that have a finite
%% amount of edges and faces: such cones can be described by image and kernel
%% representations using finite sets $E$ and $N$. The following lemma will be
%% crucial for what follows.

%% \begin{lemma}
%%   \label{lemma:from:primal:to:dual:cone:representation:1}
%%   Let $E \defeq \{ \vx^{(1)}, \ldots, \vx^{(k)} \}$ be a set of vectors in
%%   $\R^n$ and let the cone $K$ be given in image representation form, i.e.
%%   \begin{align*}
%%     K
%%       &\defeq
%%          \big\{
%%            \theta_1 \vx^{(1)} + \cdots + \theta_k \vx^{(k)}
%%            \, | \, \theta_1 \geq 0, \ldots, \theta_k \geq 0
%%          \big\}.
%%   \end{align*}
%%   Then the dual cone $K^{*}$ can be written as in kernel representation form,
%%   i.e.
%%   \begin{align*}
%%     K^{*}
%%       &= \big\{
%%            \vx \in \R^n
%%            \, | \, \langle \vx, \vx^{(\ell)} \rangle \geq 0 
%%            \ \forall \ell, 1 \leq \ell \leq k
%%          \big\}.
%%   \end{align*}
%%   On the other hand, if the cone is defined in kernel representation form,
%%   i.e.
%%   \begin{align*}
%%     K
%%       &= \big\{
%%            \vx \in \R^n
%%            \, | \, \langle \vx, \vn^{(\ell)} \rangle \geq 0 
%%            \ \forall \ell, 1 \leq \ell \leq m
%%          \big\}.
%%   \end{align*}
%%   for some set $N \defeq \{ \vn^{(1)}, \ldots, \vn^{(k)} \}$ with vectors from
%%   $\R^n$ then the dual cone $K^{*}$ can be written in image representation
%%   form, i.e.
%%   \begin{align*}
%%     K^{*}
%%       &\defeq
%%          \big\{
%%            \theta_1 \vn^{(1)} + \cdots + \theta_m \vn^{(m)}
%%            \, | \, \theta_1 \geq 0, \ldots, \theta_m \geq 0
%%          \big\}.
%%   \end{align*}
%% \end{lemma}

%% Obviously, any cone $K$ that can be represented by an image
%% representation with a finite set $E$ can also be represented by a
%% kernel representation with a finite set $N$ and vice versa. But note
%% that the number of vectors required in the set $E$ and the number of
%% vectors required in the set $N$ can vary greatly!\footnote{This effect
%% is not really apparent when the number of dimensions $n$ is very
%% small.}  For example, whereas the fundamental cone corresponding to a
%% parity-check matrix $\matr{H}$ of a $(j,k)$-regular code can be
%% described by a set $N$ whose size is $(nj/k) \cdot k = nj$ (i.e., a
%% set whose size grows linearly in $n$), the size of $E$ usually grows
%% exponentially in $n$. From
%% Lemma~\ref{lemma:from:primal:to:dual:cone:representation:1} it is
%% clear that for the dual cone of the fundamental cone the situation
%% concerning the description complexity is reversed.

%% Let $\code{C}$ be a cycle code defined by a parity-check matrix
%% $\matr{H}$ and let $\zeta(u_1, \ldots, u_n)$ be the corresponding zeta
%% function. The inverse zeta function is
%% \begin{align*}
%%   \zeta^{-1}(u_1, \ldots, u_n)
%%     &= \prod_{\vb \in B}
%%          \big(
%%            1 - \vu^\vw(\vb)
%%          \big),
%% \end{align*}
%% where $B$ is the set of backtrackless,....., irreducible walks and
%% $\vw(\vb)$ is the pseudo-codeword of such a walk ($\vu$ and $\vb$ are
%% vectors). We define a new function $\bar \zeta$ through
%% \begin{align*}
%%   \bar \zeta(\lambda_1, \ldots, \lambda_n)
%%     &\defeq 
%%        \zeta(u_1, \ldots, u_n)|_{u_i = \exp(\lambda_i)}
%%       = \zeta(\exp(\lambda_1), \ldots, \exp(\lambda_n)).
%% \end{align*}
%% We easily see that $\bar \zeta^{-1}$ can be written as
%% \begin{align*}
%%   \bar \zeta^{-1}(\lambda_1, \ldots, \lambda_n)
%%     &= \prod_{\vb \in B}
%%          \left(
%%            1 - \exp\big( \langle \vlambda, \vw(\vb) \rangle \big)
%%          \right).
%% \end{align*}
%% Let $P(\bar \zeta)$ be the set of poles of $\bar \zeta(\lambda_1, \ldots,
%% \lambda_n)$, i.e.~$P(\bar \zeta)$ is the set of zeros of $\bar
%% \zeta^{-1}(\lambda_1, \ldots, \lambda_n)$.

%% \begin{theorem}
%%   We use the notation as introduced before this theorem. Let $\fc{K} \defeq
%%   \fch{K}{H}$ be the fundamental cone corresponding to $\matr{H}$ and let
%%   $\fc{K}^{*}$ be its dual cone, then we have
%%   \begin{align*}
%%     \fc{K}^{*} \cap P(\bar \zeta)
%%       &= \boundary \fc{K}^{*},
%%   \end{align*}
%%   where $\boundary S$ is the boundary of a set $S$.
%% \end{theorem}

%% \begin{proof}
%%   It is easy to see that $\vlambda \in P(\bar \zeta)$ if and only if $\langle
%%   \vlambda, \vw(\vb) \rangle = 0$ for some $\vb \in B$, i.e.
%%   \begin{align*}
%%     P(\bar \zeta)
%%       &= \big\{
%%            \vlambda \in \R^n
%%            \, | \, \langle \vlambda, \vw(\vb) \rangle = 0 
%%            \text{ for at least one $\vb \in B$}
%%          \big\}.
%%   \end{align*}
%%   As a side result, the set $P(\bar \zeta)$ equals the set of zeros of the
%%   polynomial $\prod_{\vb \in B} \langle \vlambda, \vw(\vb) \rangle$.
  
%%   But the fundamental cone can be described as $\fc{K} = \conhull(B)$, i.e.~by
%%   an image representation using the set $B$. The dual cone $\fc{K}^{*}$ can
%%   then be written by a kernel representation, i.e.
%%   \begin{align*}
%%     K^{*}
%%       &= \big\{
%%            \vlambda \in \R^n
%%            \, | \, \langle \vlambda, \vw(\vb) \rangle \geq 0 
%%            \ \forall \vb \in B
%%          \big\}.
%%   \end{align*}
%%   Consequently, its boundary can be written as
%%   \begin{align*}
%%     \boundary \fc{K}^{*}
%%       &= \big\{
%%            \vlambda \in \R^n
%%            \, | \, \langle \vlambda, \vb \rangle \geq 0 
%%            \ \forall \vb \in B,
%%            \text{ where equality holds for at least one $\vb \in B$}
%%          \big\}.
%%   \end{align*}
%%   From this it is obvious that the intersection of $\fc{K}^{*}$ and $P(\bar
%%   \zeta)$ yields $\boundary \fc{K}^{*}$.
%% \end{proof}

%% Here are some comments that maybe expanded in the future.
%% \begin{itemize}
  
%% \item Every element $\vb \in B$ induces an edge $\{ \theta \vw(\vb) \, | \,
%%   \theta \geq 0 \}$ of the fundamental cone. (Ralf and Pascal believe this to
%%   be true, although we have not yet written a proof for it.)
  
%% \item Would ``preimage representation'' be preferable to ``kernel
%%   representation''?

%% \item In some sense the zeta function is nothing but the algebraic expression
%%   of the hyperplanes that serve as boundary of the dual cone $\fc{K}^{*}$.
  
%% \item Another interesting connection is that the dual cone is identical to the
%%   decoding region if binary antipodal signalling is used...

%% \end{itemize

cs0502033.extracted_bib
\begin{thebibliography}{1}

\bibitem{Tanner:81}
R.~M. Tanner, ``A recursive approach to low-complexity codes,'' {\em IEEE
  Trans.\ on Inform.\ Theory}, vol.~IT--27, pp.~533--547, Sept. 1981.

\bibitem{Koetter:Vontobel:03:1}
R.~Koetter and P.~O. Vontobel, ``Graph covers and iterative decoding of
  finite-length codes,'' in {\em Proc.\ 3rd Intern.~Conf.~on Turbo Codes and
  Related Topics}, (Brest, France), pp.~75--82, Sept.~1--5 2003.
\newblock Available online under \verb+http://www.ifp.uiuc.edu/~vontobel+.

\bibitem{Feldman:Karger:Wainwright:03:2}
J.~Feldman, D.~R. Karger, and M.~J. Wainwright, ``{LP} decoding,'' in {\em
  Proc.\ 41st Allerton Conf.~on Communications, Control, and Computing},
  (Allerton House, Monticello, Illinois, USA), October 1--3 2003.
\newblock Available online under
  \verb+http://www.columbia.edu/~jf2189/pubs.html+.

\bibitem{nicwi} N. Wiberg, ``Codes and Decoding on General Graphs'', Link\"oping Studies in Science and Technology, 
Ph.D thesis No. 440, Link\"oping, Sweden.
\verb+http://www.it.isy.liu.se/+ \verb+publikationer/LIU-TEK-THESIS-440.pdf+.


\bibitem{Kschischang:Frey:Loeliger:01}
F.~R. Kschischang, B.~J. Frey, and H.-A. Loeliger, ``Factor graphs and the
  sum-product algorithm,'' {\em IEEE Trans.\ on Inform.\ Theory}, vol.~IT--47,
  no.~2, pp.~498--519, 2001.

\bibitem{Hakimi:Bredeson:68:1}
S.~L. Hakimi and J.~Bredeson, ``Graph-theoretic error correcting codes,'' {\em
  IEEE Trans.\ on Inform.\ Theory}, vol.~IT--14, no.~4, pp.~584--591, 1968.

\bibitem{Forney:01:1}
G.~D. {Forney, Jr.}, ``Codes on graphs: normal realizations,'' {\em IEEE
  Trans.\ on Inform.\ Theory}, vol.~47, no.~2, pp.~520--548, 2001.

\bibitem{Massey:77:1}
W.~S. Massey, {\em Algebraic Topology: an Introduction}.
\newblock New York: Springer-Verlag, 1977.
\newblock Reprint of the 1967 edition, Graduate Texts in Mathematics, Vol. 56.

\bibitem{Stark:Terras:96:1}
H.~M. Stark and A.~A. Terras, ``Zeta functions of finite graphs and
  coverings,'' {\em Adv. Math.}, vol.~121, no.~1, pp.~124--165, 1996.

\bibitem{West:96:1}
D.~B. West, {\em Introduction to graph theory}.
\newblock Upper Saddle River, NJ: Prentice Hall Inc., 1996.

\bibitem{Hashimoto:89:1}
K.~Hashimoto, ``Zeta functions of finite graphs and representations of
  {$p$}-adic groups,'' in {\em Automorphic forms and geometry of arithmetic
  varieties}, vol.~15 of {\em Adv. Stud. Pure Math.}, pp.~211--280, Boston, MA:
  Academic Press, 1989.

%\end{thebibliography}