Spatially Coupled
Repeat-Accumulate Coded Cooperation
Naoki Takeishi and Koji Ishibashi
Advanced Wireless Communication Research Center (AWCC)The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, Japan
Email: takeishi@awcc.uec.ac.jp, koji@ieee.org

Abstract—In this paper, a new coded cooperation scheme called
spatially coupled repeat-accumulate coded cooperation (SC-RACC) is proposed for multiple access channels (MAC) with a large
number of users and one common destination. The proposed
approach combines two advantages of repeat-accumulate (RA)codes and spatial coupling. RA codes show the superior decoding
performance with the simple encoding and spatial coupling exhibits the so-called threshold saturation behavior; the threshold ofcoupled codes with sub-optimal belief propagation (BP) decoding
asymptotically achieves the optimal maximum a posterior (MAP)
decoding threshold. Our SC-RA-CC can be considered as the
distributed version of spatially coupled repeat-accumulate codes
which provide the higher spatial diversity and coding gain whenboth the number of users and the size of packets are limited. The
performance of the proposed coded cooperation is analyzed via
density evolution (DE). Numerical results confirm that SC-RACC can efficiently obtain even higher diversity and coding gain
than both direct transmission and conventional adaptive network
coded cooperation (ANCC).
Index Terms—Wireless sensor networks (WSNs), repeataccumulate codes, spatially coupled codes, coded cooperation,
density evolution.

I. I NTRODUCTION
Multiple access channels (MAC) with a large number ofusers and one common destination have been actively investigated to design many-to-one wireless communications systems
such as wireless sensor networks (WSNs) for environmental
monitoring, disaster prevention, and so on [1]. The information
should be reliably and efficiently transmitted over the wirelesschannels while the channels are typically unreliable due tothe multipath fading. When the channel coherence time islonger than a transmission frame, i.e., flat fading, and thesignal power at the destination is deeply faded, the channel
coding does not help anymore. The use of multiple antennas at
the transmitter and/or receiver side can effectively mitigate theeffect of fading even in flat fading channels [2, 3]. However, formany applications such as WSNs, the deployment of multiple
antennas is too costly in terms of size and power consumption.
To this end, cooperative diversity protocols such as amplifyand-forward (AF) and decode-and-forward (DF) protocols
have been proposed, which demonstrate a potential to achieve
a diversity gain or enhance the capacity of wireless systems
without deploying multiple antennas at every nodes [4]. Furthermore, coded cooperation has been proposed to obtain not
only the spatial diversity gain but also the coding gain throughthe cooperation [5]. Due to the half duplex constraint, theprotocol of coded cooperation is composed of two steps; at thefirst step, all transmit nodes sequentially broadcast their information packets. At the second step, every node independently
encodes a parity packet based on the others’ packets correctly
decoded at the first step and transmits it to the destination. At
the destination, every information packet and corresponding
parity packet composes a codeword where parity packets
are transmitted over mutually independent wireless channels.
Coded cooperation, hence, can enjoy both the spatial diversity
gain and coding gain.
Adaptive network coded cooperation (ANCC) has beensubsequently proposed for a large-scale network with a large
number of transmit nodes [6]. The idea of ANCC is to
dynamically map the subgraph of the network topology to
the graph of codes by randomly XORing several packets outof the successfully received ones. The resulting codes form
the low-density generator-matrix (LDGM) codes which is a
special class of low-density parity-check (LDPC) codes [7].
Although the sufficiently long codeword length is necessary
to enhance the decoding performance of LDGM codes [8],the codeword length of ANCC is given by the double of thenumber of transmit nodes, regardless of the size of information
packets. Therefore, if the number of transmit nodes is limited,the decoding performance of ANCC would have a large gap
from the theoretical limit of the underlying codes. Moreover,in order to decode these coded packets, the destination shouldhave the knowledge of entire underlying graph. In practice, theoverhead informing such information becomes considerablylarge which leads to the loss of bandwidth efficiency of thesystem. The question that may arise here is how to achieve
the decoding performance approaching to the channel capacitywith practical encoding and decoding complexity when boththe number of users and the length of information packets arelimited.
In this paper, we propose a new coded cooperation scheme
named spatially coupled repeat-accumulate coded cooperation(SC-RA-CC). Repeat-accumulate (RA) codes have been proposed in [9] as turbo-like codes, which show the decoding performance comparable to turbo codes [10] while its encoding
complexity is lower. More recently, spatially coupled LDPC
code has been proposed in [11]. The remarkable inventionof this code is spatial coupling that exhibits the so-called
threshold saturation behavior; the threshold of coupled codeswith sub-optimal BP decoding asymptotically achieves the

