Automaton Presentations of Cyclic Codes
Keywords:
automaton, cyclic codes, linear finite-state machines, encoder, decoderAbstract
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.
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.
Downloads
-
PDF (Українська)
Downloads: 190
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
