Раздел разработан в 2010 г. при поддержке компании ((http://www.raidixstorage.com/ru/ RAIDIX))
Для понимания материалов настоящего раздела крайне желательно ознакомиться с разделом ((:codes#блочные_коды КОДИРОВАНИЕ))
.
==Код Хэмминга==
~~TOC~~
Будем рассматривать двоичные коды, т.е. упорядоченные наборы (строки) $ (x_1,\dots,x_{n}) $ из $ n_{} $ чисел $ \{x_1,\dots,x_n\}\subset \{0,1\} $. Множество таких наборов, рассматриваемое вместе с операцией умножения на константы $ 0_{} $ или $ 1_{} $ и операцией поразрядного сложения по модулю $ 2_{} $:
$$ (x_1,\dots,x_n)\oplus (y_1,\dots,y_n)=(x_1\oplus y_1 ,\dots,x_n\oplus y_n ) =
$$
$$ = (x_1+y_1 \pmod{2},\dots,x_n+y_n \pmod{2}) $$
образует ((:linear_space:gf2 линейное пространство)), которое мы будем обозначать $ \mathbb V^n $, а собственно составляющие его наборы будем называть векторами; причем, для определенности, именно векторами-строками. Это пространство состоит из конечного числа векторов: $ \operatorname{Card} (\mathbb V^n)=2^n $.
===Расстояние Хэмминга==
**Расстоянием Хэмминга** между двумя векторами $ 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) $. Таким образом[[В двух последующих формулах суммирование производится "честно" --- т.е. как суммирование обычных целых чисел, а не по модулю $ 2_{} $.]]
$$ 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 R_{}^{n} $ ((http://en.wikipedia.org/wiki/Taxicab_geometry манхеттенскую метрику (такси-метрику))).
Пусть теперь во множестве $ \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 $ --- //((:algebra2:notations#целая_часть_числа целая часть числа))//.
**Доказательство.** Если $ 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 $, чем к любому другому кодовому слову.
♦
!!П!! **Пример.** Код Адамара строится на основании ((:algebra2#ортогональная матрицы Адамара)) --- квадратной матрицы, элементами которой являются только числа $ \{+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_{} $ составляет содержание __не доказанной__[[По состоянию на 2018 г.]] **гипотезы Адамара**. Хотя для многих частных случаев $ n_{} $ (например, для $ n=2^m, m \in \mathbb N $, см.
☞
((:algebra2#ортогональная ЗДЕСЬ)) ) матрицы Адамара построены.
!!Т!! **Теорема.** //Если код// $ \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} $ //означает ((:binomial#бином биномиальный коэффициент))//.
Число в правой части неравенства называется **верхней границей Хэмминга** для числа кодовых слов.
**Доказательство.** Для простоты предположим, что одно из кодовых слов кода $ \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_{} $ в произвольных местах нулевого вектора. Нахождение количества способов такой расстановки относится к задачам комбинаторики, и решение этой задачи можно найти
☞
((:basics:combinatorics#сочетания ЗДЕСЬ)). Оно равно как раз $ 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 $ имеем
| $ m_{} $ ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^
| $ s\le $ | 93 | 18 | 5 | 2 | 1 |
Чем больше ошибок хотим скорректировать (при фиксированном числе $ 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 $, т.е.
^ $ k $ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
^ $ P_k $ | 0.1 | 0.19 | 0.271 | 0.344 | 0.410 | 0.469 | 0.522 | 0.570 | 0.613 | 0.651 |
♦
Обычно, количество проверочных соотношений берется меньшим (и даже много меньшим) количества информационных битов[[Но для дальнейшего изложения этот факт несуществен.]]. Осталось только понять как составлять эти проверочные соотношения так, чтобы они смогли реагировать на ошибки передачи по каналу связи.
Сначала формализуем предложенную выше идею. В пространстве $ \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\} . $$
Можно переписать это равенство с использованием операции ((:algebra2#умножение_матриц матричного умножения)):
$$ 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]} $ имеются проверочные соотношения. Объединяя их в систему линейных уравнений, перепишем их с использованием ((:algebra2:linearsystems#матричная_форма_записи матричного формализма)):
$$
(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)}
$$
или, в альтернативном виде, с использованием ((:algebra2#транспонирование транспонирования))[[А также с учетом $ -1 \equiv 1 \pmod{2} $.]]:
$$
\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 $ называется **проверочной матрицей кода**[[Parity-check matrix.]]. Хотя вторая форма записи (когда вектор-столбец неизвестных стоит справа от матрицы) более привычна для линейной алгебры, в теории кодирования чаще используется именно первая --- с вектором-строкой $ 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 $ состоит из строк, составляющих ((:algebra2:linearsystems#система_однородных_уравнений фундаментальную систему решений)) системы уравнений $ X \mathbf H^{\top}= \mathbb O $.
♦
!!=>!! Если проверочная матрица имеет вид $ \mathbf H=\left[ P^{\top} \mid E_{n-k} \right] $,
где $ E_{n-k} $ --- ((:algebra2#единичная единичная матрица)) порядка $ n - k_{} $, $ P_{} $ --- некоторая матрица порядка $ k \times (n-k) $, а $ \mid_{} $ означает операцию ((:algebra2#конкатенация конкатенации)), то порождающая матрица может быть выбрана в виде $ \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_{} $ от ((:algebra2:linearsystems#геометрическая_интерпретация гиперплоскости)), заданной системой однородных уравнений $ X\cdot \mathbf H^{\top}=\mathbb O $.
{{ codes:code_subsp.jpg |}}
Если синдром $ 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) \ , $$
но таких[[C учетом транспонирования!]] столбцов в матрице $ \mathbf H $ __два__!
♦
**Вывод.** Для однозначного обнаружения места ошибки[[В случае ее единственности!]] достаточно, чтобы все столбцы матрицы $ \mathbf H $ были различными.
Столбцами этой матрицы являются транспонированные строки пространства $ \mathbb V^{n-k} $.
===Построение кода==
Итак, исходя из соображений, завершающих предыдущий пункт, будем строить код, исправляющий одну ошибку, беря за стартовую точку именно матрицу $ \mathbf H $. Выбираем ее произвольного порядка $ M\times N $ при $ \{M,N\} \in \mathbb N, M
☞