A New Method for Building Low-Density-Parity-Check Codes
Published at : 30 Oct 2019
Volume : IJtech
Vol 10, No 5 (2019)
DOI : https://doi.org/10.14716/ijtech.v10i5.1144
Amine, T.M., Ali, D. 2019. A New Method for Building Low-Density-Parity-Check Codes. International Journal of Technology. Volume 10(5), pp. 953-960
| Tehami Mohammed Amine | Telecommunications and Digital Signal Processing Laboratory, Djillali liabes University of Sidi Bel Abbes, Algeria |
| Djebbari Ali | Telecommunications and Digital Signal Processing Laboratory, Djillali liabes University of Sidi Bel Abbes, Algeria |
This paper proposes a new method for building
low-density-parity-check codes, exempt of cycle of length 4, based on a
circulant permutation matrix, which needs very little memory for storage it in
the encoder and a dual diagonal structure is applied to guarantee that parity
check bits can be recursively computed with linear calculation complexity. The
Bit Error Rate performance of the new low-density-parity-check codes was
compared to the uncoded bi-phase-shift-keying over
additive-white-gaussian-noise channel. This simulation shows that the proposed
codes are very efficient over additive-white-gaussian-noise. The proposed codes
ensure a very low encoding complexity and reduce the memory storage required
for the parity-check matrix, which can be more easily built than others codes
used in channel coding.
Circulant permutation matrix; Dual-diagonal matrix; Girth; Low-density-parity-check codes; Parity-check matrix
Because of their prodigious performance, low-density-parity-check (LDPC)
codes are now considered optimal (Gallager, 1962). These codes are a part of
linear block codes which have acquired considerable importance in error
correcting performances (Yahya et al., 2009). LDPC codes can be presented by specific parity check matrix H
that includes a high density of 0’-s and a low density of 1’-s (Mackay, 1999).
The Tanner graph (Tanner, 1981) is a bipartite graph comprising two groups of
nodes: the variable nodes and check nodes. Variable nodes depicting columns and
rows are represented by check nodes and connections between these two sets are
known as edges (Tanner, 1981; Juwono et al., 2013). In the Tanner graph, a
cycle is defined as a path which starts and ends at the same node, if the graph
contains a cycle; its minimum length is known as ‘girth’ (Tanner, 1981). Cycles
especially those of length 4 decrease the bit-error-rate (BER) performance of
LDPC codes, because of their impact on the independence of extrinsic
information exchanged in the decoding process (Johnson & Weller, 2001).
Gallager codes are classified: as regular if the weight of columns and rows
(i.e. density of 1’s) is constant and as irregular if column weight and row
weight are variable (Yahya et al., 2009).
The
construction of these codes is of two types; the first is random construction
that is flexible in design and construction (Mackay, 1999). The parity-check
matrix is a superposition and/or concatenation of sub-matrices and this
construction has significant drawbacks in term of the stocking and accessing a
large parity-check matrix. As random building does not guarantee small cycle
lengths, a second form of construction was developed; this is known as
deterministic construction (Moura el al., 2004; Shin et al., 2014).
In this paper, we depict a particular
category of LDPC codes, excluding cycles of length 4, which can be linearly
coded by matrix H. The parity check matrix is divided into two sections: the
first, which matches to the parity bits, is a dual-diagonal structure (Guolei
& Dong, 2010) and the second, which matches the information bits, is a
quasi-cyclic structure. For that reason, this new LDPC code is classified as
irregular code.
This paper is organized as follows. Section 2 discusses the construction of the new LDPC code based on a quasi-cyclic and a dual diagonal matrix. In section 3, we propose a deterministic rule for constructing parity-check matrix with various rates. Section 4 describes the LDPC reduced-complexity encoding method, and section 5 discusses decoding complexity. Section 6 specifies the advantages of the proposed method, followed by conclusions in Section 7.
To address quality of reception and implementation
constraints, LDPC code must be constructed with a low error floor, linear
encoding and less complex decoding. This
paper proposes a new method for constructing parity-check matrix that include girths of length 4, for different rates. Memory requirements are significantly reduced by the use of the quasi-cyclic
matrices and
dual- diagonal, which reduce encoding complexity.
| Filename | Description |
|---|---|
| R2-EECE-1144-20191015090437.docx | --- |
| R2-EECE-1144-20191015090451.docx | --- |
| R2-EECE-1144-20191015090501.docx | --- |
| R2-EECE-1144-20191015090512.docx | --- |
| R2-EECE-1144-20191015090531.docx | --- |
3GPP2, 2008. C.S0084-001-0
v3.0, Physical Layer for Ultra Mobile Broadband (UMB) Air Interface
Specification. Version 3.0.
Asvial , M., Dewandaru, G.,
Rachman, A.N., 2015. Modification of Round Robin and Best CQI Scheduling Method
for 3GPP LTE Downlink. International Journal of Technology, Volume 6(2), pp. 130–138
Berrou, C., 2010. Code and Turbo-code. Bretagne: ENST Bretagne
Edition
Divsalar, D., Dolinar, S.,
Jones, C.R., Andrews, K., 2009. Capacity-approaching Protograph
Codes. IEEE Journal on Selected Areas in Communications, Volume 27(6),
pp. 876–888
Fossorier, M.P.C., 2004.
Quasi-cyclic Low-density Parity-check Codes
from Circulant Permutation Matrices.
IEEE Transaction on Information Theory, Volume 50(8), pp. 1788?1793
Gallager, R.G., 1962.
Low-density Parity-check Codes. IRE
Transaction on Information Theory, Volume 4, pp. 21–28
Guolei, Q., Dong, Z., 2010.
Design of Structured LDPC Codes with Quasi-Cyclic
and Rotation Architecture. In: IEEE
Third International Conference on Advanced Computer Theory and Engineering,
Chengdu, China, pp. 655–657
Johnson, S.J., Weller, S.R.,
2001. Regular Low Density Parity Check Codes from Combinatorial
Design. In: IEEE Information Theory Workshop,
Cairns, Queensland, Australia, pp. 90–92
Juwono, F.H.,
Triprasetyo, Y., Gunawan, D., 2013. Exploiting LDPC Codes for Improving the
Performance of Clipped-OFDM System. International Journal of Technology, Volume 4(1),
pp. 93–99
Lin, C.Y., Wei, C.C., Ku,
M.K., 2008. Efficient Encoding for Dual Diagonal
Structured LDPC Codes based on Parity
Bit Prediction and Correction.
In: IEEE Asia Pacific Conference on Circuits and Systems, Macao, China,
pp. 1648–1651
Liu, K., Fei, Z., Kuang, J.,
Li, X., 2009. A Novel Algorithm for Removing
Cycles in Quasi-Cyclic LDPC Codes. In:
IEEE 20th International Symposium on Personal, Indoor and Mobile
Radio Communications, Tokyo, Japan, pp. 1054–1058
MacKay, D., 1999. Good Codes
based on Very Sparse Matrices. IEEE
Transactions on Information Theory, Volume 45(2), pp. 399–431
Malema, G., Liebelt, M.,
2007. Quasi-Cyclic LDPC Codes of Column-weight Two using a Search Algorithm. EURASIP
Journal on Applied Signal Processing, Volume 1(1), pp. 1–8
Mao, Y., Banihasherni, A.H.,
2001. A Heuristic Search for Good
Low-density Parity-check Codes
at Short Block Lengths. In:
IEEE International Conference on Communication, Helsinki, Finland, pp. 41–44
Moura, J.M.F., Lu, J.,
Zhang, H., 2004. Structured Low-density Parity-check
Codes. IEEE Signal Processing Magazine, Volume
21(1), pp. 42–55
O’Sullivan, M.E.,
2006. Algebraic Construction of Sparse Matrices
with Large Girth. IEEE Transaction on
Information Theory, Volume 52(2), pp. 718–727
Ping, L., Leung, W.K.,
Phamdo, N., 1999. Low Density Parity Check Codes
with Semi-random Parity Check Matrix. Electronic
Letter, Volume 35(1), pp. 38–39
Richardson, T., Kudekar, S.,
2018. Design of Low-density Parity Check Codes for 5G New Radio. IEEE
Communications Magazine, Volume 56(3),
pp. 28–34
Shin, B., Park, H., Hong,
S., No, J.S., Kim, S.H., 2014. Quasi-cyclic LDPC Codes using Overlapping
Matrices and Their Layered
Decoders. AEU-International
Journal of Electronics and Communications, Volume 68(5),
pp. 379–383
Song, H., Liu, J., Kumar,
B.V.K.V., 2002. Low Complexity LDPC Codes for Partial
Response Channels. In: IEEE
Proceedings on Global Telecommunication Conference, Taipei, Taiwan, pp.
1294–1299
Song, H., Liu, J., Kumar,
B.V.K.V., 2004. Large Girth Cycle Codes for Partial
Response Channels. IEEE Transaction on Magnetics, Volume
40(4), pp. 3084–3086
Suryanegara, M., Miyazaki,
K., 2012. Towards 4G Mobile Technology: Identifying Windows of Opportunity for a
Developing Country. International Journal of Technology, Volume 3(1), pp. 85–92
Tanner, R., 1981. A Recursive
Approach to Low Complexity
Codes. IEEE Transaction on Information Theory,
Volume 27(5), pp. 533–547
Yahya, A., Sidek, O.,
Salleh, M.F.M., Ghani, F., 2009. A New Quasi-Cyclic Low Density Parity Check Codes.
In: IEEE Symposium on Industrial Electronics & Applications (ISIEA),
Kuala Lumpur, Malaysia, Volume 1, pp. 239–242