Коды хэмминга исправляющие единичную ошибку

Время на прочтение
4 мин

Количество просмотров 525K

• Coding theory
• Golay code
• Reed–Muller code
• Reed–Solomon error correction
• Turbo code
• Low-density parity-check code
• Hamming bound
• Hamming distance

1. ^ See Lemma 12 of
2. ^ Hamming (1950), pp. 153–154.
3. ^ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), Mathematical Association of America, pp. 16–17, ISBN 0-88385-023-0
4. ^ ^{a b c} Kythe & Kythe 2017, p. 115.
5. ^ Kythe & Kythe 2017, p. 95.
6. ^ ^{a b} Moon T. Error correction coding: Mathematical Methods and
   Algorithms. John Wiley and Sons, 2005.(Cap. 3) ISBN 978-0-471-64800-0

• Hamming, Richard Wesley (1950). «Error detecting and error correcting codes» (PDF). Bell System Technical Journal. 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. S2CID 61141773. Archived (PDF) from the original on 2022-10-09.
• Moon, Todd K. (2005). Error Correction Coding. New Jersey: John Wiley & Sons. ISBN 978-0-471-64800-0.
• MacKay, David J.C. (September 2003). Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press. ISBN 0-521-64298-1.
• D.K. Bhattacharryya, S. Nandi. «An efficient class of SEC-DED-AUED codes». 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN ’97). pp. 410–415. doi:10.1109/ISPAN.1997.645128.
• «Mathematical Challenge April 2013 Error-correcting codes» (PDF). swissQuant Group Leadership Team. April 2013. Archived (PDF) from the original on 2017-09-12.
• Kythe, Dave K.; Kythe, Prem K. (28 July 2017). «Extended Hamming Codes». Algebraic and Stochastic Coding Theory. CRC Press. pp. 95–116. ISBN 978-1-351-83245-8.

Содержание

Расстоянием Хэмминга между двумя векторами $ B=(b_1,\dots,b_n) $ и $ C=(c_1,\dots,c_n) $ из $ \mathbb V^n $ называется число разрядов, в которых эти слова отличаются друг от друга; будем обозначать его $ \rho(B,C) $.

?

Доказать, что

$$ \rho(B,C)= \displaystyle \sum_{j=1}^n \left[ (1-b_j)c_j+ (1-c_j)b_j \right] \, .$$

Весом Хэмминга вектора $ B=(b_1,\dots,b_n) $ называется число его отличных от нуля координат, будем обозначать его $ w(B) $. Таким образом¹⁾
$$ w(B)= b_1+\dots+b_n, \qquad \rho(B,C)=|b_1-c_1|+\dots+ |b_n-c_n|=w(B-C) \ . $$

Расстояние Хэмминга является метрикой в пространстве $ \mathbb V^n $, т.е. для любых векторов $ \{X_1,X_2,X_3\} \subset \mathbb V^n $ выполняются свойства

1.

$ \rho(X_1,X_2) \ge 0 $, и $ \rho(X_1,X_2) = 0 $ тогда и только тогда, когда $ X_1=X_2 $;

2.

$ \rho(X_1,X_2) = \rho(X_2,X_1) $;

3.

$ \rho(X_1,X_3)\le \rho(X_1,X_2)+ \rho(X_2,X_3) $ («неравенство треугольника»).

Пусть теперь во множестве $ \mathbb V^n $ выбирается произвольное подмножество $ \mathbb U $, содержащее $ s_{} $ векторов: $ \mathbb U=\{ U_1,\dots,U_s \} $. Будем считать эти векторы кодовыми словами, т.е. на вход канала связи будем подавать исключительно только эти векторы; само множество $ \mathbb U $ будем называть кодом. По прохождении канала связи эти векторы могут зашумляться ошибками. Каждый полученный на выходе вектор будем декодировать в ближайшее (в смысле расстояния Хэмминга) кодовое слово множества $ \mathbb U $. Таким образом, «хорошим» кодом — в смысле исправления максимального числа ошибок — может считаться код $ \mathbb U $, для которого кодовые слова далеко отстоят друг от друга. С другой стороны, количество кодовых слов $ s_{} $ должно быть достаточно велико, чтобы делать использование кода осмысленным; во всяком случае, будем всегда считать $ s>1 $.

Минимальное расстояние между различными кодовыми словами кода $ \mathbb U $, т.е.
$$ d=\min_{\{j,k\}\subset \{1,\dots,s \} \atop j\ne k} \rho (U_j,U_k) $$
называется кодовым расстоянием кода $ \mathbb U $; будем иногда также писать $ d(\mathbb U) $.

Т

Теорема. Код $ \mathbb U $ с кодовым расстоянием $ d_{} $

a) способен обнаружить от $ 1_{} $ до $ d-1 $ (но не более) ошибок;

б) способен исправить от $ 1_{} $ до $ \left\lfloor \displaystyle \frac{d-1}{2} \right\rfloor $ (но не более) ошибок. Здесь $ \lfloor \ \ \ \rfloor $ — целая часть числа.

Доказательство. Если $ U_1 $ — переданное кодовое слово, а $ V_{} $ — полученный на выходе с канала вектор с $ \tau_{} $ ошибками, то $ \rho(U_1,V)=\tau $. Мы не сможем обнаружить ошибку если $ V_{1} $ совпадет с каким-то другим кодовым словом $ U_2 $, т.е. при условии $ \rho(U_2,V)=0 $. Оценим
$ \rho(U_2,V) $ при условии, что $ \tau \le d-1 $. По неравенству треугольника

