Thresholds of Braided Convolutional Codes
on the AWGN Channel
Muhammad Umar Farooq, Saeedeh Moloudi, and Michael Lentmaier

arXiv:1802.10540v1 [cs.IT] 28 Feb 2018

Dept. of Electrical and Information Technology,
Lund University, Sweden
Emails: {muhammad.umar farooq, saeedeh.moloudi, michael.lentmaier}@eit.lth.se
Abstract—In this paper, we perform a threshold analysis
of braided convolutional codes (BCCs) on the additive white
Gaussian noise (AWGN) channel. The decoding thresholds are
estimated by Monte-Carlo density evolution (MC-DE) techniques
and compared with approximate thresholds from an erasure
channel prediction. The results show that, with spatial coupling,
the predicted thresholds are very accurate and quickly approach
capacity if the coupling memory is increased. For uncoupled ensembles with random puncturing, the prediction can be improved
with help of the AWGN threshold of the unpunctured ensemble.

I. I NTRODUCTION
Braided convolutional codes (BCCs) [1] are a class of
spatially-coupled (SC) turbo-like codes with regular graph
structure. On the binary erasure channel (BEC), explicit density evolution (DE) equations have been derived for BCCs in
[4], which can be used to efficiently compute exact decoding
thresholds for that channel. The results show that BCCs have
superior maximum-a-posteriori (MAP) decoding thresholds
compared to parallel or serially concatenated codes on the
binary erasure channel (BEC) [5]. Furthermore it has been
proven analytically in [5] that threshold saturation occurs, i.e.,
with spatial coupling a belief propagation (BP) decoder can
achieve the same threshold as an optimal MAP decoder.
The aim of this paper is to compute the BP thresholds
of BCCs on the additive white Gaussian noise (AWGN)
channel. For this channel, exact DE equations are not available
for turbo-like codes, and Monte Carlo (MC) methods are
usually applied to estimate decoding thresholds. One of the
difficulties of such an approach is that the graphs of spatially
coupled systems contain a large number of edge types whose
message densities have to be considered individually during
DE. This requires significantly larger computational efforts
than classical methods, like the single edge-type extrinsic
information transfer characteristics (EXIT) chart analysis [2].
We use Monte-Carlo density evolution (MC-DE) to estimate
the thresholds of uncoupled and coupled BCCs with and without puncturing. As an efficient alternative, we then consider
the erasure channel approximation by Chung [9] for predicting
the AWGN channel thresholds from those of the BEC and
compare the results. Finally, we demonstrate that for randomly
punctured ensembles, analogously to LDPC codes [6], the
thresholds of BCCs of all higher rates can immediately be
predicted from the unpunctured thresholds of the BEC and/or
the AWGN channel. Some simulation results are also given.

ut

ut

Encoder CAU
L
(1)

DN

U
(2)

DN

P⇧tt
(0)
P⇧t t

P⇧tt

Encoder CBL

(1)

vt

(2)

vt

Fig. 1. Blockwise BCCs: turbo-like codes with parity feedback (R = 1/3).

II. B RAIDED C ONVOLUTIONAL C ODES
BCCs were originally introduced in [7]. Their characteristics
is that the parity symbols of one component encoder are used
as information symbols of the other and vice versa. Due to
this, both information and parity symbols are protected by
both component codes in a symmetric way. In this paper we
consider an example of braided convolutional codes (BCCs)
of rate R = 1/3, which are defined by using two systematic
component convolutional encoders of rate Rcc = 2/3 and three
permutors of length N . The component code and the encoding
method is same as used in [5]. In particular, we are using the
blockwise BCCs, for which an encoder diagram is shown in
Fig. 1. The parity symbols created by one encoder at time t
pass a delay of one block, DN and a permutor before entering
the other encoder at time t + 1 [7].
To compare BCCs with PCCs and SCCs, it sometimes
can be useful to define an uncoupled equivalent of BCCs.
This can be achieved by removing the delay in the encoder
depicted in Fig. 1. Since the feedback now occurs without the
delay, a straightforward encoding by means of the trellis is
not possible. But the code is still well defined by the trellis
constraints that the code symbols have to satisfy.
Turbo-like codes, like LDPC codes, can be described by
the factor graphs. This way of expressing the code is useful
in describing the exchange of messages in an iterative BP
decoder, as well as for the corresponding DE analysis. Instead
of a conventional factor graph, we use a compact graph

vU
t

vU

vU
t

1

vU

vU
t+1 u

(1)

TU

Lch

(1)

Lext,in
TO N
UU
T
T
N N TU
N

U
N T

u
ut

ut

1

vO
ut+1

