Как исправить ошибку в коде хемминга

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

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

p, blockquote 1,0,0,0,0 —>

p, blockquote 2,0,0,0,0 —>

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

p, blockquote 3,0,0,0,0 —>

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

p, blockquote 4,0,0,0,0 —>

p, blockquote 5,0,0,0,0 —>

Использование кодирования позволяет извлекать информацию без потерь даже с поврежденного CD/DVD диска, когда какая либо область становится недоступной для считывания.

p, blockquote 6,0,0,0,0 —>

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

  • запрос повторной передачи (Automatic Repeat reQuest, ARQ): с помощью помехоустойчивого кода выполняется только обнаружение ошибок, при их наличии производится запрос на повторную передачу пакета данных;
  • прямое исправление ошибок (Forward Error Correction, FEC): производится декодирование помехоустойчивого кода, т. е. исправление ошибок с его помощью.

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

p, blockquote 8,0,0,0,0 —>

Исправление ошибок в помехоустойчивом кодировании

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

p, blockquote 9,0,0,0,0 —>

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

p, blockquote 10,0,0,0,0 —>

Допустим есть 4 символа информации, А, B, С, D, и эту информацию повторяем несколько раз. В процессе передачи информации по каналу связи, где-то возникла ошибка. Есть три пакета (A1B1C1D1|A2B2C2D2|A3B3C3D3), которые должны нести одну и ту же информацию.

p, blockquote 11,0,0,0,0 —>

мажоритарный метод

p, blockquote 12,0,0,0,0 —>

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

p, blockquote 13,0,0,0,0 —>

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

p, blockquote 14,0,0,0,0 —>

Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.

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

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

  • где n – количество символов закодированного сообщения (результата кодирования);
  • m – количество проверочных символов, добавляемых при кодировании;
  • k – количество информационных символов.

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

p, blockquote 17,0,0,0,0 —>

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

p, blockquote 18,0,0,0,0 —>

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

p, blockquote 19,0,0,0,0 —>

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

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

p, blockquote 20,0,0,0,0 —>

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

p, blockquote 21,0,0,0,0 —>

1 0 1 0 0 1 0 0 | 0

p, blockquote 22,0,0,0,0 —>

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

p, blockquote 23,0,0,0,0 —>

1 1 0 1 0 1 0 0 | 1

p, blockquote 24,0,0,0,0 —>

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

p, blockquote 25,0,0,0,0 —>

1 1 0 0 0 1 0 0 | 1

p, blockquote 26,0,0,0,0 —>

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

p, blockquote 27,0,0,0,0 —>

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

p, blockquote 28,0,0,0,0 —>

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

p, blockquote 29,0,0,0,0 —>

прямоугольный код

p, blockquote 30,0,0,0,0 —>

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

p, blockquote 31,0,0,0,0 —>

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

p, blockquote 32,0,0,0,0 —>

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

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

p, blockquote 35,0,0,0,0 —>

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

p, blockquote 36,0,0,0,0 —>

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

  • Непрерывные — процесс кодирования и декодирования носит непрерывный характер. Сверточный код является частным случаем непрерывного кода. На вход кодера поступил один символ, соответственно, появилось несколько на выходе, т. е. на каждый входной символ формируется несколько выходных, так как добавляется избыточность.
  • Блочные (Блоковые) — процесс кодирования и декодирования осуществляется по блокам. С точки зрения понимания работы, блочный код проще, разбиваем код на блоки и каждый блок кодируется в отдельности.

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

  • Двоичные. Оперируют битами.
  • Не двоичные (код Рида-Соломона). Оперируют более размерными символами. Если изначально информация двоичная, нужно эти биты превратить в символы. Например, есть последовательность 110 110 010 100 и нужно их преобразовать из двоичных символов в не двоичные, берем группы по 3 бита — это будет один символ, 6, 6, 2, 4 — с этими не двоичными символами работают не двоичные помехоустойчивые коды.

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

  • Систематические — отдельно не измененные информационные символы, отдельно проверочные символы. Если на входе кодера присутствует блок из k символов, и в процессе кодирования сформировали еще какое-то количество проверочных символов и проверочные символы ставим рядом к информационным в конец или в начало. Выходной блок на выходе кодера будет состоять из информационных символов и проверочных.
  • Несистематические — символы исходного сообщения в явном виде не присутствуют. На вход пришел блок k, на выходе получили блок размером n, блок на выходе кодера не будет содержать в себе исходных данных.

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

p, blockquote 39,0,0,0,0 —>

систематический и несистематический код

p, blockquote 40,0,0,0,0 —>

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

p, blockquote 41,0,0,0,0 —>

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

p, blockquote 42,0,0,0,0 —>

Код Хэмминга

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

p, blockquote 43,0,0,0,0 —>

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

p, blockquote 44,0,0,0,0 —>

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

p, blockquote 45,0,0,0,0 —>

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

