lec14

Доказательство (продолжение):

Представим линии задержки в виде схемы автоматов следующего вида: есть входящий сигнал х(t), есть полный автомат Мура М, логические блоки F и Ф, то есть комбинационные схемы, содержащие функциональные элементы f1…fS, F – блок выхода. Ф – блок возбуждения памяти.

Они формируются следующим образом. Так как М – полный автомат Мура, то берем фиксированные два состояния q0 и q1 QM и будут существовать буквы а0 и а1, так что для q при подаче на вход М буквы а0 переведет автомат М из состояния q1 в состояние q0, а при подаче на вход а1 переведет автомат М из состояния q0 в состояние q1.

q(t-1)

x(t)											z(t)
			Ф			M
										F

11

Доказательство (продолжение):

Пусть блок Ф выдает букву а0, если на вход получил х(t)=0, а автомат М находился в состоянии q, и выдает букву а1, если на вход подается х(t)=1, а автомат М находится в состоянии q, то есть если на вход блока Ф послать сигнал 0, то блок Ф выработает сигнал, переводящий автомат М в состояние q0, а если на вход блока Ф послать сигнал 1, то блок Ф выработает сигнал, переводящий автомат М в состояние q1.

Блок F на состояние q0 создает символ 0, а на состояние q1 символ 1, а на остальных состояниях выход доопределяем произвольным образом. Такой автомат работает как элемент задержки.

Если на вход х(t)=0, то выход Ф равен a0(q), то есть q → q0, а на выходе F будет 0, но через один такт (так как стоит полный автомат Мура).

Если на вход х(t)=1, то выход Ф равен a1(q), то есть q → q1, а на выходе F будет 1, но через один такт.

q(t-1)

x(t)

z(t)

Ф

M

F

12

x(t) \ q(t–1)	0	1
0	0	0
1	1	1
R S	0	1
0 0	0	1
0 1	1	1
1 0	0	0
1 1	-	-

Пример 14.2. Получение элемента задержки из RS-триггера.

x(t)

R z(t)

S

Таблицы управления памятью.

ДНФ для R, S, z(t).

x(t) \ q(t–1)	0	1	x(t) q(t–1)		R	S
	R S R S
			0	0	-	0	R =	x(t)
0	0 0	1 0	0	1	1	0	S =	? x(t)
	1 0		1	0	0	1	z(t) = q(t–1)
1	0 1	0 0	1	1	0	-
		0 1
								13

Часть 3.

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

Пусть задана некоторая автоматно полная система Σ.

Cтруктурный синтез – это представление автомата схемой (ССА) над Σ.

Канонический синтез (алгоритм Хоффмана-Глушкова):

1)По описанию автоматного отображения составляется автоматная таблица.

2)Минимизируется число состояний полученного автомата.

3)Производится двоичное кодирование алфавита.

4)Строится автоматная таблица для полученного логического автомата.

5)Строится таблица управления памятью по полному автомату Мура.

6)Записываются канонические уравнения и уравнения для управляющих памятью функций.

7)Функции реализуются в виде схем.

15

Пример14.1. Структурный синтез ССА по автоматному отображению.

x1	0	y1	0	Q1	0	0	Битовое		X		Q
										0	1
							кодирование
x2	1	y2	1	Q2	0	1		T-триггер.
							входов X,		0	0		1
	x		y	Q3	1	0
							выходов Y,		1	1		0
					q1	q2
							состояний Q.		ψ(q)	0		1

	X \ Q	Q1	Q2	Q3	кодировка
	x1	Q2/y1	Q3/y2	Q2/y1
					таблицы
	x2	Q1/y2	Q2/y1	Q1/y1

X \ q1 q2 0 0 0 1 1 0 1 1
0	0 1/0	1 0/1	0 1/0	-
1	0 0/1	0 1/0	0 0/0	-

ψ1	X \ q1 q2 0 0 0 1 1 0 1 1					ψ2	X \ q1 q2 0 0 0 1 1 0 1 1
	0	0	1	1	-		0	1	1	1	-
	1	0	0	1	-		1	0	0	0	-

16

ТИ для ψ1, ψ2, y(t).

x(t) q1(t–1) q2(t–1)			ψ1 ψ2 y
0	0	0	0	1	0
0	0	1	1	1	1
0	1	0	1	1	0
0	1	1	-	-	-
1	0	0	0	0	1
1	0	1	0	0	0
1	1	0	1	0	0
1	1	1	-	-	-

	ДНФ для ψ1, ψ2, y(t).
ψ1 =	x(t)·q2(t–1) q1(t–1)
ψ2 =	x(t)
y(t) =	x(t)·q1(t–1)·q2(t–1) x(t)·q1(t–1)·q2(t–1)	17

x(t)

q1(t-1)

q2(t-1)

	ψ2
ψ1	T2

T1

Схема из ФЭ для ψ1, ψ2, y(t).

y(t)

	ψ1 =	x(t)·q2(t–1) q1(t–1)
	ψ2 =	x(t)	18
	y(t) =	x(t)·q1(t–1)·q2(t–1) x(t)·q1(t–1)·q2(t–1)