41. Обнаружение и исправление ошибок в двоичных комбинациях с помощью матричного кода.

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

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

Предположим, что код состоит из отдельных блоков, и в каждом блоке содержится k двоичных символов: a₁, a₂, ... , a_k.

Для работы в канале с переспросом этот код дополняется одним символом - четностью b, выражаемым через символ блока так:

При этом новый блок записывается так: a₁, a₂, ... , a_k,b.

Контроль по четности позволяет обнаружить нечетное число ошибок в блоке. Для ответа на вопрос, в каком разряде расположена ошибка, необходимо остановить передачу сообщения и сделать переспрос. Однако, обнаружить и исправить ошибку можно без операции переспроса. Дня создания кода с возможностью исправления без переспроса по каналу обрат

связи рассмотрим, например, блок с к = 12: a₁, a₂, ... , a₁₂

Расположим этот основной блок в виде матрицы:

Теперь определим четность всех строк и всех столбцов этой матрицы, приписав по ее краям символы четности b:

Считывая последовательно все строки образованной матрицы, можно получить блок с избыточностью: a1a2a3a4b1a5a6a7a8b2a9a10a11a12b3b4b5b6b7. Например, блок 101101000111 можно записать в матричной форме так:

Эту матрицу можно дополнить символами по четности. Полученный блок с избыточностью будет следующим: 10 1110 1 00101 1 1 1 100 0.

Допустим теперь, что ошибка появилась в информационном (основном) блоке a₁, a₂, ... , a₁₂. Тогда изменение одного двоичного символа на обратный приводит к нарушению четности в строке и столбце, соответствующих этому символу. По этому нарушению легко восстановить правильное значение символа. Для этого достаточно символ, находящийся на пересечении строки и столбца с нарушением четности, изменить на обратный.

Если ошибка окажется в символах контроля четности, то нарушится лишь одно условие четности. Для построения кода с исправлением двух, трех и более ошибок необходимо сделать дополнительную проверку на четность, например, по диагоналям. Вводя такую проверку на четность, можно построить самокорректирующийся код с любой надежностью.

42. Обеспечение достоверности передачи данных с помощью циклических кодов.

Циклические коды являются разновидностью систематических n- разрядных кодов с r информационными разрядами.

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

этому коду. Например, кодовая комбинация 11001001 (а₇,…, а₀) при сдвиге на один шаг влево позволяет получить кодовую

комбинацию 10010011. также принадлежащую этому коду.

Это свойство наглядно представляется, если разместить исходную комбинацию кода на ободе колеса, как показано на рис. в положение 0.

Из этого рисунка видно, что количество «спиц» в таком колесе, равное числу сдвигов комбинации на один разряд, соответствует числу разрядов в двоичной комбинации. Электронный вариант такого колеса позволяет создавать многофункциональные кодирующие устройства [11].

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

При описании циклических кодов двоичные комбинации удобно представлять в виде полиномов F(x) степени n-1 от некоторой фиктивной переменной х [4, 5, 7]. Ее степени i, i=0, .... , n-1, соответствуют разряду в комбинации:

где аi - разряды кодовой комбинации (коэффициенты), принимающие значения 0 или 1. являются элементами рассматриваемой кодовой комбинации. Рассмотренной выше кодовой комбинации 11001001 соответствует полином:

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