Декодирование происходит через вычисление синдрома по выражениям:

p, blockquote 46,0,0,0,0 —>

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

p, blockquote 47,0,0,0,0 —>

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

p, blockquote 48,0,0,0,0 —>

Таблица декодирования. Код Хэмминга

p, blockquote 49,0,0,0,0 —>

Расстояние Хэмминга

Расстояние Хэмминга — число позиций, в которых соответствующие символы двух кодовых слов одинаковой длины различны. Если рассматривать два кодовых слова, (пример на картинке ниже, 1 0 1 1 0 0 1 и 1 0 0 1 1 0 1) видно что они отличаются друг от друга на два символа, соответственно расстояние Хэмминга равно 2.

p, blockquote 50,0,0,1,0 —>

расстояние хэмминга

p, blockquote 51,0,0,0,0 —>

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

p, blockquote 52,0,0,0,0 —>

Помехоустойчивые коды

Современные коды более эффективны по сравнению с рассматриваемыми примерами. В таблице ниже приведены Коды Боуза-Чоудхури-Хоквингема (БЧХ)

p, blockquote 53,0,0,0,0 —>

Коды Боуза-Чоудхури-Хоквингема (БЧХ)

p, blockquote 54,0,0,0,0 —>

Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k.

  • n — количество символов на входе.
  • k — количество символов на выходе.
  • t — кратность исправляемых ошибок.
  • Отношение k/n — скорость кода.
  • G (энергетический выигрыш) — величина, показывающая на сколько можно уменьшить отношение сигнал/шум (Eb/No) для обеспечения заданной вероятности ошибки.

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

p, blockquote 56,0,0,0,0 —>

Пример: помехоустойчивые коды и двоичная фазовая манипуляция (2-ФМн). На графике зависимость отношения сигнал шум (Eb/No) от вероятности ошибки. За счет применения помехоустойчивых кодов улучшается помехоустойчивость.

p, blockquote 57,0,0,0,0 —>

График помехоустойчивых кодов

p, blockquote 58,0,0,0,0 —>

Из графика видим, код Хэмминга (7,4) на сколько увеличилась помехоустойчивость? Всего на пол Дб это мало, если применить код БЧХ (127, 64) выиграем порядка 4 дБ, это хороший показатель.

p, blockquote 59,0,0,0,0 —>

Компромиссы при использовании помехоустойчивых кодов

Чем расплачиваемся за помехоустойчивые коды? Добавили избыточность, соответственно эту избыточность тоже нужно передавать. Нужно: увеличивать пропускную способность канала связи, либо увеличивать длительность передачи.

p, blockquote 60,0,0,0,0 —>

Компромиссы при использовании помехоустойчивых кодов

p, blockquote 61,0,0,0,0 —>

  1. Достоверность vs полоса пропускания.
  2. Мощность vs полоса пропускания.
  3. Скорость передачи данных vs полоса пропускания

Необходимость чередования (перемежения)

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

p, blockquote 63,0,0,0,0 —>

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

p, blockquote 64,0,0,0,0 —>

Пример блочного перемежения:

p, blockquote 65,0,0,0,0 —>

Пример блочного перемежения кодов

p, blockquote 66,0,0,0,0 —> p, blockquote 67,0,0,0,1 —>

На картинке, всего 5 блоков (с 1 по 25). Код работает исправляя ошибки в рамках одного блока (если в одном блоке 1 ошибка, код его исправит, а если две то нет). В канал связи отдается информация не последовательно, а в перемешку. На выходе кодера сформировались 5 блоков и эти 5 блоков будем отдавать не по очереди а в перемешку. Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам. За счет того, что мы перемешали большое количество блоков между собой, групповая ошибка равномерно распределится по блокам.

Код Хэмминга

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

Введение

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

Готовые работы на аналогичную тему

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

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

Исправление ошибок при помехоустойчивом кодировании

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

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

Кодовая скорость R, характеризующая долю полезных (несущих информацию) данных в сообщениях. Вычисляется по следующей формуле: $R = k / n = k / m+k$, где:

  • $n$ является числом символов кодового сообщения.
  • $m$ является числом символов, предназначенных для проверки.
  • $k$ число символов информации.

Величины $n$ и $k$ иногда приводятся совместно с именем кода, чтобы можно было его однозначно идентифицировать. К примеру, код Хэмминга (7, 4).

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

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

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

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

1 0 1 0 0 1 0 0 | 0

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

1 1 0 1 0 1 0 0 | 1

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

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

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

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

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

  • Двоичное кодирование. Используется битовая система.
  • Не двоичное кодирование. Используется преобразование исходных двоичных кодов в различные символы.

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

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

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

Код Хэмминга

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

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

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

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

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

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

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

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

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

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

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

Источники:

https://zvondozvon. ru/radiosvyaz/kody-hemminga

https://spravochnick. ru/informatika/kod_hemminga/

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

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