Код Хэмминга

Содержание

Какие ошибки можно исправить с помощью кода хэмминга

Первый параметр, скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k

Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов, Рида-Соломона (15, 11) и т. д.

Второй параметр, кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.

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

Контроль чётности

Самый простой метод помехоустойчивого кодирования это добавление одного бита четности. Есть некое информационное сообщение, состоящее из 8 бит, добавим девятый бит.

Если нечетное количество единиц, добавляем 0.

1 0 1 0 0 1 0 0 | 0

Если четное количество единиц, добавляем 1.

1 1 0 1 0 1 0 0 | 1

Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.

1 1 0 0 0 1 0 0 | 1

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

Есть последовательность 0 и 1, и из этой последовательности составим прямоугольную матрицу размера 4 на 4. Затем для каждой строки и столбца посчитаем бит четности.

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

И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется.

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.

Рассчитаем скорость кода для:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

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

Классификация помехоустойчивых кодов

По используемому алфавиту:

Блочные коды делятся на

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

Смотря на картинку выше, код 1 1 0 0 0 1 0 0 | 1 является систематическим, на вход поступило 8 бит, а на выходе кодера 9 бит, которые в явном виде содержат в себе 8 бит информационных и один проверочный.

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

Код Хэмминга (7,4) — 4 бита на входе кодера и 7 на выходе, следовательно 3 проверочных бита. С 1 по 4 информационные биты, с 6 по 7 проверочные (см. табл. выше). Пятый проверочный бит y5, это сумма по модулю два 1-3 информационных бит. Сумма по модулю 2 это вычисление бита чётности.

Декодирование кода Хэмминга

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

Существует некоторый набор параметров помехоустойчивого кодирования:

Величина кратности обнаруженных ошибок. То есть число символов с ошибками, которое код способен определить.

Величина кратности исправленных ошибок. То есть число символов с ошибками, которые код способен скорректировать (обозначим символом t). Контроль чётности

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

При нечётном количестве единиц прибавляем нуль:

1 0 1 0 0 1 0 0 | 0

При чётном количестве единиц прибавляем единицу:

1 1 0 1 0 1 0 0 | 1

Когда при приёме информации полученный бит чётности не соответствует рассчитанному биту чётности, то фиксируется ошибка.

Классификация помехоустойчивых кодов

Существует следующая классификация помехоустойчивых кодов:

По применяемому символьному набору помехоустойчивые системы кодирования делятся на:

В свою очередь блочные коды подразделяются на:

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

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

Ниже приведена методика кодирования по Хэммингу:

Рисунок 1. Методика кодирования по Хэммингу. Автор24 — интернет-биржа студенческих работ

Код Хэмминга (7,4) подразумевает наличие четырёх бит на входе кодирующего устройства и семь на его выходе, то есть три бита являются проверочными. Биты с первого по четвёртый являются информационными битами, шестой и седьмой — это проверочные биты, а пятый проверочный бит является суммой по модулю два с первого по третий информационные биты. Сумма по модулю два считается вычислением бита чётности.

Декодирование кодировки Хэмминга выполняется посредством определения синдрома по выражениям:

Рисунок 2. Декодирование кодировки Хэмминга. Автор24 — интернет-биржа студенческих работ

Синдромом является сложение битов по модулю два. Если синдром не равняется нулю, то коррекция ошибки выполняется согласно таблице декодирования:

Рисунок 3. Таблица декодирования. Автор24 — интернет-биржа студенческих работ

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

Лабораторные работы Методы Документы Лабораторные работы Методички Лабораторное оборудование

Министерство образования И НАУКИ Российской Федерации

Уральский государственный технический университет-УПИ

кафедра молекулярной физики

Методические указания к лабораторной работе

Помехозащищенное кодирование. Коды Хэмминга

Научный редактор: доц., канд. физ.-мат. наук О. Е. Александров

Совершенные коды Хэмминга ¾ пример алгоритма помехозащищенного кодирования и одни из немногих известных совершенных кодов.

Описаны история возникновения и область применения помехозащищенного кодирования. Подробно рассмотрен пример реализации кодирования этим методом, в виде демонстрационной программы на MathCAD. Описано устройство программы и работа с демонстрационной программой.

Подготовлено кафедрой «Молекулярная физика».

Методические указания обсуждены на заседании кафедры молекулярной физики, протокол №

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ. 4

1. Что такое помехозащищенное кодирование. 7

1.1. История кодирования, контролирующего ошибки. 7

1.2. Приложения помехозащищённого кодирования. 9

1.3. Классификация помехоустойчивых кодов. 11

1.4. Блочные коды. 15

1.5. Линейные блоковые коды. 16

1.6. Матричное кодирование. 16

1.7. Совершенные коды. 17

2. КОДЫ ХЭММИНГА. 17

2.1. Описание кодирования по Хэммингу. 17

2.2. Описание декодирования и исправления ошибки по Хэммингу. 20

2.3. Невозможность коррекции двойных ошибок и любых ошибок большей кратности. 21

2.4. Основные недостатки кода Хэмминга. 22

2.2. Демонстрационная программа. 24

2.2.1. Состав демонстрационной программы. 24

2.2.2. Описание основных функций демонстрационной программы 25

2.2.3. Описание функций построения матрицы для матричного кодирования Хэминга. 30

3. Задания для самостоятельного выполнения. 32

Список Использованных источников. 34

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ

Сигнал — любая функция времени, в частности, любая последовательность чисел. Любой сигнал может быть представлен в двоичной форме, как некоторая последовательность битов, например: … Именно такую последовательность битов мы будем называть «сигналом» далее.

Код — форма представления сигнала, не зависящая от его физической сути.

Блок кода — кусок сигнала фиксированной длины.

