Кодер и декодер кода Хэмминга на VB. NET
Коды Хемминга позволяют закодировать исходное сообщение таким образом, чтобы после передачи его по зашумлённым каналам связи (например, по радиоканалу) и искажениям в принятой информации, можно было восстановить исходное сообщение.
1 Что такое код Хэмминга
Код Хэмминга добавляет к сообщению (информационные разряды) некоторое количество избыточной информации (проверочные разряды), сформированной определённым образом. Сообщение с добавленной проверочной информацией называется «кодовый символ» или «кодовое слово». Параметры кода указываются, например, так: (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)
Легко убедиться, что если мы внесём битовую ошибку при декодировании, то декодер восстановит исходное закодированное число.
Данный исходный код написан на С++, но переписать его на другой язык могу быстро.
Актуальность алгоритма кода Хемминга
В настоящее время актуальность подобных алгоритмов только увеличивается.
Пусть давно нет перфокарт, но зато передача данных сейчас происходит по многим каналам различной надежности, и, следовательно, вероятность ошибок при передаче также возрастает.
Из теории известно, что коды Хемминга позволяют исправлять одинарные ошибки и фиксировать двойные Таким образом, проведя статистические исследования (задавшись надежностью, как параметром) для определенного канала передачи данных, всегда можно определить оптимальную длину пакета (или слова) кодограммы.
Смысл алгоритма кодирования по Хеммингу
Смысл алгоритма кодирования и декодирования по Хеммингу представляется так:
Исходный текст, который необходимо передать по ненадежному каналу, рубится на куски определенной одинаковой длины (пакеты) и в конец каждого такого пакета помещается избыточная информация (контрольные биты).
Принятую кодограмму, алгоритм декодирования, также анализирует по пакетам Проверяется четность пакета в целом и четность каждой из групп
В этом случае, группой называется комбинация информационных бит (различной длины), причем, обязательно дополненная одним контрольным битом, который как раз и должен обеспечивать четность всей группы.
Программа, демонстрирующая самокорректирующие возможности
Внимание. При возникновении тройной и более ошибки в пакете, результат декодирования бывает непредсказуемым Поэтому для исключения такого исхода, укорачивая пакет (т. е. выбирая его длину) всегда можно достичь необходимой надежности даже для не очень надежных каналов передачи данных.
В настоящей программе, демонстрирующей кодирование и декодирование любого файла (или любого текста введенного в верхнее окно) пользователь может:
Рис.1 Программа, демонстрирующая самокорректирующие возможности
В данном проекте используется тип wchar_t, т. е. битовые значения так называемых «широких символов» хранится в двух байтах, и, следовательно, в каждый пакет попадают по четыре символа
Рис.2 Результат исправления умышленно внесенных ошибок
Матрица для схемы (64, 7)
Весь код достаточно длинен и сложен, поэтому здесь приведу только основные константы и матрицу:
const char m=64; //бит в исходном пакете
const char k=7; //контрольных бит
const char n=m+k+1; //бит в закодированном пакете (72)
unsigned char lenc; //9 байт в закодированном пакете переменная модуля
Каждая строка этой матрицы соответствует порядковому номеру бита в пакете Поэтому для кодирования достаточно перемножить вектор-строку исходных бит (длиною 64) на 64 строки данной матрицы На выходе получится вектор-строка из 8 бит (это и есть контрольный байт), который следует прибавить в конец т. е. девятым байтом и длина закодированного пакета станет 72 бита Конечно, есть некоторые тонкости, которые прописаны в коде и благодаря которым, алгоритм работает достаточно стабильно.
При декодировании 72-битная строка перемножается на ту же матрицу и результатом будет являться байт синдромов, анализ битов которого и дает однозначный ответ о наличии ошибок и возможности коррекции
Удачного Вам тестирования!
Работа с файлами
А этот вариант программы читает информацию из файла (*.txt), кодирует по алгоритму Хемминга и сохраняет в новый файл (*.cdh). Это чтобы самые «недоверчивые» могли вносить умышленные ошибки в файл кода…
Кнопка «Сохранить файл-код» создаст Вам правильный файл, усиленный избыточной информацией. Кодировка ASCII. Можете ломать…
Только помните, что если Вы внесете изменения более чем в 2 бита на пакет, (а для этого достаточно грубо изменить один символ) то, получите непредсказуемый «результат».
Для наглядности, я (аккуратно) внес единичную ошибку в копию файла testEnglish. cdh и назвал эту поврежденную копию testEnglish_err1.cdh; (символ t заменил на символ u). Файл с двойной ошибкой testEnglish_err2.cdh тоже присутствует в прикрепленном наборе (символ Y заменил на символ X). Программа Lister позволяет эти повреждения видеть…
Рис.3 Работа с файлами
Сначала воспользуйтесь кнопкой «Загрузить файл-код», а затем по кнопке «Проверить и исправить» убедиться в востановлении искаженной информации (самокоррекции) или фиксации обнаруженной ошибки.
