Практические помехоустойчивые коды

Практически все блочные коды “достаточно хорошие”
Практически все требуют построения таблиц экспоненциального от длины блока размера
Сложно
В основном рассматриваются коды, которые можно построить за полиномиальное – желательно, линейное – время

Шенноновский предел на практике не достигается
Существуют “достаточно хорошие” практически применимые коды.

Будем выделять категории “качества” кодов:

Очень хорошие коды: дают произвольно малую вероятность ошибки при скорости передачи вплоть до \(C\).
Хорошие коды: дают произвольно малую вероятность ошибки при любой скорости передачи менее максимальной, которая может не достигать \(C\)
Плохие коды: не могут обеспечить произвольно малую вероятность ошибки, либо могут при нулевой скорости передачи.

Отдельно выделим

Практические коды: Коды с полиномиальной сложностью кодирования/декодирования.

Большинство известных кодов являются линейными блочным кодами. Напомним,

\((N, K)\) блочный код: Множество \(2^K\) кодовых слов длины \(N\), кодирующих некий источник с алфавитом мощности \(2^K\).

\((N, K)\) блочный линейный код: Блочный код, в котором кодовые слова \(\brace{\mathbf x^{(s)}}\) образуют \(K\)-мерное линейное векторное пространство, являющееся подпространством \(\mathcal A_X^N\) всех возможных кодовых слов длины \(N\)

\((N, K)\) блочный линейный код: Блочный код, в котором кодовые слова \(\brace{\mathbf x^{(s)}}\) образуют \(K\)-мерное линейное векторное пространство, являющееся подпространством \(\mathcal A_X^N\) всех возможных кодовых слов длины \(N\)

линейная операция над любыми двумя разрешёнными кодовыми словами даёт разрешённое кодовое слово.

Магма: Множество \(M\) и бинарная операция \(\bullet: M\times M \to M\) называются вместе магмой, если \(\forall a, b \in M: a\bullet b \in M\), т.е. \(M\) замкнуто относительно \(\bullet\).
Полугруппа: Магма, \((S, \bullet)\), такая, что \(\forall a, b, c \in S: (a\bullet b)\bullet c = a\bullet (b\bullet c),\) т.е. операция \(\bullet\) ассоциативна.
Моноид: Полугруппа \((S, \bullet)\), такая, что \(\exists e \in S: \forall a \in S: a\bullet e = e \bullet a = a\), т.е. существует элемент, нейтральный относительно \(\bullet\).

Группа: Моноид \((G, \bullet)\): \(\forall a \in G, \exists b \in G: a\bullet b = b\bullet a = e\), т.е. для каждого элемента существует обратный ему относительно \(\bullet\).
Абелева группа (Коммутативная группа): Группа, в которой бинарная операция коммутативна, т.е. \(\forall a, b \in G: a\bullet b = b\bullet a\).

Кольцо

Множество \(R\) и две бинарных операции \(+\) и \(\cdot\) называются вместе кольцом, если:

\((R, +)\) является абелевой группой
\((R, \cdot)\) является моноидом
Операция \(\cdot\) дистрибутивна по отношению к \(+\), т.е. \(\forall a,b,c \in R:\) \(a\cdot(b+c) = a\cdot b + a\cdot c,\) \((b+c)\cdot a = b\cdot a + c\cdot a.\)

Поле

Кольцо \((R, +, \cdot)\), в котором операция \((R\setminus\brace{e}, \cdot)\) образует абелеву группу, где \(e\) – нейтральный элемент операции \(+\).

Поле Галуа (конечное поле): Поле \(GF = (F, +, \cdot),\) где \(F\) – конечное множество.

Нетривиальное поле, очевидно, не может содержать менее двух элементов.

Векторное пространство над полем \(F\)

Поле \((F, +_F, \cdot_F)\), множество \(V\) и операции \(+: V\times V\to V,\) \(\cdot: F\times V \to V,\) такие, что:

\((V, +)\) образуют абелеву группу
\(\forall a,b \in F, v\in V: a\cdot(b\cdot v) = (a\cdot_F b) \cdot v\)
\(\forall v \in V: u\cdot v = v\), где \(u\in F\) – нейтральный элемент относительно \(\cdot_F\).
\(\forall a\in F, u,v \in V: a\cdot (u+v) = a\cdot u + a\cdot v\)
\(\forall a, b\in F, v \in V: (a+_F b)\cdot v = a\cdot v + b\cdot v\)

построение кода можно описать в терминах линейной алгебры
кодирование – порождающая матрица \(K\times N\) \(\mathbf G\): \(\forall \mathbf m\) – сообщения, кодированный сигнал \(\mathbf c = \mathbf G^\T \mathbf m\).
Множество всех кодовых слов \(C = \brace{\mathbf c | \mathbf H \mathbf c = 0},\) \(0\) – нейтральный элемент операции \(+\), \(\mathbf H\) – проверочная матрица \((N-K)\times N\).
\(\mathbf H \mathbf G^\mathrm T = \mathbf 0\), \(\mathbf 0\) – нулевая матрица.

Синдром: \(\mathbf s = \mathbf H \mathbf r\), \(\mathbf r\) – сингал; \(\forall \mathbf c \in C: \mathbf H \mathbf c = 0\)

\(\mathbf s = \mathbf H \mathbf r = \mathbf H \mathbf c + \mathbf H \mathbf e = \mathbf H \mathbf e\), где \(\mathbf r\) – сингал, \(\mathbf c\) – разрешённое кодовое слово и \(\mathbf e\) – ошибка.
Синдромом однозначно соответствует вектору ошибки, если по крайней мере \(q^{N-K} \ge \sum_{j=0}^t C_N^j (q-1)^j\), где \(t\) – максимальная кратность ошибки. Совпадает с границей Хэмминга.

\(\mathbb F_q^N\) – линейное \(N\)-мерное пространство над полем Галуа мощности \(q\).
Линейный код \(\mathcal C \subset \mathbb F_q^N\) представим минимальным базисом \(K \le N\) векторов.
Векторы базиса образуют строки \(\mathbf G\).
Если \(\mathbf G = \brack{\mathbf I_K | \mathbf P},\) где \(I_K\) – единичная \(K\times K\), \(P\) – матрица \(K \times (N-K)\), то \(\mathbf G\) в стандартной форме.
Если \(\mathbf G = \brack{\mathbf I_K | \mathbf P},\) то \(\mathbf H = \brack{-\mathbf P^{\mathrm T} | \mathbf I_{N-K}}\)

\(\forall \mathbf c_0, \mathbf c \in \mathcal C:\) \(c-c_0 \in \mathcal C\) (линейность)
\(d_H(c_0, c) = d_H(c-c_0, 0)\)
\(\underset{c\neq c_0}\min d_H(c_0, c) = \underset{c\neq c_0}\min d_H(c-c_0, 0) = \underset{c\neq 0}\min d_H(c, 0).\)
В силу линейности, расстояние Хэмминга между соседними кодовыми словами одинаково

Эквивалентные коды: коды, порождающие матрицы которых отличаются только перестановкой столбцов и элементарными линейными операциями над строками.; отличаются только порядком и положением символов в кодовых словах.

В менее общих терминах, обычно – двоичный алфавит, \(q=2\)
\(\mathbb F_2\) – двоичное поле Галуа
\(+_{\mathbb F_2}\) – сложение \(\mod 2\)
\(\cdot_{\mathbb F_2}\) – умножение
В \(\mathbb F_2^N\), операции – поэлементные

Коды Хэмминга

Один из наиболее широко известных линейных кодов.

Классическая конструкция:

биты нумеруются слева направо
биты в позициях \(\forall i: n=2^i\) – проверочные, остальные – информационные.
\(c_i = \sum_{j\in J_i} c_j \mod 2,\) \(J_i = \brace{j | j \& i \neq 0}\), где \(\&\) – побитовая конъюнкция

число проверочных бит \(r = \ceil{\log_2 (n+1)}\) – исправляют одну ошибку
обычно наоборот, из числа проверочных – число информационных \(2^r - 1 = n\), \(k = n-r = 2^r - 1 - r\).

