Iterative List Decoding of LDPC Codes

JØrn Justesen, Tom Høholdt, Johann Hjaltason

We present an iterative list decoding algorithm for low-density parity-check (LDPC) codes. In particular we apply this decoder to a class of LDPC codes from finite geometries and show that the (73,45,10) projective geometry code can be maximum-likelihood (ML) decoded with low complexity. Moreover, the list decoding approach enables us to give a theoretical analysis of the performance. We also consider list bit-flipping (BF) decoding of longer LDPC codes.

Marco Chiani

Ligter, Luca

William Gay, Fernando Granha Jeronimo, Abhi Shukul

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

Telex M. N. Ngatched, Fambirai Takawira

Abstract In this paper, a list decoding algorithm for lowdensity parity-check (LDPC) codes is presented. The algorithm uses a modification of the simple Gallager bit-flipping algorithm to generate a sequence of candidate codewords iteratively one at a time using a set of test error patterns based on the reliability information of the received symbols. It is particularly efficient for short block LDPC codes, both regular and irregular. Computer simulation results are used to compare the performance of the proposed algorithm with other known decoding algorithms for LDPC codes, with the result that the presented algorithm offers excellent performances. Performances comparable to those obtained with iterative decoding based on belief propagation can be achieved at a much smaller complexity. 1 I.

Yilmaz, Fatmanur

Low-density parity-check (LDPC) codes have become a standard in modern communication systems thanks to their near-optimal error correction performance, which approaches Shannon's channel capacity as block length increases. However, in scenarios requiring short block lengths with low undetected frame error rate (UFER)-such as command and control data transmission in satellite communications-using only iterative decoders fails to achieve a balance between undetected and total frame error rates (FERs). This thesis addresses these challenges by investigating post-decoding error detection methods that enhance iterative LDPC decoding to achieve target FERs for both total and undetected errors. Specifically, we work with (128, 64) LDPC codes and explore two novel post-decoding techniques: bounded angle iterative decoding and single bit flip (SBF) list decoding, a variation of SBF decoding. These methods are applied to the iterative LDPC decoder output to manage the trade-off between total and undetected FERs effectively. Our results demonstrate that bounded angle iterative decoding effectively reduces UFER in codes with a large minimum distance with maintaining an acceptable increase in total frame error rate (TFER). Meanwhile, SBF list decoding mitigates the UFER increase introduced by standard SBF decoding, while retaining the significant TFER improvement that SBF decoding offers.