Пример 5.4

Пусть вместо указанной выше последовательности 000111011101 пришла следующая (в 5-м бите 1 заменилась 0):

Анализируем состояния контрольных битов в соответствии с табл. 5.1.

Бит 1 - неверно- т.е. ошибка находится в каком-либо бите с нечетным номером.

Бит 2- верно- следовательно из байтов с нечетными номерами 3, 7 и 11 верны (т.е. ошибка в 5 или 9-м).

Бит 4 - неверно- значит, ошибка может содержаться только в 5-м бите.

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

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

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

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

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

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

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

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

Из сопоставления видно, что выгоднее передавать и хранить более длинные последовательности битов. При этом, однако, избыточность не должна оказаться меньше L_min для выбранного канала связи.

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

Пример 3.1.

Пример 4.5

Введение

Графическая форма записи

Особенности устройств хранения информации

Вернуться в оглавление: Теоретические основы информатики