# Spatially Coupled Codes over the Multiple Access Channel

Shrinivas Kudekar1 and Kenta Kasai2

1 New Mexico Consortium and CNLS, Los Alamos National Laboratory, New Mexico,
USA
Email<EMAIL_ADDRESS>2 Dept. of Communications and Integrated Systems,
Tokyo Institute of Technology, 152-8550 Tokyo, Japan.
Email<EMAIL_ADDRESS>
###### Abstract

We consider spatially coupled code ensembles over a multiple access channel.
Convolutional LDPC ensembles are one instance of spatially coupled codes. It
was shown recently that, for transmission over the binary erasure channel,
this coupling of individual code ensembles has the effect of increasing the
belief propagation threshold of the coupled ensembles to the maximum
a-posteriori threshold of the underlying ensemble. In this sense, spatially
coupled codes were shown to be capacity achieving. It was observed,
empirically, that these codes are universal in the sense that they achieve
performance close to the Shannon threshold for any general binary-input
memoryless symmetric channels.

In this work we provide further evidence of the threshold saturation phenomena
when transmitting over a class of multiple access channel. We show, by density
evolution analysis and EXIT curves, that the belief propagation threshold of
the coupled ensembles is very close to the ultimate Shannon limit.

##  I Introduction

It has long been known that convolutional LDPC (or spatially coupled)
ensembles, introduced by Felström and Zigangirov [1], have excellent
thresholds when transmitting over general binary-input memoryless symmetric-
output (BMS) channels. The fundamental reason underlying this good performance
was recently discussed in detail in [2] for the case when transmission takes
place over the binary erasure channel (BEC). In the limit of large $L$ and
$w$, the spatially-coupled LDPC code ensemble $(\mathtt{l},\mathtt{r},L,w)$
[2] was shown to achieve the MAP threshold of $(\mathtt{l},\mathtt{r})$ code
ensemble (see last paragraph in this section for the definition of the
$(\mathtt{l},\mathtt{r},L,w)$ ensemble). This is the reason why they call this
phenomena threshold saturation via spatial coupling. In a recent paper [3],
Lentmaier and Fettweis independently formulated the same statement as
conjecture.

The phenomena of threshold saturation seems not to be restricted to the BEC.
By computing EBP GEXIT curves [4], it was observed in [5] that threshold
saturation also occurs for general BMS channels. In other words, in the limit
of large $\mathtt{l}$ (keeping $\frac{\mathtt{l}}{\mathtt{r}}$ constant), $L$
and $w$, the coupled ensemble $(\mathtt{l},\mathtt{r},L,w)$ achieves
universally the capacity of the BMS channels under belief propagation (BP)
decoding. Such universality is not a characteristic feature of polar codes [6]
and the irregular LDPC codes [7]. According to the channel, polar codes need
selection of frozen bits [8] and irregular LDPC codes need optimization of
degree distributions.

The principle which underlies the good performance of spatially coupled
ensembles has been shown to apply to many other problems in communications,
and more generally computer science. To mention just a few, the threshold
saturation effect (dynamical threshold of the system being equal to the static
or condensation threshold) of coupled graphical models has recently been shown
to occur for compressed sensing [9], and a variety of graphical models in
statistical physics and computer science like the random $K$-SAT problem,
random graph coloring, and the Curie-Weiss model [10]. Other communication
scenarios where the spatially coupled codes have found immediate application
is to achieve the whole rate-equivocation region of the BEC wiretap channel
[11], and to achieve the symmetric information rate for a class of channels
with memory [12].

It is tempting to conjecture that the same phenomenon occurs for transmission
over general multi-user channels. We provide some empirical evidence via
density evolution (DE) analysis that this is indeed the case. In particular,
we compute EXIT curves for transmission over a multiple access channel (MAC)
with erasures. We show that these curves behave in an identical fashion to the
curves when transmitting over the BEC. We compute fixed points (FPs) of the
coupled DE and show that these FPs have properties identical to the BEC case.

For a review on the literature on convolutional LDPC ensembles, we refer the
reader to [2] and the references therein. As discussed in [2], there are many
basic variants of coupled ensembles. For the sake of convenience of the
reader, we quickly review the ensemble $(\mathtt{l},\mathtt{r},L,w)$. This is
the ensemble we use throughout the paper as it is the simplest to analyze.

###  I-A $(\mathtt{l},\mathtt{r},L,w)$ Ensemble [2]

We assume that the variable nodes are at sections $[-L,L]$, $L\in\mathbb{N}$.
At each section there are $M$ variable nodes, $M\in\mathbb{N}$. Conceptually
we think of the check nodes to be located at all integer positions from
$[-\infty,\infty]$. Only some of these positions actually interact with the
variable nodes. At each position there are $\frac{\mathtt{l}}{\mathtt{r}}M$
check nodes. It remains to describe how the connections are chosen. We assume
that each of the $\mathtt{l}$ connections of a variable node at position $i$
is uniformly and independently chosen from the range $[i,\dots,i+w-1]$, where
$w$ is a “smoothing” parameter. In the same way, we assume that each of the
$\mathtt{r}$ connections of a check node at position $i$ is independently
chosen from the range $[i-w+1,\dots,i]$. The design rate of the ensemble
$(\mathtt{l},\mathtt{r},L,w)$, with $w\leq 2L$, is given by

$R(\mathtt{l},\mathtt{r},L,w)=(1-\frac{\mathtt{l}}{\mathtt{r}})-\frac{\mathtt{l}}{\mathtt{r}}\frac{w+1-2\sum_{i=0}^{w}\bigl{(}\frac{i}{w}\bigr{)}^{\mathtt{r}}}{2L+1}.$

A discussion on the above ensemble can be found in [2].

##  II Channel Model, Achievable Rate Region, Iterative Decoding and Factor
Graph

###  II-A Binary Adder Channel with Erasures

We consider the simplest synchronous 2-user multiple access channel, the
binary adder channel (BAC) with erasure. More precisely, the inputs to the MAC
are binary $X_{1},X_{2}\in\\{0,1\\}$. The users take on the values $0,1$ with
equal probability. The subscripts 1,2 denote the two users. The output
$Y\in\\{0,1,2,\text{?}\\}$ is given by

