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

  Содержание



 

1. Определение древовидных кодов

В этом разделе мы рассматриваем принципы построения древовидных кодов, их отличие от блоковых кодов, различные представления таких кодов и приводим пример древовидного кода.

1.1. Различие между древовидными и блоковыми кодами

При использовании блоковых кодов информационная последовательность, состоящая в большинстве случаев из 0 и 1, разбивается на блоки длины k, k > 0, и каждому блоку длины k по некоторому правилу сопоставляется блок длины n, n > k. Таким образом, при использовании блокового кода каждому информационному блоку однозначно соответствует кодовое слово большей длины. В древовидных кодах кодовое слово зависит не только от информационного блока, но и от местонахождения этого блока в информационной последовательности. Название "древовидный код" основано на том, что правила кодирования для кодов этого типа удобнее всего описывать посредством древовидного полубесконечного графа.

В этом разделе мы рассматриваем только последовательности, состоящие из 0 и 1, хотя практически все результаты этого раздела справедливы и для последовательностей из символов конечного поля. На первом шаге информационная последовательность разбивается на блоки длины k0. Ветвям, выходящим из вершин дерева, приписано кодовое слово длины n0, где n0 > k0. Совокупность наборов длины n0, определяемых выбранным путем, образует кодовую последовательность, сопоставляемую информационной последовательности, помечающей соответствующий путь из корня дерева. Как обычно, отношение R = k0/n0, характеризующее задержку при передаче информации с использованием помехоустойчивого кодирования, называется скоростью кода.