Материалы для студентов→ Курсовая работа /

Автомат Мили

Скачать файл
Добавил: fafnir
Размер: 376.64 KB
Добавлен: 30.04.2015
Просмотров: 497
Закачек: 13
Формат: docx

СОДЕРЖАНИЕ

Введение………………………………………………………………………. 2

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

Общая последовательность сложения чисел с ПТ………………………….. 3

Структурная схема АЛУ………………………………………………………

4

Алгоритм сложения чисел в АЛУ……………………………………………

6

Общая последовательность разработки……………………………………… 8

Формализация задания……………………………………………………….. 8

Выбор типа автомата…………………………………………………………

9

Разметка схемы алгоритма…………………………………………………... 9

Составление таблиц переходов и выходов…………………………………..

11

Кодирование состояний………………………………………………………

11

Составление кодированной таблицы переходов и выходов………………..

12

Выбор типа триггера…………………………………………………………. 12

Преобразование таблицы переходов в таблицу функций

возбуждения триггеров……………………………………………………….

13

Запись функций возбуждения и функций выходов в СДНФ……………….

13

Минимизация функций возбуждения и функций выходов…………………

15

Заключение…………………………………………………………………….. 17

Литература……………………………………………………………………..

18


Введение

Абстрактный синтез включает в себя разработку алгоритма работы автомата 

и составление его формального описания в виде автоматных таблиц или в 

виде графа переходов. Алгоритм наиболее удобно и наглядно представлять в 

виде блок-схем. Разработка алгоритмов и блок-схем является наиболее 

творческой частью работы и плохо поддаётся формализации. 

По разработанной блок-схеме описание работы автомата проще всего 

составлять в виде графа переходов. Вид графа зависит от того, проектируется 

автомат Мура или автомат Мили:

Автомат Мили        

Автомат Мура                          

  yt = f1(xt, zt)                                                 yt+1 = ft(zt+1)     

zt+1 = f2(xt, zt)                                                 zt+1 = f2(xt, zt)

Автомат Мили (англ. Mealy machine) — конечный автомат, выходная 

последовательность которого (в отличие от автомата Мура) зависит от 

состояния автомата и входных сигналов. Это означает, что в графе состояний 

каждому ребру соответствует некоторое значение (выходной символ). В 

вершины графа автомата Мили записываются выходящие сигналы, а дугам 

графа приписывают условие перехода из одного состояния в другое, а также 

входящие сигналы.

Автомат Мили можно описать пятеркой (Q,X,Y,f,g), где Q - множество 

2

yt+1

yt

xt

f1

f1

zt+1

zt+1

xt

f2

f2


состояний автомата, X - множество входных символов, Y - множество 

выходных символов, q=f(Q,X) - функция состояний, y=g(Q,Y) - функция 

выходных символов.

Автомат Мура

Зависимость выходного сигнала только от состояния представлена 

в автоматах типа Мура (англ. Moore machine). В автомате Мура функция 

выходов определяет значение выходного символа только по одному 

аргументу — состоянию автомата. Эту функцию называют также функцией 

меток, так как она каждому состоянию автомата ставит метку на выходе.

Автомат Мили

В автомате Мили (англ. Mealy machine) функция выходов λ определяет 

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

автомата. Математическая модель автомата Мили и схема рекуррентных 

соотношений не отличаются от математической модели и схемы 

рекуррентных соотношений абстрактного автомата. Таким образом, можно 

дать следующее определение:

Конечным детерминированным автоматом типа Мили называется 

совокупность пяти объектов

,

где S, X и Y — конечные непустые множества, а δ и λ — отображения вида:

 и 

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, 

…} уравнениями:

(Отображения δ и λ получили названия, соответственно функции переходов и 

функции выходов автомата A).

Особенностью автомата Мили является то, что функция выходов является 

двухаргументной и символ в выходном канале y(t) обнаруживается только 

при наличии символа во входном канале x(t). Функциональная схема не 

отличается от схемы абстрактного автомата.

Автомат Мили

В автомате Мили (англ. Mealy machine) функция выходов λ определяет 

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

автомата. Математическая модель автомата Мили и схема рекуррентных 

соотношений не отличаются от математической модели и схемы 

3


рекуррентных соотношений абстрактного автомата. Таким образом, можно 

дать следующее определение:

