Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Advances in Computer Engineering and Applications

Modified approximate lower triangular encoding of LDPC codes

Arijit Dutta, Ankita Pramanik

Published Mar 1, 2015• 5 citations
Publisher

Abstract

LDPC codes have become the most popular error control code in various fields like telecommunication, magnetic recording etc. due to their high error correcting capability. The Approximate Lower Triangular (ALT) encoding is the most commonly used encoding technique of LDPC codes. This technique though elegant suffers from the shortcoming that when a particular sub matrix of the H matrix obtained after ALT encoding is singular, the technique fails. In this paper a new algorithm is proposed to handle this shortcoming. In this work a new algorithm is proposed to bring any rectangular sparse LDPC matrix into a rectangular part and a square upper triangular part. This algorithm is implemented to encode a general H matrix. This algorithm is further appended to the ALT format of LDPC encoding and another efficient encoding technique is proposed for LDPC code. Both the proposed techniques have a pre-processing step followed by the actual encoding step. Scatter plots of the H matrices (after preprocessing) are shown. BER performance of the new Modified ALT technique is compared with the existing Systematic Approximate Lower Triangular method. The proposed algorithm gives better BER performance.

DOI
10.1109/icacea.2015.7164731

Related papers

Approximately Lower Triangular Ensembles of LDPC Codes With Linear Encoding Complexity

Shay Freundlich, David Burshtein, Simon N. Litsyn

The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

IEEE Transactions on Information Theory•Apr 1, 2007•18 citations

Approximately Lower Triangular Ensembles of LPDC Codes with Linear Encoding Complexity

Shay Freundlich, David Burshtein, Simon N. Litsyn

The complexity of brute force encoding of LDPC codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•6 citations

A class of QC-LDPC codes with low encoding complexity and good error performance

Wai Tam, Francis C. M. Lau, Chi Kong Tse

We propose a novel approximate lower triangular structure for the parity part of the parity-check matrix of QC-LDPC codes. About half of the non-zero elements in the parity part are set to locate on the upper diagonal while the remaining non-zero elements can be located almost anywhere within the lower triangular area, provided certain rules are observed. Compared with the typical dual-diagonal structure, the proposed structure requires very similar encoding complexity and produces lower error rates over an AWGN channel.

IEEE Communications Letters•Feb 1, 2010•38 citations

Research on Regular LDPC Codes with better Performance than Turbo Codes

Jian-Bing Han, He Yun He

A kind of regular LDPC codes is introduced. Its error correct ability is better than Turbo codes' and near to Shannon limit (1.2 dB). The construct of the sparse parity matrix is important. This effects the LDPC codes' error correct ability. In this paper, diagonal method is adopted to construct sparse check matrix of (n,3,6) in approximate lower triangular form by it. This meets the numbers of nonzero elements and randomness. The Belief Propagation algorithm is used in decoding simulation, to this, vector method is proposed which reduces operation time.

WASE International Conference on Information Engineering•Jul 1, 2009•4 citations

Design and performance evaluation of low complexity encoding methods for LDPC codes

Ambar Bajpai, Lunchakorn Wuttisittikulkij, Piya Kovintavewat

There is an important breakthrough in the field of forward error correction techniques, low-density parity-check (LDPC) codes. These codes have potential to approach the Shannon limit with reliable performance on a given channel, known as the channel capacity. Recently, researchers pay much more attention towards LDPC codes because its performance is better than Turbo codes. However, the LDPC code is the best when it is an irregular code and uses with a very large block-length. Although, the short block-length LDPC codes perform not so well, they are easy to implement in various practical applications. Therefore, there is still a demand of new development on the encoding side of LDPC codes for various ranges of code rate and code length so as to capable of using in many applications.This thesis proposes the development of quasi-cyclic (QC) LDPC codes for column weight 3. In the first part of this thesis, we propose a new construction algorithm of QC-LDPC codes for medium to large block-length by combining QC-LDPC codes of small block-length as their component codes, via Chinese remainder theorem (CRT). Such component codes were constructed by permuting each column block sequentially to attain the desire local girth. After combining all component codes to generate an expanded parity-check matrix, the resulting girth is greater than or at least equal to the maximum girth of the component codes. Simulation results show that our proposed construction method of the parity-check matrix significantly outperforms the other well-known existing methods in terms of low error-floor, simple structure, high performance, and can reduce encoding complexity.In addition, this thesis also proposes two new construction methods for QC-LDPC codes, namely a base matrix method and a subtraction based method. A base matrix based method is a simple, less computational complexity method for constructing the exponent matrix (3, K) of girth 8, 10 and 12 of QC-LDPC codes. Another method is a subtraction method, which has a similar exponent matrix as a base matrix method and has a girth at least 8. Results indicate that the LDPC codes constructed from these two methods have flexibility for arbitrary block-column length K and have a similar BER performance if compared to existing methods.

•Jan 1, 2015•0 citations

A Method for Constructing Quasi-Cycle Extension LDPC Codes with Low Encoding Complexity

Wei Li