3

получаем
$$ \rho(U_2,V) \ge \rho(U_1,U_2)-\rho(U_1,V) \ge d-\tau \ge 1>0 \ . $$
Для доказательства части б) предположим, что $ 2\,\tau \le d-1 $. Тогда те же рассуждения приведут к заключению
$$ \rho(U_2,V) \ge d-\tau \ge (2\,\tau+1)-t > \tau = \rho(U_1,V) \ , $$
т.е. вектор $ V_{} $ ближе к $ U_1 $, чем к любому другому кодовому слову.

♦

П

Пример. Код Адамара строится на основании матрицы Адамара — квадратной матрицы, элементами которой являются только числа $ \{+1,-1\} $; при этом ее строки (как, впрочем, и столбцы) попарно ортогональны. Так, матрица Адамара порядка $ 8_{} $ —

$$
H=\left(
\begin{array}{rrrrrrrr}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
-1 & 1 &-1 & 1 & -1 & 1 &-1 & 1\\
1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\
-1 & 1 & 1 & -1 & -1 & 1 & 1 & -1 \\
1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\
-1 & 1 &-1 & 1 & 1 & -1 &1 & -1\\
1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\
-1 & 1 & 1 & -1 & 1 & -1 & -1 & 1
\end{array}
\right) \ .
$$
Код строится следующим образом. Берутся строки матрицы $ H_{} $ и умножаются на $ +1 $ и на $ -1 $; в каждой строке множества
$$ H^{[1]},H^{[2]},\dots,H^{[8]},-H^{[1]},-H^{[2]},\dots,-H^{[8]} $$
производится замена $ +1 \to 0, -1 \to 1 $. Получаются $ 16 $ векторов
$$
(00000000),\ (10101010),\ (00110011),\ (10011001),\ (00001111),\ (10100101),\ (00111100),\
(10010110),
$$
$$
(11111111),\ (01010101), (11001100),\ (01100110),\ (11110000),\ (01011010),\ (11000011),\
(01101001),
$$
которые обозначим $ U_1,\dots,U_8,U_{-1},\dots,U_{-8} $.
Поскольку строки $ \pm H^{[j]} $ и $ \pm H^{[k]} $ ортогональны при $ j\ne k_{} $ и состоят только из чисел $ \pm 1 $, то ровно в половине своих элементов они должны совпадать, а в половине — быть противоположными. Соответствующие им векторы $ U_{} $ будут совпадать в половине своих компонент и различаться в оставшихся. Таким образом
$$ \rho( U_{\pm j}, U_{\pm k}) = 4 \quad npu \quad j\ne k, \ \rho( U_{j}, U_{-j}) = 8 , $$
и кодовое расстояние равно $ 4_{} $. В соответствии с теоремой, этот код способен обнаружить до трех ошибок, но исправить только одну. Так, к примеру, если при передаче по каналу связи слова $ U_8=(00111100) $ возникает только одна ошибка и на выходе получаем $ V_8= (00111101) $, то $ \rho(U_8,V_8)=1 $, в то время как $ \rho(U_j,V_8)\ge 3 $ для других кодовых слов. Если же количество ошибок возрастет до двух —
$ \tilde V_8= (00111111) $, — то $ \rho(U_8,\tilde V_8)=2 $, но при этом также $ \rho(U_9,\tilde V_8)=2 $. Ошибка обнаружена, но однозначное декодирование невозможно.

♦

Т

Теорема. Если существует матрица Адамара порядка $ n_{}>2 $, то

а) $ n_{} $ кратно $ 4_{} $, и

б) существует код $ \mathbb U \subset \mathbb V^n $, состоящий из $ 2\,n $ кодовых слов, для которого кодовое расстояние $ d=n/2 $.

Проблема построения кодов Адамара заключается в том, что существование матриц Адамара произвольного порядка $ n_{} $ кратного $ 4_{} $ составляет содержание не доказанной²⁾ гипотезы Адамара. Хотя для многих частных случаев $ n_{} $ (например, для $ n=2^m, m \in \mathbb N $, см.

☞

ЗДЕСЬ ) матрицы Адамара построены.

Т

Теорема. Если код $ \mathbb U \subset \mathbb V^n $ может исправлять самое большее $ m_{} $ ошибок, то количество $ s_{} $ его слов должно удовлетворять следующему неравенству

$$ s \le \frac{2^n}{C_n^0+C_n^1+\dots+C_n^m} \ , $$
где $ C_n^{j} $ означает биномиальный коэффициент.

Число в правой части неравенства называется верхней границей Хэмминга для числа кодовых слов.

Доказательство. Для простоты предположим, что одно из кодовых слов кода $ \mathbb U $ совпадает с нулевым вектором: $ U_1=\mathbb O_{1\times n} $. Все векторы пространства $ \mathbb V_n $, отстоящие от $ U_1 $ на расстояние $ 1_{} $ заключаются во множестве
$$ (100\dots 0),\ (010 \dots 0),\ \dots,\ (000 \dots 1) ; $$
их как раз $ n=C_n^1 $ штук. Векторы из $ \mathbb V^n $, отстоящие от $ \mathbb O_{} $ на расстояние $ 2_{} $ получаются в ходе расстановки двух цифр $ 1_{} $ в произвольных местах нулевого вектора. Нахождение количества способов такой расстановки относится к задачам комбинаторики, и решение этой задачи можно найти

