Похожие презентации:
Код Хэмминга
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.