Кодирование информации с использованием математического аппарата умножения и деления полиномов

Проблема сохранения целостности передаваемой и обрабатываемой информации всегда актуальна в связи с растущим объемом передаваемой и принимаемой информации. При передаче данных по каналам связи существует вероятность появления ошибок. Причины могут быть самыми разными, но результатом является искажение данных и невозможность их использования для дальнейшей обработки.

Вероятность искажения бита в потоке передаваемой информации на уровне физического канала находится в пределах 10-2 K 10-6. В тоже время со стороны пользователей и многих прикладных процессов часто выдвигается требование к вероятности ошибок в принимаемых данных не хуже 10-6 K 10-12.

Борьба с возникающими ошибками ведется на разных уровнях семиуровневой модели OSI (в основном на физическом, канальном, сетевом и транспортном уровнях. Разработаны специальные способы кодирования информации, позволяющие обнаружить и исправить возможные ошибки. Известно много способов защиты информации от ошибок. Одним из путей решения данной задачи является использование специальных процедур, основанных на применении помехоустойчивых кодов. На сегодняшний день существует большое количество способов помехоустойчивого кодирования, которые активно используются в различных системах передачи данных

Помехоустойчивое кодирование состоит в целенаправленном введении избыточности для того, чтобы появилась возможность обнаруживать и/или исправлять ошибки, возникающие при передаче по каналу связи. Введение избыточности означает, что, помимо информационной последовательности, в передаваемое сообщение вводят проверочные символы.

Из всех разновидностей помехоустойчивых кодов циклические коды получили наибольшее распространение. Это обусловлено их высокими корректирующими свойствами и сравнительно простой реализацией кодирующих и декодирующих устройств, в которых они используются.

При описании свойств циклических кодов пользуются представлением кодовых комбинаций в виде многочленов от фиктивной переменной x, в которых цифры 0 и 1, составляющие кодовые комбинации, являются коэффициентами переменной.

Если число элементов кодовой комбинации равно n, то соответствующий ей многочлен F ( x ) имеет вид:

F ( x ) = c ,x" ^{— 1} + c x n - ^{— 2} + K + cx ² + cx + c n — 1 - — 2 2 10

где c i , i = 0... - — 1 - коэффициенты, принимающие значения 0 или 1.

В циклическом (n, к) - коде каждый ненулевой кодовый полином должен иметь степень в пределах от (n - к) до (n -1).

Это определяется структурой циклических кодов, у которых первый информационный символ располагается всегда левее проверочных символов, а последний располагается в ( n - 1) позиции. Минимальный ненулевой кодовый полином будет иметь степень x^{n - к} .

Для любого циклического ( n , к ) - кода полином степени ( n - к ) является единственным и имеет следующий вид: n - 1               n - к - 1               2

g ⁽ x ) = x  + g n - к - 1 x    + K + g 2 x + g 1 x + ¹ .

В силу свойства цикличности каждый кодовый полином данного кода должен быть кратным минимальному ненулевому кодовому полиному g ( x ) , то есть должно выполняться условие:

F ( x ) = g ( x ) ‘ m ( x ) .

C другой стороны любой кодовый полином степени ( n - к ) может быть получен путем умножения полинома g ( x ) на соответствующий полином m ( x ) .

Любой циклический  (n - к)-код  полностью определяется его порождающим полиномом. В качестве образующих полиномов циклических кодов наибольшее распространение получили:

g ( x ) = x¹⁶ + x ¹⁵ + x ² + 1 ( CRC - 16)

g ( x ) = x ¹⁶ + x ¹² + x ⁵ + 1  ( CRC - CCITT )

g ( x ) = x ¹² + x ¹¹ + x ³ + x ² + x + 1  ( CRC - 12)

g ( x ) = x ³² + x²⁶ + x ²³ + x ¹⁶ + x ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1  ( CRC - 32)

Все CRC алгоритмы основаны на полиномиальных вычислениях, и для любого алгоритма CRC можно указать, какой полином он использует.

Рассмотрим три способа кодирования циклических кодов. Наиболее просто кодограммы циклического кода можно получить путем умножения многочлена,     соответствующего     исходной     последовательности информационных символов, на образующий полином

F ( x ) = m ( x ) • g ( x )

Недостатком этого способа является то, что он приводит к неразделимому коду, в котором информационные и проверочные символы не занимают постоянных мест в кодограмме.

Второй метод образования кодограмм циклического кода заключается в умножении многочлена, соответствующего исходной последовательности информационных символов, на одночлен, соответствующий старшей степени образующего полинома, и добавлении к результату умножения остатка от деления этого произведения на образующий полином

F ( x ) = x " - k • m ( x ) + r ( x )

Любой символ циклического кода является взвешенной суммой k других символов кода.

Третий способ кодирования основан на том, что циклический код является систематическим (линейным) и его проверочные и информационные символы связаны линейными соотношениями.

Представив комбинацию циклического кода в виде

F ( x ) = c ,х" ^{— 1} + c x " ^{— 2} + K + cx ² + cx + c n — 1       " — 2          2     10

где (cn_PK ,cn_k) -информационные элементы, (cn_k_„K,c,c0) -проверочные элементы, можно сказать, что j-й проверочный символ определяется соотношением к—1

C

" — k — j

= T c ,   • h

" — к — j    i i=0

где h - коэффициенты проверочного многочлена.

H ( x ) = ( x " + 1 ) / g ( x ) = hx^k + K + hx + h .

Таким образом, любой символ циклического кода является взвешенной суммой к других символов кода (суммирование выполняется по модулю 2).

Основной метод декодирования циклических кодов основан на свойствах делимости  многочленов,  описывающих кодограммы,  на образующий многочлен. Декодирующее устройство осуществляет деление принятой кодограммы на образующий многочлен. Если остаток от деления нулевой, то это указывает на отсутствие ошибки. Если остаток имеет хотя бы один ненулевой коэффициент, то в принятой кодограмме имеют место ошибки. Исправление ошибок осуществляется путем анализа полученного остатка либо на основании проверки выполнения соотношений.

Кодирование и декодирование циклических кодов предусматривает наличие схем, осуществляющих умножение и деление многочленов. Достоверность полученных результатов подтверждается при сопоставлении теоретических данных с результатами имитационного моделирования, полученными при помощи разработанного программного модуля. Построена имитационная модель адаптивной системы передачи данных, обеспечивающей контроль состояния канала в процессе передачи данных и возможность выбора оптимального варианта циклического кода из заданного ряда кодов, что позволяет повысить эффективность циклических кодов при передаче данных. Выявлены дополнительные возможности циклических кодов по коррекции ошибок и оценке качества каналов передачи данных. Программное обеспечение, необходимое для решения поставленных задач реализовано в среде MS Visual C++ 6.0.