☞

ЗДЕСЬ. Оно равно как раз $ C_n^{2}=n(n-1)/2 $. Аналогичная задача расстановки $ j_{} $ единиц в $ n_{} $-векторе имеет решением число $ C_n^j $.
Таким образом общее количество векторов, отстоящих от $ \mathbb O_{} $ на расстояние $ \le m_{} $
равно $ C_n^1+\dots+C_n^m $.
Вместе в самим $ \mathbb O_{} $-вектором получаем как раз число из знаменателя границы Хэмминга.

Предыдущие рассуждения будут справедливы и для любого другого кодового слова из $ \mathbb U $ — каждое из них можно «окружить $ m_{} $-окрестностью» и каждая из этих окрестностей будет содержать
$$ 1+C_n^1+\dots+C_n^m $$
векторов из $ \mathbb V^n $. По предположению теоремы, эти окрестности не должны пересекаться. Но тогда общее количество векторов $ \mathbb V^n $, попавших в эти окрестности (для всех $ s_{} $ кодовых слов) не должно превышать количества векторов в $ \mathbb V^n $, т.е. $ 2^{n} $.

♦

?

Доказать, что если $ n_{} $ — нечетно, а $ m=\lfloor n/2 \rfloor=(n-1)/2 $ то верхняя граница Хэмминга равна в точности $ 2_{} $.

П

Пример. Для $ n=10 $ имеем

Чем больше ошибок хотим скорректировать (при фиксированном числе $ n_{} $ разрядов кодовых слов) — тем меньше множество кодовых слов.

Коды, для которых верхняя граница Хэмминга достигается, называются совершенными.

Идея, лежащая в основе этих кодов достаточно проста: это — обобщение понятия контрольной суммы. Если вектор $ (x_1,\dots,x_k) \in \mathbb V^k $ содержит информационные биты, которые требуется передать, то для контроля целостности при передаче их по каналу присоединим к этому вектору еще один «служебный» бит с вычисленным значением
$$ x_{k+1}=x_1+\dots+x_k \pmod{2} \ . $$
Очевидно, $ x_{k+1}=1 $ если среди информационных битов содержится нечетное число единиц, и $ x_{k+1}=0 $ в противном случае. Поэтому этот бит называют битом четности. Кодовым словом становится вектор
$$ X=(x_1,\dots,x_k,x_{k+1}) \in \mathbb V^{k+1} \ . $$
По прохождении его по каналу, для полученного вектора $ Y=(y_1,\dots,y_k,y_{k+1}) $ производится проверка условия
$$ y_{k+1} = y_1+\dots+y_k \pmod{2} \ . $$
Если оно не выполнено, то при передаче произошла ошибка. Если же сравнение оказывается справедливым, то это еще не значит, что ошибки при передаче нет — поскольку комбинация из двух (или любого четного числа) ошибок не изменит бита четности.

Для более вероятного обнаружения ошибки вычислим несколько контрольных сумм — выбирая различные разряды информационного вектора $ (x_1,\dots,x_k) $:
$$
\begin{array}{lclcll}
x_{k+1}&=&x_{i_1}+&\dots&+x_{i_s} \pmod{2}, \\
x_{k+2}&=&x_{j_1}+&\dots&+x_{j_t} \pmod{2}, \\
\vdots & & \vdots \\
x_n &=&x_{\ell_1}+& \dots & +x_{\ell_w} \pmod{2}.
\end{array}
$$
Полученные биты присоединим к информационному блоку. Кодовым словом будет вектор
$$ X=(x_1,\dots,x_k,x_{k+1},\dots,x_n) \in \mathbb V^n \ , $$
который и поступает в канал связи. По прохождении его по каналу, для соответствующих разрядов полученного вектора $ Y_{} $ проверяется выполнимость контрольных сравнений. Если все они выполняются, то ошибка передачи считается невыявленной.

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

П

Пример. Если вероятность ошибочной передачи одного бита по каналу равна $ P_1=0.1 $, то вероятность появления хотя бы одной ошибки при передаче $ k_{} $ битов равна $ P_k= 1-(0.9)^k $, т.е.

♦

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

Сначала формализуем предложенную выше идею. В пространстве $ \mathbb V^n $ выделим некоторое подпространство $ \mathbb V^n_{[k]} $, состоящее из векторов
$$ (x_1,\dots,x_k,x_{k+1},\dots,x_n) \ , $$
первые $ k_{} $ компонентов которых считаются произвольными, а оставшиеся $ n-k_{} $ полностью определяются первыми посредством заданных линейных соотношений:
$$ \begin{array}{lclcll}
x_{k+1}&=&h_{k+1,1}x_1+&\dots&+h_{k+1,k}x_k \pmod{2} \\
\vdots & & \vdots \\
x_n &=&h_{n1}x_1+& \dots & +h_{nk}x_k \pmod{2}
\end{array} \qquad npu \qquad \{h_{j\ell}\} \subset \{0,1\} \ .
$$
Кодовые слова выбираются именно из подпространства $ \mathbb V^n_{[k]} $, их количество равно $ \operatorname{Card} (\mathbb V^n_{[k]} )=2^k $. При этом начальная часть каждого кодового слова, т.е. вектор $ (x_1,\dots,x_k) $, заключает информацию, которую нужно передать — эти разряды называются информационными. Остальные разряды кодового слова, т.е. биты вектора $ (x_{k+1},\dots,x_n) $, которые вычисляются с помощью выписанных линейных соотношений, являются служебными — они называются проверочными и предназначены для контроля целостности передачи информационных разрядов по каналу связи (и/или коррекции ошибок). Код такого типа называется линейным (n,k)-кодом.

