Код Хэмминга

1. Код Хэмминга

2.

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

3.

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

4.

• Наиболее известные из самоконтролирующихся
и самокорректирующихся кодов – коды
Хемминга, ориентированные на двоичную
систему счисления. Код используется для
повышения надежности передачи информации.
• Для построения самоконтролирующегося кода
достаточно иметь один контрольный разряд (код
с проверкой на четность). Но при этом
неизвестно, в каком именно разряде произошла
ошибка и отсутствует возможность ее
исправления. Чётное число ошибок остается
незамеченным.

5.

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

6.

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

7.

• Работа данного алгоритма, рассмотривается на
примере.
• Допустим, у нас есть сообщение «habr», которое
необходимо передать без ошибок. Для этого
сначала нужно наше сообщение закодировать
при помощи Кода Хэмминга. Нам необходимо
представить его в бинарном виде.

8.

• Определим длину информационного слова,
то есть длиной строки из нулей и единиц,
которые будем кодировать.
• Пусть длина слова будет равна 16. Разделим
исходное сообщение («habr») на блоки по 16
бит, которые будут кодироваться отдельно
друг от друга. Так как один символ занимает
в памяти 8 бит, то в одно кодируемое слово
помещается ровно два ASCII символа. Итак,
получим две бинарные строки по 16 бит:

9.

Контрольные биты вставляются в строго
определённых местах — это позиции с
номерами, равными степеням двойки.
При длине информационного слова в 16 бит
это будут позиции 1, 2, 4, 8, 16 (счёт с 1).
5 контрольных бит (выделены красным
цветом)

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

знаком «X» обозначены те биты, которые контролирует
контрольный бит, номер которого справа(бит номер 12
контролируется битами с номерами 4 и 8).
берём каждый контрольный бит и смотрим сколько среди
контролируемых им битов единиц, получаем некоторое
целое число и, если оно чётное, то ставим ноль, в
противном случае ставим единицу.

11.

• Высчитав контрольные биты для
информационного слова habr получаем
• Для бита 1 сумма=1(5 бит)+1(15 бит)+ 1(17 бит)
+ 1(19 бит)+(21 бит)=5 => в бит 1 записываем 1.
• Для бита 2 сумма=1(10 бит)+1(15 бит)+1(18 бит)
+ 1(19 бит)=4 => в бит 2 записываем 0.

12. Кодировка CP1251

13.

Кодировка CP1251