(t)

1!

ǫ1,2

2!

(t)

ǫ2,N +1
(t)

ǫ3,1

N+1!
(t)

3!

(t)

N!

ǫN,N +1

ǫN,3
Fig. 1. System model of cooperative network consisting of N transmit nodes
and a common destination.

Fig. 2.

Triangle distribution for evaluate spatial diversity.

optimal maximum a posterior (MAP) decoding threshold.
Based on these seminal works, spatially coupled RA codes
have been proposed to combine two advantages of RA codesand spatial coupling, namely low complexity encoding andsignificantly superior decoding performance [12]. SC-RA-CC
can be considered as a distributed version of spatially coupled
repeat-accumulate codes while the proposed approach stillshows the superior decoding performance close to the channel
capacity even when both the number of users and the lengthof information packets are limited.
This paper is organized as follows. In Section II, we
briefly describe the system model assumed in this paper. The
encoding protocol of proposed SC-RA-CC is described in
Section III. In Section IV, the threshold of SC-RA-CC withBP decoding is theoretically analyzed by using the density
evolution. In Section V, computer simulations are performed
to confirm the analytical results and compare the performanceof SC-RA-CC with the direct transmission and conventional
ANCC. Finally, Section VI concludes this work.
II. S YSTEM M ODELIn this paper, we consider a network with N transmit nodes
and a common destination as illustrated in Fig. 1. Each nodeis equipped with a single antenna and subject to the halfduplex constraint. Thus, we assume that while listening to thechannel, the node may not transmit. Each node sequentiallytransmits their own packets to the common destination basedon the time division multiple access (TDMA). We here define
a transmission block as a time period that N nodes transmit
their own packets and assume that every node transmits T
different packets through T transmission blocks.
In this paper, wireless channels are modeled as binary
erasure channel (BEC). This model simplifies the mathematical analysis of error-correcting codes. Moreover, in orderto model the effect of slow fading, we assume that the bit
erasure probability does not change during T consecutive
transmission blocks. In typical cooperative communications,the transmit nodes are closely-placed and thus the average
received signal power at the transmit nodes is even higher thanthat at the destination. Therefore, we assume that the channels
between the transmit nodes are ideally error-free for simplicity.
Then, bit erasure probability from node i ∈ {1, 2, · · · , N } toj ∈ {1, 2, · · · , N + 1} at transmission block t = 1, 2, · · · , T
can be written as{
0 (1 ≤ j ≤ N )(t)ϵi,j =.
(1)
ϵi (j = N + 1)
Here (N + 1) is a index of the destination node and ϵidenotes the bit erasure probability of the channel between
node i to the destination node. Note that, in coded cooperation,(T + 1) transmission blocks are needed to transmit T different
information packets of every user, which will be explained indetail in the next section.
To evaluate the coding gain and diversity gain obtainedby our proposed approach, we consider the following two
different channel models.
1) Constant Channel Model: In this model, the erasureprobability of every channel link between node i to thedestination is given by a constant erasure probability ϵ, namely
ϵi = ϵ. This channel model is suitable to evaluate the purecoding gain obtained by the proposed approach.
2) Triangle Distribution Channel Model: As mentioned
above, coded cooperation aims to exploit not only the coding
gain but also the spatial diversity gain. To evaluate the potentialof spatial diversity enhancement of proposed cooperation, theconstant channel model is inadequate since the model does nothave any difference between different channel links. Thus, we
further introduce a triangle distribution channel model which
can be considered as a simplified fading model. In this model,
erasure probability is characterized by the triangle distributionof which probability density function (pdf) f (x) is given by{2x
0 ≤ x ≤ 3ϵ − 1
f (x) = 3ϵ−1.
(2)2(x−1)
3ϵ − 1 < x ≤ 1
3ϵNote that the average erasure probability ϵ in this model shouldbe 13 ≤ ϵ ≤ 23 . Figure 2 illustrates the pdf with ϵ = 1.3/3 asan example.
III. S PATIALLY C OUPLED R EPEAT-ACCUMULATE C ODEDC OOPERATIONIn this section, the encoding of SC-RA-CC is explained.
Moreover, two different graph expressions of SC-RA-CC are

(t)

u1

(t)

πi,1

t=1

′(t)
(t)

Source(t)uj

Demodulator

si

i=1

i=2

i=4

i=3

i=1

i=2

′(t)

(t)

uj

πi,j

(t)

uN

t=2

u1

Combiner

′(t)

(t)

(t)

(t)

pi

vi

D

uN

πi,N

(1)

(1)

(1)

π4,1 π4,2 π4,3

(2)

(2)

(2)

π1,2 π1,3 π1,4Fig. 3. Encoding block diagram of SC-RA-CC for the transmit node i at
the tth transmission block.

given so as to elaborate the structure of SC-RA-CC achieving
the superior performance.
Fig. 4. Tanner-graph of SC-RA-CC with K = 3 and N = 4 where parity
bits of user 4 at t = 1 and user 1 at t = 2 are only illustrated.

A. Encoding
Encoding block diagram of transmit nodes i at the tth(t)transmission block is illustrated in Fig. 3. Let si denote Kbit information packet generated by transmit node i at the(t)
tth transmission block. A K-bit binary vector uj indicatesthe latest information packet transmitted by node j at the tthtransmission block and thus it can be rewritten by{(t)sj(j < i)
(t)
.
(3)
uj =
(t−1)
sj
(j > i)
(t)

t=1
t=2
t=3
i=1 i=2 i=3 i=4 i=1 i=2 i=3 i=4 i=1 i=2 i=3

+

+

+

+

+

+

+

+

+

Fig. 5.

Protograph of SC-RA-CC with N = 4 and T = 2.

+(t)

The vector uj is interleaved by corresponding interleaver πi,j′(t)
and the resulting binary vector is denoted by uj . Note that(t)
the interleaver πi,j is mutually and stochastically independentof ones with different t, i, and j. As observed in the figure,every transmission block, the transmit node i has (N − 1)interleaved vectors. These (N − 1) vectors are combined into(t)a K-bit vector vi by the following equation:
(t)

vi =

N
⊕

′(t)

uj ,

(4)

j=1
j̸=i

⊕
where
expresses bit-by-bit XOR operation. Finally, a K(t)bit parity packet pi is obtained by differentially encoding(t)the vector vi as illustrated in Fig. 3. The node i transmits(t)(t)
si and pi as its own message to the destination at the tthtransmission block.
Note that, at the first transmission block i.e., t = 1, first(N − 1) transmit nodes do not have (N − 1) information
packets from the others to calculate (4). In this case, node jjust encodes (j − 1) packets. Similarly, at the last transmission
block i.e., t = T + 1, transmit nodes do not have new
information packets anymore but the transmit node j has(N − j) packets to be encoded. Also note that the last user
j = N at the last transmission block t = T + 1 does not haveany packets to transmit. Therefore, the resulting coding rateNof SC-RA-CC R is calculated as R = 2T NT+N
−2 .

B. Graph Expressions of SC-RA-CC
To clearly show the structure of SC-RA-CC, we here
introduce a representation of bipartite graph called Tannergraph. Figure 4 is a Tanner-graph of SC-RA-CC with N = 4
and K = 3 at the arbitrary transmission block t wherecircles indicate variable nodes corresponding to coded bits andsquares indicate check nodes corresponding to a single parity
check constraint. Also, white and black circles respectively
indicate information and parity bits. Note that, in Fig. 4, parity
bits of user 4 at t = 1 and user 1 at t = 2 are only illustrated
for simplicity.
As explained above, every transmit node utilizes (N − 1)
information packets to encode the parity packet. The parity
of node 4 is obtained by XORing the interleaved information
bits of three users. Subsequently, node 1 would combine three
information packets with corresponding interleavers to encode
the parity packet at the next transmission block.
To further elaborate the structure of SC-RA-CC, we introduce a protograph [13] of SC-RA-CC. Figure 5 shows the
protograph with N = 4 and T = 2. The graph has whiteand black circles respectively indicating K-bit information
packets and parity packets, i.e., variable nodes. Also, squarenodes indicate check nodes. Note that the edges between

white variable nodes and check nodes include the operationof random permutation (cf., Fig 4). As obvious from thefigure, check nodes are connected with spatially-close variablenodes and check nodes on both ends of the graph have lessedges than those in the center. The corresponding variablenodes of check nodes with less edges would be successfully
decoded with high probability and this phenomenon would be
propagated to nodes in the center with the aid of BP decoder[14], which results in the superior performance of SC-RA-CC.
Also, transmit node 1 at the first transmission block t = 1
does not have the parity packet and transmit node 4 at the lasttransmission block t = 3 do not have any packets to transmit
as described in Section III-A.
This protograph representation clearly explains how thecooperation exploits the network structure to construct thecode even when the number of users and the length of information packet are limited. Different from ANCC, spatiallycoupled parity packets of SC-RA-CC contribute the decodingof N × T information packets and thus SC-RA-CC canefficiently construct the long codeword enough.
It is also worth noting that the SC-RA-CC does not require
the overhead to inform the XOR operation of every transmit
node. Different from ANCC, every nodes always combine all
the received packets without randomly choosing them.
IV. D ENSITY E VOLUTION A NALYSIS
In this section, the decoding threshold of SC-RA-CC isanalyzed by density evolution [15].
1) Constant Channel: Density evolution tracks average
bit erasure probability of every packets upon BP decoding.
As obvious from the protograph of SC-RA-CC described in
Section III-B, variable nodes corresponding to information
packets and parity packets have the different number of edges.
Thus, we separately derive the bit erasure probability of thesenodes.
Upon l iterations of BP decoding, bit erasure probability
(l+1)
(l+1)
of information packet xt,iand parity packet yt,iarerespectively calculated by
(
(
N −1
1 ∑
(l+1)
xt,i = ϵi
1 − (1 − µ(y, i + j))2 ×
N − 1 j=1
(5)))N −2N−1∏(1 − µ(x, i + j − k))k=1,j̸=kand(l+1)
yt,i = ϵi(
1 − (1 − µ(y, i)) ×

N
−1
∏

)
(1 − µ(x, i − k)) , (6)k=1

where the function µ(α, β) calculates the index of α by (l)
αt−1,β+N (β ≤ 0)(l)µ(α, β) = αt,β(7)(0 < β ≤ N ) .
 (l)αt+1,β−N (N ≤ β)

Fig. 6.

BER versus bit erasure probability ϵ graph on constant channel.

The decoding threshold of BP decoding ϵth is defined as{}(l)ϵth ≜ sup ϵ > 0 lim x∀t,∀i = 0(8)l→∞

For the erasure probability below this threshold, decoding
erasure probability goes to zero. Finally, the bit erasure probability ϵ is simply used instead of ϵi for the constant channel.
2) Triangle Distribution Channel: To evaluate the achievable diversity gain of cooperation, we evaluate the outage
probability rather than ϵth averaged over the channel realization where the outage event occurs when the decoding erasureprobability does not go to zero upon decoding. Thus outage
probability can be defined as
[ (
)]
(l)
Po ≜ E Pr lim x∀t,∀i > 0 .
(9)l→∞

