EXIT Chart Analysis of Block Markov
Superposition Transmission of Short Codes
Kechao Huang
∗
, Xiao Ma
∗
, and Daniel J. Costello, Jr.
†
∗
Dept. of Electronics and Communication Engineering, Sun Yat-sen University, Guangzhou, China
‡
Dept. of Electrical Engineering, University of Notre Dame, Notre Dame, USA
Email: hkech@mail2.sysu.edu.cn; maxiao@mail.sysu.edu.cn; costello.2@nd.edu
Abstract—In this paper, a modified extrinsic information trans-
fer (EXIT) chart analysis that takes into account the relation
between mutual information (MI) and bit-error-rate (BER) is
presented to study the convergence behavior of block Markov
superposition transmission (BMST) of short codes (referred to
as basic codes). We show that the threshold curve of BMST codes
using an iterative sliding window decoding algorithm with a fixed
decoding delay achieves a lower bound in the high signal-to-noise
ratio (SNR) region, while in the low SNR region, due to error
propagation, the thresholds of BMST codes become slightly worse
as the encoding memory increases. We also demonstrate that the
threshold results are consistent with finite-length performance
simulations.
I. INTRODUCTION
Spatially coupled low-density parity-check (SC-LDPC)
codes are constructed by coupling together a series of
L disjoint Tanner graphs of an underlying LDPC block
code (LDPC-BC) into a single coupled chain and can be
viewed as a type of LDPC convolutional code [1]. It was
shown in [2, 3] that the belief propagation (BP) decoding
thresholds of SC-LDPC code ensembles are numerically in-
distinguishable from the maximum a posteriori (MAP) de-
coding thresholds of their underlying LDPC-BC ensembles.
Subsequently, it was proven analytically that SC-LDPC code
ensembles exhibit threshold saturation on memoryless binary-
input symmetric-output channels under BP decoding [4]. Due
to their excellent performance, SC-LDPC codes have received
a great deal of attention recently (see, e.g., [5–9] and the
references therein).
The concept of spatial coupling is not limited to LDPC
codes. Block Markov superposition transmission (BMST) of
short codes [10, 11], for example, is equivalent to spatial
coupling of the subgraphs that specify the generator matrices
of the short codes. From this perspective, BMST codes are
similar to braided block codes [12], staircase codes [13], and
spatially coupled turbo codes [14]. A BMST code can also
be viewed as a serially concatenated code with a structure
similar to repeat-accumulate-like codes [15]. The outer code
is a short code, referred to as the basic code (not limited to
repetition codes), that introduces redundancy, while the inner
code is a rate-one block-oriented feedforward convolutional
code (instead of a bit-oriented accumulator) that introduces
memory between transmissions. Hence, BMST codes typically
have very simple encoding algorithms. To decode BMST
This work was partially supported by the 973 Program (No.
2012CB316100), the China NSF (No. 61172082 and No. 91438101), and
the U.S. NSF (No. CCF-1161754).
codes, a sliding window decoding algorithm with a tunable
decoding delay can be used, as with SC-LDPC codes. The
construction of BMST codes is flexible [16], in the sense that it
applies to all code rates of interest in the interval (0,1). Further,
BMST codes have near-capacity performance (observed by
simulation) in the waterfall region of the bit-error-rate (BER)
cruve and an error floor (predicted by analysis) that can be
controlled by the encoding memory.
On an additive white Gaussian noise channel (AWGNC),
the well-known extrinsic information transfer (EXIT) chart
analysis [17] can be used to obtain the threshold of LDPC-
BC ensembles. In [18], a novel EXIT chart analysis was
used to evaluate the performance of protograph-based LDPC-
BC ensembles, and a similar analysis was used to find the
thresholds of q-ary SC-LDPC codes with sliding window
decoding in [8]. Unlike LDPC codes, the asymptotic BER
of BMST codes with window decoding cannot be better
than a corresponding genie-aided lower bound [10]. Thus,
conventional EXIT chart analysis cannot be applied directly
to BMST codes. In this paper, we propose a modified EXIT
chart analysis, that takes into account the relation between
mutual information (MI) and BER, to study the convergence
behavior of BMST codes and to predict the performance in
the waterfall region of the BER curve. We also show that the
modified EXIT chart analysis of BMST codes is supported by
finite-length performance simulations.
II. SC-LDPC C
ODES VS. BMST CODES
In this section, both SC-LDPC codes and BMST codes are
described in terms of matrices for the purpose of showing their
similarities (dualities) and differences.
A. Protograph-Based SC-LDPC Codes
A protograph-based SC-LDPC code ensemble can be con-
structed from a protograph-based LDPC-BC code ensemble
using the edge spreading technique [3], described here in
terms of the base (parity-check) matrix representation of code
ensembles. Let B be a (N −K)×N base matrix representing
an LDPC-BC ensemble with design rate R = K/N.A
terminated SC (convolutional) base matrix B
SC
with coupling
width (syndrome former memory) m and coupling length L
can be constructed by applying the edge spreading technique