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

Cambridge University Press eBooks

LDPC Codes Based on Combinatorial Designs, Graphs, and Superposition

W.E. Ryan, Shu Hwa Lin

Published Sep 17, 2009• 1 citation
Publisher

Abstract

Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs, were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding.

DOI
10.1017/cbo9780511803253.013

Related papers

New Constructions of Quasi-cyclic LDPC Codes Based on Two Classes of Balanced Incomplete Block Designs: For AWGN and Binary Erasure Channels

Lan Lan, Ying Yu Tai, Shu Lin +2 more

Lecture notes in computer science•Jan 1, 2006•0 citations

LDPC Codes: An Introduction

Amin Shokrollahi

LDPC codes are one of the hottest topics in coding theory today. Originally invented in the early 1960’s, they have experienced an amazing comeback in the last few years. Unlike many other classes of codes, LDPC codes are already equipped with very fast (probabilistic) encoding and decoding algorithms. The question is that of the design of the codes such that these algorithms can recover the original codeword in the face of large amounts of noise. New analytic and combinatorial tools make it possible to solve the design problem. This makes LDPC codes not only attractive from a theoretical point of view, but also perfect for practical applications. In this note I will give a brief overview of the origins of LDPC codes and the methods used for their analysis and design.

Birkhäuser Basel eBooks•Jan 1, 2004•144 citations

Construction of Quasi-Cyclic LDPC Codes for AWGN and Binary Erasure Channels: A Finite Field Approach

Lan Lan, Lingqi Zeng, Y.Y. Tai +3 more

In the late 1950s and early 1960s, finite fields were successfully used to construct linear block codes, especially cyclic codes, with large minimum distances for hard-decision algebraic decoding, such as Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes. This paper shows that finite fields can also be successfully used to construct algebraic low-density parity-check (LDPC) codes for iterative soft-decision decoding. Methods of construction are presented. LDPC codes constructed by these methods are quasi-cyclic (QC) and they perform very well over the additive white Gaussian noise (AWGN), binary random, and burst erasure channels with iterative decoding in terms of bit-error probability, block-error probability, error-floor, and rate of decoding convergence, collectively. Particularly, they have low error floors. Since the codes are QC, they can be encoded using simple shift registers with linear complexity.

IEEE Transactions on Information Theory•Jun 28, 2007•264 citations

New constructions of quasi-cyclic LDPC codes based on special classes of BIBD's for the AWGN and binary erasure channels

Lan Lan, Ying Yu Tai, Shu Lin +2 more

