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

Переходя к синтезу распознающего автомата, необходимо условиться о способе его реализации. Уже выбрана синхронная модель. Теперь примем соответствующую структурную схему, которая изображена на рис. 10.

р₁

Z

Z

дешифратор

Комбинационная схема

р₂

Х

Регистр 1

Регистр 2

z₅

р₃

z₆

t₂

t₁

НУ

Рис. 10 Структурная схема распознающего автомата

Она состоит из комбинационной схемы, реализующей функции возбуждения элементов памяти; памяти, построенной из триггеров по двухрегистровой схеме; дешифраторов входных сигналов. При синхронной реализации автомата нет необходимости бороться с функциональными и логическими состязаниями в комбинационной схеме и дешифраторе, так как предполагается, что все переходные процессы в этих схемах успевают закончиться в моменту прихода синхросигнала t₁, стробирующего прием информации с выходов комбинационной схемы в триггеры регистра 1. Второй триггерный регистр, прием информации в которой стробируется синхросигналом t₂, необходим для того, чтобы сделать все состояния устойчивыми и исключить влияние гонок. Триггеры регистра 1 – вспомогательные, регистра 2 – основные. Сигнал z₅ является сигналом ОШИБКА, z₆ – сигналом принадлежности входной цепочки символов языку с грамматикой G’’. С сигнала НУ осуществляется начальная установка основных триггеров автомата.

Дешифратор – устройство, преобразующее двоичный код символов, представленных переменными р₁, р₂ и р₃ в унитарный код, в котором только одна из выходных переменных принимает значение 1, в то время как все другие равны 0. Выходы дешифратора обозначим входными символами х₀ – х₇.

Таблица 8

&

x₀

1

1

р₁

1

1

...

символ	р1	р2	р3
х0	0	0	0
х1	1	0	0
х2	0	1	0
х3	1	1	0
х4	0	0	1
х5	1	0	1
х6	0	1	1
х7	1	1	1

р₂

x₀

1

р₃

x₀

&

1

1

1

Рис. 11 Схема дешифратора

Реализация дешифратора показана на рис. 11. Она содержит 8 элементов типа ЗИ-НЕ и 14 входных инверторов, причем 3 входных инвертора используются лишь с целью уменьшения нагрузки га входные символы.

Комбинационная схема автомата реализует функцию его переходов. Исходным заданием для ее построения является граф переходов (рис. 4) или таблица переходов (табл. 7) и выбранный вариант кодирования состояний. Построить функцию переходов – найти переключательную функцию кодирующих переменных. В соответствии со структурной схемой автомата каждая внутренняя переменная представляется состоянием элемента памяти – триггера. По переключательным функциям внутренних переменных могут быть найдены функции возбуждения соответствующих им триггеров. Реализация этих функций образует комбинационную схему автомата. Сложность функции возбуждения существенно зависит от выбора типа триггера. Известно три основных типа триггеров – D-триггер, RS-триггер и Т-триггер. Поскольку заранее невозможно отдать предпочтение ни одному из этих типов, необходимо построить функции возбуждения для всех указанных типов триггеров.

Функции возбуждения	Т-триггеров	Т4	x1 * x2 0	x7 * 0 0	0 * * 0	0 0 0 0	12	11
		Т3	x0 * 0 0	x3 * x4 x7	0 * * 0	0 0 0 x3	22	21
		Т2	0 * (x2vx5) 0	(x0vx3) * 0 0	0 * * x3	(x6vx5) x3 0 0	33	17
		Т1	0 * 0 x5	x0 * 0 x1	0 * * x3	(x0vx5) 0 x3 0	30	23
	RS-триггеров	R4	0 * 0 *	0 * * *	0 * * 0	0 0 0 0	0	0
		S4	x1 * x2 0	x2 * 0 0	* * * *	* * * *	10	7
		R3	0 * * *	x3 * x4 x7	* * * *	0 0 0 x3	15	15
		S3	x0 * 0 0	0 * 0 0	0 * * 0	* * * 0	4	4
		R2	* * (x2vx5) 0 0	0 * 0 0	* * * x3	0 0 0 0	11	7
		S2	0 * 0 *	(x0vx3) * * *	0 * * 0	(x6vx5) x3 * *	17	8
		R1	* * * x5	0 * * x1	* * * x3	0 0 0 0	10	10
		S1	0 * 0 0	x0 * 0 0	0 * * 0	(x0vx5) x3 * x3 *	16	10
	D-триггеров	D4	x1 * x2 0	x7 * 0 0	1 * * 1	1 1 1 1	11	15
		D3	x0 * 0 0	*	0 * * 0	1 1 1	24	21
		D2	0 * 1	(x0vx3) * 1 1	0 * *	(x5vx6) x3 1 1	28	21
		D1	0 * 0	x0 * 0	0 * *	(x0vx5) 1 x3 1	29	25
Код сост.		z1z2z3z4	0000 1000 0100 1100	0010 1010 0110 1110	0001 1001 0101 1101	0011 1011 0111 1111	О(f)	O(f)
Симв ол.			r0 r1 r7 r9	r6 r10 r5 -	r4 r3 - -	r2 r8 - -	Слож- ность МНДФ

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

D₁ = z₁z₃z₄Vx₀₂z₃₄V₁z₁z₃V₅z₁₃₄V(x₅Vx₀)₂z₃z₄V

V₃z₁z₄Vx₃₁z₂z₄=29

₁ = ₁₃V₁z₂₄V₀₄Vx₁z₂z₃₄Vx₅₃₄V

V(x₅Vx₀)₁₂z₄Vx₃₃z₄V₃₁z₂z₄=25

x₀Vx₃

D₂=z₂z₃Vz₁₄V(x₃Vx₀)z₃₄V()z₂₄V(x₅Vx₆)₁z₃z₄Vx₃z₁₂z₄V₃z₂z₄=28

₂ = ₂₃V()₂₄V(x₂Vx₅)₁₃V() ₁₂z₄V ₃z₁₂Vx_{3 3}z₄=21

₃

D₃= z_{1 2}V ₁z₃z₄V _{3 2}z_{3 4}V _{4 1}z₂z₃V ₇z₁z_{3 4}Vx_{0 2 3 4}V ₃z₃z₄=24

₃ = z_{2 3}V ₃z₄Vx_{3 2}z_{3 4}Vx_{4 1}z_{2 4}Vx₇z_{1 4}Vx₃z₁z₂z₄V _{0 3}=21

D₄ = z₄Vx_{7 2}z₃Vx_{1 2 3}Vx_{2 1}z_{2 3}=11

₄ = z_{1 4}Vz₂z_{3 4}V ₇z_{3 4}V _{1 2 3 4}V ₂z_{2 4}=15

S₁ =x_{0 2}z_{3 4}V(x₅Vx₀)₂z₃z₄Vx₃z₂z₃z₄=16

₁ =₃Vz₂₄Vx₀₄V ()₂z₄V₃z₂=10

R₁ = x₁z₁z₃₄Vx₅₃₄Vx₃₃z₄=10

₁ = ₁Vz₃z₄V₃z₄V₁z₃V₅₃₄=10

S₂ =(x₃Vx₀)z₃₄V(x₆Vx₅)₁z₃z₄Vx₃z₁₂=17

₂ = ₃V()₄V()₁z₄V₃z₁=8

R₂ =(x₅Vx₂)₁z₂₃Vx₃₃z₄=11

₂ = z₃Vz₁₄V()₄V₃z₄=7

S₃ = x₀₂₃₄=4

₃ =z₂Vz₃Vz₄V₀=4

R₃=x₇z₁₄Vx₃₂z₃₄Vx₄₁z₂₄Vx₃z₁z₂z₄=15

₃ =₃V₁z₄V₂z₄V₃z₄V₇z₁₄V₃₂V₄₁z₂=15

S₄ =x₇₂z₃Vx₁₂₃Vx₂₁z₂₃=10

₄ = ₂z₂V₇z₃V₁₂₃=7

R₄ =0

₄ =0

x₃

T₁ =x₀₂z₃₄Vx₁z₁z₃₄Vx₅z₁₃₄V(x₅Vx₀)₁₂z₃z₄Vx₃₁z₂z₄Vx₃z₁₃z₄=30

₁ =₁₃V₁z₂₄Vz₁z₃z₄V₀₂₄V₁z₂z₃V₅₃₄V()₂z₄V₃z₂z₄=23

x₀vx₃

x₃

T₂ =(x₀Vx₃)₂z₃₄V(x₂Vx₅)₁z₂₃V(x₆Vx₅)₁₂z₃z₄Vx₃z₁₂Vx₃z₁₃z₄=33

₂ =₂₃Vz₁₄Vz₂z₃V()z₂₄V()₁z₂V()₁z₄Vx₃z₁=17

x₄

T₃ =x₃₂z₃₄Vx₄₁z₂z₃₄Vx₇z₁z₃₄Vx₀₂₃₄Vx₃z₁z₂z₃z₄=22

₃ =z₂₃V₂z₄V₃z₄V₁z₄V₃₂z₃V₄₁z₂V₇z₁₄V₀₃V₃z₄=21

T₄ =x₇₂z₃₄Vx₁₂₃₄Vx₂₁z₂₃=12

₄ =z₄­Vz₁Vz₂z₃V₇z₃V₁₂₃V₂z₂=11

8. Реализация автомата

На рис.12 приведен набор элементов – интегральных микросхем (ИМС) малой степени интеграции – серии K155, рекомендуемый для построения автомата. Этот набор содержит семь логических элементов и два элемента памяти.

K155ЛА2

K155ЛА3

K155ЛА4

K155ЛА6

&

1

2

3

&

&

&

&

1

2

3

&

&

&

12

1

2

&

&

6

8

1

2

4

5

4

5

6

9

8

8

13

3

3

4

6

10

12

11

6

4

5

9

10

11

12

13

8

9

12

13

11

10

K155ЛP4

K155ЛP1

K155ЛP3

K155TM7

9

10

1

D1 TT A1 C2

D2 A2 C2

D3 A3 C3

D4 A4 C4

16

2

& 1

&

& 1

&

2

3

& 1

&

&

&

& 1

&

2

3

1

15

3

6

4

5

13

1

8

4

10

14

13

1

8

2

11

12

10

6

8

13

9

3

4

13

11

9

7

10

5

6

8

4

K155TB1

R T

& J C & K

S

13

8

3

4

5

12

9

6

10

11

2

Рис. 12 Рекомендуемый набор элементов ИМС серии К155

Систему функций возбуждения триггеров, выбранную для реализации дополним функциями возбуждения триггера ОШИБКА и Z₆. Выпишем эту систему функций, представления которых получены после выполнения этапа минимизации:

₁= ₃Vz₂₄Vx₀₄V()₂z₄V₃z₂;

R₁= x₁z₁z₃₄Vx₅₃₄Vx₃₃z₄;

₂=(x₀Vx₃)z₃₄V(x₆Vx₅)₁z₃z₄Vx₃z₁₂ ;

₂= z₃Vz₁₄V()₄V₃z₄;

S₃= x₀₂₃₄;

R₃= x₇z₁₄Vx₃₂z₃₄Vx₄₁z₂₄vx₃z₁z₂z₄;

₄= ₂z₂V₇z₃V₁₂₃;

R₄= 0;

S₅= z₁R₁V₁S₁V z₂R₂V₂S₂Vz₃R₃V₃S₃Vz₄R₄V₄S₄Vz_6;

R₅=0

z₆=x₈₁₂₃

9. Список используемой литературы

1. Поспелов Д. А. Логические методы анализа и синтеза схем. – М.: Энергия, 1974. – 368стр.

2. Герасимов И. В. Построение цифровых устройств в автоматике и вычислительной технике на современной элементной базе: Учеб. пособие / ЛЭТИ. – Л, 1984. – 49 с.

3. Букреев И. Н. Мансуров Б. М. Микроэлектронные схемы цифровых устройств. – М.: Сов. радио, 1975. – 386с.

4. Савельев А.Я. - Прикладная теория цифровых автоматов .1987

5. Самофалов К. Г. Прикладная теория цифровых автоматов. Киев, 1978

6. Карпов Ю.Г. - Теория автоматов . 2003(djvu)

18