DOI: https://doi.org/10.15587/1729-4061.2019.157299

On the error­correcting capabilities of iterative error correction codes

Vasyl Semerenko

Abstract


The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.

The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.

A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.

The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.

It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.

A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use

Keywords


cyclic codes; low-density parity-check codes; error-correcting capabilities; iterative decoding; linear finite-state machine; permutations

References


Shennon, K. (1963). Raboty po teorii informacii i kibernetike. Moscow, 829.

Ursul, A. D. (1968). Priroda informacii. Filosofskiy ocherk. Moscow: Politizdat, 288.

Hartley, R. V. L. (1928). Transmission of Information. Bell System Technical Journal, 7 (3), 535–563. doi: https://doi.org/10.1002/j.1538-7305.1928.tb01236.x

Kolmogorov, A. N. (1965). Tri podhoda k opredeleniyu ponyatiya “kolichestvo informacii”. Problemy peredachi informacii, 1 (1), 3–11.

Kolmogorov, A. N. (1987). Teoriya informacii i teoriya algoritmov. Moscow: Nauka, 304.

Bulychev, I. I., Soroka, M. Yu. (2016). About the nature and the essense of information. Noosfernye issledovaniya, 1-2 (13-14), 191–207.

Piterson, U., Ueldon, E. (1976). Kody, ispravlyayushchie oshibki. Moscow: Mir, 596.

Sklyar, B. (2004). Cifrovaya svyaz'. Teoreticheskie osnovy i prakticheskoe primenenie. Moscow: Izd. dom «Vil'yams», 1104.

Klark, Dzh. ml., Keyn, Dzh. (1987). Kodirovanie s ispravleniem oshibok v sistemah cifrovoy svyazi. Moscow: Radio i svyaz', 392.

Dumer, I., Micciancio, D., Sudan, M. (2003). Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory, 49 (1), 22–37. doi: https://doi.org/10.1109/tit.2002.806118

Semerenko, V. (2018). Iterative hard­-decision decoding of combined cyclic codes. Eastern-European Journal of Enterprise Technologies, 1 (9 (91)), 61–72. doi: https://doi.org/10.15587/1729-4061.2018.123207

Garrammone, G., Declercq, D., Fossorier, M. P. C. (2017). Weight Distributions of Non-Binary Multi-Edge Type LDPC Code Ensembles: Analysis and Efficient Evaluation. IEEE Transactions on Information Theory, 63 (3), 1463–1475. doi: https://doi.org/10.1109/tit.2016.2647724

Liu, L., Huang, J., Zhou, W., Zhou, S. (2012). Computing the Minimum Distance of Nonbinary LDPC Codes. IEEE Transactions on Communications, 60 (7), 1753–1758. doi: https://doi.org/10.1109/tcomm.2012.050812.110073a

Uryvskiy, L. A., Osipchuk, S. A.; Bezruk, V. M., Barannik, V. V. (Eds.) (2017). Issledovanie svoystv pomekhoustoychivyh kodov klassa LDPC. Naukoemkie tekhnologii v infokommunikaciyah: obrabotka informacii, kiberbezopasnost', informacionnaya bor'ba. Kharkiv, 137–139.

Tomlinson, M., Tjhai, C. J., Ambroze, M. A., Ahmed, M., Jibril, M. (2017). Error-Correction Coding and Decoding. Bounds, Codes, Decoders, Analysis and Applications. Springer. doi: https://doi.org/10.1007/978-3-319-51103-0

Bocharova, I. E., Kudryashov, B. D., Skachek, V., Yakimenka, Y. (2017). Distance Properties of Short LDPC Codes and Their Impact on the BP, ML and Near-ML Decoding Performance. Lecture Notes in Computer Science, 48–61. doi: https://doi.org/10.1007/978-3-319-66278-7_5

Butler, B. K., Siegel, P. H. (2014). Error Floor Approximation for LDPC Codes in the AWGN Channel. IEEE Transactions on Information Theory, 60 (12), 7416–7441. doi: https://doi.org/10.1109/tit.2014.2363832

Berlekemp, E. (1971). Algebraicheskaya teoriya kodirovaniya. Moscow: Mir, 477.

Semerenko, V. P. (2009). Burst-Error Correction for Cyclic Codes. IEEE EUROCON 2009. doi: https://doi.org/10.1109/eurcon.2009.5167864

Semerenko, V. P. (1998). Parallel Decoding of Bose-Chaudhuri-Hocquenghem Codes. Engineering Simulation, 16 (1), 87–100.

Semerenko, V. P. (2015). Teoriya tsyklichnykh kodiv na osnovi avtomatnykh modelei. Vinnytsia: VNTU, 444.

Gallager, R. (1966). Kody s maloy plotnost'yu proverok na chetnost'. Moscow: Mir, 144.

Semerenko, V. P. (2015). Estimation of the correcting capability of cyclic codes based on their automation models. Eastern-European Journal of Enterprise Technologies, 2 (9 (74)), 16–24. doi: https://doi.org/10.15587/1729-4061.2015.39947


GOST Style Citations