This paper presents new methods for constructing efficiently encodable quasi-cyclic LDPC codes based on special balanced incomplete block designs (BIBD's). Codes constructed perform well over both the AWGN and binary erasure channels with iterative decoding.

IEEE Transactions on Communications•Jan 1, 2008•70 citations

A Class of (ypy-l, py, p, y, {0,1, }) Combinatorially Designed LDPC Codes with Application to IS1 Channels

Jing Li, Erozan M. Kurtas

•Jan 1, 2003•0 citations

Novel LDPC coding and decoding strategies : design, analysis, and algorithms

Jingjing Liu

In this digital era, modern communication systems play an essential part in nearly every aspect of life, with examples ranging from mobile networks and satellite communications to Internet and data transfer. Unfortunately, all communication systems in a practical setting are noisy, which indicates that we can either improve the physical characteristics of the channel or find a possible systematical solution, i.e. error control coding. The history of error control coding dates back to 1948 when Claude Shannon published his celebrated work “A Mathematical Theory of Communication”, which built a framework for channel coding, source coding and information theory. For the first time, we saw evidence for the existence of channel codes, which enable reliable communication as long as the information rate of the code does not surpass the so-called channel capacity. Nevertheless, in the following 60 years none of the codes have been proven closely to approach the theoretical bound until the arrival of turbo codes and the renaissance of LDPC codes. As a strong contender of turbo codes, the advantages of LDPC codes include parallel implementation of decoding algorithms and, more crucially, graphical construction of codes. However, there are also some drawbacks to LDPC codes, e.g. significant performance degradation due to the presence of short cycles or very high decoding latency. In this thesis, we will focus on the practical realisation of finite-length LDPC codes and devise algorithms to tackle those issues. \n \nFirstly, rate-compatible (RC) LDPC codes with short/moderate block lengths are investigated on the basis of optimising the graphical structure of the tanner graph (TG), in order to achieve a variety of code rates (0.1 < R < 0.9) by only using a single encoder-decoder pair. As is widely recognised in the literature, the presence of short cycles considerably reduces the overall performance of LDPC codes which significantly limits their application in communication systems. To reduce the impact of short cycles effectively for different code rates, algorithms for counting short cycles and a graph-related metric called Extrinsic Message Degree (EMD) are applied with the development of the proposed puncturing and extension techniques. A complete set of simulations are carried out to demonstrate that the proposed RC designs can largely minimise the performance loss caused by puncturing or extension. \n \nSecondly, at the decoding end, we study novel decoding strategies which compensate for the negative effect of short cycles by reweighting part of the extrinsic messages exchanged between the nodes of a TG. The proposed reweighted belief propagation (BP) algorithms aim to implement efficient decoding, i.e. accurate signal reconstruction and low decoding latency, for LDPC codes via various design methods. A variable factor appearance probability belief propagation (VFAP-BP) algorithm is proposed along with an improved version called a locally-optimized reweighted (LOW)-BP algorithm, both of which can be employed to enhance decoding performance significantly for regular and irregular LDPC codes. More importantly, the optimisation of reweighting parameters only takes place in an offline stage so that no additional computational complexity is required during the real-time decoding process. \n \nLastly, two iterative detection and decoding (IDD) receivers are presented for multiple-input multiple-output (MIMO) systems operating in a spatial multiplexing configuration. QR decomposition (QRD)-type IDD receivers utilise the proposed multiple-feedback (MF)-QRD or variable-M (VM)-QRD detection algorithm with a standard BP decoding algorithm, while knowledge-aided (KA)-type receivers are equipped with a simple soft parallel interference cancellation (PIC) detector and the proposed reweighted BP decoders. In the uncoded scenario, the proposed MF-QRD and VM-QRD algorithms are shown to approach optimal performance, yet require a reduced computational complexity. In the LDPC-coded scenario, simulation results have illustrated that the proposed QRD-type IDD receivers can offer near-optimal performance after a small number of detection/decoding iterations and the proposed KA-type IDD receivers significantly outperform receivers using alternative decoding algorithms, while requiring similar decoding complexity.

•Dec 18, 2012•2 citations
Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs, were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding.
LDPC codes are one of the hottest topics in coding theory today. Originally invented in the early 1960’s, they have experienced an amazing comeback in the last few years. Unlike many other classes of codes, LDPC codes are already equipped with very fast (probabilistic) encoding and decoding algorithms. The question is that of the design of the codes such that these algorithms can recover the original codeword in the face of large amounts of noise. New analytic and combinatorial tools make it possible to solve the design problem. This makes LDPC codes not only attractive from a theoretical point of view, but also perfect for practical applications. In this note I will give a brief overview of the origins of LDPC codes and the methods used for their analysis and design.
In the late 1950s and early 1960s, finite fields were successfully used to construct linear block codes, especially cyclic codes, with large minimum distances for hard-decision algebraic decoding, such as Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes. This paper shows that finite fields can also be successfully used to construct algebraic low-density parity-check (LDPC) codes for iterative soft-decision decoding. Methods of construction are presented. LDPC codes constructed by these methods are quasi-cyclic (QC) and they perform very well over the additive white Gaussian noise (AWGN), binary random, and burst erasure channels with iterative decoding in terms of bit-error probability, block-error probability, error-floor, and rate of decoding convergence, collectively. Particularly, they have low error floors. Since the codes are QC, they can be encoded using simple shift registers with linear complexity.
In this digital era, modern communication systems play an essential part in nearly every aspect of life, with examples ranging from mobile networks and satellite communications to Internet and data transfer. Unfortunately, all communication systems in a practical setting are noisy, which indicates that we can either improve the physical characteristics of the channel or find a possible systematical solution, i.e. error control coding. The history of error control coding dates back to 1948 when Claude Shannon published his celebrated work “A Mathematical Theory of Communication”, which built a framework for channel coding, source coding and information theory. For the first time, we saw evidence for the existence of channel codes, which enable reliable communication as long as the information rate of the code does not surpass the so-called channel capacity. Nevertheless, in the following 60 years none of the codes have been proven closely to approach the theoretical bound until the arrival of turbo codes and the renaissance of LDPC codes. As a strong contender of turbo codes, the advantages of LDPC codes include parallel implementation of decoding algorithms and, more crucially, graphical construction of codes. However, there are also some drawbacks to LDPC codes, e.g. significant performance degradation due to the presence of short cycles or very high decoding latency. In this thesis, we will focus on the practical realisation of finite-length LDPC codes and devise algorithms to tackle those issues. \n \nFirstly, rate-compatible (RC) LDPC codes with short/moderate block lengths are investigated on the basis of optimising the graphical structure of the tanner graph (TG), in order to achieve a variety of code rates (0.1 < R < 0.9) by only using a single encoder-decoder pair. As is widely recognised in the literature, the presence of short cycles considerably reduces the overall performance of LDPC codes which significantly limits their application in communication systems. To reduce the impact of short cycles effectively for different code rates, algorithms for counting short cycles and a graph-related metric called Extrinsic Message Degree (EMD) are applied with the development of the proposed puncturing and extension techniques. A complete set of simulations are carried out to demonstrate that the proposed RC designs can largely minimise the performance loss caused by puncturing or extension. \n \nSecondly, at the decoding end, we study novel decoding strategies which compensate for the negative effect of short cycles by reweighting part of the extrinsic messages exchanged between the nodes of a TG. The proposed reweighted belief propagation (BP) algorithms aim to implement efficient decoding, i.e. accurate signal reconstruction and low decoding latency, for LDPC codes via various design methods. A variable factor appearance probability belief propagation (VFAP-BP) algorithm is proposed along with an improved version called a locally-optimized reweighted (LOW)-BP algorithm, both of which can be employed to enhance decoding performance significantly for regular and irregular LDPC codes. More importantly, the optimisation of reweighting parameters only takes place in an offline stage so that no additional computational complexity is required during the real-time decoding process. \n \nLastly, two iterative detection and decoding (IDD) receivers are presented for multiple-input multiple-output (MIMO) systems operating in a spatial multiplexing configuration. QR decomposition (QRD)-type IDD receivers utilise the proposed multiple-feedback (MF)-QRD or variable-M (VM)-QRD detection algorithm with a standard BP decoding algorithm, while knowledge-aided (KA)-type receivers are equipped with a simple soft parallel interference cancellation (PIC) detector and the proposed reweighted BP decoders. In the uncoded scenario, the proposed MF-QRD and VM-QRD algorithms are shown to approach optimal performance, yet require a reduced computational complexity. In the LDPC-coded scenario, simulation results have illustrated that the proposed QRD-type IDD receivers can offer near-optimal performance after a small number of detection/decoding iterations and the proposed KA-type IDD receivers significantly outperform receivers using alternative decoding algorithms, while requiring similar decoding complexity.