Будем рассматривать двоичные коды, т.е. упорядоченные наборы (строки) $ (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}) $$ образует линейное пространство, которое мы будем обозначать $ \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) $. Таким образом¹⁾ $$ 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 $ имеем

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

Идея, лежащая в основе этих кодов достаточно проста: это — обобщение понятия контрольной суммы. Если вектор $ (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)-кодом.

Пример. Пусть $ 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 $. ♦

Теорема 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 $ выражением проверочных разрядов через информационные.

Является ли $ 8_{} $-мибитный код Адамара из примера ☞ ПУНКТА линейным кодом?

.

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

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