Систематические коды

 

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

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

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

В контрольные разряды записывается некоторая информацияоб исходном числе. Поэтому можно говорить, что систематический код обладает избыточностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов k, а относительная избыточность – отношением k/n, где n=m+k – общее количество разрядов в кодовом слове (m – количество информационных разрядов).

Понятие корректирующей способности кода обычно связывают с возможностью с возможностью обнаружения и исправления ошибки. Количественно корректирующая способность кода определяется вероятностью обнаружения или исправления ошибки. Если имеем n- разрядный код и вероятность искажения одного символа будет P, то вероятность того, что искажены k символов, а остальные n-k символов не искажены, по теореме умножения вероятностей будет

W=P^k(1-P)^n-k.

Число кодовых комбинаций, каждая из которых содержит k искаженных элементов, равна числу сочетаний из n по k:

Тогда вероятность искажения

Так как на практике P=10^-3÷10^-4, наибольший вес в сумме вероятностей имеет вероятность искажения одного символа. Следовательно, основное внимание нужно обратить на обнаружение и исправление одиночной ошибки.

Корректирующая способность кода связана также с понятием кодового расстояния.

Кодовое расстояниеd(A,B) кодовых комбинацийА и В определяется как вес такой третьей кодовой комбинации, которая получается сложением исходных комбинаций по модулю 2.

Вес кодовой комбинацииV(A) – количество единиц, содержащихся в кодовой комбинации.

Коды можно рассматривать и как некоторые геометрические (пространственные) фигуры. Например, триаду можно представить в виде единичного куба, имеющего координаты вершин, которые отвечают двоичным символам (Рисунок 3.1) в этом случае кодовое расстояние воспринимается как сумма длин ребер между соответствующими вершинами куба (принято, что длина одного ребра равна 1). Оказывается, что любая позиционная система отличается тем свойством, что минимальное кодовое расстояние равно 1.

В теории кодирования показано, что систематический код обладает способностью обнаружить ошибки только тогда, когда минимальное кодовое расстояние для него больше или равно 2t, т.е. , где t – кратность обнаруживаемых ошибок, t=1 (в случае обнаружения одиночных ошибок t=1). Это означает, что между соседними кодовыми комбинациями должна существовать по крайней мере одна кодовая комбинация (Рисунок 3.2).

Рисунок 5.1 - Геометрическое представление кодов

 

Рисунок 5.2 - Кодовые расстояния для позиционной системы

 

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

.