Top-office11.ru

IT и мир ПК
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Код хэмминга для исправления одиночных ошибок

Тема 17. Коррекция одиночных ошибок. Код Хэмминга.

Задача системы исправления (коррекции) ошибок заключается в обнаружении ошибки, локализации места ошибки и автоматическом исправлении ошибки. Код Хэмминга обнаруживает и исправляет одиночные ошибки. Минимальное кодовое расстояние кода Хэмминга Dmin = 3.

В коде Хэмминга разряд слова, в котором произошла ошибка, указывается его двоичным номером в передаваемом слове. Рассчитаем количество контрольных разрядов для случая передачи данных байтами (8 разрядными словами).

Длина информационного слова m = 8 разрядов. Если k ­ это количество контрольных разрядов, то длина передаваемого слова n =m+k. Ошибка может возникать в любом разряде передаваемого слова, поэтому

Один двоичный набор необходим для указания правильной передачи данных. В результате приходим к выражению

В нашем случае m = 8, k = 4, n = 12.

Для каждого контрольного разряда будет построено уравнение контроля по четности. Таблица номеров разрядов передаваемого слова имеет вид.

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

С4 С3 С2 С1 = 0 0 0 0.

При возникновении одиночной ошибки С4 С3 С2 С1 не равно

0 0 0 0.Построим уравнения контроля, складывая по модулю 2 те разряды передаваемого слова, для которых Ci =1.

В системе уравнений (24) в качестве контрольных выбираем разряды х8 х4 х2 х1, потому что встречаются в уравнениях (24) только один раз. Сформируем уравнения для вычисления контрольных разрядов. Получим систему уравнений.

Согласно уравнениям (25) структура устройства – передатчика в коде Хэмминга имеет вид.

ШиД ­ шина данных;

РгИ ­ информационный регистр;

Рг ПС ­ регистр передаваемого слова;

ШиПС ­ шина передаваемого слова.

Устройство – передатчик работает следующим образом. По шине данных в информационный регистр РгИ принимаются значения информационного слова. Схема вычисления системы уравнений ( ** ) вычисляет значения контрольных разрядов и записывает их в разряды регистра передаваемого слова РгПС. В остальные разряды РгПС принимаются значения данных из РгИ. Таким образом ,формируется передаваемое слово и передается по шине ШиПС. При передаче слова могут возникнуть ошибки в любом разряде. Поэтому ,принятое слово может не совпадать с переданным, и все разряды проверяются с целью обнаружения и исправления ошибок.

Структура устройства – приемника имеет вид.

Рис.47

Переданное передатчиком слово в коде Хэмминга принимается в регистр принимаемого слова приемника. Одновременно оно подается на комбинационную схему вычисления корректирующего слова С4 С3 С2 С1.

Для автоматической коррекции (исправления) одиночной ошибки необходимо инвертировать значение ошибочного разряда. С выхода комбинационной схемы корректирующее слово С4 С3 С2 С1 поступает на вход дешифратора DC.

Если одиночных ошибок нет, то С4С3С2С1 = 0 0 0 0, и на нулевом выходе дешифратора DC0 появится единица, указывающая на правильную передачу. Если появляется одиночная ошибка в одном из разрядов принимаемого слова, то С4 С3 С2 С1 не равно нулю, и на одном из выходов дешифратора, отличного от DC0, появится единица.

Каждый выход Dci, кроме нулевого, подается на вход схемы сложения по модулю 2 с данными с выхода РгПС .

Если Dci = 0, то есть ошибки в i – том разряде нет, то

Если в I – том разряде возникает ошибка, то Dci = 1 и ошибка исправляется.

Корректируются только разряды данных и в информационный регистр принимается правильное слово y8 y7 y6 …у2 у1.

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

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

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 9274 — | 7852 — или читать все.

Читать еще:  Ошибка 1406 autocad

Обнаружение и исправление ошибок в коде Хэмминга

Построение кода Хэмминга

Пример: Построить макет кода Хемминга и определить значения корректирующих разрядов для кодовой комбинации k=4, X=0101.

Решение:

Согласно таблице минимальное число контрольных символов r=3, при этом n = 7. Контрольный коэффициенты будут расположены на позициях 1, 2, 4. Составим макет корректирующего кода и запишем его во вторую колонку таблицы. Пользуясь таблицей для номеров проверочных коэффициентов, определим значения коэффициентов К1 К2 и К3.

Первая проверка: сумма П1+П3+П5+П7 должна быть четной, а сумма К1+0+1+1 будет четной при К =0.

