Iterative hard­-decision decoding of combined cyclic codes

Authors

DOI:

https://doi.org/10.15587/1729-4061.2018.123207

Keywords:

iterative decoding, cyclic codes, Hamming codes, linear finite-state machine, interleaving

Abstract

We propose error correction iteratively decodable cyclic codes (IDCC) that consist of two cyclic Hamming codes with different generator polynomials. As a mathematical apparatus, we apply the theory of linear finite-state machines (LFSM) in binary Galois fields. A generalized decoding algorithm was constructed based on power permutation of bits in the code word and the new technique for combining the codes.

By using hard decisions only, it is possible to achieve high speed and simple hardware-software implementation of encoder and decoder on linear feedback shift registers. The IDCC (n, k)-code makes it possible to correct the errors of multiplicity to (n−k). A code word may have arbitrary length: both small and large. Code rate (k/n) is close to one.

It was established in the course of research that approaching the theoretical limit (border) by Shannon maximally close significantly increases length of codes, complicates encoders and decoders, increases a delay in decoding, and other problems appear. That is why the main criterion for the optimality of error correction coding is proposed to be those code characteristics that are important for practical application (time and hardware costs, focus on contemporary circuitry and parallel processing). From this point of view, the developed IDCC codes can be considered as an alternative to well-known iterative codes (LDPC codes and turbo codes) whose main advantage is the maximum proximity to the Shannon limit.

This is important because at the present stage of development of science and technology one of the relevant scientific and technological problems is the task on ensuring high reliability of data transmission in different systems of digital communication. The proposed codes make it possible to solve the specified task at minimal resource costs and high efficiency.

Author Biography

Vasyl Semerenko, Vinnytsia National Technical University Khmelnytske highway, 95, Vinnytsia, Ukraine, 21021

PhD, Associate Professor

Department of computer technique