В дальнейшем будем экономить на обозначениях: знак операции $ +_{} $ будет означать суммирование по модулю $ 2_{} $.

П

Пример. Пусть $ n=5, k=3 $. Пусть проверочные биты связаны с информационными соотношениями

$$ x_4=x_1 + x_2,\ x_5=x_1 + x_3 \ . $$
Тогда $ \mathbb V^5_{[3]} $ состоит из векторов
$$ (00000),\ (10011),\ (01010),\ (00101),\ (11001),\ (10110),\ (01111),\ (11100) \ . $$

♦

Для описания пространства $ \mathbb V^n_{[k]} $ привлечем аппарат теории матриц. С одной стороны, в этом подпространстве можно выбрать базис — систему из $ k_{} $ линейно независимых векторов: обозначим их $ \{X_1,\dots,X_k\} $. Матрица, составленная из этих векторов-строк,
$$
\mathbf G=\left( \begin{array}{c} X_1 \\ \vdots \\ X_k \end{array} \right)_{k\times n}
$$
называется порождающей матрицей кода. Так, в только что приведенном примере в качестве порождающей матрицы может быть выбрана
$$
\mathbf G=
\left( \begin{array}{ccccc}
1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 &1
\end{array}
\right) \qquad \mbox{ или } \qquad
\mathbf G=
\left( \begin{array}{ccccc}
1 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0
\end{array}
\right) \ .
$$
Любая строка $ X_{} $ кода может быть получена как линейная комбинация строк порождающей матрицы:
$$ X=\alpha_1 X_1+\alpha_2X_2+\dots+\alpha_k X_k \quad npu \quad \{\alpha_1,\dots,\alpha_k\} \subset \{0,1\} . $$
Можно переписать это равенство с использованием операции матричного умножения:
$$ X=(\alpha_1,\dots,\alpha_k) \mathbf G \ . $$
Так, продолжая рассмотрение предыдущего примера:
$$
(x_1,x_2,x_3,x_4,x_5)=(x_1,x_2,x_3)
\left( \begin{array}{ccccc}
1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 &1
\end{array}
\right)=
$$
$$
=(x_1+x_2,x_2+x_3,x_3)
\left( \begin{array}{ccccc}
1 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0
\end{array}
\right) \pmod{2} \ .
$$
С другой стороны, для описания $ \mathbb V^n_{[k]} $ имеются проверочные соотношения. Объединяя их в систему линейных уравнений, перепишем их с использованием матричного формализма:
$$
(x_1,\dots,x_k,x_{k+1},\dots,x_n) \cdot
\left(\begin{array}{cccc}
h_{k+1,1} & h_{k+2,1} & \dots &h_{n1} \\
h_{k+1,2} & h_{k+2,2} & \dots & h_{n2} \\
\vdots & & & \vdots \\
h_{k+1,k} & h_{k+2,k} & \dots & h_{nk} \\
-1 & 0 & \dots & 0 \\
0 & -1 & \dots & 0 \\
\vdots & & \ddots & \vdots \\
0 & 0 & \dots & -1
\end{array}
\right)= (0,0,\dots,0)_{1\times (n-k)}
$$
или, в альтернативном виде, с использованием транспонирования⁴⁾:
$$
\underbrace{\left(\begin{array}{llclcccc}
h_{k+1,1} & h_{k+1,2} & \dots &h_{k+1,k} & 1 & 0 & \dots & 0 \\
h_{k+2,1} & h_{k+2,2} & \dots & h_{k+2,k}& 0 & 1 & \dots & 0 \\
\vdots & & & \vdots & \dots & & \ddots & \vdots \\
h_{n1} & h_{n2} & \dots & h_{nk} & 0 & 0 & \dots & 1 \\
\end{array}
\right)}_{\mathbf H}\left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right)
=\left( \begin{array}{c} 0 \\ 0 \\ \vdots \\ 0 \end{array} \right)_{(n-k)\times 1}
$$
Матрица $ \mathbf H_{} $ порядка $ (n-k)\times n $ называется проверочной матрицей кода⁵⁾. Хотя вторая форма записи (когда вектор-столбец неизвестных стоит справа от матрицы) более привычна для линейной алгебры, в теории кодирования чаще используется именно первая — с вектором-строкой $ X_{} $ слева от матрицы:
$$ X\cdot \mathbf H^{\top} = \mathbb O_{1\times k} \ . $$
Для приведенного выше примера проверочные соотношения переписываются в виде
$$ x_1 + x_2 +x_4=0,\ x_1 + x_3 + x_5=0 \ $$
и, следовательно, проверочная матрица:
$$ \mathbf H=
\left( \begin{array}{ccccc}
1 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 1
\end{array}
\right) \ .
$$

Т

Теорема 1. Имеет место матричное равенство

$$ \mathbf G \cdot \mathbf H^{\top} = \mathbb O_{k\times (n-k)} \ .$$

