Вес и расстояние Хемминга. Способность кодов обнаруживать и исправлять ошибки.

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

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

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

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

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

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

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

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

.

Коды Хэмминга – это простой класс блочных кодов, которые имеют следующую структуру: (n, k)=(2m-1, 2m-1-m), где m=2, 3…и т.д. минимальное расстояние этих кодов = 3, поэтому согласно уравнениям

t=[(dmin-1)/2] – способность кода к исправлению ошибок

e= dmin-1 – возможность определения наличия ошибки

dmin – минимальное расстояние

Коды Хэмминга способны исправить все однобитовые ошибки, или определять все модели ошибки из двух, или малого числа ошибок в блоке.