Помехоустойчивые коды: коды, позволяющие обнаружить и/или исправить ошибки в кодовых словах, возникающие при передаче через канал с шумом. Коды строятся таким образом, что используются только часть всех возможных кодовых слов. Используемые кодовые слова называются разрешёнными, прочие – запрещёнными.

Помехоустойчивые коды разделяют на две группы:

Коды с обнаружением ошибок
Коды с исправлением ошибок

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

Расстояние Хэмминга \(d_H\): число, характеризующее отличие между двумя кодовыми словами. Численно, число символов, в которых отличаются два кодовых слова, или, иными словами, число символов, которые необходимо изменить, чтобы получить из одного кодового слова другое.
Кодовое расстояние \(d_0\): для кода \(C\), наименьшее расстояние Хэмминга \(d_H\) между парой различных кодовых слов \(c_1, c_2 \in C\): \[d_0 = \underset{c_1\neq c_2}\min d_H(c_1, c_2).\]
\(t\)-кратная ошибка: Считается, что при передаче произошла \(t\)-кратная ошибка, если расстояние Хэмминга между переданным кодом \(m\) и полученным кодом \(r\) равно \(t\): \[d_H(m, r) = t.\]

Кодовое расстояние даёт границы применимости кода для обнаружения и исправления ошибок:

Если \(d_0 > t\), то код позволяет обнаружить \(t\)-кратную ошибку.
Если \(d_0 > 2t\), то код позволяет исправить \(t\)-кратную ошибку

Иными словами, код может обнаружить ошибку кратности не более \(t_d = d_0-1\), и исправить ошибку кратности не более \(t_c = \left\lfloor \frac{d_0-1}{2} \right\rfloor\).

Первое утверждение достаточно очевидно: если любые два кодовых слова отличаются по крайней мере на \(d_0\) символов, то при \(t=d_0-1\), \(t\)-кратная ошибка не может привести к разрешённому коду.

Второе утверждение может быть менее очевидно. Оно становится более понятным, если задуматься об оптимальном (минимизирующем ошибку) декодере: такой декодер должен выбирать исходное кодовое слово \(m\), имеющее минимальное расстояние Хэмминга от полученного сигнала \(r\), т.е. минимизировать \(d_H(m, r)\). Такой декодер будет работать однозначным образом при \(t\)-кратных ошибках только в том случае, если в пространстве всех возможных кодовых слов, никакая “сфера” радиуса \(t\) (в смысле расстояния Хэмминга) с центром на кодовом слове \(c_1\) не пересекается с другой сферой на другом кодовом слове \(c_2\). Тогда, ясно, расстояние Хэмминга между любыми двумя кодовыми словами должно быть строго больше \(2 t\).

Граница Хэмминга

Граница Хэмминга устанавливает предельную эффективность, т.е. степень использования пространства всех возможных кодовых слов, для кода, исправляющего ошибки.

Теорема (граница Хэмминга)

Пусть \(A_q(n,d)\) означает мощность (количество кодовых слов) блочного кода \(C\) над \(q\)-ичным алфавитом с блоком длины \(n\) и кодовым расстоянием \(d_0 = d\). Тогда, \[A_q(n, d) \le \frac{q^n}{\sum_{k=0}^t C_n^k (q-1)^k},\] где \(C_n^k = \frac{n!}{k!(n-k)!}\) – биномиальный коэффициент, \(t = \left\lfloor \frac{d-1}{2} \right\rfloor\)

Доказательство