u

N TL

v Lt

vL

(a)

1

TI 2N

v Lt

vL vL
t+1

(a)

(b)

Lext,out

Upper
Trellis

u

N TTLL N N TL

(2)

(2)

Lin

TU N

⇧

TL

(1)

Lch

vU

TL N

(0)

Upper
Trellis
(1)

Lin

Lin

(0)

vL

(c)

(b)
(d)

(1)

Lext,out

(2)

Lext,in

vI

(0)

Lext,out

Lext,in
(0)

Lch

(2)

(a)

(0)

Lch

Lch

(2)

(b)

Lch

Fig. 3. Monte Carlo Density Evolution Process

Fig. 2. Compact graph representation
TABLE I
U NCOUPLED BCC T HRESHOLDS

representation as introduced in [5]. The compact graph of a
BCC and its uncoupled equivalent is shown in Fig. 2. Each
block of symbols is represented by a variable node and each
trellis by a factor node. A permutor is indicated by a short
line that crosses an edge in the graph.
Similar to the SC-LDPC codes, a BCC code can be obtained
by repeating the graph of an uncoupled code and spreading
some edges across m+1 neighboring blocks, where m denotes
the coupling memory. The original BCCs shown in Fig. 2(a)
have coupling memory m = 1.
III. M ONTE C ARLO D ENSITY E VOLUTION
In order to describe the MC-DE process, let us consider the
upper decoder of the uncoupled (UC) BCC shown in Fig. 2(b).
The exchange of messages with the upper decoder is depicted
in Fig. 3. Due to symmetry, the processing at the lower decoder
follows analogously. In each iteration of MC-DE, assuming a
flooding schedule, the decoding at the upper and lower decoder
is performed independently in parallel and the densities of
updated output messages are exchanged. Iterative exchange
of densities continues in this fashion until the decoding error
probability converges. The key points of the MC-DE process
can be summarized in the following three major steps:
1) Variable node update: Each variable node k = 0, 1, 2 in
(k)
Fig. 3(a) takes the sequence Lch of channel LLRs and
(j)
the sequence Lext,in of incoming extrinsic LLRs received
from output j of the connected lower trellis node and
(i)
combines them to the updated message sequence Lin =
(k)
(j)
Lch +Lext,in , which forms the input i of the upper trellis
node. All sequences are of equal length N .
2) Trellis node update: The trellis node receives the three
input sequences from the different variable nodes corresponding to symbol blocks u, v U and v L . The node
performs decoding and produces the updated sequences
(i)
Lext,out of extrinsic LLRs at each output i = 0, 1, 2 of
the trellis node. Finally, these output message sequences
(i)
are used to estimate the message densities f (Lext,out ).

Thresholds
Eb /N0 (dB)

Pattern
1/3

Rate
1/2

2/3

MC
GA
GA SE

P1
P1
P1

1.003
1.023
1.050

2.408
2.399
2.708

-

MC
GA
GA SE

P2
P2
P2

1.003
1.018
1.048

2.121
2.128
2.161

4.151
4.062
4.131

3) Drawing samples from message densities: In this step
(k)
(j)
independent LLR sequences Lch , k = 0, 1, 2 and Lext,in ,
j = 0, 1, 2 are created from the channel density and the
(j)
densities f (Lext,out ) received from the lower trellis node.
These sequences are used in the next MC-DE iteration.
(i)

In the literature, the message densities f (Lext,out ) are often
approximated by Gaussian densities as well in MC-DE. In this
(i)
case, it is not necessary to estimate the exact f (Lext,out ) in step
2. Instead, some parameter like the mean, the variance or the
mutual information corresponding to the LLR sequences is
computed to characterize the Gaussian density.
Table I shows the uncoupled BCC thresholds obtained via
MC-DE with two different puncturing methods. P2 puncturing
refers to when uniform random puncturing is applied on both
information and parity bits, whereas in P1 random puncturing
is applied only on parity bits. MC refers to the threshold
obtained via MC-DE algorithm and GA refers to the threshold
(i)
when f (Lext,out ) is approximated to the Gaussian density and
(i)
Lin are drawn from it.
In determining MC and GA thresholds, the statistics along
the incoming edges to the trellis nodes are different. It means
that for a code with multi edge-types (ME), such as BCCs, the
(i)
f (Lin ) distributions are different along each incoming edge.
(i)
We can average out the densities f (Lin ) and use a single
density f (Lin ) along each incoming edge to the trellis nodes.
It can be observed that the MC thresholds are closer to
the GA thresholds for low rates. Whereas, the difference in

