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

arXiv:cond-mat/0010073 · Europhysics Letters (EPL)

Statistical mechanics of low-density parity check error-correcting codes over Galois fields

K Nakamura, Y Kabashima, David Saad

Published Nov 1, 2001• 44 citations
arXivHTMLPDF

Abstract

A variation of low-density parity check (LDPC) error-correcting codes defined over Galois fields ( GF ( q )) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C non-zero elements per column. We examine the dependence of the code performance on the value of q , for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q -dependence in the cases of C = 2 and C ⩾ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets.

DOI
10.1209/epl/i2001-00564-y

Related papers

Statistical mechanics of low-density parity check error-correcting codes over Galois fields

Kazutaka Nakamura, 樺島 祥介, Yoshiyuki Kabashima +1 more

(received; accepted) PACS. 89.90+n – Other areas of general interest to physicists. PACS. 89.70+c – Information science. PACS. 05.50+q – Lattice theory and statistics; Ising problems. Abstract. – A variation of low density parity check (LDPC) error correcting codes defined over Galois fields (GF(q)) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C nonzero elements per column. We examine the dependence of the code performance on the value of q, for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q-dependencies in the cases of C = 2 and C ≥ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets. Error correction mechanisms are essential for ensuring reliable data transmission through noisy media. They play an important role in a wide range of applications from magnetic hard

•Jan 1, 2001•14 citations

Statistical physics of regular low-density parity-check error-correcting codes

Tatsuto Murayama, Yoshiyuki Kabashima, David Saad +1 more

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

arXiv:cond-mat/0003121•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Aug 1, 2000•92 citations

Low density parity check codes over GF(q)

Matthew C. Davey, David Mackay

Binary low density parity check (LDPC) codes have been shown to have near Shannon limit performance when decoded using a probabilistic decoding algorithm. The analogous codes defined over finite fields GF(q) of order q>2 show significantly improved performance. We present the results of Monte Carlo simulations of the decoding of infinite LDPC codes which can be used to obtain good constructions for finite codes. We also present empirical results for the Gaussian channel including a rate 1/4 code with bit error probability of 10/sup -4/ at E/sub b//N/sub 0/=-0.05 dB.

IEEE Information Theory Workshop (ITW)•Nov 27, 2002•182 citations

Construction of Structured Nonbinary Low-Density Parity-Check Codes

Wojciech Sułek

Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q) are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems.The nonbinary codes can achieve significantly better performance for short and moderate block lengths.A lot of works concerning "good" LDPC codes parity check matrix construction has been published so far.However, it is well known that efficient partially parallel hardware decoder architectures are allowed only for codes with blockwise partitioned structure of the parity check matrix, called structured codes.In this paper we present a versatile algorithm for construction of codes that are both nonbinary and structured.The proposed algorithm aims at optimizing the code graph (Tanner graph) by reducing the existence of small cycles with low external connectivity, while at the same time selecting appropriate nonzero coefficients from the Galois Field under interest.The algorithm can be used for code construction of any field order, block length and code rate.

International Journal of e-Education e-Business e-Management and e-Learning•Jan 1, 2013•0 citations

Statistical physics of irregular low-density parity-check codes

Renato Vicente, David Saad, Kabashima, Yoshiyuki

Low-density parity-check codes with irregular constructions have recently been shown to outperform the most advanced error-correcting codes to date. In this paper we apply methods of statistical physics to study the typical properties of simple irregular codes. We use the replica method to find a phase transition which coincides with Shannon's coding bound when appropriate parameters are chosen. The decoding by belief propagation is also studied using statistical physics arguments; the theoretical solutions obtained are in good agreement with simulation results. We compare the performance of irregular codes with that of regular codes and discuss the factors that contribute to the improvement in performance.

•Sep 22, 2000•15 citations

Can cyclic codes be useful low-density parity-check codes?

Sarah J. Johnson, Steven R. Weller

