# 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] W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 [2] Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637 [3] Charles Amorim, Miguel Loayza, Marko A. Rojas-Medar. The nonstationary flows of micropolar fluids with thermal convection: An iterative approach. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2509-2535. doi: 10.3934/dcdsb.2020193 [4] Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 [5] Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 [6] Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 [7] Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79 [8] John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004 [9] Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265 [10] Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $\mathbb{Z}_4+u\mathbb{Z}_4$. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135 [11] Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $p$-ary $t$-weight linear codes to Ramanujan Cayley graphs with $t+1$ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133

2019 Impact Factor: 0.734