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

 

Введение

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

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

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

В соответствии с заданием на курсовое проектирование по курсу «Теория автоматов», необходимо разработать управляющий автомат (УА) с жесткой и программируемой логикой для выполнения операции:

Для реализации данной задачи необходимо разработать программу на языке низкого уровня Assembler, отладить её, и разработать для неё ГСА, по которой строится УА.

Для реализации операции на языке Assembler выберем разрядность операндов 32 бит. Форматы операндов - целые числа, крайний левый разряд знаковый. Операнды и результат вычисления находятся в оперативной памяти в дополнительном коде.

1.Разработка алгоритма работы управляющего автомата

1.1 Разработка алгоритма

Заданная микрооперация: .

Построим алгоритм в соответствии с его реализацией на языке Assembler:

1.Заносим в регистр еах число а

2.Заносим в регистр ebх число b

.Проверяем знаковый разряд регистра eax, устанавливаем флаги

.Проверяем флаг знака, если него нет - переход к пункту 6

.Инвертируем знаковый разряд регистра еах (находим модуль числа)

.Проверяем знаковый разряд регистра ebx, устанавливаем флаги

.Проверяем флаг знака, если него нет - переход к пункту 9

.Инвертируем знаковый разряд регистра еbх (находим модуль числа)

.Вычитаем ebx из еах

.Проверяем флаг знака, если его нет - переход к пункту 13

.Инвертируем знаковый разряд регистра еах

.Увеличиваем значение регистра edi на единицу

.Заносим в регистр ebx значение регистра еах

.Выполняем логический сдвиг влево регистра eax

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

.Выполняем логический сдвиг влево регистра eax

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

.Прибавляем значение регистра ebx к значению регистра еах

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

.Заносим в регистр ebx число с

.Сравниваем знаковый разряд регистра ebx с единицей

.Если равен 1 - переход к пункту 25

.Инвертируем знаковый разряд регистра ebx

.Увеличиваем значение регистра edi на единицу

.Заносим в регистр edx число 0

.Заносим в регистр ecx число 31

.Проверяем младший разряд регистра ebx

.Если равен 0 - переход к пункту 30

.Прибавляем значение регистра eax к значению регистра edx

.Выполняем арифметический сдвиг вправо регистра edx

.Выполняем арифметический сдвиг вправо регистра ebx

.Очищаем флаг cf

.Уменьшаем значение регистра ecx на единицу

.Сравниваем значение регистра ecx с 0

.Если не равен 0 - переход к пункту 27

.Выделяем младший бит регистра edx

.Выполняем n-ный сдвиг

.Сравниваем значение регистра edi с единицей

.Если не равен - переход к пункту 42

.Инвертируем знаковый разряд регистра edx

.Заносим в младшую часть переменной y значение регистра ebx

.Заносим в старшую часть переменной y значение регистра edx

.Обнуляем регистр edi. Выход из алгоритма.

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

1.2 Листинг программы

В соответствии с алгоритмом реализуем программу на языке Assembler:eax, aebx, bedi, 0:eax, ebxmodulumn1:eaxedi:ebx, eaxeax, 1finisheax, 1finisheax, ebxfinishebx, c //P2ebx, 80000000hlabel3umn2:ebxedi:edx, 0 // РСМecx, 31:ebx, 1hslozhsdvig:edx, eax:edx, 1ebx, 1ecxecx, ecxproverkaedx, 31ebx, 1edx, 1edi, 1minusrez:edxedxebxrez:dword ptr y, ebxdword ptr y[4], edxf1:er, 1:edi, 0

1.3 Тестирование алгоритма

Для отладки использовалась программа Visual Studio 2008. Этот выбор объясняется тем, что данная программа активно использовалась при прохождении курса лекций по языку Assembler, для разработки лабораторных работ.

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

Переменные а, b, c представлены в десятичной системе счисления.

Пример 1 (все числа положительные):

Набор входных данных:

а = 360= 124

с = 530

Результат, выданный программой:= (360-124)*5*530=625400

Рисунок 1

Пример 2 (1 число отрицательное):

Набор входных данных:

а = -5840= 2610

с = 3270

Результат, выданный программой:= - 138157500

Рисунок 2

Пример 3 (2 отрицательных числа):

Набор входных данных:

а = - 6732= - 1346

с = 2888

Результат выданный программой:

У = - 77773840

Рисунок 3

Пример 4 (переполнение):

Набор входных данных:

а = 1844674407370955168= 1

с = 56

Результат выданный программой:

Рисунок 4

Проверенный вручную результат совпадает с полученным в программе.

Как показала проверка и отладка - результат соответствует истине.

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

Достоинства автоматов с жёсткой логикой:

• высокое быстродействие при реализации алгоритма управления;
• хорошо разработанные формальные методы синтеза вплоть до уровня принципиальных схем.

Недостатки:

• отсутствие гибкости в отношении возможности внедрения изменений в схему, при изменении исходного алгоритма;
• пропорциональный рост объёма оборудования сложности реализуемого алгоритма;
• структура таких устройств на уровне схемы не является регулярной (повторяющейся), а это приводит к повышению сложности проектирования таких устройств и, особенно, при реализации их на СИС и БИС.

2.1 Построение ГСА с учетом задания

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

Алгоритм построения кодированной ГСА будет включать следующие шаги:

1.Пронумеруем все операторные вершины ГСА программы, предварительно введя пустые операторные (если это нужно), если в ГСА имеются циклы, состоящие только из условных вершин.

2.Каждому оператору ГСА программы поставим в соответствие вполне определённое событие (состояние) ЦА, присвоим ему индекс, соответствующий номеру вершины ГСА программы. При этом необходимо иметь в виду, что одинаковым операторам, стоящим в разных местах ГСА, должны соответствовать различные события (состояния), но одинаковые выходные сигналы. Это обеспечивается сквозной нумерацией операторных вершин ГСА.

.Начальной вершине ГСА будет соответствовать начальное событие S0, с выходным сигналом у0, конечной - событие Sk с сигналом уk.

В качестве ЦА задан автомат Мура.

2.2 Построение ПТП ЦА Мура

От начального языка задания автомата перейдем к прямой таблице переходов и выходов (ПТП) Мура.

Таблица 1. ПТП ЦА Мура

2.3 Выбор оптимального варианта кодирования состояний автомата

По ПТП ЦА Мура составим систему канонических уравнений (СКУ).

Таблица 2. СКУ ЦА Мура с указанными ценами по Квайну

1 1 4 2 4 1 1 1 1 2 1 1S1(t+1)= S0 S2(t+1)= S1 S3(t+1)=S9S2

S4(t+1)= S3

S5(t+1)= S3 S4

S6(t+1)=S5

S7(t+1)=S68(t+1)= S79(t+1)=S8

S10(t+1)=S9 11(t+1)=S10

Sk(t+1)=S11

Для нашего случая ЦА имеем 13 состояний: S=[S0, S1,…, S11, Sk].

Значит, для кодирования состояний достаточно 4 двоичных числа. Желательно, чтобы при переходе из одного состояния в другое менялось значение одного разряда кода состояния или, другими словами, менял своё состояние один триггер. В качестве элементарного автомата задан D триггер, следовательно, будем кодировать по методу №2. Этот метод основан на выборе цены по Квайну уравнения СКУ.

Таблица 3. Таблица кодов

2.4 Синтез функции возбуждения и функции выходов

В качестве элемента памяти по заданию необходимо использовать D-триггер.

Матрица переходов D триггера приведена в таблице 4.

управляющий автомат алгоритм кодирование

Таблица 4. Матрица переходов

Qt - Qt+1Dt0 - 0 0 - 1 1 - 0 1 - 10 0 1 1

Кодирование состояний автомата было произведено в п. 2.3.

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

Осуществим построение кодированной ПТП по ПТП ЦА Мура и к ней справа добавляем столбцы для функций возбуждения элементарных автоматов, которые заполняем, используя матрицу переходов D триггера.

Таблица 2. Кодированная ПТП ЦА Мура

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

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

Выходные функции:1=2=3=4=5=6=7=8=9=10=11=k=

2.5 Реализация ЦА на логических элементах

Выбор подходящей серии элементов

Данный автомат может быть реализован разными путями. Состояния автомата закодированы четырьмя разрядами, значит нужно использовать 4 D триггера К155ТM2. Для реализации функций возбуждения триггеров нам необходимы следующие логические элементы (ЛЭ): К155ЛЛ1 - 2ИЛИ; К155ЛА1 - 4И-НЕ; К155ЛА2 - 8И-НЕ. Для реализации функций выходов необходим дешифратор 4-16 с инверсными выходами. Будем использовать дешифратор К155ИД3, который имеет 4 входа, 16 выходов и два входа разрешения работы. Также необходимо предусмотреть наличие сигналов старта и стопа, для запуска и остановки схемы. При выдаче уk также необходимо остановить работу схемы. Проверим совместимость серий К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ТM2 (с динамическим управлением), который по переднему фронту синхроимпульса устанавливает триггер в соответствующее значение.

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

Для триггера с динамическим управлением быстродействие рассчитывается следующим образом: по переднему фронту синхроимпульса происходит установка триггера в соответствующее состояние и формируются функции выхода, а по заднему - формируются функции возбуждения. Длина импульса будет рассчитываться как максимальное время задержки элементов схемы по самому длинному пути. Для надёжного прихода сигнала на триггер будем брать время задержки равное tзд.

Таблица 6 - Время задержки элементов

Элементыtздвкл, нсtздвыкл, нсК155ЛА11522К155ЛА21522К155ЛА31522К155ЛИ11927К155ЛЛ12215К155ЛН11522К155ЛЕ11522К155ТМ24025К155ИД33336

Функции возбуждения:

ИД3?ЛЛ1?ЛА2=33+22+15=70 нсфвозб=70 нс

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

ИД3?ЛЛ1?ЛА3=33+22+15=70 нсфвых=мах+tтр =40+70=110 нс/2=max{tфвозб, tфвых}=110 нс

Т=220 нс=1/(220*10-9)=4,54 Мгц

Т.о. генерация синхроимпульсов должна происходить с частотой 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-ти разрядным.

Порядок работы ЦА с программируемой логикой таков:

) при поступлении сигнала инициализации регистр адреса (РА) устанавливается в ноль;

) затем значение РА поступает в ПЗУ;

) при получении импульса синхронизации, ПЗУ помещает в регистр слова (РСЛ) строку данных, соответствующую адресу, полученному из РА;

) на следующем шаге происходит сразу две операции - формируется следующий адрес на мультиплексоре и формируется соответствующая управляющая функция на дешифраторе и схеме организации управления (СхОУ);

) если на выходе формируется yk - работа ЦА останавливается и РА обнуляется;

) с мультиплексора и первых 4 бит РСЛ на РА поступает адрес следующей строки прошивки.

) алгоритм переходит на шаг 2.

3.3 Построение таблицы прошивки ПЗУ

Основным отличием автоматов с программируемой логикой является то, что алгоритм управления записывается в управляющую память (УП), которая строится на постоянном запоминающем устройстве (ПЗУ).

ПЗУ - память, из которой можно только считывать информацию, и эта информация структурирована и разбита на слова, каждое из которых записано по своему адресу. Количество адресов кратно 2n, где n - разрядность регистра адреса ПЗУ.

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

x1 001010011

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

y1 00001000100001100100001010011000111010000100101010010110110001101011100111110000100011001010011101001010110110101111100011001110101101111100111011111011111

Прошивку ПЗУ выполняем в соответствии с адресом МК:

Таблица 3. Таблица прошивки ПЗУ

Адрес слова в ПЗУМикрокомандаНомера вершин ГСААДРПЕРЛУ1Y1000000100000000001000010000000001120000110000000102300010х0010000113,4400011х0010001016,75000100000000100560001100010001119,1070010х000000011088001011000001010139001000000001001121000100100000100011110111х101000101114,151200111х0000011102113001111000001001241400110100000011023150100000000011112516010001000010000261701001х01101000127,28180100110000100102919010100000010011302001010100001010031210101100000101013222010111000010110332301х00101101011134,3524011010000010100372501100000001100036260111000000110013827001100000001101202810000х01101101039,402901111х01000101116,1730011х1101000110018,19311001000000111114532100010000011100423310000000001101141341000110000111014335100100000011110443600000000010000046

Заключение

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

Введение Эффективность применения современных средств вычислительной техники во всех сферах научной и производственной деятельности оказывает решающее вл

Больше работ по теме: