Вообще говоря, практически все блочные помехоустойчивые коды “достаточно хорошие”, но практически все они требуют построения таблиц размера, экспоненциально зависящего от длины блока. А по теореме о канале с шумом, длина блока должна быть большой. Понятно, что построение и поиск в очень больших таблицах с практической точки зрения нежелательны. Соответственно в основном рассматриваются коды, которые можно построить более просто – под “более просто” в данном случае означает за полиномиальное время от длины блока – желательно, линейное время от длины блока.
На практике, построение практически применимых кодов, настолько хороших, как обещает теорема о канале с шумом, на текущий момент является нерешённой проблемой. Т.е. предел, установленный Шенноном на практике не достигается. Тем не менее, существуют “достаточно хорошие” практически применимые коды.
- Очень хорошие коды
- Семейство блочных кодов, которые для данного зашумлённого канала дают произвольно малую вероятность ошибки при любой скорости передачи вплоть до пропускной способности канала.
- Хорошие коды
- Семейство блочных кодов, которые для данного зашумлённого канала дают произвольно малую вероятность ошибки при любой скорости передачи вплоть до некоторого максимума, который может быть меньше пропускной способности канала.
- Плохие коды
- Семейства блочных кодов, которые не могут обеспечить произвольно малую вероятность ошибки, либо (номинально) могут только при нулевой скорости передачи.
- Практические коды
- Коды, кодирование-декодирование которых имеет полиномиальную сложность1 при кодировании и декодировании.
Большинство известных кодов являются линейными блочным кодами. Напомним,
- \((N, K)\) блочный код
- Множество \(2^K\) кодовых слов длины \(N\), кодирующих некий источник с алфавитом мощности \(2^K\).
- \((N, K)\) блочный линейный код
- Блочный код, в котором кодовые слова \(\brace{\vect x^{(s)}}\) образуют \(K\)-мерное линейное векторное пространство, являющееся подпространством \(\mathcal A_X^N\) всех возможных кодовых слов длины \(N\), т.е. линейная операция над любыми двумя разрешёнными кодовыми словами даёт разрешённое кодовое слово.
Напомним несколько определений из линейной алгебры.
- Магма
- Множество \(M\) и бинарная операция \(\bullet: M\times M \to M\) называются вместе магмой, если \(\forall a, b \in M: a\bullet b \in G\), т.е. \(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\)
Если любой линейный код образует векторное пространство, то процесс построения кода должен естественным образом описываться в терминах линейной алгебры. Это действительно так.
Операция кодирования может быть представлена в виде матрицы \(\vect G\), такой, что при кодировании сообщения \(\vect s\), кодированный сигнал \(\vect t = \vect G^\mathrm T \vect s\).
Множество всех кодовых слов \(\brace{\vect t}\) может быть определено как множество, удовлетворяющее уравнению \(\vect H \vect t = 0,\) где \(0\) – нейтральный элемент операции \(+\).
Матрица \(\vect G\) называется порождающей матрицей, матрица \(\vect H\) – проверочной матрицей. Они, ясно, должны удовлетворять условию \(\vect H \vect G^\mathrm T = \vect 0\), где \(\vect 0\) – нулевая матрица.
- Синдром
- Произведение проверочной матрицы и принятого сигнала \(\vect s = \vect H \vect r\) называется синдромом. Для разрешённых кодовых слов, синдром равен нулю.
Поскольку \(\vect H \vect t = 0\), для принятого сигнала \(\vect r\), \(\vect s = \vect H \vect r = \vect H t + \vect H \vect e = \vect H \vect e\), где \(t\) – разрешённое кодовое слово и \(e\) – ошибка. Таким образом, между синдромом и вектором ошибки можно поставить взаимно однозначное соответствие. Если быть точным, то это возможно, если, по крайней мере, \(q^{(n-k)} \ge \sum_{j=0}^t C_n^j (q-1)^j\), где \(t\) – максимальная кратность ошибки, что совпадает с границей Хэмминга.
Пусть \(\mathbb F_q^n\) – линейное \(n\)-мерное пространство над полем Галуа мощности \(q\). Тогда линейный код \(C\), являющийся подпространством \(\mathbb F_q^n\) можно представить в виде некоторого минимального базиса \(k \le n\) векторов. Векторы этого базиса образуют строки порождающей \(k\times n\) матрицы \(\vect G\). Если матрица \(\vect G\) имеет блочную форму \(\vect G = \brack{\vect I_k | \vect P},\) где \(I_k\) – единичная матрица \(k\times k\), \(P\) – некоторая матрица \(k \times (n-k)\), мы говорим, что \(\vect G\) находится в стандартной форме.
Если \(\vect G = \brack{\vect I_k | \vect P},\) то \(\vect H = \brack{-\vect P^{\mathrm T} | \vect I_{n-k}}\) – одно из решений уравнения \(\vect H \vect G^\mathrm T = \vect 0\). Проверочная матрица имеет размер \((n-k)\times n\).
Следует отметить, что \(n\) – число символов в коде, \(k\) – число информационных символов и \(n-k\) – число проверочных символов.
Линейность гарантирует, что минимальное расстояние Хэмминга между кодовым словом \(c_0\) и любым другим кодовым словом \(c\neq c_0\) не зависит от \(c_0\). Действительно, свойство линейности даёт \(c-c_0 \in C\), а из определения расстояния Хэмминга, \(d(c_0, c) = d(c-c_0, 0)\), тогда \[\underset{c\neq 0}\min d(c_0, c) = \underset{c\neq 0}\min d(c-c_0, 0) = \underset{c\neq 0}\min d(c, 0).\]
Два кода называются эквивалентными, если их порождающие матрицы отличаются только перестановкой столбцов и элементарными линейными операциями над строками. Такие коды по сути отличаются только положением проверочных символов в кодовых словах.
В менее общих, более практических терминах, коды в основном строятся над двоичными алфавитами. Тогда поле \(F\) представляет собой двоичное поле Галуа, где операции \(+_F\) и \(\cdot_F\) соответственно представляют собой сложение \(\mod 2\) и умножение. Элементы векторного пространства, в свою очередь, представляют собой элементы пространства \(F^N\), сложение является поэлементным сложением \(\mod 2\), умножение – поэлементное умножение.
Коды Хэмминга
Коды Хэмминга – один из наиболее широко известных классов линейных кодов.
Коды Хэмминга конструируются следующим образом: биты, находящиеся в кодовом слове в разрядах с номером, являющимся степенью 2, являются проверочными, остальные – информационные. Значение \(i\)-го проверочного бита определяется суммой по модулю 2 всех информационных бит с номерами \(j\), таких, что \(i \& j \neq 0,\) где \(\&\) – побитовая конъюнкция двоичных представлений чисел \(i\) и \(j\). В каноническом варианте биты нумеруются слева направо.
Число проверочных бит выбирается исходя из возможности исправить 1 ошибку в соответствии с границей Хэмминга: \(r = \ceil{\log_2 (n+1)}\). Собственно, обычно поступают наоборот – исходя из числа проверочных бит, определяют максимально возможное число информационных: \(2^r - 1 = n\). Тогда, кодов Хэмминга с 1 проверочным битом не существует, код Хэмминга с 2 проверочными битами содержит 1 информационный бит и т.д.
Коды Хэмминга обозначаются парой чисел: количеством бит в кодовом слове и количеством информационных бит.
С точки зрения систематического подхода, проверочная матрица кодов Хэмминга \(H\) состоит из \(r\) строк и \(n\) столбцов, причём столбцы различны и не равны нулю. А поскольку \(n = 2^r - 1\), столбцы этой матрицы неизбежно включают все ненулевые комбинации из \(r\) бит.
Например, код Хэмминга (7, 4) имеет проверочную матрицу (упорядоченную по возрастанию столбцов) \[\vect H = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix}\]
Или в каноническом варианте (получается перестановкой 1, 2 и 4 столбцов на 5, 6, 7 позиции соответственно):
\[\vect H = \paren{\begin{array}{cccc|ccc} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array}}\]
Каноническая порождающая матрица тогда: \[\vect G^\mathrm 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}\]
Порождающая матрица, соответствующая исходной проверочной (получается перестановкой 5,6,7 строк на 1, 2, 4 позиции соответственно): \[\vect 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}\]
Тогда коды для соответствующих сообщений:
| Сообщение \(\vect m\) | Код \(\vect G^\mathrm T \vect m\) |
|---|---|
| 0000 | 0000000 |
| 0001 | 0001111 |
| 0010 | 0010011 |
| 0011 | 0011100 |
| 0100 | 0100101 |
| 0101 | 0101010 |
| 0110 | 0110110 |
| 0111 | 0111001 |
| 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 |
Например, получив сообщение r=1101010, вычислим синдром Hr = 110, что соответствует вектору ошибки 1000000. Тогда исходное сообщение c=0101010, m=0101.
Канонический вариант кода Хэмминга получается перестановкой проверочных бит на соответствующие позиции кодового слова:
| Сообщение \(\vect m\) | Код \(\vect G^\mathrm T \vect m\) |
|---|---|
| 0000 | 0000000 |
| 0001 | 1101001 |
| 0010 | 0101010 |
| 0011 | 1000011 |
| 0100 | 1001100 |
| 0101 | 0100101 |
| 0110 | 1100110 |
| 0111 | 0001111 |
| 1000 | 1110000 |
| 1001 | 0011001 |
| 1010 | 1011010 |
| 1011 | 0110011 |
| 1100 | 0111100 |
| 1101 | 1010101 |
| 1110 | 0010110 |
| 1111 | 1111111 |
Циклические коды
Циклический код – это линейный блоковый код, обладающий свойством цикличности: циклический сдвиг разрешённого кодового слова влево или вправо на 1 бит даёт разрешённое кодовое слово.
При построении циклических кодов, используют формализм операций над многочленами: множество кодовых слов длины \(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)\) в соответствующем кольце, разрешённое кодовое слово немедленно получается умножением \(m(x)\) на \(g(x)\). В таком случае, при \(g(x) = \sum_{i=0}^{r} g_i x^i\), соответствующая порождающая матрица имеет вид \[\vect 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}\tag{1}\] (либо отражённая по горизонтали при обратном порядке бит – мы однако будем исходить из того, что младший бит соответствует нулевой степени)
Однако на практике используется систематический подход, разделяющий информационные и проверочные символы.
Для данного сообщения \(m(x)\), оно умножается на \(x^r\) и делится на \(g(x)\), так, что \[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).\]
Тогда кодовые слова представляют из себя конкатенацию исходного сообщения \(m(x)\) и отрицания остатка от деления \(m(x)x^r\) на \(g(x)\), и тогда порождающая матрица имеет вид
\[\vect G = \begin{bmatrix} \vect I_k | - \vect R \\ \end{bmatrix},\] где \[\vect 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)\) определяется как остаток от деления полученного кодового слова на \(g(x)\). Соответствующий вектор ошибки определяется из \(\mathrm{rem}(e(x),g(x)) = s(x).\) Ясно, что, поскольку кодовые слова имеют делителем \(g(x)\) по построению, для них синдром равен нулю.
Немаловажным нюансом является то, что выбор порождающего многочлена, вообще говоря, не произволен – это ясно, если внимательно посмотреть на порождающую матрицу.
Действительно, рассмотрим первые две строчки матрицы \(\vect G\) из \((1).\) Эти строчки являются разрешёнными кодовыми словами. Нулевой вектор так же является разрешённым кодовым словом. Находя расстояние Хэмминга от нулевого кодового слова до первой строчки \(\vect G\), получаем, что кодовое расстояние циклического кода не может превышать число ненулевых членов в порождающем многочлене. Находя расстояние Хэмминга между первой и второй строчками, получаем, что, если все коэффициенты порождающего многочлена отличны от нуля, то кодовое расстояние не может быть больше 2, а вообще не превышает \(2+\floor{\frac{r-1}{2}}\). Соответственно, не более половины “средних” (т.е. кроме старшего и младшего) членов \(g(x)\) будут ненулевыми, причём младший и старший всегда ненулевые.
Некоторые коды Хэмминга, а именно, коды \((n, k)\), в которых \(n\) и \(k-1\) являются взаимно простыми (или \(k=2\)), являются так же циклическими (с точностью до перестановок)
Например, код, эквивалентный коду Хэмминга (7,4) можно представить как циклический код с порождающим многочленом \(g(x) = x^3+x+1\). Действительно, \(n=7\), \(k=4\), \(r=3\).
| m | \(m(x)\) | \(r(x)\) | Код |
|---|---|---|---|
| 0000 | \(0\) | \(0\) | 0000 000 |
| 0001 | \(1\) | \(x+1\) | 0001 011 |
| 0010 | \(x\) | \(x^2+x\) | 0010 110 |
| 0011 | \(x+1\) | \(x^2+1\) | 0011 101 |
| 0100 | \(x^2\) | \(x^2+x+1\) | 0100 111 |
| 0101 | \(x^2+1\) | \(x^2\) | 0101 100 |
| 0110 | \(x^2+x\) | \(1\) | 0110 001 |
| 0111 | \(x^2+x+1\) | \(x\) | 0111 010 |
| 1000 | \(x^3+0\) | \(x^2+1\) | 1000 101 |
| 1001 | \(x^3+1\) | \(x^2+x\) | 1001 110 |
| 1010 | \(x^3+x\) | \(x+1\) | 1010 011 |
| 1011 | \(x^3+x+1\) | \(0\) | 1011 000 |
| 1100 | \(x^3+x^2\) | \(x\) | 1100 010 |
| 1101 | \(x^3+x^2+1\) | \(1\) | 1101 001 |
| 1110 | \(x^3+x^2+x\) | \(x^2\) | 1110 100 |
| 1111 | \(x^3+x^2+x+1\) | \(x^2+x+1\) | 1111 111 |
Допустим, мы получили код \(0011 000\), что соответствует многочлену \(x^3+x^4\). Остаток от деления на \(g(x)\) \(x^2+1\), что соответствует ошибке передачи. \(x^6/g(x) = x^2+1\), тогда синдром соответствует ошибке в 7-м бите. Кодовое слово тогда \(1011 000\) и исходное сообщение \(1011\). Таблица синдромов имеет вид:
| Синдром | Вектор ошибки |
|---|---|
| 1 | 0000001 |
| x | 0000010 |
| x^2 | 0000100 |
| x+1 | 0001000 |
| x^2+x | 0010000 |
| x^2+x+1 | 0100000 |
| x^2+1 | 1000000 |
О возможности существования очень хороших совершенных кодов
Рассмотрим двоичный симметричный канал с вероятностью перехода \(f\).
Ёмкость двоичного симметричного канала \(C(f) = 1 - H_2(f)\) (см. семинар 1, пример 6). По теореме Шеннона о канале с шумом, для достаточно большой длины кода \(N\), существуют блочные коды, имеющие плотность кодирования \(\rho\), сколь угодно близкую к \(C(f)\) и исчезающе малую вероятность ошибки. Для больших \(N\), число битовых ошибок в блоке примерно \(fN\), следовательно, такие блочные коды можно назвать исправляющими fN ошибок (почти наверняка).
Рассмотрим теперь ДСК, где \(f > 1/3\). Пусть существует совершенный исправляющий fN ошибок код. Рассмотрим три кодовых слова из этого кода (у такого кода должно быть \(2^{N\rho} \approx 2^{NC(f)}\) кодовых слов, поэтому при больших N найдётся хотя бы три). Без ограничения общности, пусть один из этих кодов будет нулевым (т.е. состоящим из нулей), второй имеет \((u+v)N\) первых единиц, прочие нули, третий – \(uN\) нулей, \((v+w)N\) единиц, остальные нули. Все коды (из рассматриваемых трёх) имеют \(x = (1-u-v-w)N\) нулей в конце. Если это совершенный исправляющий fN ошибок код, то кодовое расстояние должно быть больше \(2fN\), тогда \[u+v > 2 f,\] \[v+w > 2 f,\] \[u+w > 2 f,\]
Суммируя, получаем: \[u+v+w > 3 f.\]
Но \(f>1/3\), и \(u+v+w > 1\), тогда \(x < 0\), что невозможно.
То есть, совершенный исправляющий \(fN\) ошибок код не может иметь даже трёх кодовых слов, не говоря уже о \(2^{N\rho}\).
О возможности существования очень хороших линейных кодов
Несмотря на невозможность существования очень хороших совершенных кодов, очень хорошие линейные коды существуют. В первую очередь это связано с тем, что на самом деле при длине кодовых слов \(N\to\infty\), вероятность того, что в результате изменения \(fN\) бит в кодовом слове, результат будет неоднозначен, стремится к нулю.
Рассмотрим линейный код с двоичной проверочной матрицей \(\vect H\), имеющей \(M\) строк и \(N\) столбцов. Считаем, что \(M \sim N\). Плотность кодирования такого кода по крайней мере \[\rho \ge 1 - \frac{M}{N}.\] Далее полагаем худший случай, т.е. \(\rho = 1 - \frac{M}{N}.\)
Выбирается кодовое слово \(\vect t\), такое, что \[\vect H \vect t = 0 \mod 2.\]
ДСК добавляет вектор шума \(\vect x\), так, что \[\vect r = \vect t+\vect x \mod 2.\]
Получатель должен восстановить \(t\) и \(x\) из \(r\). Используя подход декодирования по синдрому. Получатель вычисляет синдром \[\vect z = \vect H \vect r \mod 2 = \vect H \vect x \mod 2.\]
Поскольку синдром \(\vect z\) зависит только от вектора шума \(\vect x\), задача декодирования состоит в нахождении наиболее вероятного \(\vect {\hat x}\), удовлетворяющего условию \[\vect H \vect {\hat x} = \vect z \mod 2,\] который затем можно вычесть из \(\vect r\) чтобы получить наиболее вероятное исходное кодовое слово \(\vect {\hat t}\).
Мы хотим показать, что вероятность ошибки стремится к нулю с ростом \(N\) для случайной матрицы \(\vect H\).
Рассмотрим субоптимальную стратегию. Пусть субоптимальный декодер (назовём его декодером типичных множеств) рассматривает множество типичных векторов шума \[T = \brace{\vect x \in X^N : \left|\log_2\frac{1}{P(\mathbf x)} - N H(X)\right| < \beta},\] где для ДСК \(H(X) = H_2(f)\), проверяя, какие из них удовлетворяют найденному синдрому. Если ни один элемент типичного множества не удовлетворяет вычисленному синдрому, или если ему удовлетворяют более одного, то декодер сообщает об ошибке.
Для данной матрицы \(\vect H\), вероятность ошибки можно записать как \[P = P_1 + P_2,\] где \(P_1\) – вероятность того, что \(\vect x\) не типичный, а \(P_2\) – что \(\vect x\) типичный, и по крайней мере ещё один вектор \(\vect x'\) имеет такой же синдром. \(P_1\) уменьшается с ростом \(N\), как показано при доказательстве теоремы Шеннона о кодировании источника (см. лекцию 5). \(P_2\) по сути есть вероятность наличия двух типичных векторов \(\vect x\) и \(\vect x'\), таких, что \[\vect H(\vect x' - \vect x) = 0.\]
Введём функцию \[f(\vect x, \vect x') = \left\{\begin{align} 1, && \vect H (\vect x' -\vect x) = 0 \\ 0, && \vect H (\vect x' -\vect x) \neq 0 \end{align}\right.\]
Количество ошибок \(N_e\) для данного типичного вектора \(\vect x\) тогда \[N_e(\vect x) \le \sum_{\begin{align}\vect x'\in T\\\vect x'\neq \vect x\end{align}} f(\vect x, \vect x')\]
\(N_e(\vect x) \in \brace{0,1}\), правая часть может быть больше 1.
Тогда усредняя по \(\vect x\), \[P_2 = \sum_{x\in T} P(\vect x) N_e(\vect x) \le \sum_{x\in T} P(\vect x) \sum_{\begin{align}\vect x'\in T\\\vect x'\neq \vect x\end{align}} f(\vect x, \vect x').\]
Усредняя по всем матрицам \(\vect H\), \[\bar P_2 \le \sum_{\vect H} P(\vect H) \sum_{x\in T} P(\vect x) \sum_{\begin{align}\vect x'\in T\\\vect x'\neq \vect x\end{align}} f(\vect x, \vect x')\]
\(P(\vect x)\) не зависит от \(\vect H\), поэтому
\[\bar P_2 \le \sum_{x\in T} P(\vect x) \sum_{\begin{align}\vect x'\in T\\\vect x'\neq \vect x\end{align}} \sum_{\vect H} P(\vect H) f(\vect x, \vect x')\]
Выражение \(\sum_{\vect H} P(\vect H) f(\vect x, \vect x')\) это по сути вероятность равенства вектора синдрома нулю по всем возможным случайным матрицам \(\vect H\). Она не превышает вероятности равенства нулю случайного вектора, т.е., поскольку вектор синдрома имеет размер \(M\), \[\sum_{\vect H} P(\vect H) f(\vect x, \vect x') \le 2^{-M}.\]
Тогда, \[\bar P_2 \le (\sum_{x\in T} P(\vect x)) \paren{\abs T -1} 2^{-M} \le \abs T 2^{-M}.\]
При доказательстве теоремы о кодировании источника, было показано, что в типичном множестве примерно \(2^{NH(X)}\) элементов, тогда \[\bar P_2 \le 2^{NH(X)-M}.\]
Если \(NH(X)-M < 0\), т.е. \(H(X) < M/N,\) то вероятность средняя вероятность ошибки экспоненциально убывает с ростом \(N\). Тогда, если в среднем по всем возможным проверочным матрицам вероятность ошибки убывает, то неизбежно существуют такие линейные коды, для которых она так же убывает. Более того, таких кодов большинство.
Отметим, что подставляя условие на энтропию в \(\rho = 1 - M/N,\) получаем \[1 - \rho = M/N,\] \[1 - \rho > H(X),\] \[\rho < 1 - H(X) = 1-H_2(f),\] что совпадает с условием теоремы Шеннона для ДСК.
Отдельно следует отметить, что по сути мы заодно доказали теорему о кодировании источника. Действительно, поскольку мы “угадываем” вектор шума \(\vect x\) длины \(N\) по вектору синдрома \(\vect z\) длины \(M\), с исчезающе малой вероятностью ошибки, если \(H(X) < M/N\), то это означает, что, при достаточно больших \(N\), существует схема кодирования, позволяющая “почти безошибочно” передать \(N\) бит сообщения в коде длины \(M\), так, что \(M = N H(X) + \varepsilon\).
Вообще говоря, имеется ввиду временная или пространственная сложность. Однако в теории сложности алгоритмов доказывается, что \(P(n) \subseteq PSPACE(n)\), т.е. семейство алгоритмов, полиномиальных по времени есть нестрогое подмножество семейства алгоритмов, полиномиальных по памяти, поэтому требование \(P\) и/или \(PSPACE\) по сути эквивалентно требованию \(P\).↩︎