Разрежённость кода. Расстояние Хэмминга.

Определение 1.Расстоянием Хэмминга между двумя словами x и y одинаковой длины называется число позиций, в которых они различны. Оно обозначается через d(x, y).Расстояние Хэмминга будем называть также просто расстоянием.

Например, d(10101,01110) = 4, d(1a0b1,0a111) = 3.

Определение 2 .Разреженностью (или минимальным расстоянием) кода называется наименьшее из всех расстояний между двумя словами кода.

(Разреженность кода не определена, если он содержит лишь одно слово.)

Разреженность кода обычно обозначается через d^*.

Теорема 1. Пусть x, y, z — слова одинаковой длины. Тогда

1) d(x, y) = 0 ⇐⇒ x = y,

2) d(x, y) = d(y, x),

3) d(x, y) ≤ d(x, z) + d(z, y) (”неравенство треугольника”).

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

1) , 2): Очевидно. 3): Пусть d(x, z) = d₁, d(z, y) = d₂. Можно преобразовать слово x в слово z, изменив в x символы на d1 позициях. Обозначим I₁ — множество этих d₁ позиций (например, I = {2,7}, если изменяются только 2 и 7 позиции). От слова z к слову y можно перейти, изменив в z символы

на d₂ позициях. Обозначим I₂ — множество этих d₂ позиций. Следовательно, от x к y можно перейти, произведя изменения символов в позициях из множества I₁ ∪ I₂, т. е. не более, чем в |I₁ ∪ I₂| ≤ d₁ + d₂ позициях. Таким образом, d(x, y) ≤ d₁ + d₂.

(Теорема показывает, что множество всех слов одинаковой длины в алфавите A есть метрическое пространство с метрикой d(x, y).)

Определение 3. Пусть M — множество всех слов длины n в алфавите A и пусть x ∈ M и r∈ N ∪ {0}. Шаром радиуса r с центром в x называется множество B_r(x) := {m ∈ M | d(x, m) ≤ r}.

В частности, B₀(x) = {x}, B_n(x) = M, B_n+1(x) = M.

Определение 4. Пусть M — множество всех слов длины n в алфавите A и K — блоковый код, содержащийся в M. Говорят, что код K исправляет t ошибок (или что K исправляет любую конфигурацию из t ошибок), если любые два шара радиуса t в M с центрами в словах кода K не пересекаются.

Т. е. шары радиуса t с центрами в кодовых словах попарно не пересекаются. Тогда, если при передаче кода K по каналу связи в слове происходит не более t ошибок,то принятое слово x будет находится на расстоянии ≤ t от переданного кодового слова x и на расстоянии > t от любого другого кодового слова. Код разреженности d^∗ позволяет обнаруживать d^∗−1 ошибок, так как в шаре радиуса d^∗−1 с центром в кодовом слове нет других кодовых слов.

Теорема 2. Пусть K — блоковый код разреженности d^∗ и t∈N. Равносильны условия:

- 5 -

(1) код K исправляет t ошибок,

(2) d^∗ ≥ 2t + 1.

Следовательно, максимальное число ошибок, которое может исправить код разреженности d^∗, есть [(d^∗−1)/2].

Доказательство. (1) ⇒(2): Пусть код K состоит из слов длины n в алфавите A и M =W(n, A). Пусть верно (1) и x, y — слова из K, находящиеся на расстоянии m = d^∗. Тогда в M существуют слова x₁, ..., x_m−1 такие,

что в ряду x, x₁, ..., x_m−1, y расстояние между соседними словами равно 1.

Очевидно, x_t ∈ B_t(x), а так как B_t(x)∩B_t(y) = 0 по определению 4, то должно быть d(x_t, y) > t, т. е. m − t > t и m ≥ 2t + 1. Так как d^∗ = m, то (2) верно.

(2)⇒(1): Пусть d^∗ ≥ 2t + 1. Если не верно (1), то существуют два слова x, y ∈ K такие, что B_t(x) ∩ B_t(y) ≠0. Пусть z ∈ B_t(x) ∩ B_t(y). Тогда d^∗ ≤ d(x, y) ≤ d(x, z) + d(z, y) ≤ t + t = 2t. Получилось противоречие с (2). Итак, (2) ⇒(1).

Теперь пусть t₀ — максимальное число ошибок, которые может исправить код K. Согласно доказанному утверждению (1)⇐⇒(2) t₀ есть максимальное из целых чисел t таких, что 2t+1 ≤ d^∗, т. е. таких, что t ≤[(d^∗−1)/2], и, потому,

t₀ = [(d^∗−1)/2].