The outage probability of direct communication is simply
calculated by
[∫ th
]
ϵ
Po = Ef (x)dx ,(10)0where the function f (x) is given by (2) and ϵth is calculated by(8). Also, the outage probability of SC-RA-CC is numericallycalculated using (5) and (6).
V. N UMERICAL R ESULTS
In this section we shows numerical results of computer
simulation and density evolution analysis. In the following, we
assume that T = 20 and the maximum number of iterations
in every BP decoding is 300.
A. Constant Channel
Figure 6 shows the bit erasure rate (BER) of direct communication, SC-RA-CC, and conventional ANCC [6] where
the length of information packets is assumed to be K = 100,
300, and 500 and the number of transmit nodes is assumed
to be N = 4 and 8. For ANCC, the degree D is set to be 2
that is optimized via computer simulations. Theoretical limits

Fig. 7. DER versus average bit erasure probability ϵ over triangle distributed
channels.

Fig. 8. BER versus average bit erasure probability ϵ over triangle distributed
channels.

of SC-RA-CC with N = 4 and 8 are also presented, which
are calculated by (8). Note that the coding rate of SC-RA-CC
with N = 4 and 8 and conventional ANCC is 0.494, 0.491,
and 0.5, respectively.
Comparing with the direct transmission and conventional
ANCC, SC-RA-CC significantly improves the decoding performance because of high coding gain. Also, SC-RA-CC
provides the lower BER as K increases since the codeword
length of SC-RA-CC is proportional to both the length of
information packets and the number of users while that of
ANCC only depends on the number of users. However, gaps
between simulation results and decoding thresholds obtainedby density evolution are still observed, which are about 0.04.
This is because, in the calculation of density evolution, theinfinite codeword length is assumed while the codeword lengthin simulations is limited.
The performance of N = 4 exhibits the error floor evenwhen K = 500. SC-RA-CC couples (N − 1) information
packets as explained in Section III-B. This structure efficiently
retrieves the erased bits from the end points to the center ofthe protograph. However, if the coupling is too weak (namely
N is small), the performance improvement via BP decoding
would be limited and the SC-RA-CC would exhibit the error
floor.