Доказательство. Каждая строка матрицы $ \mathbf G $ — это кодовое слово $ X_{j} $ , которое, по предположению, должно удовлетворять проверочным соотношениям $ X_j \cdot \mathbf H^{\top} = \mathbb O_{1\times k} $. Равенство из теоремы — это объединение всех таких соотношений в матричной форме. Фактически, порождающая матрица $ \mathbf G $ состоит из строк, составляющих фундаментальную систему решений системы уравнений $ X \mathbf H^{\top}= \mathbb O $.

♦

=>

Если проверочная матрица имеет вид $ \mathbf H=\left[ P^{\top} \mid E_{n-k} \right] $,
где $ E_{n-k} $ — единичная матрица порядка $ n — k_{} $, $ P_{} $ — некоторая матрица порядка $ k \times (n-k) $, а $ \mid_{} $ означает операцию конкатенации, то порождающая матрица может быть выбрана в виде $ \mathbf G = \left[ E_k \mid P \right] $.

Доказательство следует из предыдущей теоремы, правила умножения блочных матриц —
$$ \mathbf G \cdot \mathbf H^{\top} = E_k \cdot P + P \cdot E_{n-k} = 2P \equiv \mathbb O_{k\times (n-k)} \pmod{2} \ , $$
и того факта, что строки матрицы $ \mathbf G $ линейно независимы. Последнее обстоятельство обеспечивается структурой этой матрицы: первые $ k_{} $ ее столбцов являются столбцами единичной матрицы. Любая комбинация
$$ \alpha_1 \mathbf G^{[1]}+\dots+\alpha_k \mathbf G^{[k]} $$
строк матрицы дает строку $ (\alpha_1,\dots,\alpha_k,\dots ) $ и для обращения ее в нулевую необходимо, чтобы $ \alpha_1=0,\dots,\alpha_k=0 $.

♦

Видим, что по структуре матрицы $ \mathbf G $ и $ \mathbf H $ очень похожи друг на друга. Задав одну из них, однозначно определяем другую. В одном из следующих пунктов, мы воспользуемся этим обстоятельством — для целей исправления ошибок оказывается выгоднее сначала задавать $ \mathbf H $.

Т

Теорема 2. Кодовое расстояние линейного подпространства $ \mathbb V^{n}_{[k]} $ равно минимальному весу его ненулевых кодовых слов:

$$ d( \mathbb V^{n}_{[k]})= \min_{ U \in \mathbb V^{n}_{[k]} \atop U \ne \mathbb O } w(U) \ . $$

Доказательство. Линейное подпространство замкнуто относительно операции сложения (вычитания) векторов. Поэтому если $ \{U_1,U_2\}\subset \mathbb V^{n}_{[k]} $, то и $ U_1-U_2 \in \mathbb V^{n}_{[k]} $, а также $ \mathbb O \in V^{n}_{[k]} $. Тогда
$$ \rho(U_1,U_2)=\rho(U_1-U_2, \mathbb O)= w(U_1-U_2) \ . $$

♦

Кодовое расстояние дает третью характеристику линейного кода — теперь он описывается набором чисел $ (n,k,d) $.

Т

Теорема 3. Пусть $ d_{} $ означает кодовое расстояние кода $ \mathbb V^{n}_{[k]} $ с проверочной матрицей $ \mathbf H $. Тогда любое подмножество из $ \ell_{} $ столбцов этой матрицы будет линейно независимо при $ \ell < d $. Обратно, если любое подмножество из $ \ell_{} $ столбцов матрицы $ \mathbf H $ линейно независимо, то $ d > \ell $.

Доказательство. Если $ d_{} $ — кодовое расстояние, то, в соответствии с теоремой 2, ни одно ненулевое кодовое слово $ X\in \mathbb V^{n}_{[k]} $ не должно иметь вес, меньший $ d_{} $. Если предположить,
что столбцы $ \{\mathbf H_{[i_1]},\dots,\mathbf H_{[i_{\ell}]}\} $ линейно зависимы при $ \ell< d $, то
существуют числа $ x_{i_1},\dots,x_{i_{\ell}} $ не все равные нулю, такие что
$$ x_{i_1}\mathbf H_{[i_1]}+\dots+x_{i_{\ell}} H_{[i_{\ell}]} = \mathbb O \ . $$
Придавая всем остальным переменным $ \{x_1,\dots,x_n\} \setminus \{ x_{i_1},\dots,x_{i_{\ell}} \} $ нулевые значения, получаем вектор $ X_{} \in \mathbb V^n $, удовлетворяющий равенству
$$ x_1 \mathbf H_{[1]}+\dots + x_n \mathbf H_{[n]} = \mathbb O \ , $$
и вес этого вектора $ \le \ell< d $. Но тогда этот вектор принадлежит и $ \mathbb V^{n}_{[k]} $ поскольку $ \mathbf H X^{\top} = \mathbb O $.
Это противоречит предположению о весе кодовых слов. Следовательно любые $ \ell_{} $ столбцов матрицы $ \mathbf H $ линейно независимы если $ \ell < d $.

Обратно, пусть любые $ \ell_{} $ столбцов матрицы $ \mathbf H $ линейно независимы, но существует кодовое слово $ X_{}=(x_1,\dots,x_n) \ne \mathbb O $ веса $ \le \ell $. Пусть, для определенности, $ x_{\ell+1}=0,\dots, x_{n}=0 $. Тогда
$$ x_1 \mathbf H_{[1]}+\dots + x_{\ell} \mathbf H_{[\ell]}= \mathbb O $$
при хотя бы одном из чисел $ \{x_j\}_{j=1}^{\ell} $ равном $ 1_{} $. Но это означает, что столбцы
$ \mathbf H_{[1]},\dots, \mathbf H_{[\ell]} $ линейно зависимы, что противоречит предположению.

