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

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

Синтез канонической структуры осуществляется  на основе :

- множества информационных слов S, которым ставятся в соответствие регистры той же разрядности (S_a,S_b1,...S_b2);

-  множества микроопераций   Y={y_1,y₂...y_m};

-  множества логических условий   X={x₁,x₂...x_l};

Каждой из операций ставится в соответствие оператор вида  S_a=j_m(S_b1,S_b2...S_bk), реализованный на структурном уровне следующей схемой (рис.2.3).

Каждому логическому условию ставится в соответствие комбинационная схема y_l  так, что  x_l=y_l(S_b1,S_b2...S_bq) (рис.2.4).

									xl
			ym

 

Sb2

Sa

jm

                     

                                                ^x                                             

 

Рис.2.3                                  Рис.2.4

Обладая максимальной производительностью каноническая структура является избыточной по затратам оборудования, так как все микрооперации, связанные с вычислением одного и того же слова, являются функционально-несовместимыми и могут быть реализованы меньшим количеством схем. Например, если кодопреобразователи j_m и j_n реализуют эквивалентные функции (рис.2.5), то для вычисления слова  S_a, используют один обобщенный оператор j (рис.2.6).

         

S_b1                                                                                           S_b1           y_m ,y_n

x

j_m       y_m                                y_m

S_b2                                    x                      S_b2     x            j                                                    

   

  .....                                    x                       ^{. . . . .}      x

j_n        y_n                                   S_bk         y_n

S_bk                                                                                                             

Рис.2.5                                             Рис.2.6                

Если в микропрограмме встречаются микрооперации вида S_a=j_m(S_a1,S_a2...S_aq) и S_b=j_m(S_b1,S_b2...S_bn), вычисляющие значения слов S_a и S_b с использованием одной функции j_m, применяемой к различным наборам значений (S_a1,...S_aq) и (S_b1,...S_bn), то оптимальный подход к синтезу устройства может предполагать использование только одного функционального кодопреобразователя. Однако, использование одной комбинационной схемы для выполнения нескольких микроопераций исключает совместимость этих микроопераций, то есть их выполнение возможно только в различных тактах. При этом производительность операционного устройства может значительно упасть.

Операционный автомат, производительность которого не ниже производительности автомата с канонической структурой, а затраты оборудования минимальны выделяется в класс I-автоматов (рис.2.7). Требуемая производительность может быть обеспечена только в том случае, если синтезируемая структура не будет вносить ограничений на совместимость микроопераций, поэтому для  I-автоматов характерно, что каждый из регистров обслуживается своей комбинационной схемой.