Минимальное кодовое расстояние

Минимальное кодовое расстояние — это фундаментальный параметр блочного корректирующего кода, равный наименьшему числу позиций, в которых различаются любые две различные кодовые комбинации (кодовые слова) данного кода. В теории кодирования минимальное кодовое расстояние обозначается обычно как \(d_{\min}\) и определяет способность кода обнаруживать и исправлять ошибки, возникающие при передаче или хранении данных. Чем больше минимальное кодовое расстояние, тем выше помехоустойчивость кода, но при этом, как правило, ниже его скорость (избыточность).

Определение и формализация

Для двоичного блочного кода, состоящего из \(M\) кодовых слов длины \(n\) (бит), расстояние Хэмминга \(d(x, y)\) между двумя словами \(x\) и \(y\) — это количество позиций, в которых их символы различаются. Минимальное кодовое расстояние определяется как:

\[ d_{\min} = \min_{x, y \in C, x \neq y} d(x, y), \]

где \(C\) — множество всех кодовых слов. Для недвоичных кодов (например, кодов Рида — Соломона) расстояние вычисляется аналогично, но по символам, а не по битам.

Связь с корректирующей способностью

Минимальное кодовое расстояние напрямую определяет, сколько ошибок код может гарантированно обнаружить и исправить.

Обнаружение ошибок

Код может гарантированно обнаружить любую комбинацию из \(t\) ошибок, если выполняется условие:

\[ d_{\min} \geq t + 1. \]

Иными словами, если искажённое кодовое слово не совпадает ни с одним другим истинным кодовым словом, ошибка будет обнаружена. При \(d_{\min} = 3\) код обнаруживает до 2 ошибок.

Исправление ошибок

Код может гарантированно исправить любую комбинацию из \(s\) ошибок, если выполняется условие:

\[ d_{\min} \geq 2s + 1. \]

Это объясняется тем, что вокруг каждого кодового слова можно построить сферу радиуса \(s\) (в метрике Хэмминга). Если сферы не пересекаются, принятое слово однозначно декодируется в ближайшее кодовое слово. При \(d_{\min} = 3\) код исправляет 1 ошибку.

Одновременное обнаружение и исправление

Если требуется одновременно исправлять \(s\) ошибок и обнаруживать \(t\) ошибок (\(t > s\)), условие имеет вид:

\[ d_{\min} \geq s + t + 1. \]

Классификация кодов по минимальному расстоянию

Коды делятся на классы в зависимости от значения \(d_{\min}\):

• Коды с \(d_{\min} = 1\) — не имеют корректирующей способности (например, простой код без избыточности).
• Коды с \(d_{\min} = 2\) — позволяют обнаружить одну ошибку (код с проверкой на чётность).
• Коды с \(d_{\min} = 3\) — исправляют одну ошибку (код Хэмминга).
• Коды с \(d_{\min} \geq 4\) — исправляют одну и обнаруживают две ошибки (расширенный код Хэмминга), либо исправляют две и более ошибок (коды БЧХ, Рида — Соломона, свёрточные коды).

Примеры

Код с проверкой на чётность

Для кода длины \(n = 3\) с одним битом чётности кодовые слова: 000, 011, 101, 110. Расстояния между парами: \(d(000,011)=2\), \(d(000,101)=2\), \(d(000,110)=2\), \(d(011,101)=2\), \(d(011,110)=2\), \(d(101,110)=2\). Минимальное расстояние \(d_{\min}=2\). Код обнаруживает одну ошибку.

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

Классический код Хэмминга с длиной 7 бит и 4 информационными битами имеет \(d_{\min}=3\). Он исправляет одну ошибку и обнаруживает две. Например, кодовые слова: 0000000, 0001011, 0010111, 0100110 и т. д. Минимальное расстояние между любыми двумя различными словами равно 3.

Код Рида — Соломона (255, 239)

Этот недвоичный код, используемый в системах хранения данных (CD, DVD, QR-коды) и спутниковой связи, имеет минимальное кодовое расстояние \(d_{\min}=17\) (по символам). Он исправляет до 8 символьных ошибок.

Связь с другими параметрами кода

Минимальное кодовое расстояние связано с другими характеристиками кода:

• Скорость кода \(R = k/n\), где \(k\) — число информационных символов. Для заданной длины \(n\) увеличение \(d_{\min}\) обычно требует снижения скорости.
• Граница Синглтона — теоретический предел: \(d_{\min} \leq n - k + 1\). Коды, достигающие этого равенства, называются кодами с максимальным расстоянием (MDS-коды), например, коды Рида — Соломона.
• Граница Хэмминга (или граница сферической упаковки) — для кода, исправляющего \(s\) ошибок, выполняется неравенство: \(2^n \geq \sum_{i=0}^{s} \binom{n}{i} \cdot M\), где \(M = 2^k\) — число кодовых слов. Коды, достигающие этой границы, называются совершенными (например, коды Хэмминга).

Применение

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

• Цифровая связь (Wi-Fi, LTE, спутниковая связь) — используются коды с \(d_{\min}\) от 3 до 10 и более (свёрточные, турбокоды, LDPC).
• Хранение данных (жёсткие диски, флеш-память, RAID-массивы) — применяются коды Рида — Соломона с большим \(d_{\min}\) для исправления пакетов ошибок.
• Космическая связь — коды с \(d_{\min}\) до 32 и выше (например, код Голея, коды БЧХ).
• Криптография — в кодах Мак-Элиса минимальное расстояние используется для оценки стойкости.

Интересные факты

• Понятие минимального кодового расстояния ввёл Ричард Хэмминг в 1950 году в работе «Error detecting and error correcting codes».
• Для кода с \(d_{\min}=3\) вероятность ошибочного декодирования при однократной ошибке равна нулю, если ошибка кратна одному биту.
• В теории кодирования существует понятие «вес Хэмминга» — число ненулевых символов в кодовом слове. Для линейных кодов минимальное расстояние равно минимальному весу ненулевого кодового слова.

Источники

• Хэмминг Р. В. «Теория кодирования и теория информации». — М.: Радио и связь, 1983.
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. «Теория кодов, исправляющих ошибки». — М.: Связь, 1979.
• Питерсон У., Уэлдон Э. «Коды, исправляющие ошибки». — М.: Мир, 1976.
• Блейхут Р. «Теория и практика кодов, контролирующих ошибки». — М.: Мир, 1986.