The graphical structure of iterative low-density parity-check decoding

立平 森, Ryuhei Mori

Florent Pirou

Eric T. Psota, Lance C. Pérez

The error mechanisms of iterative message‐passing decoders for low‐density parity‐check codes are studied. A tutorial review is given of the various graphical structures, including trapping sets, stopping sets, and absorbing sets that are frequently used to characterize the errors observed in simulations of iterative decoding of low‐density parity‐check codes. The connections between trapping sets and deviations on computation trees are explored in depth using the notion ofproblematictrapping sets in order to bridge the experimental and analytic approaches to these error mechanisms. A new iterative algorithm for finding low‐weight problematic trapping sets is presented and shown to be capable of identifying many trapping sets that are frequently observed during iterative decoding of low‐density parity‐check codes on the additive white Gaussian noise channel. Finally, a new method is given for characterizing the weight of deviations that result from problematic trapping sets.

Gulnihal Mercanoglu, Achilleas Anastasopoulos, S. Sandeep Pradhan

Capacity-approaching quantum error correction faces a fundamental tension: the required parity-check matrices need to become increasingly dense, while practical decoding and syndrome extraction favor sparse, bounded-degree structures. Reconciling these competing requirements remains an important open problem in quantum code design. We construct Calderbank-Shor-Steane (CSS) code ensembles that approach the CSS rate over memoryless Pauli channels under maximum-likelihood decoding while retaining sparse, bounded-degree graphical representations. The construction separates parity-check density from graphical complexity: although capacity-approaching components may require dense parity-check matrices, they are represented by sparse concatenated factor graphs. We first study a construction combining low-density parity-check (LDPC) and low-density generator-matrix (LDGM) component codes and numerically analyze the average weight distributions of the resulting codes. Motivated by these results, we introduce a second construction based on concatenated LDPC and LDGM codes and generalized irregular repeat-accumulate (GIRA) codes. We derive bounds on the average weight distribution of the resulting sum ensemble and use the Miller-Burshtein framework to prove simultaneous reliability of the two CSS decoding components. Consequently, the proposed ensemble achieves rates arbitrarily close to the CSS hashing bound under separate bit- and phase-error correction, while maintaining bounded graphical complexity, thus providing a foundation for future iterative decoders and indirect syndrome-extraction architectures.

А В Башкиров, А. А. Пирогов, O Y Makarov +3 more

Abstract The article deals with the peculiarities of modeling the characteristics of low-density parity-check codes (LDPC) in terms of their decoding. When decoding low-density parity-check codes in various communication standards, the iterative belief propagation algorithm (BP) and its various modifications - Pearl’s algorithm, sum-of-products algorithm - are widely used. In the article, special attention is given to this algorithm. The BP algorithm is a message-passing algorithm on a graphical model and consists of two basic messaging procedures between the nodes in the Tanner graph for LDPC code. The issues of constructing an effective architecture for an iterative decoder operating on the belief propagation algorithm in a heterogeneous system with massively parallel computing on a graphics processing unit are considered. It is shown that the use of the GPU allows to achieve a significant gain in decoding time with a sufficient size of the test matrix (a sufficient number of code and test nodes), obtained due to the parallelism of the architecture. Expressions for calculation of the size of the “working group” are given. The benefit of using a modified decoder architecture is estimated.

Pirouz Zarrinkhat