АВТОМАТНІ ПРЕДСТАВЛЕННЯ ЦИКЛІЧНИХ КОДІВ

  • В. П. Семеренко Вінницький національний технічний університет
Ключові слова: автомат, циклічні коди, лінійний автомат, лінійна послідовнісна схема, кодер, декодер

Анотація

Відомі способи представлення циклічних кодів (поліноміальний, матричний та алгебраїчний) придатні для всіх класів лінійних блокових завадостійких кодів, але вони не враховують особливостей конкретних класів кодів. Наприклад, властивість циклічності таких кодів містить в собі великі потенціальні можливості, яка майже не використовуються у зазначених способах представлення кодів.

Пропонуються автоматні представлення циклічних кодів з використанням скінченних автоматів в полях Галуа — лінійних послідовнісних схем (ЛПС). Цей тип скінченних автоматів належить до систем, процеси в яких розвиваються циклічно в часі, тобто до динамічних систем. Розглядаються дві автоматні моделі циклічних кодів: автоматно-аналітична і автоматно-графова. Наведено означення циклічних кодів на основі цих автоматних моделей. Показано взаємозв’язок автоматного представлення з відомими представленнями циклічних кодів.

Проведено класифікацію ЛПС з позицій автоматного представлення циклічних кодів. Вперше для класифікації враховується дві характеристичні матриці ЛПС, що дає можливість розрізняти чотири базових типи ЛПС: рекурсивні та нерекурсивні ЛПС типів Галуа та Фібоначчі. Для врахування напряму переміщення даних можна розрізняти лівосторонні та правосторонні ЛПС, тобто вісім типів ЛПС.

Проведено дослідження процедур систематичного кодування та декодування циклічних кодів на основі їх автоматно-аналітичних моделей. Показано, що всі типи ЛПС дають однаковий результат при кодуванні та декодуванні, але з різною трудомісткістю. Теоретично обґрунтовано апаратну реалізацію для кожного типу ЛПС. Наведені критерії вибору типу ЛПС відносно фізичного часу та програмно-апаратних витрат.

Основна перевага методів кодування та декодування циклічних кодів  на основі запропонованих математичних моделей — лінійна складність обчислень і проста програмно-апаратна реалізація.

Біографія автора

В. П. Семеренко, Вінницький національний технічний університет

канд. техн. наук, доцент, доцент кафедри обчислювальної техніки

Посилання

Р. Морелос-Сарагоса, Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Москва, Россия: Техносфера, 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.

Опубліковано
2018-04-27
Як цитувати
[1]
В. Семеренко, АВТОМАТНІ ПРЕДСТАВЛЕННЯ ЦИКЛІЧНИХ КОДІВ, Вісник Вінницького політехнічного інституту, № 2, с. 89-100, Квіт 2018.
Номер
Розділ
Інформаційні технології та комп'ютерна техніка

Найчитабильні статті цього ж автора(ів)