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

Lecture notes in computer science

Low density parity check codes based on sparse matrices with no small cycles

J.W. Bond, Siqi Hui, H. Schmidt

Published Jan 1, 1997• 4 citations
Publisher
DOI
10.1007/bfb0024448

Related papers

Regular Low-Density Parity-Check codes based on shifted identity matrices

Shanbao He, Chunming Zhao, Ming Jiang

Journal of Electronics (China)•Jan 1, 2006•0 citations

An improved method for counting 6-cycles in low-density parity-check codes

Djamel Slimani, Abdellah Kaddai

Since their rediscovery in the early 1990s, low-density parity-check (LDPC) codes have become the most popular error-correcting codes owing to their excellent performance. An LDPC code is a linear block code that has a sparse parity-check matrix. Cycles in this matrix, particularly short cycles, degrade the performance of such a code. Hence, several methods for counting short cycles in LDPC codes have been proposed, such as Fan?s method to detect 4-cycles, 6- cycles, 8-cycles, and 10-cycles. Unfortunately, this method fails to count all 6- cycles, i.e., ignores numerous 6-cycles, in some given parity-check matrices. In this paper, an improvement of this algorithm is presented that detects all 6-cycles in LDPC codes, as well as in general bipartite graphs. Simulations confirm that the improved method offers the exact number of 6-cycles, and it succeeds in detecting those ignored by Fan?s method.

Serbian Journal of Electrical Engineering•Jan 1, 2023•0 citations

The low-density parity-check codes based on The n-queen problem

Li Peng, Guangxi Zhu, Xiao Liu

This paper presents a new family of low-density parity-check (LDPC) code, the sparse parity-check matrix of which is constructed by self-defining non-diagonal identity sub-matrix that is a solution of the "n-queen problem". So this sub-matrix is called the Q-matrix and these LDPC codes are called the Q-matrixes LDPC codes. The Q-matrixes LDPC codes are good or very good codes with iterative decoding and their Tanner graphs are free of 4-lines cycle. Furthermore, they can be created in cycle form. Their encoding can be achieved in linear time. Especially, their code length and code rate can be flexible and quickly adjusted according to the practical situation, and the performance of high rate is also very good. The other unique excellence is that the large sparse parity-check matrixes of long Q-matrixes LDPC codes require very small storage space. The result of this paper is very significant not only for designing low complexity encoder, improving performance and reducing the complexity of the sum-product iterative decoding algorithm, but also for building practice system of encodable and decodable LDPC code.

•Oct 15, 2004•6 citations

REGULAR LOW-DENSITY PARITY-CHECK CODES BASED ON SHIFTED IDENTITY MATRICES

He, Shanbao, Zhao +3 more

Journal of Electronics (China)•Jan 1, 2006•0 citations

A NEW FAMILY OF LOW-DENSITY PARITY CHECK CODES WITH LARGE GIRTH AND LOW COMPLEXITY

Xu Xia, Yanping Li, Moon Ho Lee

한국통신학회 학술대회 및 강연회•Apr 1, 2004•0 citations

Toward Universal Belief Propagation Decoding for Short Binary Block Codes

Yifei Shen, Zongyao Li, Yuqing Ren +5 more

Belief propagation (BP) decoding has been recognized for its capacity-approaching performance and high throughput when decoding long low-density parity-check (LDPC) codes. However, the application of BP decoding for short codes is hindered by dense parity-check matrices (PCMs) and prevalent short cycles in the Tanner graph. In this paper, we introduce a general method to extract an optimized sparse PCM for short binary block codes, which removes length-four cycles and enhances the connectivity of short cycles to enable BP decoding with improved performance. Notably, for short binary codes with lengths up to 64, our BP decoding performance approaches the maximum likelihood bound and surpasses the best-reported BP results with reduced computational complexity. Compared with other universal decoding algorithms, BP decoding using our extracted sparse PCMs is competitive in terms of both error-rate performance and computational complexity. These promising results suggest that our method to improve BP decoding for short codes is a step toward a practical universal BP decoder for next-generation communication systems.

IEEE Journal on Selected Areas in Communications•Feb 14, 2025•9 citations
Since their rediscovery in the early 1990s, low-density parity-check (LDPC) codes have become the most popular error-correcting codes owing to their excellent performance. An LDPC code is a linear block code that has a sparse parity-check matrix. Cycles in this matrix, particularly short cycles, degrade the performance of such a code. Hence, several methods for counting short cycles in LDPC codes have been proposed, such as Fan?s method to detect 4-cycles, 6- cycles, 8-cycles, and 10-cycles. Unfortunately, this method fails to count all 6- cycles, i.e., ignores numerous 6-cycles, in some given parity-check matrices. In this paper, an improvement of this algorithm is presented that detects all 6-cycles in LDPC codes, as well as in general bipartite graphs. Simulations confirm that the improved method offers the exact number of 6-cycles, and it succeeds in detecting those ignored by Fan?s method.
This paper presents a new family of low-density parity-check (LDPC) code, the sparse parity-check matrix of which is constructed by self-defining non-diagonal identity sub-matrix that is a solution of the "n-queen problem". So this sub-matrix is called the Q-matrix and these LDPC codes are called the Q-matrixes LDPC codes. The Q-matrixes LDPC codes are good or very good codes with iterative decoding and their Tanner graphs are free of 4-lines cycle. Furthermore, they can be created in cycle form. Their encoding can be achieved in linear time. Especially, their code length and code rate can be flexible and quickly adjusted according to the practical situation, and the performance of high rate is also very good. The other unique excellence is that the large sparse parity-check matrixes of long Q-matrixes LDPC codes require very small storage space. The result of this paper is very significant not only for designing low complexity encoder, improving performance and reducing the complexity of the sum-product iterative decoding algorithm, but also for building practice system of encodable and decodable LDPC code.
Belief propagation (BP) decoding has been recognized for its capacity-approaching performance and high throughput when decoding long low-density parity-check (LDPC) codes. However, the application of BP decoding for short codes is hindered by dense parity-check matrices (PCMs) and prevalent short cycles in the Tanner graph. In this paper, we introduce a general method to extract an optimized sparse PCM for short binary block codes, which removes length-four cycles and enhances the connectivity of short cycles to enable BP decoding with improved performance. Notably, for short binary codes with lengths up to 64, our BP decoding performance approaches the maximum likelihood bound and surpasses the best-reported BP results with reduced computational complexity. Compared with other universal decoding algorithms, BP decoding using our extracted sparse PCMs is competitive in terms of both error-rate performance and computational complexity. These promising results suggest that our method to improve BP decoding for short codes is a step toward a practical universal BP decoder for next-generation communication systems.