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

 

 

A=B

A = a₁ a₂ a₃ a₄ … a_n B = b₁ b₂ b₃ b₄ … b_n

a	b	r - равенство	q - неравенство

R = r₁ r₂ r₃ r₄ … r_n r_i=a_ib_i + _{i i}

q_i= _i b_i + _i a_i = Q = q₁ q₂ q₃ q₄ … q_n

 

42. Схемы сравнения слов на > и <.

 

A<B

A
B
Bдк	0.1
-Адк	1.1
B-A	10.0

Первая цифра из 10.0 – это р (знак переноса) р=1

A>B

A
B
Bдк	0.0
-Адк	1.0
B-A	01.0

Первая цифра из 01.0 – это р (знак переноса) р=0

A<B если p = 1 A>B если p = 0

 

 

43. Принципы построения микропрограммных автоматов с "жесткой логикой". Абстрактная и структурная модели цифровых автоматов.

В управляющих автоматах на элементах с жесткой логикой - для хранения информации о состоянии используется набор триггеров, на их тактовый вход подается тактирующий сигнал, входные сигналы X подаются на комбинационные устройства, вырабатывающие сигналы управления для (функции возбуждения) триггеров. Выходные сигналы Yформируются при помощи других комбинационных схем из выходных сигналов триггеров A (для автомата Мили) или из выходных сигналов триггеров Aи входных сигналов Y (для автомата Мура, именно его блок схема представлена на рисунке).

 

 

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

выбор типа запоминающих и логических элементов;

кодирование состояний автомата;

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

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

Абстрактным автоматом называют дискретный преобразователь информации с конечным входным алфавитом Z= {z1,..., zf,...,zF}, конечным выходным алфавитом W = {w1,..., wg,...,wG}, конечным множеством внутренних состояний A = {a1,..., am,...,aM} и двумя характеристическими функциями: функцией переходов δ и функцией выходов λ.

Абстрактный автомат имеет один входной и один выходной каналы. Функционирование автомата происходит в дискретные моменты автоматного времени, ход которого обозначается натуральными числами i = 0, 1, 2,...

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

Абстрактный автомат называется конечным, так как множества A, Z, W конечны. Кроме того, он называется полностью определенным, если для любой пары (a_m, z_f) определены функции δ и λ. У частичного автомата функции δ и λ определены не для всех пар (а_m, z_f). При рассмотрении функционирования автомата считается, что исходным состоянием в момент t = 0 является а(0)=а1, которое называется начальным состоянием.

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

Существует 3 способа задания автоматов:

- канонический метод

-табличный метод

- граф

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

 

В автоматах Мили - выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент времени (t-1). Математической моделью таких автоматов служит система уравнений:

 

q(t) = δ (g(t-1), х(t)) и y(t) = λ (g(t-1), х(t)),

 

В автоматах Мура выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени t.Математической моделью таких автоматов является система:

 

q(t) = δ (g(t-1), х(t)) и y(t) = λ (g(t)),

 

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

 

1)Таблица

.

as=δ(am, zf)Таблица переходов автомата Милли

 

	a1	a2	a3
z1	a3	a2	а2
z2	а1	a3	a1

Wg= λ(am, zf)Таблица выходов

	a1	a2	a3
z1	w1	w3	w2
z2	w2	w2	w1

Совмещенная таблица автомата Милли

	a1	a2	a3
z1	a3/w1	a2/w3	а2/w2
z2	а1/w2	a3/w2	a1/w1

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

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

 

2) граф

Вершины-состояния

Дуги-переходы

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

 

В автоматах Мили - выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент времени (t-1). Математической моделью таких автоматов служит система уравнений:

 

q(t) = δ (g(t-1), х(t)) и y(t) = λ (g(t-1), х(t)),

 

В автоматах Мура выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени t.Математической моделью таких автоматов является система:

 

q(t) = δ (g(t-1), х(t)) и y(t) = λ (g(t)),

 

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