communication and ANCC achieve the better performance at
the high erasure probability region. In SC-RA-CC, the BP
decoder retrieves the information from the end points to thecenter. The BP decoding, however, would stop when facingwith burst erasures [16]. This phenomenon results in worse
DER performance at the high erasure probability region. Also,
as similar to the case with constant channel, the higher coding
gain can be obtained by increasing N .
Finally, Fig. 8 shows the BER performance of directcommunication, conventional ANCC, and SC-RA-CC with
N = 4 and 8 over triangle distribution channels. Different
from all the results shown above, the SC-RA-CC with small
N provides the lower BER performance. When facing withthe burst erasures, the BP decoding of SC-RA-CC causes
more bit erasures in the codeword. When large N is utilized,
the resulting protograph becomes sensitive to burst erasures.
To overcome this issue, an attractive option is the use ofmulti-dimensional spatial coupling [16] or irregularly spatial
coupling like Luby transform (LT) codes [17], which still
remains as the future work.

B. Triangle Distribution Channel
Figure 7 shows the decoding error rate (DER) of directcommunication, conventional ANCC, and SC-RA-CC with
N = 4 and 8 versus average bit erasure probability ϵ ofthe triangle distribution channel where the decoding error isdefined that the decoded codeword includes at least one bit
erasure. In the following, the length of information packet K
is 100. The outage probabilities of direct communication and
SC-RA-CC are also drawn in the figure.
As obvious from the figure, owing to the diversity gain,
the slope of SC-RA-CC is steeper than that of direct communication and conventional ANCC meanwhile the direct