Конечным детерминированным автоматом типа Мили называется 

совокупность пяти объектов

,

где S, X и Y — конечные непустые множества, а δ и λ — отображения вида:

 и 

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, 

…} уравнениями:

(Отображения δ и λ получили названия, соответственно функции переходов и 

функции выходов автомата A).

Особенностью автомата Мили является то, что функция выходов является 

двухаргументной и символ в выходном канале y(t) обнаруживается только 

при наличии символа во входном канале x(t). Функциональная схема не 

отличается от схемы абстрактного автомата.

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

Разработать схему блока управления в АЛУ, выполняющего операцию 

сложения чисел с плавающей точкой в обратном коде, принимая в расчёт 

следующие:

Исходные данные:  Тип автомата - автомат Мура

                                   Тип триггера - T-триггер

                  2.  Общая последовательность сложения чисел с ПТ

При сложении определяется сумма С = А + В,  где:

А – слагаемое;

В – слагаемое;

С – сумма.

Перед   выполнением   операции   числа   записаны   в   оперативной   памяти   в 

прямом   коде.   Для   выполнения   операции   числа   должны   быть   считаны   из 

памяти и переданы в АЛУ. Особенностью сложения чисел с ПТ является то, 

что   в   общем   случае   операнды   могут   иметь   различные   порядки,   поэтому 

4


перед   суммированием   мантисс   необходимо   выровнять   порядки.   После 

анализа   знака   разности   порядков,   мантисса   числа   с   меньшим   порядком 

сдвигается   вправо   на   величину   разности   порядков.   При   этом   могут   быть 

потеряны   младшие   разряды   мантиссы.   Так   как   операция   сложения 

проводится с учетом знака, то числа представляются в дополнительном коде. 

При сложении в дополнительном коде представляются оба слагаемых, если 

они   отрицательны.   В   остальных   случаях   числа   представляются   в   прямом 

коде. Сложение выполняется в сумматоре, на выходе которого формируется 

результат операции сложения.

  Для уменьшения погрешности выполняется округление результата. После 

суммирования результат может оказаться ненормализованным, в этом случае 

необходима   его   нормализация.                 Полученный   результат   может   быть 

отрицательный, в этом случае он представлен в дополнительном коде. Перед 

записью результата в оперативную память результат преобразуется в прямой 

код. Кроме результата с помощью специальных схем определяются признаки 

результата.

3.  Структурная схема АЛУ

Структурная   схема   АЛУ   строится   в   соответствии   с   общей 

последовательностью   операции   сложения.   АЛУ   имеет   типовую   структуру, 

представленную на рисунке 2. 

Для выполнения каждого действия в операционном блоке АЛУ должны быть 

предусмотрены соответствующие узлы. Так для хранения исходных чисел (А 

и  В)    на  время  выполнения  операции  в   состав   АЛУ  должны  входить   два 

регистра. Для сложения чисел в операционном блоке должен быть сумматор. 

Обычно сумматор выполняется в виде комбинационной схемы, поэтому для 

фиксации результата операции он должен иметь регистр сумматора.

Для определения признака результата должны использоваться схемы, которые 

объединяются в общую схему формирования признаков результата. 

Соединив   основные   узлы   операционного   блока   между   собой 

информационными связями,

а   также   операционный   блок   и   блок   управления   управляющими   связями, 

получим структурную схему АЛУ, представленную на рисунке 2.

       

                        

            

5


Из

м.

Лист

№ докум

Подпись Дата

Разраб.

Рисунок 2

Структурная схема АЛУ

Лит.

Лист

Листов

Проверил

ер.

1

1

Н. Контр.

Утверд.

                      

Шина данных

 

 

Регистр 

А                      

  

 

Сигнал 

 

начала

 

операции                                                                                            

 

 

Регистр В

                        

Управляющие сигналы

  

 

6

   

ОП

        

Бло

к 

упра

влен

ия

  М       Р

Схема  анализа 

Мантиссы на 

  

М       Р

Схема  анализа 

порядкана нуль


                      Сигнал

                       готов­

                        ности

                                                             

ПК   ДК ПК ДК          

                                                          

                                  

                                   

                                      

                                   

 

                                         Признаки результата

       

                        

            

6.

Алгоритм сложения чисел в АЛУ

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

  в   соответствии   с   общей 