these thresholds becomes high as the fraction of puncturing
(i)
increases. With punctured bits, f (Lin ) will be a mixture of
the Gaussian and erasure densities. The erasure density will be
dominant in this mixture at higher rate. Therefore we expect
that the Gaussian approximation of the densities at higher rate
results in inaccuracies. Furthermore, the difference from GA
SE thresholds to other thresholds is relatively larger. The GA
SE case is equivalent to the classical EXIT chart technique.
In general, in case of ME ensembles the MC-DE process with
(i)
GA of densities f (Lin ) is equivalent to the protograph LDPC
EXIT analysis technique [3].
In order to get a high accurancy of estimated thresholds via
MC-DE, a large number of trellis node output messages are
collected before computing the densities within each iteration.
The statistics are considered stabilized when the bit error rate
(BER) as a function of the number of simulated blocks within
an iteration reaches a steady state with a difference of .0001.
This requirement of accuracy control makes MC-DE take days
to compute UC-BCCs thresholds and it takes even much longer
for the SC-BCCs. The accuracy of the MC-DE thresholds can
be increased by running MC-DE for longer time.
Life can be much more easier if we can predict the thresholds on the Gaussian channel reliably and much faster than
the MC-DE does. One way would be to use the exact DE
equations as is used in [5] for BCCs over the BEC. However,
the DE equations for the BCCs on the AWGN channel are
not available. Therefore, we have to look for an alternative
solution to find the thresholds of BCCs much faster than MCDE does.
IV. E RASURE C HANNEL P REDICTION OF AWGN
C HANNEL T HRESHOLDS
It has been observed in [9] that the thresholds of LDPC
codes on the AWGN channel can be approximated by the
corresponding thresholds on the BEC. Such an erasure channel prediction (ECP) is computationally attractive for turbolike code ensembles, since BEC thresholds can be computed
exactly with relatively small efforts. In this section we will
apply this approach to uncoupled and coupled BCC ensembles
and compare the resulting thresholds with those obtained from
MC-DE.
Let CE (ε) = 1 − ε denote the capacity of a BEC with
erasure probability ε and CG (σ) denote the capacity of a
binary-input AWGN channel with noise variance σ 2 . Let ε∗
and σ ∗ denote the DE thresholds computed on the two types
of channels for a given code ensemble. The ECP is based on
the observation that CE (ε∗ ) ≈ CG (σ ∗ ), which suggests the
approximation
−1
−1
σ ∗ ≈ CG
(CE (ε∗ )) = CG
(1 − ε∗ ) .

(1)

Using (1), the AWGN threshold of a given ensemble can
now be predicted from the corresponding BEC threshold ε∗ .
Table II shows the resulting predicted thresholds for UCBCCs and SC-BCCs along with the corresponding MC-DE
thresholds. The original BEC thresholds are also given, where
the values of puncturing pattern P1 are identical to Table II

TABLE II
P REDICTED VS E STIMATED T HRESHOLDS (Eb /N0 ) OF BCC
Erasure
1SC
U C

UC BCC
ECP
MC

SC BCC
ECP
MC

Rate

Pattern

1/3
1/2
2/3
3/4
4/5

P1
P1
P1
P1
P1

0.6609
0.4932
0.3257
0.2411
0.1915

0.5541
0.3013
-

1.213
2.716
-

1.00
2.40
-

-0.399
0.276
1.156
1.746
2.164

-0.39
0.25
1.12
1.70
2.12

1/3
1/2
2/3
3/4
4/5

P2
P2
P2
P2
P2

0.6609
0.4914
0.3219
0.2371
0.1862

0.5541
0.3312
0.1083
-

1.213
2.335
4.336
-

1.00
2.12
4.15
-

-0.400
0.300
1.204
1.800
2.241

-0.39
0.29
1.18
1.77
2.21

of [5]. We can see from Table II that the ECP thresholds of
SC-BCCs are quite close to the MC thresholds. However, the
difference is larger on higher rates than it is on lower rates as
we have observed in the UC-BCCs thresholds. The ECP and
MC thresholds of the UC-BCCs have bigger difference than
the SC-BCCs. Furthermore, the ECP and the MC thresholds
are much closer to each other on P2 puncturing compared to
P1 puncturing.
V. T HRESHOLDS OF R ANDOMLY P UNCTURED E NSEMBLES
Can we predict the thresholds such that the difference of
the predicted and the estimated threshold do not increase as
the fraction of puncturing increases? In [6], it has been shown
that for the P2 punctured LDPC codes, it is possible to closely
predict the thresholds on the AWGN channel, given just the
threshold of the unpunctured code ensemble and the design
rate R. In the following, we will apply the methods discussed
in [6] to the randomly punctured BCC ensembles and discuss
the results obtained by it.
A. θE Predictions
This method takes only the unpunctured code threshold
on the BEC and predicts the thresholds for the punctured
ensembles on the BEC by using
∗ (α) = 1 − θE R(α) ,