Кодирование сигнала — преобразование одной последовательности битов в другую последовательность битов, допускающую восстановление исходной последовательности битов без искажений.

Блочный код — способ кодирования, когда блок кода преобразуется в блок кода другой длины.

Ошибки — случайные искажения битов сигнала при передаче или хранении.

Кратность ошибки — число искаженных битов на один блок кода.

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

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

Введение

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

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

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

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

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

Методические материалы и программа позволят студентам лучше понять принципы помехозащищенного кодирования.

1. Что такое помехозащищенное кодирование

1.1. История кодирования, контролирующего ошибки

История кодирования, контролирующего ошибки, началась в 1948 г. публикацией знаменитой статьи Клода Шеннона. Шеннон показал, что с каждым каналом связано измеряемое в битах в секунду и называемое пропускной способностью канала число С, имеющее следующее значение. Если требуемая от системы связи скорость передачи информации R (измеряемая в битах в секунду) меньше С, то, используя коды, контролирующие ошибки, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала. В самом деле, из шенноновской теории информации следует тот важный вывод, что построение слишком хороших каналов является расточительством; экономически выгоднее использовать кодирование. Фактически в работе Шеннона утверждается, что мощность сигнала, шум в канале и полоса частот ограничивают лишь скорость передачи, а не ее точность. Шеннон, однако, не указал, как найти подходящие коды, а лишь доказал их существование. В пятидесятые годы много усилий было потрачено на попытки построения в явном виде классов кодов, позволяющих получить обещанную сколь угодно малую вероятность ошибки, но результаты были скудными. В следующем десятилетии решению этой увлекательной задачи уделялось меньше внимания; вместо этого исследователи кодов предприняли длительную атаку по двум основным направлениям.

Первое направление носило чисто алгебраический характер и преимущественно рассматривало блоковые коды. Первые блоковые коды были введены в 1950 г., когда Хэмминг описал класс блоковых кодов, исправляющих одиночные ошибки. Коды Хэмминга были разочаровывающе слабы по сравнению с обещанными Шенноном гораздо более сильными кодами. Несмотря на усиленные исследования, до конца пятидесятых годов не было построено лучшего класса кодов. В течение этого периода без какой-либо общей теории были найдены многие коды с малой длиной блока. Основной сдвиг произошел, когда Боуз и Рой-Чоудхури [1960] и Хоквингем [1959] нашли большой класс кодов, исправляющих кратные ошибки (коды БЧХ), а Рид и Соломон [1960] нашли связанный с кодами БЧХ класс кодов для недвоичных каналов. Хотя эти коды остаются среди наиболее важных классов кодов, общая теория блоковых кодов, контролирующих ошибки, с тех пор успешно развивалась, и время от времени удавалось открывать новые коды.

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

В 70-х годах эти два направления исследований опять стали переплетаться. Теорией сверточных кодов занялись алгебраисты, представившие ее в новом свете. В теории блоковых кодов за это время удалось приблизиться к кодам, обещанным Шенноном: были предложены две различные схемы кодирования (одна Юстесеном, а другая Гоппой), позволяющие строить семейства кодов, которые одновременно могут иметь очень большую длину блока и очень хорошие характеристики. Обе схемы, однако, имеют практические ограничения, и надо ждать дальнейших успехов. Между тем к началу 80-х годов кодеры и декодеры начали появляться в новейших конструкциях цифровых систем связи и цифровых систем памяти.

1.2. Приложения помехозащищённого кодирования

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

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

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

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

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

1.3. Классификация помехоустойчивых кодов

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

К комбинационным кодам можно отнести также антифединговые коды, предназначенные для обнаружения и исправления ошибок в каналах с замираниями (федингом) сигналов. Для таких каналов с группированием ошибок применяют метод перемежения символов или декорреляции ошибок. Он заключается в том, что символы, входящие в одну кодовую комбинацию, передаются не непосредственно друг за другом, а перемежаются символами других кодовых комбинаций исходного систематического или любого другого кода. Если интервал между символами, входящими в одну кодовую комбинацию, сделать длиннее "памяти" (интервала корелляции) канала с замираниями, то в пределах длительности одной исходной кодовой комбинации группирования ошибок не будет. На приёме после обратной "расфасовки" в кодовых комбинациях можно производить декодирование с обнаружением и исправлением ошибок.

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

К систематическим кодам относятся коды с проверкой на чётность, коды с повторением, корреляционный, инверсный, коды Хэмминга, Голея, Рида-Маллера, Макдональда, Варшамова, с малой плотностью проверок на чётность, итеративный код. Эти коды получили наибольшее применение в системах передачи дискретной информации.

Разновидностью систематических кодов являются циклические коды. Кроме всех свойств систематического кода, циклические коды имеют следующее свойство: если некоторая кодовая комбинация принадлежит коду, то получающаяся путём циклической перестановки символов новая комбинация также принадлежит данному коду. К наиболее известным циклическим кодам относятся простейшие коды, коды Хэмминга, Боуза – Чоудхури – Хоквингема, мажоритарные, коды Файра, Абрамсона, Миласа – Абрамсона, Рида – Соломона, компаундные коды. Проблема помехоустойчивого кодирования представляет собой обширную область теоретических и прикладных исследований. Основными задачами при этом являются следующие: отыскание кодов, эффективно исправляющих ошибки требуемого вида; нахождение методов кодирования и декодирования и простых способов их реализации.

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

1.4. Блочные коды

Блочный код задает блок из k информационных символов n-символьным кодовым словом. Скорость R блокового кода определяется равенством R = k/n.

О блочном коде судят по трем параметрам: длине блока n, информационной длине k и минимальному расстоянию d*. Минимальное расстояние является мерой различия двух наиболее похожих кодовых слов.

1.5. Линейные блоковые коды

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

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках, менее высока.