Remkomplekty.ru

IT Новости из мира ПК
31 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Код хемминга паскаль

Код Хемминга. Демонстрирующая программа

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

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

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

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

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

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

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

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

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

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

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

Этот же алгоритм удалит из кодограммы не нужные больше контрольные биты и оставит только исходный текст.

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

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

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

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

Матрица для схемы (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

Читать еще:  Поменять строки в матрице паскаль

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

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

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

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

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

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

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

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

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

Код Хэмминга (7; 4)

Всем привет! Сегодня я хочу рассказать вам немного о коде Хэмминга (7; 4). Этот простейший код может быть с лёгкостью применён любым человеком для передачи самокорректирующихся сообщений , и сегодня я хочу вам показать как именно этот код можно легко и просто использовать.

Структурно слова кода Хэмминга состоят из двух частей. Сначала идут информационные 4 бита, затем три бита проверочных. Будем обозначать информационные биты буквами ABCD, проверочные буквами xyz.

Таким образом слово кода Хэмминга имеет следующую структуру:

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

Естественно, использование кода Хэмминга при передаче данных требует увеличенных ресурсов. Здесь есть такое важное понятие как скорость кода — отношение числа информационных бит к общему числу бит. В случае кода Хэмминга скорость равна 4/7. Т.е., к примеру, чтобы передавать информацию со скоростью 1 Мбит/сек и коррекцией ошибок с помощью кода Хэмминга вам потребуется канал с пропускной способностью минимум в 7/4=1.75 Мбит/сек.

Для подсчёта проверочных бит можно использовать следующие формулы:

x = A + B + C mod 2,

y = A + B + D mod 2,

z = A + C + D mod 2,

где n mod 2 означает остаток от деления числа n на 2.

К примеру, если информационный вектор есть ABCD = 1001, то кодовый вектор будет ABCDxyz = 1001 100

Вместо непонятных формул можно использовать следующую картинку:

Здесь всё очень просто. Подставляете вместо букв значения соответствующих битов и затем считаете значения x, y и z как сумму по модулю 2 тех информационных бит, которые есть в соответствующем круге.

В приведённом выше примере будет:

Куда более интересным является вопрос об исправлении ошибок. Очевидно, вывод об отсутствии ошибок приёмник может сделать просто взяв информационные биты ABCD, посчитав на их основе проверочные биты xyz и сравнить посчитанные проверочные биты с принятыми. Если есть ошибка, то часть проверочных битов не совпадёт.

Предположим что произошла ошибка в проверочном бите y и было принято слово 1001 110

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

Предположим, что произошла ошибка в одном из информационных битов BCD — к примеру в бите B.

В таком случае не сойдутся аж два проверочных бита — x (он равен 1, а «должен» равняться 0) и y. Посмотрев на круги легко увидим что они пересекаются по битам B и A. Т.к. не сошлось две проверки, то берём бит B (расположенный на пересечении двух проверок).

Наконец, отдельно рассмотрим бит A. Если в нём ошибка, то у нас не сойдутся все три проверки:

Увидев такое безобразие сразу же делаем вывод о том, что ошибка в бите A.

Таким образом, можно легко и просто вычислять локацию ошибки и исправлять её. Замечу что если ошибок больше одной, то описанный выше алгоритм сработает неверно. К примеру, допустим что произошли ошибки в битах C и z:

Читать еще:  Динамический и статический массив паскаль

Проверочные биты y и z сойдутся, а бит x нет. Алгоритм исправит бит x и всё. Это вполне естественное поведение, т.к. если вероятность ошибки p 0).

Естественно, работать с цветными кругами удобно человеку, но неудобно компьютеру. У кодов Хэмминга есть одна особенность, которая позволяет их лёгкое декодирование на компьютере. Итак, рассмотрим следующий алгоритм:

Определим числа g, b, r как сумму всех четырёх бит в кругах соответствующего цвета. Т.е.:

g = A + B + C + x mod 2,

b = A + B + D + y mod 2,

