Пред.Страница  След.Страница   Раздел   Содержание


9.1.10.3 Структурная схема на основе регистра со сдвигом.

      Перейдем к описанию схем, блок памяти в которой и функции переходов выполнены на сдвигающем регистре . Рассмотрим вначале возможность построения такой схемы для автомата с одним входом и двоичным входным алфавитом. Допустим, что автомат задан полным размеченным деревом входных последовательностей. Закодируем состояния этого автомата следующим образом. Начальному состоянию припишем код 00 ... 01. Состояния остальных ярусов дерева кодируются последовательно в порядке увеличения номера яруса. Если состоянию si уже приписан код a1 , a2, ...,ah-1 ,ah и если под действием входного сигнала d из этого состояния автомат переходит в состояние sj, то состоянию sj припишем код         a2, ...,ah-1 ,ah d. Согласно этому правилу, код каждого следующего состояния получается из кода предыдущего состояния путем сдвига последнего влево на один разряд и записи входного сигнала в освободившийся последний разряд. При таком способе кодирования требуемое число двоичных разрядов h определяется числом ярусов дерева входных последовательностей. В качестве иллюстрации описанного способа на рис. 9.27 показано кодирование графа автомата, полученного из дерева входных последовательностей добавлением дуг, ведущих из узлов последнего яруса в начальный узел.

Рис. 9.27. Кодирование с использованием операции сдвига


Пред.Страница  След.Страница   Раздел   Содержание