Traditionally, low-density parity-check (LDPC) codes are constructed randomly and it is not clear whether algebraically constructed codes, such as cyclic codes, can compete with the error correction performances of the random codes. We consider in this paper new cyclic low-density parity-check codes decoded with the sum-product algorithm. The cyclic codes we present have sparse parity-check matrices, good minimum distance and girth 6. Using frnite-length analysis and simulation results we show that the most significant benefit of the new codes, in terms of error correction performance, is the linearly dependent rows in their parity-check matrices. Our results suggest that increasing column weight to improve the minimum distance and the minimum stopping set size of the code proves beneficial at low erasure probabilities but adversely affects performance in channels with high erasure probabilities.

•Jan 1, 2003•1 citation
A variation of low-density parity check (LDPC) error-correcting codes defined over Galois fields ( GF ( q )) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C non-zero elements per column. We examine the dependence of the code performance on the value of q , for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q -dependence in the cases of C = 2 and C ⩾ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets.
(received; accepted) PACS. 89.90+n – Other areas of general interest to physicists. PACS. 89.70+c – Information science. PACS. 05.50+q – Lattice theory and statistics; Ising problems. Abstract. – A variation of low density parity check (LDPC) error correcting codes defined over Galois fields (GF(q)) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C nonzero elements per column. We examine the dependence of the code performance on the value of q, for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q-dependencies in the cases of C = 2 and C ≥ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets. Error correction mechanisms are essential for ensuring reliable data transmission through noisy media. They play an important role in a wide range of applications from magnetic hard
A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.
Binary low density parity check (LDPC) codes have been shown to have near Shannon limit performance when decoded using a probabilistic decoding algorithm. The analogous codes defined over finite fields GF(q) of order q>2 show significantly improved performance. We present the results of Monte Carlo simulations of the decoding of infinite LDPC codes which can be used to obtain good constructions for finite codes. We also present empirical results for the Gaussian channel including a rate 1/4 code with bit error probability of 10/sup -4/ at E/sub b//N/sub 0/=-0.05 dB.
Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q) are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems.The nonbinary codes can achieve significantly better performance for short and moderate block lengths.A lot of works concerning "good" LDPC codes parity check matrix construction has been published so far.However, it is well known that efficient partially parallel hardware decoder architectures are allowed only for codes with blockwise partitioned structure of the parity check matrix, called structured codes.In this paper we present a versatile algorithm for construction of codes that are both nonbinary and structured.The proposed algorithm aims at optimizing the code graph (Tanner graph) by reducing the existence of small cycles with low external connectivity, while at the same time selecting appropriate nonzero coefficients from the Galois Field under interest.The algorithm can be used for code construction of any field order, block length and code rate.
Low-density parity-check codes with irregular constructions have recently been shown to outperform the most advanced error-correcting codes to date. In this paper we apply methods of statistical physics to study the typical properties of simple irregular codes. We use the replica method to find a phase transition which coincides with Shannon's coding bound when appropriate parameters are chosen. The decoding by belief propagation is also studied using statistical physics arguments; the theoretical solutions obtained are in good agreement with simulation results. We compare the performance of irregular codes with that of regular codes and discuss the factors that contribute to the improvement in performance.
Traditionally, low-density parity-check (LDPC) codes are constructed randomly and it is not clear whether algebraically constructed codes, such as cyclic codes, can compete with the error correction performances of the random codes. We consider in this paper new cyclic low-density parity-check codes decoded with the sum-product algorithm. The cyclic codes we present have sparse parity-check matrices, good minimum distance and girth 6. Using frnite-length analysis and simulation results we show that the most significant benefit of the new codes, in terms of error correction performance, is the linearly dependent rows in their parity-check matrices. Our results suggest that increasing column weight to improve the minimum distance and the minimum stopping set size of the code proves beneficial at low erasure probabilities but adversely affects performance in channels with high erasure probabilities.