r = A + C + D + z mod 2.

Фактически каждый из этих бит можно определить как сумму соответствующего проверочного бита, вычисленного на основании принятых информационных бит, с принятым проверочным битом. Т.е. к примеру g есть сумма (A + B + C mod 2) (по этой формуле считался x на стороне передатчика) и принятого x. Аналогично b соответствует y, r соответствует z.

Если ошибок нет, то gbr = 000 (принятые проверочные биты сошлись с вычисленными на основе информационного вектора).

Если же есть 1 ошибка, то число gbr есть номер (в двоичной записи) ошибочного бита в векторе ABCxDyz.

В качестве примера рассмотрим уже знакомый нам вектор ABCDxyz = 1001 100, в котором произошла ошибка в бите x (четвёртый бит в векторе ABCxDyz). Посчитаем gbr:

gbr = 100 [2] = 4 [10]. Ошибка в 4 бите, которым и является x. Таким образом, для декодирования и исправления ошибки в кодовом слове длины 7 требуется лишь вычислить три суммы и из полученного числа несложной функцией получить местонахождение ошибки.

Кодер и декодер кода Хэмминга на 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)

Для быстрой проверки кодировщика и декодировщика кода Хэмминга (15, 11), используя вышеописанные классы, я написал две программы. Первая – кодер Хэмминга . Вводите 11-разрядное число (от 0 до 0x7FF или 2047), и на выходе получаем 16-разрядное число, представленное в виде двух байтов.

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

Вторая программа – декодер кода Хмминга (15, 11) .

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

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

Обе программы работают под ОС Windows и требуют .NET версии 3.5 . Выкладываю описанные программы.

Расширенный код Хэмминга

Краткие теоретические сведения

Код Хемминга с кодовым расстоянием dmin = 4 называется расширенным. Он обеспечивает исправление всех однократных ошибок и обнаружение всех двух- и трехкратных ошибок. Для этого вводится дополнительный проверочный разряд b, который дописывается к проверочной матрице Хемминга с кодовым расстоянием dmin = 3, благодаря чему последнее увеличивается на 1.

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

Читать еще:  Классы в си шарп

На практике лучше применять иной метод получения расширенного кода Хемминга. Для этого кодовую комбинацию кода Хемминга просто дополняют дополнительным проверочным элементом b, который находится с помощью проверки кодовой комбинации на парность. При этом проверочный элемент равен 1, если количество единиц в закодированной кодовой комбинации непарное, и 0, если парное.

Декодируют в обратной последовательности: сначала выполняют общую проверку, а потом проверку без дополнительного элемента b. При этом могут возникнуть такие варианты:

1) ошибок нет (обе проверки дают нулевые синдромы);

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

3) есть двукратная ошибка (общая проверка говорит об отсутствии ошибок, а проверка без дополнительного проверочного элемента показывает место ошибки; но эту ошибку исправлять не надо, надо просто констатировать то, что ошибки 2).

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

С учетом вышесказанного коды Хемминга с dmin = 4 используются, как правило, для обнаружения одно-, двух-, и трехкратных ошибок.

Кодирование

Кодовая комбинация, которую необходимо закодировать:

Сначала необходимо закодировать комбинацию обычным кодом Хемминга (с кодовым расстоянием dmin = 3), что было выполнено в разделе 3.5.3. Был получен следующий результат:

11111101111111101001.

Для получения расширенного кода Хемминга далее выполняем кодирование с проверкой на четность, тем самым расширяя обычный код Хемминга дополнительным проверочным элементом b. Количество единиц в кодовом слове – 16, следовательно, проверочный разряд равен 0, поскольку тогда количество единиц в закодированной кодовой комбинации будет четное. Дописываем дополнительный проверочный разряд и получаем закодированное сообщение:

111111011111111001001 .

Декодирование

Пускай при передаче закодированного сообщения произошла ошибка в 13-ом разряде, и декодер получил следующую искаженную кодовую комбинацию:

111111011111110010010.