последовательностью   сложения   и   структурной   схемой   АЛУ. 

Микропрограмма   сложения   чисел   в   АЛУ   в   виде   схемы   алгоритма 

представлена   на   рисунке   3.   Здесь   под   микропрограммой   понимается 

последовательность   микроопераций.   Микрооперация   –   элементарная 

операция, для управления которой достаточно одного управляющего сигнала.

7

Схепма 

округления

 Сумматор М         Сумматор Р 

            Регистр сумматора

Схема 

формирования


      Перед началом операции числа находятся в оперативной памяти. Если АЛУ 

не занято                                выполнением очередной операции, то блок  

управления находится в исходном состоянии и выдает сигнал готовности.

           Блок управления начинает работу, если на него поступает код операции 

(оператор 1). В данном случае выполняется только одна операция, поэтому 

код операции является одновременно и сигналом начала операции.

Выполнение операции начинается с того, что числа  А и В последовательно 

считываются из оперативной памяти и записываются в регистры РгА и РгВ 

(операторы 2 и 3). 

Для   сложения   двух   чисел   с   ПТ   необходимо,   чтобы   их   порядки   были 

одинаковы. После извлечения чисел из ОП, вычисляется разность порядков 

dP (оператор 4). Если dP не равно 0, то необходимо выравнивание порядков 

(оператор 6). Для помещения чисел в сумматор, необходимо учитывать знак 

чисел,   для   представления   их   в   соответствующем   коде   (прямой   или 

дополнительный). Операторы 7, 8 и 9 выполняют эту функцию: Если  А<0 и 

В<0,   то   оба   числа   отправляем   в   сумматор   в   дополнительном   коде   (ДК)   – 

оператор 11. Если А<0, а B>0 то число В заносится в сумматор в прямом коде 

(ПК) – оператор 10. Если А>0,а В<0, то число А заносится в сумматор в ПК, а 

В в ДК – оператор 13. Если А>0 и B>0 то оба числа заносятся в сумматор в 

ПК – оператор 12. Оба числа поступают на входы сумматора одновременно, 

при   этом   на   выходах   сумматора   формируется   значение   суммы,   которое 

записывается в регистр сумматора.

После   сложения   необходимо  провести   нормализацию   результата   (оператор 

14).   Для   уменьшения   погрешности   выполняем   округление   результата 

(оператор   15).   Полученная   сумма   анализируется   в   схеме   формирования 

признака результата (оператор 16). Если число отрицательное (оператор 17) 

то результат преобразовывается в ПК и записывается в ОП (операторы 18 и 

19), если нет, то результат просто заносится в ОП (оператор 19).

Приведённая схема является упрощённой.

Из

м.

Лист

№ докум

Подпись Дата

Разраб.

Рисунок 3

Алгоритм сложения 

чисел в АЛУ

Лит.

Лист

Листов

Проверил

ер.

1

1

Н. Контр.

8


Утверд.

0  Начало

Х1

А=0

Х2

В=0

0*

0(да)

1(нет)

1(нет)

0(да)

1

С=В

2

С=А

3

С=А+В

Х3

Sg1Sg2

4

Продолжение

5

Останов ЭВМ

0  Конец

1*

3*

9


0*

0(нет)

1(да)

10


5. Разработка функциональной схемы блока управления

5.1 Общая последовательность разработки

Блок управления представляет собой автомат с памятью. Алгоритм работы 

блока управления задан в виде микропрограммы. В этом случае разработка 

блока управления включает следующие этапы:

Формализация задания.

Выбор типа автомата.

Разметка схемы алгоритма.

Составление таблицы переходов и выходов автоматов.

Кодирование состояний.

Составление кодированной таблицы переходов и выходов.

Выбор типа триггеров.

Преобразование  таблицы  переходов  в таблицу  функций  возбуждения 

триггеров.

Запись функций возбуждения и функций выходов в СДНФ.

Минимизация функций возбуждения и функций выходов.

Выбор типа логических элементов.

Преобразование функций переходов и выходов.

Построение функциональной схемы блока управления.

Проверка правильности работы блока управления.

5.2 Формализация задания

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

числу различных условных операторов микропрограммы. В данном случае 

число условных операторов равно 5(операторы 8, 9  - одинаковы).

Для   упрощения   записи   логических   функций   на   рисунке   3   приняты 

