Вопрос. Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях, то есть число «единиц» в векторе .

Минимальное расстояние линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов.

Вес вектора — расстояние Хемминга между этим вектором и нулевым вектором, иными словами — число ненулевых компонент вектора.

Теорема 1:

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

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

Расстояние между двумя векторами удовлетворяет равенству , где — вес Хемминга вектора . Из того, что разность любых двух кодовых слов линейного кода также является кодовым словом линейного кода, вытекает утверждение теоремы:

Минимальное расстояние Хемминга является важной характеристикой линейного блокового кода. Она определяет другую, не менее важную характеристику — корректирующую способность:

, здесь угловые скобки обозначают округление «вниз».

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

Поясним на примере. Предположим, что есть два кодовых слова A и B, расстояние Хемминга между ними равно 3. Если было передано слово A, и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову A, чем B. Но если каналом были внесены ошибки в двух битах, декодер может посчитать, что было передано слово B.

Число обнаруживаемых ошибок — число ошибок, при котором код может судить об ошибочной ситуации. Это число равно

.

Теорема 2 (без доказательства):

Если любые столбцов проверочной матрицы H линейного (n, k)-кода линейно независимы, то минимальное расстояние кода равно по меньшей мере d. Если при этом найдутся d линейно зависимых столбцов, то минимальное расстояние кода равно d в точности.

Теорема 3 (без доказательства):

Если минимальное расстояние линейного (n, k)-кода равно d, то любые столбцов проверочной матрицы H линейно независимы и найдутся d линейно зависимых столбцов.