Граничные соотношения между параметрами помехоустойчивых кодов

Классификация корректирующих кодов

Корректирующими называются коды, позволяющие обнаружить и исправить ошибки в кодовых комбинациях. Они делятся на две группы: 1) коды с обнаружением ошибок; 2) коды с обнаружением и исправлением ошибок.

1) Особенность кодов с обнаружением ошибок состоит в том, что кодовые комбинации, входящие в их состав, отличаются друг от друга не менее, чем на d=2. Их можно условно разделить на две группы:

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

Код с постоянным числом единиц и нулей в комбинациях (код с постоянным весом).

(10.2)

где l – число единиц в слове длиной n.

Распределительный код Это также разновидность кода с постоянным весом, равным единице. В любой кодовой комбинации содержится только одна единица. Число кодовых комбинаций в распределительном коде

(10.3)

Кодовые комбинации при n=6 можно записать в виде 000001,000010,000100,001000,010000,100000. Сложение по модулю 2 двух комбинаций показывает, что они отличаются друг от друга на кодовое расстояние d=2.

Т а б л и ц а 10.1 - Код с постоянным числом единиц и нулей

Код	Код
11000 10010 01010 00011 01100 01001 00101 10001 00110 10100

б) коды, в которых используются все комбинации но к каждой из них по определенному правилу добавляются контрольные символы m - символы.

Код с проверкой на четность. Такой код образуется путем добавления к передаваемой комбинации, состоящей из к информационных символов неизбыточного кода, одного контрольного символов m (0 или 1), так, чтобы общее число единиц в передаваемой комбинации было четным. В общем случае

Т а б л и ц а 10.2 - Код с проверкой на четность

Информационные символы к	Контрольные символы m	Полная кодовая комбинация n=k+m

Общее число комбинаций N=2^n-1

Код с числом единиц, кратным трем. Этот код образуется добавлением к к информационным символам двух дополнительных контрольных символов (m=2), имеющих такие значения, чтобы сумма единиц, посылаемых в линию кодовых комбинаций, была кратной трем

Т а б л и ц а 10.3

Информационные символы к	Контрольные символы m	Полная кодовая комбинация

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

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

Существуют граничные оценки, связывающие d₀, n и k.

Граница Хэмминга, которая близка к оптимальной для высокоскоростных кодов, определяется соотношениями:

для q-ного кода
для двоичного кода

Граница Плоткина, которую целесообразно использовать для низкоскоростных кодов определяется соотношениями:

для q-ного кода
для двоичного кода

Границы Хэмминга и Плоткина являются верхними границами для кодового расстояния при заданных n и k, задающими минимальную избыточность, при которой существует помехоустойчивый код, имеющий минимальное кодовое расстояние и гарантийно исправляющий t_u - кратные ошибки.

Граница Варшамова-Гильберта (нижняя граница), определяемая соотношениями:

и

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

Дата добавления: 2014-10-22