следующие обозначения:

-

K – сигнал кода операции;

-

P – проверка разности порядков

-    A – проверка знака числа А;

-

B – проверка знака числа В;

-

S – проверка знака результата.

Тогда входными сигналами блока управления являются сигналы K, P, A, B, S

каждый из которых может принимать значение 0 или 1.

Число выходных сигналов блока управления равно числу микроопераций в 

микропрограмме.

При   анализе   микропрограммы   можно   установить,   что   безусловные 

операторы  2, 3, 4, 6141517, 1819 содержат по одной микрооперации, а 

операторы  10,   11,   12,   13  –  по   две   совместимых   микрооперации.   Однако 

операторы  10,  11, 12, 13   содержат повторяющиеся микрооперации. Кроме 

того,   начальному   оператору   соответствует   выходной   сигнал,   который 

сообщает о готовности блока управления   к выполнению операции. Таким 

11


образом, общее число выходных сигналов равно 14. Обозначение выходных 

сигналов и соответствующие им микрооперации приведены в таблице 1.

  

      

Таблица 1

№ №

  п/п

 Выходные

  сигналы

                              Микрооперации

    0

        

0

Y

Сигнал готовности

    1

        

1

Y

Прием числа А из ОП в регистр РгА

    2

        

2

Y

Прием числа В из ОП в регистр РгВ

    3

        

3

Y

Вычитание порядков

    4

        

4

Y

Выравнивание порядков

    5

        

5

Y

Запись числа А в сумматор в дополнительном  

коде

    6

        

6

Y

Запись числа А в сумматор в прямом коде

    7

        

7

Y

Запись числа В в сумматор в прямом коде

    8

        

8

Y

Запись числа В в сумматор

в дополнительном коде

    9

        

9

Y

Нормализация результата

   10

        

10

Y

Округление результата

   11

        

11

Y

Формирование признака результата

   12

        

12

Y

Преобразование результата в прямой код

   13

        

13

Y

Запись в оперативную память

5.3  Выбор типа автомата

Заданием предусмотрена реализация блока управления в виде автомата Мура

12


5.4

 Разметка схемы алгоритма

Для разметки используется формальная схема алгоритма, в которой названия 

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

таблицы 1. При разметке используются следующие правила:

1.

Начальный и конечный операторы помечаются символами начального 

состояния  (

0

Q

).

2.

Безусловные операторы помечаются символами последовательно 

пронумерованных состояний 

1

Q

2

Q

3

Q

Размеченная схема алгоритма представлена на рисунке 5. Как видно по 

результатам разметки, автомат имеет 14 состояний  (

0

Q

1

Q

, … ,Q13).

13


Из

м.

Лист

№ докум

Подпись Дата

Разраб.

Рисунок 5

Разметка схемы алгоритма

Лит.

Лист

Листов

Проверил

ер.

1

1

Н. Контр.

Утверд.

14


15


5.5  Составление таблицы переходов и выходов

Таблица переходов  и выходов составляется по размеченной схеме алгоритма. 

Число строк таблицы (без заглавной) равно числу комбинаций входных 

сигналов, а число столбцов (без заглавного) равно числу состояний автомата.

В каждой клетке таблицы указывается новое состояние. Для сокращения 

размеров таблицы следует учесть, что при входном сигнале K = 0 автомат 

может находиться только в состоянии 

0

Q

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

автомата приведена в виде таблицы 2.

Таблица  2

Входы

                                                    Состояния и выходы

K P A 

B S

Y0 Y1 Y2 Y3 Y4 Y5, 

Y7

Y5

Y8

Y6, 

Y7

Y6, 

Y8

Y9

Y10     Y11     Y12     Y13

Q0 Q1 Q2 Q3 Q4

Q5

Q6

Q7

Q8

Q9

Q10

Q11  Q12  Q13

0 -  -  -  

-

Q0

-

-

-

-

-

-

-

  -

-

  -

  -

-

-

1 0 0 0 

0

Q1 Q2 Q3 Q7 Q7

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

1 0 0 0 

1

Q1 Q2 Q3 Q7 Q7

Q9

Q9

Q9

Q9

Q10

Q11

Q12

Q13

Q0

1 0 0 1 

0

Q1 Q2 Q3 Q8 Q8

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

1 0 0 1 

1

Q1 Q2 Q3 Q8 Q8

Q9

Q9

Q9

Q9

Q10

Q11

Q12

Q13

Q0

1 0 1 0 

0

Q1 Q2 Q3 Q5 Q5

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

1 0 1 0 

1

Q1 Q2 Q3 Q5 Q5

Q9

Q9

Q9

Q9

Q10

Q11

Q12

Q13

Q0

1 0 1 1 

0

Q1 Q2 Q3 Q6 Q6

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

1 0 1 1 

Q1 Q2 Q3 Q6 Q6

Q9

Q9

Q9

Q9

Q10

Q11

Q12

Q13

Q0

1 1 0 0 

Q1 Q2 Q3 Q4 Q7

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

1 1 0 0 

1

Q1 Q2 Q3 Q4 Q7

Q9

Q9

Q9

Q9

Q10

Q11

Q12

Q13

Q0

1 1 0 1 

0

Q1 Q2 Q3 Q4 Q8

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

1 1 0 1  Q1 Q2 Q3 Q4 Q8

Q9

Q9

Q9

Q9

Q10

Q11

Q12

Q13

Q0

16


1

1 1 1 0 

Q1 Q2 Q3 Q4 Q5

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

1 1 1 0 

1

Q1 Q2 Q3 Q4 Q5

Q9

Q9

Q9

Q9

Q10

Q11

Q12

Q13

Q0

1 1 1 1 

0

Q1 Q2 Q3 Q4 Q6

Q9

Q9

Q9

Q9

Q10

Q11

Q13

Q13

Q0

5.6  Кодирование состояний

Принимаем естественный способ кодирования. Число элементов памяти при 

этом будет равно

                                                         n = (

2

log

N)  ,

где:  n – число элементов памяти;

        N – число S состояний автомата;

         - знак округления в большую сторону до целого.

При N = 14 получим:

                                                n = (

2

log

 14)  = 4.

Обозначим элементы памяти символами 

1

q

2

q

3

q

 и 

4

q

. Далее каждому 

состоянию поставим в соответствие двоичный код его номера и набор 

состояний элементов памяти. В результате получим следующее кодирование 

состояний.                  

                                           -  -   -   -                                       -

                  

0

Q

 0000  

4

3

2

1

q

q

q

q

             

7

Q

 0111  

4

3

2

1

q

q

q

q

                                            -  -   - 

             -  -   -   

                   

1

Q

 0001  

4

3

2

1

q

q

q

q

                         

8

Q

 1000  

4

3

2

1

q

q

q

q

                                            -   -      -                                                        -   -

                   

2

Q

 0010  

4

3

2

1

q

q

q

q

                         

9

Q

 1001  

4

3

2

1

q

q

q

q

                                            -  -

-      -

                   

3

Q

 0011  

4

3

2

1

q

q

q

q

                         

10

Q

 1010  

4

3

2

1

q

q

q

q

                                            -       -  -

-

                   

4

Q

 0100  

4

3

2

1

q

q

q

q

                         

11

Q

 1011  

4

3

2

1

q

q

q

q

 -      -

-  -

17


                   

5

Q

 0101  

4

3

2

1

q

q

q

q

                         

12

Q

 1100  

4

3

2

1

q

q

q

q

-          -                                                             -

                   

6

Q

 0110  

4

3

2

1

q

q

q

q

                         

13

Q

 1101  

4

3

2

1

q

q

q

q

                

5.7  Составление кодированной таблицы переходов и выходов

       Для составления кодированной таблицы переходов заменим в таблице 2 

состояния    

i

Q

  их   двоичными   номерами   в   соответствии   с   принятым 

кодированием.   В   результате   получим   кодированную   таблицу   переходов   и 

выходов, которая имеет вид таблицы 3. В таблице 3 приведены как двоичные 

Q номера состояний, так и состояния каждого элемента памяти

     

5.8

 Выбор типа триггера

Выбор типа триггера производится методом перебора. При этом поочередно 

выполняется синтез автомата для всех рассматриваемых типов триггеров. Для 

реализации выбирается тип триггера, при использовании которого автомат 

имеет меньшую сложность. В данном случае синтез производится для   T- 

триггера.

 

Таблица 3

Вход

ы

                                                    Состояния и выходы

kpa

bs

Y0

Y1

Y2

Y3

Y4

Y5, 

Y7

Y5, 

Y8

Y6, 

Y7

Y6,

Y8

Y9

Y10     Y11     Y12     Y13

Q0

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Q9

Q10

Q11  Q12  Q13

Код

и-

ров

ка

000

0

000

1

001

0

001

1

010

0

010

1

011

0

011

1

100

0

100

1

101

0

101

1

110

0

110

1

0- - 

- -

 

000

0

-

-

-

-

-

-

-

  -

-

  -

-

-

-

100

00

 

000

1

001

0

001

1

011

1

011

1

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

100

01

 

000

001

0

001

1

011

1

011

1

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

18


1

100

10

 

000

1

001

0

001

1

100

0

100

0

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

100

11

 

000

1

001

0

001

1

100

0

100

0

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

101

00

 

000

1

001

0

001

1

010

1

010

1

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

101

01

 

000

1

001

0

001

1

010

1

010

1

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

101

10

 

000

1

001

0

001

1

011

0

011

0

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

1011

 

000

1

001

0

001

1

011

0

011

0

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

110

00 

 

000

1

001

0

001

1

010

0

011

1

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

110

01

 

000

1

001

0

001

1

010

0

011

1

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

110

10

 

000

1

001

0

001

1

010

0

100

0

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

1101

1

 

000

1

001

0

001

1

010

0

100

0

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

1110

 

000

1

001

0

001

1

010

0

010

1

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

1110

1

 

000

1

001

0

001

1

010

0

010

1

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

1111

0

 

000

1

001

0

001

1

010

0

011

0

100

1

100

1

100

1

100

1

101

0

101

1

110

1

110

1

000

0

1111

1

 

000

1

001

0

001

1

010

0

011

0

100

1

100

1

100

1

100

1

101

0

101

1

110

0

110

1

000

0

19


5.9 Преобразование таблицы переходов в таблицу функций возбуждения 

триггеров

Приведем   преобразование   таблицы   переходов   в   таблицу   функций 

возбуждения для 

T – триггеров. Эта таблица имеет вид таблицы 4.

Таблица 4

Входы                                                     Состояния и выходы

kpabs

Y

0

Y1

Y2

Y3

Y5, 

Y6

Y5, 

Y7

Y4, 

Y6

Y4, 

Y7

Y8

Y9

Y10     Y11     Y12     Y13

Q

0

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Q9

Q10

Q11  Q12  Q13

Коди-

ровка

0

0

0

0

000

1

001

0

001

1

010

0

010

1

011

0

011

1

100

0

100

1

101

0

101

1

110

0

110

1

0- - - -

0

0

0

0

-

-

-

-

-

-

-

  -

-

  -

-

-

-

10000

0

0

0

1

001

1

000

1

010

0

001

1

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

10001

0

0

0

1

001

1

000

1

010

0

001

1

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

10010

0

0

0

001

1

000

1

101

1

110

0

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

20


1

10011

0

0

0

1

001

1

000

1

101

1

110

0

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

10100

0

0

0

1

001

1

000

1

011

0

000

1

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

10101

0

0

0

1

001

1

000

1

011

0

000

1

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

10110

0

0

0

1

001

1

000

1

010

1

001

0

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

10111 

0

0

0

1

001

1

000

1

010

1

001

0

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

11000 

0

0

0

1

001

1

000

1

011

1

001

1

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

11001

0

0

0

1

001

1

000

1

011

1

001

1

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

11010

0

0

0

1

001

1

000

1

011

1

110

0

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

11011

0

0

0

1

001

1

000

1

011

1

110

0

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

11100 

0

0

0

1

001

1

000

1

011

1

000

1

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

11101

0

0

0

001

1

000

1

011

1

000

1

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

21


1

11110

0

0

0

1

001

1

000

1

011

1

001

0

110

0

111

1

111

0

000

1

001

1

000

1

011

0

000

1

110

1

11111

0

0

0

1

001

1

000

1

011

1

001

0

110

0

111

1

111

0

000

1

001

1

000

1

011

1

000

1

110

1

5. 10  Запись функций возбуждения и функций выходов в СДНФ

Функции возбуждения T – триггера:

           - -   -      - -       -   -                  - -   -     - -            -  -         -       -      -  -         -  

-             -          -