$\displaystyle Y$
$\displaystyle=\left\\{\begin{array}[]{ll}Z=X_{1}+X_{2}&\text{ with
probability }1-\epsilon\\\ \text{?}&\text{ with probability
}\epsilon,\end{array}\right.$

where $\epsilon$ is the fraction of erasures.

###  II-B Achievable Rate Region

We assume that the two users do not coordinate their transmission. This
implies that the joint input distribution has a product form. Let $R_{1}$ and
$R_{2}$ denote the transmission rates of the two users. The achievable rate
region is given as follows.

$\displaystyle R_{1}\leq$ $\displaystyle I(X_{1};Y|X_{2}),$ $\displaystyle
R_{2}\leq$ $\displaystyle I(X_{2};Y|X_{1}),$ $\displaystyle R_{1}+R_{2}\leq$
$\displaystyle I(X_{1},X_{2};Y).$

The mutual information values above can be computed as

$\displaystyle I(X_{1};Y|X_{2})$ $\displaystyle=I(X_{2};Y|X_{1})=1-\epsilon,$
$\displaystyle I(X_{1},X_{2};Y)$ $\displaystyle=\frac{3(1-\epsilon)}{2},$
$\displaystyle I(X_{1};Y)$ $\displaystyle=I(X_{2};Y)=\frac{1-\epsilon}{2}.$

The Shannon limit is defined as the ultimate erasure threshold below which
both users can successfully decode using any decoder. Thus, the Shannon
threshold is given by,

$\displaystyle\epsilon_{\mathrm{Sh}}=\min(1-R_{1},1-R_{2},1-\frac{2}{3}(R_{1}+R_{2})).$
(1)

###  II-C Factor Graph and Iterative Decoding

Figure 1 shows the factor graph representation used in the BP decoder
analysis. The channel output is the vector $\underline{y}$ and the user inputs
are $\underline{x}_{1}$ and $\underline{x}_{2}$. Each user has its own code
and there is a function node which connects the two factor graphs (dark
squares in Figure 1). This function node represents the channel factor node
$p(y_{i}|x_{1,i},x_{2,i})$ and we call it the MAC function node (see [13, 14]
for details). Figure 1 shows the spatially coupled ensemble used by each user.
For the ease of illustration, we show the protograph-based variant of
spatially coupled codes. If we do not use coupled codes for transmission, then
the two protographs above will be replaced by the usual LDPC codes.

$\text{-}L$$\cdots$(60,-10)(9.2,0)[b]$\text{-}4$,$\text{-}3$,$\text{-}2$,$\text{-}1$,$0$,$1$,$2$,$3$,$4$$\cdots$$L$
Figure 1: The figure shows two protograph-based spatially coupled codes (each
belonging to one user) in light gray. The two protographs are connected by the
MAC function node shown in dark. Note that in the actual code the MAC function
node connects each variable node of one user to the corresponding variable
node of the other user. For the ease of illustration, we just show connections
across one-half of the variable nodes.

The BP decoder passes messages between the various nodes in the factor graph.
The message passing schedule involves first passing the channel observations
from the MAC function nodes to the variable nodes of both of the users, then
performing one round of BP for both the users (in parallel) and then sending
the extrinsic information back to the MAC function node (from both the users).

##  III Uncoupled System: Density Evolution, Exit-like Curves

###  III-A Density Evolution

Before we proceed to the analysis of coupled codes, it is instructive to
consider the DE analysis for the uncoupled $(\mathtt{l},\mathtt{r})$-regular
ensemble. More precisely, users 1 and 2 pick a code from the ensemble
$(\mathtt{l}_{1},\mathtt{r}_{1})$-regular and
$(\mathtt{l}_{2},\mathtt{r}_{2})$-regular respectively. From the schedule
given above it is not hard to see that for finite number of iterations and
large blocklengths, the local neighborhood around any node is a tree with high
probability. See [13, 14] for more details on the DE setup. Also, the BAC with
erasures can be thought of as a BEC (for either user) with erasure probability
equal to $\epsilon+(1-\epsilon)\mu/2$, where $\mu$ is the erasure message
flowing into the MAC function node. Indeed, the channel output is either
erased (wp $\epsilon$) or it is not erased (wp $1-\epsilon$) and we are still
uncertain of the transmitted symbol if the output is equal to 1 (occurs wp
1/2) and the other symbol is uncertain (wp $\mu$). The FPs of the DE are then
given by,

$\displaystyle y_{1}$ $\displaystyle=1-(1-x_{1})^{\mathtt{r}_{1}-1},$
$\displaystyle x_{1}$
$\displaystyle=(\epsilon+\frac{1-\epsilon}{2}y_{2}^{\mathtt{l}_{2}})y_{1}^{\mathtt{l}_{1}-1},$
$\displaystyle y_{2}$ $\displaystyle=1-(1-x_{2})^{\mathtt{r}_{2}-1},$
$\displaystyle x_{2}$
$\displaystyle=(\epsilon+\frac{1-\epsilon}{2}y_{1}^{\mathtt{l}_{1}})y_{2}^{\mathtt{l}_{2}-1},$

where $x_{1}(y_{1})$ and $x_{2}(y_{2})$ are variable-to-check (check-to-
variable) erasure messages of user 1 and 2 respectively. Note that if
$\mathtt{l}_{1}=\mathtt{l}_{2}=\mathtt{l}$ and
$\mathtt{r}_{1}=\mathtt{r}_{2}=\mathtt{r}$, then the above equations reduce to
a single parameter equation and is given by

$\displaystyle
x=(\epsilon+\frac{(1-\epsilon)}{2}y^{\mathtt{l}})y^{\mathtt{l}-1},$
$\displaystyle y=1-(1-x)^{\mathtt{r}-1}.$

###  III-B Exit-like Curves

We define the BP EXIT-like111The reason we call this function EXIT-like is
because we do not provide any operational interpretation of these curves like
the Area theorem [13]. The curves are drawn only to illustrate that the BP
performance of coupled codes is close to the Shannon threshold, which is the
main result of the paper. function as follows.

$\displaystyle
h^{\mathrm{BP}}(\epsilon)=\frac{3}{2}y_{1}^{\mathtt{l}_{1}}y_{2}^{\mathtt{l}_{2}}+y_{1}^{\mathtt{l}_{1}}(1-y_{2}^{\mathtt{l}_{2}})+(1-y_{1}^{\mathtt{l}_{1}})y_{2}^{\mathtt{l}_{2}}.$
(2)

An intuitive reason as to why we define the BP EXIT function as above is since
the entropy of $Z_{i}=X_{1,i}+X_{2,i}$ is $H(1/4,1/4,1/2)=3/2$ when a priori
messages from both LDPC codes are erased and since the entropy of $Z_{i}$ is 1
when either of them is erased and the other is not.

Assume that all the FPs are parametrized with $x_{1}$ such as
$(x_{1},y_{1}(x_{1}),x_{2}(x_{1}),y_{2}(x_{1}),\epsilon(x_{1})).$ This
assumption is true if
$(\mathtt{l}_{1},\mathtt{r}_{1})=(\mathtt{l}_{2},\mathtt{r}_{2})=(\mathtt{l},\mathtt{r})$
with

$\displaystyle y_{1}(x_{1})$
$\displaystyle=y_{2}(x_{1})=1-(1-x_{1})^{\mathtt{r}-1},$ $\displaystyle
x_{2}(x_{1})$ $\displaystyle=x_{1},$ $\displaystyle\epsilon(x_{1})$
$\displaystyle=\frac{\frac{x_{1}}{y_{1}(x_{1})^{\mathtt{l}-1}}-\frac{y_{2}(x_{1})^{\mathtt{l}}}{2}}{1-\frac{y_{2}(x_{1})^{\mathtt{l}}}{2}}.$

We then have BP EXIT function as follows

$\displaystyle h^{\mathrm{BP}}(x_{1})=$
$\displaystyle\frac{3}{2}y_{1}(x_{1})^{\mathtt{l}_{1}}y_{2}(x_{1})^{\mathtt{l}_{2}}$
$\displaystyle+y_{1}(x_{1})^{\mathtt{l}_{1}}(1-y_{2}(x_{1})^{\mathtt{l}_{2}})$
$\displaystyle+(1-y_{1}(x_{1})^{\mathtt{l}_{1}})y_{2}(x_{1})^{\mathtt{l}_{2}}.$

We also consider the extended BP EXIT (EBP EXIT) curve which is the plot of
all the fixed points of DE. In the case of codes (of each user) being picked
from the same ensemble, the EBP EXIT-like curve is given by the parametric
curve $(h^{\text{\tiny BP}}(x),\epsilon(x))$, where $x$ is the variable-to-
check node message of either code.

###### Example 1

Figure 2 shows the plot of the EBP EXIT-like curve for
$\mathtt{l}_{1}=\mathtt{l}_{2}=3,\mathtt{r}_{1}=\mathtt{r}_{2}=6$. We choose
this particular example since as seen from above it is easier to evaluate the
value of $\epsilon$ given a fixed value of $x$ (the variable-to-check node
message in either of the code). The BP threshold is $\approx 0.12256$ which is
much less than the Shannon threshold of $1/3$.

(50,-8)(20,0)[cb] ,$0.2$,$0.4$,$0.6$,$0.8$(36,0)(0,30)[l]
,$0.3$,$0.6$,$0.9$,$1.2$$0.0$$\epsilon$

$h^{\text{\scriptsize BP}}$

$\epsilon^{\text{\tiny BP}}\approx 0.12256$

Figure 2: EBP EXIT curve for the case when both users pick a code from the
$(3,6)$ and $(3,6)$. The BP threshold is $\approx 0.12256$ and the Shannon
threshold is $1/3$.

We observe that if we increase the degrees to $(4,8)$ for both the codes, the
BP threshold dramatically drops to zero. Also note the C shape of the EXIT
curve, indicating that there are exactly 3 FPs including a trivial FP plotted
at $(0,\epsilon)$ for each channel value, similar to the BEC case.

##  IV Main Results

In this section, we analyze the performance of coupled codes over BAC with
erasures. We use the $(\mathtt{l}_{1},\mathtt{r}_{1},L,w)$ coupled ensemble
for user 1 and $(\mathtt{l}_{2},\mathtt{r}_{2},L,w)$ ensemble for user 2. As a
shorthand notation we use
$(\mathtt{l}_{1},\mathtt{r}_{1},\mathtt{l}_{2},\mathtt{r}_{2},L,w)$ to denote
both the ensembles. Our main result is that, via DE analysis, the BP threshold
of the coupled ensemble is very close to the Shannon threshold given by (1).
Furthermore, by increasing the degrees, the BP threshold of the coupled
ensemble goes to the Shannon threshold.

Next, we develop the DE equation when transmitting using the coupled codes.

###  IV-A Density Evolution for the
$(\mathtt{l}_{1},\mathtt{r}_{1},\mathtt{l}_{2},\mathtt{r}_{2},L,w)$ ensemble

We develop the DE equations assuming that the two users use ensembles of
different degrees. Consider the
$(\mathtt{l}_{1},\mathtt{r}_{1},\mathtt{l}_{2},\mathtt{r}_{2},L,w)$ ensemble.
To perform the DE analysis, we already take the limit $M\to\infty$ (the number
of variable nodes in each section).

Let $x_{1,i}$, $i\in\mathbb{Z}$, denote the average erasure probability which
is emitted by variable nodes at position $i$ to check nodes at position $i$
for user 1. Similarly define $x_{2,i}$ for the user 2. For $i\not\in[-L,L]$,
we set $x_{1,i}=x_{2,i}=0$. For $i\in[-L,L]$ the DE is given by

$\displaystyle y_{1,i}$
$\displaystyle=1-(1-\frac{1}{w}\sum_{k=0}^{w-1}x_{1,i-k})^{\mathtt{r}_{1}-1},$
$\displaystyle x_{1,i}$
$\displaystyle=\big{(}\epsilon+\frac{1-\epsilon}{2}\big{(}\frac{1}{w}\sum_{j=0}^{w-1}y_{2,i+j}\big{)}^{\mathtt{l}_{2}}\big{)}\big{(}\frac{1}{w}\sum_{j=0}^{w-1}y_{1,i+j}\big{)}^{\mathtt{l}_{1}-1},$
$\displaystyle y_{2,i}$
$\displaystyle=1-(1-\frac{1}{w}\sum_{k=0}^{w-1}x_{2,i-k})^{\mathtt{r}_{2}-1},$
$\displaystyle x_{2,i}$
$\displaystyle=\big{(}\epsilon+\frac{1-\epsilon}{2}\big{(}\frac{1}{w}\sum_{j=0}^{w-1}y_{1,i+j}\big{)}^{\mathtt{l}_{1}}\big{)}\big{(}\frac{1}{w}\sum_{j=0}^{w-1}y_{2,i+j}\big{)}^{\mathtt{l}_{2}-1}.$
(3)

We will use the notation $\epsilon^{\text{\tiny
BP}}(\mathtt{l}_{1},\mathtt{r}_{1},\mathtt{l}_{2},\mathtt{r}_{2},L,w)$ to
denote the threshold of the BP decoder when we use coupled codes for
transmission. Also, we use $\epsilon^{\text{\tiny
BP}}(\mathtt{l}_{1},\mathtt{r}_{1},\mathtt{l}_{2},\mathtt{r}_{2})$ to denote
the BP threshold of the underlying uncoupled ensemble.

As a shorthand we use $g_{1}(x^{1,2}_{i-w+1},\dots,x^{1,2}_{i+w-1})$ to denote
$(\epsilon+\frac{1-\epsilon}{2}(\frac{1}{w}\sum_{j=0}^{w-1}y_{2,i+j})^{\mathtt{l}_{2}})(\frac{1}{w}\sum_{j=0}^{w-1}y_{1,i+j})^{\mathtt{l}_{1}-1}$
and also $g_{2}(x^{1,2}_{i-w+1},\dots,x^{1,2}_{i+w-1})$ to denote
$(\epsilon+\frac{1-\epsilon}{2}(\frac{1}{w}\sum_{j=0}^{w-1}y_{1,i+j})^{\mathtt{l}_{1}})(\frac{1}{w}\sum_{j=0}^{w-1}y_{2,i+j})^{\mathtt{l}_{2}-1}$.

######  Definition 2 (FPs of Density Evolution)

Consider DE for the
$(\mathtt{l}_{1},\mathtt{r}_{1},\mathtt{l}_{2},\mathtt{r}_{2},L,w)$ ensemble.
Let $\underline{x}_{1}=(x_{1,-L},\dots,{x}_{1,L})$ and
$\underline{x}_{2}=(x_{2,-L},\dots,{x}_{2,L})$ denote the vector of variable-
to-check erasure messages for user 1 and 2 respectively. We call
$\underline{x}_{1}$ and $\underline{x}_{2}$ the constellation of user 1 and 2
respectively. We say that $(\underline{x}_{1},\underline{x}_{2})$ forms a FP
of DE with channel $\epsilon$ if $(\underline{x}_{1},\underline{x}_{2})$
fulfills (IV-A) for $i\in[-L,L]$. As a shorthand we then say that
$(\epsilon,\underline{x}_{1},\underline{x}_{2})$ is a FP. We say that
$(\epsilon,\underline{x}_{1},\underline{x}_{2})$ is a non-trivial FP if either
$\underline{x}_{1}$ or $\underline{x}_{2}$ is not identically equal to
$0\,\,\forall\,i$. Again, for $i\notin[-L,L]$, $x_{1,i}=x_{2,i}=0$. ∎

######  Definition 3 (Forward DE and Admissible Schedules)

Consider forward DE for the
$(\mathtt{l}_{1},\mathtt{r}_{1},\mathtt{l}_{2},\mathtt{r}_{2},L,w)$ ensemble.
More precisely, pick a channel $\epsilon$ and initialize
$\underline{x}^{(0)}_{1}=\underline{x}^{(0)}_{2}=(1,\dots,1)$. Let
$\underline{x}^{(\ell)}_{1}$ and $\underline{x}^{(\ell)}_{2}$ be the result of
$\ell$ rounds of DE for user 1 and 2 respectively. More precisely,
$\underline{x}^{(\ell+1)}_{1}$ and $\underline{x}^{(\ell+1)}_{2}$ are
generated from $\underline{x}^{(\ell)}_{1}$ and $\underline{x}^{(\ell)}_{2}$
by applying the DE equation (IV-A) to each section $i\in[-L,L]$,

$\displaystyle x_{1,i}^{(\ell+1)}$
$\displaystyle=g_{1}(x_{i-w+1}^{1,2,(\ell)},\dots,x_{i+w-1}^{1,2,(\ell)}),$
$\displaystyle x_{2,i}^{(\ell+1)}$
$\displaystyle=g_{2}(x_{i-w+1}^{1,2,(\ell)},\dots,x_{i+w-1}^{1,2,(\ell)}),$

where we use the notation $x_{i}^{1,2,(\ell)}$ to denote
$(x_{1,i}^{(\ell)},x_{2,i}^{(\ell)})$. We call this the parallel schedule.

More generally, consider a schedule in which in each step $\ell$ an arbitrary
subset of the sections is updated, constrained only by the fact that every
section is updated in infinitely many steps. We call such a schedule
admissible. Again, we call $\underline{x}^{(\ell)}_{1}$ and
$\underline{x}^{(\ell)}_{2}$ the resulting sequence of constellations. ∎

One can show that if we perform forward DE under any admissible schedule, then
the constellations $\underline{x}^{(\ell)}_{1}$ and
$\underline{x}_{2}^{(\ell)}$ converge to a FP of DE and this FP is independent
of schedule. This statement can be proved similar to the one in [2, 13].

For the case when $\mathtt{l}_{1}=\mathtt{l}_{2}$ and
$\mathtt{r}_{1}=\mathtt{r}_{2}$ we have that for any FP, $x_{1,i}=x_{2,i}$ and
$y_{1,i}=y_{2,i}$ for all $i$.

###  IV-B Forward DE – Simulation Results

In the examples below, the Shannon threshold is computed using equation (1).

######  Example 4 (Equal Degrees – BP goes to Shannon)

We consider forward DE for the coupled ensembles. More precisely, we fix an
$\epsilon$ and initialize all $x_{1,i}$ and $x_{2,i}$ to 1, for $i\in[-L,L]$.
Then we run the DE given by (IV-A) till we reach a fixed-point. We fix
$L=200$. For $\mathtt{l}_{1}=\mathtt{l}_{2}=3$ and
$\mathtt{r}_{1}=\mathtt{r}_{2}=6$, we have that $\epsilon^{\text{\tiny
BP}}(3,6,3,6,200,3)\approx 0.332287$. If we increase the degrees we get
$\epsilon^{\text{\tiny BP}}(4,8,4,8,200,4)\approx 0.333195$,
$\epsilon^{\text{\tiny BP}}(5,10,5,10,200,5)\approx 0.333286$. We observe that
by increasing the degrees the BP threshold approaches the Shannon threshold of
$1/3$. On the other hand for the uncoupled codes, $\epsilon^{\text{\tiny
BP}}(3,6,3,6)\approx 0.12256$ and for larger degrees the BP threshold is zero.

######  Example 5 (Unequal Degrees – BP goes to Shannon)

We also consider the more general case when the degrees are not equal. For
$\mathtt{l}_{1}=5,\mathtt{r}_{1}=10$ and $\mathtt{l}_{2}=6,\mathtt{r}_{2}=13$
we get $\epsilon^{\text{\tiny BP}}(5,10,6,13,500,10)\approx 0.307647$. The
Shannon threshold in this case is equal to $\approx 0.307692$. For
$\mathtt{l}_{1}=9,\mathtt{r}_{1}=10$ and $\mathtt{l}_{2}=6,\mathtt{r}_{2}=10$
we get $\epsilon^{\text{\tiny BP}}(9,10,6,10,500,10)\approx 0.59992$ and the
Shannon threshold is $=0.6$.

###  IV-C EXIT curve plots

We also show via EXIT analysis that the coupling of regular LDPC codes pushes
the BP threshold (of the coupled systems) to the Shannon threshold. For the
purpose of illustration of the threshold saturation phenomena we focus only on
the case when $\mathtt{l}_{1}=\mathtt{l}_{2}$ and
$\mathtt{r}_{1}=\mathtt{r}_{2}$. Thus, the variable-to-check node messages,
for any FP of DE, for both the users are equal (cf. (IV-A)). Now, to plot the
EBP EXIT curve, which is essentially the plot of all the fixed-points of DE,
we define the entropy of a constellation as

$\displaystyle\chi=\frac{1}{2L+1}\sum_{i=-L}^{L}x_{1,i}.$

To plot all the FPs of DE, we first fix a value of $\chi\in[0,1]$ and then run
the reverse DE process given in [4]. Briefly, we start with an initial
variable-to-check message and run it through the check node. Then the
appropriate channel value is found such that the resulting constellation has
entropy equal to $\chi$. This process is run till we get an FP. Figure 3 shows
the plot of the EBP EXIT curve for the $(3,6,3,6,L,3)$ ensemble with
$L=2,4,8,16,32,64,128,256$. We observe that the plot looks very similar to the
case of single user transmission over a BEC. For small values of $L$ there is
a large rateloss and the EBP EXIT curve is to the right. As $L$ increases, the
rateloss diminishes and the curves move to the left. The limiting BP EXIT
curve of the coupled system looks very similar to when we are transmitting
over the BEC. It traces the BP EXIT function of the underlying uncoupled codes
until the channel erasure value is very close to the Shannon threshold and
then drops vertically to almost zero entropy.

(50,-8)(20,0)[cb] ,$0.2$,$0.4$,$0.6$,$0.8$(36,0)(0,30)[l]
,$0.3$,$0.6$,$0.9$,$1.2$$0.0$$\epsilon$

$h^{\text{\scriptsize BP}}$

Figure 3:  The EBP EXIT curve for $(3,6,3,6,L,3)$ with
$L=2,4,8,16,32,64,128,256$. The curve with light gray background is the BP
EXIT curve for the uncoupled $(3,6,3,6)$ ensemble. We see that as $L$
increases the EBP EXIT curves of the coupled system moves to the left. The BP
threshold of the coupled system is $\approx 0.3323$ which is very close to the
Shannon threshold.

###  IV-D Shape of the Constellation

Figure 4 shows the constellation of an unstable FP (which cannot be reached by
BP). This FP is obtained via the reverse DE process. This special FP was the
key ingredient in proving threshold saturation over the BEC [2]. Let us
describe the (empirically observed) crucial properties of this constellation.

  * (i)

The constellation is symmetric around $i=0$ and is unimodal. The constellation
has $\epsilon\approx 0.3323$, which is close to the Shannon threshold of
$1/3$.

  * (ii)

The value in the flat part in the middle is $\approx 0.6548$ which is very
close to the stable FP of DE for the underlying uncoupled $(3,6)$-regular
ensemble at $\epsilon\approx 0.3323$.

  * (iii)

The transition from values close to zero to values close to $0.6548$ is very
quick.

(6,0)(14.4,0)[b]$\text{-}16$,$\text{-}14$,$\text{-}12$,$\text{-}10$,$\text{-}8$,$\text{-}6$,$\text{-}4$,$\text{-}2$,0,2,4,6,8,10,12,14,16
Figure 4:  The unstable FP shown above has an entropy of $0.28$ and is
obtained via reverse DE. The constellation is symmetric around $0$ and is
unimodal. The flat middle part has value close to $0.6548$ which is the value
of stable FP for the uncoupled system at $\epsilon\approx 0.3323$. Both the
users have identical FP constellation.

##  V Discussion

In this paper we show that, by using coupled regular LDPC codes when
transmitting over the 2 user BAC with erasures, the BP threshold can be made
very close to the Shannon threshold. In this sense, the coupled codes are
threshold saturating. We demonstrate this by plotting EXIT-like curves. The
behavior of these curves is very similar to when transmitting over the BEC.
Even the shape of the constellation of an unstable FP of DE is same as the BEC
case. Thus we believe one should be able to provide a proof of this phenomena
on the lines of the BEC proof [2].

Another interesting question is to determine area theorems which will also
further show that the BP threshold of the coupled system goes to the MAP
threshold of the underlying uncoupled codes, when we consider finite degrees.
To do this we would need to define an appropriate EXIT function.

Lastly, it would be interesting to see if we can demonstrate the threshold
saturation phenomena to more general MAC channels, like the 2 user BAC with
additive Gaussian noise.

##  VI Acknowledgments

SK acknowledges support of NMC via the NSF collaborative grant CCF-0829945 on
“Harnessing Statistical Physics for Computing and Communications.” SK would
also like to thank Rüdiger Urbanke for his encouragement.

## References

  * [1] A. J. Felström and K. S. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix,” _IEEE Trans. Inform. Theory_ , vol. 45, no. 5, pp. 2181–2190, Sept. 1999.
  * [2] S. Kudekar, T. Richardson, and R. Urbanke, “Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC,” 2010, e-print: http://arxiv.org/abs/1001.1826.
  * [3] M. Lentmaier and G. P. Fettweis, “On the thresholds of generalized LDPC convolutional codes based on protographs,” in _Proc. of the IEEE Int. Symposium on Inform. Theory_ , Austing, TX, USA, June 2010, pp. 709–713.
  * [4] C. Méasson, A. Montanari, T. Richardson, and R. Urbanke, “The generalized area theorem and some of its consequences,” _IEEE Trans. Inform. Theory_ , vol. 55, no. 11, pp. 4793–4821, Nov. 2009.
  * [5] S. Kudekar, C. Méasson, T. Richardson, and R. Urbanke, “Threshold saturation on BMS channels via spatial coupling,” Apr. 2010, e-print: http://arxiv.org/abs/1004.3742.
  * [6] E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Trans. Inform. Theory_ , vol. 55, no. 7, pp. 3051–3073, 2009.
  * [7] T. Richardson, A. Shokrollahi, and R. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” _IEEE Trans. Inform. Theory_ , vol. 47, no. 2, pp. 619–637, Feb. 2001.
  * [8] R. Mori and T. Tanaka, “Performance and construction of polar codes on symmetric binary-input memoryless channels,” Jan. 2009, http://arxiv.org/abs/0901.2207.
  * [9] S. Kudekar and H. D. Pfister, “The effect of spatial coupling on compressive sensing,” in _Proc. of the Allerton Conf. on Commun., Control, and Computing_ , Monticello, IL, USA, 2010.
  * [10] S. H. Hassani, N. Macris, and R. Urbanke, “Coupled graphical models and their thresholds,” in _Proc. of the IEEE Inform. Theory Workshop_ , Dublin, Ireland, Sept. 2010.
  * [11] V. Rathi, R. Urbanke, M. Andersson, and M. Skoglund, “Rate-equivocation optimally spatially coupled LDPC codes for the BEC wiretap channel,” 2010, e-print: http://arxiv.org/abs/1010.1669.
  * [12] S. Kudekar and K. Kasai, “Threshold Saturation on Channels with Memory via Spatial Coupling,” 2011, e-print: http://arxiv.org/abs/0211.1669.
  * [13] T. Richardson and R. Urbanke, _Modern Coding Theory_. Cambridge University Press, 2008.
  * [14] A. Amraoui, S. Dusad, and R. Urbanke, “Achieving general points in the 2-user Gaussian MAC without time-sharing or rate-splitting by means of iterative coding,” in _Proc. of the IEEE Int. Symposium on Inform. Theory_ , Lausanne, Switzerland, June 2002, conference, p. 334.