Код Хэмминга с арифметическим порядком столбцов

[Without Name]

Есть разновидность кодов Хэмминга, когда при кодировании и вычислении синдрома используется не систематическая матрица, а матрица, полученная таким способом, когда в ее столбцы по порядку записываются двоичные представления чисел от 1 до $n$. Тогда процедура декодирования становится очень простой: синдром равен номеру бита, в котором произошла ошибка, и чтобы исправить ошибку, достаточно инвертировать этот бит.

Я хочу разобраться в этом способе кодирования и декодирования. Читаю книгу, отрывки из которого прикладываю ниже. Здесь мутная фраза "при вычислении проверочных символов проверяются номера столбцов, и те столбцы, номера которых не являются степенью 2, сопоставляются информационным позициям слова. Соответствующие информационные символы включатся в процесс вычисления проверок". Я здесь ничего не понял и к тому же в книге нет примера к этой теме. Как "проверяются номера столбцов", как "столбцы сопоставляются информационным позициям слова"? Выглядит как наукообразная каша, формально как будто правильная, но без смысла. Очень плохое объяснение. Можете растолковать мне, каким образом работает в целом такой алгоритм кодирования?

Вот теория из книги:

[Without Name]

Как вообще выполняется кодирование при помощи ПРОВЕРОЧНОЙ матрицы $H$?

[svv]

Сначала отвечу на последний вопрос.

Without Name в сообщении #1586990 писал(а):

Как вообще выполняется кодирование при помощи ПРОВЕРОЧНОЙ матрицы $H$?

Перед формулой (1.18) говорится, что кодирование с помощью проверочной матрицы выполняется с помощью уравнения (1.12) $\mathbf v\mathbf H^\top=\mathbf 0$.

Кодовое слово $\mathbf v$ длины $n$ состоит из информационной части $\mathbf u$ длины $k$ (совпадает с исходным сообщением) и проверочной части $\mathbf v_p$ длины $n-k$.
Матрица $\mathbf H^\top$ состоит из двух блоков (формула (1.16) с учётом транспонирования). Верхний блок — это матрица $\mathbf P$ размера $k\times(n-k)$. Нижний блок — единичная матрица $\mathbf I$ порядка $n-k$.

Тогда уравнение (1.12) даёт
$\mathbf v\mathbf H^\top=\mathbf u\mathbf P+\mathbf v_p\mathbf I=\mathbf u\mathbf P+\mathbf v_p=\mathbf 0$
Поскольку в поле $\mathrm{GF}(2)$ сложение и вычитание совпадают,
$\mathbf v_p=\mathbf u\mathbf P$
По этой формуле и вычисляются проверочные символы.

Например, пусть (стр. 51, пример 14)
$\mathbf H=\begin{bmatrix}{\color{blue}1101}100\\{\color{blue}1011}010\\{\color{blue}0111}001\end{bmatrix}$,
тогда
$\mathbf P=\begin{bmatrix}110\\101\\011\\111\end{bmatrix}$
— это транспонированная выделенная часть матрицы $\mathbf H$.
Если элементы $\mathbf u$ и $\mathbf v$ нумеровать с единицы, то $v_j=u_j (j=1,2,3,4)$ и
$\begin{bmatrix}v_5&v_6&v_7\end{bmatrix}=\begin{bmatrix}u_1&u_2&u_3&u_4\end{bmatrix}\begin{bmatrix}110\\101\\011\\111\end{bmatrix}$
То есть
$v_5=u_1+u_2+u_4$
$v_6=u_1+u_3+u_4$
$v_7=u_2+u_3+u_4$

Подтвердите, что всё понятно, тогда расскажу про кодирование с помощью $\mathbf H^*$.

[Without Name]

Да, с этим все понятно, спасибо. Я вчера тоже вывел даже формулы для проверочных символов из той матрицы:

$v = (u, v_p)$

$v_p = uP = (u_0 + u_1 + u_3, u_0 + u_2 + u_3, u_1 + u_2 + u_3)$

А как кодировать при помощи $H^*$?

[svv]

В матрице $\mathbf H$ (и $\mathbf H^*$ тоже) $n=2^m-1$ столбцов. Каждый столбец можно рассматривать как двоичную запись некоторого целого числа от $1$ до $n$ (считая, что самый младший разряд числа записан в верхней строке, а самый старший в нижней). Причём каждое число встречается ровно один раз. Соответственно, столбцы не повторяются и нет нулевого.

В кодовом слове из $n$ символов $m$ проверочных и $k=2^m-1-m$ информационных. Обратите внимание на совпадение: среди целых чисел от $1$ до $n=2^m-1$ ровно $m$ являются степенью двойки: $1=2^0, 2=2^1, 4=2^2, ..., 2^{m-1}$ (а $2^m$ уже не входит в диапазон). И ровно $k=n-m=2^m-1-m$ не являются степенью двойки: $3,5,6,7,9,...$. Столбцы, в которых «записана» степень двойки, легко узнать: в них ровно одна единица, остальные элементы нули. Можно сказать более определённо: столбцы матрицы $\mathbf H$, в которых записана степень двойки, соответствуют проверочным символам кодового слова (при декодировании), а остальные — информационным. Например, здесь «проверочные» столбцы выделены малиновым, информационные — чёрные:
$\mathbf H=\begin{bmatrix}1101{\color{magenta}100}\\1011{\color{magenta}010}\\0111{\color{magenta}001}\end{bmatrix}$
$.\quad\quad\;\;\, 3567{\color{magenta}124}$
Потому что если трактовать столбцы, как целые числа, это будут слева направо числа $3,5,6,7,{\color{magenta}1,2,4}$. Также заметьте, что не-степени-двойки строго возрастают, и степени-двойки строго возрастают, но сначала идут не-степени, потом степени. И этим столбцам соответствуют символы кодового слова $v_1,v_2,v_3,v_4,v_5,v_6,v_7$ (в данном случае удобнее нумерация с единицы).

