Каждой условной вершине содержательной ГСА ставится в соответствие один из входных сигналов управляющего автомата X1…Xm, список которых приведен в таблице 3.

Таблица 3

Далее в полном соответствии с содержательной ГСА строится отмеченная ГСА, условным вершинам которой приписывается один из входных сигналов УА, а операторным вершинам - одна из МК (приложение В).

Получаем ГСА, размеченную для модели Мили символами a₀…a₇, для модели Мура символами b₀…b₁₁.

6. Построение графов автомата для моделей Мили и Мура

На основе отмеченной ГСА построены графы автомата для модели Мили (приложение Г) и для модели Мура (приложение Д).

Граф автомата Мили имеет 8 вершин, соответствующих состояниям автомата a₀,…,a₇. Дуги его отмечены входными сигналами, действующими на каждом переходе, и набором выходных сигналов, вырабатываемых УА на данном переходе.

Граф автомата Мура имеет 12 вершин, соответствующих состояниям автомата b₀,…,b₁₁, каждое их которых (кроме фиктивных) определяет наборы выходных сигналов y₀,…,y₈ УА, а дуги графа отмечены входными сигналами, действующими на данном переходе.

7. Выбор и обоснование функциональной схемы управляющего автомата и типов элементов памяти

Рассмотрим некоторые варианты возможных структурных схем УА, предложенные в [2]:

классическая структура УА пригодна для реализации любого УА, но она не является минимальной с точки зрения цены КС;

модифицированная классическая структура на основе регистра и дешифратора, использование которого понижает цену схемы классического варианта;

структура УА на основе сдвигового регистра с выбором унитарного кодирования внутренних состояний целесообразно использовать только в тех случаях, когда число разрядов кода ненамного меньше числа внутренних состояний, иначе возникнут значительные затраты на память автомата, которые поглотят выигрыш от уменьшения цены КС;

структура на основе счетчика выгодна, когда граф проектируемого автомата имеет большое количество последовательных (стандартных) переходов и незначительное число нестандартных;

модифицированная структура на основе счетчика с использованием дешифратора, введение которого приводит к снижению цены схемы.

После рассмотрения данных вариантов структур УА, опираясь на графы моделей Мура и Мили, можно сделать вывод о том, что для реализации автомата по модели Мура следует использовать структуру на основе регистра и дешифратора. Для реализации модели Мили можно использовать вариант на основе регистра и дешифратора, а также попробовать вариант на основе счетчика и дешифратора.

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

Для кодирования состояний автомата Мура потребуется 4 разряда. Поэтому для реализации управляющего автомата на основе модели Мура потребуется 4-х разрядный регистр и дешифратор.

8. Кодирование внутренних состояний автомата

В управляющем автомате в качестве ЭП могут использоваться как D-триггеры, так и RS-триггеры. Также могут использоваться и счетчики.

При использовании D-триггеров в качестве элементов памяти при переходе из одного состояния в другое сигналы возбуждения должны быть поданы на те триггеры, которые в коде состояния содержат единицу. Отсюда следует, что для получения минимального кодирования необходимо закодировать состояния кодами, содержащими наименьшее количество единиц. Для этого используют инверсные таблицы переходов.

Для RS-триггеров лучше использовать соседнее кодирование, так как именно этот способ минимизирует число переключений ЭП.

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

8.1 Кодирование состояний для модели Мили на D-триггерах

Составим инверсную таблицу переходов (см. таблицу 4) и закодируем состояния четырехразрядными двоичными числами, в которые будет входить наименьшее число единиц.

Таблица 4

Как видно из таблицы 4, состояние a₀ с наибольшим числом переходов в него кодируется 000. Состояния с меньшим числом переходов обозначаются кодом с одной единицей, затем с двумя и до тех пор, пока все состояния графа не будут закодированы.

8.2 Кодирование состояний для модели Мура на D-триггерах

Составим инверсную таблицу переходов (см. таблицу 5) и закодируем состояния четырехразрядными двоичными числами, в которые будет входить наименьшее число единиц.

Таблица 5

8.3 Кодирование состояний для модели Мили на RS-триггерах

Составим матрицу переходов М и произведем кодирование состояний автомата [4].

1) K(a₀)=000

K(a₁)=001

2) =2B={1}

C₁={011, 101}

K(a₂)=011

3) =3B={2}

C₂={111, 010}

K(a₃)=111

4) =4B={3, 0}

C₃={101, 110}

C₀={100, 010}

W₁₀₁=1+2=3

W₁₁₀=1+2=3

W₁₀₀=2+1=3

W₀₁₀=2+1=3

K(a₄)=101

5) =5B={4}

C₄={100}

K(a₅)=100

6) =7B={4, 0}

C₄={}

C₀={010}

K(a₇)=010

7) K(a₆)=110

8.4 Кодирование состояний для модели Мура на RS-триггерах

Составим матрицу переходов М и произведем кодирование состояний автомата [4].

1) K(b₀)=0000

2) K(b₁)=0001

3) 2) =2B={1}

4) C₁={0011,0101,1001}

5) K(b₂)=0011

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

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

3) =3B={2}

C₂={1011,0111,0010}

K(b₃)=0010

4) =4B={2,3}

C₂={1011, 0111}

C₃={1010, 0110}

W₁₀₁₁=1+2=3

W₀₁₁₁=1+2=3

W₁₀₁₀=2+1=3

W₀₁₁₀=2+1=3

K(b₄)=1011

5) =5B={4, 0}

C₄={1111, 1001, 1010}

C₀={1000, 0100}

W₁₁₁₁=1+4=5

W₁₀₀₁=1+2=3

W₁₀₁₀=1+2=3

W₁₀₀₀=2+1=3

W₀₁₀₀=4+1=5

K(b₅)=1001

6) =6B={5}

C₅={1101, 1000}

K(b₆)=1101

7) =7B={5}

C₅={1000}

K(b₇)=1000

8) =8B={5,6,7}

C₅={}

C₆={0101, 1111, 1100}

C₇={1010}

W₀₁₀₁=2+1+3=6

W₁₁₁₁=2+1+3=6

W₁₁₀₀=2+1+1=4

W₁₀₁₀=2+3+1=6

K(b₈)=1100

9) =10B={5,8}

C₅={}

C₈={0100, 1110}

W₀₁₀₀=3+1=4

W₁₁₁₀=3+1=4

K(b₁₀)=1110

10) =11B={5,8,10,0}

C₅={}

C₁₀={0110, 1111}

C₈={0100}

C₀={}

W₀₁₁₀=2+4+2+1=9

W₁₁₁₁=4+2+2+1=9

W₀₁₀₀=1+3+1+2=7

K(b₁₁)=0100

11) =9B={8, 10, 11}

C₈={}

C₁₀={0110, 1111}

C₁₁={0101}

W₀₁₁₀=2+1+1=4

W₁₁₁₁=2+1+2=5

W₀₁₀₁=2+3+1=6

K(b₉)=0110

8.5 Кодирование состояний для модели Мили на счетчике

Закодируем состояния таким образом, чтобы разность кодов между соседними состояниями составляла единицу (см.таблицу 6).

Таблица 6

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

9. Получение логических уравнений и их совместная минимизация

Построим структурные таблицы переходов и выходов. Получим логические уравнения для функции возбуждения ЭП и функций выходов и их совместно минимизируем.

9.1 Получение и минимизация логических уравнений для модели Мили на D-триггерах

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

Таблица 7

Из таблицы получим логические выражения для каждой функции возбуждения D-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний a_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

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

Цена комбинационной схемы по Квайну C=49.

9.2 Получение и минимизация логических уравнений для модели Мура на D-триггерах

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

Таблица 8

Из таблицы получим логические выражения для каждой функции возбуждения D-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний b_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

После выделения общих частей в логических выражениях и некоторого их упрощения получаем логические уравнения для построения функциональной схемы УА (функции выхода остались те же).

Цена комбинационной схемы по Квайну C=87.

9.3 Получение и минимизация логических уравнений для модели Мили на RS-триггерах

Структурная таблица переходов и выходов представлена в таблице 9

Таблица 9

Из таблицы получим логические выражения для каждой функции возбуждения RS-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний a_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

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

Цена комбинационной схемы по Квайну C=45.

9.4 Получение и минимизация логических уравнений для модели Мура на RS-триггерах

Таблица 10

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

Из таблицы получим логические выражения для каждой функции возбуждения RS-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний b_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

После выделения общих частей в логических выражениях и некоторого их упрощения получаем логические уравнения для построения функциональной схемы УА (функции выхода не изменились).

Цена комбинационной схемы по Квайну C=91.

9.5 Получение и минимизация логических уравнений для модели Мили на счетчике

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

Таблица 11

Из таблицы получим логические выражения для каждой функции возбуждения счетчика, а также для функций выходов как конъюнкции соответствующих исходных состояний a_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

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

Цена комбинационной схемы по Квайну C=49.

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

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

Наиболее оптимальной по аппаратурным затратам является модель Мили на RS-триггерах. Ее цена по Квайну составляет 45, поэтому построение функциональной схемы будем производить для нее.

Функциональная схема построена в основном логическом базисе в полном соответствии с приведенной для модели Мили системой логических уравнений для выходов и функций возбуждения ЭП. Кроме того, на схему подаются сигналы синхронизации C и начальной установки B.

Заключение

В ходе выполнения курсовой работы был разработан автомат, управляющий операцией умножения двоичных чисел с ПЗ в ДК с автоматической коррекцией. Были рассмотрены 5 вариантов построения управляющего автомата: 3 варианта для модели Мили (на D-триггерах, на RS-триггерах и на счетчике) и 2 варианта для модели Мура (на D- и на RS-триггерах). Оказалось, что наименьшую комбинационную схему дает модель Мили с использованием RS-триггеров. Причем, в схеме использован дешифратор на 3 разряда.

Приложение А

Функциональная схема операционного автомата

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

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

Приложение Б

Граф автомата для модели Мили

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

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

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