♦

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

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

Если $ X\in \mathbb V^{n}_{[k]} $ — кодовое слово, а $ Y\in \mathbb V^n $ — вектор, получившийся по прохождении этого слова по каналу, то $ Y-X $ называется вектором ошибок. Понятно, что при $ w(Y-X)=0 $ ошибки при передаче нет.

Предположим, что $ w(Y-X)=1 $, т.е. что при передаче произошла ошибка ровно в одном разряде кодового слова $ X_{} $. Попробуем ее обнаружить исходя из предположения, что кодовое слово выбиралось во множестве $ \mathbb V^{n}_{[k]} $ линейного $ (n,k) $-кода, определенного в предыдущем пункте при какой-то проверочной матрице $ \mathbf H $. Если для полученного вектора $ Y_{} $ выполняются все проверочные условия:
$$ Y \cdot \mathbf H^{\top} = \mathbb O_{1\times k} \ , $$
(или, что то же $ Y \in \mathbb V^{n}_{[k]} $), то ошибка передачи считается не выявленной.

Для произвольного вектора $ Y \in \mathbb V^{n} $ вектор-строка
$$ S=Y \cdot \mathbf H^{\top} \in \mathbb V^{k} $$
называется синдромом вектора Y. C точки зрения линейной алгебры его можно интерпретировать как показатель отхода вектора $ Y_{} $ от гиперплоскости, заданной системой однородных уравнений $ X\cdot \mathbf H^{\top}=\mathbb O $.

Если синдром $ S_{} $ ненулевой: $ Y \cdot \mathbf H^{\top} \ne \mathbb O_{1\times k} $,
то полученный вектор $ Y_{} $ не принадлежит множеству $ \mathbb V^{n}_{[k]} $ допустимых кодовых слов. Факт ошибки подтвержден. Изначально мы предположили, что произошла только одна ошибка, т.е.
$$ Y-X= {\mathfrak e}_j = \big(\underbrace{0,\dots,0,1}_{j},0,\dots,0\big) $$
при некотором $ j\in \{1,\dots n\} $. Тогда
$$ S= Y \cdot \mathbf H^{\top} = (X+{\mathfrak e}_j) \cdot \mathbf H^{\top}=X\cdot \mathbf H^{\top}+
{\mathfrak e}_j \cdot \mathbf H^{\top}=
$$
$$
=\mathbb O_{1\times k} + \mathbf H_{[j]}^{\top} = \mathbf H_{[j]}^{\top}
$$
при $ \mathbf H_{[j]} $ означающем $ j_{} $-й столбец проверочной матрицы $ \mathbf H $. Таким образом получили соответствие
$$ {}_{} \mathbf{HOMEP} \mbox{ поврежденного бита} \mathbf{=HOMEP} \mbox{ столбца проверочной матрицы.} $$
И, следовательно, мы получили возможность обнаружить место повреждения — по факту совпадения синдрома со столбцом проверочной матрицы. К сожалению, реальность оказывается более сложной…

П

Пример. В примере предыдущего пункта проверочная матрица была выбрана в виде

$$ \mathbf H=
\left( \begin{array}{ccccc}
1 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 1
\end{array}
\right) \ .
$$
Если при передаче кодового слова $ (10011) $ произошла ошибка в первом бите, т.е. $ Y=(00011) $, то синдром
$$ S=Y \cdot \mathbf H^{\top} = (11) $$
однозначно укажет на номер столбца матрицы $ \mathbf H $. Если же ошибка произошла в четвертом бите, т.е. $ Y=(10001) $, то
$$ S=(10) \ , $$
но таких⁶⁾ столбцов в матрице $ \mathbf H $ два!

♦

Вывод. Для однозначного обнаружения места ошибки⁷⁾ достаточно, чтобы все столбцы матрицы $ \mathbf H $ были различными.

Столбцами этой матрицы являются транспонированные строки пространства $ \mathbb V^{n-k} $.

Итак, исходя из соображений, завершающих предыдущий пункт, будем строить код, исправляющий одну ошибку, беря за стартовую точку именно матрицу $ \mathbf H $. Выбираем ее произвольного порядка $ M\times N $ при $ \{M,N\} \in \mathbb N, M<N $ и вида
$$ \mathbf H_{M\times N} = \left[ \tilde P \mid E_M \right] \ , $$
где матрица $ E_M $ — единичная порядка $ M_{} $, а матрица $ \tilde P $ имеет порядок $ M\times (N-M) $, и столбцы ее должны быть различными, ненулевыми и отличаться от столбцов матрицы $ E_M $. По этой проверочной матрице — в соответствии со следствием к теореме $ 1 $ из

☞

ПУНКТА — строим порождающую матрицу:
$$ \mathbf G_{(N-M)\times N} = \left[ E_{N-M} \mid \tilde P^{\top} \right] \ . $$
Строки матрицы $ \mathbf G $ могут быть взяты в качестве базисных векторов подпространства кодовых слов.

П

Пример. Пусть $ M=2 $. Здесь имеем единственный вариант:

