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

Задание

Синтезировать автомат для преобразования двоично-десятичного кода с весами x1, x2, x3, x4, который поступает на вход в последовательной форме, начиная со старшего разряда, в двоично-десятичный код, с весами соответственно y1, y2, y3, y4, который снимают с выхода автомата также в последовательной форме, начиная со старшего разряда.

Таблица функционирования автомата

Вес
№	Х1	Х2	Х3	Х4	Y1	Y2	Y3	Y4

Таблица соответствия

Zдоп.	W*
Z0 Z0 Z0 Z0	W0 W0 W0 W0
Z0 Z0 Z0 Z1	W0 W0 W0 W1
Z0 Z0 Z1 Z1	W0 W0 W1 W0
Z0 Z1 Z0 Z0	W0 W1 W0 W0
Z0 Z1 Z0 Z1	W0 W1 W0 W1
Z0 Z1 Z1 Z1	W0 W1 W1 W0
Z1 Z0 Z0 Z0	W1 W0 W0 W1
Z1 Z0 Z1 Z0	W1 W0 W1 W0
Z1 Z0 Z1 Z1	W1 W0 W1 W1
Z1 Z1 Z0 Z0	W1 W1 W0 W1

Абстрактный синтез

Разметка автомата Мили по первой стратегии

Z₀ Z₀ Z₀ Z₀

W₀ W₀ W₀ W₀

_{1 2 3 4 1}

Z₀ Z₀ Z₀ Z₁

W₀ W₀ W₀ W₁

_{1 2 3 4 1}

Z₀ Z₀ Z₁ Z₁

W₀ W₀ W₁ W₀

_{1 2 3 5 1}

Z₀ Z₁ Z₀ Z₀

W₀ W₁ W₀ W₀

_{1 2 6 7 1}

Z₀ Z₁ Z₀ Z₁

W₀ W₁ W₀ W₁

_{1 2 6 7 1}

Z₀ Z₁ Z₁ Z₁

W₀ W₁ W₁ W₀

_{1 2 6 8 1}

Z₁ Z₀ Z₀ Z₀

W₁ W₀ W₀ W₁

_{1 9 10 11 1}

Z₁ Z₀ Z₁ Z₀

W₁ W₀ W₁ W₀

_{1 9 10 12 1}

Z₁ Z₀ Z₁ Z₁

W₁ W₀ W₁ W₁

_{1 9 10 12 1}

Z₁ Z₁ Z₀ Z₀

W₁ W₁ W₀ W₁

_{1 9 13 14 1}

Таблица переходов и выходов

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

Z0

a2 W0

a3 W0

a4 W0

a1 W0

- -

a7 W0

a1 W0

- -

a10 W0

a11 W0

a1 W1

a1 W0

a14 W0

a1 W1

Z1

a9 W1

a6 W1

a5 W1

a1 W1

a1 W0

a8 W1

a1 W1

a1 W0

a13 W1

a12 W1

- -

a1 W1

- -

- -

Разметка автомата Мили по второй стратегии

Z₀ Z₀ Z₀ Z₀

W₀ W₀ W₀ W₀

_{1 2 3 4 1}

Z₀ Z₀ Z₀ Z₁

W₀ W₀ W₀ W₁

_{1 2 3 4 1}

Z₀ Z₀ Z₁ Z₁

W₀ W₀ W₁ W₀

_{1 2 3 5 1}

Z₀ Z₁ Z₀ Z₀

W₀ W₁ W₀ W₀

_{1 2 3 4 1}

Z₀ Z₁ Z₀ Z₁

W₀ W₁ W₀ W₁

_{1 2 3 4 1}

Z₀ Z₁ Z₁ Z₁

W₀ W₁ W₁ W₀

_{1 2 3 5 1}

Z₁ Z₀ Z₀ Z₀

W₁ W₀ W₀ W₁

_{1 6 7 8 1}

Z₁ Z₀ Z₁ Z₀

W₁ W₀ W₁ W₀

_{1 6 7 4 1}

Z₁ Z₀ Z₁ Z₁

W₁ W₀ W₁ W₁

_{1 6 7 4 1}

Z₁ Z₁ Z₀ Z₀

W₁ W₁ W₀ W₁

_{1 6 5 8 1}

Таблица переходов и выходов

	a1	a2	a3	a4	a5	a6	a7	a8
Z0	a2 W0	a3 W0	a4 W0	a1 W0	a8 W0	a7 W0	a8 W0	a1 W1
Z1	a6 W1	a3 W1	a5 W1	a1 W1	a1 W0	a5 W1	a4 W1	- -

Разметка автомата Мура по первой стратегии

Z₀ Z₀ Z₀ Z₀

W₀ W₀ W₀ W₀

_{1 2 3 4 5}

Z₀ Z₀ Z₀ Z₁

W₀ W₀ W₀ W₁

_{1 2 3 4 6}

Z₀ Z₀ Z₁ Z₁

W₀ W₀ W₁ W₀

_{1 2 3 7 8}

Z₀ Z₁ Z₀ Z₀

W₀ W₁ W₀ W₀

_{1 2 9 10 11}

Z₀ Z₁ Z₀ Z₁

W₀ W₁ W₀ W₁

_{1 2 9 10 12}

Z₀ Z₁ Z₁ Z₁

W₀ W₁ W₁ W₀

_{1 2 9 13 14}

Z₁ Z₀ Z₀ Z₀

W₁ W₀ W₀ W₁

_{1 15 16 17 18}

Z₁ Z₀ Z₁ Z₀

W₁ W₀ W₁ W₀

_{1 15 16 19 20}

Z₁ Z₀ Z₁ Z₁

W₁ W₀ W₁ W₁

_{1 15 16 19 21}

Z₁ Z₁ Z₀ Z₀

W₁ W₁ W₀ W₁

_{1 15 22 23 24}

Таблица переходов и выходов

- a1

W0 a2

W0 a3

W0 a4

W0 a5

W1 a6

W1 a7

W0 a8

W1 a9

W0 a10

W0 a11

W1 a12

W1 a13

W0 a14

W1 a15

W0 a16

W0 a17

Z0

a2

a3

a4

a5

-

-

-

-

a10

a11

-

-

-

-

a16

a17

a18

Z1

a15

a9

a7

a6

-

-

a8

-

a13

a12

-

-

a14

-

a22

a19

-

	W1 a18	W1 a19	W0 a20	W1 a21	W1 a22	W0 a23	W1 a24
Z0	-	a20	-	-	a23	a24	-
Z1	-	a21	-	-	-	-	-

Разметка автомата Мура по второй стратегии

Z₀ Z₀ Z₀ Z₀

W₀ W₀ W₀ W₀

_{1 2 3 4 5}

Z₀ Z₀ Z₀ Z₁

W₀ W₀ W₀ W₁

_{1 2 3 4 1}

Z₀ Z₀ Z₁ Z₁

W₀ W₀ W₁ W₀

_{1 2 3 6 2}

Z₀ Z₁ Z₀ Z₀

W₀ W₁ W₀ W₀

_{1 2 7 2 3}

Z₀ Z₁ Z₀ Z₁

W₀ W₁ W₀ W₁

_{1 2 7 2 7}

Z₀ Z₁ Z₁ Z₁

W₀ W₁ W₁ W₀

_{1 2 7 6 2}

Z₁ Z₀ Z₀ Z₀

W₁ W₀ W₀ W₁

_{1 8 4 5 1}

Z₁ Z₀ Z₁ Z₀

W₁ W₀ W₁ W₀

_{1 8 4 1 2}

Z₁ Z₀ Z₁ Z₁

W₁ W₀ W₁ W₁

_{1 8 4 1 8}

Z₁ Z₁ Z₀ Z₀

W₁ W₁ W₀ W₁

_{1 8 6 5 1}

Таблица переходов и выходов

	W1 a1	W0 a2	W0 a3	W0 a4	W0 a5	W1 a6	W1 a7	W1 a8
Z0	a2	a3	a4	a5	a1	a5	a2	a4
Z1	a8	a7	a6	a1	-	a2	a6	a6

Минимизация автомата методом Пола и Ангера

Автомат Мили, полученный по второй стратегии.

	a1	a2	a3	a4	a5	a6	a7	a8
Z0	a2 W0	a3 W0	a4 W0	a1 W0	a8 W0	a7 W0	a8 W0	a1 W1
Z1	a6 W1	a3 W1	a5 W1	a1 W1	a1 W0	a5 W1	a4 W1	- -

Производим построение диаграммы пар совместимости для автомата типа Мили, построенному по второй стратегии

	2-3 6-3
	2-4 5-6	3-4 3-5
	1-2 1-6	1-3	1-4 1-5
	2-8 1-6	х	х	х
	2-7 5-6	3-7 3-5	4-7	1-7 1-5	х
	2-8 4-6	3-8 3-4	4-8 4-5	1-8 1-4	х	7-8 4-5
	1-2	х	х	х	х	х	х

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

	х
	х	х
	х	х	х
	х	х	х	х
	х	х	х	х	х
	х	х	х	х	х	х
	х	х	х	х	х	х	х

Совместимых состояний нет. Данный автомат является минимальным.

Поверка минимизированного автомата Мили, полученного по второй стратегии.

t= 1 2 3 4 z(t)=Z0 Z0 Z0 Z0 a(t)= a1 a2 a3 a4 w(t)=W0 W0 W0 W0	t= 1 2 3 4 z(t)=Z0 Z0 Z0 Z1 a(t)= a1 a2 a3 a4 w(t)=W0 W0 W0 W1	t= 1 2 3 4 z(t)=Z0 Z0 Z1 Z1 a(t)= a1 a2 a3 a5 w(t)=W0 W0 W1 W0	t= 1 2 3 4 z(t)=Z0 Z1 Z0 Z0 a(t)= a1 a2 a3 a4 w(t)=W0 W1 W0 W0	t= 1 2 3 4 z(t)=Z0 Z1 Z0 Z1 a(t)= a1 a2 a3 a4 w(t)=W0 W1 W0 W1
t= 1 2 3 4 z(t)=Z0 Z1 Z1 Z1 a(t)= a1 a2 a3 a5 w(t)=W0 W1 W1 W0	t= 1 2 3 4 z(t)=Z1 Z0 Z0 Z0 a(t)= a1 a6 a7 a8 w(t)=W1 W0 W0 W1	t= 1 2 3 4 z(t)=Z1 Z0 Z1 Z0 a(t)= a1 a6 a7 a4 w(t)=W1 W0 W1 W0	t= 1 2 3 4 z(t)=Z1 Z0 Z1 Z1 a(t)= a1 a6 a7 a4 w(t)=W1 W0 W1 W1	t= 1 2 3 4 z(t)=Z1 Z1 Z0 Z0 a(t)= a1 a6 a5 a8 w(t)=W1 W1 W0 W1

Таблица соответствия

Zдоп.	W*
Z0 Z0 Z0 Z0	W0 W0 W0 W0
Z0 Z0 Z0 Z1	W0 W0 W0 W1
Z0 Z0 Z1 Z1	W0 W0 W1 W0
Z0 Z1 Z0 Z0	W0 W1 W0 W0
Z0 Z1 Z0 Z1	W0 W1 W0 W1
Z0 Z1 Z1 Z1	W0 W1 W1 W0
Z1 Z0 Z0 Z0	W1 W0 W0 W1
Z1 Z0 Z1 Z0	W1 W0 W1 W0
Z1 Z0 Z1 Z1	W1 W0 W1 W1
Z1 Z1 Z0 Z0	W1 W1 W0 W1

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

Таблица переходов и выходов

	a1	a2	a3	a4	a5	a6	a7	a8
Z0	a2 W0	a3 W0	a4 W0	a1 W0	a8 W0	a7 W0	a8 W0	a1 W1
Z1	a6 W1	a3 W1	a5 W1	a1 W1	a1 W0	a5 W1	a4 W1	- -

1) Определим общее количество физических входов структурного автомата

L- общее количество физических входов структурного автомата

2^L≥F 2^L≥2 L=1

	X
Z0
Z1

2) Определим общее количество физических выходов структурного автомата

N- общее количество физических выходов структурного автомата

2^N≥G 2^N≥2 N=1

	Y
W0
W1

3) Определим общее количество элементов памяти структурного автомата

R- общее количество элементов памяти структурного автомата

2^R≥M 2^R≥8 R=3

	Q1	Q2	Q3
a1
a2
a3
a4
a5
a6
a7
a8

Словарь JK-триггера

F	J	K
		-
	-
α		-
β	-

Кодированная таблица переходов-выходов

t

t+1

FQ1

FQ2

FQ3

t

X

Q1

Q2

Q3

Y

Q1

Q2

Q3

J1

K1

J2

K2

J3

K3

α

-

-

-

α

β

-

-

-

α

-

-

-

β

β

-

-

-

α

α

-

-

-

α

β

-

-

-

α

-

-

-

β

β

β

-

-

-

α

α

-

-

-

α

β

-

-

-

α

β

-

-

-

β

β

-

-

-

β

-

-

-

β

-

-

-

β

α

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

Карта Карно на 4 переменных для Y

Q₂Q₃

XQ₁ 00 01 11 10

		-

10
Y=XQ₁+X Q₃+X Q₂+ Q₁ Q₂ Q₃

Карта Карно на 4 переменных для J₁

Q₂Q₃

XQ₁ 00 01 11 10

-	-	-	-
-	-	-	-

10
J₁=XQ₃

Карта Карно на 4 переменных для K₁

Q₂ Q₃

XQ₁ 00 01 11 10

-	-	-	-
		-
-	-	-	-

10
K₁=XQ₃+Q₂ Q₃

Карта Карно на 4 переменных для J₂

Q₂Q₃

XQ₁ 00 01 11 10

		-	-
		-	-
		-	-
		-	-

10
J₂=X Q₁+Q₁ Q₃

Карта Карно на 4 переменных для K₂

Q₂Q₃

XQ₁ 00 01 11 10

-	-
-	-
-	-	-
-	-

10
K₂= Q₃+XQ₁

Карта Карно на 4 переменных для J₃

Q₂Q₃

XQ₁ 00 01 11 10

	-	-
	-	-
	-	-
	-	-

10
J₃=X+ Q₁Q₂+ Q₁ Q₂

Карта Карно на 4 переменных для K₃

Q₂Q₃

XQ₁ 00 01 11 10

-			-
-			-
-		-	-
-			-

10
K₃=1

Система булевых функций

Y=X Q₁+X Q₃+X Q₂+ Q₁ Q₂ Q₃

J₁=XQ₃

K₁=XQ₃+Q₂ Q₃

J₂=X Q₁+Q₁ Q₃

K₂= Q₃+XQ₁

J₃=X+Q₁Q₂+ Q₁ Q₂

K₃=1