VI. C ONCLUSION
In this paper, we proposed SC-RA-CC and numerical results confirmed that SC-RA-CC can significantly improve thedecoding performance even when the number of nodes andthe length of information packets are limited.
ACKNOWLEDGMENT
This work was supported in part by JSPS KAKENHI Grant
Number 24760295.
R EFERENCES[1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey
on sensor networks”, IEEE Commun. Mag., vol. 40, no. 8, pp. 102–114,
Aug 2002.
[2] L. Zheng and D.N.C. Tse, “Diversity and multiplexing: a fundamental
tradeoff in multiple-antenna channels”, IEEE Trans. Inf. Theory., vol.
49, no. 5, pp. 1073–1096, May 2003.

[3] V. Tarokh, H. Jafarkhani, and A.R. Calderbank, “Space-time block codesfrom orthogonal designs”, IEEE Trans. Inf. Theory., vol. 45, no. 5, pp.
1456–1467, Jul 1999.
[4] C. Deqiang and J. Laneman, “Modulation and demodulation for cooperative diversity in wireless systems”, IEEE Trans. Wireless Commun.,vol. 5, no. 7, pp. 1785–1794, July 2006.
[5] T.E. Hunter and A. Nosratinia, “Diversity through coded cooperation”,
IEEE Trans. Wireless Commun., vol. 5, no. 2, pp. 283–289, Feb 2006.
[6] X. Bao and J. Li, “Adaptive network coded cooperation (ANCC)
for wireless relay networks: matching code-on-graph with network-ongraph”, IEEE Trans. Wireless Commun., vol. 7, no. 2, pp. 574–583,
February 2008.
[7] R.G. Gallager, “Low-density parity-check codes”, IRE Trans. Inf.
Theory., vol. 8, no. 1, pp. 21–28, January 1962.
[8] J. Hou, P.H. Siegel, and L.B. Milstein, “Performance analysis andcode optimization of low density parity-check codes on rayleigh fading
channels”, IEEE J. Sel. Areas Commun., vol. 19, no. 5, pp. 924–934,
May 2001.
[9] D. Divsalar, H. Jin, and R. J. McEliece, “Coding theorems for turbolike
codes”, Proc.36th Allerton Conf. on Commun. Control andComput., pp. 201–210, September 1998.
[10] C. Berrou, A Glavieux, and P. Thitimajshima, “Near Shannon limit
error-correcting coding and decoding: Turbo-codes. 1”, in Proc. IEEE
Int. Conf. Commun., Geneva, Switzerland, May 1993, vol. 2, pp. 1064–
1070 vol.2.
[11] A. Jimenez Felstrom and K.S. Zigangirov, “Time-varying periodic
convolutional codes with low-density parity-check matrix”, IEEE Trans.
Inf. Theory., vol. 45, no. 6, pp. 2181–2191, Sep 1999.
[12] S. Johnson and G. Lechner, “Spatially coupled repeat-accumulate
codes”, IEEE Commun. Lett., vol. 17, no. 2, pp. 373–376, February
2013.
[13] J. Thorpe, “Low-density parity-check (LDPC) codes constructed fromprotographs”, JPL INP, Tech. Rep. 42-154, Aug 2003.
[14] F.R. Kschischang, B.J. Frey, and H.-A Loeliger, “Factor graphs and thesum-product algorithm”, IEEE Trans. Inf. Theory., vol. 47, no. 2, pp.
498–519, Feb 2001.
[15] T.J. Richardson and R.L. Urbanke, “The capacity of low-density
parity-check codes under message-passing decoding”, IEEE Trans. Inf.
Theory., vol. 47, no. 2, pp. 599–618, Feb 2001.
[16] R. Ohashi, K. Kasai, and K. Takeuchi, “Multi-dimensional spatiallycoupled codes”, in Inf. Theory Proc. (ISIT), 2013 IEEE Int. Symposium
on, July 2013, pp. 2448–2452.
[17] M. Luby, “LT codes”, in Proc. 43rd Annual Symp. on Fundations ofComputer Science (FOCS), 2002, pp. 271–280.