Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов, страница 17

Рис.3.2

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

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

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

                                  x₁                                         y₁

                                          . . .                     . . .   

x_ly_n

Рис.3.3

Автомат имеет несколько структурных входных и выходных шин (рис.3.3), количество которых соответственно равно l=]log_qF[ и n=]log_qN[ , где ]A[ означает ближайшее целое число, большее A или равное ему, если A - целое, F - множество входных и N - множество выходных сигналов абстрактного автомата. Количество реальных входных и выходных цепей автомата можно определить из графа алгоритма работы автомата. Количество входных каналов автомата равно числу различных логических переменных (x_1,x₂,...x_l) в графе алгоритма, а выходных каналов - числу различных микроопераций  (y_1, y_2, ... y_n), вырабатываемых   автоматом.

На этапе структурного синтеза ставят в соответствие каждому абстрактному входному и выходному сигналам автомата соответствующие структурные сигналы. 

Так для автомата, граф алгоритма работы которого приведен на рис.3.1, абстрактные таблицы переходов и выходов на рис.3.2, существует следующее соответствие между абстрактными и структурными входными и выходными сигналами.

Входные сигналы:

 ,    _, ,       z₄ =x₁ ,   ,   

Выходные сигналы:

 ;         Y₂ =y₂  ;         ;         ;        

В рассматриваемом автомате имеются три входные шины x₁, x₂, x₃ и четыре выходные .

tR

t1

                                                                                                    x_{1  ..…}  x_l   

                              

           

КС

                                                П_{1            . . . . .}            П_R                                                 

               

                                    j₁j_R

                                 

y_{1  .….}  y_n

Рис.3.4.

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

Каждое состояние абстрактного автомата a_m кодируется в структурном автомате вектором (t_m1...t_mR), компонентами которого являются состояния элементов памяти П₁...П_R. При использовании триггеров и двоичного алфавита каждая компонента вектора может принимать только два значения (0 или 1). Если абстрактный автомат имеет М различных состояний, то для обеспечения кодирования каждого состояния своим кодом требуется m³]log₂ M[ триггеров.   

При изменении состояний элементов памяти осуществляется переход автомата из одного состояния в другое. Так, если автомат переходит из состояния a_m , закодированного с помощью двух триггеров Т₁ и Т₂ кодом 10 (триггер Т₁ находится в состоянии 1, а Т₂ - в 0), в состояние a₂, закодированное кодом 01, это означает, что триггер Т₁ переходит  из состояния 1 в 0, а триггер Т₂ - из состояния 0 в 1.

Синтез структурного автомата сводится к синтезу комбинационной схемы, реализующей функции:

y₁ = y₁ (t₁ , ... , t_R ,  x₁ , ... , x_L)

y₂ = y₂ (t₁ , ... , t_R ,  x₁ , ... , x_L)

.

.

.

y_n = y_n (t₁ , ... , t_R ,  x₁ , ... , x_L)