Код Хэмминга

Содержание

Какое количество ошибок в кодовом слове может исправить код хемминга 7 4

Код Хэмминга добавляет к сообщению (информационные разряды) некоторое количество избыточной информации (проверочные разряды), сформированной определённым образом. Сообщение с добавленной проверочной информацией называется «кодовый символ» или «кодовое слово». Параметры кода указываются, например, так: (7, 4). Это означает, что длина кодового слова равна 7 битам, а длина сообщения – 4 бита. В зависимости от количества информационных и проверочных разрядов в кодовых словах существуют коды Хэмминга (7,4), (9,5), (11, 7), (15, 11), (31, 26), (63, 57) и т. д.

Общий вид формулы, по которой определяются виды кодов Хэмминга по соотношению числа информационных символов к проверочным: (2 x − 1, 2 x − x − 1), где x – натуральное число.

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

Из-за своей простоты, кодирование кодом Хемминга получило широкое распространение. Оно применяется, например, в беспроводной технологии WiFi, в системах хранения данных (RAID-массивах), в некоторых типах микросхем памяти, в схемотехнике и т. д.

Хорошая статья, описывающая принцип работы кода Хэмминга, есть, например, на Хабре.

2 Кодер кода Хэмминга (15, 11), написанный на VB. NET

Напишем кодировщик, который будет получать на вход 11 бит данных, кодировать их и возвращать 15 бит выходной информации. Если на вход пришло больше 11-ти бит данных, генерируется исключение. Если данных меньше 11-ти бит (например, 1 байт – 8 бит), то число дополняется нулями в старших разрядах до 11-ти бит и далее кодируется обычным образом. Возвращает кодер 16 бит (кодовое слово).

Код кодера Хэмминга (15, 11) на VB. NET (разворачивается)

Данный кодер легко переписать таким образом, чтобы он работал не с битовыми массивами типа BitArray(), а с байтами: на вход получал 11-разрядное число (от 0 до 0x7FF) и выдавал 2 закодированных байта:

3 Декодер кода Хэмминга (15, 11), написанный на VB. NET

Теперь пора поговорить о декодере. Декодер получает на вход 2 байта закодированных данных и возвращает 11 бит декодированных данных, которые распределены по двум байтам. Если в кодер были переданы 8 бит данных, то нас будет интересовать только первый байт, полученный с декодера.

Код декодера Хэмминга (15, 11) на VB. NET (разворачивается)

4 Консольная программа, кодирующая и декодирующая код Хемминга (15, 11)

Внешний вид программы кодера кода Хэмминга (15, 11)

Внешний вид программы декодера кода Хэмминга (15, 11)

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

Код Хэмминга — это самый популярный первый самокорректирующийся код.

Введение

Целью помехоустойчивой системы кодирования является обеспечение защиты информации от вероятных ошибок помех при информационных обменах и сохранении данных. Помехоустойчивая система кодирования позволяет ликвидировать возникающие при информационном обмене ошибки, а также ошибки при хранении информации. При трансляции информационных данных по каналам связи, возможно появление помех и ошибок. При этом какая-то часть информации может быть утеряна. Без применения помехоустойчивого кодирования нет возможности передачи значительных информационных объёмов, поскольку практически во всех системах трансляции информации и её сохранения всегда возможно появление ошибок.

Готовые работы на аналогичную тему

Существует следующая классификация помехоустойчивых кодов:

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

В свою очередь блочные коды подразделяются на:

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

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

Ниже приведена методика кодирования по Хэммингу:

Рисунок 1. Методика кодирования по Хэммингу. Автор24 — интернет-биржа студенческих работ

Код Хэмминга (7,4) подразумевает наличие четырёх бит на входе кодирующего устройства и семь на его выходе, то есть три бита являются проверочными. Биты с первого по четвёртый являются информационными битами, шестой и седьмой — это проверочные биты, а пятый проверочный бит является суммой по модулю два с первого по третий информационные биты. Сумма по модулю два считается вычислением бита чётности.

Декодирование кодировки Хэмминга выполняется посредством определения синдрома по выражениям: