Файл: Реферат по Архитектуре эвм тема " Код Хэминга" студент группы 20ИН1 Бурданов Дмитрий Проверил Преподаватель Худяков Ю. В.docx
Добавлен: 26.10.2023
Просмотров: 26
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство образования, науки
и молодежной политики Нижегородской области
Государственное бюджетное профессиональное образовательное учреждение
“Сормовский механический техникум
имени Героя Советского Союза П.А. Семенова”
РЕФЕРАТ
по Архитектуре ЭВМ
Тема: “ Код Хэминга”
Выполнил:
студент группы 20ИН1
Бурданов Дмитрий
Проверил:
Преподаватель
Худяков Ю.В.
Нижний Новгород
2022г.
ВВЕДЕНИЕ………………………………………………………………3с
1. Самоконтролирующиеся коды……………………………………….4с
2. Самокорректирующиеся коды………………………………………..5с
3. Принцип построения кодов Хэмминга……………………………….7с
ЗАКЛЮЧЕНИЕ…………………………………………………………..9с
Введение
Коды Хэмминга – наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления. Код Хэмминга используется в некоторых прикладных программах в области хранения данных, особенно в RAID 2 (избыточный массив независимых/недорогих дисков для ПЭВМ); кроме того, метод Хемминга давно применяется в памяти типа ECC и позволяет «на лету» исправлять однократные и обнаруживать двукратные ошибки. В середине 40-х годов Ричард Хемминг работал в знаменитых Лабораториях Белла на счетной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень медленной: один оборот за несколько секунд. Данные вводились в машине с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую. Хемминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто был должен перегружать свою программу из-за ненадежности перфокарт. На протяжении нескольких лет он проводил много времени над построением эффективных алгоритмов исправления ошибок. В 1950 году он опубликовал способ, который на сегодняшний день мы знаем, как код Хемминга.
-
Самоконтролирующиеся коды
Коды Хэмминга являются самоконтролирующимся кодами, то есть коды, позволяющие автоматически обнаруживать наиболее вероятные ошибки при передаче данных Для построения их достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру такого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде, передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающий количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.
При этом, разумеется, мы не получаем никаких указаний о том, в каком именно разряде произошла ошибка, и, следовательно, не имеем возможности исправить ее. Остаются незамеченными также ошибки, возникающие одновременно в двух, в четырех или вообще в четном количестве разрядов. Впрочем, двойные, а тем более четырехкратные ошибки полагаются маловероятными.
-
Самокорректирующиеся коды
Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенству или, где m – количество основных двоичных разрядов кодового слова. Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице № 1.
| | | | | | | |
| Диапазон, m | | Диапазон, m | | Диапазон, m | | |
| 1 | 2 | 2-4 | 3 | - | - | |
| 5-11 | 4 | 12-26 | 5 | 27-40 | 6 | |
Таблица 1
Имея разрядов, самокорректирующийся код можно построить следующим образом. Присвоим каждому из разрядов свой номер – от 1 до; запишем эти номера в двоичной системе счисления. Поскольку, каждый номер можно представить, очевидно, k-разрядным двоичным числом.
Предположим далее, что все разрядов кода разбиты на контрольные группы, которые частично перекрываются, причем так, что единицы в двоичном представлении номера разряда указывают на его принадлежность к определенным контрольным группам. Например, разряд № 5 принадлежит к 1-й и 3-й контрольным группам, потому что в двоичном представлении его номера 510 = …0001012. Можно видеть, что 1-й и 3-й разряды содержат единицы.
Среди разрядов кода при этом имеется k разрядов, каждый из которых принадлежит только к одной контрольной группе:
Разряд № 1: 110 = …0000012 принадлежит только к 1-й контрольной группе.
Разряд № 2: 210 = …0000102 принадлежит только к 2-й контрольной группе.
Разряд № 4: 410 = …0001002 принадлежит только к 3-й контрольной группе.
Разряд № 2k ? 1 принадлежит только к k-й контрольной группе.
Эти k разрядов мы и будем считать контрольными. Остальные m разрядов, каждый из которых принадлежит по меньшей мере к двум контрольным группам, будут информационными разрядами.
В каждом из k контрольных групп будем иметь по одному контрольному разряду. В каждый из контрольных разрядов поместим такую цифру (0 или 1), чтобы общее количество единиц в его контрольной группе было четным.
-
Принцип построения кодов Хэмминга
Построение кодов Хемминга базируется на принципе проверки на четность веса W (числа единичных символов) в информационной группе кодового блока. Поясним идею проверки на четность на примере простейшего корректирующего кода, который так и называется кодом с проверкой на четность или кодом с проверкой по паритету (равенству). В таком коде к кодовым комбинациям без избыточного первичного двоичного k-разрядного кода добавляется один дополнительный разряд (символ проверки на четность, называемый проверочным, или контрольным). Если число символов 1 исходной кодовой комбинации четное, то в дополнительном разряде формируют контрольный символ 0, а если число символов 1 нечетное, то в дополнительном разряде формируют символ 1. В результате общее число символов 1 в любой передаваемой кодовой комбинации всегда будет четным.
Таким образом, правило формирования проверочного символа сводится к следующему: r1 = i1 ? i2 ? ... ? i*k, где i - соответствующий информационный символ (0 или 1); k - общее их число а под операцией "?" здесь и далее понимается сложение по mod 2. Очевидно, что добавление дополнительного разряда увеличивает общее число возможных комбинаций вдвое по сравнению с числом
комбинаций исходного первичного кода, а условие четности разделяет все комбинации на разрешенные и неразрешенные. Код с проверкой на четность позволяет обнаруживать одиночную ошибку при приеме кодовой комбинации, так как такая ошибка нарушает условие четности, переводя разрешенную комбинацию в запрещенную. Критерием правильности принятой комбинации является равенство нулю результата S суммирования по mod 2 всех n символов кода, включая проверочный символ r1. При наличии одиночной ошибки S принимает значение 1: S = r1 ? i1 ? i2 ? ... ? i*k =? 0 - ошибки нет, = ?1 - однократная ошибка. Этот код является (k +1, k) - кодом, или (n, n-1) - кодом. Минимальное расстояние кода равно двум (d*min = 2), и, следовательно, никакие ошибки не могут быть исправлены.
Простой код с проверкой на четность может использоваться только для обнаружения (но не исправления) однократных ошибок. Увеличивая число дополнительных проверочных разрядов и формируя по определенным правилам проверочные символы r, равные 0 или1, можно усилить корректирующие свойства кода так, чтобы он позволял не только обнаруживать, но и исправлять ошибки. На этом и основано построение кодов Хемминга.
Коды Хемминга позволяют исправлять одиночную ошибку, с помощью непосредственного описания. Для каждого числа проверочных символов r = 3, 4, 5… существует классический код Хемминга с маркировкой (n, k) = (2r-1, 2r-1 - r), (3.20) т. е. (7,4), (15,11), (31,26) … При других значениях числа информационных символов k получаются так называемые усеченные (укороченные) коды Хемминга. Так, для Международного телеграфного кода МТК-2, имеющего5 информационных символов, потребуется использование корректирующего кода (9,5), являющегося усеченным от классического кода Хемминга (15,11), так как число символов в этом коде уменьшается(укорачивается) на 6.
Заключение
Предложенные Хэммингом регулярные методы построения кодов, корректирующих ошибки, имеют фундаментальное значение. Они демонстрируют инженерам практическую возможность достижения пределов, на которую указывали законы теории информации. Эти коды нашли практическое применение при создании компьютерных систем. Работа Хэмминга привела к решению проблемы более плотной упаковки для конечных полей. Он ввел в научный обиход важнейшие понятия теории кодирования. Работа Хэмминга сыграла ключевую роль в последующем развитии теории
кодирования и стимулировала обширные исследования, выполненные в последующие годы.
Коды Хэмминга позволяют не только обнаружить наличие ошибки, но и место ее нахождения и, следовательно, дают возможность ее исправить.