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

Закодировать кодом хэмминга и проверить исправление одной ошибки в любом бите

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

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

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

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

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

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

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

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

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

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

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

Рис.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 Работа с файлами

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

учебно-методическое пособие по информатике и икт (10, 11 класс) по теме

Коробейникова Ольга Витальевна

На сегодняшний день в мире передается огромное количество информации, хотя системы передачи данных отвечают всем требованиям. Они не являются столь совершенными.

Скачать:

Предварительный просмотр:

Федеральное государственное бюджетное образовательное учреждение

«Омский государственный педагогический университет»

Факультет математики, информатики, физики и технологии

Кафедра прикладной информатики и математики

Направление: педагогическое образование

Профиль: Информатика и Технология

Дисциплина: Теоретические основы информатики

«__» _______________ 20___г.

Введение

На сегодняшний день в мире передается огромное количество информации, хотя системы передачи данных отвечают всем требованиям. Они не являются столь совершенными. При передаче данных могут возникать помехи. Помехоустойчивость – способность системы осуществлять прием информации в условиях наличия помех в линии связи и искажений во внутри аппаратных трактах. Помехоустойчивость обеспечивает надежность и достоверность передаваемой информации (данных).Управление правильностью передачи информации выполняется с помощью помехоустойчивого кодирования. Есть коды, обнаруживающие ошибки, и корректирующие коды, которые еще и исправляют ошибки. Помехозащищенность достигается с помощью введения избыточности, дополнительных битов. В симплексных каналах связи устраняют ошибки с помощью корректирующих кодов. В дуплексных–достаточно применения кодов, обнаруживающих ошибки. [1]

История развития помехоустойчивого кодирования началась еще с 1946г., а именно, после публикации монографии американского ученого К. Шеннона «Работы по теории информации и кибернетике».В этой работе он не показал как построить эти коды, а доказал их существование. Важно отметить, что результаты работы К. Шеннона опирались на работы советских ученых, таких как: А. Я. Хинчин, Р. Р. Варшамов и др. На сегодняшний день проблема передачи данных является особо актуальной, т.к. сбой при передаче может вызвать не только искажение сообщения в целом, но и полную потерю информации. Для этого и существуют помехоустойчивые коды, способные предотвратить потерю и искажение информации. В настоящее время существует ряд разновидностей помехоустойчивых кодов, обеспечивающих высокую достоверность при малой величине избыточности и простоте технической реализации кодирующих и декодирующих устройств. Принципиально коды могут быть использованы как для обнаружения, так и для исправления ошибок. Однако удобства построения кодирующих и декодирующих устройств определили преимущественное применение лишь некоторых из них, в частности корректирующего кода Хемминга.

Цель данной курсовой работы: Ознакомление с помехоустойчивым кодированием и изучение кода Хемминга.

1) Ознакомиться с видами помехоустойчивого кодирования;

2) Ознакомиться с кодом Хемминга, как с одним из видов помехоустойчивого кодирования;

3) Изучить алгоритм построения кода Хемминга.

Объект исследования : помехоустойчивое кодирование.

Предмет исследования : код Хемминга.

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

Глава 1. Теоретические основы изучения помехоустойчивого кодирования

1.1. Виды помехоустойчивого кодирования

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

Рис. 1.Помехи и их источники

Внешние источники помех вызывают в основном импульсные помехи, а внутренние – флуктуационные. Помехи, накладываясь на видеосигнал, приводят к двум типам искажений: краевыеи дробления. Краевые искажения связаны со смещением переднего или заднего фронта импульса. Дробление связано с дроблением единого видеосигнала на некоторое количество более коротких сигналов [2].

Приведем классификацию помехоустойчивых кодов.

1) Обнаруживающие ошибки:

2) Корректирующие коды:

А) С пороговым декодированием;

Б) По макс. правдоподобия;

В) С последовательным декодированием.

Теперь рассмотрим более подробно каждый вид кодирования.

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

