Design of Low-Density Parity-Check Codes and Their Decoding Algorithms
- Title
- Design of Low-Density Parity-Check Codes and Their Decoding Algorithms
- Authors
- 조성혜
- Date Issued
- 2018
- Publisher
- 포항공과대학교
- Abstract
- In this thesis, we propose low-complexity designing algorithms for non-binary low-density
parity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding
algorithms for binary LDPC codes.
We first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q)
based on message-passing algorithms. Short cycles in an NB-LDPC code may be even
more harmful to its performance if they do not satisfy the so-called full rank condition
(FRC). This is because they may induce low-weight codewords or absorbing sets in that
case. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as
the number of short cycles for analyzing the performance of an NB-LDPC code. In order to
count those cycles, we first develop a novel message-passing algorithm and identify how it
is related to the FRC.We then propose a low-complexity algorithmfor counting the number
of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short
cycles. The proposed algorithm is not only theoretically validated, but its computational
and storage complexities are also computed. It does not require cycle enumeration with
high complexity, and therefore is still feasible even in the case of large code length, say
≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal
rule to choose a nonzero element for a given edge and propose a low-complexity algorithm
for designing an NB-LDPC code with low error floor. Furthermore, several design examples
are presented to verify the validity of the proposed design algorithm.
Secondly, we propose a low-complexity decoding algorithm for binary LDPC codes over
the binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding
algorithm for binary LDPC codes and has lower computational complexity than the
sum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it
has performance degradation. Furthermore, reducing the number of bits for representing
messages to two in a decoding algorithm for further reducing computational and storage
complexities, causes significant performance losses. In order to minimize the performance
degradation and computational and storage complexities, we propose a low-complexity
decoding algorithm which uses several decoders with two-bit precision for binary LDPC
codes over the BSC. The proposed algorithm adaptively changes decoders according to
the number of unsatisfied check nodes at each iteration. Compared with the SPA using
floating-point operations, the proposed decoding algorithm greatly reduces computational
and storage complexities with negligible performance losses. Numerical results show that
the proposed decoding algorithm has similar performance to the SPA with floating-point
operations over the BSC.
In the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes
for the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms
B (GDB) and E (GDE) for binary LDPC codes have much lower computational
complexity and much less required memory size than the SPA. This is because GDB and
GDE only use binary or integer operations, while the SPA requires real operations and
a look-up table. However, they are hardly used in commercial communication systems
since they have poorer performance than the SPA. Layered-division multiplexing (LDM)
is considered in ATSC 3.0 in order to deliver multiple broadcasting streams with distinct
robustness in a single radio frequency channel. Due to the unique characteristic of the
LDM, we propose to use GDB or GDE rather than the SPA for decoding the core layer signal
at fixed receivers. Numerical results show that the computational complexity and the
required memory size can be reduced without any performance loss by about 50 percent
and 80 percent, respectively, when GDB and GDE are employed.
- URI
- http://postech.dcollection.net/common/orgView/200000012127
https://oasis.postech.ac.kr/handle/2014.oak/93354
- Article Type
- Thesis
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.