Вторая проверка: сумма П2+П3+П6+П7 должна быть четной, а сумма К2+0+0+1 будет четной при К2=1.

Третья проверка: сумма П4+П5+П6+П7 должна быть четной, а сумма К3+1+0+1 будет четной при К3=0.

Окончательное значение искомой комбинации корректирующего кода записываем в третью колонку таблицы макета кода.

Пример . Предположим, в канале связи под действием помех произошло искажение и вместо 0100101 было принято 01001(1)1.

Решение: Для обнаружения ошибки производят уже знакомые нам проверки на четность.

Первая проверка: сумма П1+П3+П5+П7 = 0+0+1+1 четна. В младший разряд номера ошибочной позиции запишем 0.

Вторая проверка: сумма П2+П3+П6+П7 = 1+0+1+1 нечетна. Во второй разряд номера ошибочной позиции запишем 1

Третья проверка: сумма П4+П5+П6+П7 = 0+1+1+1 нечетна. В третий разряд номера ошибочной позиции запишем 1. Номер ошибочной позиции 110= 6. Следовательно, символ шестой позиции следует изменить на обратный, и получим правильную кодовую комбинацию.

Код, исправляющий одиночную и обнаруживающий двойную ошибки

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

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

|следующая лекция ==>
|

Дата добавления: 2013-12-11 ; Просмотров: 3615 ; Нарушение авторских прав?

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

Дата добавления: 2014-11-28 ; просмотров: 4271 ; Нарушение авторских прав

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

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

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

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

Проверочные битыКонтролируемые биты
2 0 =1
2 1 =2
2 2 =4
2 3 =8
2 4 =16
2 5 =32
Читать еще:  18456 ошибка sql

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

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

Пусть, например, пришло следующее сообщение:

Бит 1 (контролирует 1,3,5,7,9, 11 биты. Сумма единиц в них нечетная) указывает на наличие ошибки в каком-либо бите с нечетным номером.

Бит 2 (контролирует 2,3,6,7,10,11 бит, сумма единиц в них четная) свидетельствует о том, контролируемые биты переданы верно, Что позволяет исключить ошибку в 3, 7 и 11 битах, т.е. ошибка в 5 или 9-м.

Бит 4 (контролируемые 4,5,6,7,12 биты, сумма единиц нечетная) указывает, что ошибка в 5-м бите.

Таким образом, однозначно устанавливается, что ошибочным является 5-й бит – можно исправить его значение на противоположное и, тем самым, восстановить правильную последовательность.

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

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

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

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

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

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

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

Число информационных битЧисло контрольных битИзбыточность
1,50
1,31
1,06

Из сопоставления видно, что выгоднее передавать и хранить более длинные последовательности бит.

Безусловно, данный способ кодирования требует увеличения объема памяти компьютера приблизительно на одну треть при 16-битной длине машинного слова, однако, он позволяет автоматически исправлять одиночные ошибки.

Методы коррекции ошибок широко используются в целях повышения надежности ВТ. Например, они используются в драйверах магнитных дисков большой емкости, чтобы снизить вероятность искажения хранимой информации в результате дефектов поверхности диска. Более того, главное отличие между форматом, используемым в звуковых компакт-дисках, и форматом CD-ROM, заключается именно в использовании кодов с исправлением ошибок. Функция исправления ошибок в формате CD-DA позволяет устранить только одну ошибку на два компакт диска. Однако, для компаний, поставляющих ПО, наличие ошибок в 50% поставляемыми ими компакт-дисков является совершенно недопустимым. Поэтому в формат CD-ROM включены дополнительные средства, позволяющие снизить вероятность возникновения ошибки до одной на 20 000 компакт-дисков.

[1] О – одинарный формат; Д –двойной формат

Код Хэмминга (7; 4)

Всем привет! Сегодня я хочу рассказать вам немного о коде Хэмминга (7; 4). Этот простейший код может быть с лёгкостью применён любым человеком для передачи самокорректирующихся сообщений , и сегодня я хочу вам показать как именно этот код можно легко и просто использовать.

Структурно слова кода Хэмминга состоят из двух частей. Сначала идут информационные 4 бита, затем три бита проверочных. Будем обозначать информационные биты буквами ABCD, проверочные буквами xyz.

Таким образом слово кода Хэмминга имеет следующую структуру:

