Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Алгоритм синтеза автомата

Алгоритм синтеза автомата

Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 14.10.2012
Размер файла 141,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

26

2

Размещено на http://www.allbest.ru/

Алгоритм синтеза автомата

Содержание

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

1. Техническое задание

2. Таблица функционирования и соответствия

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

3.1 Разметка вход-выходных слов для автомата Мили

3.2 Разметка вход-выходных слов для автомата Мура

3.3 Минимизация автомата

4. Структурный синтез

4.1 Кодировка алфавитов и состояний

4.2 Построение булевых функций

4.3 Раздельная минимизация

4.4 Факторизация и совместная минимизация

4.5 Реализация на элементах малой степени интеграции (К155)

1. Техническое задание

Синтезировать автомат для преобразования двоично-десятичного кода с весами х1=3, х2=3, х3=2, х4=1, который поступает на вход в последовательной форме, начиная со старшего разряда, в двоично-десятичный код с весами у1=5, у2=3, у3=2, у4=1, который снимается с выхода автомата в последовательной форме, начиная со старшего разряда.

2. Таблицы функционирования и соответствия

Ниже приведена одна из возможных таблиц соответствия входных и выходных слов

Веса входного слова

Веса выходного слова

х1

х2

х3

х4

у1

у2

у3

у4

№

3

3

2

1

5

3

2

1

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

1

2

0

0

1

0

0

0

1

0

3

0

0

1

1

0

0

1

1

4

0

1

0

1

0

1

0

1

5

0

1

1

0

0

1

1

0

6

0

1

1

1

0

1

1

1

7

1

1

0

1

1

0

1

0

8

1

1

1

0

1

1

0

0

9

1

1

1

1

1

1

0

1

Автоматное отображение

№ Z доп.

W*

0

Z0

Z0

Z0

Z0

C

C

W0

W0

W0

W0

1

Z0

Z0

Z0

Z1

C

C

W0

W0

W0

W1

2

Z0

Z0

Z1

Z0

C

C

W0

W0

W1

W0

3

Z0

Z0

Z1

Z1

C

C

W0

W0

W1

W1

4

Z0

Z1

Z0

Z1

C

C

W0

W1

W0

W1

5

Z0

Z1

Z1

Z0

C

C

W0

W1

W1

W0

6

Z0

Z1

Z1

Z1

C

C

W0

W1

W1

W1

7

Z1

Z1

Z0

Z1

C

C

W1

W0

W1

W0

8

Z1

Z1

Z1

Z0

C

C

W1

W1

W0

W0

9

Z1

Z1

Z1

Z1

C

C

W1

W1

W0

W1

Полученное автоматное отображение удовлетворяет следующим условиям:

1. автоматное отображение является однозначным;

2. автоматное отображение сохраняет длину слова;

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

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

3.1 Разметка вход-выходных слов для автомата Мили

3.1.1 Первая стратегия

0

z0

z0

z0

z0

c

c

w0

w0

w0

w0

a1

a2

a3

a4

a5

a1

1

z0

z0

z0

z1

c

c

w0

w0

w0

w1

a1

a2

a3

a4

a6

a1

2

z0

z0

z1

z0

c

c

w0

w0

w1

w0

a1

a2

a3

a7

a8

a1

3

z0

z0

z1

z1

c

c

w0

w0

w1

w1

a1

a2

a3

a7

a9

a1

4

z0

z1

z0

z1

c

c

w0

w1

w0

w1

a1

a2

a10

a11

a12

a1

5

z0

z1

z1

z0

c

c

w0

w1

w1

w0

a1

a2

a10

a13

a15

a1

6

z0

z1

z1

z1

c

c

w0

w1

w1

w1

a1

a2

a10

a13

a15

a1

7

z1

z1

z0

z1

c

c

w1

w0

w1

w0

a1

a16

a17

a18

a19

a1

8

z1

z1

z1

z0

c

c

w1

w1

w0

w0

a1

a16

a17

a20

a21

a1

9

z1

z1

z1

z1

c

c

w1

w1

w0

w1

a1

a16

a17

a20

a22

a1

Проверка :

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z0

z0

c

z(t)

z0

z0

z0

z1

c

z(t)

z0

z0

z1

z0

