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

David Saad, Yoshiyuki Kabashima, Tatsuto Murayama +1 more

祥介 樺島, YOSHIYUKI KABASHIMA

K Nakamura, Y Kabashima, David Saad

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.

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

祥介 樺島, Yoshiyuki Kabashima, David Saad

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.