$$ \mathbf H_{2\times 3} = \left( \begin{array}{c|cc} 1 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right) \ , $$
поскольку в $ \mathbb V^2 $ имеется лишь одна ненулевая строка, отличная от $ (10) $ и $ (01) $. Таким образом $ N=3 $ и
$$ \mathbf G_{1\times 3}=( 1\, 1\, 1 ) \ . $$
Следовательно, подпространство кодовых слов в $ \mathbb V^3 $ является одномерным, и имеем всего два возможных кодовых слова: $ (000) $ и $ (111) $.

Пусть $ M=3 $. В $ \mathbb V^3 $ имеется уже большой выбор строк, отличных от $ (100), (010), (001) $. Так, можно взять
$$
\mathbf H_{3\times 4} = \left( \begin{array}{c|ccc} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{array} \right) \quad \mbox{ или } \quad
\mathbf H_{3\times 5} = \left( \begin{array}{cc|ccc} 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{array} \right)
$$
$$
\mbox{ или } \quad
\mathbf H_{3\times 6} =
\left( \begin{array}{ccc|ccc} 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) \quad \mbox{ или } \quad
\mathbf H_{3\times 7} =
\left( \begin{array}{cccc|ccc} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) \ .
$$
Соответственно,
$$ \mathbf G= (1\, 1\, 1\, 1) \quad \quad \mbox{ или } \quad
\mathbf G=
\left( \begin{array}{cc|ccc} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{array} \right)
\quad
$$
$$
\mbox{ или } \quad
\mathbf G=
\left( \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right)
\quad \quad \mbox{ или } \quad
\mathbf G=
\left( \begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1
\end{array} \right) \ .
$$
Кодовых векторов в соответствующих кодах будет $ 2^1,2^2,2^3,2^4 $. Любой из них способен исправить одну ошибку, полученную в ходе передачи.

♦

Если поставить задачу максимизации числа кодовых слов, то матрицу $ \mathbf H $ следует выбирать самой широкой, т.е. делать $ N_{} $ максимально возможным. При фиксированном $ M_{} $ это достигается при выборе $ N=2^M-1 $. Тогда соответствующий линейный $ (n,k) $-код имеет значения параметров $ n=2^M-1,k=2^M-M-1 $, и именно он обычно и выбирается в качестве кода Хэмминга.

Найдем величину его кодового расстояния $ d_{} $. В соответствии с теоремой $ 3 $ из

☞

ПУНКТА, $ d>\ell $, если любое подмножество из $ \ell_{} $ столбцов матрицы $ \mathbf H $ линейно независимо. Поскольку столбцы проверочной матрицы кода Хэмминга все различны, то любая пара из них линейно независима (свойство

3

☞

ЗДЕСЬ ). Следовательно, $ d>2 $. По теореме из

☞

ПУНКТА, получаем —

Если при передаче произошла ровно одна ошибка, то код Хэмминга способен ее исправить; если при передаче произошло ровно две ошибки, то код Хэмминга достоверно устанавливает лишь факт наличия ошибки.

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

П

Пример. Для проверочной матрицы $ (7,4) $-кода Хэмминга

$$
\mathbf H_{3\times 7} =
\left( \begin{array}{ccccccc} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right)
$$
вектор $ X=(0011110) $ является кодовым. Если при передаче произошла лишь одна ошибка и на выходе канала получили вектор $ Y=(1011110) $, то синдром этого вектора $ S=Y \mathbf H^{\top}=(111) $. Поскольку $ S^{\top} $ совпадает с первым столбцом матрицы $ \mathbf H $, то заключаем, что ошибка произошла в первом разряде. Тут же исправляем его на противоположный: $ X=Y+\mathfrak e_1 $.

Если при передаче произошло две ошибки и на выходе канала получили вектор $ \tilde Y=(1011010) $, то синдром этого вектора $ S=\tilde Y \mathbf H^{\top}=(011) $. Поскольку синдром ненулевой, то факт наличия ошибки подтвержден. Однако корректно исправить ее — по аналогии с предыдущим — не удается. $ S^{\top} $ совпадает с третьим столбцом матрицы $ \mathbf H $, но в третьем разряде полученного вектора ошибки нет.

Наконец, если при передаче произошли три ошибки и на выходе канала получили вектор $ \widehat Y=(1011011) $, то синдром этого вектора $ S=\widehat Y \mathbf H^{\top}=(010) $. Наличие ошибки подтверждено, исправление невозможно. Если же — при передаче того же вектора $ X=(0011110) $ — получаем вектор
$ \widehat Y_1=(1111111) $ (также с тремя ошибками), то его синдром оказывается нулевым: $ \widehat Y_1 \mathbf H^{\top}=(000) $ и ошибка не обнаруживается.

♦