Сначала выполним декодирование кода с проверкой на четность. Сумма единиц в полученном слове равна 15, то есть число нечетное, что свидетельствует о наличии ошибки. Поскольку расширенный код Хэмминга позволяет исправлять только одиночные ошибки, то предположим, что произошедшая ошибка одиночная, и исправим ее. Отбрасываем дополнительный проверочный разряд и получаем кодовую комбинацию обычного кода Хэмминга, в которой есть одиночная ошибка:

Далее выполняем декодирование обычного кода Хэмминга. Для этого для данной кодовой комбинации вычислим синдром ошибки при помощи системы, полученной в п. 3.5.3. из проверочной матрицы H21,16:

Следовательно, синдром имеет вид:

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

Инвертируем искаженный 13-й разряд, отбрасываем проверочные 1-й, 2-й, 4-й, 8-й и 16-й разряды и получаем декодированное сообщение с исправленной ошибкой:

Итеративный код

Краткие теоретические сведения

Для передачи информации широко используются итеративные коды, обладающие высокой обнаруживающей способностью. При определении проверочных элементов q-ичных итеративных кодов производят сложение элементов кодовых комбинаций базового кода по модулю q. Обнаружение ошибок производится по аналогии с двоичным кодом – сравнением проверочных элементов каждой строки (столбца), принятых из канала и полученных на приемной стороне путем вычислений.

Исправление искаженного элемента производят следующим образом. Если не выполняется проверка для i-ой строки и j-ого столбца, то элемент, находящийся на пересечении i-ой строки и j-ого столбца, заменяется элементом, вычисленным путем сложения данного принятого элемента (ошибочного) со значением, полученным путем вычитания значений принятого из канала и вычисленного на приемной стороне проверочных элементов i-ой строки (или j-ого столбца).

Кодирование

Кодовая комбинация, которую необходимо закодировать:

11101111 11101001 11110111.

Необходимо разбить нашу кодовую комбинацию на блоки таким образом, чтобы матрица, строки которой представляют собой эти блоки, была наиболее близка к квадратной – тогда количество проверочных разрядов будет наименьшим. Следовательно, нашу 24-битную комбинацию нужно разбить на блоки по 6 бит (6×4 = 24):

111011 111110 100111 110111.

Построим матрицу из этих 4-х блоков и вычислим проверочные символы путем сложения элементов строк и столбцов матрицы по модулю 2, то есть, кодируем строки и столбцы кодом с проверкой на четность.

Закодируйте сообщениеα кодом Хемминга из задачи 4.4.4

Образец:Закодируйте сообщениеα=(0101)кодом Хемминга из задачи 4.4.4. (образец):

Решение: Умножим кодовое слово a на порождающую матрицу G:

.

Отсюда кодированное сообщение имеет вид (0101011).

Первые m=4 информационные символы вектора αG образуют исходное сообщение α=(0101), последние n-m=3символа используются для контроля.

4.4.6. Решите задачу:

Декодируйте кодом Хемминга сообщение b в задаче 4.4.3.:

Образец: Декодируйте кодом Хемминга сообщение b=(0111001) в задаче 4.4.3.

Решение: Умножим проверочную матрицу из задачи 4.30 на вектор-столбец = – транспонированное сообщение b. Имеем

.

Т.к. в результате получен ненулевой вектор , то это означает, что при декодировании была допущена ошибка. Т.к. этот вектор-столбец совпадает с первым столбцом проверочной матрицы M, то надо изменить, (инвертировать) именно первый символ в сообщении b. Получим новый вектор bн=(1111001), в котором при m=4 первые четыре буквы a=(1111) составляют истинное декодированное сообщение.

4.4.7.Построить коды H(b) для заданных слов b=(010101), x=(110100), y=(011010).

1) Для построения кодов H(b) необходимо иметь двоичные векторы, записанные словом длиной k. Рассчитаем по k формуле . При n = 6 имеем неравенство . Отсюда т.к. 4 2 3 . Значит k=3.

2) Двоичные векторы длины 3 обозначим e3:

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×