В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно. Изменение этого бита (например с 0 на 1) сообщает о возникшей ошибке.

Начальные данные: 1111

Данные после кодирования: 11110 (1 + 1 + 1 + 1 = 0 (mod 2))

Принятые данные: 10110 (изменился второй бит)

Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка [3].

Корреляционные коды (код с удвоением ).

Элементы данного кода заменяются двумя символами, единица «1» преобразуется в 10, а ноль «0» в 01.

Вместо комбинации 1010011 передается 10011001011010. Ошибка обнаруживается в том случае, если в парных элементах будут одинаковые символы 00 или 11 (вместо 01 и 10) [2].

Код с постоянным весом.

Одним из простейших блочных неразделимых кодов является код с постоянным весом. Примером такого кода может служить семибитный телеграфный код МТК–3, в котором каждая разрешенная кодовая комбинация содержит три единицы и четыре нуля (рис.2). Весом кодовой комбинации называют число содержащихся в ней единиц. В рассматриваемом коде вес кодовых комбинаций равен трем.

Число разрешенных кодовых комбинаций в кодах с постоянным весом определяется как количество сочетаний из n символов по g и равно

Рис.2. Примеры разрешенных и запрещенных комбинаций кода МТК-3

К исходной комбинации добавляется такая же комбинация по длине. В линию посылается удвоенное число символов. Если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную комбинацию, если нечетное, то добавляемая комбинация является инверсной по отношению к исходной.

Прием инверсного кода осуществляется в два этапа. На первом этапе суммируются единицы в первой основной группе символов. Если число единиц четное, то контрольные символы принимаются без изменения, если нечетное, то контрольные символы инвертируются. На втором этапе контрольные символы суммируются с информационными символами по модулю два. Нулевая сумма говорит об отсутствии ошибок. При ненулевой сумме, принятая комбинация бракуется. Покажем суммирование для принятых комбинаций без ошибок (1,3) и с ошибками (2,4).

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

Недостатком кода Грея является его невесомость, т. е. вес единицы не определяется номером разряда. Информацию в таком виде трудно обрабатывать на ЭВМ. Декодирование кода также связано с большими затратами. Поэтому перед вводом в ЭВМ (или перед декодированием) код Грея преобразуется в простой двоичный код, который удобен для ЭВМ и легко декодируется.

Для перевода простого двоичного кода в код Грея нужно:

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

1.2.Характеристика кода Хэмминга при помехоустойчивом кодировании

В середине 40-х годов Ричард Хемминг работал в знаменитых Лабораториях Белла на счётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машине с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.

Р. Хемминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто был должен перегружать свою программу из-за ненадежности перфокарт. На протяжении нескольких лет он проводил много времени над построением эффективных алгоритмов исправления ошибок. В 1950 году он опубликовал способ, который на сегодняшний день мы знаем как код Хемминга.[6.].

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

(r – количество проверочных разрядов).

Рис.3. Проверочная матрица

Перестановкой столбцов, содержащих одну единицу, данную матрицу можно привести к виду(рис.4)

Рис. 4.Измененная матрица

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

Рис.5. Система проверочных уравнений

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

Операция кодирования может выполняться в два этапа. На первом этапе определяется кодовая комбинация с использованием матрицы H, соответствующей коду с на втором — добавляется один проверочный разряд, в котором записывается результат суммирования по модулю два всех разрядов кодового слова, полученного на первом этапе. Операция декодирования также состоит из двух этапов. На первом вычисляется синдром, соответствующий коду на втором — проверяется последнее проверочное соотношение.[8]

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

1.3.Алгоритмы использования кода Хэмминга для нахождения ошибок

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

Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

Количество разрядов m – определяет количество проверок.

В третью проверку – коэффициенты которые содержат 1 в третьем разряде и т. д.

Источники:

https://orenstudent. ru/Hemming. htm

https://nsportal. ru/shkola/informatika-i-ikt/library/2016/10/03/kursovaya-rabota-kod-hemminga

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: