IEEE Communications Letters

Low-Complexity and Piecewise Systematic Encoding of Non-Full-Rank QC-LDPC Codes

Chien-Fu Tseng, Jenn‐Hwan Tarng

Published Mar 9, 2015• 9 citations

Abstract

In this letter, we present a low-complexity encoding method for quasi-cyclic (QC) low-density parity-check (LDPC) codes in the case of non-full-rank parity-check matrices. Gaussian elimination can achieve systematic encoding, but it is usually too complex to implement. For QC-LDPC codes, efficient encoding methods have been presented by using shift-registers, but the encoded codewords are not systematic when parity-check matrices are non-full-rank. However, a systematic structure is important in practice. Therefore, we propose an encoding method which allows all information bits appear piecewise in the codeword, called piecewise systematic encoding.

DOI: 10.1109/lcomm.2015.2411255

Related papers

A low complexity encoder construction for systematic quasi-cyclic LDPC codes

Yuval O. Genga, Olayinka Olaolu Ogundile, Olutayo O. Oyerinde +1 more

For practical applications in forward error correction, the importance of a systematic codeword cannot be overemphasized. Thus, this paper proposes the construction of a systematic quasi-cyclic (QC) LDPC code. This systematic structure is achieved by a row reduction technique different from the conventional Gaussian elimination method. This row reduction technique has the advantage of being easier to implement when compared to Gaussian row reduction techniques. The proposed row reduction technique maintains the quasi cyclic structure and the sparsity of the QC-LDPC parity check matrix while providing a low complexity approach to the construction of the generator matrix. In addition, the proposed construction exhibits a good BER performance for high rate codes.

IEEE AFRICONSep 1, 20175 citations

Quasi-cyclic LDPC codes for fast encoding

Seho Myung, Kyeongcheol Yang, Jaeyoel Kim

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.

IEEE Transactions on Information TheoryJul 19, 2005278 citations

Construction and Encoding of QC-LDPC Codes Using Group Rings

Hassan Khodaiemehr, Dariush Kiani

Quasi-cyclic (QC) low-density parity-check (LDPC) codes which are known as QC-LDPC codes, have many applications due to their simple encoding implementation by the means of cyclic shift registers. In this paper, we construct QC-LDPC codes from group rings. A group ring is a free module (at the same time a ring) constructed in a natural way from any given ring and any given group. We present a structure based on the elements of a group ring for constructing QC-LDPC codes. Some of the previously addressed methods for constructing QC-LDPC codes based on finite fields are special cases of the proposed construction method. The constructed QC-LDPC codes perform very well over the additive white Gaussian noise channel with iterative decoding in terms of bit-error probability and block-error probability. Simulation results demonstrate that the proposed codes have competitive performance in comparison with the similar existing LDPC codes. Finally, we propose a new encoding method for the proposed group ring-based QC-LDPC codes that can be implemented faster than the current encoding methods. The encoding complexity of the proposed method is analyzed mathematically, and indicates a significate reduction in the required number of operations, even when compared to the available efficient encoding methods that have linear time and space complexities.

IEEE Transactions on Information TheoryJan 18, 201717 citations

Using Minors to Construct Generator Matrices for Quasi-Cyclic LDPC Codes

Roxana Smarandache, Anthony Gómez-Fonseca, David G. M. Mitchell

This paper gives a simple method to construct generator matrices with polynomial entries (and hence offers an alternative encoding method to the one commonly used) for all quasi-cyclic low-density parity-check (QC-LDPC) codes, even for those that are rank deficient. The approach is based on constructing a set of codewords with the desired total rank by using minors of the parity-check matrix. We exemplify the method on several well-known and standard codes. Moreover, we explore the connections between the minors of the parity-check matrix and the known upper bound on minimum distance and provide a method to compute the rank of any parity-check matrix representing a QC-LDPC code, and hence the dimension of the code, by using the minors of the corresponding polynomial parity-check matrix.

IEEE International Symposium on Information Theory (ISIT)Jun 26, 20225 citations

A method for constructing parity-check matrices of non-binary quasi-cyclic LDPC codes

Stanislav Kruglik, Valeriya Potapova, Alexey Frolov

An algorithm for constructing parity-check matrices of non-binary quasi-cyclic low-density parity-check (NB QC-LDPC) codes is proposed. The algorithm finds short cycles in the base matrix and tries to eliminate them by selecting the circulants and the elements of GF(q). Firstly the algorithm tries to eliminate the cycles with the smallest number edges going outside the cycle. The efficiency of the algorithm is demonstrated by means of simulations. In particular, it was shown that NB QC-LDPC codes constructed with use of our algorithm loose less that 0.1 dB in comparison to the best NB LDPC codes.

arXiv:1705.10717May 30, 20170 citations

Construction and Encoding of QC-LDPC Codes Using Group Rings

Hassan Khodaiemehr, Dariush Kiani

Quasi-cyclic (QC) low-density parity-check (LDPC) codes which are known as QC-LDPC codes, have many applications due to their simple encoding implementation by means of cyclic shift registers. In this paper, we construct QC-LDPC codes from group rings. A group ring is a free module (at the same time a ring) constructed in a natural way from any given ring and any given group. We present a structure based on the elements of a group ring for constructing QC-LDPC codes. Some of the previously addressed methods for constructing QC-LDPC codes based on finite fields are special cases of the proposed construction method. The constructed QC-LDPC codes perform very well over the additive white Gaussian noise (AWGN) channel with iterative decoding in terms of bit-error probability and block-error probability. Simulation results demonstrate that the proposed codes have competitive performance in comparison with the similar existing LDPC codes. Finally, we propose a new encoding method for the proposed group ring based QC-LDPC codes that can be implemented faster than the current encoding methods. The encoding complexity of the proposed method is analyzed mathematically, and indicates a significate reduction in the required number of operations, even when compared to the available efficient encoding methods that have linear time and space complexities.

arXiv:1701.00210Jan 1, 20170 citations