(2)

where

1 − ∗
.
(3)
R
The elegance of this method is that it will provide the exact
BEC thresholds for all rates R(α), R ≤ R(α) ≤ 1/θE , based
on a single parameter θE and hence it is not required to
perform DE on all different rates. However, this method is
limited to the puncturing pattern P2 only.
Once we know the BEC thresholds, we can apply the ECP
method discussed in Section IV. Equivalently, we can write
θE =

hG (σ ∗ (α)) ≈ hE (ε∗ (α)) = ∗ (α) = 1 − θE R(α) ,

(4)

where hG (σ) = 1 − CG (σ) and hE (ε) = 1 − CE (ε) = ε
denote the conditional entropy of the AWGN channel and
the BEC, respectively. From (4) we can compute the AWGN

TABLE III
U NCOUPLED BCC T HRESHOLDS
Pattern

Erasure Probability
MC-DE
θE Predicted
θG Predicted
MP

P2
P2
P2
P2
P2

1/3

Rate
1/2

2/3

0.5541
1.003
1.214
1.003
1.003

0.3312
2.121
2.336
2.054
2.195

0.1083
4.151
4.338
3.798
4.197

0.9

Shannon Capacity
Erasure Predicted( E )
Gaussian Predicted( G )

0.8

Measured Threshold
Mixed Prediction

0.7

Rate

Thresholds
Eb /N0 (dB)

1

0.6

0.5

thresholds in terms of standard deviation σ or signal-to-noise
ratio Eb /N0 . The results obtained via this method for UCBCCs are given in Table III.

0.4

0.3
0

0.1

0.2

0.3

0.4

0.5

0.6

Entropy

B. θG Predictions
While the θE prediction works especially well for high
code rates, it can be further improved for low rates if the
unpunctured threshold σ ∗ is available. Then

where
θG =

1 − hG (σ ∗ )
.
R

0.9
m=1 SC BCC
0.8

(6)

It can be seen in Table III that for the lower code rates,
the MC thresholds and the θG predictions are quite close.
However, for a higher fraction of punctured bits, the MC
thresholds are closer to the θE predictions.
C. Mixed Predictions

UC BCC
0.7

0.6
Measured Threshold
Mixed Prediction
Erasure Predicted( E )

0.5

0.4

To account for the higher puncturing fraction in the prediction of thresholds on the AWGN channel, a mixed prediction
(MP) method is suggested in [6], where both θE and hG (σ ∗ )
are used.
The important idea behind the mixed prediction method is
that various punctured code ensemble thresholds on the BEC,
when viewed in the entropy domain, lie on a straight line.
The slope of this line is characterized by θE . It is further
demonstrated in [6] that for P2 punctured LDPC codes on the
AWGN channel the estimated entropies, corresponding to the
Eb /N0 thresholds, are observed to follow a straight line.
From the observation that at lower rate the estimated thresholds are closer to the θG predictions and at higher rates are
closer to the θE predictions, we obtain the following mixed
prediction
hG (σBP (α)) ≈

1

(5)

Rate

hG (σ ∗ (α)) ≈ 1 − θG R(α) ,

Fig. 4. Entropy vs Rate of UC-BCCs

(R(α) − R) · (1 − θE − hG (σ ∗ ))
1−R
+hG (σ ∗ )

(7)

where R ≤ R(α) ≤ Rmax . Rmax is an intercept that can
be obtained by setting hG (σBP (α)) = 0 in (7). This straight
line prediction passes through the unpunctured rate R(0) and
the associated threshold (entropy) on the AWGN channel and
R(α) = 1 and its associated threshold (entropy) on the BEC.
The results of the mixed predictions are shown in Fig. 4 for

Gaussian Predicted( G )
Shannon Capacity

0.3
-1

0

1

2

3

4

5

6

7

8

E b /N0

Fig. 5. Eb /N0 vs Rate of SC and UC-BCCs