T0  = (kpabs  v  kpabs)  

4

3

2

1

q

q

q

q

  v  (  kpabs  v  kpabs  v  kpabs  v  kpabs)  

4

3

2

1

q

q

q

q

v  k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v

          -                           -

       k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

           - - - -     - - -        -  - -      -  -         -     -      -              - - -       - -          -   -  

-             - -

T1 = (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v 

kpabs v kpabs v

              -              -                 -  -                - -  -      - -            -   -        -       -      -   - 

        kpabs v kpabs v kpabs) 

4

3

2

1

q

q

q

q

v (kpabs v kpabs v kpabs v kpabs) 

4

3

2

1

q

q

q

q

          -      -             -          -        -                       -                        -

       k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

            - -  -      - -          -  - -      -  -           - - -       - -          -   -        -             - -  

-

T2 = (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v 

kpabs v

                -                 -  -                - - - -     - - -        -    -      -              - - -       - -  

-        

        kpabs v kpabs) 

4

3

2

1

q

q

q

q

v (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v 

kpabs v

                    -      -  -         -          -        -                        -  -               -                 -  -  -

22


        kpabs)

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

            - -  -      - -          -    -       -              - - -       - -          -   -        -             - -  

-              -

T3 = (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v 

kpabs v kpabs v

                     -  -                 - - - -     - - -        -  - -      -  -          - - -       - -            - -  

-      -      -  -    

        kpabs) 

4

3

2

1

q

q

q

q

 v (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v 

kpabs) 

4

3

2

1

q

q

q

q

v

           -  -   -  -         -  -   -            -          -            -  -   -            -  -                -      -  

-  -

               k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v

                   -            -  -       -

        k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

Выражения   в   скобках   можно   упростить   методом   непосредственных 

преобразований. В результате получим следующие выражения:

          - -   -  -               -    -      -  -         -      -            -          -        -                           -

T0 = kpab

4

3

2

1

q

q

q

q

v kab

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

            - -                   -  -                -    -      -  -        -                       -                        -   

-          -

T1 = (kpb v kp v ka) 

4

3

2

1

q

q

q

q

v kab

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

 v

          

-      -

       

k

4

3

2

1

q

q

q

q

  -          -            -  -                - -             -       -  -         -          -        -                  

-  -

23


T2 = (kab v kab v kp) 

4

3

2

1

q

q

q

q

v (kab v kab)

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v

               -                -  -  -

        k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

             -             -  -               -  -      -  -              -                -  -  -  -         -  -  -            

-  -       -

T3 = (kpb v kb) 

4

3

2

1

q

q

q

q

v kb

4

3

2

1

q

q

q

q

v ks

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v

          -          -            -  -   -            -  -                 -      -                -  -                -

       k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

v k

4

3

2

1

q

q

q

q

Функции выходов:

        _  _  _  _                                              _    _          _     

Y0= 

4

3

2

1

q

q

q

q

                                    Y7= q1q2q3q4  

4

3

2

1

q

q

q

q

       _  _  _                                                   _         _          _  _  _

Y1=

4

3

2

1

q

q

q

q

                                     Y8=

4

3

2

1

q

q

q

q

 

4

3

2

1

q

q

q

q

       _  _      _

                                     _  _

Y2=

4

3

2

1

q

q

q

q

                                     Y9= 

4

3

2

1

q

q

q

q

       _  _                                                             _      _

Y3=

4

3

2

1

q

q

q

q

                                     Y10= 

4

3

2

1

q

q

q

q

       _      _  _                                                      _

Y4=

4

3

2

1

q

q

q

q

                                       Y11= 

4

3

2

1

q

q

q

q

       _     _               _ _                                            _  _

Y5=q1q2q3q 4 v  

4

3

2

1

q

q

q

q

                               Y12= 

4

3

2

1

q

q

q

q

            _  _  _      _                                                 _                                

Y6= 

4

3

2

1

q

q

q

q

 

4

3

2

1

q

q

q

q

                   

Y13= 

4

3

2

1

q

q

q

q

5.11

Минимизация функций возбуждения и функций выходов

Для окончательной минимизации функций используется метод Карно. При 

минимизации следует учесть, что все функции являются не полностью 

24


определенными, так как в таблице переходов не использованы состояния  Q14 

и Q15 .  