Идея в том, чтобы переставить столбцы проверочной матрицы так, чтобы соответствующие столбцам числа от $1$ до $n$ шли по возрастанию:
$\mathbf H^*=\begin{bmatrix}{\color{magenta}1}{\color{magenta}0}1{\color{magenta}0}101\\{\color{magenta}0}{\color{magenta}1}1{\color{magenta}0}011\\{\color{magenta}0}{\color{magenta}0}0{\color{magenta}1}111\end{bmatrix}$
$.\quad\quad\quad\,{\color{magenta}1}{\color{magenta}2}3{\color{magenta}4}567$
Тогда изменится и кодирование:
информационные символы:
$v_3=u_1$
$v_5=u_2$
$v_6=u_3$
$v_7=u_4$
проверочные символы:
$v_1=v_3+v_5+v_7=u_1+u_2+u_4$
$v_2=v_3+v_6+v_7=u_1+u_3+u_4$
$v_4=v_5+v_6+v_7=u_2+u_3+u_4$
Зато декодирование будет очень простым.

[Without Name]

Спасибо большое за такое подробное объяснение! Я понял почти все, кроме одного: почему столбцы матрицы $\mathbf H$, в которых записана степень двойки, соответствуют проверочным символам кодового слова?
Есть книга, где это описывается?

[svv]

Хэмминг вычислил, что если у нас есть кодовое слово $\mathbf v$ длиной $n=2^m-1$, и от кода требуется гарантированное исправление одной ошибки, то из $n$ символов кодового слова необходимо назначить проверочными по крайней мере $m$ символов. Потому что принятое слово $\mathbf r=\mathbf v+\mathbf e$ должно нести информацию не только о переданном сообщении, но и о месте ошибки ($n$ вариантов), либо о том, что ошибки нет ($1$ вариант), всего $n+1=2^m$ вариантов, а это $m$ символов. Но как выбрать их позиции в кодовом слове (ещё на этапе разработке кодера/декодера)?

Допустим, мы кодируем с помощью матрицы $\mathbf H$ из примера 14. Предположим, что мы решили символы $v_4,v_5,v_6,v_7$ назначить информационными (то есть на этапе кодирования они известны), а символы $v_1,v_2,v_3$ сделать проверочными (их надо найти из информационных). Распишем матричное уравнение $\mathbf v\mathbf H^\top=\mathbf 0$:
${\color{magenta}v_1+v_2}+v_4+v_5=0$
${\color{magenta}v_1+v_3}+v_4+v_6=0$
${\color{magenta}v_2+v_3}+v_4+v_7=0$
Смотрите, как плохо получается: ни одну из неизвестных $v_1,v_2,v_3$ нельзя найти из уравнений непосредственно, потому что в каждое уравнение входит ещё по крайней мере одна неизвестная.

Зато, если считать проверочными $v_5,v_6,v_7$, их можно вычислить из уравнений непосредственно:
$v_1+v_2+v_4+{\color{magenta}v_5}=0$
$v_1+v_3+v_4+{\color{magenta}v_6}=0$
$v_2+v_3+v_4+{\color{magenta}v_7}=0$
На матричном языке причина очевидна: в этом хорошем случае проверочные символы — те, которые соответствуют столбцам единичной матрицы $\mathbf I$, которая легко обращается:
$\begin{bmatrix}\mathbf P^\top&\mathbf I_{m}\end{bmatrix}\begin{bmatrix}\mathbf u\\\mathbf v_p\end{bmatrix}=\begin{bmatrix}\mathbf 0\end{bmatrix}$
А в каждом столбце $\mathbf I$ ровно одна единица (хотя в данном случае простота разрешимости системы — следствие того, что в каждой строке $\mathbf I$ ровно одна единица). Что и даёт степень двойки при «двоичной» трактовке $\mathbf H$.

[Without Name]

Попробую что-нибудь закодировать. Возьму сообщение $u = (u_1, u_2, u_3, u_4) = (0101)$. Отображение кодирования выглядит так:
$(u_1, u_2, u_3, u_4)\mapsto (u_1 + u_2 + u_4, u_1 + u_3 + u_4, u_1, u_2 + u_3 + u_4, u_2, u_3, u_4)$

$0101 \mapsto 0100101$

Теперь декодирование. Отображение синдрома: $(c_1 c_2 c_3 c_4 c_5 c_6 c_7) \mapsto (c_1 + c_3 + c_5 + c_7, c_2 + c_3 + c_6 + c_7, c_4 + c_5 + c_6 + c_7)$. Вычисляем: внесем ошибку в первый левый разряд, $1100101$, синдром равен $(1+0+1+1, 1+0+0+1, 0+1+0+1) = (100) = 4$. По замыслу ошибка должна быть в 4 разряде, т.к. синдром равен 4, но это не так - ошибка в старшем разряде. Я где-то ошибся?

[svv]

svv в сообщении #1587235 писал(а):

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

Получается
$1\cdot 2^0+0\cdot 2^1+0\cdot 2^2=1$

[Without Name]

А, спасибо большое, теперь понял

[svv]

На странице 52 автор пишет:

Цитата:

Программа hamming.c на домашней странице ECC реализует именно этот вариант кодирования и декодирования двоичных кодов Хемминга.

Я проверил, страничка жива, программу легко найти. Может в чём-то помочь.