Алгоритм кода Хемминга - программа демонстрирует самокоррекцию

Самокоррекция - это исправление ошибок в пакетах данных, возникающих при передаче.

В Рунете можно подробно прочитать о том, как замучавшись исправлять ошибки от ввода данных в ЭВМ с перфокарт, Ричард Хемминг разработал алгоритм ввода в исходный текст избыточной информации (контрольных бит). По анализу расширенных пакетов текста можно было не только фиксировать (т.е. обнаруживать) ошибки, но и даже исправлять их (самокоррекция).

1. Актуальность алгоритма кода Хемминга
2. Смысл алгоритма кодирования по Хеммингу
3. Программа, демонстрирующая самокорректирующие возможности
4. Матрица для схемы (64, 7)
5. Работа с файлами

Данный исходный код написан на С++, но переписать его на другой язык могу быстро...

Актуальность алгоритма кода Хемминга

В настоящее время актуальность подобных алгоритмов только увеличивается.

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

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

Смысл алгоритма кодирования по Хеммингу

Смысл алгоритма кодирования и декодирования по Хеммингу представляется так:
Исходный текст, который необходимо передать по ненадежному каналу, рубится на куски определенной одинаковой длины (пакеты) и в конец каждого такого пакета помещается избыточная информация (контрольные биты).
Принятую кодограмму, алгоритм декодирования, также анализирует по пакетам Проверяется четность пакета в целом и четность каждой из групп
В этом случае, группой называется комбинация информационных бит (различной длины), причем, обязательно дополненная одним контрольным битом, который как раз и должен обеспечивать четность всей группы.

Вот и вся премудрость По результатам проверки четности, декодирующий алгоритм однозначно определит:

• Пакеты без ошибок
• Пакеты с одинарной ошибкой (которую автоматически исправит)
• Пакеты с двойной ошибкой (не исправит, но сообщит, что пакет с двойной ошибкой)

Программа, демонстрирующая самокорректирующие возможности

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

В настоящей программе, демонстрирующей кодирование и декодирование любого файла (или любого текста введенного в верхнее окно) пользователь может:

Рис.1        Программа, демонстрирующая самокорректирующие возможности

• Первичный текст делится на пакеты по 8 байт (или 64 бита)
• Вычисляются 7 контрольных бит и бит четности, формируя, таким образом, дополнительный контрольный байт, который и размещается после 8 исходных байт.
• Во второе окно выводятся 72-битные пакеты кодограммы

1. инвертировать любое количество бит во втором окне и обязательно щелкнуть «Сохранить изменения», чтобы ошибочные биты отличительно покраснели. Если не хотите загонять алгоритм Хемминга в пятый угол, то меняйте не более 2 бит в одном пакете
2. Далее можно щелкать «Проверить и исправить». Результат работы (проверки и самокоррекции) увидите в третьем окне
3. Кнопка «Декодировать», уберет не нужные больше контрольные биты в четверном окне (пакеты снова станут 64-битовыми), а в пятом предоставит исходный текст в символьном виде, причем, если ошибки не поддались коррекции, то текст будет искаженным (его отдельные символы)

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

Рис.2        Результат исправления умышленно внесенных ошибок

Матрица для схемы (64, 7)

Весь код достаточно длинен и сложен, поэтому здесь приведу только основные константы и матрицу:


const char m=64;    //бит в исходном пакете
const char k=7;    //контрольных бит
const char n=m+k+1;    //бит в закодированном пакете (72)

unsigned char lenc;    //9 байт в закодированном пакете переменная модуля

unsigned char matr[n * (k+1)]={
//количество единиц в строке матрицы - нечетное
// (т.к. одна в разряде)
    0,0,0,0,0,1,1, 1,    // 7 - 1
    0,0,0,0,1,0,1, 1,    // 11 - 2
    0,0,0,0,1,1,0, 1,    // 13 - 3
    0,0,0,0,1,1,1, 0,    // 14 - 4
    0,0,0,1,0,0,1, 1,    // 19 - 5
    0,0,0,1,0,1,0, 1,    // 21 - 6
    0,0,0,1,0,1,1, 0,    // 22 - 7
    0,0,0,1,1,0,0, 1,    // 25 - 8
    0,0,0,1,1,0,1, 0,    // 26 - 9
    0,0,0,1,1,1,0, 0,    // 28 - 10
    0,0,0,1,1,1,1, 1,    // 31 - 11
    0,0,1,0,0,0,1, 1,    // 35 - 12
    0,0,1,0,0,1,0, 1,    // 37 - 13
    0,0,1,0,0,1,1, 0,    // 38 - 14
    0,0,1,0,1,0,0, 1,    // 41 - 15
    0,0,1,0,1,0,1, 0,    // 42 - 16
    0,0,1,0,1,1,0, 0,    // 44 - 17
    0,0,1,0,1,1,1, 1,    // 47 - 18
    0,0,1,1,0,0,0, 1,    // 49 - 19
    0,0,1,1,0,0,1, 0,    // 50 - 20
    0,0,1,1,0,1,0, 0,    // 52 - 21
    0,0,1,1,0,1,1, 1,    // 55 - 22
    0,0,1,1,1,0,0, 0,    // 56 - 23
    0,0,1,1,1,0,1, 1,    // 59 - 24
    0,0,1,1,1,1,0, 1,    // 61 - 25
    0,0,1,1,1,1,1, 0,    // 62 - 26
    0,1,0,0,0,0,1, 1,    // 67 - 27
    0,1,0,0,0,1,0, 1,    // 69 - 28
    0,1,0,0,0,1,1, 0,    // 70 - 29
    0,1,0,0,1,0,0, 1,    // 73 - 30
    0,1,0,0,1,0,1, 0,    // 74 - 31
    0,1,0,0,1,1,0, 0,    // 76 - 32
    0,1,0,0,1,1,1, 1,    // 79 - 33
    0,1,0,1,0,0,0, 1,    // 81 - 34
    0,1,0,1,0,0,1, 0,    // 82 - 35
    0,1,0,1,0,1,0, 0,    // 84 - 36
    0,1,0,1,0,1,1, 1,    // 87 - 37
    0,1,0,1,1,0,0, 0,    // 88 - 38
    0,1,0,1,1,0,1, 1,    // 91 - 39
    0,1,0,1,1,1,0, 1,    // 93 - 40
    0,1,0,1,1,1,1, 0,    // 94 - 41
    0,1,1,0,0,0,0, 1,    // 97 - 42
    0,1,1,0,0,0,1, 0,    // 98 - 43
    0,1,1,0,0,1,0, 0,    // 100 - 44
    0,1,1,0,0,1,1, 1,    // 103 - 45
    0,1,1,0,1,0,0, 0,    // 104 - 46
    0,1,1,0,1,0,1, 1,    // 107 - 47
    0,1,1,0,1,1,0, 1,    // 109 - 48
    0,1,1,0,1,1,1, 0,    // 110 - 49
    0,1,1,1,0,0,0, 0,    // 112 - 50
    0,1,1,1,0,0,1, 1,    // 115 - 51
    0,1,1,1,0,1,0, 1,    // 117 - 52
    0,1,1,1,0,1,1, 0,    // 118 - 53
    0,1,1,1,1,0,0, 1,    // 121 - 54
    0,1,1,1,1,0,1, 0,    // 122 - 55
    0,1,1,1,1,1,0, 0,    // 124 - 56
    0,1,1,1,1,1,1, 1,    // 127 - 57
    1,0,0,0,0,0,1, 1,    // 131 - 58
    1,0,0,0,0,1,0, 1,    // 133 - 59
    1,0,0,0,0,1,1, 0,    // 134 - 60
    1,0,0,0,1,0,0, 1,    // 137 - 61
    1,0,0,0,1,0,1, 0,    // 138 - 62
    1,0,0,0,1,1,0, 0,    // 140 - 63
    1,0,0,0,1,1,1, 1,    // 143 - 64

    1,0,0,0,0,0,0, 0,
    0,1,0,0,0,0,0, 0,
    0,0,1,0,0,0,0, 0,
    0,0,0,1,0,0,0, 0,
    0,0,0,0,1,0,0, 0,
    0,0,0,0,0,1,0, 0,
    0,0,0,0,0,0,1, 0,

    0,0,0,0,0,0,0, 1
};


Каждая строка этой матрицы соответствует порядковому номеру бита в пакете Поэтому для кодирования достаточно перемножить вектор-строку исходных бит (длиною 64) на 64 строки данной матрицы На выходе получится вектор-строка из 8 бит (это и есть контрольный байт), который следует прибавить в конец т.е. девятым байтом и длина закодированного пакета станет 72 бита Конечно, есть некоторые тонкости, которые прописаны в коде и благодаря которым, алгоритм работает достаточно стабильно.

При декодировании 72-битная строка перемножается на ту же матрицу и результатом будет являться байт синдромов, анализ битов которого и дает однозначный ответ о наличии ошибок и возможности коррекции

Скачать ехе-файл для тестирования

Удачного Вам тестирования!

Работа с файлами

А этот вариант программы читает информацию из файла (*.txt), кодирует по алгоритму Хемминга и сохраняет в новый файл (*.cdh). Это чтобы самые «недоверчивые» могли вносить умышленные ошибки в файл кода…

Кнопка "Сохранить файл-код" создаст Вам правильный файл, усиленный избыточной информацией. Кодировка ASCII. Можете ломать…

Только помните, что если Вы внесете изменения более чем в 2 бита на пакет, (а для этого достаточно грубо изменить один символ) то, получите непредсказуемый "результат".

Для наглядности, я (аккуратно) внес единичную ошибку в копию файла testEnglish.cdh и назвал эту поврежденную копию testEnglish_err1.cdh; (символ t заменил на символ u). Файл с двойной ошибкой testEnglish_err2.cdh тоже присутствует в прикрепленном наборе (символ Y заменил на символ X). Программа Lister позволяет эти повреждения видеть…

Рис.3        Работа с файлами

Сначала воспользуйтесь кнопкой "Загрузить файл-код", а затем по кнопке "Проверить и исправить" убедиться в востановлении искаженной информации (самокоррекции) или фиксации обнаруженной ошибки.

Скачать ехе-файл для тестирования

Другие примеры на тему «Шифрование, Кодирование и/или Сжатие Информации»

Другие примеры на языках «C»,«C++»,«C#»