Стоит отметить, что метод Карно применим непосредственно только к 

функциям не более четырех переменных. В случае более сложных функций 

они минимизируются по частям.

Диаграммы Карно для функций  T0  ,  T1  ,  T2  ,  T3  представлены на рисунках 

15.12, 15.13, 15.14, 15.15.

                                                                T0|                                                       T0|         

T0| |                                                                                                     

                                    

1

q

                              

 

 

 

 

 *

 

 *

  1

 

 

 1

 *

 

 *

 

 

 

 

 1

 *

 1 

 1

 1

 *

 

 

                                               

2

q

         

3

q

   Рисунок 5.12

25


 

  T1|                                                      T1|                                                              T1| |

                                     

1

q

                                                                                      

                              

 

 

 

 

 *

 

 *

  1

 

 

 1

 *

 

 *

 

 

 

 

 1

 *

 

 1

 1

 *

 1 

 

 1

                                               

2

q

         

                            

                             

3

q

 

Рисунок 5.13

                    

T2|                                                       T2|                                                              T3| |

26


                                       

1

q

                              

 

 

 

 

 *

 

 *

  1

 

 

 1

 *

 

 *

 

 

 

 

 1

 *

 

 1

 1

 *

 

 

 1

 1

                                               

2

q

         

3

q

Рисунок 5.14

                                    

            

                                                                  T3|                                                        T3|      

T3| |

27


                                                                                                         

                                    

1

q

                              

 

 

 

 

 *

 

 *

  1

 

 

 1

 *

 

 *

 

 

 

 

 *

 

 *

 

 

 1

                                               

2

q

         

3

q

28


T3| |

 1

 1

 1   1 

 1

 *

 1

 *

 1

 1

 

 1

Рисунок 5.15

В результате минимизации получим следующие выражения для функций T – 

триггеров:

          - -   -  -               -    -      -  -                             -         -    

T0 = kpab

4

3

2

1

q

q

q

q

v kab

4

3

2

1

q

q

q

q

v k q2q3v k q1q2q4 v k q1q2q4

          - -  -  -                  -  -                  -  -               -    -      -  -

T1 = kpb

4

3

2

1

q

q

q

q

v kp

4

3

2

1

q

q

q

q

v ka

4

3

2

1

q

q

q

q

v kab

4

3

2

1

q

q

q

q

v k q2q4v k q2q3v k q1q3q4

          -   -  -                 -  -  -                  -  -               - -  -      -  -              -      -  -      

T2 = kab

4

3

2

1

q

q

q

q

v kab

4

3

2

1

q

q

q

q

v kp

4

3

2

1

q

q

q

q

v kab

4

3

2

1

q

q

q

q

 v kab

4

3

2

1

q

q

q

q

v k q2q3 

           -                   -

       k q1q2q4 v k q1q2q4

29


            -  -  -                   -  -                -  -      -  -                              -  -            -           

-        -  -  -

T3 = kpb

4

3

2

1

q

q

q

q

 v kb

4

3

2

1

q

q

q

q

 v kb

4

3

2

1

q

q

q

q

 v ks

4

3

1

q

q

q

 v k q2q4v k q1q3v k q3q4v k 

q2q3q4

5.17 Граф

0

000

1

001

4

100

2

010

5

101

3

011

 z1 z2 z3

1

30


1

1

1

х1 х2

х1 х2

х1

х3

х3

31


7.

  Заключение

В результате выполнения задания синтезирован блок управления операции 

сложении в АЛУ.

Блок управления построен на основе автомата и имеет минимальный 

аппаратурный состав и обеспечивает формирование выходных сигналов при 

любых сочетаниях сигналов на входах блока.

32


8. Литература

1.

Горнец Н.Н., Рощин А.Г., Соломенцев В.В. Организация ЭВМ и систем.-

М:2006

2.

Рощин А.Г., Половов Р.М. Тексты лекций по дисциплине "Теория 

автоматов".Ч.1.-М. 

3.

Рощин А.Г., Половов Р.М. Тексты лекций по дисциплине "Теория 

автоматов".Ч.2.-М. 

4.

Юхнов В.И.. Тексты лекций по дисциплине "Теория автоматов" СКФ 

МТУСИ 2010

5.

Юхнов В.И.. Методическое указание к курсовой работе СКФ МТУСИ 

2010

33