Основы теории передачи информации


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


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

Пусть U = (U0, U1, U2, ...Un-1) - двоичная последовательность длиной  n.

Число единиц (ненулевых компонент) в этой последовательности называется весом Хемминга  вектора  U  и  обозначается   w(U).

Например, вес Хемминга вектора U = ( 1001011 ) равен четырем, для вектора  U = ( 1111111 ) величина  w(U)

составит 7 и т.д.

Таким образом, чем больше единиц в двоичной последовательности, тем больше ее вес Хемминга.

Далее, пусть U

и V  будут двоичными последовательностями длиной n.

Число разрядов, в которых эти последовательности различаются, называется расстоянием Хемминга   между U и V  и обозначается d( U, V).

Например, если U = ( 1001011 ),  а V = ( 0100011 ), то d( U, V) = 3.

Задав линейный код, то есть определив все 2k его кодовых слов, можно вычислить расстояние между всеми возможными парами кодовых слов. Минимальное из них называется минимальным кодовым расстоянием кода и обозначается dmin.

Можно проверить и убедиться, что минимальное кодовое расстояние для рассматриваемого нами в примерах (7,4)-кода равно трем: dmin(7,4) = 3. Для этого нужно записать все кодовые слова (7,4)-кода Хемминга (всего 16 слов), вычислить расстояния между их всеми парами и взять наименьшее значение. Однако можно определить dmin блочного кода и более простым способом.

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

Если при передаче кодового слова по каналу связи в нем произошла одиночная ошибка, то расстояние Хемминга между переданным словом U и принятым вектором  r  будет равно единице. Если при этом одно кодовое слово не перешло в другое (а при dmin > 1 и при одиночной ошибке это невозможно), то ошибка будет обнаружена при декодировании.




Начало  Назад  Вперед



Книжный магазин