% %You can use \\ for explicit line-break An Efficient Joint Source-Channel Decoder with Dynamical Block Priors%
% %Use \scshape for the family name Ido \textsc{Kanter}
Haggai \textsc{Kfir} and Shahar \textsc{Keren} %
kanter_kfir_keren.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%   template.tex for PTPTeX.cls <ver.0.9>  %%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[seceq,supplement]{ptptex}
%\documentclass[letter]{ptptex}
%\documentclass[seceq,supplement]{ptptex}
%\documentclass[seceq,addenda]{ptptex}
%\documentclass[seceq,errata]{ptptex}
%\documentclass[seceq,preprint]{ptptex}

\usepackage{graphicx}
\usepackage{wrapft}

%%%%% Personal Macros %%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\pubinfo{Vol.~11X, No.~X, Mmmmm YYYY}%Editorial Office will fill in this.
%\setcounter{page}{}                  %Editorial Office will fill in this.
%\def\ptype{p}                        %Editorial Office will fill in this.
%\def\ptpsubject{}                    %Editorial Office will fill in this.
%\def\pageinfo{X-X}                   %Editorial Office will fill in this.
%-------------------------------------------------------------------------
%\nofigureboxrule                     %to eliminate the rule of \figurebox
%\notypesetlogo                       %comment in if to eliminate PTPTeX
%---- When [preprint] you can put preprint number at top right corner.
%\preprintnumber[3cm]{%<-- [..]: optional width of preprint # column.
%KUNS-1325\\PTPTeX ver.0.8\\ August, 1997}
%-------------------------------------------------------------------------