c

a(t)

a1

a2

a3

a4

a5

a1

a(t)

a1

a2

a3

a4

a6

a1

a(t)

a1

a2

a3

a7

a8

a1

w(t)

с

w0

w0

w0

w0

w(t)

с

w0

w0

w0

w1

w(t)

с

w0

w0

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z1

z1

c

z(t)

z0

z1

z0

z1

c

z(t)

z0

z1

z1

z0

c

a(t)

a1

a2

a3

a7

a9

a1

a(t)

a1

a2

a10

a11

a12

a1

a(t)

a1

a2

a10

a13

a14

a1

w(t)

с

w0

w0

w1

w1

w(t)

с

w0

w1

w0

w1

w(t)

с

w0

w1

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z1

z1

z1

c

z(t)

z1

z1

z0

z1

c

z(t)

z1

z1

z1

z0

c

a(t)

a1

a2

a10

a13

a15

a1

a(t)

a1

a16

a17

a18

a19

a1

a(t)

a1

a16

a17

a20

a21

a1

w(t)

с

w0

w1

w1

w1

w(t)

с

w1

w0

w1

w0

w(t)

с

w1

w1

w0

w0

t

0

1

2

3

4

5

z(t)

z1

z1

z1

z1

c

a(t)

a1

a16

a17

a20

a22

a1

w(t)

с

w1

w1

w0

w1

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

a(t)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

z0

a2

a3

a4

a5

a1

a1

a8

a1

a1

a11

-

a1

a14

a1

с

w0

w0

w0

w0

w1

w1

w0

w1

w1

-

w1

w1

w0

z1

a16

a10

a7

a6

a1

a1

a9

a1

a1

a13

a12

a1

a15

a1

с

w0

w0

w0

w0

w1

w1

w0

w1

w1

w0

w1

w1

w0

a(t)

a15

a16

a17

a18

a19

a20

a21

a22

z0

a1

-

a18

-

a1

a21

a1

a1

w1

-

w0

-

w0

w0

w0

w1

z1

a1

a17

a20

a19

a1

a22

a1

a1

w1

w1

w1

w1

w0

w0

w0

w1

3.1.2 Вторая стратегия

0

z0

z0

z0

z0

c

c

w0

w0

w0

w0

a1

a2

a3

a4

a5

a1

1

z0

z0

z0

z1

c

c

w0

w0

w0

w1

a1

a2

a3

a4

a6

a1

2

z0

z0

z1

z0

c

c

w0

w0

w1

w0

a1

a2

a3

a7

a5+

a1

3

z0

z0

z1

z1

c

c

w0

w0

w1

w1

a1

a2

a3

a7

a6+

a1

4

z0

z1

z0

z1

c

c

w0

w1

w0

w1

a1

a2

a8

a4+

a6

a1

5

z0

z1

z1

z0

c

c

w0

w1

w1

w0

a1

a2

a8

a7+

a5

a1

6

z0

z1

z1

z1

c

c

w0

w1

w1

w1

a1

a2

a8

a7

a6

a1

7

z1

z1

z0

z1

c

c

w1

w0

w1

w0

a1

a9

a10

a11

a5+

a1

8

z1

z1

z1

z0

c

c

w1

w1

w0

w0

a1

a9

a10

a4+

a5

a1

9

z1

z1

z1

z1

c

c

w1

w1

w0

w1

a1

a9

a10

a4

a6

a1

Проверка :

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z0

z0

c

z(t)

z0

z0

z0

z1

c

z(t)

z0

z0

z1

z0

c

a(t)

a1

a2

a3

a4

a5

a1

a(t)

a1

a2

a3

a4

a6

a1

a(t)

a1

a2

a3

a7

a5+

a1

w(t)

с

w0

w0

w0

w0

w(t)

с

w0

w0

w0

w1

w(t)

с

w0

w0

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z1

z1

c

z(t)

z0

z1

z0

z1

c

z(t)

z0

z1

z1

z0

c

a(t)

a1

a2

a3

a7

a6+

a1

a(t)

a1

a2

a8

a4+

a6

a1

a(t)

a1

a2

a8

a7+

a5

a1

w(t)

с

w0

w0

w1

w1

w(t)

с

w0

w1

w0

