Материал: Лекция 6

увеличивается, стремясь к пределу, равному 1.

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

Минимальное кодовое расстояние

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

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

Количество разрядов (символов), которыми отличаются две кодовые комби­нации, принято за кодовое расстояние между ними. Для определения этого расстояния нужно сложить две кодовые комбинации по модулю 2 и подсчитать число единиц в полученной сумме. Например, две кодовые комбинации и имеют расстояние , так как

(5.11)

Заметим, что кодовое расстояние между комбинацией и нулевой называют весом комбинации , т. е. вес равен числу «1» в ней.

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

Минимальное кодовое расстояние некоторого кода определяется как минимальное расстояние Хэмминга между любыми разрешенными кодовыми словами этого кода.

Пример. Даны разрешенные комбинации

Определить минимальное кодовое расстояние.

Определяем кодовое расстояние между и

Определяем кодовое расстояние между и

Определяем кодовое расстояние между и

Определяем кодовое расстояние между и

Определяем кодовое расстояние между и

Определяем кодовое расстояние между и

.

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

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

Число обнаруживаемых или исправляемых ошибок

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

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

. (5.12)

Р ис. 5.6. Геометрическая модель кода

В этом случае никакая комбинация из ошибок не может перевести одну разрешенную кодовую комбинацию в другую разрешенную. Таким образом, ус­ловие обнаружения всех ошибок кратностью можно записать в виде:

. (5.13)

Чтобы можно было исправить все ошибки кратностью и менее, необхо­димо иметь минимальное расстояние, удовлетворяющее условию:

. (5.14)

В соответствии с этим условие исправления всех ошибок кратностью не более можно записать в виде:

(5.15)

Из (5.13) и (5.15) следует, что если код исправляет все ошибки кратностью , то число ошибок, которые он может обнаружить, равно .

Аналогично можно показать, что для одновременного исправления ошибок кратности t_u и обнаружения ошибок кратности t_о кодовое расстояние должно быть равно:

.

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

Из этих выражений видно, что .

Корректирующие возможности кодов

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

Так, граница Плоткина определяет верхнюю границу кодового расстояния при заданном числе разрядов в кодовой комбинации и числе информацион­ных разрядов т для двоичных кодов:

(5.16)

или

, при . (5.17)

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

, (5.18)

где — число сочетаний из по элементов, которое рассчитывается согласно выражения

.

Отсюда можно получить выражение для оценки числа проверочных символов:

. (5.19)

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

. (5.20)

Отметим, что для некоторых частных случаев Хэмминг получил простые со­отношения, позволяющие определить необходимое число проверочных символов:

для ,

для ,

Блочные коды с и в литературе обычно называют кодами Хэмминга.

Все приведенные выше оценки дают представление о верхней границе чис­ла при фиксированных значениях и или определяют минимальное число проверочных символов : при заданных и .