5: Синтез структурного автомата

5.1 Структурный автомат

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

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

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

Рис. 5.1.

В структурном автомате учитывается структура входных и выходных сигналов, то есть их конкретное представление в виде двоичных векторов. Состояния автомата так же кодируются двоичными векторами.

Рассмотрим совмещенный автомат (рис.5.2). Каждое состояние  абстрактного автомата кодируется двоичным вектором:

,

 ;

 - число состояний абстрактного автомата;

 - число элементов памяти.

Рис. 5.2.

Входной и выходные сигналы представляются также двоичными векторами:

• , ,  - число входных сигналовабстрактного автомата,  - число входов структурного автомата ;
• ,  - число выходных сигналов 1 типа,  -число выходов 1 типа структурного автомата ;
• ,  - число выходных сигналов 2 типа,  - число выходов 2 типа структурного автомата

5.2 Канонический метод структурного синтеза автоматов

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

Рис. Об этом говорит сайт https://intellect.icu . 5.3.

Комбинационная схема 2 предназначена для формирования выходных сигналов 2 типа  как функций с выходов элементов памяти .

Так как в автомате Мили сигналы 2 типа отсутствуют, то, соответственно в структурной схеме отсутствует комбинационная схема 2. Схема структурного автомата Мили показана на рис.5.4.

Рис. 5.4.

В автомате Мура сигналы 1 типа отсутствуют, следовательно, в структурной схеме в комбинационной схеме 1 отсутствуют выходные сигналы 1 типа . Схема структурного автомата Мура показана на рис.5.5.

Рис. 5.5.

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

•  ;
•  ;
• . . .
• 
• 
• 
• . . .
• 
• 
• 
• . . .
• 

5.4.Этапы синтеза

1. Находим количество элементов памяти , (  - число состояний абстрактного автомата) и кодируем состояния абстрактного автомата (табл.5.1).

   Таблица 5.1.

   am\
   a1
   a2
   …
   aM

    
2. Кодируем входные и выходные сигналы, то есть
   • находим количество входов структурного автомата , (  - число входных сигналовабстрактного автомата);
   • количество выходов 1 типа  ; (  - число выходных сигналов 1 типа);
   • количество выходов 2 типа , (  - число выходных сигналов 2 типа) и кодируем входные (табл.5.2) и выходные сигналы (табл.5.3) и (табл.5.4) абстрактного автомата.

     Таблица 5.2.

     z f / x 1	xL x1x2…x1
     z
     z
     …
     z

      

     Таблица 5.3.

     wf/y 1y2…yN	y 1y2…yN
     w1
     w2
     …
     wG

      

     Таблица 5.4.

     uh/r 1 r2…rD	r 1 r2…rD
     u1
     u2
     …
     uH

      
    
3. Структурный автомат представляем обобщенной схемой (рис.5.6).
   

   
   Рис. 5.6.
    
4. Составляем закодированную таблицу выходов автомата и по ней записываем уравнения выходов.
   •  ;
   •  ;
   • . . .
   •  ;
   •  ;
   •  ;
   • . . .
   •  ;
   • . . .
    
5. Составляем закодированную таблицу переходов автомата и по ней записываем уравнения для функций возбуждения, используя таблицы переходов соответсвующих элементов памяти.
   •  ;
   •  ;
   • . . .
   •  ;
    
6. Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ}).