Progressive-Edge-Growth(PEG) algorithm is an efficient method for constructing LDPC codes with short and intermediate block lengths.However,the complexity of codes produced directly by this algorithm is proportional to quadratic length of the codes,which restricts the implementation of the LDPC codes.To solve the problem,a method was proposed for constructing quasi-cycle extension LDPC codes with low encoding complexity and good error performance.Based on PEG algorithm,a base matrix with an approximate lower triangular was constructed,then all its elements were replaced by circulation permutations.The new method could eliminate the short cycles effectively without changing the degree distribution fraction of the basic matrix.The simulation results show that: compared with LDPC codes generated by PEG algorithm,the LDPC codes presented here have lower encoding complexity and better error performance,which is easy for implementation with hardware.

Electronics Optics & Control•Jan 1, 2012•1 citation
LDPC codes have become the most popular error control code in various fields like telecommunication, magnetic recording etc. due to their high error correcting capability. The Approximate Lower Triangular (ALT) encoding is the most commonly used encoding technique of LDPC codes. This technique though elegant suffers from the shortcoming that when a particular sub matrix of the H matrix obtained after ALT encoding is singular, the technique fails. In this paper a new algorithm is proposed to handle this shortcoming. In this work a new algorithm is proposed to bring any rectangular sparse LDPC matrix into a rectangular part and a square upper triangular part. This algorithm is implemented to encode a general H matrix. This algorithm is further appended to the ALT format of LDPC encoding and another efficient encoding technique is proposed for LDPC code. Both the proposed techniques have a pre-processing step followed by the actual encoding step. Scatter plots of the H matrices (after preprocessing) are shown. BER performance of the new Modified ALT technique is compared with the existing Systematic Approximate Lower Triangular method. The proposed algorithm gives better BER performance.
The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes
The complexity of brute force encoding of LDPC codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes
We propose a novel approximate lower triangular structure for the parity part of the parity-check matrix of QC-LDPC codes. About half of the non-zero elements in the parity part are set to locate on the upper diagonal while the remaining non-zero elements can be located almost anywhere within the lower triangular area, provided certain rules are observed. Compared with the typical dual-diagonal structure, the proposed structure requires very similar encoding complexity and produces lower error rates over an AWGN channel.
A kind of regular LDPC codes is introduced. Its error correct ability is better than Turbo codes' and near to Shannon limit (1.2 dB). The construct of the sparse parity matrix is important. This effects the LDPC codes' error correct ability. In this paper, diagonal method is adopted to construct sparse check matrix of (n,3,6) in approximate lower triangular form by it. This meets the numbers of nonzero elements and randomness. The Belief Propagation algorithm is used in decoding simulation, to this, vector method is proposed which reduces operation time.
There is an important breakthrough in the field of forward error correction techniques, low-density parity-check (LDPC) codes. These codes have potential to approach the Shannon limit with reliable performance on a given channel, known as the channel capacity. Recently, researchers pay much more attention towards LDPC codes because its performance is better than Turbo codes. However, the LDPC code is the best when it is an irregular code and uses with a very large block-length. Although, the short block-length LDPC codes perform not so well, they are easy to implement in various practical applications. Therefore, there is still a demand of new development on the encoding side of LDPC codes for various ranges of code rate and code length so as to capable of using in many applications.This thesis proposes the development of quasi-cyclic (QC) LDPC codes for column weight 3. In the first part of this thesis, we propose a new construction algorithm of QC-LDPC codes for medium to large block-length by combining QC-LDPC codes of small block-length as their component codes, via Chinese remainder theorem (CRT). Such component codes were constructed by permuting each column block sequentially to attain the desire local girth. After combining all component codes to generate an expanded parity-check matrix, the resulting girth is greater than or at least equal to the maximum girth of the component codes. Simulation results show that our proposed construction method of the parity-check matrix significantly outperforms the other well-known existing methods in terms of low error-floor, simple structure, high performance, and can reduce encoding complexity.In addition, this thesis also proposes two new construction methods for QC-LDPC codes, namely a base matrix method and a subtraction based method. A base matrix based method is a simple, less computational complexity method for constructing the exponent matrix (3, K) of girth 8, 10 and 12 of QC-LDPC codes. Another method is a subtraction method, which has a similar exponent matrix as a base matrix method and has a girth at least 8. Results indicate that the LDPC codes constructed from these two methods have flexibility for arbitrary block-column length K and have a similar BER performance if compared to existing methods.
Progressive-Edge-Growth(PEG) algorithm is an efficient method for constructing LDPC codes with short and intermediate block lengths.However,the complexity of codes produced directly by this algorithm is proportional to quadratic length of the codes,which restricts the implementation of the LDPC codes.To solve the problem,a method was proposed for constructing quasi-cycle extension LDPC codes with low encoding complexity and good error performance.Based on PEG algorithm,a base matrix with an approximate lower triangular was constructed,then all its elements were replaced by circulation permutations.The new method could eliminate the short cycles effectively without changing the degree distribution fraction of the basic matrix.The simulation results show that: compared with LDPC codes generated by PEG algorithm,the LDPC codes presented here have lower encoding complexity and better error performance,which is easy for implementation with hardware.