Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Самокорректирующиеся коды. Код Хэмминга




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

Метод, позволяющий определить место появления ошибочного знака и исправить его, был предложен в 1948 году Р.Хэммингом. Построенные с использованием этого метода коды получили название - коды Хэмминга.

В основу метода положено добавление к информационным битам добавочных битов проверки четности суммы знаков двоичной кодовой комбинации. Проверочные знаки расположены в разрядах, номера которых равны степеням числа 2: 1=20, 2=21, 4=22, 8=23, ….
В остальных разрядах кодовой комбинации размещаются информационные знаки. Для любого проверочного знака с номером k, начиная с него, k бит подряд являются проверяемыми, далее k бит подряд непроверяемыми, затем k бит подряд проверяемыми, и так далее. Для разряда с номером 1 проверяемыми являются разряды 1, 3, 5, 7, и так далее. Для разряда с номером 2 проверяемыми являются разряды 2, 3, 6, 7, 10, 11, … Для разряда 4 проверяемыми являются разряды 4, 5, 6, 7, 12,13,14,15, … Значение 0 или 1 вносится в разряд проверочного знака (с номером 1, 2, 4,..) так, чтобы сумма всех проверяемых разрядов была четным числом.

 

№ проверочных знаков 20 21   22       23        
№ разряда                        
Кодовая комбинация                        

 

проверочный разряд 1                        
проверочный разряд 2                        
проверочный разряд 4                        
проверочный разряд 8                        
                         

Алгоритм проверки полученной кодовой комбинации и устранения ошибки в ней состоит в следующем:

· Производится проверка всех разрядов четности,

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

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

Пример. В отличие от выше приведенной переданной кодовой комбинации, в 5-ом разряде ошибочно принят знак 0. В связи с этим получены нечетные суммы проверочных разрядов 1 и 4, сумма которых равна 5.

 

№ разряда                        
Кодовая комбинация                        
проверочный разряд 1                        
проверочный разряд 2                        
проверочный разряд 4                        
проверочный разряд 8                        

 

Пример.

Пусть Х= 101100. Из условия p = 4. Обозначим эти разряды y4y3y2y1.

Номер разряда в 10-ном представлении Номер разряда в 2-ном представлении обозна-чение разряда значе-ние разряда s4 s3 s2 s1 кодовая комби-нация
    X1            
  1 0 X2            
  1 1 X3            
  1 0 0 X4            
  1 0 1 X5            
  1 1 0 X6            
  1 1 1 Y1     Y1 Y1 Y1  
  1 0 0 0 Y2   Y2        
  1 0 0 1 Y3   Y3     Y3  
  1 0 1 0 Y4   Y4   Y4    
  s4s3s2s1              
  0 0 0 0              
  0 0 0 1              

 

Запишем номера разрядов в двоичном представлении, как показано в таблице. Имеем 4 столбца номеров Åразрядов. В контрольные суммы si будем суммировать по модулю 2 значения разрядов имеющих на i –ом месте 1. Тогда имеем систему уравнений:

s1 = 0Å1Å0Åy1 Åy3 = 0, y3= 1

s2 = 0Å1Å1Åy1 Åy4 = 0, y4= 0

s3 = 1Å0Å1Åy1 = 0, y1= 0

s4 = y2Åy3Åy4 = 0. y2= 1

Отсюда y1=0, y2=1, y3=1, y4=0.

Если в последнем разряде возник ошибочный бит, вместо 0 будет 1, то в контрольном коде получим значение 0001, что указывает на номер Подробная информация по теме занятия размещена в электронных учебниках (Lessons и «Медицинская информатика»)






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных