A Class of Low-Complexity Codes Based on
Doubly Recursive Block Markov Superposition
Transmission
Shancheng Zhao
∗
, Xiao Ma
†
, Qin Huang
‡
, and Baoming Bai
§
∗
College of Information Science and Technology, Jinan University, Guangzhou, China
†
School of Data and Computer Science, Sun Yat-sen University, Guangzhou, China
‡
School of Electronic and Information Engineering, Beihang University, Beijing, China
§
State Key Laboratory of ISN, Xidian University, Xi’an, China
Abstract—In this paper, we introduce the doubly recursive
block Markov superposition transmission (DrBMST) of short
code. An important characteristic of DrBMST codes is that
the degrees of the constraint nodes in their normal graphical
realizations are at most three. As a result, DrBMST codes can
be decoded with low complexity. We propose to use an enlarged
code ensemble to analyze the performance of DrBMST under
windowed maximum likelihood decoding. Further, the extrinsic
information transfer (EXIT) chart analysis is used to study the
iterative decoding thresholds of DrBMST code ensembles. The
EXIT analysis shows that the iterative decoding thresholds of
DrBMST code ensembles are comparable to those of the BMST
codes. We have also compared the error performance and the
decoding complexity of finite-length DrBMST codes with regular
spatial-coupled low-density parity-check (SC-LDPC) codes under
equal decoding latency. The comparison results show that the
DrBMST code performs about 0.1 dB better than a (4, 8)-regular
SC-LDPC code, but with lower computational complexity.
Index Terms—Block Markov superposition transition (BMST),
block-oriented convolutional code, SC-LDPC codes, spatial cou-
pling.
I. INTRODUCTION
Spatial-coupled low-density parity-check (SC-LDPC)
codes [1–5] are constructed by interconnecting together
a series of disjoint graphs specified by the parity-check
matrix of an LDPC block code into a single chain. It has
been shown that the iterative decoding threshold of an SC-
LDPC ensemble achieves the maximum a posteriori (MAP)
threshold of the underlying LDPC block ensemble over
binary-input memoryless output-symmetric channels [3].
Hence, channel capacity can be achieved by increasing
the density of the parity-check matrices of the underlying
uncoupled ensemble. In [6], spatial-coupled low-density
generator matrix (SC-LDGM) codes were used to approach
the rate-distortion limits.
Most recently, a special class of spatial-coupled codes
called block Markov superposition transmission (BMST) was
proposed [7–9] by spatial-coupling of the generator matri-
ces. Different from SC-LDGM codes, the sparsity of the
generator matrices is not required in BMST construction.
From the encoding point of view, the BMST codes admit
a serial concatenation structure similar to repeat-accumulate-
Fig. 1. Encoder of a DrBMST code, where ENC is implemented with an
encoder of the basic code C[n, k], the nodes D are length-n registers, and
Π
i
are random interleavers of size n.
like codes [10]. The primary difference lies in the fact that
block-oriented convolutional codes, instead of bit-oriented
convolutional codes, are used in BMST. To be specific, a
BMST code is constructed by concatenating a simple outer
code, referred to as the basic code, with an inner rate-one
block-oriented convolutional code. When compared with SC-
LDPC codes and SC-LDGM codes, BMST codes are superior
in terms of encoding complexity. Asymptotic analysis of non-
recursive and recursive BMST codes are presented in [9, 11]. It
is shown that the decoding thresholds of both the recursive and
non-recursive BMST codes are close to the channel capacities.
However, recursive BMST code typically requires a smaller
encoding memory than non-recursive BMST code to achieve
near-capacity performance.
For message-passing decoding, constraint nodes, e.g., check
node and variable node, of low degrees are preferred, as the
implementation cost of a constraint node is proportional to
its degree [12]. To achieve near-capacity performance, the
required encoding memory of recursive BMST (rBMST) codes
is three [13]. Hence, normal graph of an rBMST code contains
constraint nodes with degree five. To reduce the implemen-
tation cost of rBMST codes while maintaining near-capacity
performance, we propose in this paper the doubly recursive
BMST (DrBMST) codes, in which the inner code is formed by
the serial concatenation of two block-oriented accumulators.
As a result, the degrees of the constraint nodes in the normal
graph of a DrBMST code are at most three. Asymptotic
analysis of DrBMST codes is presented. Analytical results
2018 IEEE International Symposium on Information Theory (ISIT)
978-1-5386-4780-6/18/$31.00©2018 IEEE 1365