8. Моделирование на ПК с использованием симулятора ModelSim
9. Заключение
10. Список литературы
1. Задание
Спроектировать управляющий цифровой автомат типа Мура, функционирующий согласно заданной ГСА. ГСА строится соединением фрагментов (рис. 1) в заданной последовательности (2, 1, 3, 4). Каждая операторная вершина определяет некоторый выходной сигнал. Количество условных вершин в ГСА определяет входной алфавит автомата. Тип используемых триггеров JK.
2. Введение
Курсовая работа заключается в решении комплексной задачи синтеза дискретного устройства с памятью по заданным условиям работы на заданной элементной базе. Решение должно быть доведено до функциональной схемы устройства (автомата).
Термин автомат, как правило, используется в двух аспектах. С одной стороны, автомат -- устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом аспекте автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q={q1(t), q2(t),..., qn(t)}, в которые он под воздействием входных сигналов переходит скачкообразно, т. е. практически мгновенно, минуя промежуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время.
Цифровой автомат - устройство, предназначенное для преобразования цифровой информации. Входные сигналы в цифровых автоматах представляются в виде конечного множества мгновенных сигналов. Теоретически это означает, что входные сигналы не имеют длительности, хотя практически это не так. Такое допущение упрощает рассмотрение процессов, происходящих в автоматах, так как все события (состояния) должны относиться к фиксированному моменту времени t. Условно также принимается, что число выходных сигналов y(t) конечно и они возникают в результате действия входных сигналов. При этом следует учитывать, что одновременно с появлением выходного сигнала происходит скачкообразный переход автомата из состояния qi(t) в состояние qj(t).
Понятие состояния автомата используется для описания систем, выходы которых зависят не только от входных сигналов в данный момент времени, но и от некоторой предыстории, т. е. сигналов, которые поступили на входы системы ранее. Состояние автомата соответствует некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.
Время для цифрового автомата имеет также важное значение. Для решения задач анализа и синтеза цифровых автоматов обычно вводится автоматное время. Функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности (интервал дискретности).
Общая теория автоматов разбивается на две большие части -- абстрактную теорию автоматов и структурную теорию автоматов. Различие между ними заключается в том, что в абстрактной теории мы отвлекаемся от структуры как самого автомата, так и его входных и выходных сигналов. Не интересуясь способом построения автомата, абстрактная теория изучает лишь те переходы, которые претерпевает автомат под воздействием входных сигналов, и те выходные сигналы, которые он при этом выдает. Абстрактная теория автоматов близка теории алгоритмов, является ее дальнейшей детализацией.
В противоположность абстрактной теории, в структурной теории автоматов рассматриваются прежде всего структуры как самого автомата, так и его входных и выходных сигналов. В структурной теории изучаются способы построения автоматов из элементарных автоматов, способы кодирования входных и выходных сигналов элементарными сигналами и т.п.
3. Абстрактный синтез автомата
Одной из разновидностей языка, позволяющей описывать логические схемы алгоритмов, является язык граф-схем алгоритмов (ГСА).
Граф-схема алгоритма -- ориентированный связный граф, содержащий одну начальную вершину, произвольное число условных и операторных вершин и одну конечную вершину.
Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. Начальная и операторная вершины имеют по одному выходу, конечная вершина выходов не имеет, условная вершина имеет два выхода, помеченных символами 1 и 0. Граф-схема алгоритма удовлетворяет следующим условиям:
1) входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода к входу;
2) каждый выход соединен только с одним входом;
3) любой вход соединяется, по крайней мере, с одним выходом;
4) любая вершина графа лежит, по крайней мере, на одном пути из начальной к конечной вершине;
5) в каждой условной вершине записывается один из элементов множества логических условий A = { A1,A2, ,..., Ak}, разрешается в различных условных вершинах запись одинаковых элементов множества A;
6) в каждой операторной вершине записывается один из элементов множества операторов V={v1,v2,..., vN }., разрешается в различных операторных вершинах запись одинаковых элементов множества V.
Язык ГСА используется очень часто при описании алгоритмов функционирования как самого цифрового автомата, так и программ, выполняющих то или иное действие.
Чтобы построить схему управляющего автомата Мура, нужно задать микропрограмму работы операционного устройства. Микропрограмма операционного блока имеет вид, представленный на рис.2. Микропрограмма выполняется при начальном условии Н = 1. Блок производит выработку управляющих функциональных сигналов в определённой последовательности, зависящей от значений сигналов A0-A3.
Микропрограмма операционного блока
Граф - схема алгоритма (ГСА)
Рисунок 2
4. Структурный синтез автомата
Структурный синтез предполагает физическую реализацию схемы автомата из выбранного набора логических и запоминающих элементов, которая функционировала бы в соответствии с заданными таблицами переходов и выходов исходного абстрактного автомата.
Каждой микрокоманде, отдельно представленной на графе, ставится в соответствие отдельное состояние автомата. Состояния автомата отмечаются управляющими функциональными сигналами соответствующих микрокоманд.
Условия перехода от микрокоманды к микрокоманде представляются в виде конъюнкции входных сигналов, влияющих на переход. Каждая конъюнкция выписывается так, чтобы набор значений входных переменных, обращающих конъюнкцию в 1, соответствовал условию перехода. При безусловном переходе конъюнкция заменяется на константу 1.
q(t) = ?( q(t-1), х(t))
y(t)=?(q(t-1),x(t)), t = 1,2
Для построения автомата используем синхронные RS -триггеры, имеющие следующую таблицу переходов:
Таблица 2.
t
t+1
Примечания
R
S
Q
0
0
Q(t)
Хранение
0
1
1
Установка 1
1
0
0
Установка 0
1
1
---
Запрещенное состояние
Определим количество элементов памяти (триггеров) структурного автомата:
2R - количество различных внутренних состояний структурного автомата
М - мощность алфавита внутренних состояний абстрактного автомата
2R ? М
2R ? 4 => R = 4
Для определения функций возбуждения триггеров составим кодированную таблицу переходов и выходов (табл. 4).
Таблица 4. Кодированная таблица переходов и выходов.
Булевы функции описания выходов схемы и входов триггеров:
8. Моделирование на ПК с использованием симулятора ModelSim
9. Заключение
В данной курсовой работе мы спроектировали управляющий цифровой автомат, функционирующий согласно заданной ГСА. В качестве элементной базы использовались интегральные микросхемы пяти различных типов. Был выполнен абстрактный и структурный синтез заданного автомата, получены функции выходов и возбуждения элементов памяти, а также построена функциональная схема. Также был произведен выбор элементов для физического синтеза схемы, составлено описание автомата на языке VHDL и выполнено моделирование на ПК с использованием симулятора ModelSim.
10. Список литературы1. Методические указания по выполнению курсовой работы по дисциплине «Организация ЭВМ».2. Лекции по предмету «Теория автоматов»