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

Обновлено: 07.07.2024

Они позволяют не только обнаруживать ошибки, но и исправлять их.

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

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

Так как допускается искажение какого-либо одного информационного или контрольного разряда или отсутствие искажения, то общее количество возможных ситуаций равно: m+k+1, где m – количество информационных разрядов.

Учитывая, что с помощью k двоичных разрядов можно закодировать 2 k состояний, можно получить неравенство:

Например, если m=4, то из этого неравенства находим, k=3 ( так как 2 3 >=4+3+1).

Практически можно получить следующие значения:

Расположение контрольных разрядов в коде Хемминга определяется соображениями удобства построения опознавателя. Поэтому они располагаются последовательно справа налево в позициях, номера которых являются степенями двойки. Информационные разряды кода занимают оставшиеся свободные позиции. Таким образом, общая структура кода при m=4 имеет вид:

7 6 5 4=2 2 3 2=2 1 1=2 0

a₄

a₃

a₂

k₃

a₀

k₂

k₁

Для того, чтобы определить какие позиции кода контролируются каждым из контрольных разрядов, строится вспомогательная таблица (табл.16), строки которой представляют собой двоичные номера последовательности от 1 до (m+k).

Номер строки	k₃	k₂	k₁
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

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

k₁ контролирует четность 3, 5 и 7-го разрядов кода;

k₂ контролирует четность 3, 6 и 7-го разрядов кода;

k₃ контролирует четность 5, 6 и 7-го разрядов кода.

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

В качестве опознавателя используется k-разрядное слово (r₃ r₂ r₁). Его

Разряды определяются по формулам:

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

Число 13 переводится в двоичную систему счисления: 13₁₀ = 1101₂

Число двоичных информационных разрядов m=4. Количество контрольных

разрядов k=3 ( было определено ранее).

Для получения полной структуры кода, значения информационных

разрядов подставляются в соответствующие позиции. Общая структура кода

Значения информационных и контрольных разрядов подставляются в

структуру кода. В результате получается искомый код Хемминга.

7 6 5 4=2 2 3 2=2 1 1=2 0

Предполагаем, что в результате сбоя при передаче исказился третий

pазряд кода и его единичное значение изменилось на противоположное

(нулевое). В результате получен код: 1 1 0 0 0 1 0.

Исходя из нового ошибочного значения кода, вычисляется значение

Опознаватель r₃ r₂ r₁=011₂=3₁₀, то есть ошибка произошла в третьем разряде.

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

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

1)a=111111, m=6
2)a=010100,m=6
3)a=111110,m=6
4)a-011110,m=6
5)a=100001,m=6

Заранее спасибо, с наступающем Вас!

Кодирование и проверка кода Хэмминга
суть в чем, кодирование и проверка кода хэмминга-нужно изобразить на ассемблере, как это сделать?

Как реализовать кодирование кода Хэмминга?
Подскажите пожалуйста как реализовать кодирование кода Хэмминга на C++?

Кодирование Хэмминга
Здравствуйте! Подскажите, пожалуйста, что это значит в кодере Хэмминга (с&(1<<i))>>i c -.

