Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
Аннотация к работе
В соответствии с заданием на курсовое проектирование по курсу «Теория автоматов», необходимо разработать управляющий автомат (УА) с жесткой и программируемой логикой для выполнения операции: Для реализации данной задачи необходимо разработать программу на языке низкого уровня Assembler, отладить ее, и разработать для нее ГСА, по которой строится УА. Заносим в регистр еах число а 2. Заносим в регистр ebx число b Заносим в регистр ebx значение регистра еах В соответствии с алгоритмом реализуем программу на языке Assembler: mov eax, a mov ebx, b mov edi, 0 vcht: sub eax, ebx js modul jmp umn1 modul: neg eax inc edi umn1: mov ebx, eax shl eax, 1 jo finish shl eax, 1 jo finish add eax, ebx jo finish mov ebx, c //P2 test ebx, 80000000h js label3 jmp umn2 label3: neg ebx inc edi umn2: mov edx, 0 // РСМ mov ecx, 31 proverka: test ebx, 1h jnz slozh jmp sdvig slozh: add edx, eax sdvig: rcr edx, 1 rcr ebx, 1 clc dec ecx test ecx, ecx jnz proverka bt edx, 31 rcr ebx, 1 clc shr edx, 1 cmp edi, 1 jz minus jmp rez minus: neg edx dec edx neg ebx jmp rez rez: mov dword ptr y, ebx mov dword ptr y[4], edx jmp f1 finish: mov er, 1 f1: mov edi, 0В данной курсовой работе был разработан в соответствии с заданием управляющий автомат, ориентированный на выполнение заданной микрооперации.
Введение
Эффективность применения современных средств вычислительной техники во всех сферах научной и производственной деятельности оказывает решающее влияние на увеличение производительности труда и непрерывное ускорение научно-технического прогресса.
ЭВМ широко применяются в области экономики, планирования, управления производственной деятельностью предприятий, автоматизации исследований и проектно-конструкторских работ, автоматизации технологических процессов и управления различными объектами и др.
Создание средств вычислительной техники, способных управлять приборами, станками, оборудованием, механизмами немыслимо без применения научно обоснованных методов прикладной теории цифровых автоматов.
В соответствии с заданием на курсовое проектирование по курсу «Теория автоматов», необходимо разработать управляющий автомат (УА) с жесткой и программируемой логикой для выполнения операции: Для реализации данной задачи необходимо разработать программу на языке низкого уровня Assembler, отладить ее, и разработать для нее ГСА, по которой строится УА.
Для реализации операции на языке Assembler выберем разрядность операндов 32 бит. Форматы операндов - целые числа, крайний левый разряд знаковый. Операнды и результат вычисления находятся в оперативной памяти в дополнительном коде.
1.
Разработка алгоритма работы управляющего автомата
1.1 Разработка алгоритма
Заданная микрооперация: .
Построим алгоритм в соответствии с его реализацией на языке Assembler: 1. Заносим в регистр еах число а 2. Заносим в регистр ebx число b
41. Заносим в младшую часть переменной y значение регистра ebx
42. Заносим в старшую часть переменной y значение регистра edx
43. Обнуляем регистр edi. Выход из алгоритма.
44. Заносим в переменную er значение 1. Выход из алгоритма.
1.2 Листинг программы
В соответствии с алгоритмом реализуем программу на языке Assembler: mov eax, a mov ebx, b mov edi, 0 vcht: sub eax, ebx js modul jmp umn1 modul: neg eax inc edi umn1: mov ebx, eax shl eax, 1 jo finish shl eax, 1 jo finish add eax, ebx jo finish mov ebx, c //P2 test ebx, 80000000h js label3 jmp umn2 label3: neg ebx inc edi umn2: mov edx, 0 // РСМ mov ecx, 31 proverka: test ebx, 1h jnz slozh jmp sdvig slozh: add edx, eax sdvig: rcr edx, 1 rcr ebx, 1 clc dec ecx test ecx, ecx jnz proverka bt edx, 31 rcr ebx, 1 clc shr edx, 1 cmp edi, 1 jz minus jmp rez minus: neg edx dec edx neg ebx jmp rez rez: mov dword ptr y, ebx mov dword ptr y[4], edx jmp f1 finish: mov er, 1 f1: mov edi, 0
1.3 Тестирование алгоритма
Для отладки использовалась программа Visual Studio 2008. Этот выбор объясняется тем, что данная программа активно использовалась при прохождении курса лекций по языку Assembler, для разработки лабораторных работ.
Для тестирования алгоритма зададим некоторый набор данных.
Переменные а, b, c представлены в десятичной системе счисления.
Пример 1 (все числа положительные): Набор входных данных: а = 360 b = 124 с = 530
Результат, выданный программой: y = (360-124)*5*530=625400
Рисунок 1
Пример 2 (1 число отрицательное): Набор входных данных: а = -5840 b = 2610 с = 3270
Результат, выданный программой: Y = - 138157500
Рисунок 2
Пример 3 (2 отрицательных числа): Набор входных данных: а = - 6732 b = - 1346 с = 2888
Результат выданный программой: У = - 77773840
Рисунок 3
Пример 4 (переполнение): Набор входных данных: а = 1844674407370955168 b = 1 с = 56
Результат выданный программой:
Рисунок 4
Проверенный вручную результат совпадает с полученным в программе.
Как показала проверка и отладка - результат соответствует истине.
2.
Синтез управляющего автомата с жесткой логикой
Достоинства автоматов с жесткой логикой: высокое быстродействие при реализации алгоритма управления;
хорошо разработанные формальные методы синтеза вплоть до уровня принципиальных схем.
Недостатки: отсутствие гибкости в отношении возможности внедрения изменений в схему, при изменении исходного алгоритма;
пропорциональный рост объема оборудования сложности реализуемого алгоритма;
структура таких устройств на уровне схемы не является регулярной (повторяющейся), а это приводит к повышению сложности проектирования таких устройств и, особенно, при реализации их на СИС и БИС.
2.1 Построение ГСА с учетом задания
Для цифрового автомата берется не весь алгоритм, а та его часть, которая была выделена руководителем курсового проектирования.
Алгоритм построения кодированной ГСА будет включать следующие шаги: 1. Пронумеруем все операторные вершины ГСА программы, предварительно введя пустые операторные (если это нужно), если в ГСА имеются циклы, состоящие только из условных вершин.
2. Каждому оператору ГСА программы поставим в соответствие вполне определенное событие (состояние) ЦА, присвоим ему индекс, соответствующий номеру вершины ГСА программы. При этом необходимо иметь в виду, что одинаковым операторам, стоящим в разных местах ГСА, должны соответствовать различные события (состояния), но одинаковые выходные сигналы. Это обеспечивается сквозной нумерацией операторных вершин ГСА.
3. Начальной вершине ГСА будет соответствовать начальное событие S0, с выходным сигналом у0, конечной - событие Sk с сигналом ук.
В качестве ЦА задан автомат Мура.
2.2 Построение ПТП ЦА Мура
От начального языка задания автомата перейдем к прямой таблице переходов и выходов (ПТП) Мура.
Таблица 1. ПТП ЦА Мура
2.3 Выбор оптимального варианта кодирования состояний автомата
По ПТП ЦА Мура составим систему канонических уравнений (СКУ).
Таблица 2. СКУ ЦА Мура с указанными ценами по Квайну
Для нашего случая ЦА имеем 13 состояний: S=[S0, S1,…, S11, Sk].
Значит, для кодирования состояний достаточно 4 двоичных числа. Желательно, чтобы при переходе из одного состояния в другое менялось значение одного разряда кода состояния или, другими словами, менял свое состояние один триггер. В качестве элементарного автомата задан D триггер, следовательно, будем кодировать по методу №2. Этот метод основан на выборе цены по Квайну уравнения СКУ.
Таблица 3. Таблица кодов
2.4 Синтез функции возбуждения и функции выходов
В качестве элемента памяти по заданию необходимо использовать D-триггер.
Матрица переходов D триггера приведена в таблице 4. управляющий автомат алгоритм кодирование
Таблица 4. Матрица переходов
Qt - Qt 1 Dt
0 - 0 0 - 1 1 - 0 1 - 1 0 0 1 1
Кодирование состояний автомата было произведено в п. 2.3.
В кодировании входных и выходных сигналов нет необходимости, т.к. они сами являются двоичными.
Осуществим построение кодированной ПТП по ПТП ЦА Мура и к ней справа добавляем столбцы для функций возбуждения элементарных автоматов, которые заполняем, используя матрицу переходов D триггера.
Таблица 2. Кодированная ПТП ЦА Мура
Для достижения максимального быстродействия и минимальных аппаратных затрат удобнее работать с инверсными состояниями. Поэтому возьмем двойное отрицание от каждой функции возбуждения и от выходных функций.
Данный автомат может быть реализован разными путями. Состояния автомата закодированы четырьмя разрядами, значит нужно использовать 4 D триггера К155ТМ2. Для реализации функций возбуждения триггеров нам необходимы следующие логические элементы (ЛЭ): К155ЛЛ1 - 2ИЛИ; К155ЛА1 - 4И-НЕ; К155ЛА2 - 8И-НЕ. Для реализации функций выходов необходим дешифратор 4-16 с инверсными выходами. Будем использовать дешифратор К155ИД3, который имеет 4 входа, 16 выходов и два входа разрешения работы. Также необходимо предусмотреть наличие сигналов старта и стопа, для запуска и остановки схемы. При выдаче ук также необходимо остановить работу схемы. Проверим совместимость серий К155, К555. У всех серий тип логики - ТТЛ. Напряжение источника питания: 5,0 В 5%. К155 и К555 имеют логические уровни нуля 0,4 В, единицы 2,4 В. Для выбранных элементов общий вывод - 7, вывод питания - 14.
Для того, чтобы получать входные сигналы и выдавать выходные будем использовать разъем СНП34С-135Р, тип розетка. У него три линии контактов A, B, и C по 45 контактов соответственно.
Общее описание работы схемы
Схема управляется двумя сигналами: START и STOP.
Сигнал START запускает автомат. После прихода сигнала STOP и выдачи сигнала yk схема автоматически останавливается, устанавливаясь в исходное состояние. Для устойчивой работы схемы необходимо сгладить помехи на шине питания. Для фильтрации частотной помех необходимо в непосредственной близости от корпуса каждой микросхемы на входах питания разместить конденсаторы по 68 НФ каждый.
2.6 Расчет быстродействия и максимально допустимой частоты задающего генератора
В качестве элементарного автомата используется D-триггер К555ТМ2 (с динамическим управлением), который по переднему фронту синхроимпульса устанавливает триггер в соответствующее значение.
Для корректного выполнения схемой поставленной задачи необходимо обеспечить такую длину синхроимпульса во время которой микросхемы сменят свои состояния и сформируют выходной сигнал.
Для триггера с динамическим управлением быстродействие рассчитывается следующим образом: по переднему фронту синхроимпульса происходит установка триггера в соответствующее состояние и формируются функции выхода, а по заднему - формируются функции возбуждения. Длина импульса будет рассчитываться как максимальное время задержки элементов схемы по самому длинному пути. Для надежного прихода сигнала на триггер будем брать время задержки равное тзд.
Таблица 6 - Время задержки элементов
Элементы тздвкл, нс тздвыкл, нс
К155ЛА1 15 22
К155ЛА2 15 22
К155ЛАЗ 15 22
К155ЛИ1 19 27
К155ЛЛ1 22 15
К155ЛН1 15 22
К155ЛЕ1 15 22
К155ТМ2 40 25
К155ИД3 33 36
Функции возбуждения: ИД3>ЛЛ1>ЛА2=33 22 15=70 нс тфвозб=70 нс
Т.о. генерация синхроимпульсов должна происходить с частотой 4,54 МГЦ.
2.7 Проверка работоспособности схемы
Проверим один из переходов. Возьмем состояние S0. На прямых выходах триггеров соответственно будет присутствовать логический уровень 1110. На выходе 16 дешифратора DD12 будет присутствовать нулевой сигнал, на всех остальных - единичный. Под действием этих сигналов на логических элементах формируются следующие функции возбуждения: Согласно матрице переходов для D триггера несложно определить, что на прямых выходах триггеров появится следующий логический уровень 1000 (S1) соответственно. Обратившись к прямой таблице переходов, мы убеждаемся в том, что состояние S0 независимо от условий переходит в состояние S1.
Аналогичным образом выполнена проверка переходов S3-S4 и S10-S11.
3.
Синтез управляющего автомата с программируемой логикой
Альтернативой микропрограммного автомата с жесткой логикой является микропрограммный автомат с программируемой логикой.
Достоинства микропрограммного автомата с программируемой логикой: предопределенность структуры микропрограммного автомата, т.е. состава его функциональных узлов, их связей между собой;
гибкость структуры автомата при модификации алгоритма работы (при изменении алгоритма работы достаточно внести изменения в управляющую память, т.е. перепрошить ПЗУ, остальные же блоки остаются без изменения;
Основным недостатком является их меньшее быстродействие (чем с жесткой логикой) с использованием одной и той же электронной базы.
Микропрограммные автоматы с программируемой логикой имеет смысл использовать, когда число операторных и условных вершин в алгоритме >150, но в нашем случае использование таких автоматов необходимо по заданию.
3.1 Выбор формата микрокоманд
Каждое слово в ПЗУ, расположенное по своему адресу в микропрограммном автомате с программируемой логикой называется микрокомандой (МК).
Требуемое количество бит в МК определяет разрядность используемого ПЗУ.
Каждая МК в общем случае содержит следующую информацию: о микрооперациях, выполняемых в данном такте работы автомата;
информацию об адресе следующей МК.
По заданию необходимо разработать микропрограммный автомат с принудительной адресацией.
Кодированную ГСА автомата с программируемой логикой получим из ГСА программы (см. приложение). Причем, для ЦА с программируемой логикой берется весь алгоритм, в отличие от ЦА с жесткой логикой, для которого берется часть алгоритма.
Нумеруются как операционные, так и управляющие вершины.
Формат МК выберем исходя из следующих соображений: т.к. количество вершин (операторных и условных) составляет 46, то для полей адреса перехода (АДРПЕР) к следующей МК выделим 6 бит;
т.к. имеем три входных сигнала, закодируем поле логического условия (ЛУ) 3-мя битами. т.к. задан критерий минимума оборудования, то будем использовать один ЛУ.
Формат микрокоманды будет выглядеть следующим образом:
3.2 Проектирование функциональной схемы
Для хранения МК будем использовать ПЗУ, количество слов которого соответствует количеству строк в табл. 5, а количество бит в слове определяется в соответствии с форматом МК. В итоге получим ПЗУ 64х16.
Разрядность регистра адреса (РА) будет соответствовать разрядности адреса ПЗУ, т.е. 6 бит.
Регистр слова (РСЛ) выберем в соответствии с форматом МК, т.е. 16-ти разрядным.
Порядок работы ЦА с программируемой логикой таков: 1) при поступлении сигнала инициализации регистр адреса (РА) устанавливается в ноль;
2) затем значение РА поступает в ПЗУ;
3) при получении импульса синхронизации, ПЗУ помещает в регистр слова (РСЛ) строку данных, соответствующую адресу, полученному из РА;
4) на следующем шаге происходит сразу две операции - формируется следующий адрес на мультиплексоре и формируется соответствующая управляющая функция на дешифраторе и схеме организации управления (СХОУ);
5) если на выходе формируется yk - работа ЦА останавливается и РА обнуляется;
6) с мультиплексора и первых 4 бит РСЛ на РА поступает адрес следующей строки прошивки.
7) алгоритм переходит на шаг 2.
3.3 Построение таблицы прошивки ПЗУ
Основным отличием автоматов с программируемой логикой является то, что алгоритм управления записывается в управляющую память (УП), которая строится на постоянном запоминающем устройстве (ПЗУ).
ПЗУ - память, из которой можно только считывать информацию, и эта информация структурирована и разбита на слова, каждое из которых записано по своему адресу. Количество адресов кратно 2n, где n - разрядность регистра адреса ПЗУ.
Прошивку ПЗУ выполняем в соответствии с адресом МК: Таблица 3. Таблица прошивки ПЗУ
Адрес слова в ПЗУ Микрокоманда Номера вершин ГСА
АДРПЕР ЛУ1 Y1
0 000001 000 000000 0
1 000010 000 000001 1
2 000011 000 000010 2
3 00010х 001 000011 3,4
4 00011х 001 000101 6,7
5 000100 000 000100 5
6 000110 001 000111 9,10
7 0010х0 000 000110 8
8 001011 000 001010 13
9 001000 000 001001 12
10 001001 000 001000 11
11 0111х1 010 001011 14,15
12 00111х 000 001110 21
13 001111 000 001001 24
14 001101 000 000110 23
15 010000 000 001111 25
16 010001 000 010000 26
17 01001х 011 010001 27,28
18 010011 000 010010 29
19 010100 000 010011 30
20 010101 000 010100 31
21 010110 000 010101 32
22 010111 000 010110 33
23 01х001 011 010111 34,35
24 011010 000 010100 37
25 011000 000 011000 36
26 011100 000 011001 38
27 001100 000 001101 20
28 10000х 011 011010 39,40
29 01111х 010 001011 16,17
30 011х11 010 001100 18,19
31 100100 000 011111 45
32 100010 000 011100 42
33 100000 000 011011 41
34 100011 000 011101 43
35 100100 000 011110 44
36 000000 000 100000 46
Вывод
В данной курсовой работе был разработан в соответствии с заданием управляющий автомат, ориентированный на выполнение заданной микрооперации. Предварительно была разработана ГСА операционного автомата, а затем для отдельной его части были построены схема электрическая принципиальная управляющего автомата с жесткой логикой и функциональная схема МПА с программируемой логикой.