# 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] Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $A_n$-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118 [2] Patrick W. Dondl, Martin Jesenko. Threshold phenomenon for homogenized fronts in random elastic media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 353-372. doi: 10.3934/dcdss.2020329 [3] 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, 2020  doi: 10.3934/dcdss.2020451 [4] Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316 [5] Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339 [6] Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458 [7] Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051 [8] Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024 [9] Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

2019 Impact Factor: 0.734