Кодирование с помощью кода Хэмминга

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

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

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

изменен 24 Дек '14 18:50

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

(24 Дек '14 1:28) falcao

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

(20 Мар '16 17:03) Роман83

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

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

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

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

(20 Мар '16 19:06) Trumba

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

(20 Мар '16 21:46) falcao
10|600 символов нужно символов осталось
0

@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{1}^n$%, где $%\mathbf{1}^n$% — вектор длины $%n$%, состоящий из единиц.
  • Таким образом, код Хэмминга имеет единичное кодовое слово, которое, очевидно, соответствует единичному информационному блоку.

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

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

Поскольку код Хэмминга не определен, то определим его сами, составив проверочную матрицу размера $%4\times15$% из всех ненулевых двоичных столбцов длины $%m=4$%: $$H=\left(\begin{array}{ccccccccccc|cccc} 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{array}\right).$$

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

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

Таким образом, с помощью приведенной теоремы получаем порождающую матрицу размера $%11\times15$%: $$G=\left(\begin{array}{ccccccccccc|cccc} 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{array}\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{array}{cccccc|cc} 1&1&1&1&1&1&1&0\\ 1&2&3&4&5&6&0&1 \end{array}\right).$$ С помощью теоремы о связи между проверочной и порождающей матрицами линейного кода строим порождающую матрицу размера $%6\times8$%: $$G=\left(\begin{array}{cccccc|cc} 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{array}\right).$$

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

ссылка

отвечен 16 Июл 18:05

изменен 16 Июл 18:14

@PerfectCode: там с параметрами какая-то путаница, по-моему. Через m обычно обозначают число вспомогательных бит. Здесь же в условии это то, что обычно обозначается через k. Причём эта информация лишняя, так как все сообщения из условия уже 6-битные. Всё это сбивает с толку, не говоря о том, что не указано, на какие места полагается помещать вспомогательные символы. В разных реализациях это может быть сделано по-разному. Поэтому от авторов вопросов уместно требовать или полное и точное описание, или ссылки на читаемый им курс.

(16 Июл 23:53) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,535
×40

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

показан
407 раз

обновлен
16 Июл 23:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru