Расстояние Хэмминга

К числу ключевых понятий теории кодирования принадлежит понятие расстояния между двоичными словами.

На множестве двоичных слов длины m расстоянием d(а,b) между двумя словами a и b называют число несовпадающих позиций этих слов, например: расстояние между словами a=0110100 и b=0010101 равно 2.

Определенное таким образом понятие называется расстоянием Хэмминга. Оно удовлетворяет следующим аксиомам расстояний:

1. d(а,b) 0 и d(а,b) = 0 тогда и только тогда, когда a = b;

2. d(а,b) = d(b,a);

3. d(а,b) d(a,c)+ d(c,b) – неравенство треугольника.

Расстояние минимально и равно единице, если слова отличаются только в одной позиции. Для возможностей обнаружения ошибки в одной позиции минимальное расстояние между кодовыми словами должно быть равно 2. Иначе ошибке в одной позиции может превратить одно кодовое слово в другое, и она не будет обнаружена.

Весом w(а) слова а называют число единиц среди его координат. Тогда расстояние d(а,b) между двоичными словами a и b есть вес их суммы, т.е. d(a,b)=w(a+b), где символом + обозначена операция покоординатного сложения по модулю 2.

Например

w(0101) = 2

w(1101) = 3

d(1011, 1111) = 1

d(1101, 1101)=0

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

[1] Здесь «шум» – это помехи при передаче.

[2] Криптография – тайнопись

[3] Коды, использующие два различных элементарных сигнала, называются двоичными. Эти сигналы удобно обозначать символами 0 и 1. Тогда кодовое слово будет состоять из последовательности нулей и единиц.

Дата добавления: 2015-08-03