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

  Содержание



 

2.6. Пример декодирования

Пример: Непосредственной проверкой можно убедиться, что кодовое расстояние для древовидного кода при n = 4 на рисунке 1 равно 3. Действительно, первое множество {0000, 0011, 1101, 1110} кодовых слов (нечетные вершины) разбивается на подмножества {0000, 0011} и {1101, 1110}, наименьшее расстояние между словами которых равно 3. Второе множество {0100, 0111, 1010, 1001} кодовых слов (четные вершины) разбивается на подмножества {0100, 0111} и {1010, 1001}, наименьшее расстояние между словами которых также равно 3. Таким образом, данный код при ДКО = 4 исправляет все одиночные ошибки. Заметим, что наименьшее расстояние между двумя различными кодовыми словами в нашем примере равно 2. Таким образом, если бы данный код использовался как блоковый, то мы бы не смогли исправить одиночную ошибку типа 0 → 1, например, в третьем символе кодового слова 0000, т.к. принятое слово 0010 имеет одинаковое расстояние 1 до двух кодовых слов 0011 и 0000. В данном же случае такая ошибка будет исправлена. Пусть передается информационная последовательность 0011... , и в соответствующей кодовой последовательности 00 00 11 10 ... произошла ошибка в третьем разряде, т.е. принимается последовательность 00 10 11 10 .... При декодировании первого блока длины k0 = 1 в таблице декодирования для вершины 1 (рисунок 3) слово 00 10 длины n находится в первом подмножестве кодовых слов. Следовательно первый информационный блок равен 0, и после декодирования информационного символа 0 первые два символа 00 удаляются из декодера. На следующем шаге декодер, в котором содержится слово 1011, находится в вершине 3 дерева, т.е. мы используем ту же таблицу декодирования (рисунок 3). В этой таблице слово 10 11 принадлежит первому подмножеству кодовых слов, следовательно, второй информационный блок также равен 0, т.е. ошибка в третьем символе кодовой последовательности 00 00 11 10 ... будет исправлена.