Проблема сравнения синдрома полученного вектора $ Y_{} $ со столбцами проверочной матрицы $ \mathbf H $ с целью определения места ошибки — не такая тривиальная, особенно для больших $ n_{} $. Для упрощения этой процедуры воспользуемся следующим простым соображением. Размещение проверочных разрядов в конце кодового слова обусловлено лишь соображениями удобства изложения учебного материала. С точки зрения практической реализации, $ n-k $ проверочных разрядов можно разместить в любых местах кодового слова $ X_{} $ и даже «вразбивку», т.е. не подряд. Перестановке разрядов в кодовом слове будет соответствовать перестановка столбцов в матрице $ \mathbf H $, при этом само множество столбцов остается неизменным — это транспонированные строки пространства $ \mathbb V^{n-k} $ (ненулевые и различные). Рассмотрим $ (n,k) $-код Хэмминга при $ n=2^M-1,k=2^M-M-1, M \ge 2 $. Тогда каждую ненулевую строку пространства $ \mathbb V^{n-k}= \mathbb V^M $ можно интерпретировать как двоичное представление числа из множества
$ \{1,2,3,\dots,2^M-1\} $. Пусть
$$ j=\underline{{\mathfrak b}_1{\mathfrak b}_2 \dots {\mathfrak b}_{M-1} {\mathfrak b}_{M}}=
{\mathfrak b}_1 \times 2^{M-1}+{\mathfrak b}_2 \times 2^{M-2}+\dots+{\mathfrak b}_{M-1} \times 2+ {\mathfrak b}_{M} \quad npu \quad \{ {\mathfrak b}_j\}_{j=1}^M\subset \{0,1\} \quad — $$
— двоичное представление числа $ j_{} $. Переупорядочим столбцы проверочной матрицы $ \mathbf H $ так, чтобы
$$ \mathbf H_{[j]}=\left[ {\mathfrak b}_1{\mathfrak b}_2 \dots {\mathfrak b}_{M-1} {\mathfrak b}_{M}\right]^{\top} \ , $$
т.е. чтобы $ j_{} $-й столбец содержал двоичное представление числа $ j_{} $. При таком упорядочении,
синдром произвольного вектора $ Y_{} $, отличающегося от кодового слова $ X_{} $ в единственном разряде, является двоичным представлением номера этого разряда:
$$ {\bf \mbox{СИНДРОМ }} \ (Y)=\mathbf{HOMEP} \ (\mbox{ошибочный разряд}) \ . $$

Осталось теперь выяснить какие разряды кодового слова содержат проверочные биты.

П

Пример. Для $ (7,4) $-кода Хэмминга матрицу $ \mathbf H $, построенную в предыдущем примере, переупорядочим по столбцам; будем рассматривать ее в виде

$$
\begin{array}{c}
\left( \begin{array}{ccccccc}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1
\end{array} \right) \\
\begin{array}{ccccccc}
\uparrow & \uparrow & \uparrow & \uparrow & \uparrow & \uparrow & \uparrow \\
\scriptstyle 1 & \scriptstyle 2 & \scriptstyle 3 & \scriptstyle 4 & \scriptstyle 5 & \scriptstyle 6 & \scriptstyle 7
\end{array}
\end{array}
$$
Распишем проверочные соотношения $ X\mathbf H^{\top}=\mathbb O $ покомпонентно:
$$
\left\{
\begin{array}{ccccccc}
& & & x_4&+x_5&+x_6&+x_7=0 \\
&x_2&+x_3& & & +x_6&+x_7=0 \\
x_1& & +x_3& & +x_5 & & +x_7=0
\end{array} \right. \quad \iff
$$
$$
\iff \quad
\left\{
\begin{array}{ccccccc}
x_1& & +x_3& & +x_5 & & +x_7=0 \\
&x_2&+x_3& & & +x_6&+x_7=0 \\
& & & x_4&+x_5&+x_6&+x_7=0
\end{array} \right.
$$
Переписанные в последнем виде, эти уравнения представляют конечный пункт прямого хода метода Гаусса решения системы линейных уравнений, а именно — трапециевидную форму этой системы. Если бы мы поставили задачу поиска общего решения этой (однородной) системы и нахождения фундаментальной системы решений, то в качестве зависимых переменных однозначно бы выбрали $ x_1, x_2, x_4 $. Выпишем это общее решение :
$$
x_1=x_3+x_5+x_7,\ x_2=x_3+x_6+x_7,\ x_4=x_5+x_6+x_7 \ .
$$
Это и есть проверочные соотношения, а проверочными разрядами кодового вектора являются $ 1_{} $-й, $ 2_{} $-й и $ 4_{} $-й.

Проверим правильность этих рассуждений. Придадим оставшимся разрядам произвольные значения, например:
$ x_3=1,x_5=1,x_6=0,x_7=1 $. Тогда $ x_1=1, x_2=0,x_4=0 $ и кодовый вектор $ X=(1010101) $. Пусть на выходе из канала он превратился в $ Y=(1000101) $. Синдром этого вектора $ Y\mathbf H^{\top}=(011) $ — это двоичное представление числа $ 3_{} $. И ведь действительно: ошибка — в третьем разряде!

♦

Алгоритм построения (n,k)-кода Хэмминга

для $ n=2^M-1,k=2^M-M-1, M \ge 2 $.

1.

Строится матрица $ \mathbf H $ порядка $ M \times (2^M-1) $ из столбцов, представляющих двоичные представления чисел $ \{1,2,3,\dots,2^M-1\} $ (младшие разряды — внизу).

2.

Проверочные разряды имеют номера, равные степеням двойки: $ 1,2,2^2,\dots,2^{M-1} $.

3.

Проверочные соотношения получаются из матричного представления $ X\mathbf H^{\top}=\mathbb O $ выражением проверочных разрядов через информационные.

Можно немного улучшить код Хэмминга, увеличив кодовое расстояние до $ 4_{} $.

?

Является ли $ 8_{} $-мибитный код Адамара из примера

☞

ПУНКТА линейным кодом?

.

[1]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.

[2]. Марков А.А. Введение в теорию кодирования. М.Наука. 1982