Shennon K. Raboty po teorii informacii i kibernetike. Moscow, 1963. 829 p.

Ursul A. D. Priroda informacii. Filosofskiy ocherk. Moscow: Politizdat, 1968. 288 p.

Hartley R. V. L. Transmission of Information // Bell System Technical Journal. 1928. Vol. 7, Issue 3. P. 535–563. doi: https://doi.org/10.1002/j.1538-7305.1928.tb01236.x 

Kolmogorov A. N. Tri podhoda k opredeleniyu ponyatiya “kolichestvo informacii” // Problemy peredachi informacii. 1965. Vol. 1, Issue 1. P. 3–11.

Kolmogorov A. N. Teoriya informacii i teoriya algoritmov. Moscow: Nauka, 1987. 304 p.

Bulychev I. I., Soroka M. Yu. About the nature and the essense of information // Noosfernye issledovaniya. 2016. Issue 1-2 (13-14). P. 191–207.

Piterson U., Ueldon E. Kody, ispravlyayushchie oshibki. Moscow: Mir. 1976, 596 p.

Sklyar B. Cifrovaya svyaz'. Teoreticheskie osnovy i prakticheskoe primenenie. Moscow: Izd. dom «Vil'yams», 2004. 1104 p.

Klark Dzh. ml., Keyn Dzh. Kodirovanie s ispravleniem oshibok v sistemah cifrovoy svyazi. Moscow: Radio i svyaz', 1987. 392 p.

Dumer I., Micciancio D., Sudan M. Hardness of approximating the minimum distance of a linear code // IEEE Transactions on Information Theory. 2003. Vol. 49, Issue 1. P. 22–37. doi: https://doi.org/10.1109/tit.2002.806118 

Semerenko V. Iterative hard­decision decoding of combined cyclic codes // Eastern-European Journal of Enterprise Technologies. 2018. Vol. 1, Issue 9 (91). P. 61–72. doi: https://doi.org/10.15587/1729-4061.2018.123207 

Garrammone G., Declercq D., Fossorier M. P. C. Weight Distributions of Non-Binary Multi-Edge Type LDPC Code Ensembles: Analysis and Efficient Evaluation // IEEE Transactions on Information Theory. 2017. Vol. 63, Issue 3. P. 1463–1475. doi: https://doi.org/10.1109/tit.2016.2647724 

Computing the Minimum Distance of Nonbinary LDPC Codes / Liu L., Huang J., Zhou W., Zhou S. // IEEE Transactions on Communications. 2012. Vol. 60, Issue 7. P. 1753–1758. doi: https://doi.org/10.1109/tcomm.2012.050812.110073a 

Uryvskiy L. A., Osipchuk S. A. Issledovanie svoystv pomekhoustoychivyh kodov klassa LDPC. Naukoemkie tekhnologii v infokommunikaciyah: obrabotka informacii, kiberbezopasnost', informacionnaya bor'ba: kolekt. monogr. / V. M. Bezruk, V. V. Barannik (Eds.). Kharkiv, 2017. P. 137–139.

Error-Correction Coding and Decoding. Bounds, Codes, Decoders, Analysis and Applications / Tomlinson M., Tjhai C. J., Ambroze M. A., Ahmed M., Jibril M. Springer, 2017. doi: https://doi.org/10.1007/978-3-319-51103-0 

Distance Properties of Short LDPC Codes and Their Impact on the BP, ML and Near-ML Decoding Performance / Bocharova I. E., Kudryashov B. D., Skachek V., Yakimenka Y. // Lecture Notes in Computer Science. 2017. P. 48–61. doi: https://doi.org/10.1007/978-3-319-66278-7_5 

Butler B. K., Siegel P. H. Error Floor Approximation for LDPC Codes in the AWGN Channel // IEEE Transactions on Information Theory. 2014. Vol. 60, Issue 12. P. 7416–7441. doi: https://doi.org/10.1109/tit.2014.2363832 

Berlekemp E. Algebraicheskaya teoriya kodirovaniya. Moscow: Mir, 1971. 477 p.

Semerenko V. P. Burst-Error Correction for Cyclic Codes // IEEE EUROCON 2009. 2009. doi: https://doi.org/10.1109/eurcon.2009.5167864 

Semerenko V. P. Parallel Decoding of Bose-Chaudhuri-Hocquenghem Codes // Engineering Simulation. 1998. Vol. 16, Issue 1. P. 87–100.

Semerenko V. P. Teoriya tsyklichnykh kodiv na osnovi avtomatnykh modelei: monohrafiya. Vinnytsia: VNTU, 2015. 444 p.

Gallager R. Kody s maloy plotnost'yu proverok na chetnost'. Moscow: Mir, 1966. 144 p.

Semerenko V. P. Estimation of the correcting capability of cyclic codes based on their automation models // Eastern-European Journal of Enterprise Technologies. 2015. Vol. 2, Issue 9 (74). P. 16–24. doi: https://doi.org/10.15587/1729-4061.2015.39947 







Copyright (c) 2019 Vasyl Semerenko

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061