Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ПОЛИТЕХНИЧЕСКИХ ИНСТИТУТ (ФИЛИАЛ) ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО АВТОНОМНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«СЕВЕРО-ВОСТОЧНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

ИМЕНИ М.К.АММОСОВА» В Г. МИРНОМ

ФАКУЛЬТЕТ ГУМАНИТАРНЫХ И ЕСТЕСТВЕННЫХ НАУК

КАФЕДРА ФУНДАМЕНТАЛЬНОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ

Реферат

На тему:

Коды Хэмминга

Выполнил: студент 1-го курса

гр. ПМ-15 Готовцева Е.А.

Проверил: д.ф.-м.н., проф. Усманов З.Д.

Мирный, 2015

Содержание

• Введение
• Самоконтролирующиеся коды
• Самокорректирующиеся коды
• Код Хэмминга
• Принцип построения кодов Хемминга
• Заключение
• Список литературы


Введение

Самоконтролирующиеся коды

Коды Хемминга являются самоконтролирующимся кодами, то есть коды, позволяющие автоматически обнаруживать наиболее вероятные ошибки при передаче данных Для построения их достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру такого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде, передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающий количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.

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

Самокорректирующиеся коды

Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенству или, где m - количество основных двоичных разрядов кодового слова. Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице № 1.

Таблица 1

Имея разрядов, самокорректирующийся код можно построить следующим образом. Присвоим каждому из разрядов свой номер - от 1 до; запишем эти номера в двоичной системе счисления. Поскольку, каждый номер можно представить, очевидно, k-разрядным двоичным числом.

Предположим далее, что все разрядов кода разбиты на контрольные группы, которые частично перекрываются, причем так, что единицы в двоичном представлении номера разряда указывают на его принадлежность к определенным контрольным группам. Например, разряд № 5 принадлежит к 1-й и 3-й контрольным группам, потому что в двоичном представлении его номера 5₁₀ = …000101₂. Можно видеть, что 1-й и 3-й разряды содержат единицы.

Среди разрядов кода при этом имеется k разрядов, каждый из которых принадлежит только к одной контрольной группе:

Разряд № 1: 1₁₀ = …000001₂ принадлежит только к 1-й контрольной группе.

Разряд № 2: 2₁₀ = …000010₂ принадлежит только к 2-й контрольной группе.

Разряд № 4: 4₁₀ = …000100₂ принадлежит только к 3-й контрольной группе.

Разряд № 2^{k ? 1} принадлежит только к k-й контрольной группе.

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

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

Например, довольно распространен код Хемминга с m=7 и k=4.

Пусть исходное слово (кодовое слово без контрольных разрядов) - 0110101₂.

Обозначим - контрольный разряд №i; а - информационый разряд №i, где i = 1,2,3,4…

Таблица 2

Интересно посмотреть, как перекрываются контрольные группы в данном случае (Рис №1). Первая группа контролирует разряды № 3,7,5 исходного кода, вторая -- 3,7,6… (№ группы = № контрольного разряда). Очевидно, что они частично перекрываются.

Рис.№1. Первая группа контролирует разряды № 3,7,5 исходного кода, вторая -- 3,7,6…. Очевидно, что они частично перекрываются

Предположим теперь, для примера, что при передаче данного кодового слова 10001100101 произошла ошибка в 11-м разряде, так, что было принято новое кодовое слово 10001100100. Произведя в принятом коде проверку четности внутри контрольных групп, мы обнаружили бы, что количество единиц нечетно в 1-й,2-й и 4-й контрольных группах, и четно в 3-й контрольной группе. Это указывает, во-первых, на наличие ошибки, во-вторых, означает, что номер ошибочно принятого разряда в двоичном представлении содержит единицы на первом, втором и четвертом местах и нуль - на третьем месте, так как ошибка только одна, и 3-я контрольная сумма оказалась верной.

Таблица 3

Из таблицы следует, что ошибка произошла в 11-м разряде и её можно исправить. Построенный код, разумеется, не рассчитан на возможность одновременной ошибки в двух разрядах.

Например (Рис №2), когда ошибки одновременно прошли в 3-м и 7-м разрядах исходного кода, первый и второй контрольные биты даже не замечают подмены.

Рис.№2 Когда ошибки прошли в 3-м и 7-м разрядах исходного кода, первый и второй контрольные биты даже не замечают ошибки

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

Например, предположим теперь, что при передаче данного кодового слова 10001100101 произошли ошибки в 3-м и 6-м разрядах, так, что принято кодовое слово 10101000101.

Таблица 4

Вывод: ошибка произошла в 5-м разряде Истинное кодовое слово: 1 0 0 0 1 1 0 0 1 0 1 Ошибочное кодовое слово: 1 0 1 0 1 0 0 0 1 0 1 Исправленное кодовое слово: 1 0 1 0 0 0 0 0 1 0 1 Результат получается еще более отдаленным от правильного, чем принятый код. Исправление кода по общему правилу не только не улучшило, но даже ухудшило бы дело.

Код Хэмминга

Заключение

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

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

Список литературы

1. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 600 c.

2. Кларк Д., Кейн Д. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. М.: Радио и Связь,1987, 300 с.

3. http://wreferat.baza-referat.ru

4. http://referatwork.ru/category/svyaz/view/422783_kody_hemminga

Размещено на Allbest.ru