Encoding of Certain LDPC Codes with Decoding
Resources
Z. H. Cai, P. S. Chin, J. Hao, C. M. Pang, and S. Sun
Institute for Infocomm Research
#21-01, 1 Fusionopolis Way
Singapore 138632
Abstract- This paper addresses the issue of encoding of LDPC
codes for certain transmission standards that employ LDPC as
coding scheme. It is shown that for these LDPC codes, the
encoding can be done simply by reusing decoding resources with
negligible overhead. Compared to conventional encoding designs,
our approach requires much less resources specified for encoder.
I. INTRODUCTION
Low density parity check (LDPC) codes are one of the most
powerful error correcting codes available today. First
introduced by R. G. Gallager decades ago and rediscovered by
Spielman, Mackay and many others, can achieve very good
performance when decoded with the belief-propagation (BP)
or the sum-product algorithm [1-2]. The remarkable
performance of LDPC codes has positioned themselves as
strong candidate for forward-error-correction (FEC) codes in
many digital communication systems, such as IEEE 802.11n
[3], WiMedia [4], IEEE 802.15.3c [5], and WiMax [6]. LDPC
decoding requires huge amount of messages exchanged in an
iterative manner. The LDPC codec implementation becomes
very hardware efficient when employing an architecture-aware
code design [7-8].
Compared with decoding, the encoding of LDPC codes is
much simpler, but it is by no means a trivial task. By taking
advantage of certain properties that exist in LDPC codes,
encoder design can be very straightforward and hardware
efficient [9-11]. By exploiting the dual-diagonal structure of
the standard H matrices, with little modification of Hs, a low-
complexity correction-based efficient encoding scheme that
requires no designated hardware is reported in [12], i.e., the
encoding can be done with the hardware resources for
decoding. And the overall computational complexity of the
proposed encoding scheme is lower than the well-known
Richardson’s efficient encoding scheme [9].
However, modifications on standardized matrices are not
always feasible; this will raise compliance issues. In this paper
we show that, without any modification on the standard H
matrices, for LDPC codes defined in WiMedia 1.5 [4], WiMax
[6] and IEEE 802.11n [3], and the emerging IEEE 802.15.3c
[5] (mmWave), efficient encoding can be done by reusing
decoding resources such as buffer memory, parity check
matrices ROM, routing/shuffling network between check node
processors (CNPs) and variable node processors (VNPs). Only
negligible overhead is required.
The rest of the paper is organized as follows. Section II
presents efficient encoding process for some carefully
designed LDPC codes. Algorithms/architectures for LDPC
decoding are discussed in Section III. Fitting encoding into
decoding architecture is detailed in Section IV and the
summary is given in Section V.
II. E
FFICIENT ENCODING OF BLOCK-LDPC CODES
For LDPC codes in [3-6], each LDPC code is defined by a
parity-check matrix H of size m × n, where n is the length of
the code and m is the number of parity check bits in the code.
The number of systematic bits is n-m.
The matrix H is defined as
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎣
⎡
=
−−−−
−
−
1,11,10,1
1,11,10,1
1,01,00,0
bbbb
b
b
nmmm
n
n
hhh
hhh
hhh
H
"
"
"
"
(1)
where each entry
h
i,j
represents a circular right shift ([0 z-1])
of the identity matrix
I
Z
or a z × z zero matrix. Thus, the
matrix
H is composed of m
b
block rows and n
b
block columns,
where n = z × n
b
and m = z × m
b
. Hence, it can be concisely
described by an m
b
× n
b
matrix where entry (i,j) contains either
-1 (
h
i,j
= 0) or the circular shift number.
A. H with Dual-diagonal (Staircase) Form
For LDPC codes defined in [3-4] and [6], the parity check
matrices have the dual-diagonal structure. An example parity
check matrix for WiMedia 1.5 LDPC code with rate 4/5 (z =
30, m
b
= 8 and n
b
= 40) is shown in Figure 1 (The -1 entries
are omitted here).
Figure 1 WiMedia 1.5 rate 4/5 LDPC parity check matrix
As shown in the Figure, the matrix can be partitioned as the
approximate lower triangular form as described in [9] with
D
being 1 × 1 block matrix. Denote the codeword
c = [m; p
0
; p
1
]
where
m is the systematic part, [p
0
p
1
] denotes the parity part
CDE
ABT
21st Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications
978-1-4244-8015-9/10/$26.00 ©2010 IEEE 269