Обеспечение надежности передачи данных

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

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

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

При помехоустойчивом кодировании сообщения для канала связи могут ставиться две задачи:

• кодирование обеспечивает только установление факта искажения информации - в этом случае исправление произво­дится путем ее повторной передачи;

• кодирование позволяет локализовать и автоматически исправить ошибку передачи.

Общим условием является использование только равномер­ных кодов.

Надежность передачи при кодировании помехоустойчивым кодом обеспечивается тем, что вместе с разрядами сообщения Кс передается Кк контрольных разрядов.

Избыточность сооб­щения для реального канала L характеризуется относительной величиной:

L = (Кс + Кк)/Кс = 1 + (Кк/Кс).

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

1. Коды, обнаруживающие ошибку

Пусть имеется цепочка информационных бит длиной Кс. Добавим к ним один контрольный бит Кк, значение которого определяется тем, что новая кодо­вая цепочка из (Кс + 1) бит должна содержать четное количество единиц - по этой причине такой контрольный бит называется би­том четности. Например, для информационного байта 01010100 бит четности будет иметь значение 1, а для байта 11011011 бит четности равен 0.

Избыточность сообщения L = 1 + (1/Кс)

2. Коды, исправляющие одиночную ошибку

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

1) Н = -p*log₂p - (1 - p) *log₂(1 - р) – неопределенность передачи одного бита сообщения; где р - вероятность появления ошибки в сообщении. Для восста­новления информационного содержания сообщения, очевидно, следует дополнительно передать количество информации не ме­нее величины ее потерь, т.е. вместо передачи каждого 1 бит информации следует передавать (1 + Н) бит. В этом случае избыточность сообщения составит

Lmin =(1 +H)/1 = 1 – p* log₂p - (1 - p) *log₂(1 - р)

В 1948 г. Р. Хемминг предложил код, устраняющий одиночные ошибки. Основная идея состоит в добавлении к информационным битам нескольких битов четности, каждый из которых контролирует опре­деленные информационные биты. Если пронумеровать все пере­даваемые биты, начиная с 1 слева направо (стоит напомнить, что информационные биты нумеруются с 0 и справа налево), то кон­трольными (проверочными) оказываются биты, номера которых равны степеням числа 2, а все остальные являются информаци­онными. Например, для 8-битного информационного кода кон­трольными окажутся биты с номерами 1, 2, 4 и 8:

Номера кода Хеминга

1 2 3 4 5 6 7 8 9 10 11 12

11 10 9 8 7 6 5 4 3 2 1 0

Номера информационных битов

Контрольные разряды

Номера контролируемых битов для каждого проверочного приве­дены в таблице.

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

Легко усматривается принцип выделения контролируемых би­тов в таблице: для любого номера проверочного бита (n), начиная с него, п бит подряд оказываются проверяемыми, затем - группа n непроверяемых бит; далее происходит чередование групп.

При построении кода начинают со старшего проверочного разряда кода сообщения.

Пример. Закодировать по коду Хемминга сообщение 01101101.

1 шаг – формируется значение 8-го старшего для данного кода значение контрольного разряда _ _ 0_110ÿ1101. Значение 8 разряда будет 1, т.к. в исходном коде значение 8 – 11 разрядов при сложении по модулю два дают 1.

2 шаг – формирование 4-го контрольного разряда по исходному коду011011101. Оно будет равно 1. Код станет 0111011101.

3 шаг – определение значение второго контрольного разряда. Оно будет равно 0.

4 шаг – значение первого контрольного разряда равно 0. Значение передаваемого кода будет 000111011101.

Пусть вместо указанной выше последовательности 000111011101 на приемном конце принята последовательность, у которой в пятом разряде вместо 1 принят 0.

При проверке анализируются проверочные разряды, начиная с младшего:

1 шаг – значение первого проверочного разряда 1 – не верно, что означает ошибку в одном из нечетных разрядов;

2 шаг – значение второго проверочного разряда 0 – верно, что означает отсутствие ошибки в 3, 7 и 11 разрядах кода (остаются 5 и 9разряды);

3 шаг – значение четвертого проверочного разряда 1 - не верно, что означает отсутствие ошибки в 9 разряде и наличие ошибки в 5 разряде.

Номер бита, содержащего ошибку (5), равен сумме номеров контрольных битов, указавших на ее существование (1 и 4) - это не случайное совпадение, а общее свойство кодов Хемминга.

На основании сказанного можно сформулировать простой алго­ритм проверки и исправления передаваемой последовательности бит в представлении Хемминга:

(a) произвести проверку всех битов четности;

(b) если все биты четности верны, то перейти к п.(е);

(c) вычислить сумму номеров всех неправильных битов четно­сти;

(d) инвертировать содержимое бита, номер которого равен сумме, найденной в п.(с);

(e) исключить биты четности, передать правильный информа­ционный код.

Избыточность кодов Хемминга для различных длин передавае­мых последовательностей приведена ниже:

Безусловно, данный способ кодирования требует увеличения объема памяти компьютера приблизительно на одну треть при 16-битной длине машинного слова, однако, он позволяет автомати­чески исправлять одиночные ошибки. Поэтому, оценивая время на­работки на отказ, следует исходить из вероятности появления пар­ной ошибки в одной последовательности (т.е. сбои должны произой­ти в двух битах одновременно). Расчеты показывают, что для ука­занного ранее количества ячеек в памяти объемом 1 Мбайт среднее время появления ошибки составляет более 80 лет, что, безусловно, можно считать вполне приемлемым с практической точки зрения.