Схемы сравнения на равенство

Логическое условие А=В, где А=а₁а₂…а₄, В=b₁b₂…b₄n-разрядные слова, вычисляются комбинационной схемой, называемой схемой сравнения (по равенству). Значения А и В равны, если одновременно равны их одноименные разряды a_i, b_i, i=1,…,n. Таблица истинности, где

r_i – признак равенства значений a_i и b_i;

q_i - признак неравенства, представлена ниже:

Таблица истинности значений функций равенства и неравенства

ai	bi	ri	qi

r_i определяется следующей булевой функцией:

.

Признак равенства двух n-разрядных слов вычисляется как конъюнкция

R=r_1..r₂...r_n.

По вышеизложенным выражениям построена схема сравнения трехразрядных слов А и В (Рис. 3.11):

Рисунок 3.11 – Схема сравнения двух трехразрядных слов

Если значения слов представляются в парафазном коде цена n-разрядной схемы сравнения составляет 7nединиц по Квайну. Время сравнения, определяемое промежутком от момента поступления слов А, В до момента выработки осведомительного сигнала Rcоставляет t_ср=3t, где t - задержка сигнала на одном логическом элементе.

Схема, вычисляющая значения логического условия А¹К строятся аналогично. Из таблицы истинности следует, что значение признака неравенства q_iодноименных разрядов a_i, b_iслов А и В, определяется булевой функцией:

.

Слова А и В не равны, если хотя бы в одном разряде q_i=1.

3.6.3 Схемы сравнения на больше-меньше

Вычисление значения логического условия A>B, где А=а₁а₂…а_n, В=b₁b₂…b_nn-разрядные слова называется сравнением слов на больше-меньше. Значение A>B можно вычислить с помощью сумматора путем определения знака разности , где - дополнительный код значения А, используемый для замены операции вычитания на сложение. В соответствии с правилами машинной арифметики разность (В-А)<0, если перенос из старшего разряда суммы отсутствует, и разность (В-А)³0, если формируется перенос из старшего разряда суммы. Следовательно, отсутствие переноса свидетельствует об истинности отношения A>B, а наличие переноса – о ложности этого отношения. Если для вычисления отношения A>B должна использоваться специальная схема (нет необходимости в использовании сумматора), то для сравнения на больше-меньше используется n-подсхем формирования переносов. Такие подсхемы П объединяются в схему сравнения на больше-меньше в соответствии с рисунком 3.12:

Рисунок 3.12 – Схема сравнения на больше-меньше

На вход схемы подается обратный код слова А и прямой код b₁b₂…b_n слова В. Для получения дополнительного кода используется вход переноса в младший разряд P_n=1. Перенос из старшего разряда q_iопределяет значение отношения A>B: если q_i =0, то A>B, то есть отношение истинно, если q_i =1, то A≤B, то есть отношение ложно. Из рисунка видно, что цена одной схемы П составляет 8 единиц по Квайну и задержка сигнала переноса P_i-2t. Следовательно, цена схемы сравнения n-разрядных слов равна 8n единиц и время сравнения t_ср=2nt+t= (2n+1)t.

3.4 Контрольные вопросы

1. Перечислить основные операционные устройства ЭВМ и информационных систем.

2. Основные схемные варианты синхронных и асинхронных счетчиков.

3. Двоичные счетчики с различными коэффициентами пересчета.

4. Схемы сравнения чисел (на равенство,больше-меньше).

4 УПРАВЛЕНИЕ ИНФОРМАЦИОННЫМИ СИСТЕМАМИ БЕЗОПАСНОСТИ ПРОИЗВОДСТВЕННЫХ ПРОЦЕССОВ

В ВМ и информационных сетях преобразование информации осуществляется логическими схемами, которые подразделяются на 2 класса:

1. комбинационные схемы, или автоматы без памяти,

2. последовательностные схемы, или автоматы с памятью.

Вопросы синтеза комбинационных схем мы рассмотрели ранее.

В комбинационных схемах каждому набору (комбинации) входных сигналов соответствует определенная комбинация выходных сигналов.

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

На практике используются два типа моделей цифровых автоматов и, соответсвенно, два подхода к описанию закона функционирования автоматов: абстрактный и структурный.

Абстрактная модель наиболее распространена в теории автоматов. На практике абстрактная модель цифрового автомата позволяет произвести определенную оптимизацию схемы автомата, в первую очередь исключить так называемые лишние состояния автомата.

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

Абстрактная модель цифрового автомата (ЦА).

Абстрактный автомат (АА) – математическая модель дискретного устройства, определяемая упорядоченным множеством, состоящим из шести компонентов:

