9.1.10 Структурные схемы, использующие типовые блоки цифровых устройств.

      Если работа автомата задается оператором неавтоматного вида, то его необходимо преобразовать таким образом, чтобы он стал автоматным. Напомним, что такое преобразование выполняется путем применения операций выравнивания и пополнения. В результате применения этих операций длина перерабатываемых слов, состоящих из n букв, может увеличиться на (n - 1) пустую букву. Такое увеличение длины эквивалентно внесению задержки между последовательностью входных и выходных сигналов.    

9.1.10.1 Структурная схема с запоминанием входного слова.

      Если по условию работы автомата допустима задержка в n тактов, то можно использовать универсальную схему для реализации операторов как автоматного, так и неавтоматного вида. Принцип работы такой схемы основан на том, что в течение первых n тактов входное слово х₁, х₂, ..., х_nзапоминается, а в следующие n тактов осуществляется последовательное считывание букв выходного словаz₁, z₂, ..., z_n. При этом буквы выходного слова вырабатываются одновременно комбинационной схемой, на вход которой, начиная с n-го такта, в виде параллельного кода подаются буквы входного слова.       Структурная схема автомата, реализующего предложенный принцип, приведена на рис. 25. Схема состоит: из ряда схем “И”, разрешающих запись букв входного слова на элементы памяти ЭП1 - ЭПh; второго ряда схем “И”, используемых для образования выходного слова; комбинационной схемы и распределителя, который построен на основе счетчика (С) с дешифратором (ДС).

9.1.10.2 Структурная схема на основе счетчика.

      Структурная схема автомата, память которого выполнена в виде двоичного счетчика и шифратора, изображена на рис. 26.

Счетчик, используемый в схеме, должен иметь один счетный вход и несколько установочных входов, на которые подаются сигналы y₁', y₂', ..., y_h'. Сигнал, подаваемый на счетный вход, изменяет состояние счетчика таким образом, что двоичное число, соответствующее новому состоянию, получается всегда путем увеличения на единицу двоичного числа, соответствующего старому состоянию. Установочные входы позволяют заносить в счетчик произвольный код. Сигналы на установочные входы подаются с выходов шифратора. Обычно на входе шифратора либо все сигналы равны нулю, либо имеется только один сигнал, отличный от нуля. Каждый такой сигнал преобразуется шифратором в совокупность выходных сигналовy₁', y₂', ..., y_h' , определяющих новое состояние счетчика. Практически схема шифратора в большинстве случаев представляет собой совокупность схем “ИЛИ”, с выходов которых снимаются сигналыy₁', y₂', ..., y_h'. Каждый входной сигнал шифратора r_jподается на входы всех тех схем “ИЛИ”, на выходе которых должен быть получен сигнал, равный единице. Для того чтобы осуществить задержку перехода в новое состояние, в приведенной схеме либо используют счетчик с удвоенным числом элементов памяти, либо включают в схему дополнительный регистр, в котором сохраняется старое состояние.

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

      Перейдем к описанию схем, блок памяти в которой и функции переходов выполнены на сдвигающем регистре . Рассмотрим вначале возможность построения такой схемы для автомата с одним входом и двоичным входным алфавитом. Допустим, что автомат задан полным размеченным деревом входных последовательностей. Закодируем состояния этого автомата следующим образом. Начальному состоянию припишем код 00 ... 01. Состояния остальных ярусов дерева кодируются последовательно в порядке увеличения номера яруса. Если состоянию s_iуже приписан код₁,₂, ...,_h-1 ,_hи если под действием входного сигналаиз этого состояния автомат переходит в состояние s_j, то состоянию s_jприпишем код₂, ...,_h-1 ,_h . Согласно этому правилу, код каждого следующего состояния получается из кода предыдущего состояния путем сдвига последнего влево на один разряд и записи входного сигнала в освободившийся последний разряд. При таком способе кодирования требуемое число двоичных разрядов h определяется числом ярусов дерева входных последовательностей. В качестве иллюстрации описанного способа на рис. 27 показано кодирование графа автомата, полученного из дерева входных последовательностей добавлением дуг, ведущих из узлов последнего яруса в начальный узел.