Для передачи 4 бит информации нам требуется передавать кодовое слово из целых 7 бит! Последние три бита в случае, когда ошибки отсутствуют, не несут никакой новой информации, ибо они зависят от первых 4. Однако если в кодовом слове из 7 бит произошла 1 ошибка, то исходные информационные 4 бита всё равно можно будет восстановить точно! В этом и состоит главная особенность самокорректирующихся кодов.

Естественно, использование кода Хэмминга при передаче данных требует увеличенных ресурсов. Здесь есть такое важное понятие как скорость кода — отношение числа информационных бит к общему числу бит. В случае кода Хэмминга скорость равна 4/7. Т.е., к примеру, чтобы передавать информацию со скоростью 1 Мбит/сек и коррекцией ошибок с помощью кода Хэмминга вам потребуется канал с пропускной способностью минимум в 7/4=1.75 Мбит/сек.

Читать еще:  Коды ошибок приложений

Для подсчёта проверочных бит можно использовать следующие формулы:

x = A + B + C mod 2,

y = A + B + D mod 2,

z = A + C + D mod 2,

где n mod 2 означает остаток от деления числа n на 2.

К примеру, если информационный вектор есть ABCD = 1001, то кодовый вектор будет ABCDxyz = 1001 100

Вместо непонятных формул можно использовать следующую картинку:

Здесь всё очень просто. Подставляете вместо букв значения соответствующих битов и затем считаете значения x, y и z как сумму по модулю 2 тех информационных бит, которые есть в соответствующем круге.

В приведённом выше примере будет:

Куда более интересным является вопрос об исправлении ошибок. Очевидно, вывод об отсутствии ошибок приёмник может сделать просто взяв информационные биты ABCD, посчитав на их основе проверочные биты xyz и сравнить посчитанные проверочные биты с принятыми. Если есть ошибка, то часть проверочных битов не совпадёт.

Предположим что произошла ошибка в проверочном бите y и было принято слово 1001 110

В таком случае два проверочных бита сойдутся, а один нет. Этого вполне достаточно чтобы сделать вывод что нужно исправить бит y (для которого проверка не сошлась).

Предположим, что произошла ошибка в одном из информационных битов BCD — к примеру в бите B.

В таком случае не сойдутся аж два проверочных бита — x (он равен 1, а «должен» равняться 0) и y. Посмотрев на круги легко увидим что они пересекаются по битам B и A. Т.к. не сошлось две проверки, то берём бит B (расположенный на пересечении двух проверок).

Наконец, отдельно рассмотрим бит A. Если в нём ошибка, то у нас не сойдутся все три проверки:

Увидев такое безобразие сразу же делаем вывод о том, что ошибка в бите A.

Таким образом, можно легко и просто вычислять локацию ошибки и исправлять её. Замечу что если ошибок больше одной, то описанный выше алгоритм сработает неверно. К примеру, допустим что произошли ошибки в битах C и z:

Проверочные биты y и z сойдутся, а бит x нет. Алгоритм исправит бит x и всё. Это вполне естественное поведение, т.к. если вероятность ошибки p 0).

Естественно, работать с цветными кругами удобно человеку, но неудобно компьютеру. У кодов Хэмминга есть одна особенность, которая позволяет их лёгкое декодирование на компьютере. Итак, рассмотрим следующий алгоритм:

Определим числа g, b, r как сумму всех четырёх бит в кругах соответствующего цвета. Т.е.:

g = A + B + C + x mod 2,

b = A + B + D + y mod 2,

r = A + C + D + z mod 2.

Фактически каждый из этих бит можно определить как сумму соответствующего проверочного бита, вычисленного на основании принятых информационных бит, с принятым проверочным битом. Т.е. к примеру g есть сумма (A + B + C mod 2) (по этой формуле считался x на стороне передатчика) и принятого x. Аналогично b соответствует y, r соответствует z.

Если ошибок нет, то gbr = 000 (принятые проверочные биты сошлись с вычисленными на основе информационного вектора).

Если же есть 1 ошибка, то число gbr есть номер (в двоичной записи) ошибочного бита в векторе ABCxDyz.

В качестве примера рассмотрим уже знакомый нам вектор ABCDxyz = 1001 100, в котором произошла ошибка в бите x (четвёртый бит в векторе ABCxDyz). Посчитаем gbr:

gbr = 100 [2] = 4 [10]. Ошибка в 4 бите, которым и является x. Таким образом, для декодирования и исправления ошибки в кодовом слове длины 7 требуется лишь вычислить три суммы и из полученного числа несложной функцией получить местонахождение ошибки.

Ссылка на основную публикацию
Adblock
detector