w1

w(t)

с

w0

w1

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z1

z1

z1

c

z(t)

z1

z1

z0

z1

c

z(t)

z1

z1

z1

z0

c

a(t)

a1

a2

a8

a7

a6

a1

a(t)

a1

a9

a10

a11

a5+

a1

a(t)

a1

a9

a10

a4+

a5

a1

w(t)

с

w0

w1

w1

w1

w(t)

с

w1

w0

w1

w0

w(t)

с

w1

w1

w0

w0

t

0

1

2

3

4

5

z(t)

z1

z1

z1

z1

c

a(t)

a1

a9

a10

a4

a6

a1

w(t)

с

w1

w1

w0

w1

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

a(t)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

z0

a2

a3

a4

a5

a1

a1

a5

a4

-

a11

-

с

w0

w0

w0

w0

w1

w1

w1

-

w0

-

z1

a9

a8

a7

a6

a1

a1

a6

a7

a10

a4

a5

с

w0

w0

w0

w0

w1

w1

w1

w1

w1

w1

3.2 Разметка вход-выходных слов для автомата Мура

3.2.1 Первая стратегия

0

z0

z0

z0

z0

c

c

w0

w0

w0

w0

a1

a2

a3

a4

a5

a6

1

z0

z0

z0

z1

c

c

w0

w0

w0

w1

a1

a2

a3

a4

a7

a8

2

z0

z0

z1

z0

c

c

w0

w0

w1

w0

a1

a2

a3

a9

a10

a11

3

z0

z0

z1

z1

c

c

w0

w0

w1

w1

a1

a2

a3

a9

a12

a13

4

z0

z1

z0

z1

c

c

w0

w1

w0

w1

a1

a2

a14

a15

a16

a17

5

z0

z1

z1

z0

c

c

w0

w1

w1

w0

a1

a2

a14

a18

a19

a20

6

z0

z1

z1

z1

c

c

w0

w1

w1

w1

a1

a2

a14

a18

a21

a22

7

z1

z1

z0

z1

c

c

w1

w0

w1

w0

a1

a23

a24

a25

a26

a27

8

z1

z1

z1

z0

c

c

w1

w1

w0

w0

a1

a23

a24

a28

a29

a30

9

z1

z1

z1

z1

c

c

w1

w1

w0

w1

a1

a23

a24

a28

a31

a32

Проверка :

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z0

z0

c

z(t)

z0

z0

z0

z1

c

z(t)

z0

z0

z1

z0

c

a(t)

a1

a2

a3

a4

a5

a6

a(t)

a1

a2

a3

a4

a7

a8

a(t)

a1

a2

a3

a9

a10

a11

w(t)

с

c

w0

w0

w0

w0

w(t)

с

c

w0

w0

w0

w1

w(t)

с

c

w0

w0

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z1

z1

c

z(t)

z0

z1

z0

z1

c

z(t)

z0

z1

z1

z0

c

a(t)

a1

a2

a3

a9

a12

a13

a(t)

a1

a2

a14

a15

a16

a17

a(t)

a1

a2

a14

a18

a19

a20

w(t)

с

c

w0

w0

w1

w1

w(t)

с

c

w0

w1

w0

w1

w(t)

с

с

w0

w1

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z1

z1

z1

c

z(t)

z1

z1

z0

z1

c

z(t)

z1

z1

z1

z0

c

a(t)

a1

a2

a14

a18

a21

a22

a(t)

a1

a23

a24

a25

a26

a27

a(t)

a1

a23

a24

a28

a29

a30

w(t)

с

c

w0

w1

w1

w1

w(t)

с

c

w1

w0

w1

w0

w(t)

с

c

w1

w1

w0

w0

t

0

1

2

3

4

5

z(t)

z1

z1

z1

z1

c

a(t)

a1

a23

a24

a28

a31

a32

w(t)

с

c

w1

w1

w0

w1

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

a(t)

-

-

w0

w0

w0

w0

w0

w1

w0

w1

w0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

z0

a2

a3

a4

a5

a6

-

a8

-

a10

a11

-

z1

a23

a14

a9

a7

a6

-

a8

-

a12

a11

-

a(t)

w1

w1

w0

w1

w0

w1

w1

w1