Кодирование Хэмминга
Сори за тупой вопрос Как закодировать текст данным методом? Сам принцип работы понятен (тот что с.

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

задан 24 Дек '14 1:19

Было бы полезно уточнить параметры кода.

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

Открытый ключ - это ключ известный всем. Закрытый ключ - это ключ, известный только его автору или узкой группе лиц.

Понятия открытого и закрытого ключа - общие понятия, не связанные с кодом Хэмминга.

Для каких целей нужно такое кодирование?

вопрос непонятен: какое такое кодирование? кодирование с закрытым ключом или код Хэмминга? Зачем нужен код Хэмминга можно узнать в Вики (ошибки отлавливать и корректировать). Кодирование с открытым и закрытым ключом ярко проявляется в системе RSA - тоже см. Вики.

@Роман83: коды Хэмминга, по сути дела, не содержат "ключей". Идея в том, что если мы знаем, что на L передаваемых бит возможно не более одной ошибки, то мы, пересылая k бит, формируем код из L=k+m бит, что позволило бы нам откорректировать искажённый бит в случае ошибки. Для этого необходимо, чтобы m дополнительных бит могли различать L+1 ситуацию, то есть $%2^m\ge L+1$%. Конструкция кода Хэмминга показывает, что этого условия достаточно. В принципе, это всё лучше посмотреть в каком-нибудь учебнике типа Яблонского: в Вики бывает много слишком общей, а потому посторонней информации.

1 ответ

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

Из условия очевидно, что нам необходим код с размерностью не менее 6, в идеале должна быть равна 6.

Двоичный код Хэмминга

Если полагать, что кодируем двоичным кодом Хэмминга, то для размерности $%k$% такого кода верно $%k=2^m-1-m$% для любых целых $%m>1$%. Выбирая наименьшее $%k$% такое, что $%k\geq6$%, получим код Хэмминга размерности $%11$% и длины $%15$% при $%m=4$%. Таким образом, для кодирования нам потребуется расширить информационный блок с имеющихся $%6$% символов до $%11$%.

Условие 1. Вариант хитрый, подходит только для $%a=(111111)$%.

Если дополнить блок $%a$% пятью единицами слева, то мы получим информационный блок длины $%11$%, состоящий только из единиц. Тогда для кодирования такого блока можно применить следующую хитрость:

Код Хэмминга — линейный, следовательно, он имеет нулевое кодовое слово.
Двоичный код Хэмминга — совершенный, следовательно, он обладает свойством антиподальности, то есть вместе с произвольным кодовым словом $%x$% имеет также кодовое слово $%x+\mathbf^n$%, где $%\mathbf^n$% — вектор длины $%n$%, состоящий из единиц.
Таким образом, код Хэмминга имеет единичное кодовое слово, которое, очевидно, соответствует единичному информационному блоку.

В итоге, слово $%a=(111111)$% мы кодируем кодовым словом из $%15$% единиц: $%(111111111111111)$%.

Условие 2. Вариант честный.

Поскольку код Хэмминга не определен, то определим его сами, составив проверочную матрицу размера $%4\times15$% из всех ненулевых двоичных столбцов длины $%m=4$%: $$H=\left(\begin 0&0&0&0&1&1&1&1&1&1&1&1&0&0&0\\ 0&1&1&1&0&0&0&1&1&1&1&0&1&0&0\\ 1&0&1&1&0&1&1&0&0&1&1&0&0&1&0\\ 1&1&0&1&1&0&1&0&1&0&1&0&0&0&1 \end\right).$$

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

Теорема о связи между проверочной и порождающей матрицами линейного кода. Если проверочная матрица линейного кода в каноническом виде имеет вид $$H=(A_|E_),$$ то порождающая матрица данного кода имеет вид: $$G=(E_k|-A_^\top).$$ Верно и обратное.

Таким образом, с помощью приведенной теоремы получаем порождающую матрицу размера $%11\times15$%: $$G=\left(\begin 1&0&0&0&0&0&0&0&0&0&0&0&0&1&1\\ 0&1&0&0&0&0&0&0&0&0&0&0&1&0&1\\ 0&0&1&0&0&0&0&0&0&0&0&0&1&1&0\\ 0&0&0&1&0&0&0&0&0&0&0&0&1&1&1\\ 0&0&0&0&1&0&0&0&0&0&0&1&0&0&1\\ 0&0&0&0&0&1&0&0&0&0&0&1&0&1&0\\ 0&0&0&0&0&0&1&0&0&0&0&1&0&1&1\\ 0&0&0&0&0&0&0&1&0&0&0&1&1&0&0\\ 0&0&0&0&0&0&0&0&1&0&0&1&1&0&1\\ 0&0&0&0&0&0&0&0&0&1&0&1&1&1&0\\ 0&0&0&0&0&0&0&0&0&0&1&1&1&1&1 \end\right).$$ Далее дополняем, например, единицами слева вектор $%a=(010100)$% до информационного блока $%a'=(11111010100)$% и осуществляем кодирование: $$a'\cdot G=(111110101001000).$$

Недвоичный код Хэмминга

Если не ограничиваться двоичными кодами Хэмминга, то можно заметить, что существует $%q$%-значный код Хэмминга с $%2$%-я проверочными символами длины $%n=q+1$% такой, что его размерность $%k=q-1$% как раз равна $%6$%. Очевидно, что $%q=7$%. Таким образом, семизначный или семеричный код Хэмминга длины $%8$% в некотором смысле является оптимальным для данного условия задачи с точки зрения возможности передачи в одном кодовом слове целого вектора $%a$% и наибольшей наибольшей плотности ошибок для канала связи, но не более, чем одна на $%8$% символов.

Условие 3. Семизначный код Хэмминга.

Действуем аналогично предыдущему варианту. Выбираем проверочную матрицу размера $%2\times8$% в каноническом виде. Для этого нам потребуются все попарно линейно независимые семизначные столбцы длины $%2$%: $$H=\left(\begin 1&1&1&1&1&1&1&0\\ 1&2&3&4&5&6&0&1 \end\right).$$ С помощью теоремы о связи между проверочной и порождающей матрицами линейного кода строим порождающую матрицу размера $%6\times8$%: $$G=\left(\begin 1&0&0&0&0&0&6&6\\ 0&1&0&0&0&0&6&5\\ 0&0&1&0&0&0&6&4\\ 0&0&0&1&0&0&6&3\\ 0&0&0&0&1&0&6&2\\ 0&0&0&0&0&1&6&1 \end\right).$$

Далее осуществляем кодирование информационного блока $%a=(111110)$%: $$a\cdot G=(11111026).$$

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

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

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

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

Подготовка

Было:

Стало:

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

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

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

Заключение.

Примечание.

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

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 пакета информации.

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

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

p, blockquote 17,0,0,0,0 -->

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

p, blockquote 18,0,0,0,0 -->

p, blockquote 19,0,0,0,0 -->

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

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 -->

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 -->

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 — с этими не двоичными символами работают не двоичные помехоустойчивые коды.

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

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

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 -->

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 -->

Достоверность vs полоса пропускания.
Мощность vs полоса пропускания.
Скорость передачи данных 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 блоков будем отдавать не по очереди а в перемешку. Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам. За счет того, что мы перемешали большое количество блоков между собой, групповая ошибка равномерно распределится по блокам.

Читайте также: