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

Y1        R                                                  D                                            S1                                  x1                          F1                                     y1               Y2                                                                        F2                                              S2                    y2          x2          Yn                      .....                    .....                                                                                                            xl                         Fn                   Sn                              yl

                                           

Рис.2.7.   I-автомат

Синтез I-автоматов состоит из следующих этапов:

1. Множество микроопераций Y={y₁,y_2,...y_m} разбивается на подмножества Y₁,Y₂,...Y_n соответствующие словам  S₁, S₂ . . .S_n.

2. На подмножестве Y_i (i=1,n) выделяются классы  эквивалентных микроопераций k_ij.

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

4. На основе содержательного графа с использованием обобщенных операторов строится структура I-автоматов.

А2

При выполнении операций затраты оборудования в комбинационной части автомата можно минимизировать, если каждую комбинационную схему j_m обобщить по отношению ко всем регистрам (словам S₁,...S_n), то есть использовать каждую комбинационную схему j_m  для выполнения всех эквивалентных микроопераций. Такой операционный автомат, синтезированный по принципу обобщения всех комбинационных схем, выделяется в класс M-автоматов (рис.2.8).

 

x                      x                          x

Любая микрооперация, выполняющая преобразования j_m, реализуется с помощью общей комбинационной схемы Ф равнодоступной каждому регистру устройства. Информация на схему Ф поступает по информационным шинам А₁, А₂ под действием соответствующих управляющих сигналов а_iÎ{a₁,a₂,...a_n} и b_jÎ{b₁,b₂,...,b_n}. Комбинационная схема Ф под действием управляющего сигнала j_m реализует функцию Z=j_m(A₁,A₂), результат выполнения которой выдается на шину Z и под действием сигнала d_kÎ{d₁,d₂,...d_n} записывается в регистр S_k. Таким образом, для реализации микрооперации S_k:=j_m(S_i,S_j) в M-автомат поступает специфичный набор управляющих сигналов: a_i, b_j, j_m, d_k, который в свою очередь порождает собственный набор микроопераций: {A₁:=S_i}, {A₂:=S_j}, {Z:=j_m(A₁,A₂)}, {S_k:=Z}. Организация комбинационной схемы y, формирующей логические условия, не отличается от канонической структуры, так как, в противном случае, при последовательном анализе условий схема значительно бы усложнилась. Дальнейшая минимизация схемы операционного автомата возможна за счет объединения шин, по которым информация передаётся в комбинационную схему Ф.

В общем  случае для подключения регистров необходимо наличие двух управляемых шин. Но далеко не всегда каждый регистр подключается к обеим обобщенным шинам A₁, A₂. В общем случае количество их может колебаться от m до 2m. Минимизация числа управляющих шин сводится к разделению множества числа слов S на два подмножества: которые должны удовлетворять следующим условиям:

1)  Если слова S_i и S_j участвуют в одной и той же микрооперации, они должны находится в разных подмножествах, то есть S_iÎA₁, S_jÎA₂  или S_iÎA₂ ,  S_jÎA₁.

2)  Каждое слово должно входить хотя бы в одно из подмножеств.

3)  Распределение слов по подмножествам должно производиться таким образом, чтобы затраты оборудования в схемах передачи операндов с регистров на схему Ф были минимальными.