# American Institute of Mathematical Sciences

February  2017, 11(1): 123-137. doi: 10.3934/amc.2017007

## On the multiple threshold decoding of LDPC codes over GF(q)

 1 Skolkovo Institute of Science and Technology (Skoltech), and Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia 2 Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia

A part of the results of this paper were presented at the 2015 IEEE International Symposium on Information Theory, June 2015, Hong Kong [7].

Received  July 2015 Revised  March 2016 Published  February 2017

Fund Project: The research was carried out at the IITP RAS and supported by the Russian Science Foundation (project no. 14-50-00150).

We consider decoding of LDPC codes over GF(q) with a harddecision low-complexity majority algorithm, which is a generalization of the bit-flipping algorithm for binary LDPC codes. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time, introducing multiple thresholds does not affect the order of decoding complexity.

Citation: Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007
##### References:

show all references

##### References:
Tanner graph
Single threshold decoding. The lower estimate $L(W)$ is valid only up to $W^*$, that is why the line is dashed after the point. Points A, C and B have coordinates ($W^*/2$; $W^* \ell/2$), ($W^{(S)}$; $W^{(S)} \ell$) and ($W^*$; $W^* \ell / 2$) accordingly
A subgraph of Tanner graph
Multiple thresholds. The lower estimate $L(W)$ is valid only up to $W^*$, that is why the line is dashed after the point
The dependency of $\alpha^{(S)}$ and $\alpha^{(M)}$ on $\ell$
Results for $q=16$
 ($\ell$, $n_0$); $R$ $\delta$ $\omega^*$ $\rho^{(S)}$ $\rho^{(M)}$ $\rho^{(M)}/\rho^{(S)}$ (45, 52); 0.135 0.6130 0.0103 0.0053 0.0065 1.226 (43, 58); 0.26 0.4855 0.0095 0.0049 0.0060 1.224 (40, 64); 0.375 0.3797 0.0085 0.0044 0.0054 1.227 (31, 62); 0.5 0.2808 0.0072 0.0037 0.0046 1.243 (24, 64); 0.625 0.1935 0.0053 0.0028 0.0034 1.214 (24, 96); 0.75 0.1168 0.0033 0.0017 0.0021 1.235 (26,208);0.875 0.0507 0.0015 0.0008 0.0010 1.250
 ($\ell$, $n_0$); $R$ $\delta$ $\omega^*$ $\rho^{(S)}$ $\rho^{(M)}$ $\rho^{(M)}/\rho^{(S)}$ (45, 52); 0.135 0.6130 0.0103 0.0053 0.0065 1.226 (43, 58); 0.26 0.4855 0.0095 0.0049 0.0060 1.224 (40, 64); 0.375 0.3797 0.0085 0.0044 0.0054 1.227 (31, 62); 0.5 0.2808 0.0072 0.0037 0.0046 1.243 (24, 64); 0.625 0.1935 0.0053 0.0028 0.0034 1.214 (24, 96); 0.75 0.1168 0.0033 0.0017 0.0021 1.235 (26,208);0.875 0.0507 0.0015 0.0008 0.0010 1.250
Results for $q=64$
 ($\ell$, $n_0$); $R$ $\delta$ $\omega^*$ $\rho^{(S)}$ $\rho^{(M)}$ $\rho^{(M)}/\rho^{(S)}$ (21, 24); 0.125 0.7355 0.0156 0.0082 0.0099 1.207 (24, 32); 0.25 0.5863 0.0131 0.0068 0.0083 1.221 (20, 32); 0.375 0.4585 0.0104 0.0054 0.0066 1.222 (22, 44); 0.5 0.3445 0.0081 0.0042 0.0052 1.238 (27, 72); 0.625 0.2415 0.0059 0.0031 0.0038 1.226 (24, 96); 0.75 0.1485 0.0037 0.0019 0.0024 1.263 (26,208); 0.875 0.0661 0.0017 0.0009 0.0011 1.222
 ($\ell$, $n_0$); $R$ $\delta$ $\omega^*$ $\rho^{(S)}$ $\rho^{(M)}$ $\rho^{(M)}/\rho^{(S)}$ (21, 24); 0.125 0.7355 0.0156 0.0082 0.0099 1.207 (24, 32); 0.25 0.5863 0.0131 0.0068 0.0083 1.221 (20, 32); 0.375 0.4585 0.0104 0.0054 0.0066 1.222 (22, 44); 0.5 0.3445 0.0081 0.0042 0.0052 1.238 (27, 72); 0.625 0.2415 0.0059 0.0031 0.0038 1.226 (24, 96); 0.75 0.1485 0.0037 0.0019 0.0024 1.263 (26,208); 0.875 0.0661 0.0017 0.0009 0.0011 1.222
 [1] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [2] Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046 [3] Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005 [4] Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 [5] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [6] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433 [7] Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385 [8] Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83 [9] Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179 [10] Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419 [11] Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1 [12] Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49 [13] Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485 [14] Robert F. Bailey, John N. Bray. Decoding the Mathieu group M12. Advances in Mathematics of Communications, 2007, 1 (4) : 477-487. doi: 10.3934/amc.2007.1.477 [15] Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020089 [16] Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259 [17] Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002 [18] Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311 [19] Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331 [20] Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009

2019 Impact Factor: 0.734