Information technologies and computer sciences

Automaton Presentations of Cyclic Codes

Authors

V. P. Semerenko
Vinnytsia National Technical University ROR

Keywords

automaton cyclic codes linear finite-state machines encoder decoder

Abstract

Known methods for representing cyclic codes (polynomial, matrix, and algebraic) are suitable for all classes of linear block error-correcting codes, but they do not take into account the particularities of specific classes of the codes. For example, the cycle property of the cyclic codes contains large potential features that are not nearly used in the specified methods of code representation.

The automaton representations of cyclic codes using finite automaton in Galois fields – linear finite-state machine (LFSM) – are proposed. This type of finite automaton belongs to the systems the processes of which are developing in time cyclically, i.e. to dynamic systems. The automaton-analytic and automaton-graphical models are considered. Accordingly, the definition of cyclic codes based on these automaton models is given. The relationship between the automaton representation and the known representations of cyclic codes is shown.

The classification of LFSM from the positions of the automaton representation of cyclic codes is done. For the first time, two characteristic LFSM matrices are taken into account for classification, which makes it possible to distinguish four basic LFSM types: recursive LFSM and non-recursive LFSM of Galois and Fibonacci. When taking into account the direction of data movement, it is possible to distinguish between left-hand and right-hand LFSM, i.e. eight types of LFSM.

A study of the procedures of systematic encoding and decoding of cyclic codes based on their automaton-analytical models is carried out. It is shown that all types of LFSM give an identical result at encoding and decoding, but with different labor intensiveness. The hardware implementation for each type of LFSM is theoretically substantiated. Criteria over type selection LFSM of relatively physical time and hardware-software expenses are brought.

Basic advantage of methods of encoding and decoding of cyclic codes based on offered mathematical models is the linear complexity of computations and simple hardware-software implementation.

303 243

How to Cite

[1]
“Automaton Presentations of Cyclic Codes”, Вісник ВПІ, no. 2, pp. 89–100, Apr. 2018, Accessed: Oct. 03, 2026. Available: https://visnyk.vntu.edu.ua/index.php/visnyk/article/view/2219

Author Biography

V. P. Semerenko, Vinnytsia National Technical University

 Cand. Sc. (Eng.), Associate Professor, Associate Professor of the Chair of Computer Technique,

References

Р. Морелос-Сарагоса, Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Москва, Россия: Техносфера, 2006.
В. Д. Колесник, Кодирование при передаче и хранении информации (Алгебраическая теория блоковых кодов). Москва, Россия: Высш. школа, 2009.
Э. С. Айчифер, и Б. У. Джервис, Цифровая обработка сигналов: практический подход, 2-е изд. испр. Москва, Россия: Издательский дом «Вильямс», 1992.
Р. Лидл, и Г. Нидеррайтер, Конечные поля. В 2 т., Т. 1. Москва, Россия: Мир, 1988.
О. П. Кузнецов, и Г. М. Адельсон-Вельский. Дискретная математика для инженера, 2-е изд. Москва, Россия: Энергоатомиздат, 1988.
B. Friedland, “Linear Modular Sequential Circuits,” IRE Trans, vol. 6, pp. 61-68, 1959.
А. Гилл, Линейные последовательностные машины. Москва, Россия : Наука, 1974.
В. П. Семеренко, Теорія циклічних кодів на основі автоматних моделей. Вінниця, Україна : ВНТУ, 2015.
F. Arnault, T. Berger, and M. Minier, “Revisiting LFSRs for Cryptographic Applications,” IEEE Transactions on Information Theory, vol. 57, no. 12, pp. 8095-8113, 2011.
E. Milovanovic, M. Stojcev, I. Milovanovic, and T. Nikolic, “Concurrent Generation of Pseudo Random Numbers with LFSR of Fibonacci and Galois Type,” Computing and Informatics, vol. 34, pp. 941-958, 2015.
V. P. Semerenko, “The Theory of Parallel CRC Codes Based on Automaton Models,” Eastern-European Journal of Enterprise Technologies, vol. 6, issue 9 (84), pp. 45-55. 2016. doi: 10.15587/1729-4061.2016.85603.
Т. Х. Кормен, Ч. Е. Лейзерсон, Р. Л. Ривест, и К. Штайн, Алгоритмы: построение и анализ, 3-е изд. Москва, Россия: ООО Издательский дом «Вильямс», 2014.
В. П. Семеренко, «Высокопроизводительные алгоритмы для исправления независимых ошибок в циклических кодах,» в Системи обробки інформації: зб. наук. пр. Харків, Україна: ХУПС, вип. 3(84), с. 80-89, 2010.
В. П. Семеренко, «Декодирование кодов Рида-Соломона на основе графовой и автоматной моделей,» Электронное моделирование, № 1, с. 57-72, 2011.

Most read articles by the same author(s)