23.2.2. КОД ХЕММИНГА

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

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

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

Способ обнаружения ошибок с помощью контрольных разрядов поясним на примере -разрядного числа. Для того чтобы обеспечить защиту комбинации в 16 бит, необходимо, как следует из табл. 23.1, пять контрольных разрядов; следовательно, общая длина слова составляет 21 бит.

Таблица 23.1 (см. скан) Минимально-необходимое число контрольных разрядов для обнаружения и коррекции единичной ошибки в зависимости от длины информационного слова

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

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

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

Варианты подсоеденения на приемной стороне приведены в табл. 23.3 Для одноразрядного способа проверки на четность получаем

При этом определяется для переданного информационного кода по той же схеме, что и для передатчика, и сравнивается с переданным Соответствующая схема представлена на рис. 23.8.

Контрольное слово декодируется в ПЗУ. Если обнаружена ошибка в информационном разряде, то на выходах появляется двоичный номер неправильного разряда и дешифратор типа «1 из 16» запускается подачей сигнала с выхода Выбранный элемент ИСКЛЮЧАЮЩЕЕ ИЛИ инвертирует нарушенный бит информации, т.е. производит коррекцию.

При обнаружении ошибки в контрольном разряде на выходе устанавливается единица. Двоичный номер неправильного контрольного разряда появляется на выходах Каждая обнаруженная ошибка вызывает появление «1» на выходе Из 32 возможных кодовых комбинаций, которые может принимать контрольное слово, в рассматриваемом случае используется 22 Остальные 10 комбинаций могут возникнуть только тогда, когда нарушено

Рис. 23.8. (см. скан) Передача данных с коррекцией единичной ошибки

(см. скан)

несколько бит информации. Такая многократная ошибка обозначается единицей на выходе Этот способ не позволяет ее скорректировать. Аппаратурные затраты на исправление таких ошибок, естественно, значительно больше [23.2.3]. Таблица истинности для реализации описанных функций может быть непосредственно получена из таблицы 23.3.

Как видно из схемы 23.8, защита данных по Хеммингу благодаря возможности параллельной работы требует сравнительно небольших аппаратурных затрат и не приводит к большой потере скорости. По этой причине такой метод часто применяется для защиты данных в памяти вычислительных систем. Особое преимущество его состоит в том, что возникающие в памяти ошибки могут быть зарегистрированы, несмотря на то что из-за коррекции они могли бы остаться незамеченными. Можно своевременно определить дефектную ИС и заменить ее. Таким образом, надежность вычислительных машин значительно повышается [23.4].