Код Хемминга. Программа на С++ (Visual Studio 2008), демонстрирующая
самокорректирующие возможности кодирования Ричарда Хемминга.

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

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

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

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

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

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

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

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

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

C++ Кодирование Хемминга

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

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

C++ Кодирование и декодирование Хемминга

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

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-битная строка перемножается на ту же матрицу и результатом будет являться байт синдромов, анализ битов которого и дает однозначный ответ о наличии ошибок и возможности коррекции…

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

скачать exe-файл

Возможно, кому-то пригодится (понадобится) скайп-консультация…
Готов ответить на вопросы…


Условия получения кода?    Показать?


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

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




Если на этой странице не нашлось того, что Вы так искали...

         Не расстраивайтесь, не все потеряно... Смело щелкайте...

исходный код на заказ. orenstudent.ru Автоматизация документов MS Office. orenstudent.ru исходный код на заказ. orenstudent.ru Помогите найти и устранить ошибку в исходном коде программы. orenstudent.ru Skype-консультирование по программированию
Скайп-консультации

Акция !!!
Весь код по 49 руб


требуются
школьники!


и СТУДЕНТЫ!
Кому не плевать
на деньги!
Сайт помощи студентам по программированию и информатике