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

  Содержание



 

1.3. Автоматное представление древовидных кодов

Если дерево периодическое, то процесс кодирования можно представить с помощью конечного полностью определенного детерминированного автомата. Под конечным автоматом или просто автоматом в данном пособии понимается шестерка А = (S, X, Y, δ, λ, s0), где S - конечное непустое множество состояний с выделенным начальным состоянием s0, X - конечное непустое множество входных символов, Y - конечное непустое множество выходных символов, δ: S×XS - функция переходов автомата, λ: S×XY - функция выходов. Автомат удобно задавать посредством диаграммы переходов, которая представляет собой ориентированный граф. Вершины графа отождествлены с состояниями автомата, ребра помечены так называемыми входо-выходными парами x/y, x Î X, y Î Y. Из вершины s существует ребро в вершину s', помеченное входо-выходной парой x/y, если и только если s= δ(s,x) и y = λ(s,x).

Поведение автомата естественным образом распространяется на входные последовательности. Последовательность (x1.....xk, y1.....yk) называется входо-выходной последовательностью автомата в состоянии s, если существует состояния s1, ..., sk+1, такие, что s = s1 и для любого j Î {1,....,k} справедливо: δ(sj,xj) = sj+1 и λ(sj,xj) = yj. Последовательность y1.....yk называется выходной реакций (или просто реакцией) автомата на входную последовательность i1.....ik в состоянии s.

При представлении автоматом периодического дерева древовидного кода входными символами являются двоичные слова длины k0, выходными символами - двоичные слова длины n0. Вершины диаграммы соответствуют узлам дерева, а ребра, помеченные стрелками, указывают возможные переходы между состояниями. Каждое ребро помечено соответствующей входо/выходной парой «k0 информационных символов/n0 кодовых символов».

Пример: На рисунке 1 дерево является периодическим. Непосредственной проверкой нетрудно убедиться, что поддеревья с корнями в вершинах с нечетными номерами, т.е. 1, 3 и т.д., и поддеревья с корнями в вершинах с четными номерами, 2, 4 и т.д., попарно изоморфны. Таким образом, соответствующий автомат имеет два состояния, и его диаграмма переходов приведена на рисунке 2.

Рисунок 2. Диаграмма состояний