S = (A, Z, W,δ, λ, a₁ ), у которого

1. A = {a₁,…,a_m,…,a_M} – множество состояний (алфавит состояний);

2. Z = {z₁,…,z_f,…,z_F} – множество входных сигналов (входной алфавит);

3. W = {w₁,...,w_g,…,w_G} - множество выходных сигналов (выходной алфавит);

4. δ - функция переходов, определяющая порядок чередования внутренних состояний автомата. Другими словами, функция δ некоторым парам состояние – выходной сигнал (a_m, z_f)ставит в соответствие состояния автомата a_s = δ(a_m ,z_f), a_s ? A;

5. λ – функция выходов, задающая значения выходного сигнала в зависимости от значения входного сигнала (возможно и в неявном виде) и внутреннего состояния. Функция λ некоторым парам состояние – входной сигнал (a_m ,z_f) ставит в соответствие выходные сигналы автомата w_g = λ(a_m ,z_f);

6. a₁ ? A – начальное состояние автомата.

Абстрактный автомат имеет один вход, один выход и одно внутреннее состояние.

G

F

M

Z   W A

Рисунок 4.1 – Структура абстрактного автомата

где: F – количество входных состояний (входных сигналов),

M– количество внутренних состояний,

G– количество выходных состояний (выходных сигналов).

Автомат работает в дискретном времени, принимающим целые неотрицательные значения t = 0,1,2,.... В каждый момент дискретного времени автомат находится в определенном состоянии a(t) = a_m? Aиз множества состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии a(0)= a₁.

В момент времени t, будучи в состоянии a(t) автомат способен воспринять на входе букву входного алфавита z(t) ? Z. В соответствии с функцией выходов он выдает в тот же момент времени tбукву выходного алфавита w(t) = λ(a(t),z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1) = δ(a(t),z(t));a(t) ? A, w(t )? W.

Смысл понятия абстрактого автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Zв множество слов выходного алфавита W. Иначе, если на вход автомата, установленного в начальное состояние a_1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0),z(1),z(2),…- входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0),w(1),w(2),…-выходное слово. Относя к каждому входному слову соответствующее ему выходное слово, мы получим отображение µ, индуцированное абстрактным автоматом.

Таким образом, на уровне абстрактной теории понятие «работа автомата» понимается ка преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате мы отвлекаемся от его структуры – содержимого прямоугольника на рисунке 4.1, рассматривая его как «черный ящик» (принятый в кибернетике подход, когда основное внимание уделяется поведению системы относительно внешней среды). Такое абстрагирование от структуры устройства позволяет решить ряд сложных проблем, которые на структурном уровне скрываются за множеством деталей, несущественных с точки зрения поведения всей системы в целом. В каком-то смысле понятие абстрактного автомата в теории дискретныхустройств воплотило в себе системный подход, в отличие от структурного подхода, при котором свойства объекта определяются свойствами составляющих его элементов.

Автомат называется конечным, если конечны множества A,Z,W. Автомат называется полностью определенным, если для любой пары (a_m,z_f) ? AxZ, являющейся элементом произведения множества Aна множество Z, определены функции δ и λ.

У неполностью определенного, или частичного автомата функции δ и λ опрелены не для всех пар (a_m,z_f) ? A x Z.

4.2 Способы задания автоматов. Автоматы Мили и Мура.

Для задания конечного автомата ) необходимо описать все компоненты вектора S = (A, Z, W, δ, λ, a₁), т.е. входной и выходной алфавиты состояний, а также функции переходов и выходов. Среди множества состояний необходимо выделить состояние a₁ ,в котором автомат находится в момент времени t=0.

Закон функционирования автоматов может быть задан в виде:

- каноническом, или в виде уравнений,

- в виде таблиц, и

- в виде графов.

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

- автоматы Мура (E.F.Moore), и

- автоматы Мили (G.H.Mealy).

Автоматами Мура называют такие автоматы, у которых выходной сигнал w(t) не зависит явно от входного сигнала z(t), а определяется лишь внутренним состоянием автомата в момент времени t. Автомат Мура задается уравнениями:

a(t+1) = δ(a(t), z(t));

w(t) = λ(a(t)).}

В автомате Мили выходной сигнал в момент времени t зависит как от внутреннего состояния автомата в момент t, так так и от входногосигнала в момент времени t.

Функции переходов и выходов автомата Мили описываются уравнениями:

a(t+1) = δ(a(t), z(t));

w(t) = λ(a(t)), z(t)).

