Разработка цифрового автомата Мили, содержащий в качестве памяти D-триггер
Содержание
Введение
1. Анализ технического задания
. Разработка таблиц работы и
графа автомата Мили
3. Синтез автомата
4. Разработка входного и выходного
преобразователей
5. Выбор и обоснование серии
микросхем
Заключение
Список использованной литературы
Приложение А. Спецификация
Введение
Потребность в вычислениях возникла у людей на
самых ранних стадиях развития человеческого общества. Причем с самого начала
для облегчения счета люди использовали различные приспособления. Многие из них
были весьма интересными и остроумными по принципу действия, но все они
обязательно требовали, чтобы в процессе вычислений активно участвовал
человек-оператор. Качественно новый этап развития вычислительной техники
наступил с изобретением и созданием электронных вычислительных машин, которые
работают автоматически, без участия человека, в соответствии с заранее заданной
программой.
В настоящее время электронные вычислительные
машины в основном используются для решения сложных математических и инженерных
задач, в качестве управляющих машин в промышленности и военной технике, а так
же в сфере обработки информации.
Теория автоматов - раздел дискретной математики,
изучающий абстрактные автоматы - вычислительные машины, представленные в виде
математических моделей - и задачи, которые они могут решать. Теория автоматов
наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную
информацию по шагам в дискретные моменты времени и формирует результат по шагам
заданного алгоритма.
Для формального описания узлов ЭВМ при их
анализе и синтезе используется аппарат алгебры логики. Основные положения
алгебры логики разработал в XIX в. английский математик Джордж Буль. Алгебру
логики называют также булевой алгеброй.
Логические элементы - устройства,
предназначенные для обработки информации в цифровой форме (последовательности
сигналов высокого - «1» и низкого - «0» уровней в двоичной логике,
последовательность "0", "1" и "2" в троичной
логике, последовательности "0", "1", "2",
"3", "4", "5", "6", "7",
"8"и "9" в десятичной логике).
Триггер - это устройство последовательного типа
с двумя устойчивыми состояниями равновесия, предназначенное для записи и
хранения информации. Под действием входных сигналов триггер может переключаться
из одного устойчивого состояния в другое. При этом напряжение на его выходе
скачкообразно изменяется.
Как правило, триггер имеет два выхода: прямой и
инверсный. Число входов зависит от структуры и функций, выполняемых триггером.
По способу записи информации триггеры делят на асинхронные и синхронизируемые (тактируемые).
В асинхронных триггерах информация может записываться непрерывно и определяется
информационными сигналами, действующими на входах в данный момент времени. Если
информация заносится в триггер только в момент действия так называемого
синхронизирующего сигнала, то такой триггер называют синхронизируемым или
тактируемым. Помимо информационных входов тактируемые триггеры имеют тактовый
вход синхронизации. В цифровой технике приняты следующие обозначения входов
триггеров:- раздельный вход установки в единичное состояние (напряжение
высокого уровня на прямом выходе Q);- раздельный вход установки в нулевое
состояние (напряжение низкого уровня на прямом выходе Q);- информационный вход
(на него подается информация, предназначенная для занесения в триггер);- вход
синхронизации;
Т - счетный вход.
Наибольшее распространение в цифровых
устройствах получили RS-триггер с двумя установочными входами, тактируемый
D-триггер и счетный Т-триггер.
Регистр - последовательное логическое
устройство, используемое для хранения n-разрядных двоичных слов (чисел) и
выполнения преобразований над ними.
Регистр представляет собой упорядоченную
последовательность триггеров, число которых соответствует числу разрядов в
слове. С каждым регистром обычно связано комбинационное цифровое устройство, с
помощью которого обеспечивается выполнение некоторых операций над словами.
Фактически любое цифровое устройство можно
представить в виде совокупности регистров, соединённых друг с другом при помощи
комбинационных цифровых устройств.
Основой построения регистров являются
D-триггеры, RS-триггеры.
1.
Анализ технического задания
В данной курсовой работе требуется разработать
цифровой автомат Мили, содержащий в качестве памяти D-триггер.
Необходимо проанализировать работу выбранного D-триггера.триггер
(от английского DELAY) называют информационным триггером, также триггером
задержки. D - триггер бывает только синхронным.
Он может управляться (переключаться) как уровнем
тактирующего импульса, так и его фронтом. Для триггера типа D, состояние в интервале
времени между сигналом на входной линии и следующим состоянием триггера
формируется проще, чем для любого другого типа.
Правило работы:
Если на вход D
триггера подается «0», то триггер устанавливает на выходе Q
«0» и хранит его. При условии, если на вход D
триггера подается «1» , триггер устанавливается в «1» и хранит её. Таким
образом что подается на вход D-триггера
то он и хранит.
Рис1. Общая схема D-триггера
Цифровое устройство с памятью называется цифровым
автоматом. Так как число переменных на входе, выходе и число состояний является
конечным числом. Таким образом он задаётся тройным множеством:
- входные сигналы;
- выходные состояния;
- множество состояний автомата;
А так же функцией переходов, которая
определяет состояние перехода:
- функция переходов;
- функция выходов;
Такой автомат называется автоматом
Мили.
Рис.2. Общая схема цифрового
автомата
Схема состоит из переключателей
схемы F,
элементарных автоматов Q1Q2 и
преобразователей П1 и П2. Входной алфавит автомата
представляет собой множество букв x1...x3.
Преобразователь П1, называемый преобразователем входного алфавита,
преобразовывает символы входного алфавита x1…x3 в
совокупность двоичных значений сигналов на физических входах автомата , . Выходной
алфавит автомата представляет собой множество букв y1…y4.
Преобразователь П2, называемый преобразователем выходного алфавита,
преобразует совокупность двоичных значений сигналов на физических выходах
автомата , в символы
выходного алфавита y1…y4.
Переключательная схема F определяет
логику работы автомата. На ее входы подаются сигналы с физических входов
автомата , и с выходов
элементарных автоматов Q1, Q2, а выходы
схемы соединяются с физическими выходами автомата , и со
входами элементарных автоматов.
2.
Разработка таблиц работы и графа автомата Мили
В данной курсовой работе необходимо задать
цифровой автомат в виде таблицы переходов, таблицы выходов и графа.
Таблица переходов состояния автомата.
|
Z0
|
Z1
|
Z2
|
Z3
|
X1
|
Z2
|
Z0
|
Z1
|
Z3
|
X2
|
Z3
|
Z2
|
Z1
|
Z0
|
X3
|
Z0
|
Z3
|
Z2
|
Z1
|
Таблица выхода состояния автомата Мили
|
Z0
|
Z1
|
Z2
|
Z3
|
y4
|
y2
|
y4
|
y3
|
X2
|
y3
|
y2
|
y1
|
y2
|
X3
|
y4
|
y3
|
y1
|
y1
|
Для работы автомата необходимо произвести
синтез. Для этого определяется число автоматов:
где k - число
физических входов. В данной работе представлены 3 буквы входных сигналов,
поэтому число физических входов будет равно 2 (квадратные скобки «наружу»
указывают на то что число округлено в сторону большего целого).
где m - число
физических выходов, следовательно, число физических выходов равно 2.
Граф - это совокупность непустого
множества вершин и множества пар вершин. автомат мили триггер
преобразователь
Объекты представляются как вершины,
или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения
виды графов могут различаться направленностью, ограничениями на количество
связей и дополнительными данными о вершинах или рёбрах.
В данной работе граф представляет
цифровой автомат, в котором вершины представляют состояние.
Рис. 3. Граф цифрового автомата.
3.
Синтез автомата
Структурным синтезом занимается структурная
теория автоматов. Основная цель этой теории - нахождение общих приемов
построения сложных структурных схем автоматов из более простых автоматов,
называемых элементарными автоматами. На практике в большинстве случаев
применяют элементарные автоматы с двумя внутренними состояниями. В процессе
синтеза элементарные автоматы соединяют между собой с помощью логических
элементов.
Кодирование сигналов для задания
схемы П1.
1-ая таблица - кодирование физического входа
-ая таблица - кодирование состояния
3-я таблица - кодирование физических
выходов ,.
-ая таблица
-ая таблица
-я таблица.
Таблица синтеза состоит из n
столбцов и m строк. При
составлении таблицы синтеза цифрового устройства необходимо придерживаться
следующих правил:
1. Столбцы и заполняются
в зависимости от входной комбинации и состояний в S-том такте . По таблице
переходов ЦУ (таблица 1) определяется, в какое состояние переходит
ЦУ, и его код (код определяется по таблице
кодирования) заполняется в соответствующую строку таблицы синтеза.
. Для заполнения столбцов функций
возбуждения D1, D2 берутся из
строчки таблицы синтеза значения и , подставляются в характеристическое
уравнения или в таблицу состояний D-триггера
(таблица 3) и определяются значения D1 и D2 для этой
строки.
. Столбцы функций выходов заполняются
в соответствии с входной комбинацией состояний и таблицей
выходов (таблица 2). Подставляется в строчку значения в
соответствии с таблицей выходов и с таблицей кодирования выходов .
. Для входной комбинации входная
переменная отсутствует,
поэтому клетки строчек, принадлежащих входной комбинации ,
заполняются прочерками-неопределенностями. Все неопределенности в таблице
синтеза могут доопределяться любыми значениями - «нулем» или «единицей».
Таблица синтеза цифрового автомата.
|
|
|
D1D2
|
|
|
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
1
|
0
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
1
|
1
|
0
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
Нахождение переключательных функций
для вычисления D1, D2, , , которая
зависит от четырех переменных, обозначены в 1-4 столбцах , ,, использует
диаграмму Вейча.
Минимизация переключательной функции
с помощью диаграмм Вейча. С целью минимизации совершенно дизъюнктивной
нормальной формы используется диаграмма Вейча, которая представляет собой один
из табличных способов. Диаграмма Вейча состоит из клеток, поэтому для этой
переменной требуется клеток.
Каждая клетка номеруется с помощью чисел «0» и «1». Номера клеток присваиваются
таким образом, что бы номера соседних клеток в двоичном коде отличались не
более чем на 1 разряд. Для того что бы с помощью диаграмм Вейча задать функцию,
в каждую клетку необходимо занести значения , которое она принимает на наборе .
Нумерация клеток диаграммы Вейча
состоит так что их двоичные номера у соседних клеток отличаются только в одном
разряде.
Для минимизации переключательной
функции с помощью диаграмм Вейча и их синтеза в форме минимальной дизъюнктивной
нормальной форме (МДНФ). Взаимно соседние клетки в диаграмме Вейча заполненные
единицами должны быть объединены площадями минимизации. Площади минимизации
состоит из взаимно
соседних клеток и имеет форму квадрата или прямоугольника.
Рис. 4. Диаграмма Вейча для .
Рис. 5. Диаграмма Вейча для .
Рис. 6. Диаграмма Вейча для .
Рис. 7. Диаграмма Вейча для .
4.
Работа входного и выходного преобразователей
Входной преобразователь - устройство на входе
системы или прибора, преобразующее входные воздействия в сигналы, удобные для
дальнейшей обработки, передачи и регистрации или для согласования работы систем
с различными входными - выходными параметрами. В зависимости от физической
природы сигнала, формы его представления, принципа действия источника и
приёмника сигналов бывают Входной преобразователь неэлектрических величин
(например, давления, перемещения, температуры и т. д.) в электрические (ток,
напряжение, заряд) и наоборот; электрических и неэлектрических величин в код
(например, цифровой, позиционный и др.) и наоборот. Основное требование к
входному преобразователю: максимальная точность передачи входного воздействия и
минимальное влияние на работу согласуемых систем или устройств. В соответствии
с таблицей кодирования входных сигналов строится таблица синтеза входного
преобразователя.
Таблица синтеза входного преобразователя.
|
|
|
|
|
0
|
0
|
0
|
-
|
-
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
-
|
-
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
-
|
-
|
1
|
1
|
0
|
-
|
-
|
1
|
1
|
1
|
-
|
-
|
Рис. 8. Диаграмма Вейча для .
Рис. 9. Диаграмма Вейча для .
Рис. 10. Схема входного
преобразователя.
|
|
|
|
|
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
Рис. 11. Диаграмма Вейча для
Рис. 12. Диаграмма Вейча для
Рис. 13. Диаграмма Вейча для
Рис. 14. Диаграмма Вейча для
Рис. 15. Схема выходного
преобразователя
5. Выбор
и обоснование серии микросхем
В вычислительной технике применяют разные
логики. Самые распространенные:
· Транзисторно-транзисторная логика
(ТТЛ);
· Комплементарная логика на
транзисторах металл-оксид-полупроводник;
· Эмиттерно-связанная логика;
Транзисторно-транзисторная логика (ТТЛ, TTL) -
разновидность цифровых логических микросхем, построенных на основе биполярных
транзисторов и резисторов. Название транзисторно-транзисторный возникло из-за
того, что транзисторы используются как для выполнения логических функций
(например, И, ИЛИ), так и для усиления выходного сигнала (в отличие от
резисторно-транзисторной и диодно-транзисторной логики).
КМОП (К-МОП; комплементарная логика на
транзисторах металл-оксид-полупроводник; КМДП[1]; англ. CMOS,
Complementary-symmetry/metal-oxide semiconductor) - технология построения
электронных схем. В технологии КМОП используются полевые транзисторы с
изолированным затвором с каналами разной проводимости. Отличительной
особенностью схем КМОП по сравнению с биполярными технологиями (ТТЛ, ЭСЛ и др.)
является очень малое энергопотребление в статическом режиме (в большинстве
случаев можно считать, что энергия потребляется только во время переключения
состояний). Отличительной особенностью структуры КМОП по сравнению с другими
МОП-структурами (N-МОП, P-МОП) является наличие как n-, так и p-канальных
полевых транзисторов; как следствие, КМОП-схемы обладают более высоким
быстродействием и меньшим энергопотреблением, однако при этом характеризуются
более сложным технологическим процессом изготовления и меньшей плотностью
упаковки.
Эмиттерно-связанная логика (ЭСЛ) - семейство
цифровых интегральных микросхем на основе дифференциальных транзисторных
каскадов. ЭСЛ является самой быстродействующей из всех типов логики,
построенной на биполярных транзисторах. Это объясняется тем, что транзисторы в
ЭСЛ работают в линейном режиме, не переходя в режим насыщения, выход из
которого замедлен. Низкие значения логических перепадов в ЭСЛ-логике
способствуют снижению влияния на быстродействие паразитных ёмкостей.
Таблица сравнения логик.
Вид
логики
|
«0»
|
«1»
|
Серии
|
Быстродействие
|
Потребление
|
ТТЛ
|
0В
- 0.4В
|
2.4В
- 5В
|
155
555 1530 1533
|
10
н.с. 4 н.с. 3 н.с.
|
10микро
Вт 4микро Вт
|
КМОП
|
0В
- 0.6В
|
3В
- 12В
|
561
564 1564
|
0т
100 н.с.
|
1
микро Вт
|
ЭСЛ
|
-5.2В
- -1.8В
|
1.5В
- 0В
|
500
1500
|
До
600 микро Вт
|
Наиболее удобным и выгодным вариантом для
разработки данного цифрового автомата является ТТЛ - логика.
Заключение
В ходе выполнения данной курсовой
работы был разработан цифровой автомат Мили по заданным таблицам переходов и
выходов. Разработана таблица синтеза цифрового автомата, по которым были
найдены переключательные функции для вычисления D1, D2, , и
минимизированы с помощью диаграмм Вейча. Также построены входные и выходные
преобразователи в соответствии с таблицами кодирования входных и выходных
сигналов.
Список
используемой литературы
1. Методы синтеза цифровой
схемотехники. Кропотов Ю.А
. Статистический анализ и синтез
радиотехнических устройств и систем. Харисов В.Н., Тихонов В.И. ,М: Радио и
связь, 1991 - 608 с.:ил.
3. Теория автоматов. Карпов
Ю.Г.
. Дискретная математика для
программистов. Новиков Ф.А. - СПб: Питер, 2000 - 304с.: ил.
5. Виды логик. Электронная
энциклопедия Википедия. http://ru.wikipedia.org/wiki/Delphi
6. ТТЛ - логика. Мега
энциклопедия Кирилла и Мефодия. http://www.megabook.ru/Article.asp?AID=606810
Приложение
А
Обозначение
|
Наименование
микросхемы
|
Кол-во
|
Примечание
|
DD1
|
133ЛН3
|
2
|
|
DD13
|
|
|
|
DD2
|
К555ЛИ4
|
5
|
|
DD3
|
|
|
|
DD6
|
|
|
|
DD10
|
|
|
|
DD11
|
|
|
|
DD5
|
К155ЛИ1
|
2
|
|
DD14
|
|
|
|
DD4
|
К555ЛИ6
|
1
|
|
DD7
|
КР531ЛЕ7
|
1
|
|
DD12
|
К555ЛЕ4
|
1
|
|
|
|
|
|
|