Проверочная матрица \(r \times n\) \(H\), столбцы различны и не равны нулю;
Т.к. \(n = 2^r - 1\), столбцы – все ненулевые комбинации из \(r\) бит.

Код Хэмминга (7, 4)

“Классический” вариант (как у Хэмминга)

\[\mathbf H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}\]

Каноническая форма

\(\mathbf H = \left(\begin{array}{c} \\ \\ \\ \end{array}\right.\)

\(\begin{array}{cccc} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{array}\;\;\)

\(\left.\begin{array}{|ccc} & 1 & 0 & 0 \\ & 0 & 1 & 0 \\ & 0 & 0 & 1 \\ \end{array} \right)\)

Порождающая матрица:

Каноническая форма

\[\mathbf G^\T = \]

\(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \hline \end{matrix}\)

\(\begin{array}{cccc} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{array}\;\;\)

Каноническая форма

\[\mathbf G^\T = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \hline 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{pmatrix}\]

“Как у Хэмминга”

\[\mathbf G^\mathrm T = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}\]

Сообщение \(\mathbf m\)	Код \(\mathbf G^\mathrm T \mathbf m\)
0000	0000000
0001	0001111
0010	0010011
0011	0011100
0100	0100101
0101	0101010
0110	0110110
0111	0111001

Сообщение \(\mathbf m\)	Код \(\mathbf G^\mathrm T \mathbf m\)
1000	1000110
1001	1001001
1010	1010101
1011	1011010
1100	1100011
1101	1101100
1110	1110000
1111	1111111

Синдром	Вектор ошибки
110	0000001
101	0000010
011	0000100
111	0001000
100	0010000
010	0100000
001	1000000

“Классический” вариант перестановкой бит

Сообщение \(\mathbf m\)	Код \(\mathbf G^\T \mathbf m\)
0000	0000000
0001	1101001
0010	0101010
0011	1000011
0100	1001100
0101	0100101
0110	1100110
0111	0001111

Сообщение \(\mathbf m\)	Код \(\mathbf G^\T \mathbf m\)
1000	1110000
1001	0011001
1010	1011010
1011	0110011
1100	0111100
1101	1010101
1110	0010110
1111	1111111

Синдром	Вектор ошибки
001	0000001
010	0000010
011	0000100
100	0001000
101	0010000
110	0100000
111	1000000

Циклические коды

Циклический код: линейный код, циклический сдвиг кодового слова влево или вправо даёт кодовое слово.

формализм операций над многочленами
множество кодовых слов длины \(n\) – множество многочленов степени \(n-1\),
делятся без остатка на \(g(x)\) степени \(r = n-k\), являющийся делителем \(x^n-1\)
Все операции по модулю \(x^n-1\)
таким образом, образует кольцо,
умножение на \(x\) – циклический сдвиг
Проверочный многочлен \(h(x) = (x^n-1)/g(x)\), для любого разрешённого кодового слова \(f(x)\), \(f(x) h(x) = 0\).

\(m(x)\) – сообщение, разрешённое кодовое слово \(c(x) = m(x)g(x)\)
Если \(g(x) = \sum_{i=0}^{r} g_i x^i\), \[\mathbf G = \begin{pmatrix} g \\ x g \\ x^2 g \\ \vdots \\ x^k g \\ \end{pmatrix} = \begin{pmatrix} 0 & \cdots & 0 & 0 & g_r & \cdots & g_0 \\ 0 & \cdots & 0 & g_r & \cdots & g_0 & 0 \\ \vdots & & & \ddots & & & \vdots \\ g_r & g_{r-1} & \cdots & g_0 & 0 & \cdots & 0 \\ \end{pmatrix}\]

На практике – систематический подход, информационные и проверочные символы разделяются.

Если \(m(x) x^r = q(x) g(x) + r(x),\) где \(q(x)\) – частное, \(r(x)\) – остаток,
то \(c(x) = q(x)g(x) = m(x)x^r - r(x)\)
\(c(x) = m(x) || - r(x)\)

