[Править] Метод «чётности» и общая идея

Простым примером кода с обнаружением одной ошибки является код с битом чётности. Конструкция его такова: к исходному слову добавляется бит чётности. Если в исходном слове число единичек чётно, то значение этого бита 0, если нечётно — 1. Таким образом допустимые слова этого кода имеют чётное количество единичек. Если получено слово с нечётным количеством единичек, то при передаче произошла ошибка.

В случае вероятных групповых ошибок эту технику можно скорректировать. Разобъём передаваемые данные на n слов по k бит и расположим их в виде матрицы  (n столбцов). Для каждого столбца вычислим бит чётности и разместим его в дополнительной строке. Матрица затем передается по строкам. По получению матрица восстанавливается, и если обнаруживется несоответствие, то весь блок передается повторно. Этот метод позволяет обнаружить групповые ошибки длины .

Задача 3.

Слово длиной n с чётным количеством единиц передано по каналу с уровнем шума p. Покажите, что вероятность того, что при передаче произошли ошибки и мы их не заметили равна

Что можно привести к виду

Например, при n = 1000 и p = 10 ^{− 6} получаем

Конец задачи.

Следующая задача повышенной сложности.

Задача 4. (task:errmod) Пусть у нас есть возможность контролировать

сумму единичек по модулю d. Тогда вероятность нефиксируемых ошибок в слове длиной n при передаче его по каналу с шумом p равна P_miss(d,n,p):

Примечание. Интерес здесь представляет неявно заданная функция n(d,P_miss,p), а точнее даже коэффициент содержания полезной информации в переданных n бит как функция от величины шума и вероятности незамеченных ошибок. Чем выше желаемая надёжность передачи, то есть чем меньше вероятность P_miss, тем меньше коэффициент содержания полезной информации.

Конец задачи.

Итак, с помощью одного бита чётности мы повышаем надёжность передачи, и вероятность незамеченной ошибки равна P_miss(2,n,p). Это вероятность уменьшается с уменьшением n. При n = 2 получаем P_miss(2,2,p) = p², это соответствует дублированию каждого бита. Рассмотрим общую идею того, как с помощью специального кодирования можно добиться сколь угодно высокой надёжности передачи.

Общая идея На множестве слов длины n определена метрика Хемминга: расстояние Хемминга между двумя словами равно количеству несовпадающих бит. Например,

ρ_H(10001001,10110001) = 3.

Задача 5.

Докажите, что ρ_H метрика.

Конец задачи.

Если два слова находятся на расстоянии r по Хеммингу, это значит, что надо инвертировать ровно r разрядов, чтобы преобразовать одно слово в другое. В описанном ниже кодировании Хемминга любые два различных допустимых слова находятся на расстоянии . Если мы хотим обнаруживать d ошибок, то надо, чтобы слова отстояли друг от друга на расстояние . Если мы хотим исправлять ошибки, то надо чтобы кодослова отстояли друг от друга на . Действительно, даже если переданное слово содержит d ошибок, оно, как следует из неравенства треугольника, все равно ближе к правильному слову, чем к какому-либо еще, и следовательно можно определить, исходное слово. Минимальное расстояние Хемминга между двумя различными допустимыми кодовыми словами называется расстоянием Хемминга данного кода.

Элементарный пример помехоустойчивого кода — это код, у которого есть только четыре допустимых кодовых слова:

Расстояние по Хеммингу у этого кода 5, следовательно он может исправлять двойные ошибки и замечать 4 ошибки. Если получатель получит слово 0001010111, то ясно, что исходное слово имело вид 0000011111. Коэффициент раздувания равен 5. То есть исходное слово длины m будет кодироваться в слово длины n = 5m

Отметим что имеет смысл говорить о двух коэффициентах:

•  — коэффициент содержания полезной информации

•  — коэффициент раздувания информации

Первый есть функция от переменной n, а второй, обратный ему, — от переменной m.

Здесь мы подошли к довольно трудной задаче — минимизировать коэффициент раздувания для требуемой надёжности передачи. Она рассматривается в разделе (theory).