В первом билете

Билет

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

На этапе структурного синтеза предварительно выбираются элементарные автоматы, из которых затем путем их композиции строится структурная схема полученного на этапе абстрактного синтеза автомата Мили или Мура или С-автомата. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.

Теоретическим основанием канонического метода структурного синтеза автоматов является теорема о структурной полноте[i]

Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов-выходов и какую-либо функционально полную систему логических элементов, является структурно полной.

Существует общий конструктивный прием (канонический метод структурного синтеза), позволяющий в рассматриваемом случае свести задачу структурного синтеза произвольных автоматов к задаче синтеза комбинационных схем.

Результатом канонического метода структурного синтеза является система логических уравнений, определяющих выходные сигналы автомата и функции возбуждения элементов памяти. Эти уравнения называются каноническими.

Для правильной работы схемы нельзя разрешить, чтобы сигналы на входе запоминающих элементов непосредственно участвовали в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. В связи с этим запоминающими элементами должны быть не автоматы Мили, а автоматы Мура.

С учетом определения функций выхода автомата Мили и автомата Мура структурные схемы этих двух типов цифровых автоматов различаются, как показано на Рис. 3.