Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

1.2.Ошибки типа замещения символов и принцип максимального правдоподобия


Пусть слово длины n, состоящее из двоичных символов 0 и 1, передается по каналу передачи. Обычно при передаче символа 0 (1) на приемнике принимается тот же символ. Однако, иногда вместо 0 может быть принята 1 и, наоборот, вместо 1 может быть принят 0. Если в среднем ошибочным оказывается один из 100 символов, то можно считать, что вероятность неправильной передачи символа равна 0,01. Такие ошибки называются ошибками типа замещения символов.

Одиночной ошибкой типа 0 → 1 (1 → 0) в двоичном слове x называют преобразование слова x, состоящее в замене одного из его символов 0 (соответственно одного из его символов 1) символом 1 (соответственно символом 0). Одиночные ошибки типа  0 → 1 и 1 → 0 называют также аддитивными ошибками.

Пусть было передано двоичное слово x = x1...xn, а на приемнике принято двоичное слово y = y1...yn. Так как канал с шумом, то принятый вектор y может отличаться от переданного вектора x. Удобно ввести вектор ошибки ex Å y, который называется вектором ошибок. Таким образом, канал искажает вектор x, прибавляя к нему вектор ошибок e. Пусть p, 0  ≤  p << ½, - вероятность неправильной передачи двоичного символа. Тогда ej = 0 с вероятностью 1 - p, и     ej = 1 с вероятностью p.

Расстоянием Хэмминга между двумя двоичными векторами x и y, обозначение: d(x, y), называется число позиций, в которых эти векторы отличаются. Например, d(10111, 00011) = 2. Весом двоичного вектора, обозначение: w(x), называется число единичных компонент вектора x. Таким образом, d(x, y) = d(xÅy) = w(e). Если вес вектора ошибок e равен t, то говорят, что при передаче кодового вектора x произошла t-кратная ошибка или ошибка кратности t.

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

Декодирование полным перебором по принципу максимального правдоподобия заключается в следующем. Выписываются все 2k кодовых слов, и принятое слово сравнивается с каждым кодовым словом. Ошибка будет исправлена, если ближайшее кодовое слово единственно. Такой метод очень трудоемкий, так как обычно число информационных символов достигает нескольких сотен. Поэтому одной из задач теории кодирования является построение кодов, которые позволяют обнаруживать и исправлять ошибки без полного перебора кодовых слов.