При табличном задании закона функционирования автомата Мили используются таблицы переходов и выходов (таблицы 4.1 и 4.2 соответственно).

Таблица 4.1 переходов автомата Мили Таблица 4.2 выходов автомата Мили

	a1	a2	a3			a1	a2	a3
z1	a2	a3	a2	z1	w1	w3	w3
z2	a3	a2	a1	z2	w2	w1	w1

Где: A={a₁,a₂,a₃}, Z={z₁,z₂}, W={w₁,w₂,w₃}.

Строки этих таблиц соответствуют входным сигналам, а столбцы – состояниям, причем причем крайний левый столбец обозначен начальным состянием a₁ . Входные сигналы и состояния, отмечаюие строки и столбцы таблиц, относятся к моменту времени t, т.е. отображают z(t) и a(t). На пересечении столбца a(t)=a_mи строки z(t)=z_fв таблице переходов ставится состояние a(t+1)=a_s=δ(a_m,z_f) в которое автомат переходит из состояния a_mпод действием сигнала z_f. В таблице выходов на пересечении столбца a(t)=a_mи строки z(t)=z_fставится соответствующий этому переходу выходной сигнал w(t)=w_g, определяемый функцией выходов w_g=λ(a_m,z_f).

По этим таблицам можно проследить последовательность работы автомата.В начальный момент времени t=0 автомат находится в исходном состоянии a(0)=a₁. Если на входе в момент времени t=0 будет действовать, например, сигнал z(0)=z₂, то автомат сформирует на выходе сигнал w₂=w(0)=λ(a(0), z(0)) и в следующий момент времени t=1 переключится в новое состояние a₃=a(1)=δ(a(0), z(0)). В момент времени t=1, автомат, находясь в состоянии a(1)=a₃, может воспринять на входе любой сигнал из множества Z, например, z(1)=z₂.Тогда автомат сформирует на выходесигнал w₁=w(1)=λ(a(1), z(1)) и в следующий момент времени t=2 перключится в новое состояние a₂=a(2)=δ(a(1),z(1) и т.д. Таким образом, если на вход автомата, предварительно установленного в начальное состояние a₁, подавать в последовательные моменты времени t=0,1,2,…, буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2),...- входное слово, то то на ваыходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1), w(2),…- выходное слово, при этом автомат будет последовательно переключаться в состояния a(1), a(2), a(3),…

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

Таблица 4.3. Совмещенная таблица переходов автомата Мили

	a1	a2	a3
z1	a2 w1	a3 w3	a2 w3
z2	a3 w2	a2 w1	a1 w1

Если функции переходов и выходов автомата определены не на всех упорядоченных парах символов (a_m,z_f) ? A x Z, то автомат по условию не полностью определенный, и поэтому некоторые клетки таблиц переходов и выходов (или совмещенной таблицы переходов и выходов) будут пусты. В этом случае в клетках таблиц ставятся прочерки. Пример таблиц переходов и выходов для частичного автомата Мили приведены в таблицах 4.4 и 4.5.

Таблица 4.4 переходов Таблица 4.5 выходов частичного

частичного автомата Мили автомата Мили

	a1	a2	a3			a1	a2	a3
z1	a2	a3	-	z1	w2	w2	-
z2	a1	-	a1	z2	w1	-	w3

Поскольку в автомате Мура выходной сигнал не зависит явно от входного сигнала, а зависит только от состояния, автомат Мура задается отмеченной таблицей переходов, в которой каждому ее столбцу приписан кроме состояния a_m еще и выходной сигнал w_g= λ(a_m), соответствующий этому состоянию (таблица 4.6).

Таблица 4.6. Отмеченная таблица

переходов автомата Мура

	w1	w1	w3	w2
a1	a2	a3	a4
z1	a2	a5	a2	a3
z2	a4	a2	a2	a1

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

Если в автомате Мили под действием входного сигнала z_f ? Z осуществляется переход из состояния a_m ? A в состояние a_s? A с выдачей выходного сигнала w_g ? W, то вершины графа a_m (исходное состояние) и a_s (состояние перехода) соединяются дугой, направленной от a_m к a_s, а дуга отмечается парой символов (z_f, w_g), как это показано на рисунке 4.1.

Рисунок 4.1 – Представление переходов автомата Мили

В общем случае переход автомата из состояния a_s ? A может происходить под действием нескольких входных сигналов, при каждом таком переходе может формироваться свой выходной символ. Очевидно, что в этом случае следует провести столько дуг из a_m в a_s сколько переходов имеется между ними, при этом каждая дуга должна отмечаться парой символов из Z и W. На рисунке 4.2 приведен граф автомата Мили, заданного ранее таблицами 4.1 и 4.2.

Рисунок 4.2 – Граф автомта Мили

Чтобы не загромождать изображение автомата графом, множество дуг, исходящих из вершины a_m и входящих в вершину a_s, заменяют одной дугой, отмечаемой дизъюнкцией пар символов, которыми размечаются исходные дуги.

При описании автомата Мура в виде графа выходной сигнал w_g = λ(a_s) записывается внутри вершины a_s или рядом с ней, а дуга, соответствующая переходу a_m в a_s отмечается входным сигналом z_f, под действием которого происходит этот переход. Если имеется множество дуг, исходящих из a_m и входящих в a_s, то они заменяются одной дугой, которую отмечают дизъюнкцией входных сигналов. Граф автомата Мура, ранее заданного отмеченной таблицей переходов, приведен на рисунке 4.3.

Рисунок 4.3 – Граф автомата Мура

Мы будем рассматривать только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Автомат, заданный таблицей переходов, всегда детерминированный, так как на пересечении столбца a_m и строки z_f записывается только одно состояние a_s = δ(a_m, z_f), если переход определен, и ставится прочерк, если функция δ на паре (a_m, z_f) не определена. Применительно к графическому способу задания автомата условие однозначности означает, что в графе автомата из любой вершины не могут выходить две и более дуги, отмеченные одним и тем же сигналом.

Минимизация абстрактных автоматов (АА)

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

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

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

Рассмотрим применение этого алгоритма для минимизации автомата Мили, заданного таблицами 45.7 и 4.8 переходов и выходов соответственно.

По таблице выходов получаем множество π₁ классов одноэквивалентных состояний путем объединения в эквивалентные классы столбцов с одинаковыми выходными сигналами. При этом:

π_{1 =} {B₁, B₂, B₃};

B_{1 =} {a₁ ,a₆}; B₂ = {a₂ , a₅}; B₃ = {a₃ , a₄}.

Таблица 4.7 переходов неми- Таблица 4.8 выходов неми-

нимального автомата Мили нимального автомата Мили

a1

a2

a3

a4

a5

a6

a1

a2

a3

a4

a5

a6

z1

a2

a5

a2

a5

a2

a2

z1

w2

w1

w1

w1

w1

w2

z2

a6

a2

a5

a3

a5

a6

z2

w2

w2

w2

w2

w2

w2

z3

a1

a6

a4

a5

a6

a1

z3

w1

w1

w2

w2

w1

w1

Строим таблицу π₁ (таблица 4.9) заменяя состояния в таблице переходов (таблица 4.7) соотвествующими классами одноэквивалентности. По таблице 4.9 получаем множество π₂ классов двухэквивалентных состояний (таблица 4.10), где: π₂ = {C₁,C₂,C₃,C₄}; C₁ = {a₁,a₆}; C₂ = {a₂,a₅}; C₃ = {a₃}; C₄ = {a₄}.

Таблица45.9. Разбиение π₁ на клас- Табица 4.10. Разбиение π₂ на классы

сы одноэквивалентных состояний двухэквивалентных состояний

B1

B2

B3

C1

C2

C3

C4

a1

a6

a2

a5

a3

a4

a1

a6

a2

a5

a3

a4

z1

B2

B2

B2

B2

B2

B2

z1

C2

C2

C2

C2

C2

C2

z2

B1

B1

B2

B2

B2

B3

z2

C1

C1

C2

C2

C2

C3

z3

B1

B1

B1

B1

B3

B2

z3

C1

C1

C1

C1

C4

C2

Далее производим разбиение π₃ = {D₁, D₂, D₃, D₄}; D₁ = {a₁, a₆};

D₂ = {a₂,a₅}; D₃ = {a₃}; D₄ = {a₄}, которое совпадает с π₂. На этом процедура разбиения заканчиватся. Разбиение π₂ есть разбиение множества состояний исходного автомата Мили на классы эквивалентных между собой состояний. Далее каждому классу эквивалентных состояний приписывается один и тот же символ внутреннего состояния. Таким символом, например, может быть символ внутреннего состояния с наименьшим порядковым номером. Возьмем, к примеру, в качестве множества состояний минимального автомата Мили A¹ = {a₁,a₂,a₃,a₄} – по одному из каждого класса C₁,C₂,C₃,C₄. Теперь из первоначальной таблицы переходов (таблица 4.7) и выходов (таблица 4.8) вычеркиваем лишние состояния a₅ и a_6, в чего получаем минимальный автомат Мили, эквивалентный исходному, и представленный таблицами 4.11 и 4.12 для переходов и выходов соответственно.

Таблица 4.11 переходов мини- Таблица 4.12 выходов мини-

мального автомата Мили мального автомата Мили

	a1	a2	a3	a4			a1	a2	a3	a4
z1	a2	a2	a2	a2	z1	w2	w1	w1	w1
z2	a1	a2	a2	a3	z2	w2	w2	w2	w2
z3	a1	a1	a4	a2	z3	w1	w1	w2	w2

Граф исходного неминимального автомата приведен на рисунке 4.4, а минимального – на рисунке 4.5.

Рисунок 4.4 – Граф исходного неминимального автомата

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

Структурный автомат (СА). Канонический метод структурного синтеза автоматов.

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

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

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

Структурный синтез автомата сводится к построению такой схемы, которая функционирует в соответствии с заданными таблицами переходов и выходов исходного абстрактного автомата. Структурный автомат имеет L входных каналов (входов), на которые поступают входные двоичные переменные x₁,…,x_l,…,x_L, N, и N выходных каналов, на которые выдаются выходные двоичные сигналы y₁,…,y_n,…,y_N, и R элементов памяти П₁,...Пr,...,П_R. Комбинационная часть структурного автомата вырабатывает выходные сигналы U₁,…,U_r,…,U_R, предназначенные для переключения элементов памяти и называемые сигналами переключения памяти (сигналами возбуждения элементов памяти). Сигналы Q₁,…Q_r,…,Q_R определяют состояние элементов памяти и, следовательно, состояние структурного автомата. Они поступают на вход комбинационной схемы, участвуя в выработке выходных сигналов автомата и сигналов переключения элеменов памяти, и называются сигналами обратной связи.

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

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

Для перехода от абстрактного автомата (АА) к его структурной схеме необходимо:

Поставить в соответствие каждой букве входного алфавита z_f, где

f = 1,…,F совокупность значений двоичных сигналов x₁,…,x_l на входных каналах, т.е. закодировать входные сигналы АА. Количество L физических входов структурного (СА) определяют из условия L≥ }log₂F{, выбирая ближайшее целое число.

1. Поставить в сответствие каждой букве выходного алфавита w_g,

g = 1,…,G, совокупность значений двоичных выходных сигналов СА y₁,…y_n,…y_N на его выходных каналах, т.е. закодировать выходные сигналы АА. Количество N физических выходов СА определяется из условия N ≥} log₂G{.

2. Поставить в соответствие каждому состоянию АА a₁,…a_m,…,a_M

совокупность состояний элементов памяти Q_!,…,Q_r,…,Q_R, т.е. закодировать состояния АА. Количество R элементов памяти определяют из условия

R≥ }log₂M{, где - }a{ означает ближайшее целое число, большее a,или равное ему, если a – целое.

3. Составить систему логических уравнений для функций y1,…,y_r,…,y_R,

U₁,…,U_r,…,U_R. Эти функции определяют структуру комбинационной схемы автомата.

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

y₁ = y₁ (Q₁,…,Q_R, x₁,…,x_L),

y₂ = y₂ (Q₁,…,Q_R, x₁,…,x_L),

. . . . . . . . . . . .

y_N = y_N (Q₁,…,Q_R, x₁,…,x_L),

U₁= U₁ (Q₁,…,Q_R, x₁,…,x_L),

U₂= U₂ (Q₁,…,Q_R, x₁,…,x_L),

. . . . . . . . . . . .

U_R= U_R (Q₁,…,Q_R, x₁,…,x_L).

Эта система уравнений называется канонической.

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

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

Пример канонического метода структурного синтеза автоматов на Т-триггерах

Пусть задан частичный автомат Sтаблицами переходов и выходов (таблицы 4.13 и 4.14 соответственно).

Таблица 4.13 переходов автомата S Таблица 4.14 выходов автомата S

	a1	a2	a3			a1	a2	a3
z1	a3	a1	a1	z1	w2	w1	w1
z2	-	a3	a2	z2	-	w3	w2
z3	a2	-	a1	z3	w4	-	w1

Таблица переходов элементарного автомата памяти типа Т-триггера приведена в таблице 4.15, где символом Т обозначен входной сигнал триггера.

Таблица 4.15 переходов Т-триггера

Q T		Q(t) 1
		Q(t+1) 1

T(t)

Определяем количество входов структурного автомата L ≥ log₂3. L = 2. Кодируем входные сигналы автомата S, результаты заносим в таблицу 4.16.

Определяем количество выходов структурного автомата N ≥