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

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

В контрольные разряды записывается некоторая информация об исходном числе. Поэтому можно говорить, что систематический код обладает избыточностью. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов 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) – количество единиц, содержащихся в кодовой комбинации.

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

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

001 011

а) d=1 d=1

101.  110

000 010 A₁ A₂ A₃

100.  110

Рис. 4.1 Геометрическое Рис. Кодовые расстояния для пози-

представление кодов ционной системы

4. Помехоустойчивость кода.

Минимальное кодовое расстояние некоторого кода определяется как минимальное расстояние Хэмминга между любыми разрешенными кодовыми словами этого кода. У безызбыточного кода минимальное кодовое расстояние d_min=1. Чем больше минимальное кодовое расстояние, тем больше избыточность кода. Максимальное кодовое расстояние кода, очевидно, равно его размеру, т.е. числу двоичных разрядов в кодовом слове.

Непосредственные вычисления кодовых расстояний у рассмотренного выше кода, построенного методом контрольных сумм, дают следующие значения показателей: d_min=3 и d_max=7.

Очевидно, что -кратная ошибка приводит к тому, что искаженная кодовая комбинация отодвигается от исходной на расстояние . В то же время ошибка не может быть обнаружена, если она переводит одну разрешенную кодовую комбинацию в другую, тоже разрешенную. Следовательно, способность кода обнаруживать все ошибки некоторой кратности зависит от минимального расстояния между разрешенными кодовыми словами: чем больше минимальное кодовое расстояние, тем большей кратности требуется ошибка для перевода любой разрешенной кодовой комбинации в другую разрешенную. Код с минимальным кодовым расстоянием d_min способен обнаруживать любые ошибки кратностью

У рассмотренного выше кода d_min=3, следовательно, он может обнаруживать любые однократные и двукратные ошибки.

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

У рассмотренного выше кода, построенного методом контрольных сумм, d_min=3, следовательно, он может исправлять только любые однократные ошибки.

Рассмотрим n-разрядный код, основанный на n-кратном повторении каждого передаваемого символа. У него d_min= n. Следовательно, максимальная кратность обнаруживаемых ошибок равна n-1, что соответствует случаю искажения всех символов, кроме одного. Максимальная кратность исправляемых ошибок равна (n-1)/2, что соответствует искажению «почти» половины всех символов. Это соответствует фиксации ошибки при обнаружении хотя бы одного неодинакового символа и исправлению ошибки на основе определения, каких значений больше.

Рассмотрим n-разрядный код, основанный на введении одного разряда контроля четности. У него d_min= 2, и, следовательно, максимальная кратность обнаруживаемых ошибок равна 1, а исправляемых – 0 (код не способен исправлять ошибки).