УказательРазделыОбозначенияАвторО проекте


. Настоящий раздел поддерживается компанией


§

Для понимания материалов полезно предварительно ознакомиться с разделом КОДИРОВАНИЕ

Код Хэмминга

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

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} манхеттенскую метрику (такси-метрику).

Пусть теперь во множестве \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_{} составляет содержание не доказанной2) гипотезы Адамара. Хотя для многих частных случаев 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 имеем

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

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

Сначала формализуем предложенную выше идею. В пространстве \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 или \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 k}

или, в альтернативном виде, с использованием транспонирования4):

\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)_{k\times 1}

Матрица \mathbf H_{} порядка (n-k)\times n называется проверочной матрицей кода5). Хотя вторая форма записи (когда вектор-столбец неизвестных стоит справа от матрицы) более привычна для линейной алгебры, в теории кодирования чаще используется именно первая — с вектором-строкой 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} поврежденного бита\mathbf{=HOMEP} столбца проверочной матрицы.

И, следовательно, мы получили возможность обнаружить место повреждения — по факту совпадения синдрома со столбцом проверочной матрицы. К сожалению, реальность оказывается более сложной…:-/

П

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

\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) \ ,

но таких6) столбцов в матрице \mathbf H два!

Вывод. Для однозначного обнаружения места ошибки7) достаточно, чтобы все столбцы матрицы \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 или \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) \quad или \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 или
\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 или \quad \mathbf G= \left( \begin{array}{cc|ccc} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{array} \right) \quad \quad или \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 или
\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_{} в единственном разряде, является двоичным представлением номера этого разряда:

\mathbf{CUHDPOM} \ (Y)=\mathbf{HOMEP} \ (ошибочный разряд) \ .

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

П

Пример. Для (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 \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. Выпишем это общее решение8):

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]. Акритас А. Основы компьютерной алгебры с приложениями. М. Мир. 1994

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

1) В двух последующих формулах суммирование производится «честно» — т.е. как суммирование обычных целых чисел, а не по модулю 2_{}.
2) По состоянию на 2014 г.
3) Но для дальнейшего изложения этот факт несуществен.
4) А также с учетом -1 \equiv 1 \pmod{2}.
5) Parity-check matrix.
6) C учетом транспонирования!
7) В случае ее единственности!
8) С учетом -1 \equiv 1 \pmod{2}.

2017/03/07 16:27 редактировал au