\[\mathbf G =\begin{bmatrix}\mathbf I_k | - \mathbf R \\\end{bmatrix},\] \[\mathbf R = \begin{pmatrix} \mathrm{rem}(x^n, g(x))\\ \mathrm{rem}(x^{n-1}, g(x))\\ \vdots\\ \mathrm{rem}(x^r, g(x))\\ \end{pmatrix}\]

синдром \(s(x) = t(x) \mod g(x)\), где \(t(x)\) полученный сигнал
вектор ошибки из \(\mathrm{rem}(e(x),g(x)) = s(x).\)

Выбор порождающего многочлена не произволен.

\[\mathbf G = \begin{pmatrix} 0 & \cdots & 0 & 0 & g_r & \cdots & g_0 \\ 0 & \cdots & 0 & g_r & \cdots & g_0 & 0 \\ \vdots \end{pmatrix}\]

строчки – разрешённые кодовые слова (соответственно \(c_i\)), нулевой вектор – разрешён
\(d_H(c_i, 0) =\) числу ненулевых членов в \(g(x)\)
\(\underset{c_i\neq c_1}\min d_H(c_i, c_1) \le 2+\floor{\frac{r-1}{2}}\)
для оптимизации \(d_0\), \(g_0 \neq 0\), \(g_r\neq 0\), из прочих половина ненулевые.

Коды Хэмминга \((n, k)\), в которых \(n\) и \(k-1\) являются взаимно простыми или \(k=2\) – циклические (с точностью до перестановок)
Код Хэмминга (7,4) эквивалентен циклическому \(g(x) = x^3+x+1\).

О возможности существования очень хороших линейных кодов

Очень хорошие линейные коды существуют
При \(N\to\infty\), вероятность неоднозначности \(\to 0\).

Рассмотрим линейный код с двоичной проверочной матрицей \(\mathbf H\), \(M\times N\), \(M \sim N\).
Плотность кодирования \(\rho \ge 1 - \frac{M}{N}.\)
Далее полагаем худший случай \(\rho = 1 - \frac{M}{N}.\)

Выберем кодовое слово \(\mathbf c:\: \mathbf H \mathbf c = 0 \mod 2.\)
ДСК добавляет шум \(\mathbf x\); \(\mathbf r = \mathbf c+\mathbf x \mod 2.\)
Получатель восстанавливает \(\mathbf c\) и \(\mathbf x\) из \(\mathbf r\)
Декодирование по синдрому, \(\mathbf s = \mathbf H \mathbf r \mod 2 = \mathbf H \mathbf x \mod 2.\)

Декодирование по синдрому, \(\mathbf s = \mathbf H \mathbf r \mod 2 = \mathbf H \mathbf x \mod 2.\)

\(\mathbf s\) зависит только \(\mathbf x\)
задача декодирования – найти наиболее правдоподобный \(\mathbf{\hat x}: \mathbf H \mathbf{\hat x} = \mathbf s \mod 2\)
Тогда \(\mathbf{\hat c} = \mathbf r - \mathbf{\hat x} \mod 2\)

Рассмотрим субоптимальную стратегию.
Пусть декодер (декодер типичных множеств) рассматривает множество типичных векторов шума \[T = \brace{\mathbf x \in X^N : \left|\log_2\frac{1}{P(\mathbf x)} - N H(X)\right| < \beta},\] где для ДСК \(H(X) = H_2(f)\)
если ни один \(\mathbf x\in T\) не удовлетворяет \(\mathbf H \mathbf x = \mathbf s\), или их несколько, ошибка декодирования.

Для данной \(\mathbf H\), вероятность ошибки \(P = P_1 + P_2,\)
\(P_1\) – вероятность \(\mathbf x \notin T\)
\(P_2\) – \(\mathbf x\in T\) и \(\exists \mathbf x': \mathbf H \mathbf x = \mathbf H \mathbf x'\)
\(\underset{N\to\infty}\lim P_1 = 0,\) что показано в доказательстве теоремы о кодировании источника
\(P_2\) – вероятность \(\exists \mathbf x\in T, \mathbf x' \in T:\) \(\mathbf H(\mathbf x' - \mathbf x) = 0\)

Введём функцию \[f(\mathbf x, \mathbf x') = \left\{\begin{align} 1, && \mathbf H (\mathbf x' -\mathbf x) = 0 \\ 0, && \mathbf H (\mathbf x' -\mathbf x) \neq 0 \end{align}\right.\]

Количество ошибок декодирования \(N_e\in \brace{0,1}\) для данного \(\mathbf x \in T\) тогда

\[N_e(\mathbf x) \le \sum_{\begin{align}\mathbf x'\in T\\\mathbf x'\neq \mathbf x\end{align}} f(\mathbf x, \mathbf x')\]

Тогда усредняя по всем \(\mathbf x \in T\),

\[P_2 = \sum_{\mathbf x\in T} P(\mathbf x) N_e(\mathbf x)\]

\[P_2 \le \sum_{\mathbf x\in T} P(\mathbf x) \sum_{\begin{align}\mathbf x'\in T\\\mathbf x'\neq \mathbf x\end{align}} f(\mathbf x, \mathbf x').\]

Усредняя по всем матрицам \(\mathbf H\),

\[\bar P_2 \le \sum_{\mathbf H} P(\mathbf H) \sum_{\mathbf x\in T} P(\mathbf x) \sum_{\begin{align}\mathbf x'\in T\\\mathbf x'\neq \mathbf x\end{align}} f(\mathbf x, \mathbf x')\]

\[\bar P_2 \le \sum_{\mathbf x\in T} P(\mathbf x) \sum_{\begin{align}\mathbf x'\in T\\\mathbf x'\neq \mathbf x\end{align}} \sum_{\mathbf H} P(\mathbf H) f(\mathbf x, \mathbf x')\]

\[\bar P_2 \le \sum_{\mathbf x\in T} P(\mathbf x) \sum_{\begin{align}\mathbf x'\in T\\\mathbf x'\neq \mathbf x\end{align}} 2^{-M}\]

\[\bar P_2 \le \sum_{\mathbf x\in T} P(\mathbf x) (|T|-1) 2^{-M}\]

\[\bar P_2 \le (|T|-1) 2^{-M} \underset{\le 1}{\underbrace{\sum_{\mathbf x\in T} P(\mathbf x)}}\]

\[\bar P_2 \le (|T|-1) 2^{-M}\]

\[\bar P_2 \le |T| 2^{-M}\]

\[\bar P_2 < 2^{N(H(X)+\beta)-M}\]

\(\sum_{\mathbf H} P(\mathbf H) f(\mathbf x, \mathbf x')\) – вероятность \(\mathbf H(\mathbf x' - \mathbf x) = 0\) по всем случайным \(\mathbf H\)

не превышает вероятности равенства нулю случайного вектора; поскольку синдром длины \(M\), \(\sum_{\mathbf H} P(\mathbf H) f(\mathbf x, \mathbf x') \le 2^{-M}\)

При доказательстве теоремы о кодировании источника показано, \(|T|< 2^{N(H(X)+\beta)}\)

\[\bar P_2 < 2^{N(H(X)+\beta)-M}\]

Если \(N(H(X)+\beta)-M < 0\), т.е. \(H(X) < M/N,\) то \(\overline P \to 0\) с ростом \(N\)
если в среднем по всем возможным \(\mathbf H\) вероятность ошибки убывает, существуют линейные коды, для которых она убывает.
Более того, таких кодов большинство.

Отметим, что подставляя \(H(X) < M/N\) в \(\rho = 1 - M/N\):

\[\rho = 1 - M/N\]

\[M/N = 1 - \rho\]

\[H(X) < M/N = 1 - \rho\]

\[H(X) < 1 - \rho\]

\[\rho < 1 - H(X)\]

\[\rho < 1 - H_2(f)\]

Условие теоремы кодирования канала для ДСК.

Мы заодно доказали теорему о кодировании источника.

Мы “угадываем” вектор шума \(\mathbf x\) длины \(N\) по вектору синдрома \(\mathbf z\) длины \(M\), с \(P(\text{err})\to 0\), если \(H(X) < M/N\)
т.е. существует схема кодирования, позволяющая с \(P(\text{err}) = \delta\) передать \(N\) бит сообщения в коде длины \(M = N H(X) + \varepsilon\).