References

  1. Shennon, K. (1963). Raboty po teorii informatsii i kibernetike. Moscow: Izd-vo inostr. lit., 829.
  2. Gallager, R. G. (1963). Low Density Parity-Check Codes. Cambridge: M.I.T. Press, 90.
  3. Berrou, C., Glavieux, A., Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1. Proceedings of ICC ’93 – IEEE International Conference on Communications. doi: 10.1109/icc.1993.397441
  4. Vargauzin, V. (2005). Vblizi granitsy Shennona. Telemul'timedia, 6, 3–10.
  5. Morelos-Saragosa, R. (2006). Iskusstvo pomekhoustoychivogo kodirovaniya. Metody, algoritmy, primenenie. Moscow: Tekhnosfera, 320.
  6. Sklyar, B. (2004). Tsifrovaya svyaz'. Teoreticheskie osnovy i prakticheskoe primenenie. Moscow: Izd. dom «Vil'yams», 1104.
  7. Stollings, V. (2002). Komp'yuternye sistemy peredachi dannyh. Moscow: Izdatel'skiy dom «Vil'yams», 928.
  8. Topalov, V. V. (2014). The modification the bi-directional Soft Output Viterbi Algorithm for decoding of turbo product codes. Technology audit and production reserves, 6 (3 (20)), 62–65. doi: 10.15587/2312-8372.2014.34592
  9. Novikov, R. S., Astrahantsev, A. A. (2014). Vybor parametrov LDPC kodov dlya kanalov s ABGSH. Systemy obrobky informatsiyi, 1 (117), 195–199.
  10. Tomlinson, M., Tjhai, C. J., Ambroze, M. A., Ahmed, M., Jibril, M. (2014). Error-Correction Coding and Decoding. Bounds, Codes, Decoders, Analysis and Applications. Springer International Publisher, 522. doi: 10.1007/978-3-319-51103-0
  11. Mankar, M. V., Asutkar, G. M., Dakhole, P. K. (2016). Quasi Cyclic Low Density Parity Check Decoder Using Min-sum Algorithm for IEEE 802.11n. IOSR Journal of VLSI and Signal Processing, 06 (04), 01–07. doi: 10.9790/4200-0604020107
  12. ETSI Standard EN 302 307-2 V1.1.1: Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2) (2005). European Telecommunications Standards Institute, Valbonne.
  13. Revathy, M., Saravanan, R. (2015). A Low-Complexity Euclidean Orthogonal LDPC Architecture for Low Power Applications. The Scientific World Journal, 2015, 1–8. doi: 10.1155/2015/327357
  14. Zolotarev, V. V., Zubarev, Yu. B., Ovechkin, G. V. (2012). Mnogoporogovye dekodery i optimizatsionnaya teoriya kodirovaniya. Moscow: Goryachaya liniya – Telekom, 239.
  15. Li, J., Lin, S., Abdel-Ghaffar, K., Ryan, W. E., Costello, D. J. J. (2016). LDPC Code Designs, Constructions, and Unification. Cambridge University Press. doi: 10.1017/9781316780152
  16. Kim, S., Sobelman, G. E. (2013). Scaling, Offset, and Balancing Techniques in FFT-Based BP Nonbinary LDPC Decoders. IEEE Transactions on Circuits and Systems II: Express Briefs, 60 (5), 277–281. doi: 10.1109/tcsii.2013.2251959
  17. Fedorenko, S., Kolesnik, V. (1995). Multi-step decoding of the iteration of Hamming codes. Proc. of the Seventh Joint Swedish-Russian International Workshop on Information Theory. Saint Petersburg, 80–83.
  18. Yang, Z., Li, S., Feng, H., Honold, T., Yu, G. (2009). Cross-Layer Iterative Decoding of Irregular LDPC Codes using Cyclic Redundancy Check Codes. 2009 IEEE Wireless Communications and Networking Conference. doi: 10.1109/wcnc.2009.4917653
  19. Zhang, L., Huang, Q., Lin, S. (2010). Iterative decoding of a class of cyclic codes. 2010 Information Theory and Applications Workshop (ITA). doi: 10.1109/ita.2010.5454113
  20. Forni, D. (1970). Kaskadnye kody. Moscow: Mir, 207.
  21. Klark, ml. Dzh., Keyn, Dzh. (1987). Kodirovanie s ispravleniem oshibok v sistemah tsifrovoy svyazi. Moscow: Radio i svyaz', 392.
  22. 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: 10.15587/1729-4061.2015.39947
  23. Semerenko, V. P. (2015). Teoriya tsyklichnykh kodiv na osnovi avtomatnykh modelei. Vinnytsia: VNTU, 444.
  24. Gill, A. (1974). Lineynye posledovatel'nostnye mashiny. Moscow: Nauka, 288.
  25. Semerenko, V. P. (1998). Parallel Decoding of Bose-Chaudhuri-Hocquenghem Codes. Engineering Simulation, 16 (1), 87–100.
  26. Kasami, T., Tokura, H., Ivadari, E., Inagaki, Ya. (1978). Teoriya kodirovaniya. Moscow: Mir, 576.
  27. Prange, E. (1957). Cyclic error-correcting codes in two symbols. Air Force Cambridge Research Center, 26.
  28. Kognovitskiy, O. S. (2009). Dvoystvenniy bazis i ego primenenie v telekommunikatsiyah. Sankt-Peterburg: Link, 411.
  29. Hlynov, A. A. (2012). Issledovanie printsipov realizatsii LDPC kodeka na PLIS. Materialy mezhdunar. nauch.-tekhn. konf. “INTERMATIC – 2012”. Moscow, 150–156.
  30. Semerenko, V. P. (2015). Theory and practice of CRC codes: new results based on automaton models. Eastern-European Journal of Enterprise Technologies, 4 (9 (76)), 38–48. doi: 10.15587/1729-4061.2015.47860

Downloads

Published

2018-02-09

How to Cite

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

Issue

Vol. 1 No. 9 (91) (2018): Information and controlling system

Section

Information and controlling system

License

Copyright (c) 2018 Vasyl Semerenko

Creative Commons License

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

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.