the P2 punctured UC-BCCs ensembles. The estimated MCDE thresholds almost follow the mixed prediction line in this
figure. However, the estimated thresholds do not strictly lie on
a straight line as was the case in [6].
It can be seen in Table II that for SC-BCCs, the MC-DE
and predicted thresholds are almost identical. As a result of
threshold saturation, the SC-BCCs performance is much better
compared to the performance of UC- BCCs and the gap to
capacity is much smaller for SC-BCCs, which can be seen
in Fig. 5. θE predictions for the punctured m = 1 SC-BCCs
have been made by using θE = 1.017. Similary, θE and θG
predictions for the punctured UC-BCCs have been made by
using θE = 1.337 and θG = 1.293 respectively. Since the θE
predictions are very close to the MC-DE thresholds, θG and
mixed predictions have not been included in this table.
Consider now a larger coupling memory m = 3. The
predicted thresholds are given in Table IV, where it can be
seen that m = 3 SC-BCCs outperform m = 1 SC-BCCs and

R EFERENCES

TABLE IV
BCC COUPLED - m = 3
Thresholds
Eb /N0 (dB)

1/3

Shannon Capacity
Erasure Probability
θE prediction

-0.50
0.6644
-0.4585

1/2

Rate
2/3

3/4

4/5

0.18
0.4967
0.2307

1.06
0.3289
1.1151

1.63
0.2450
1.6924

2.05
0.1947
2.1166

100
R1/3
R2/3
Threshold R1/3
Threshold R1/2
Threshold R2/3
R1/2

10-1

10-2

BER

10-3

10-4

10-5

10-6

10-7
-0.5

0

0.5

1

1.5

2

E b /N0

Fig. 6. BER vs Eb /N0 thresholds of P2 punctured SC-BCCs

operate very close to the Shannon limit. Since, for m = 3
SC-BCCs, the θE predictions and MC-DE thresholds are very
close to each other, we have only provided the θE predictions.
D. Simulation Results
The simulated BER performance of P2 punctured m = 1
SC-BCCs on the AWGN channel is shown in Fig. 6. The
simulations are obtained with a sliding window decoder [8]
with window size w = 5, and 20 iterations at each window
position. We can see from Fig. 6 that for all the considered
rates R = 1/3, 1/2, 2/3 the BER curves are in accordance
with their corresponding thresholds.
VI. C ONCLUSIONS
In this paper, have presented MC-DE as a technique to
compute the AWGN channel thresholds of spatially-coupled
turbo-like codes. Furthermore, we have applied the threshold
prediction methods presented for LDPC codes in [6] for
predicting BCC thresholds. The θE and θG predictions of
the UC and SC-BCC ensembles have been compared with
the estimated thresholds obtained by MC-DE. The results
show that, with spatial coupling, the predicted thresholds are
very accurate and quickly approach capacity if the coupling
memory is increased. For uncoupled ensembles with random
puncturing, the prediction can be improved with help of the
AWGN threshold of the unpunctured ensemble.

[1] W. Zhang, M. Lentmaier, K. Sh. Zigangirov, and D. J. Costello, Jr.,
“Braided convolutional codes: A new class of turbo-like codes,” IEEE
Transactions on Information Theory, vol. 56, no. 1, pp. 316–331, Jan.
2010.
[2] S. ten Brink,“Convergence behavior of iteratively decoded parallel concatenated codes,” IEEE Trans. Commun., vol. 40, pp. 17271737, Oct.
2001.
[3] G. Liva and M. Chiani, “Protograph LDPC codes design based on EXIT
analysis,” in Proc. IEEE Globecom, Washington, DC, Nov. 2730, 2007,
pp. 32503254.
[4] S. Moloudi and M. Lentmaier, “Density evolution analysis of braided
convolutional codes on the erasure channel,” in Proc. IEEE International
Symposium on Information Theory, Honolulu, HI, USA, July 2014.
[5] S. Moloudi, M. Lentmaier, and A. Graell i Amat, “Spatially coupled
turbo-liked codes,” in IEEE Transactions on Information Theory, Vol. 63,
No. 10, 2017, p. 6199 - 6215
[6] D. G. M. Mitchell, M. Lentmaier, A. E. Pusane, and D. J. Costello, Jr.,
“Randomly punctured LDPC codes, in IEEE J. Sel. Areas Commun., vol.
34, no. 2, pp. 408421, Feb. 2016.
[7] D. J. Costello, Jr., M. Lentmaier, and D. G. M. Mitchell, “New perspectives on Braided Convolution Codes, in IEEE 9th international symposium
on Turbo codes and iterative information processing, 2016.
[8] M. Zhu, D. G. M. Mitchell, M. Lentmaier, D. J. Costello and B. Bai,
“Braided Convolutional Codes with Sliding Window Decoding, in IEEE
Trans. Comm., May 2017.
[9] S.-Y. Chung, “On the construction of some capacity-approaching coding schemes, Ph.D. dissertation, Dept. Elect. Eng. Comput. Sci., Massachusetts Inst. Technol., Cambridge, MA, USA, Sep. 2000.