\markboth{%     %running head for odd-page (authors' name)
I. Kanter, H. Kfir and S. Keren%
}{%             %running head for even-page (`short' title)
JSC Decoder with Dynamical Block Priors%
}

\title{%        %You can use \\ for explicit line-break
An Efficient Joint Source-Channel Decoder with Dynamical Block Priors%
}

%\subtitle{Subtitle}    %use this when you want a subtitle

\author{%       %Use \scshape  for the family name
Ido \textsc{Kanter}, Haggai \textsc{Kfir} and  Shahar \textsc{Keren} %
}

\inst{%         %Affiliation, neglected when [addenda] or [errata]
Minerva Center and Department of Physics, Bar-Ilan University
Ramat-Gan, 52900 Israel }

%\publishedin{%         %Write this ONLY in cases of addenda and errata
%Prog.~Theor.~Phys.\ \textbf{XX} (19YY), page.}

%\recdate{Mmmmm DD, YYYY}%            %Editorial Office will fill in this.

\abst{%         %this abstract is neglected when [addenda] or [errata]
An efficient joint source-channel (s/c) decoder based on the side
information of the source and on the MN-Gallager algorithm over
Galois fields is presented. The dynamical block priors (DBP) are
derived either from a statistical mechanical approach via
calculation of the entropy for the correlated sequences, or from
the Markovian transition matrix. The Markovian joint s/c decoder
has many advantages over the statistical mechanical approach. In
particular, there is no need for the construction and the
diagonalization of a $q \times q$ matrix and for a solution to
saddle point equations in $q$ dimensions. Using parametric
estimation, an efficient joint s/c decoder with the lack of side
information is discussed. Besides the variant joint s/c decoders
presented, we also show that the available sets of
autocorrelations consist of a convex volume, and its structure can
be found using the Simplex algorithm.

}

\begin{document}

\maketitle

\section{Introduction}
Source coding is a process for removing redundant information from
the source information symbol stream. Channel coding is a procedure
for adding redundancy as protection into the information stream
which is to be transmitted. During the last decade engineers and
also physicists have designed efficient error correction techniques
such as Low-Density-Parity-Check-Codes (LDPC)\citen{Cover,Gallager}
or Turbo codes, that nearly saturate Shannon's limit.


The Shannon separation theorem states that source coding
(compression) and channel coding (error protection) can be performed
separately and sequentially, while maintaining optimality
\citen{Shannon,Cover}. However, this is true only in the case of
asymptotically long block lengths of data and point-to-point
transmission. In many practical applications, the conditions of the
Shannon's separation theorem neither hold, even approximatly. Thus,
considerable interest has developed in various schemes of joint
source-channel (s/c) coding, where compression and error correction
are combined into one mechanism.
% (see, for instance, the following selected
%publications
%\cite{shamail1,shamail2,shamail3,shamail4,shamail5,shamail6}).

The paper is organized as follows. In Section 2, Statistical
Mechanical (SM) methods are used to explore properties of
correlated sequences. In section 3, the space of possible sets of
autocorrelations is investigated. In sections 4 Mackay and Neal's
(MN) algorithm for error correction is briefly introduced, and the
results of section 2 are used to extend this algorithm to a joint
s/c scheme. The estimation of the threshold of the code using the
scaling argument for the convergence time is presented in section
5. Section 6 presents simulation results, and compares joint to
separation schemes. In Sections 7 and 8, the joint s/c problem is
attacked from a different point of view, a Markovian approach, and
an efficient joint scheme \emph{with the lack of side information}
is demonstrated.

%The paper is organized as follows. In Section II Statistical
%Mechanical (SM) joint s/c coding is introduced, whereas in Section
%III the threshold of the code is calculated using scaling behavior
%for the required number of messages passing for the convergence of
%the algorithm \cite{KS,KS-Gaussian,KK}. In Section IV the
%efficiency of the SM joint s/c coding is compared to various
%separation schemes. A degradation in the performance of the SM
%joint s/c coding is examined in Section V as a function of the
%spectrum of the eigenvalues of the transfer matrix. In Section VI
%the Simplex algorithm is used to calculate the available space of
%a possible set of autocorrelations. The drawbacks of the SM joint
%s/c coding are discussed in Section VII, and advanced s/c coding
%is presented in Section VIII. The Markovian joint s/c coding and
%its efficiency are discussed in Section IX. Based on the
%parametric estimation methods the Markovian joint s/c decoder with
%the lack of side information is discussed in Section X.  Its
%extension to higher dimensions is discussed in Section XI. The
%paper closes with some concluding remarks.




\section{Joint s/c coding - Statistical Mechanical approach}

In our recent papers\citen{KR,KK} a particular scheme based on a SM
approach for the implementation of the joint s/c coding was
presented and the main steps are briefly summarized below.  The
original boolean source is first mapped to a binary source
\citen{sourlas} $\left\{ x_{i}=\pm1\right\} ~i=1,...,L$, and is
characterized by a finite set of autocorrelations bounded by the
length $k_0$
\begin{equation}
C_{k_1, ...,k_m}=\frac{1}{L}\sum_{i=1}^{L}x_{i}\prod_{j=0}^m
x_{\left(i+k_j\right)\: \mathbf{mod}\: L} \label{ck}
\end{equation}
\noindent where $k_m \le k_0$ is the highest length autocorrelation
taken and the total number of possible different autocorrelations is
$2^{k_0}$.  For $k_0=2$, for instance, there are only $4$ possible
correlations, $C_0$, $C_1$, $C_2$ and $C_{12}$, and for $k_0=3$
there are $8$ possible different correlations;
$C_0,~C_1~,C_2,~C_3,~C_{12},~C_{13},~C_{23},~C_{123}$, where we do
not assume left-right symmetry for the source.  Note that for
general $k_0$ and $m=1$, Eq. (\ref{ck}) reduces to the two-point
autocorrelation function \citen{liat}. The number of sequences
obeying these $2^{k_0}$ constraints is given by
\begin{equation}
\Omega = Tr_{\{ x_i = \pm 1 \} }\!\!\!\!
\prod_{\{k_1,k_2,...,k_m\}}\!\!\!\!\! \delta
(\sum_{i=1}^{L}x_{i}\prod_{j=0}^m x_{i+k_j} - LC_{k_1, ...,k_m})
\label{omega}
\end{equation}
\noindent where $m=0$ stands for $C_0$. Using the integral
representation of the delta functions, Eq. (\ref{omega}) can be
written as
\begin{eqnarray}
\Omega \!\!=\!\!\!\! \int\!\!\!\! \prod_{\{k_1,..,k_m\}}
\!\!\!\!\!\!\!dy_{\{k_1,..,k_m\}} \exp(\sum
\!\!-y_{k_1,..,k_m}C_{k_1,..,k_m}) Tr \exp
(\!\!\!\sum_{k_1,..,k_m} \!\!\!\!y_{k_1,...,k_m}\!\!\!\sum_{i}
\!x_{i}\prod_{j=0}^m \!x_{i+k_j} )\nonumber \label{omega1}
\end{eqnarray}
Since $k_j \le k_0$, the last term of this equation indicates that
the trace can be performed using the standard transfer matrix (of
size $2^{k_0} \times 2^{k_0}$) method\citen{baxter}. More precisely,
assume two successive blocks of $k_0$ binary variables denoted by
$(x_1,...,x_{k_0})$ and $(x_{k_0+1},...  ,x_{2k_0})$. The element
$(i,j)$ of the transfer matrix is equal to the value of the last
exponential term (on the r.h.s of the trace), where the first block
is in state $i$ (among $2^{k_0}$ possible states) and the second
block is in state $j$. The transfer matrix is a non-negative matrix
(as long as the $y_{k_1,...,k_m}$ are real numbers), and the leading
eigenvalue is positive and non-degenerate\citen{baxter}. In the
leading order one finds
\begin{eqnarray}
\Omega =\int dy_k\exp\{-L\lbrack \sum
y_{k_1,...,k_m}C_{k_1,...,k_m}  - \ln \lambda_{max}(\{
y_{k_1,...,k_m}\}) \rbrack \} \label{omega-sp}
\end{eqnarray}
\noindent where $\lambda_{max}$ is the maximal eigenvalue of the
corresponding transfer matrix.  For large $L$ and using the saddle
point method, the entropy, $H_2(\{C_{k_1,...,k_m} \})$, is given
in the leading order by
\begin{eqnarray}
H_2\left(\{C_{k_1...,k_m}\}\right) = {1 \over \ln 2} \lbrack
\frac{1}{k_0}\ln \lambda_{max}\left (\{ y_{k_1,...,k_m}\}\right)
-\sum_{k_1,...,k_m}^{k_0}y_{k_1,...,k_m} C_{k_1,...,k_m} \rbrack
\label{entropy-ck} \label{h2}
\end{eqnarray}
\noindent where $\{y_{k_1,...,k_m}\}$ are determined from the saddle
point equations of $\Omega$ \citen{KR,KK}. Assuming a Binary
Symmetric Channel (BSC) and using Shannon's lower bound, the channel
capacity of sequences with a given set of autocorrelations bounded
by a distance $k_0$ is given by
\begin{equation}
C=\frac{1-H_{2}\left(f\right)}{H_{2}(\left\{C_{k_1,...,k_m}\}\right)-
H_{2}\left(P_{b}\right)} \label{capacity}
\end{equation}
\noindent where $f$ is the channel bit error rate and $p_b$ is a
bit error rate.  The saddle point solutions derived from Eq.
 (\ref{h2}) indicate that the equilibrium properties of the
one-dimensional Ising spin system ($x_i=\pm1$) with up to order
$k_0$ multi-spin interactions\citen{ido-msi}
\begin{equation}
H=-\sum_i \sum_{k=1}^{k_0} \frac{y_{k_1,...,k_m}}{\beta }
x_{i}\prod_{j=0}^m x_{i+k_j} \label{hamiltonian}
\end{equation}
\noindent obey in the leading order the autocorrelation
constraints, Eq. (\ref{ck}).  This property of the effective
Hamiltonian, Eq. (\ref{hamiltonian}), is used in simulations to
generate an ensemble of signals (source messages) with the desired
set of autocorrelations. {\it Note that in the following we choose
$\beta=1$, and hence we denote $\{y_{k_1,...,k_m}\}$ as
interactions.}

\section{ Possible sets of autocorrelations and the Simplex algorithm}

The entropy of correlated sequences can be calculated from Eq.
 (\ref{h2}).  For the simplest case of sequences obeying only $C_1$
and $C_2$ the numerical solution of the saddle point equations
indicate that the entropy is positive only in the regime
\begin{equation}
-(1+C_2)/2 \le C_1 \le (1+C_2)/2 \label{c1c2}
\end{equation}
\noindent where outside of this regime the entropy is zero. At the
boundaries, $C_1=|(1+C_2)/2|$, two phenomena are observed: (a) the
entropy falls abruptly to zero at the boundary, and (b) $y_1$ and
$-y_2$ diverge at the boundary (the one-dimensional Hamiltonian, Eq.
(\ref{hamiltonian}) consists of frustrated loops).

These limited results obtained from the numerical solutions of the
saddle point equations suffer from the following limitations: (a)
finding the boundaries of the region in the space of
$\{C_{k_1,...,k_m}\}$ with a finite entropy is very sensitive to
the numerical precision since on the boundary the $\{|y_i|\}$
diverge; (b) it is unclear whether the available space consists of
a connected regime; (c) the question of whether out of the space
with a finite entropy, there are a finite or infinite number of
sequences (for instance  $e^{\sqrt{L}}$) obeying the set of
autocorrelations cannot be answered using the saddle point method;
(d) extension of the saddle point solutions to identify the
boundaries of the finite entropy regime to many dimensions is a
very heavy numerical task.

%and answer the above questions
To overcome these difficulties, we show below how the possible sets
of autocorrelations can be identified using the Simplex algorithm.


For the case of only two constraints $C_1$ and $C_2$, for instance,
following the methodology of the transfer matrix, let us concentrate
on four successive binary variables $S_i,S_{i+1},S_{i+2},S_{i+3}$,
where $S_i=\pm 1$. Since the Hamiltonian, Eq. (\ref{hamiltonian}),
obeys in this case an inversion symmetry, let us examine only the
$8$ configurations out of $16$ where $S_3=-$, $(\pm\pm-\pm)$. For
these $8$ configurations one can assign the following marginal
probabilities, $P_{\pm\pm-\pm}$, where each probability stands for
the fraction of sequences obeying $C_1$ and $C_2$ with a given state
for these four successive binary variables. In the SM language we
measure the probabilities of these four states in thermal
equilibrium of the micro-canonical ensemble obeying Eq.  (\ref{ck}).
It is clear that the Hamiltonian, Eq. (\ref{hamiltonian}), is
translationally invariant, $P(S_i,S_{i+1},S_{i+2},S_{i+3})$ is
independent on $i$ after averaging over all sequences obeying
constraints (\ref{ck}).


For these $8$ marginal probabilities one can write the following
$14$ equations:

\begin{eqnarray}
&P&_{---+}+P_{----}+P_{++-+}+P_{++--}-P_{-+-+}-P_{-+--}-P_{+--+}-P_{+---}=C_1/2\nonumber\\
&P&_{---+}+P_{----}+P_{+---}+P_{+--+}-P_{-+-+}-P_{-+--}-P_{++--}-P_{++-+}=C_1/2\nonumber\\
&P&_{-+--}+P_{----}+P_{+---}+P_{++--}-P_{-+-+}-P_{---+}-P_{+--+}-P_{++-+}=C_1/2\nonumber\\
&P&_{---+}+P_{----}+P_{-+--}+P_{-+-+}-P_{+--+}-P_{+---}-P_{++--}-P_{++-+}=C_2/2\nonumber\\
&P&_{----}+P_{-+-+}+P_{+---}+P_{++-+}-P_{---+}-P_{-+--}-P_{+--+}-P_{++--}=C_2/2\nonumber\\
&P&_{----}+P_{---+}+P_{-+--}+P_{-+-+}+P_{+---}+P_{+--+}+P_{++--}+P_{++-+}=1/2\nonumber\\
%&P&(-,-,+)+P(-,-,-)-P(+,-,+)-P(+,-,-)=C_1/2 \nonumber\\
%&P&(+,-,-)+P(-,-,-)-P(+,-,+)-P(-,-,+)=C_1/2  \nonumber\\
%&P&(-,-,+)+P(-,-,-)+P(+,-,+)+P(+,-,-)=1/2  \nonumber\\
%&P&(+,-,+)+P(-,-,-)-P(+,-,-)+P(-,-,+)=C_2/2  \nonumber\\
&0& \le P_{\pm\pm-\pm} \le 1 \label{simplex12}
\end{eqnarray}

\noindent For a given $C_1$, these $14$ equations can be solved for
the minimum and the maximum available $C_2$ using the Simplex
method. Running over values of $-1 \le C_1 \le 1$, we indeed recover
the result of Eq. (\ref{c1c2}). However, the {\it Simplex solution
indicates the lack of even a finite number of sequences beyond the
regime with finite entropy}. Hence, a simple geometrical calculation
obeying constraint \ref{c1c2} indicates that the fraction of the 2D
space (-1:1,-1:1) of $(C_1,C_2)$ with available sequences is $1/2$.


For the case of three constraints, $C_1, C_2$ and $C_3$, one can
similarly write  $45$ equalities and inequalities for the $32$
probabilities of $6$ successive binary variables
$P_{\pm\pm\pm\pm-\pm}$. For a given $C_1$ and $C_2$, these $45$
equations and inequalities can be solved for the minimum and the
maximum available $C_3$ using the Simplex method. The Simplex
solution indicates: (a) the solution space in the three-dimensional
box $(-1:1,-1:1,-1:1)$ for $(C_1,C_2,C_3)$ is a connected region
bounded by a few planes. This result is consistent with the solution
obtained from Eqs. (\ref{omega-sp},\ref{h2}); (b) the fraction of
the volume of the box obeying the three constants is $\sim 0.222$.
Preliminary results indicate that for $4$ ($C_i,~i=1,2,3,4$) and $5$
($C_i,~i=1,2,3,4,5$) constraints the available volume is $\sim
0.085,~0.034$, respectively.

The fraction of possible sets of autocorrelations appears  to
decrease as the number of constraints increases. However, the
question of whether the fraction of available autocorrelations
drops exponentially with the number of constraints as well as its
detailed spatial shape is the subject of our current research.

We conclude the discussion in this section with the following
general result. The available volume for the general case of $q$
constraints $\{C_{k_1,...,k_m}\}$, $k_m<\log_2(q)$, is convex. The
main idea is that one can verify that the set of equalities can be
written in a matrix representation in the following form
\begin{equation}
{\bf M} P = C \label{manfred}
\end{equation}
\noindent where ${\bf M}$ is a matrix with elements $\pm 1$; $P$
represents the marginal probabilities $P(\pm,\pm,....)$ and $C$
represents the desired correlations or a normalization constant (for
instance $C_1/2$, $C_2/2$ and $1/2$, for the case of Eq.
(\ref{simplex12})). The inequalities force the probabilities into
the range $\lbrack 0:1\rbrack$. Clearly if $P_1(\pm,\pm,...)$ and
$P_2(\pm,\pm,...)$ are two sets of probabilities obeying Eq.
 (\ref{manfred}) then
\begin{equation}
\lambda P_1+(1-\lambda)P_2 \label{convex}
\end{equation}
\noindent is also a solution of the set of the equalities ($0 \le
\lambda \le 1$).  Hence, the available volume is convex.


%\onecolumn



%\begin{eqnarray}
%&P&(+,+,-,+)+P(+,+,-,-)+P(-,-,-,+)+P(-,-,-,-)  \nonumber \\
%-&P&(+,-,-,+)-P(+,-,-,-)-P(-,+,-,+)- P(-,+,-,-)=C_1/2 \nonumber \\
%&P&(+,-,-,+)+P(+,-,-,-)+P(-,-,-,+)+P(-,-,-,-) \nonumber \\
%-&P&(+,+,-,+)-P(+,+,-,-)-P(-,+,-,+)-P(-,+,-,-)=C_1/2 \nonumber \\
%&P&(+,+,-,-)+P(+,-,-,-)+P(-,+,-,-)+P(-,-,-,-) \nonumber \\
%-&P&(+,+,-,+)-P(+,-,-,+)-P(-,+,-,+)-P(-,-,-,+)=C_1/2 \nonumber \\
%&P&(-,+,-,+)+P(-,+,-,-)+P(-,-,-,+)+P(-,-,-,-) \nonumber \\
%-&P&(+,+,-,+)-P(+,+,-,-)-P(+,-,-,+)-P(+,-,-,-)=C_2/2 \nonumber \\
%&P&(+,+,-,+)+P(+,-,-,-)+P(-,+,-,+)+P(-,-,-,-)  \nonumber \\
%-&P&(+,+,-,-)-P(+,-,-,+)-P(-,+,-,-)-P(-,-,-,+)=C_2/2 \nonumber \\
%&P&(+,+,-,+)+P(+,-,-,+)+P(-,+,-,-)+P(-,-,-,-) \nonumber \\
%-&P&(+,+,-,-)-P(+,-,-,-)-P(-,+,-,+)-P(-,-,-,+)=C_3/2 \nonumber \\
%&P&(+,+,-,+)+P(+,-,-,-)+P(-,+,-,+)+P(-,-,-,-) \nonumber \\
%+&P&(+,+,-,-)+P(+,-,-,+)+P(-,+,-,-)+P(-,-,-,+)=1/2 \nonumber \\
%&0& \le P(\pm,\pm,-,\pm) \le 1 \label{simplex123}
%\end{eqnarray}
%\twocolumn


%%%%%%%%%%%%%%%%%%

\section{Joint s/c decoder: Statistical Mechanical approach}
The transfer matrix method indicates that the relevant scale of the
correlated source message is $k_0$.  Hence, our encoding/decoding
procedure is based on the MN code for a finite field $q=2^{k_0}$
\citen{LDPC-GF(q)}, which is based on the construction of two sparse
matrices $A$ and $B$ of dimensionalities $(L_0/R)\!\times\! L_0$ and
$(L_0/R)\! \times\! (L_0/R)$ respectively, where $R$ is the
code-rate and the number of symbols in the source is $L_0=L/k_0$.
The matrix $B^{-1}A$ is then used for encoding the message
\begin{equation}
t = B^{-1}A x\  (\: \mathbf{mod}\:\ \ q) \label{trans}
\end{equation}
The finite field message vector $t$ is mapped to a binary vector
and then transmitted. The received message, $r$, is corrupted by
the channel bit error rate, $f$.


The decoding of symbols of $k_0$ successive bits (named in the
following as a {\it block} of bits or binary variables) is based
on the solution of the syndrome
\begin{equation}
Z= Br = Ax + Bn\   (\: \mathbf{mod}\:\ \ q) \label{decoding}
\end{equation}
\noindent where $n$ stands for the corresponding noise of $k_0$
successive bits.  The solution of the $L_0/R$ equations with
$L_0(1/R+1)$ variables is based on the standard message passing
algorithm introduced for the MN decoder over Galois fields with
$q=2^{k_0}$\citen{LDPC-GF(q)} and with the following modification.
The horizontal pass is left unchanged, {\it but a dynamical set of
probabilities assigned for each block is used in the vertical pass}.
The Dynamical Block Probabilities (DBP), $\{P_n^c\}$, are determined
following the current belief regarding the neighboring blocks and
are given by
\begin{eqnarray}
\gamma_{n}^{c}  =  S_{I}\left(c\right)\left(\sum
_{l=1}^{q}q_{L}^{l}S_{L}\left(l,c\right)\right)\left(\sum
_{r=1}^{q}q_{R}^{r}S_{R}\left(c,r\right)\right)  ~~~~ ;~~~~
P_{n}^{c} = \frac{\gamma _{n}^{c}}{\sum _{j=1}^{q}\gamma
_{n}^{j}}\label{tm-vertical-pass} \label{dbp}
\end{eqnarray}
\noindent where $l/r/c$ denotes the state of the left/right/center
($n\!-\!1\,/\,n\!+\!1\,/\,n$) block respectively and
$q_{L}^{l}/q_{R}^{r}$ are their posterior probabilities.
$S_I(c)=e^{-\beta H_I}$ stands for the Gibbs factor of the inner
energy of a block ($k_0$ successive binary variables spins),
characterized by an energy $H_I$ at a state $c$, see Eq.
 (\ref{hamiltonian}).
%$S_I(c)=e^{-\beta H_I}$,
%where $H_I$ is the inner energy of a block of $k_0$ spins at a state
%$c$, see eq. 6.
Similarly $S_L(l,c)$ ($S_R(c,r)$) stands for the Gibbs factor of
consecutive Left/Center (Center/Right) blocks at a state $l,c$
$(c,r)$ \citen{KK,KR}. The complexity of the calculation of the
block prior probabilities is $O(Lq^2/ \log q)$ where $L/\log q$ is
the number of blocks.  The decoder complexity per iteration of the
MN codes over a finite field $q$ can be reduced to order
$O(Lqu)$\citen{David-Mackay1}, where $u$ stands for the average
number of checks per block.  Hence the total complexity of the DBP
decoder is of the order of $O(Lqu+Lq^2/ \log q)$.

%\begin{wrapfigure}{r}{6.6cm} % r: RIGHT, 6.6cm: WIDTH
%\includegraphics[width=2.5in]{figs/layer_graph_BW.eps}
%\caption{A message passing in the SM joint s/c decoder is
%represented by a graph with the following three layers.  The check
%blocks are represented by full squares, the full/open circles
%denote source/noise block variables and the open diamonds denote
%the calculators for the dynamical block posterior probabilities
%for the source block variables. Each one of these calculators
%receives an input message from its two neighbors (module $L_0$)
%and sends its output message to its block.  }
%\label{message-passing}
%\end{wrapfigure}

\begin{figure}[htb]
\parbox{\halftext}{% %\def\halftext{.471\textwidth}
\includegraphics[width=2.0in]{layer_graph_ptp.eps}
\caption{A message passing in the joint s/c decoder is represented
by a bipartite graph with an additional
layer.}\label{message-passing}} \hfill
\parbox{\halftext}{
\includegraphics[width=2.5in]{KSconstruction_L0_1.eps}
\caption{The structure of the matrices $A$ and $B$ for the MN
decoder taken from reference\citen{KS}, for rate $1/3$. The black
dots (area) denote the non-zero elements of the matrices
$A,~B,~B^{-1}$. } \label{ks}}
\end{figure}


Another way to represent the dynamical behavior of the SM joint
s/c decoder is in the framework of message passing on a graph
(Fig. \ref{message-passing}). Typically for LDPC, the graph is
bipartite and consists of variable nodes (circles) and check nodes
(squares). For the MN algorithm, there are two types of variable
nodes: source nodes (filled circles) and noise nodes (open
circles). A message from variables to checks is a horizontal pass,
and a message from checks to variables is a vertical pass. In the
joint s/c decoder there is a {\it third} layer (diamonds): each
element in this layer sends a message (outbound arrow) to a single
source variable (namely, the dynamical block prior), and receives
two messages (inbound arrows) from the neighboring source
variables (namely their a-posteriori probabilities).

%\begin{wrapfigure}{r}{8.6cm} % r: RIGHT, 6.6cm: WIDTH
%\includegraphics[width=3.0in]{figs/KSconstruction_L0_1.eps}
%\caption{The structure of the matrices $A$ and $B$ for the MN
%decoder taken from reference cite{KS}, for rate $1/3$. The black
%dots (area) denote the non-zero elements of the matrices
%$A,~B,~B^{-1}$ } \label{ks}
%\end{wrapfigure}



For simplification of the discussion below, in almost all of the
simulation results we concentrate on rate $1/3$ and the construction
of the matrices $A$ and $B$ follow reference \citen{KS} which is
sketched in Fig. \ref{ks}. The advantage of this construction is
that the matrices $A$ and $B$ are very sparse, but the threshold of
the code for large blocks is only $1-3\%$ of the channel
capacity\citen{KS,KS-Gaussian}. Furthermore, since $B$ has a
systematic structure, the complexity of the encoder scales linearly
with $L$ although $B^{-1}$ is dense\citen{saad,saad1}. Of course,
codes with higher thresholds exist, hence the performance of the
joint s/c algorithm reported below should be interpreted as a lower
bound. (Results for a limited example with rate greater than one,
$R>1$, are briefly discussed in reference \citen{r89})


We conclude this section with the comment that the possibility of
the SM joint s/c algorithm in the framework of the MN-Gallager
decoder to the Gallager decoder\citen{Gallager} is in question. In
the Gallager decoder we first solve $L_0(1/R-1)$ equations for the
noise variables, and only in the final step is the message
recovered. Since the noise is not spatially correlated, we do not
see a simple way to incorporate in the Gallager case the side
information about the spatial correlations among the message
variables. The equivalence between these two (MN-Gallager and
Gallager) similar decoders therefor also in doubt.


%\begin{wrapfigure}{r}{6.6cm} % r: RIGHT, 6.6cm: WIDTH
%\includegraphics[width=2.5in,height=2.5in,angle=270]{figs/msi_pb_f.eps}
%\caption{Simulation results for rate $R=1/3$, $L=10,000$, $q=4$
%and $8$. Each point was averaged over at least $1,000$ source
%messages with the desired set of autocorrelations. (refer to text
%for description)} \label{msi_pb}
%\end{wrapfigure}



For illustration, in Fig. \ref{msi_pb} we present results for rate
$R=1/3$, $L=10,000$, $q=4$ and $8$ where the decoding is based on
the dynamical block posterior probabilities, Eq. (\ref{dbp}), and
with the following parameters. For $q=4$ (open circles)
$C_1=0.55,~C_2=0.5,~C_{12}=0.4$
($y_1=0.275,~y_2=0.291,~y_{12}=0.149$) and $H_2=0.683$. Shannon's
lower bound, Eq. (\ref{capacity}), is denoted by the double dotted
line, where for $p_b=0$ the channel noise level is $f_c=0.227$. For
$q=8$ (open diamonds) $C_1=0.77,~C_2=0.69,~C_3=0.56,~C_{123}=0.7$
($y_1=0.349,~y_2=0.36,~y_3=-0.211,~y_{123}=0.443$) and $H_2=0.453$.
Shannon's lower bound is denoted by the dashed line, where for
$p_b=0$ the channel noise level is $ f_c=0.275$.  Each point was
averaged over at least $1,000$ messages. These results for both
$q=4$ and $8$ indicate that the threshold of the presented decoder
with $L=10,000$ is $\sim 15\%-20\%$ below the channel capacity for
infinite source messages. It is worth mentioning, that without using
the dynamical block priors, Eq. (\ref{dbp}), the decoder fails to
decode at $f_c=\sim 0.13-0.14$.

\begin{figure}[htb]
\parbox{\halftext}{% %\def\halftext{.471\textwidth}
\includegraphics[height=2.5in, angle=270]{msi_pb_f.eps}
\caption{Simulation results for rate $R=1/3$, $L=10,000$, $q=4$
and $8$. Each point was averaged over at least $1,000$ source
messages with the desired set of autocorrelations. (refer to text
for description)} \label{msi_pb} }
 \hfill
\parbox{\halftext}{
\includegraphics[width=2.0in,height=2.0in,angle=270]{gf4_different_L.eps}
\caption{The flip rate $f$ as a function of $1/t_{med}$ for
$GF(4)$ with $C_1=C_2=0.8$ and $L=1,000,~5,000~,50,000$.  The
lines are a result of a linear fit. The threshold, $f_{\infty}
\sim 0.272$, extrapolated from the scaling behavior Eq.
(\ref{scaling}), is independent of $L$.  } \label{different_N} }
\end{figure}





\section{The threshold of the code}


% Although without any \emph{practical} importance, $f_{\infty}$, the threshold of the
% code for infinitely large sequences ($L\rightarrow\infty$), is an
% interesting property. since LDPC codes are known to suffer from finite size effects,
%$f_\infty$ enables one to compar the performance among different
%field size (Note that the system size (i.e. $L$) shrinks
%considerably when moving to higher fields). As was demonstrated
%for $GF(2)$\cite{KS,KS-Gaussian} , $f_\infty$ is efficiently
%calculated using the scaling property for the convergence time
%$t$:
%\begin{equation}\label{scaling}
%    t_{med}\propto\frac{1}{f_\infty-f(t)}.
%\end{equation}
%by monitoring the median of the convergence time, $t_{med}(f)$ (in
%iterations), at different noise levels, $f_\infty$ is found by a
%linear fit. This method is demonstrated in Fig. \ref{different_N}.
%Note that $f_{\infty}$ is independent of $L$, hence, this
%estimation can be done with moderate computation effort.



%
%An interesting question is to measure the efficiency of the
%decoder, eq. \ref{dbp}, as a function of the maximal correlation
%length taken $k_0$, the strength of the correlations, the size of
%the finite fields $q$ and to compare the efficiency with the
%separation schemes.  A direct answer to the questions raised is to
%implement exhaustive simulations on increasing source length,
%various finite fields $q$, and sets of autocorrelations, which
%result in the bit error probability versus the flip rate $f$.
%Besides the enormous computational time required, the conclusions
%would be controversial since it is unclear how to compare, for
%instance, the performance as a function of $q$; with the same
%number of transmitted blocks or with the same number of
%transmitted bits.
%



The threshold $f_c$ for $L \rightarrow  \infty $ is estimated from
the scaling argument of the convergence time, which was previously
observed for $q=2$\citen{KS,KS-Gaussian}.  The median convergence
time, measured in iterations of the MN algorithm, is assumed to
diverge as the level of noise approaches $f_c$ from below. More
precisely, we found that the scaling for the divergence of $t_{med}$
is {\it independent of $q$} and is consistent with:
\begin{equation}
t_{med} = {A \over f_c-f} \label{scaling}
\end{equation}
\noindent where for a given set of autocorrelations and $q$, $A$ is
a constant. Moreover, for a given set of autocorrelations and a
finite field $q$, the extrapolated threshold $f_c$ is independent of
$L$, as demonstrated in Fig. \ref{different_N}.  This observation is
essential to determine the threshold of a code based on the above
scaling behavior. Note that the estimation of $t_{med}$ is a simple
computational task in comparison with the estimation of low bit
error probabilities for large $L$, especially close to the
threshold. We also note that the analysis is based on $t_{med}$
instead of the \emph{average} number of iterations,
$t_{av}$,\citen{KS} since we wish to prevent the dramatic effect of
a small fraction of finite samples with slow convergence or no
convergence.\citen{median} We note that preliminary results
indicates that for a given $\{C_k\}$, $f_c(q)$ appears
asymptotically to be consistent with $f_c(q) \sim f_c -const/q$.


%\begin{wrapfigure}{r}{6.6cm}% r: RIGHT, 6.6cm: WIDTH
%\includegraphics[width=2.5in, angle=270]{figs/gf4_different_L.eps}
%\caption{The flip rate $f$ as a function of $1/t_{med}$ for
%$GF(4)$ with $C_1=C_2=0.8$ and $L=1,000,~5,000~,50,000$.  The
%lines are a result of a linear fit. The threshold, $f_{\infty}
%\sim 0.272$, extrapolated from the scaling behavior eq.
%\ref{scaling}, is independent of $L$.  } \label{different_N}
%\end{wrapfigure}




%All simulation results presented below are derived for rate $1/3$
%and the construction of the matrices $A$ and $B$ of the MN code
%are taken from \cite{KS}. In all examined sets of
%autocorrelations, $10^3 \le L \le 5\!\times\!10^4$ and $4 \le q
%\le 64$, the scaling for the median convergence time was indeed
%recovered. For illustration, in Fig. 5, we present the scaling
%behavior for the amount of message passing for the two examined
%cased presented in Fig. 3. (Note that this decoder can be extended
%to rate $R>1$ and results for a limited example are presented in
%reference \cite{r89})


\section{Comparison between joint and separation schemes}


Results of simulations for $q=4,~8,~16$ and $32$ and selected sets
of autocorrelations are summarized in Table I (Fig. \ref{t1}) and
the definition of the symbols is: $\{C_k\}$ denotes the imposed
values of two-point autocorrelations as defined in eqs.  \ref{ck}
and \ref{omega}; $\{y_k\}$ are the interactions strengths, Eq.
 (\ref{hamiltonian}); $H$ represents the entropy of sequences with
the given set of autocorrelations, Eq. (\ref{entropy-ck}); $f_c$ is
the estimated threshold of the MN decoder with the DBP derived from
the scaling behavior of $t_{med}$, Eq. (\ref{scaling}); $f_{Sh}$ is
Shannon's lower bound, Eq. (\ref{capacity}); Ratio is the efficiency
of our code, $f_c/f_{Sh}$; $Z_R$ indicates the gzip compression rate
averaged over files of the sizes $10^5-10^6$ bits with the desired
set of autocorrelations. We assume that the compression rate with
$L=10^6$ achieves its asymptotic ratio, as was indeed confirmed in
the compression of files with different $L$; $1/R^{\star}$ indicates
the ideal (minimal) ratio between the transmitted message and the
source signal after implementing the following two steps:
compression of the file using gzip and then using an {\it ideal
optimal encoder/decoder}, for a given BSC with $f_c$.  A number
greater than (less than) $3$ in this column indicates that the MN
joint s/c decoder is more efficient (less efficient) in comparison
to the channel separation method using the standard gzip
compression.  The last four columns of Table I (Fig. \ref{t1}) are
devoted to the comparison of the presented joint s/c decoder with
advanced compression methods. $PPM_R$ and $AC_R$ represent the
compression rate of files of the size $10^5-10^6$ bits with the
desired autocorrelations using the Prediction by Partial
Match\citen{PPM} and for the Arithmetic Coder\citen{AC},
respectively. Similarly to the gzip case, $1/R_{PPM}$ and $1/R_{AC}$
denote the optimal (minimal) rate required for the separation
process (first a compression and then an ideal optimal
encoder/decoder) assuming a BSC with $f_c$.


\begin{figure}
\centering
\includegraphics[width=5.75in]{gf4_table.ppm1.eps}
%\centerline{\epsfxsize=5.75in \epsffile{2/gf4_table.ppm1.eps}}
\caption{Results for $q=4,~8,~16,~32$ and selected sets of
two-point autocorrelations $\{C_k\}$ } \label{t1}
\end{figure}




Table I indicates the following main results: (a) a degradation in
the performance is observed as the correlations are enhanced. (b)
The efficiency of our joint s/c coding technique is superior to the
alternative standard gzip compression in the separation technique.
The gain disappears as the entropy decreases. These results are
farther discussed in \citen{KK} .
%
%Summarizing this part, we conclude by mentioning the advantages of
%the SM based decoder:
%\begin{itemize}
%    \item performs competitive with the separate scheme.
%    \item the amount of required side information is small: the
%    encoder needs to reliably pass to the decoder only the ${y_k}$
%    interactions, the maximal number of interactions is
%    $q=2^{k_0}$.
%\end{itemize}

The DBP decoder based on the SM approach suffers one major
disadvantage: computing the ${y_k}$ interactions, which involves
finding the eigenvalues of a $q\times q$ matrix ($O(q^3)$), and
solving the saddle-point equations, \ref{h2}, which is also a
heavy numerical task, even for $k_0>4$.

%\section{ The role of the spectrum of eigenvalues}
%
%For a given $q$, there are many sets of autocorrelations,
%$\{C_{k_1,...,k_m} \}$, in $q$ dimensions obeying the same entropy
%(see the discussion in section VI below).  An interesting question
%is whether the performance of the presented MN decoder measured by
%the Ratio $(\equiv f_c/f_{Sh})$ is a function of the entropy only.
%Our numerical simulations indicate that the entropy is not the
%only parameter which controls the performance of the algorithm.
%For the same entropy and $q$ the Ratio can fluctuate widely among
%different sets of correlations.  For illustration, in Table II
%(Fig. \ref{t2}) results for two sets of autocorrelations with {\it
%the same entropy} are summarized for each $q=4,~8,~16$ and $32$.
%It is clear that as the Ratio $(\equiv f_c/f_{Sh})$ is much
%degradated the gzip performance is superior (the second example
%with $q=8$ and $32$ in Table II (Fig. \ref{t2}) where the Ratio is
%$0.8$ and $0.72$, respectively). The crucial question is to find
%the criterion to classify the performance of the algorithm among
%all sets of autocorrelations obeying the same entropy.  Our
%generic criterion is {\it the decay of the correlation function
%over distances beyond two successive blocks}. However, before
%examination of this criterion, we return to some aspects of
%statistical physics.
%
%
%
%
%The entropy of sequences with a given set of autocorrelations
%bounded by a distance $k_0=\log_2(q)$ is determined via the
%effective Hamiltonian consisting of $q$ interactions, eq.
%\ref{hamiltonian}.  As a result the entropy of these sequences is
%{\it the same} as the entropy of the effective Hamiltonian,
%$H\{y_{k_1,...,k_m} \}$, at the inverse temperature $\beta=1$, eq.
%\ref{h2}.  As for the usual scenario of the transfer matrix
%method, the leading order of quantities such as free energy and
%entropy are a function of the {\it largest eigenvalue} of the
%transfer matrix only. On the other hand the decay of the
%correlation function is a function of the whole spectrum of the
%$q=2^{k_0}$ eigenvalues (and eigenvectors)\cite{baxter}.
%Asymptotically, the decay of the correlation function is
%determined from the ratio between the second largest eigenvalue,
%$\lambda_2$, and the largest eigenvalue,
%$\lambda_2/\lambda_{max}$.  From the statistical mechanical point
%of view, one may wonder why the first $q$ correlations can be
%determined using the information of $\lambda_{max}$ only. The
%answer is that once the transfer matrix is defined as a function
%of $\{y_{k_1,...,k_m} \}$, eqs. 3-7, {\it all eigenvalues} are
%determined as well as $\lambda_{max}$. There is no way to
%determine $\lambda_{max}$ independently of all other eigenvalues.
%
%In Table II (Fig. \ref{t2}) results of the MN decoder, eq.
%\ref{dbp}, for $q=4,~8,~16,~32$ are presented. For each $q$, two
%different sets of autocorrelations characterized by the {\it same
%entropy} and threshold $f_{Sh}$ are examined.  The practical
%method we used to generate different sets of autocorrelations with
%the same entropy was a simple Monte Carlo over the space of
%$\{C_{k_1,...,k_m} \}$\cite{haggai1}. The additional column in
%Table II (in comparison with Table I) is the ratio between
%$\lambda_2/\lambda_{max}$, which characterizes the decay of the
%correlation function over large distances.  It is clear that for a
%given entropy as $\lambda_2/\lambda_{max}$ increases/decreases,
%the performance of the joint s/c decoder measured by the Ratio
%$f_c/f_{Sh}$ is degradated/enhanced, independent of $q$.  The new
%criterion to classify the performance of the decoder among all
%sets of autocorrelations obeying the same entropy is the decay of
%the correlation function.  This criterion is consistent with the
%tendency that as the first $k_0$ two-points autocorrelations are
%increased/decreased a degradation/enhancement in the performance
%is observed (see Table I).  The physical intuition is that as the
%correlation length increases, the relaxation time to the
%equilibrium macroscopic state increases, and flips on larger
%scales than nearest neighbor blocks are required. Finally, we note
%that in the general scenario, the first two largest eigenvalues
%are not sufficient to approximate the correlation function on
%short length scales and the comparison of the efficiency of the
%decoder should take into account the entire spectrum of
%eigenvalues and the eigenvectors \cite{baxter}.
%
%
%
%\begin{figure}
%\centering
%\includegraphics[width=5.75in]{figs/Lamda_Rate_table.ps}
%%\centerline{\epsfxsize=5.75in \epsffile{2/Lamda_Rate_table.ps}}
%\caption{Results for $q=4,~8,~16,~32$ and different sets of
%two-point autocorrelations.  For each $q$, two different sets of
%two-point autocorrelations characterized by the same entropy and
%threshold $f_{Sh}$ are examined.  As $\lambda_2/\lambda_{max}$
%increases/decreases, the performance of the joint s/c decoder
%measured by the Ratio $f_c/f_{Sh}$ is degradated/enhanced.}
%\label{t2}
%\end{figure}
%
%Note that the decay of the correlation function in the
%intermediate region of a small number of blocks is a function of
%all the $2^{k_0}$ eigenvalues.  Hence, in order to enhance the
%effect of the fast decay of the correlation function in the case
%of small $\lambda_2/\lambda_{max}$, we also try to enforce in our
%Monte Carlo search that all other $2^{k_0}-2$ eigenvalues be less
%than $A\lambda_{max}$ with the minimal possible constant $A$.
%This additional constraint was easily fulfilled for $q=4$ with
%$A=0.1$, but for $q=32$ the minimal $A$ was around $0.5$.
%



%\section{ Drawbacks of the SM approach}
%
%The presented joint s/c decoder based on the SM approach suffers
%from the following drawbacks:
%%(a) As the strength of the interactions is enhanced,
%%$|y_{k_1,...,k_m}| \gg 0$, a dramatic degradation in the performance
%%of the DBP algorithm is observed. In Fig. 2, results of simulations
%%for rate, $R=1/3$, $L=10,000$ and $C_1=0.64,~C_2=0.33$ ($y_1 \sim 1.4,
%%y_2 \sim -0.44$) are presented. The performance of the DBP algorithm
%%is degradated even in a comparison to the same algorithm with unbiased
%%({\it i.i.d}) sources.
%(a) For each transmitted block one must calculate a $q \times q$
%matrix, where each element of this matrix is a function of all $q$
%autocorrelations, $\{ C_{k_1,...,k_m}\}$.  Hence, the naive
%complexity of the construction of the transfer matrix is $O(q^4)$.
%Furthermore, for each transmitted block the complexity of the
%calculation of the leading eigenvalue of the transfer matrix is of
%$O(q^3)$.  (b) The required memory is of the order $O(q^2)$,
%where, for instance, for $K_0=20$ it results in a 1Mega Bytes.
%(c) The solution of the saddle point equations, eqs. 4-5, requires
%the calculation many times and with high precision of the leading
%eigenvalue of $q \times q$ matrix. From our experience, the
%calculation with high precision of the saddle point equations in
%$q=2^{k_0}$ dimensions, $\{ y_{k_1,...,k_m} \}$ is a heavy
%numerical task for $k_0 \ge 4$.  (d) The extension of the decoder
%based on the SM approach to include an array of bits in two or a
%higher number of dimensions is impossible, since the trace in eq.
%\ref{omega} can be done only for very limited two-dimensional
%cases\cite{baxter}.


\section{Markovian joint s/c decoder}



In order to overcome the abovementioned  drawbacks of the SM
approach, we now treat the source sequence from a different point
of view, by assuming that these sequences were generated by a
Markov process. Hence, the sequence can be described by an
alphabet $GF(q)$, a transition matrix $T_{kj}=P(x_i=j|x_{i-1}=k)$,
and the stationary solutions of the process, $P(j)$. The key point
is that for large messages, $T$ and $P(j)$ can be (approximately)
measured by the sender (for each chunk of data) with $O(L_0)$
operations. $T$ and $P(j)$ may then be transmitted reliably to the
decoder and used as side information in the decoding process
(similar to the transmission of the ${y_1,...y_{k_0}}$
interactions in the SM approach).

Consider three successive symbols $x_{i-1},x_i,x_{i+1}$ in such a
sequence. The probability of the triplet $a,b,c$ is given by:

\begin{eqnarray}\label{Pabc}
% \nonumber to remove numbering (before each equation)
  P(a,b,c)=P(a,b)\cdot P(c|a,b)=P(a,b)\cdot P(c|b)
%  =P(a)\cdot P(b|a)\cdot P(c|b)
=\frac{P(a,b)P(b,c)}{P(b)}
\end{eqnarray}

\noindent where use has been made of the Bayes Rule:
$P(x,y)=P(x)\cdot P(y|x)$, and fact that the process is
memoryless. Now, given the a-posteriori probabilities for the
first and last symbols in the triplet: $q_{i-1}^a=Pr(x_{i-1}=a)$
and $q_{i+1}^c=Pr(x_{i+1}=c)$, one can calculate a dynamical block
prior (corresponding to the prior in (\ref{dbp}) for the
probability that $x_i=b$:

\begin{eqnarray}\label{Prior(b)}
% \nonumber to remove numbering (before each equation)
  Pr(x_i=b)=\frac{1}{Z}\cdot \sum_{a,c=1}^q{P(a,b,c)\cdot q(a)}\cdot q(c)=\nonumber \\
  =\frac{1}{Z}P(b)^{-1} \left(\sum_{a=1}^q{P(a,b) q_{i-1}^a}\right)\cdot
 \left(\sum_{c=1}^q{P(b,c) q_{i+1}^c}\right),
%  =\frac{1}{Z}\cdot \sum_{a=1}^q{(P(a)\cdot P(b|a)\cdot Q_{i-1}^a)}\cdot
%\sum_{c=1}^q{(P(c|b)\cdot Q_{i+1}^c)},
\end{eqnarray}

\noindent where $Z$ is a normalization constant such that:
$\sum_{b=1}^q{Pr(x_i=b)}=1$.

The extension of the MN algorithm to the joint source-channel case
consists of the following steps:\begin{enumerate}
    \item A binary sequence of $L_0\cdot log_2(q)$ bits is converted to $L_0$ $GF(q)$ symbols.
    \item The encoder measures $T$ and $P(j)$ for all
    the $q$ symbols over the source, and transmits reliably this side
    information to the decoder.
    \item The source is encoded according to
    (\ref{trans}), then reconverted to binary representation
    and transmitted.
    \item The decoder maps the received signal back to GF($q$), and
    performs the regular decoding
    (\ref{decoding}), but after every iteration of message passing, the prior for each source symbol is
    recalculated according to (\ref{Prior(b)}).
\end{enumerate}
The complexity of calculating the $q$ priors for a single symbol
according to the posteriors of its neighbors is reduced from $q^3$
to $q^2$ by Eq. (\ref{Prior(b)}), hence the decoder's complexity
remains linear, with total complexity of $O(L_0qu+L_0q^2)$ per
iteration.

\begin{wrapfigure}{r}{6.6cm} % r: RIGHT, 6.6cm: WIDTH
\includegraphics[width=2.5in, angle=270]{Markov_c07.eps}
\caption{ The bit error rate, $p_b$ versus the channel bit error
rate $f$ for $L=10,000$, $R=1/3$, $q=8$ with $C_1=C_2=C_3=0.7$.
Decoding following the Markovian process, Eq. (\ref{Prior(b)})
(open triangle), decoding following the Markovian process where
only $8$ dominated elements of the transition matrix, $T$, are
taken as a side information (open circle). Shannon's lower bound,
$f_c=0.271$ ($H=0.47$), is denoted by an arrow.} \label{q88}
\end{wrapfigure}


However, there is still a need for the transmission of the side
information ($T$, $P(j)$). Hence the size of the header is of the
order of $O(q^2)$.  For $L \rightarrow \infty$ or more precisely
for $L \gg q^2$ the overhead of the transmitted side information
is negligible; however, for a finite $L \le q^2$ it may cancel the
benefits of the Markovian joint s/c decoder.



The header size can be reduced using the following observation:
For sequences with enhanced autocorrelations, the structure of $T$
was observed to be dominated by a small number of large elements.
One can transmit only these dominated elements, and the remaining
elements of each row of $T$ will be filled evenly to maintain:
$\sum_{j=1}^q{T_{ij}}   =1$.

Fig. \ref{q88} represents simulation results for the Markovian
scheme.  Triangles mark decoding using full $T$, while circles
mark decoding using only the 8 (out of 64) most dominant elements
of $T$. The performance seems to be only slightly affected by this
approximation, which dramatically reduces the required transmitted
side information.




%\begin{figure}
%\centering \vspace{2.5cm}
%\includegraphics[width=2.5in]{figs/Markov_c068068060655.new1.eps}
%%\centerline{\epsfxsize=2.5in
%%\epsffile{2/Markov_c068068060655.new1.eps}}
%
%\caption{ The bit error rate, $p_b$ versus the channel bit error
%rate $f$ for $L=10,000$, $R=1/3$, $q=16$ with
%$C_1=0.68,~C_2=0.68,~,C_3=0.6,C_4=0.655$.  Decoding following the
%Markovian process, Eq. \ref{pabc} (open triangular) and decoding
%following the Markovian process where only $16$ dominated elements
%of the transition matrix, ${\hat P}(A,B)$, are taken as a side
%information, and the rest of the elements are set equal to a
%constant such that the sum of each row is equal to $1$ (open
%circle).  Shannon's lower bound, $f_c=0.266$, is denoted by an
%arrow.} \label{q1616}
%\end{figure}

An interesting open question is the effect of use of the
sparseness of $T$ on  the complexity and performance of the
decoder.

\section{Efficient Joint s/c decoder with the lack of side information}

The discussion in the previous sections indicates that the
performance of the presented joint s/c coding is not too far from
Shannon's lower bound and, most probably, using an optimized code
(a better construction for the matrices $A$ and $B$ of the MN
code), the channel capacity can be nearly saturated. However, for
a finite block length. the main drawback of our algorithm is the
overhead of the header which must be encoded and transmitted
reliably. One has to remember that the size of the header scales
with $q^2$ where the precision of each element is of the order
$O(\log L)$. This overhead is especially intolerable in the limit
where $q^2 \log / L \sim O(1)$
%\begin{equation}
%{q^2 \log (L) \over L} \sim O(1) \label{largeblock}
%\end{equation}
Note that this is indeed the situation even for very large
messages, $L=10^6$, and the largest taken autocorrelation length
is only $\log_2q=8$.
%
%the first $N$ rows of $A$ are characterized by one non-zero
%element per row and column, where the first $N$ rows of $B$ are
%characterized by $2$ non-zero elements (furthermore, each row of
%$B$ cannot be written as a linear combination of the other rows).
%Hence, the first $N$ bits of the syndrome, eq. \ref{decoding}, are
%equal to the source with an effective flip rate equal to
%$f_{eff}=2f(1-f)$. The EM algorithm with $f_{eff}$ can now be used
%to estimate the finite number of parameters of the Markovian
%process generating the sequence.

In this section we explain how the Markovian joint s/c can be
implemented without any side information. The key points are the
special properties of KS construction \citen{KS} (Fig. \ref{ks}):
the first $L_0$ rows of $A$ are characterized by one non-zero
element per row and column, where the first $L_0$ rows of $B$ are
characterized by $2$ non-zero elements. Furthermore, due to the
systematic form of $B$, each row cannot be written as a linear
combination of the other rows. Hence, the first $L_0$ bits of the
syndrome, Eq. (\ref{decoding}), are equal (up to a simple
permutation) to the source, with an effective flip rate, $f_{eff}$.
For $GF(2)$ for instance, $Z_j=x_i+n_j+n_{j+1}$ ($i$ marks the
position of the nonzero element in the $j^{th}$ row of $A$), and
$f_{eff}=2f(1-f)$. The first $L_0$ symbols of $Z$ are therefore a
result of a Hidden Markov Model (HMM).  The underlaying transition
matrix, $T$, generating the source sequence, can be estimated by
means of the EM algorithm \citen{EM}. This is a standard tool for
solving such \emph{Parametric Estimation} problems, which has linear
complexity. Having $T$ (approximately) revealed, the Dynamical Block
Priors can be used as described in \ref{Prior(b)}.

%
%\begin{equation}\label{Z1=Ax+Bn1n2}
%    Z_1=x_i+n_1+n_2,
%\end{equation}
%where $i$ marks the position of the single nonzero element in the
%first row of $A$. Hence, $Z_1$ is identical to $x_i$, up to an
%effective noise $f_e$ (for $GF(2)$: $f_e=2f\cdot (1-f)$).
%therefore, if one permutes the first $k$ elements of $Z$ in a
%manner that $Z_1'$ will correspond to $x_1$, $Z_2'$ to
%$x_2$...$Z_k'$ to $x_k$, this permuted vector $Z'$ will be
%identical to the source vector $x$, up to the effective noise
%$f_e$. Recalling that $x$ was generated by a Markov process, the
%first $k$ elements of $Z'$ are a result of a Hidden Markov Model
%(HMM) with noise $f_e$. The underlaying transition matrix, $T$,
%generating the source sequence, can be estimated by means of the
%EM algorithm \cite{EM} , which is a standard, linear in $L_0$,
%tool for solving such \emph{Parametric Estimation} problems in
%statistics. Having $T$ (approximately) revealed, the Dynamical
%Block Priors can be used as described in \ref{Prior(b)}.
%

%The first $N$ received bits (the source message) using the
%Gallager code with systematic parity-check matrix is the message
%itself which is generated by a Markovian process plus the
%additional channel noise $f$. Hence, from the receiver point of
%view the generator of the first $N$ received bits is a Hidden
%Markov Process.  The first task of the receiver is to estimate
%${\hat P}(A,B)$ from the knowledge of the noisy received source
%message and the channel flip rate $f$.  This type of {\it
%parametric estimation} is a common problem in statistics and can
%be solved (exactly or approximately) using the EM algorithm or by
%one of its variants \cite{EM}. More precisely, for an infinite
%source, $L \rightarrow \infty$, the transition matrix eq.
%\ref{t-ij} (or the interaction strengths eq. \ref{h2}) can be
%recovered within a bounded error with $O(L)$ time complexity. For
%a finite $L$ sequence the parameters of the Markovian process can
%be estimated approximately with an error of the order $O(q^2/L)$.
%Hence, the required parameters for the presented joint s/c decoder
%based on the dynamical block posterior probabilities can be
%estimated from the received noisy message.  Note that as explained
%above, the error in the dominated elements of the transition
%matrix, ${\hat P}(A,B)$, is the most important ingredient for the
%performance of our joint s/c decoder, hence one may desire an
%efficient algorithm to estimate especially the dominated part of
%the transition matrix.
%
%The critical problem with the above description is that our
%efficient decoder can be implemented only by the MN algorithm,
%where the decoder {\it simultaneously} estimates the values for
%the source and noise bits.  In contrast, in the Gallager decoder,
%the values for the noise bits are firstly estimated, and only in
%the next step are the source bits recovered. Hence, the dynamical
%block posterior probabilities cannot be used (to our current
%knowledge) in the framework of the Gallager algorithm.  Since in
%the MN decoder the source is not transmitted by itself, the
%question now is how to estimate the parameters of the Markovian
%process which are responsible for generating of the source message
%from the received message. Nevertheless, as explained below, this
%problem can be solved also for the MN case in $O(L)$ time
%complexity.
%
%Let us first explain the solution for the examined MN
%construction, Fig. \ref{ks}, then later sketch the general
%solution.  For the used MN construction, Fig. \ref{ks}, the first
%$N$ rows of $A$ are characterized by one non-zero element per row
%and column, where the first $N$ rows of $B$ are characterized by
%$2$ non-zero elements (furthermore, each row of $B$ cannot be
%written as a linear combination of the other rows). Hence, the
%first $N$ bits of the syndrome, eq. \ref{decoding}, are equal to
%the source with an effective flip rate equal to $f_{eff}=2f(1-f)$.
%The EM algorithm with $f_{eff}$ can now be used to estimate the
%finite number of parameters of the Markovian process generating
%the sequence.
%
For the general construction of the MN algorithm, one adds/subtracts
rows of the concatenated matrix $[A,B]$ and the corresponding
symbols in $z$ (see Eq. (\ref{decoding})), such that the following
situation is finally reached: The first $L_0$ rows of $A$ are the
identity matrix, regardless of the construction of the first $L_0$
rows of $B$. From the knowledge of the noise level $f$ and the
structure of $i^{th}$ row of $B$ one can now calculate the effective
noise level, $f_{i,eff}$, of the $i^{th}$ received source symbol.
Since all $\{f_{i,eff}\}$ are functions of a unique noise level $f$,
one can again estimate the parameters of the Markovian process using
some variants of the EM algorithm. Note, that in the general case
the first $L_0$ rows of $B$ contain loops, hence the $\{f_{i,eff}
\}$, are correlated. However, these correlations are assumed to be
small as the typical loop size is of the order of $O(\log
(L))$\citen{erdos}.

%The only approximation used in the calculation of $\{f_{i,eff} \}$
%{\it in the general case} is that the new form of the first $N$
%rows of $B$ contain loops, hence $\{f_{i,eff} \}$ are correlated.
%However, these correlations are assumed to be small as the typical
%loops are of the order of $O(\log (L))$.

%\section{ Markovian joint s/c coding in higher dimensions}
%
%The decoder based on the SM approach, eq. \ref{dbp}, is limited to
%a one-dimensional stream of bits, since the trace in eq.
%\ref{omega1} can be done using the transfer matrix method (or any
%known method) only to very limited cases of a two-dimensional
%array of bits \cite{baxter}. The analytical solution of a
%two-dimensional Ising system with arbitrary strength of even
%nearest neighbor interactions is not known and in three dimensions
%no analytical solution is known.  On the contrary, the
%one-dimensional Markovian joint s/c decoder can be easily extended
%to a joint s/c coding of a two-dimensional array of bits or even
%to an array of bits in higher dimensions.
%
%For illustration, assume that we have a two-dimensional picture to
%transmit using a joint s/c mechanism via a noisy channel. A simple
%way would be to convert the two-dimensional picture into a
%one-dimensional sequence and then to use, for instance, one of the
%abovementioned decoders.  However, it is clear that the mapping of
%the two-dimensional picture into a one-dimensional sequence is not
%unique and of course the natural two-dimensional correlations are
%destroyed in this mapping (at least for the realistic case of
%finite $k_0$). An alternative way is to generalize the advanced
%threshold joint s/c decoder, eq. \ref{dbp3}, to two dimensions,
%where each block is updated following its four neighboring blocks.
%The generalization of eq. \ref{pabc} to this case is given by
%\begin{eqnarray}
%{\hat P}(B_{i,j-1},B_{i-1,j},B_{i,j},B_{i+1,j},B_{i,j+1}) \equiv
%\nonumber \\
%{1 \over L_0^2} \sum_{i,j}^{L_0} \prod_{k+m=-1,0,1}
%\delta_{A_{i+k,j+m},B_{i+k,j+m}} \label{pabc-2d}
%\end{eqnarray}
%\noindent where $L_0^2=(L/k_0)^2$ is the number of blocks of the
%two-dimensional array of bits, and again periodic boundary
%conditions are assumed.  Similarly to eq. \ref{pabc}, the
%dynamical posterior probabilities now take the following form
%\begin{eqnarray}
%\gamma_{n}^{B_{k,m}} = \sum_{i,j,s,t=1}^q { {\hat
%P}(B_{i},B_{j},B_{k,m},B_{s},B_{t}) \over \sum_{b=1}^q {\hat
%P}(B_i,b,B_j) }\times  \nonumber \\ q_{k-1,m}^{i} q_{k,m-1}^j
%q_{k+1,m}^{s} q_{k,m+1}^t \label{gamma-2d}
%\end{eqnarray}
%\noindent It is clear that the generalization of this decoder to a
%higher dimension is straightforward and in the naive decoding the
%complexity of the decoder scales as $L_0^dq^{2d-1}$.
%Nevertheless, similarly to the Markovian joint s/c decoder also in
%the higher dimensional case the complexity can be reduced and, for
%instance, in two dimensions
%\begin{eqnarray}
%&{\hat P}(B_{i,j-1},B_{i-1,j},B_{i,j},B_{i,j+1},B_{i+1,j})= \nonumber \\
%&{ {\hat P}(B_{i,j-1},B_{i,j}) {\hat P}(B_{i-1,j},B_{i,j}) {\hat
%P}(B_{i,j+1},B_{i,j}) {\hat P}(B_{i+1,j-},B_{i,j}) \over {\hat
%P}(B_{i,j})^3 } \label{pabc-d}
%\end{eqnarray}
%\noindent and similarly in higher dimensions. Hence, the
%complexity of a message passing in $d$ dimensions is reduced to
%$(L_0)^dq^2$, or alternatively the complexity per block is of the
%order of $O(q^2)$.
%
%Besides the above simplification, it is important to note that for
%finite $L$ the tensor of the probabilities of occurrence of
%nearest blocks, for instance eq. \ref{pabc-d}, for the
%two-dimensional case, is expected to be very sparse. Hence, the
%decoder can be accelerated as was discussed for the
%one-dimensional case.
%
%From an analytical point of view, we do not have an effective way
%to generate an ensemble of arrays with a given set of
%autocorrelations in two or higher dimensions, since we do not know
%how to derive the effective interactions, eq. \ref{hamiltonian}.
%From a practical point of view, for a given two-dimensional
%picture and $k_0$, we can measure the correlations, eq.
%\ref{pabc-d}, and then apply the Markovian decoder. However, there
%is no reference point to compare the efficiency of the decoder,
%since we do not have an effective way to calculate the entropy,
%$H_2$, and then Shannon's lower bound, eq. \ref{capacity}, for a
%given set of correlations in more than one dimension. Practically,
%%a comparison can be made of
%the performance of the Markovian decoder in higher dimensions can
%be compared to other known efficient lossless compression methods
%for two and higher dimensions.  This important comparison
%certainly warrants further research.


\section{Concluding remarks}

The only remaining major drawback of the presented Markovian joint
s/c coding is that the complexity of the decoder per message
passing, scales as $O(Lq^2/\log_2(q))$, this may considerably slow
down the decoder even for moderate alphabet size. Note however,
that for large $q$, such that $q^2\geq L$, and low entropy
sequences, the transition matrix, $T$, is expected to be very
sparse (consider $q=1024$ vs. block size of $L=100,000$). Taking
advantage of the sparseness of $T$, the complexity of the decoder
can be further reduced.

The one-dimensional Markovian joint s/c decoder can be easily
extended to coding of a two-dimensional array of symbols or even to
an array of symbols in higher dimensions. The complexity of the DBP
decoder scales as $L_0^dq^{2d+1}$, where $L_0^d$ is the number of
blocks in the array, and $d$ denotes the dimension\citen{haggai1}.
Using Markovian and Bayesian assumptions, the complexity can be
reduced to $O(L_0^dq^2)$.

%We note that asymptotically the complexity of the Markovian joint
%s/c decoder per message passing might be reduced to
%$O(Lq\log(q))$.  The main idea can be exemplified in the framework
%of the original SM scheme, eq. \ref{dbp}. The complexity of the
%calculation of each $\gamma_n^c$ is of the order of $q$, and it is
%required to calculate such $q$ different elements. Each summation
%in eq. \ref{dbp} consists of the following two types of terms. The
%first one is the static terms, $S_{L}(l,c) (S_R(c,r))$, which are
%the Boltzmann factors, or a row of the transition matrix of the
%Markov process. The second type is the dynamical posterior
%probabilities for the neighboring blocks, $q_L^l,~q_R^r$.  The
%static terms can be ordered in a decreasing rank order only once,
%in the initial stage of the decoder, and the first $O(\log(q))$
%largest dynamical posterior probabilities can be found at the cost
%of $O((q\log(q)))$ per block.  Next we run the usual decoder, eq.
%\ref{dbp}, in one of the following two options: (a) the summations
%in eq. \ref{dbp} are done only on the {\it current} leading
%$O(\log(q))$ of the dynamical block posterior probabilities, or
%alternatively (b) the summations are done as was proposed in (a)
%with the additional $O(\log(q))$ leading terms of the static
%terms, or any combination of (a) and (b).
%
%The idea behind the above procedure is similar to results of
%section IX, where only a limited degradation in the performance of
%the Markovian decoder was observed where the transition matrix was
%approximated by the knowledge of only a small number dominated
%terms. Similarly in the presented approximation, we expect that
%most of the bits are correctly ordered by the dominated part of
%the static Boltzmann weights and by the dominated part of the
%dynamical block posterior probabilities.  In the final stage of
%the decoder, rare events of a pair of blocks, small Boltzmann
%factors, will be correctly ordered by the dominated true posterior
%block probabilities for one of its two neighbors.
%
%
%The question which remains to be answered is the origin of the
%suggested scaling of the order of $O(\log(q))$ dominated taken
%terms in the summations of eq. \ref{dbp}. The explanation is based
%on the characteristic features of random graphs
%\cite{erdos,kanter1}. In the full operation of the Markovian
%process one assigns for each pair of nearest blocks a dynamical
%transition matrix of size $q \times q$, which resembles a fully
%connected graph consisting of $q$ nodes. The purpose of our
%approximation is to replace the fully connected graph with the
%diluted one, {\it but the graph has still to be connected}; the
%maximal component of the graph must be $q$. The lack of finite
%components is a necessary condition, since in such an event the
%enhancement of the true block posterior probability may be
%dynamically forbidden, since there are isolated nodes (states).
%From the random graph theory it is known that the maximal
%component is equal to $q$ where the average connectivity (the
%average number of non-zero transitions per row) is of the order of
%$O(\log(q))$\cite{erdos,kanter1}. This prediction has still to be
%confirmed in large scale simulations, large $L$ and $q$.





\section*{Acknowledgements}
I.K. thanks David Forney, Wolfgang Kinzel, Manfred Opper, Shlomo
Shamai, and Shun-ichi Amari for many helpful discussions and
comments. This work was partially supported by the Israeli Academy
of Science.


%\appendix
%\section{First Appendix} %Empty argument \section{} yields `Appendix'.
%
%\section{Second Appendix}


\begin{thebibliography}{99}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Some macros are available for the bibliography:
%  o for general use
%    \JL : general journals                 \andvol : Vol (Year) Page
%  o for individual journal
%    \AJ   : Astrophys. J.           \NC         : Nuovo Cim.
%    \ANN  : Ann. of Phys.           \NPA, \NPB  : Nucl. Phys. [A,B]
%    \CMP  : Commun. Math. Phys.     \PLA, \PLB  : Phys. Lett. [A,B]
%    \IJMP : Int. J. Mod. Phys.      \PRA - \PRE : Phys. Rev. [A-E]
%    \JHEP : J. High Energy Phys.    \PRL        : Phys. Rev. Lett.
%    \JMP  : J. Math. Phys.          \PRP        : Phys. Rep.
%    \JP   : J. of Phys.             \PTP        : Prog. Theor. Phys.
%    \JPSJ : J. Phys. Soc. Jpn.      \PTPS       : Prog. Theor. Phys. Suppl.
% Usage:
%  \PRD{45,1990,345}          ==> Phys.~Rev.\ \textbf{D45} (1990), 345
%  \JL{Nature,418,2002,123}   ==> Nature \textbf{418} (2002), 123
%  \andvol{B123,1995,1020}    ==> \textbf{B123} (1995), 1020
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibitem{rf:2}
%S.~Weinberg, Phys.\ Rev.\ Lett.\ \textbf{19} (1967), 1264.

%\bibitem{forney}
%Sae-Young Chung, Forney GD Jr, Richardson TJ, Urbanke R, {\em
%IEEE, Communications Letters, vol.5, no.2, Feb. 2001, pp.58-60.}
%
%\bibitem{David-Mackay2} Richardson TJ, Urbanke R.
%{\em IEEE Transactions on Information Theory, vol.47, no.2, Feb.
%2001, pp.599-618.}
%
%
%\bibitem{Shokrollahi} Luby MG, Mitzenmacher M, Shokrollahi MA,
%Spielman DA, {\em Proceedings of the Thirtieth Annual ACM
%Symposium on Theory of Computing.  ACM. 1998, pp.249-58. New York,
%NY, USA.}
\bibitem{Cover} Cover TM, Thomas JA. {\it Elements of information
theory.}  Wiley. 1991, UK.

\bibitem{Gallager} Gallager RG,  {\em Low Density Parity Check Codes}
Research monograph series {\bf 21} (MIT press), 1963.

\bibitem{Shannon} Shannon CE, A mathematical theory of
communication, {\emph Bell System Technical J.}, {\bf 27},
379-423, 623-656, 1948.

\bibitem{KR} Kanter I and Rosemarin H, (cond-mat-0301005).

\bibitem{KK} Kanter I and Kfir H,
%Statistical mechanical aspects of joint source-channel coding,%
 {\it Europhys. Lett. Vol. 63 No. 2
pp. 310 (July 2003)}.

\bibitem{sourlas} Sourlas N,
%Spin-glass models as error-correcting codes.
{\it Nature, vol.339, no.6227, 29 June 1989, pp.693-5}.

\bibitem{liat} Ein-Dor L, Kanter I, Kinzel W,
%Low autocorrelated multiphase sequences.%
  {\it Physical Review E, vol.65, no.2, Feb.
2002}.

\bibitem{baxter}Baxter RJ, Exactly Solved Models in Statistical
Mechanics, {\emph Academic Press, London}, 1982.

\bibitem{ido-msi} Kanter I,
%The equivalence between discrete-spin Hamiltonians and Ising Hamiltonians with multi-spin interactions,
{\it J. Phys. A, vol. 20 pp. L257 1987}.

\bibitem{LDPC-GF(q)} Davey MC and MacKay DJC,
%Low-density parity check codes over GF(q).
{\it Communications Letters, vol.2, no.6, June 1998, pp.165-7}.

\bibitem{David-Mackay1} MacKay DJC and Davey MC,
{\it Gallager Codes for Short Block Length and High Rate
Applications, Codes, Systems and Graphical Models}, IMA Volumes in
Mathematics and its Applications, Springer-Verlag (2000).

\bibitem{KS} Kanter I, Saad D, {\em Phys. Rev. Let., vol.83,
no.13, 27 Sept. 1999, pp.2660-3.}

\bibitem{KS-Gaussian} Kanter I, Saad D,
%Finite-size effects and error-free communication in Gaussian channels.
{\it j. Phys. A, vol.33, no.8, 3 March 2000, pp.1675-81.}

\bibitem{saad} Kabashima Y, Saad D,
% Statistical mechanics of error-correcting codes.  %
{\it Europhysics Letters, vol.45, no.1, 1 Jan. 1999, pp.97-103}.

\bibitem{saad1} Skantzos NS, van Mourik J,  Saad D and
Kabashima  Y,
%Average and reliability error exponents in low-density-parity-check-codes,
J. Phys. A 36 No 43 (31 October 2003) 11131-11141.

\bibitem{r89} For rate $9/8$, for instance, the chosen construction
for the matrices $A$ and $B$ is as follows. $A$ hase sets of rows
with $1,2,3,5,9$ random non-zero elements per row. the number of
rows from each type is $(m/16,m/4,m/16,m/16,m/16)$, where $m$ is
the number of rows in $A$. The structure of $B$ is the same as
illustrated in Fig. \ref{ks}, but $1.75$ is replaced with $7/9$.
We ran simulations for this construction with $C_1=C_2=0.7$ and
the corresponding entropy is $H_2=0.513$ and $L=9,000$.  The
extrapolation of $t_{med}$ indicates that the threshold of this
code for large $L$ is $f_c \sim 0.057$. In the separation scheme
using {\it optimal compression and error correction schemes} and
with $f_c=0.057 ~(R_{i.i.d}=0.618)$, one can find that the overall
inverse rate of the communication channel is $1/R=0.513/0.618 \sim
0.83$, which is only about $6\%$ below our joint s/c inverse rate
$1/R=8/9 \sim 0.89$.  One must remember that our MN construction
can be further optimized, and the critical channel noise is
expected to be enhanced, $f_c > 0.057$.

\bibitem{median} In practice we define $t_{med}$ to be the average
convergence time of all samples with $t \le$ the median time.

\bibitem{PPM} The PPMZ software used can be downloaded from
www.cbloom.com/src/ppmz.html

\bibitem{AC} The AC software used can be downloaded from
www.cs.mu.oz.au/~alistair/arith\_coder

\bibitem{EM} McLachlan GJ and Krishan T,  The EM Algorithm and
Extension. {\it Wiley Sons, NY, 1997}.

\bibitem{erdos} Erdos P and Reyni A, The Art of Counting,
Edit. by J. Spencer (MIT Press, Cambridge MA , 1973).

\bibitem{haggai1} Kfir H and Kanter I (unpublished).








%\bibitem{turbo} Berrou C, Glavieux A, Thitimajshima P, {\em ICC
%'93 Geneva. IEEE International Conference on Communications '93.
%IEEE. 1993, pp.1064-70 vol.2.}. and Berrou C, Glavieux A,  {\em
%IEEE Transactions on Communications, vol.44, no.10, Oct. 1996,
%pp.1261-71.}







%\bibitem{err_cor_book} Michelson, AM  and Levesque, AH,
%{\it Error-Control Techniques for Digital Communications,} Wiley,
%New York, 1985.
%
%\bibitem{Frey} Frey BJ, {\em Graphical Models for Machine Learning
%and Digital Communication} (MIT Press), 1998.



%\bibitem{shamail1} Kliewer J, Thobaben R, {\it Proceedings DCC
%2002. Data Compression Conference. IEEE Comput. Soc. 2002,
%pp.83-91.  Los Alamitos, CA, USA.}
%
%\bibitem{shamail2} Shamai S, Verdu S, {\it European Transactions on
%Telecommunications \& Related Technologies, vol.6,no.5, Sept.-Oct.
%1995, pp.587-600.}
%
%\bibitem{shamail3} Liveris A, Xiong Z and Georghiades CN,
%{\it Proceedings of Globecom 2002, Taipei, Taiwan, November 17-21
%2002. }
%
%
%\bibitem{shamail4} Garcia-Frias J and  Villasenor JD,
%%Joint Turbo Decoding and Estimation of Hidden Markov Sources
%{\it IEEE J. Selec. Areas Commun., Vol. 19, No. 9, pp. 1671-1679,
%Sept. 2001}.
%
%
%\bibitem{shamail5} C.-C. Zhu and F. Alajaji,
%%Turbo Codes for Non-Uniform Memoryless Sources over Noisy Channels,
%{\it IEEE Communications Letters, Vol. 6, No. 2, pp. 64-66,
%February 2002}.
%
%
%\bibitem{shamail6} Garcia-Frias J , Zhao Y,
%% Compression of binary memoryless sources using punctured turbo codes,
%{\it IEEE Communication Letters, vol.6, no.9, pp.394�396 (2002).}







%\bibitem{sourlas1} Sourlas N,
%%Statistical mechanics and capacity-approaching error-correcting codes.%
% {\it Physica A, vol.302, no.1-4, 15 Dec. 2001, pp.14-21. }



%\bibitem{kinzel} We thank W. Kinzel for his advice to simplify
%the decoder by using the Markovian process.





%\bibitem{MacKay} MacKay DJC and  Neal RM,
%% Near Shannon limit performance of low density parity check codes.
% {\it Electronics Letters, vol.33, no.6, 13 March 1997, pp.457-8}. MacKay DJC,
% % Good error-correcting codes based on very sparse matrices. %
% {\it IEEE Transactions on Information Theory, vol.45, no.2, March 1999,
%pp.399-431. }



%\bibitem{KABA} Nakamura K, Kabashima Y and Saad D,
%%Statistical mechanics of low-density parity-check codes over Galois fields,
%{\it Europhys. Lett., vol.  56, 2001, pp. 610-616}.


%\bibitem{Davey} MacKay D. J. C, Wilson S. T. , Davey M. C.
%%Comparison of constructions of irregular Gallager codes.
% {\it IEEE Transactions on Communications, vol.47, no.10, Oct. 1999,
%pp.1449-54. Publisher: IEEE, USA} M.C.~Davey and D.J.C.~MacKay,
%{\em IEEE Comm. Lett.}, in press (1999).












%\bibitem{domany} Priel A, Blatt M, Grossman T, Domany E, Kanter
%I,
%%Computational capabilities of restricted two-layered perceptrons.
%{\it Physical Review E, vol.50, no.1,
% July 1994,
%pp.577-95.}









%\bibitem{bias} A similar degradation in the performance was observed
%for $q=2$ and biased binary messages (each source bit is equal
%$0/1$ and is chosen with probability $p/1-p$).  As $|p-0.5|$
%increases the entropy decreases and a degradation in the
%performance of the MN algorithm was observed.




%\bibitem{shahar} Shahar K and Kanter I (unpublished).






%\bibitem{manfred} I. Kanter thanks Manfred Opper for the discussion
%on this general result.



%\bibitem{comment} In principle one can generalize the tensor to
%include nearest and next-nearest blocks.

%

%
%\bibitem{kanter1} Kanter I, Sompolinsky H.
%%Mean-field theory of spin-glasses with finite coordination number.
%{\it Phys. Rev. Let., vol.58, no.2, 12 Jan. 1987, pp.164-7.}




\end{thebibliography}
\end{document}

cond-mat0412574.extracted_bib
\begin{thebibliography}{99}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Some macros are available for the bibliography:
%  o for general use
%    \JL : general journals                 \andvol : Vol (Year) Page
%  o for individual journal
%    \AJ   : Astrophys. J.           \NC         : Nuovo Cim.
%    \ANN  : Ann. of Phys.           \NPA, \NPB  : Nucl. Phys. [A,B]
%    \CMP  : Commun. Math. Phys.     \PLA, \PLB  : Phys. Lett. [A,B]
%    \IJMP : Int. J. Mod. Phys.      \PRA - \PRE : Phys. Rev. [A-E]
%    \JHEP : J. High Energy Phys.    \PRL        : Phys. Rev. Lett.
%    \JMP  : J. Math. Phys.          \PRP        : Phys. Rep.
%    \JP   : J. of Phys.             \PTP        : Prog. Theor. Phys.
%    \JPSJ : J. Phys. Soc. Jpn.      \PTPS       : Prog. Theor. Phys. Suppl.
% Usage:
%  \PRD{45,1990,345}          ==> Phys.~Rev.\ \textbf{D45} (1990), 345
%  \JL{Nature,418,2002,123}   ==> Nature \textbf{418} (2002), 123
%  \andvol{B123,1995,1020}    ==> \textbf{B123} (1995), 1020
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibitem{rf:2}
%S.~Weinberg, Phys.\ Rev.\ Lett.\ \textbf{19} (1967), 1264.

%\bibitem{forney}
%Sae-Young Chung, Forney GD Jr, Richardson TJ, Urbanke R, {\em
%IEEE, Communications Letters, vol.5, no.2, Feb. 2001, pp.58-60.}
%
%\bibitem{David-Mackay2} Richardson TJ, Urbanke R.
%{\em IEEE Transactions on Information Theory, vol.47, no.2, Feb.
%2001, pp.599-618.}
%
%
%\bibitem{Shokrollahi} Luby MG, Mitzenmacher M, Shokrollahi MA,
%Spielman DA, {\em Proceedings of the Thirtieth Annual ACM
%Symposium on Theory of Computing.  ACM. 1998, pp.249-58. New York,
%NY, USA.}
\bibitem{Cover} Cover TM, Thomas JA. {\it Elements of information
theory.}  Wiley. 1991, UK.

\bibitem{Gallager} Gallager RG,  {\em Low Density Parity Check Codes}
Research monograph series {\bf 21} (MIT press), 1963.

\bibitem{Shannon} Shannon CE, A mathematical theory of
communication, {\emph Bell System Technical J.}, {\bf 27},
379-423, 623-656, 1948.

\bibitem{KR} Kanter I and Rosemarin H, (cond-mat-0301005).

\bibitem{KK} Kanter I and Kfir H,
%Statistical mechanical aspects of joint source-channel coding,%
 {\it Europhys. Lett. Vol. 63 No. 2
pp. 310 (July 2003)}.

\bibitem{sourlas} Sourlas N,
%Spin-glass models as error-correcting codes.
{\it Nature, vol.339, no.6227, 29 June 1989, pp.693-5}.

\bibitem{liat} Ein-Dor L, Kanter I, Kinzel W,
%Low autocorrelated multiphase sequences.%
  {\it Physical Review E, vol.65, no.2, Feb.
2002}.

\bibitem{baxter}Baxter RJ, Exactly Solved Models in Statistical
Mechanics, {\emph Academic Press, London}, 1982.

\bibitem{ido-msi} Kanter I,
%The equivalence between discrete-spin Hamiltonians and Ising Hamiltonians with multi-spin interactions,
{\it J. Phys. A, vol. 20 pp. L257 1987}.

\bibitem{LDPC-GF(q)} Davey MC and MacKay DJC,
%Low-density parity check codes over GF(q).
{\it Communications Letters, vol.2, no.6, June 1998, pp.165-7}.

\bibitem{David-Mackay1} MacKay DJC and Davey MC,
{\it Gallager Codes for Short Block Length and High Rate
Applications, Codes, Systems and Graphical Models}, IMA Volumes in
Mathematics and its Applications, Springer-Verlag (2000).

\bibitem{KS} Kanter I, Saad D, {\em Phys. Rev. Let., vol.83,
no.13, 27 Sept. 1999, pp.2660-3.}

\bibitem{KS-Gaussian} Kanter I, Saad D,
%Finite-size effects and error-free communication in Gaussian channels.
{\it j. Phys. A, vol.33, no.8, 3 March 2000, pp.1675-81.}

\bibitem{saad} Kabashima Y, Saad D,
% Statistical mechanics of error-correcting codes.  %
{\it Europhysics Letters, vol.45, no.1, 1 Jan. 1999, pp.97-103}.

\bibitem{saad1} Skantzos NS, van Mourik J,  Saad D and
Kabashima  Y,
%Average and reliability error exponents in low-density-parity-check-codes,
J. Phys. A 36 No 43 (31 October 2003) 11131-11141.

\bibitem{r89} For rate $9/8$, for instance, the chosen construction
for the matrices $A$ and $B$ is as follows. $A$ hase sets of rows
with $1,2,3,5,9$ random non-zero elements per row. the number of
rows from each type is $(m/16,m/4,m/16,m/16,m/16)$, where $m$ is
the number of rows in $A$. The structure of $B$ is the same as
illustrated in Fig. \ref{ks}, but $1.75$ is replaced with $7/9$.
We ran simulations for this construction with $C_1=C_2=0.7$ and
the corresponding entropy is $H_2=0.513$ and $L=9,000$.  The
extrapolation of $t_{med}$ indicates that the threshold of this
code for large $L$ is $f_c \sim 0.057$. In the separation scheme
using {\it optimal compression and error correction schemes} and
with $f_c=0.057 ~(R_{i.i.d}=0.618)$, one can find that the overall
inverse rate of the communication channel is $1/R=0.513/0.618 \sim
0.83$, which is only about $6\%$ below our joint s/c inverse rate
$1/R=8/9 \sim 0.89$.  One must remember that our MN construction
can be further optimized, and the critical channel noise is
expected to be enhanced, $f_c > 0.057$.

\bibitem{median} In practice we define $t_{med}$ to be the average
convergence time of all samples with $t \le$ the median time.

\bibitem{PPM} The PPMZ software used can be downloaded from
www.cbloom.com/src/ppmz.html

\bibitem{AC} The AC software used can be downloaded from
www.cs.mu.oz.au/~alistair/arith\_coder

\bibitem{EM} McLachlan GJ and Krishan T,  The EM Algorithm and
Extension. {\it Wiley Sons, NY, 1997}.

\bibitem{erdos} Erdos P and Reyni A, The Art of Counting,
Edit. by J. Spencer (MIT Press, Cambridge MA , 1973).

\bibitem{haggai1} Kfir H and Kanter I (unpublished).








%\bibitem{turbo} Berrou C, Glavieux A, Thitimajshima P, {\em ICC
%'93 Geneva. IEEE International Conference on Communications '93.
%IEEE. 1993, pp.1064-70 vol.2.}. and Berrou C, Glavieux A,  {\em
%IEEE Transactions on Communications, vol.44, no.10, Oct. 1996,
%pp.1261-71.}







%\bibitem{err_cor_book} Michelson, AM  and Levesque, AH,
%{\it Error-Control Techniques for Digital Communications,} Wiley,
%New York, 1985.
%
%\bibitem{Frey} Frey BJ, {\em Graphical Models for Machine Learning
%and Digital Communication} (MIT Press), 1998.



%\bibitem{shamail1} Kliewer J, Thobaben R, {\it Proceedings DCC
%2002. Data Compression Conference. IEEE Comput. Soc. 2002,
%pp.83-91.  Los Alamitos, CA, USA.}
%
%\bibitem{shamail2} Shamai S, Verdu S, {\it European Transactions on
%Telecommunications \& Related Technologies, vol.6,no.5, Sept.-Oct.
%1995, pp.587-600.}
%
%\bibitem{shamail3} Liveris A, Xiong Z and Georghiades CN,
%{\it Proceedings of Globecom 2002, Taipei, Taiwan, November 17-21
%2002. }
%
%
%\bibitem{shamail4} Garcia-Frias J and  Villasenor JD,
%%Joint Turbo Decoding and Estimation of Hidden Markov Sources
%{\it IEEE J. Selec. Areas Commun., Vol. 19, No. 9, pp. 1671-1679,
%Sept. 2001}.
%
%
%\bibitem{shamail5} C.-C. Zhu and F. Alajaji,
%%Turbo Codes for Non-Uniform Memoryless Sources over Noisy Channels,
%{\it IEEE Communications Letters, Vol. 6, No. 2, pp. 64-66,
%February 2002}.
%
%
%\bibitem{shamail6} Garcia-Frias J , Zhao Y,
%% Compression of binary memoryless sources using punctured turbo codes,
%{\it IEEE Communication Letters, vol.6, no.9, pp.394�396 (2002).}







%\bibitem{sourlas1} Sourlas N,
%%Statistical mechanics and capacity-approaching error-correcting codes.%
% {\it Physica A, vol.302, no.1-4, 15 Dec. 2001, pp.14-21. }



%\bibitem{kinzel} We thank W. Kinzel for his advice to simplify
%the decoder by using the Markovian process.





%\bibitem{MacKay} MacKay DJC and  Neal RM,
%% Near Shannon limit performance of low density parity check codes.
% {\it Electronics Letters, vol.33, no.6, 13 March 1997, pp.457-8}. MacKay DJC,
% % Good error-correcting codes based on very sparse matrices. %
% {\it IEEE Transactions on Information Theory, vol.45, no.2, March 1999,
%pp.399-431. }



%\bibitem{KABA} Nakamura K, Kabashima Y and Saad D,
%%Statistical mechanics of low-density parity-check codes over Galois fields,
%{\it Europhys. Lett., vol.  56, 2001, pp. 610-616}.


%\bibitem{Davey} MacKay D. J. C, Wilson S. T. , Davey M. C.
%%Comparison of constructions of irregular Gallager codes.
% {\it IEEE Transactions on Communications, vol.47, no.10, Oct. 1999,
%pp.1449-54. Publisher: IEEE, USA} M.C.~Davey and D.J.C.~MacKay,
%{\em IEEE Comm. Lett.}, in press (1999).












%\bibitem{domany} Priel A, Blatt M, Grossman T, Domany E, Kanter
%I,
%%Computational capabilities of restricted two-layered perceptrons.
%{\it Physical Review E, vol.50, no.1,
% July 1994,
%pp.577-95.}









%\bibitem{bias} A similar degradation in the performance was observed
%for $q=2$ and biased binary messages (each source bit is equal
%$0/1$ and is chosen with probability $p/1-p$).  As $|p-0.5|$
%increases the entropy decreases and a degradation in the
%performance of the MN algorithm was observed.




%\bibitem{shahar} Shahar K and Kanter I (unpublished).






%\bibitem{manfred} I. Kanter thanks Manfred Opper for the discussion
%on this general result.



%\bibitem{comment} In principle one can generalize the tensor to
%include nearest and next-nearest blocks.

%

%
%\bibitem{kanter1} Kanter I, Sompolinsky H.
%%Mean-field theory of spin-glasses with finite coordination number.
%{\it Phys. Rev. Let., vol.58, no.2, 12 Jan. 1987, pp.164-7.}




\end{thebibliography}