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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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, 8 000 0000h

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=625 400

Рисунок 1

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

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

а = -5840

b = 2610

с = 3270

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

Y = - 138 157 500

Рисунок 2

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

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

а = - 6732

b = - 1346

с = 2888

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

У = - 77 773 840

Рисунок 3

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

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

а = 1 844 674 407 370 955 264

b = 1

с = 56

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

Рисунок 4

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

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

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

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

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

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

Недостатки:

отсутствие гибкости в отношении возможности внедрения изменений в схему, при изменении исходного алгоритма;

пропорциональный рост объёма оборудования сложности реализуемого алгоритма;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для нашего случая ЦА имеем 13 состояний: S=[S₀, S₁,…, S₁₁, S_k].

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

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

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

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

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

управляющий автомат алгоритм кодирование Таблица 4. Матрица переходов

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

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

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

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

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

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

Выходные функции:

y₁=

y₂=

y₃=

y₄=

y₅=

y₆=

y₇=

y₈=

y₉=

y₁₀=

y₁₁=

y_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 и выдачи сигнала y_k схема автоматически останавливается, устанавливаясь в исходное состояние. Для устойчивой работы схемы необходимо сгладить помехи на шине питания. Для фильтрации частотной помех необходимо в непосредственной близости от корпуса каждой микросхемы на входах питания разместить конденсаторы по 68 нФ каждый.

2.6 Расчёт быстродействия и максимально допустимой частоты задающего генератора

В качестве элементарного автомата используется D-триггер К555ТM2 (с динамическим управлением), который по переднему фронту синхроимпульса устанавливает триггер в соответствующее значение.

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

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

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

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

ИД3>ЛЛ1>ЛА2=33+22+15=70 нс

t_фвозб=70 нс Функции выходов:

ИД3>ЛЛ1>ЛА3=33+22+15=70 нс

t_фвых=мах+t_тр =40+70=110 нс

T/2=max{t_фвозб, t_фвых}=110 нс Т=220 нс

F=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-ти разрядным.

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

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

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

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

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

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

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

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

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

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

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

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

x1 001

x2 010

x3 011

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

y1 1

y2 10

y3 11

y4 100

y5 101

y6 110

y7 111

y8 1 000

y9 1 001

y10 1 010

y11 1 011

y12 1 100

y13 1 101

y14 1 110

y15 1 111

y16 10 000

y17 10 001

y18 10 010

y19 10 011

y20 10 100

y21 10 101

y22 10 110

y23 10 111

y24 11 000

y25 11 001

y26 11 010

y27 11 011

y28 11 100

y29 11 101

y30 11 110

y31 11 111

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

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

Заключение

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