w0

w1

w1

a12

a13

a14

a15

a16

a17

a18

a19

a20

a21

a22

z0

a13

-

a15

-

a17

-

a19

a20

-

a22

-

z1

a13

-

a18

a16

a17

-

a21

a20

-

a22

-

a(t)

-

w1

w0

w1

w0

w1

w0

w0

w0

w1

a23

a24

a25

a26

a27

a28

a29

a30

a31

a32

z0

-

a25

-

a27

-

a29

a30

-

a32

-

z1

a24

a28

a26

a27

-

a31

a30

-

a32

-

3.2.2 Вторая стратегия

0

z0

z0

z0

z0

c

c

w0

w0

w0

w0

a1

a2

a3

a4

a5

a6

1

z0

z0

z0

z1

c

c

w0

w0

w0

w1

a1

a2

a3

a4

a6+

a7

2

z0

z0

z1

z0

c

c

w0

w0

w1

w0

a1

a2

a3

a8

a7+

a1+

3

z0

z0

z1

z1

c

c

w0

w0

w1

w1

a1

a2

a3

a8

a9

a2+

4

z0

z1

z0

z1

c

c

w0

w1

w0

w1

a1

a2

a10

a11

a6+

a7

5

z0

z1

z1

z0

c

c

w0

w1

w1

w0

a1

a2

a10

a12

a7+

a1

6

z0

z1

z1

z1

c

c

w0

w1

w1

w1

a1

a2

a10

a12

a9+

a2

7

z1

z1

z0

z1

c

c

w1

w0

w1

w0

a1

a13

a14

a6+

a7

a1

8

z1

z1

z1

z0

c

c

w1

w1

w0

w0

a1

a13

a14

a11+

a15

a1

9

z1

z1

z1

z1

c

c

w1

w1

w0

w1

a1

a13

a14

a11

a6+

a2

Проверка :

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z0

z0

c

z(t)

z0

z0

z0

z1

c

z(t)

z0

z0

z1

z0

c

a(t)

a1

a2

a3

a4

a5

a6

a(t)

a1

a2

a3

a4

a6

a7

a(t)

a1

a2

a3

a8

a7

a1

w(t)

с

c

w0

w0

w0

w0

w(t)

с

c

w0

w0

w0

w1

w(t)

с

c

w0

w0

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z0

z1

z1

c

z(t)

z0

z1

z0

z1

c

z(t)

z0

z1

z1

z0

c

a(t)

a1

a2

a3

a8

a9

a2

a(t)

a1

a2

a10

a11

a6

a7

a(t)

a1

a2

a10

a12

a7

a1

w(t)

с

c

w0

w0

w1

w1

w(t)

с

c

w0

w1

w0

w1

w(t)

с

с

w0

w1

w1

w0

t

0

1

2

3

4

5

t

0

1

2

3

4

5

t

0

1

2

3

4

5

z(t)

z0

z1

z1

z1

c

z(t)

z1

z1

z0

z1

c

z(t)

z1

z1

z1

z0

c

a(t)

a1

a2

a10

a12

a9

a2

a(t)

a1

a13

a14

a6

a7

a1

a(t)

a1

a13

a14

a11

a15

a1

w(t)

с

c

w0

w1

w1

w1

w(t)

с

c

w1

w0

w1

w0

w(t)

с

c

w1

w1

w0

w0

t

0

1

2

3

4

5

z(t)

z1

z1

z1

z1

c

a(t)

a1

a13

a14

a11

a6

a7

w(t)

с

c

w1

w1

w0

w1

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

a(t)

w0

w1

w0

w0

w0

w0

w1

w0

w1

w0

w1

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

z0

a2

a3

a4

a5

a6

a7

a1

a7

a2

a11

a15

z1

a13

a10

a8

a6

a6

a7

a1

a9

a2

a12

a6

a(t)

w1

-

w1

w0

a12

a13

a14

a15

z0

a7

-

a6

a1

z1

a9

a14

a11

a1

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

Таблица переходов-выходов автомата Мили, построенного по второй стратегии

a(t)

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

z0

a2

a3

a4

a5

a1

a1

a5

a4

-

a11

-

с

w0

w0

w0

w0

w1

w1

w1

-

w0

-

z1

a9

a8

a7

a6

a1

a1

a6

a7

a10

a4

a5

с

w0

w0

w0

w0

w1

w1

w1

w1

w1

w1

3.3 Минимизация автомата

Диаграмма совместимости

2

2~3

9~8

3

2~4

9~7

3~4

7~8

4

2~5

6~9

3~5

6~8

4~5

7~6

5

1~2

1~9

1~3

1~8

1~4

1~7

1~5

1~6

6

1~2

1~9

7

2~5

6~9

1~5

1~6

8

2~4

9~7

4~1

1~7

5~4

6~7

9

9~10

1~10

6~10

7~10

10

2~11

9~4

10~4

11

9~5

1~5

6~5

7~5

10~5

4~5

1

2

3

4

5

6

7

8

9

10

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

№

МС-классы.

0

1,2,3,4,5,6,7,8,9,10,11

1

1,3,4,5,6,7,8,9,10,11 1,2,3,4,5

2

1,4,5,6,7,8,9,10,11 1,2,3,4,5

3

1,5,6,7,8,9,10,11 1,2,3,4,5

4

1,6,7,8,9,10,11 1,2,3,4,5

5

1,6,7,8,9,11 1,10 1,2,3,4,5

6

1 2 3 4 5 6 7 8 9 10 11

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

4.1 Кодировка алфавитов и состояний

Кодировка входного алфавита

Определим количество внешних входов L. Пусть 2L - число различных комбинаций, которые можно подать на входы. Тогда 2L ? F- мощности входного алфавита. F = 2. 21=2 , значит L =1.

Z(t)

X

Z0

0

Z1

1

Кодировка выходного алфавита

Определим количество внешних выходов N. Пусть 2N - число различных комбинаций, которые могут поступить на выходы. Тогда 2N ? G - мощности выходного алфавита. G = 2. 21 = 2 , значит N=1.

W(t)

Y

W0

0

W1

1

Кодировка внутренних состояний

Определим количество элементов памяти (триггеров) R. Пусть 2R- число различных внутренних состояний, в которых может находиться структурный автомат. Тогда 2R ? M - мощности алфавита состояний. M=11. 24 > 11, значит R=4.

а(t)

Q1

Q2

Q3

Q4

а1

0

0

0

1

а2

0

0

1

0

а3

0

0

1

1

а4

0

1

0

0

а5

0

1

0

1

а6

0

1

1

0

а7

0

1

1

1

а8

1

0

0

0

а9

1

0

0

1

а10

1

0

1

0

а11

1

0

1

1

4.2 Построение булевых функций

Для заполнения таблицы переходов-выходов будем использовать таблицу функции переходов i-того элемента памяти и словарь JK - триггера.

Таблица функции переходов i-того элемента памяти

Qit

Qit+1

fQi

0

0

0

0

1

б

1

0

?

1

1

1

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

fQi

J

K

0

0

-

1

-

0

б

1

-

?

-

1

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

t

t+1

t

№

x

Q1

Q2

Q3

Q4

y

Q1

Q2

Q3

Q4

fQ

fQ

fQ

fQ

J1

K1

J2

K2

J3

K3

J4

K4

1

0

0

0

0

1

-

0

0

1

0

0

0

б

?

0

-

0

-

1

-

-

1

2

0

0

0

1

0

0

0

0

1

1

0

0

1

б

0

-

0

-

-

0

1

-

3

0

0

0

1

1

0

0

1

0

0

0

б

?

?

0

-

1

-

-

1

-

1

4

0

0

1

0

0

0

0

1

0

1

0

1

0

б

0

-

-

0

0

-

1

-

5

0

0

1

0

1

0

0

0

0

1

0

?

0

1

0

-

-

1

0

-

-

0

6

0

0

1

1

0

1

0

0

0

1

0

?

?

б

0

-

-

1

-

1

1

-

7

0

0

1

1

1

1

0

1

0

1

0

1

?

1

0

-

-

0

-

1

-

0

8

0

1

0

0

0

1

0

1

0

0

?

б

0

0

-

1

1

-

0

-

0

-

9

0

1

0

0

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

10

0

1

0

1

0

0

1

0

1

1

1

0

1

б

-

0

0

-

-

0

1

-

11

0

1

0

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

12

1

0

0

0

1

-

1

0

0

1

б

0

0

1

1

-

0

-

0

-

-

0

13

1

0

0

1

0

0

0

1

0

1

0

б

?

б

0

-

1

-

-

1

1

-

14

1

0

0

1

1

0

0

1

1

1

0

б

1

1

0

-

1

-

-

0

-

0

15

1

0

1

0

0

0

0

1

1

0

0

1

б

0

0

-

-

0

1

-

-

0

16

1

0

1

0

1

0

0

0

0

1

0

?

0

1

0

-

-

1

0

-

-

0

17

1

0

1

1

0

1

0

0

0

1

0

?

?

б

0

-

-

1

-

1

1

-

18

1

0

1

1

1

1

0

1

1

0

0

1

1

?

0

-

-

0

-

0

-

1

19

1

1

0

0

0

1

0

1

1

1

?

б

б

б

-

1

1

-

1

-

1

-

20

1

1

0

0

1

1

1

0

1

0

1

0

б

?

-

0

0

-

1

-

-

1

21

1

1

0

1

0

1

0

1

0

0

?

б

?

0

-

1

1

-

-

1

0

-

22

1

1

0

1

1

1

0

1

0

1

?

б

?

1

-

1

1

-

-

1

-

0

4.3 Раздельная минимизация

Минимизация булевых функций с помощью карт Карно

y

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

0

-

1

1

-

0

-

01

-

0

-

-

1

-

0

-

11

0

1

-

-

1

-

1

0

10

0

1

-

0

1

-

1

0

A

J1

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

0

-

-

-

-

0

-

01

0

0

-

-

-

-

0

11

0

0

-

-

-

-

0

0

10

0

0

-

-

-

-

0

0

A

K1

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

-

-

1

1

-

-

-

01

-

-

-

-

0

-

-

-

11

-

-

-

-

1

-

-

-

10

-

-

-

0

1

-

-

-

A

J2

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

-

-

1

1

-

-

-

01

0

-

-

-

0

-

-

0

11

1

-

-

-

1

-

-

1

10

0

-

-

0

1

-

-

1

A

K2

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

0

-

-

-

-

0

-

01

-

1

-

-

-

-

1

-

11

-

0

-

-

-

-

0

-

10

-

1

-

-

-

-

1

-

A

J3

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

0

-

0

1

-

1

-

01

1

0

-

-

1

-

0

0

11

-

-

-

-

-

-

-

-

10

-

-

-

-

-

-

-

-

A

K3

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

-

-

-

-

-

-

-

01

-

-

-

-

-

-

-

-

11

1

-

1

-

1

-

0

0

10

0

-

1

0

1

-

1

1

A

J4

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

1

-

0

1

-

-

-

01

-

-

-

-

-

-

-

-

11

1

-

1

-

1

-

0

0

10

0

-

1

0

1

-

1

1

A

K4

xQ1Q2

A

Q3Q4

000

001

011

010

110

111

101

100

00

-

-

-

-

-

-

0

-

01

1

0

-

-

1

-

0

0

11

1

0

-

-

0

-

1

0

10

-

-

-

-

-

-

-

-

A

Таким образом, получена система булевых функций:

4.4 Факторизация и совместная минимизация

Совместная минимизация

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

Факторизация:

Факторизация Y

Факторизация K3

С учетом факторизации и совместной минимизации функций получаем следующую систему:

4.5 Реализация на элементах малой степени интеграции (К155)

Использованные элементы серии К155 и их УГО:

1) К155ТВ15

Микросхема представляет собой два тактируемых J-K триггера с установкой в 0 и 1. Считывание информации с входов J и K происходит во время положительного перепада на входе С, а на выходы она передается во время отрицательного перепада. Логические уровни на J и K не должны изменяться, пока на С высокий уровень. Если соединить выводы J и K триггер будет работать как обычный счетный (делить частоту на 2).

1,15 - вход установки "0";2 - вход J1;3 - вход K1;4,12 - вход синхронизации;5,11 - вход установки "1";6,7,9,10 - выходы;8 - общий;13 - вход K2;14 - вход J2;16 - напряжение питания;

2) К155ЛН1

Микросхема представляет собой шесть логических элементов НЕ. Корпус К155ЛН1 типа 201.14-1, масса не более 1 г и у КМ155ЛН1 типа 201.14-8, масса не более 2,2 г.

1,3,5,9,11,13 - входы;2,4,6,8,10,12 - выходы;7 - общий;14 - напряжение питания;

3) К155ЛР1

Микросхема представляет собой 2 логических элемента 2-2И-2ИЛИ-НЕ, один расширяемый по ИЛИ. Корпус К155ЛР1 типа 201.14-2, масса не более 1 г и у КМ155ЛР1 типа 201.14-8, масса не более 2,2 г.

1-5,9-13 - входы;6,8 - выходы;7 - общий;14 - напряжение питания;

4) К155ЛИ1

Микросхема представляет собой четыре логических элемента 2И. Корпус К155ЛИ1 типа 201.14-1, масса не более 1 г и у КМ155ЛИ1 типа 201.14-8, масса не более 2,2 г.

1,2,4,5,9,10,12,13 - входы;3,6,8,11 - выходы;7 - общий;14 - напряжение питания;

5) К155ЛЛ1

Микросхема представляет собой четыре логических элемента 2ИЛИ. Корпус К155ЛЛ1 типа 201.14-1, масса не более 1 г и у КМ155ЛЛ1

типа 201.14-8, масса не более 2,2 г.

1,2,4,5,9,10,12,13 - входы;3,6,8,11 - выходы;7 - общий;14 - напряжение питания;

Для всех микросхем на 14 ножку подается +5В, на 7 - заземление

DD1, DD2 - К155ТВ15;

DD3 - К155ЛР1;

DD4, DD10, DD11, DD13 - К155ЛЛ1;

DD6, DD7, DD8, DD9, DD12 - К155ЛИ1;

DD5, DD14, DD15, DD16 - К155ЛН1.

Размещено на Allbest.ru


Подобные документы

  • Моделирование дискретного автомата

    Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.

    курсовая работа [964,2 K], добавлен 20.07.2015

  • Синтез микропрограммного управляющего автомата с жесткой логикой

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

    курсовая работа [764,0 K], добавлен 27.08.2012

  • Минимизация абстрактного автомата

    Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.

    курсовая работа [997,7 K], добавлен 28.03.2011

  • Разработка цифрового автомата Мили, содержащий в качестве памяти D-триггер

    Общая схема D-триггера и цифрового автомата Мили. Построение входных и выходных преобразователей в соответствии с таблицами кодирования входных и выходных сигналов. Составление таблиц переходов и выхода состояния автомата Мили. Выбор серии микросхем.

    курсовая работа [525,4 K], добавлен 04.11.2012

  • Абстрактный автомат Мили

    Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.

    курсовая работа [823,8 K], добавлен 19.07.2012

  • Проектирование управляющего цифрового автомата

    Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.

    курсовая работа [506,9 K], добавлен 26.12.2012

  • Построение кодопреобразователя

    Понятие и назначение дискретного (цифрового) автомата, сферы и правила его использования. Граф-дерево автомата Мура и мили, их отличительные черты. Таблица переходов с распределением неопределённостей. Представление функции возбуждения и ее минимизация.

    курсовая работа [423,7 K], добавлен 11.10.2008

  • Дослідження методів реалізації автоматів Мура

    Оптимізація схеми мікропрограмного автомата Мура за рахунок нестандартного подання кодів станів. Аналіз методів синтезу автомата та аналіз сучасного елементного базису. Використанні особливостей автомата для зменшення площини матричної схеми автомата.

    презентация [357,0 K], добавлен 16.10.2013

  • Проектирование цифрового автомата в САПР OrCAD 9.1 и Active-HDL 7.1

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

    курсовая работа [831,2 K], добавлен 23.09.2013

  • Синтез управляющего автомата с жесткой логикой, реализующего функцию умножения, начиная с младших разрядов множителя

    Определение функций выходных сигналов и сигналов возбуждения. Построение функциональной схемы управляющего автомата. Способы выполнения операции умножения с фиксированной и с плавающей запятой. Получение функциональной ГСА. Кодирование состояния автомата.

    курсовая работа [60,9 K], добавлен 15.02.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены