Автоматні представлення циклічних кодів

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.