для чего нужен синдром в коде хэмминга

12. Декодирование по синдрому и еще раз о коде Хемминга

Слово «синдром» означает обычно совокупность признаков, характерных для того или иного явления. Такой же примерно смысл имеет понятие «синдром» и в теории кодирования. Синдром вектора, содержащего, быть может, ошибки, дает возможность распознать наиболее вероятный характер этих ошибок. Правда, определение, которое мы приводим ниже, не сразу позволяет это увидеть. Синдромом вектора и называется вектор s(u), определяемый равенством:

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

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

На языке теории групп это означает, что U есть смежный класс по подгруппе V (пространство L_n и его кодовое подпространство V можно рассматривать соответственно как группу и ее подгруппу относительно операции сложения векторов).

Сказанное позволяет сделать следующие выводы:

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

2. Вектор ошибки e для вектора u нужно искать в силу равенства (2) в том же смежном классе, которому принадлежит и сам вектор u.

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

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

1. Вычисляем синдром s(u) принятого вектора u.

2. По синдрому s(u) = s_i определяем из таблицы лидер e_i соответствующего смежного класса.

3. Определяем посланный кодовый вектор υ как разность

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

Алгоритм исправления одиночных ошибок в этом случае удивительно прост. Если вектор и содержит ошибочный символ в i-й позиции, то синдром s(u) этого вектора совпадает с i-м столбцом проверочной матрицы. Таким образом, этот синдром, читаемый как двоичное число, и есть номер ошибочного символа.

Например, из приведенной выше проверочной матрицы для (15,11)-кода Хемминга получается следующая проверочная матрица для расширенного (16,11)-кода:

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

Во втором случае считаем, что допущены две или любое большее четное число ошибок, если s(u) ≠ 0. Если же s(u) = 0, то, как обычно, полагаем, что ошибок при передаче не было.

Источник

Код Хэмминга. Пример работы алгоритма

Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:

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

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

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

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

Как это работает.

Для того, чтобы понять работу данного алгоритма, рассмотрим пример.

Подготовка

Допустим, у нас есть сообщение «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.

На этом этапе стоит определиться с, так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать. Допустим, у нас длина слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:

и

После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно, у нас получилось 5 контрольных бит (выделены красным цветом):

Было:

Стало:

Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».

Вычисление контрольных бит.

Теперь необходимо вычислить значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит (как неожиданно), но не от всех, а только от тех, которые этот контрольных бит контролирует. Для того, чтобы понять, за какие биты отвечает каждых контрольный бит необходимо понять очень простую закономерность: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N. Не очень понятно, но по картинке, думаю, станет яснее:

Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Ясно, что чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.

Но как же вычислить значение каждого контрольного бита? Делается это очень просто: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу. Вот и всё! Можно конечно и наоборот, если число чётное, то ставим единицу, в противном случае, ставим 0. Главное, чтобы в «кодирующей» и «декодирующей» частях алгоритм был одинаков. (Мы будем применять первый вариант).
Высчитав контрольные биты для нашего информационного слова получаем следующее:

и для второй части:

Вот и всё! Первая часть алгоритма завершена.

Декодирование и исправление ошибок.

Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):

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

Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Теперь просто сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию ошибочного бита. Теперь просто инвертировав его и отбросив контрольные биты, мы получим исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со второй частью сообщения.

Заключение.

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

Примечание.

На написание этого топика меня подвигло то, что в поиске я не нашёл на Хабре статей на эту тему (чему я был крайне удивлён). Поэтому я решил отчасти исправить эту ситуацию и максимально подробно показать как этот алгоритм работает. Я намеренно не приводил ни одной формулы, дабы попытаться своими словами донести процесс работы алгоритма на примере.

Источник

15. Особенности и принцип построения кода Хэмминга. Обнаружение и исправление ошибок кодом Хэмминга. Синдром линейного кода.

К кодам Хэмминга обычно относятся коды с =3, исправляющие все одиночные ошибки и коды с=4, исправляющие все одиночные и обнаруживающие все двойные ошибки. Для исправления всех одиночных ошибок число синдромов должно бытьn+1 ( n – число разрядов ). Из них n синдромов используются для указания местоположения ошибки, а один – нулевой, соответствует их отсутствию. Следовательно, .n=m+k, где m –информационные разряды, к –проверочные.

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

Сгруппируем в первую сумму все элементы, номера которых имеют значение «1» в 1-м младшем разряде двоичного числа. Во вторую сумму сгруппируем элементы, номера которых имеют значение «1» во втором разряде двоичного числа и т.д. для третьей и четвертой сумм.

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

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

Порядок кодирования кодом Хэмминга в устройстве защиты от ошибок передатчика:

1. от источника принимается 5-ти элементная кодовая комбинация и ее разряды записываются в отведенных для них местах 3,5,6,7 и 9.

2. Суммированием по модулю 2 определяются проверочные разряды. Их значения должны быть такими, чтобы сумма, в которую входит данный проверочный разряд, равнялась «0». Другими словами, каждый проверочный разряд должен дополнить свою сумму до четного количества единиц.

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

4. Сформированная таким образом кодовая комбинация передается в канал.

Рассмотрим пример: Источник выдает информационные элементы

Тогда полная кодовая комбинация, которая будет передаваться в канал, имеет вид:

Порядок декодирования на приеме в устройстве защиты от ошибок.

1. Подсчитываем 4 суммы в каждую из которых входят информационные разряды и по одному проверочному.

2. Производится анализ полученных сумм, при этом возможны три случая:

а) проверочное число, состоящее из результатов суммирований равно 0000, что свидетельствует об отсутствии ошибок.

б) проверочное число отличается от значения 0000, причем по его значению можно определить номер ошибочного разряда.

в) проверочное число отличается от значения 0000, но определить место ошибки невозможно.

3. В зависимости от результатов анализа:

а) информация выдается потребителю;

б) ошибки исправляются и информация выдается потребителю;

в) принятая комбинация стирается и в устройстве защиты от ошибок вырабатывается сигнал «ошибка».

Все «0», значит комбинация принята верно.

Допустим что произошло искажение в третьем элементе и вместо 1 принят 0. Тогда принятая комбинация имеет вид:

В данном случае синдром равен 0011, что соответствует ошибке в 3 элементе кодовой комбинации. Для устранения данной ошибки необходимо изменить находящийся в этом элементе символ на обратный.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый параметр, скорость кода 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 это вычисление бита чётности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник