АВТОМАТНІ ПРЕДСТАВЛЕННЯ ЦИКЛІЧНИХ КОДІВ
Ключові слова:
автомат, циклічні коди, лінійний автомат, лінійна послідовнісна схема, кодер, декодерАнотація
Відомі способи представлення циклічних кодів (поліноміальний, матричний та алгебраїчний) придатні для всіх класів лінійних блокових завадостійких кодів, але вони не враховують особливостей конкретних класів кодів. Наприклад, властивість циклічності таких кодів містить в собі великі потенціальні можливості, яка майже не використовуються у зазначених способах представлення кодів.
Пропонуються автоматні представлення циклічних кодів з використанням скінченних автоматів в полях Галуа — лінійних послідовнісних схем (ЛПС). Цей тип скінченних автоматів належить до систем, процеси в яких розвиваються циклічно в часі, тобто до динамічних систем. Розглядаються дві автоматні моделі циклічних кодів: автоматно-аналітична і автоматно-графова. Наведено означення циклічних кодів на основі цих автоматних моделей. Показано взаємозв’язок автоматного представлення з відомими представленнями циклічних кодів.
Проведено класифікацію ЛПС з позицій автоматного представлення циклічних кодів. Вперше для класифікації враховується дві характеристичні матриці ЛПС, що дає можливість розрізняти чотири базових типи ЛПС: рекурсивні та нерекурсивні ЛПС типів Галуа та Фібоначчі. Для врахування напряму переміщення даних можна розрізняти лівосторонні та правосторонні ЛПС, тобто вісім типів ЛПС.
Проведено дослідження процедур систематичного кодування та декодування циклічних кодів на основі їх автоматно-аналітичних моделей. Показано, що всі типи ЛПС дають однаковий результат при кодуванні та декодуванні, але з різною трудомісткістю. Теоретично обґрунтовано апаратну реалізацію для кожного типу ЛПС. Наведені критерії вибору типу ЛПС відносно фізичного часу та програмно-апаратних витрат.
Основна перевага методів кодування та декодування циклічних кодів на основі запропонованих математичних моделей — лінійна складність обчислень і проста програмно-апаратна реалізація.
Посилання
Р. Морелос-Сарагоса, Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Москва, Россия: Техносфера, 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.
##submission.downloads##
-
PDF
Завантажень: 190
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, згодні з такими умовами:
- Автори зберігають авторське право і надають журналу право першої публікації.
- Автори можуть укладати окремі, додаткові договірні угоди з неексклюзивного поширення опублікованої журналом версії статті (наприклад, розмістити її в інститутському репозиторії або опублікувати її в книзі), з визнанням її первісної публікації в цьому журналі.
- Авторам дозволяється і рекомендується розміщувати їхню роботу в Інтернеті (наприклад, в інституційних сховищах або на їхньому сайті) до і під час процесу подачі, оскільки це сприяє продуктивним обмінам, а також швидшому і ширшому цитуванню опублікованих робіт (див. вплив відкритого доступу).