Для каждого кодового слова \(c \in C\), рассмотрим множество \(B_c\) всех q-ичных последовательностей, отличающихся от \(c\) на расстояние Хэмминга \(t' \le \left\lfloor \frac{1}{2}(d-1) \right\rfloor.\) Если для любой пары кодовых слов эти множества не пересекаются, то код исправляет \(t\)-кратные ошибки. Пусть \(t = \left\lfloor \frac{1}{2}(d-1) \right\rfloor.\) Число элементов такого множества \(|B_c|\) тогда можно получить как число комбинаций, отличающихся от \(c\) в \(t\) или менее позициях, т.е. имеющих в соответствующих позициях одно из \(q-1\) значений, отличных от соответствующего значения в \(c\): \[|B_c| = \sum_{k=0}^t C_n^k (q-1)^k.\]

\(A_q(n,d)\) есть число кодовых слов в \(C\). Тогда, поскольку множества \(B_c\) не пересекаются, можем записать \[|B_c| A_q(n,d) \le q^n.\] Эквивалентно, \[A_q(n,d) \le \frac{q^n}{|B_c|} = \frac{q^n}{\sum_{k=0}^t C_n^k (q-1)^k}.\]

\(\not \Delta\)

Утверждение теоремы может быть удобно переформулировать: \(q^n\) отражает полное число возможных \(q\)-ичных кодов длины \(n\), \(A_q(n,d)\) – полное число разрешённых кодов в этом пространстве. Тогда доля используемых кодов \[\frac{A_q(n, d)}{q^n} \le \frac{1}{\sum_{k=0}^t C_n^k (q-1)^k},\] или, в терминах относительного информационного содержания, \[\log_2 A_q(n, d) - \log_2 q^n \le - \log_2 {\sum_{k=0}^t C_n^k (q-1)^k},\] \[I_T - I_C \ge \log_2 {\sum_{k=0}^t C_n^k (q-1)^k},\] где \(I_T\) – число бит на кодовое слово, \(I_C\) – число “полезных” бит в кодовом слове. \(I_T-I_C\) можно интерпретировать как число дополнительны “проверочных” бит в коде, т.е. бит, не несущих смысловой нагрузки, а используемых только для проверки корректности передачи.

Для двоичных кодов \(q=2\), выражение несколько упрощается: \[I_T - I_C \ge \log_2 {\sum_{k=0}^t C_n^k}.\]

Граница Варшамова-Гилберта

Граница Варшамова-Гилберта устанавливает нижнюю границу количества элементов в исправляющем ошибки коде, т.е. ставит границу сверху на максимальное число дополнительных “проверочных” бит.

Теорема (граница Варшамова-Гилберта)

Пусть \(A_q(n,d)\) означает максимальную мощность (количество кодовых слов) для любого блочного кода \(C\) над \(q\)-ичным алфавитом с блоком длины \(n\) и кодовым расстоянием \(d_0 = d\). Тогда, \[A_q(n, d) \ge \frac{q^n}{\sum_{k=0}^{d-1} C_n^k (q-1)^k},\] где \(C_n^k = \frac{n!}{k!(n-k)!}\) – биномиальный коэффициент.

Доказательство

Пусть \(C\) – код, имеющий максимальную мощность, \(|C| = A_q(n,d)\).

Тогда, для любого \(x \in \mathbb F_q^n\) (\(\mathbb F_q^n\) – множество всех \(q\)-ичных векторов длины \(n\)), существует хотя бы одно кодовое слово \(c_x \in C\): \(d_H(x, c_x) \le d-1.\) В противном случае, мы могли бы добавить \(x\) в код, сохранив все его свойства, что противоречит предположению о его максимальной мощности.

Пусть множество \(B_c\) есть множество всех элементов \(\mathbb F_q^n\), имеющих расстояние Хэмминга от \(c\) не более, чем \(d-1.\) Тогда, \[\mathbb F_q^n = \bigcup_{c\in C} B_c.\]

Каждое из множеств \(B_c\) имеет размер \[|B_c| = \sum_{k=0}^{d-1} C_n^k (q-1)^k.\]

Тогда, \[q^n = |\mathbb F_q^n| = \left|\bigcup_{c\in C} B_c \right| \le \sum_{c\in C} |B_c| = |C| |B_c|,\] \[q^n \le A_q(n,d) \sum_{k=0}^{d-1} C_n^k (q-1)^k,\] \[A_q(n,d) \ge \frac{q^n}{\sum_{k=0}^{d-1} C_n^k (q-1)^k}.\] \(\not\Delta\)

Перефразируя утверждение теоремы, получаем

\[I_T - I_C \le \log_2 {\sum_{k=0}^{d-1} C_n^k (q-1)^k}.\]

Для двоичного алфавита \(q=2\): \[I_T - I_C \le \log_2 {\sum_{k=0}^{d-1} C_n^k }.\]

Совершенные коды

Любой исправляющий ошибки код, таким образом, удовлетворяет неравенствам:

\[\log_2 {\sum_{k=0}^{t} C_n^k} \le I_R \le \log_2 {\sum_{k=0}^{d-1} C_n^k },\] где \(t = \left\lfloor \frac{1}{2}(d-1) \right\rfloor\), \(I_R\) – количество дополнительной информации в коде.

Понятно, что, если мы хотим максимизировать пропускную способность канала, то мы должны минимизировать количество дополнительной информации, т.е. добиться \[I_R = \log_2 {\sum_{k=0}^{t} C_n^k},\] или аналогично \[A_q(n, d) = \frac{q^n}{\sum_{k=0}^t C_n^k (q-1)^k}.\]

Коды, удовлетворяющие этому равенству называются совершенными.

Использование совершенных кодов с возрастающей длиной блока позволило бы сколь угодно близко подходить к пределу Шеннона. Однако, есть одна проблема: совершенных кодов крайне мало.

Собственно, все существующие нетривиальные совершенные коды над двоичным алфавитом можно перечислить:

Коды Хэмминга для \(t=1\)
Повторные коды, т.е. коды, \(N\) раз посылающие сообщение, с нечётным \(N\) и \(t = (N-1)/2\).
Совершенный двоичный код Голея с \(t=3\), имеющий длину кодового слова \(N=23\), “полезную нагрузку” \(I_C = 12\) и \(d_0=7\).