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

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

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

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

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

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

.

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

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

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

Второй тип кодов основаны на предложение Р. Хемминга 1948 г., определившим алгоритм устранения одиночных ошибок.

Минимальная избыточность кода, исправляющего одиночную ошибку определяется в соответствии с . Для восстановления информационного содержания сообщения, очевидно, следует дополнительно передать количество информации не менее величины ее потерь, т. е. вместо передачи каждого 1 бит информации следует передавать бит. В этом случае избыточность сообщения составит:

.

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

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

Рис. 28 Пример кода Хемминга для 8-битного сообщения

Номера контролируемых битов для каждого проверочного приведены в табл. 12. Они определяются по следующиму принципу: для любого номера проверочного бита (), начиная с него, бит подряд оказываются проверяемыми, затем — группа непроверяемых бит и т. д.

Табл. 12 Номера контролируемых битов проверочными

Алгоритм кодирования информации с помощью кода Хемминга состоит из 4-х шагов:

1. Добавление проверочных битов (в позициях всех степеней числа 2) к передаваемым данным и их нумерация слева направо, начиная с 1.

2. Выбор в качестве определяемого бита бит с номером .

3. Присваивание определяемому проверочному биту сумму по модулю 2 контролируемых им битов, кроме себя самого.

4. Уменьшение на 1.

5. Выполнение шагов 2–4 до тех пор, пока .

! Пример: Закодировать по коду Хемминга сообщение 01101101.
1. 01101101 → _ _ 0 _ 1 1 0 _ 1 1 0 1.
2. _ _ 0 _ 1 1 0 _ 1 1 0 1 → _ _ 0 _ 1 1 0 € 1101 →
→ _ _ 0 _ 1 1 0 1 1 1 0 1, т. к. .
3. _ _ 0 _ 1 1 0 1 1 1 0 1 → _ _ 0 € 110 1 1 1 0 1 →
→ _ _ 0 1 1 1 0 1 1 1 0 1, т. к. .
4. _ _ 0 1 1 1 0 1 1 1 0 1 → _ € 0 1 1 10 1 1 10 1 →
→ _ 0 0 1 1 1 0 1 1 1 0 1, т. к. .
5. _ 0 0 1 1 1 0 1 1 1 0 1 → € 0 0 1 1 1 0 1 1 1 0 1 →
→ 0 0 0 1 1 1 0 1 1 1 0 1, т. к. .
Сообщение 01101101 кодом Хемминга будет закодировано как 000111011101.

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

Табл. 13 Избыточность кодов Хемминга для различных длин сообщений

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

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

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

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

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

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

Алгоритм проверки и исправления передаваемой последовательности бит в представлении Хемминга представляет собой простой набор операций:

1. Производится проверка всех битов четности.

2. Если все биты четности верны, то осуществляетсяпереход к п. 5.

3. Вычисление суммы номеров всех неправильных битов четности.

4. Инвертация содержимого бита, номер которого равен сумме, найденной в п. 3.

5. Исключение битов четности, передача правильного информационного кода.

! Пример: Дешифровать код Хемминга для сообщения 000101011101.
1. Первый бит четности неверен, т. к. .
Второй бит четности верен, т. к. .
Четвертый бит четности неверен, т. к. .
Восьмой бит четности верен, т. к. .
2. В сообщении 000101011101 содержится ошибка на которую указывают первый
и четвертый биты четности.
3. Сумма номеров неправильных битов четности .
4. 0 0 0 1 0 1 0 1 1 1 0 1 → 0 0 0 1 1 1 0 1 1 1 0 1.
5. 00 0 1 1 1 0 1 1 1 0 1 → 0 1 1 0 1 1 0 1.
Сообщение 000101011101 кода Хемминга дешифровано как 01101101.