Исследование и логическое проектирование конечного частично-определенного автомата
Рассмотрение исходных таблиц поведения автомата. Характеристика графа автомата. Особенности кодирования данных. Построение системы булевых функций для JK-триггеров. Основные принципы построения функции выхода. Реализация логической схемы автомата в EWB.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 26.05.2015 |
| Размер файла | 469,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования РФ
Федеральное бюджетное государственное образовательное учреждение
высшего профессионального образования
Уфимский государственный авиационный технический университет
филиал в г. Ишимбае
кафедра физики и математики
Курсовая работа
«Исследование и логическое проектирование конечного частично-определенного автомата»
Вариант 18
Выполнил: ст.гр. АТПз-111
Круглов С.Н.
Проверил: к.ф.-м.н., доцент
Мугафаров М.Ф.
Ишимбай 2013
Содержание
Введение. Постановка задачи синтеза
1. Исходные таблицы поведения автомата. Граф автомата
2. Кодирование данных
3. Построение системы булевых функций для JK-триггеров
4. Булевая функция для реализации функции ц
5. Логическая схема автомата
Заключение
автомат граф булевой триггер
Введение. Постановка задачи синтеза
В наиболее общем случае автоматами называют технически или программно реализованные модули, предназначенные для переработки поступающей информации. Конечный автомат - это модуль, имеющий конечное число возможных состояний и функционирующий в дискретном времени. В данной работе конечный автомат изучается как абстрактное алгоритмическое устройство, предназначенное для обработки слов фиксированного входного алфавита. Считаем, что обработку произвольного слова во входном алфавите автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние; состояние, в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины l автомат работает l тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.
Целью данной работы является исследование и логическое проектирование конечного частично определенного автомата.
Автомат будем описывать с помощью таблицы соединений, а для наглядности использовать графы.
При табличном описании можно задавать две таблицы, первая из которых раскрывает функции перехода , а вторая - функцию выходов .
Число строк таблиц равно числу состояний автомата, а число столбцов таблиц равно числу символов входного алфавита. В клетки первой таблицы записываются значения очередных состояний для каждой пары . В клетки второй таблицы записываются выходные символы для каждой пары .
Анализ поведения автомата проводится с помощью графа. Его вершинами являются элементы множества Q, т.е. состояния автомата.
Основными этапами проектирования конечного автомата являются:
кодирование алфавитов;
выбор комбинационного автомата;
выбор элементов двоичной задержки;
формирование функции выхода и переходов;
построение логической схемы структурного автомата.
В качестве элементов двоичной задержки в работе используются JK-триггеры. Триггер представляет собой автомат Мура, обладающий двумя устойчивыми состояниями «0» и «1». Система функции переходов триггера является полной, т.е. для любого состояния существует входной сигнал, переводящий триггер в другое состояние.
1. Исходные таблицы поведения автомата. Граф автомата
Согласно номеру варианта из таблиц 16-19 приложения 1 пособия [1] выберем исходные данные, которые отобразим в виде таблицы поведения автомата (*/* - не рассматриваем).
|
Xi q(ф) |
x1 |
x2 |
x3 |
x4 |
|
|
q1 |
q10/* |
Q12/1 |
*/1 |
*/1 |
|
|
q2 |
q11/* |
*/1 |
*/1 |
*/* |
|
|
q3 |
q12/1 |
*/1 |
*/* |
q5/0 |
|
|
q4 |
*/1 |
*/1 |
Q5/0 |
Q6/0 |
|
|
q5 |
*/1 |
Q2/* |
Q6/0 |
Q7/0 |
|
|
q6 |
*/1 |
Q5/0 |
Q7/0 |
Q8/0 |
|
|
q7 |
Q1/* |
Q6/0 |
Q8/0 |
Q9/* |
|
|
q8 |
Q5/0 |
Q7/0 |
Q9/* |
Q10/* |
|
|
q9 |
Q6/0 |
Q8/0 |
Q10/* |
Q11/* |
|
|
q10 |
Q7/0 |
Q9/* |
Q11/* |
Q12/1 |
|
|
q11 |
Q8/0 |
Q10/* |
Q12/1 |
*/1 |
|
|
q12 |
Q9/* |
Q11/* |
*/1 |
*/1 |
Ячейки таблицы соединений автомата образуют квадратную матрицу, строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент ms, стоящий на пересечении m-ой строки и s-го столбца, соответствует входному сигналу, вызывающему переход из состояния qm в состояние qs, и выходному сигналу, выдаваемому на этом переходе. Если данный переход происходит под действием нескольких сигналов, элемент ms представляет собой множество пар (вход/выход) для этого перехода, соединенных знаком дизъюнкции.
|
q(ф+1) q(ф) |
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
q7 |
q8 |
q9 |
q10 |
q11 |
q12 |
|
|
q1 |
X1/* |
X2/1 |
|||||||||||
|
q2 |
X1/* |
||||||||||||
|
q3 |
X4/0 |
X1/1 |
|||||||||||
|
q4 |
X3/0 |
X4/0 |
|||||||||||
|
q5 |
X2/* |
X3/0 |
X4/0 |
||||||||||
|
q6 |
X2/0 |
X3/0 |
X4/0 |
||||||||||
|
q7 |
X1/* |
X2/0 |
X3/0 |
X4/* |
|||||||||
|
q8 |
X1/0 |
X2/0 |
X3/* |
X4/* |
|||||||||
|
q9 |
X1/0 |
X2/0 |
X3/* |
X4/* |
|||||||||
|
q10 |
X1/0 |
X2/* |
X3/* |
X4/1 |
|||||||||
|
q11 |
X1/0 |
X2/* |
X3/1 |
||||||||||
|
q12 |
X1/* |
X2/* |
2. Кодирование данных
|
x1 |
x2 |
x3 |
x4 |
|
|
00 |
01 |
10 |
11 |
|
q1 |
0000 |
|
|
q2 |
0001 |
|
|
q3 |
0010 |
|
|
q4 |
0011 |
|
|
q5 |
0100 |
|
|
q6 |
0101 |
|
|
q7 |
0110 |
|
|
q8 |
0111 |
|
|
q9 |
1000 |
|
|
q10 |
1001 |
|
|
q11 |
1010 |
|
|
q12 |
1011 |
|
Вх.с. Код.с. |
00 |
01 |
10 |
11 |
|
|
0000 |
1001/* |
1011/0 |
*/1 |
*/1 |
|
|
0001 |
1010/* |
*/1 |
*/1 |
*/* |
|
|
0010 |
1011/1 |
*/1 |
*/* |
0100/0 |
|
|
0011 |
*/1 |
*/1 |
0100/0 |
0101/0 |
|
|
0100 |
*/1 |
0001/* |
0101/0 |
0110/0 |
|
|
0101 |
*/1 |
0100/0 |
0110*0 |
0111/0 |
|
|
0110 |
0000/* |
0101/0 |
0111/0 |
1000/* |
|
|
0111 |
0100/0 |
0110/0 |
1000/* |
1001/* |
|
|
1000 |
0101/0 |
0111/0 |
1001/* |
1010/* |
|
|
1001 |
0110/0 |
1000/* |
1010/* |
1011/1 |
|
|
1010 |
0111/0 |
1001/* |
1011/1 |
*/1 |
|
|
1011 |
1000/* |
1010/* |
*/1 |
*/1 |
3. Система булевых функций для возбуждения JK-триггеров, реализующих функцию ш
Таблица сигналов для JK-триггеров
|
00 |
01 |
10 |
11 |
Адресация для карт Карно |
||
|
0000 |
1001 **** |
1011 **** |
**** **** |
**** **** |
1 |
|
|
0001 |
101* ***1 |
**** **** |
**** **** |
**** **** |
2 |
|
|
0010 |
10*1 **0* |
**** **** |
**** **** |
01*0 **1* |
3 |
|
|
0011 |
**** **** |
**** **** |
01** **11 |
01** **10 |
4 |
|
|
0100 |
**** **** |
0*01 *1** |
0*01 *0** |
0*10 *0** |
5 |
|
|
0101 |
**** **** |
0*0* *0*1 |
0*1* *0*1 |
0*1* *0*0 |
6 |
|
|
0110 |
0**0 *11* |
0**1 *01* |
0**1 *00* |
1**0 *11* |
7 |
|
|
0111 |
0*** *011 |
0*** *001 |
1*** *111 |
1*** *110 |
8 |
|
|
1000 |
*101 1*** |
*111 1*** |
*001 0*** |
*010 0*** |
9 |
|
|
1001 |
*11* 1**1 |
*00* 0**1 |
*01* 0**1 |
*01* 0**0 |
10 |
|
|
1010 |
*1*1 0*0* |
*0*1 0*1* |
*0*1 0*0* |
**** **** |
11 |
|
|
1011 |
*0** 0*11 |
*0** 0*01 |
**** **** |
**** **** |
12 |
Uj1 = (q2^x1) (q2^q3^q4^x1^x2) (q2^q3^x1^x2)
Uj2 = (q1^q2^q4^x1^x2) (q1^q3^x1^x2) (q1^q2^q3^q4^x1) (q1^x1)
Uj3 = (q4^x2) (q2^q4^x1^x2) (x1^x2)
Uj4 =(q2^x1) (x1^x2) (x1^x2)
Uk1 =(q1^q3^x1^x2) (q1^q2^q3^q4^x1)
Uk2 = (q1^q2^q3^q4^x1) (q2^q4^x1^x2) (q3^q4^x1) (q3^x1^x2)
Uk3=(q2^q4^x1) (q4^x2) (q2^q4^x2) (x1^x2)
Uk4 = (q4^x1) (q4^x2)
4. Булевая функция для реализации функции ц
|
Вх.с. Код.с. |
00 |
01 |
10 |
11 |
Адресация для карт Карно |
|
|
0000 |
* |
0 |
1 |
1 |
1 |
|
|
0001 |
* |
1 |
1 |
* |
2 |
|
|
0010 |
1 |
1 |
* |
0 |
3 |
|
|
0011 |
1 |
1 |
0 |
0 |
4 |
|
|
0100 |
1 |
* |
0 |
0 |
5 |
|
|
0101 |
1 |
0 |
0 |
0 |
6 |
|
|
0110 |
* |
0 |
0 |
* |
7 |
|
|
0111 |
0 |
0 |
* |
* |
8 |
|
|
1000 |
0 |
0 |
* |
* |
9 |
|
|
1001 |
0 |
* |
* |
1 |
10 |
|
|
1010 |
0 |
* |
1 |
1 |
11 |
|
|
1011 |
* |
* |
1 |
1 |
12 |
ц =(q1^q3^x1^x2) (q2^q3^q4^x1^x2) (q2^q3^x1^x2) (q2^q4^x1^x2) (q1^x1)
(q1^q2^q3^x1)
5. Логическая схема автомата
Размещено на Allbest.ru
...Подобные документы
Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем.
дипломная работа [1,8 M], добавлен 18.08.2013Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.
курсовая работа [997,7 K], добавлен 28.03.2011Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.
курсовая работа [903,9 K], добавлен 14.07.2012Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа.
курсовая работа [615,1 K], добавлен 19.06.2012Устройство управления и синхронизации в структуре микропроцессора. Порядок синтеза конечного автомата (КА) для устройства управления ЭВМ. Алгоритм функционирования КА, заданный с помощью графа, функции переходов. Состояние триггеров в микросхеме.
методичка [1019,0 K], добавлен 28.04.2009Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.
курсовая работа [964,2 K], добавлен 20.07.2015Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Общая схема D-триггера и цифрового автомата Мили. Построение входных и выходных преобразователей в соответствии с таблицами кодирования входных и выходных сигналов. Составление таблиц переходов и выхода состояния автомата Мили. Выбор серии микросхем.
курсовая работа [525,4 K], добавлен 04.11.2012Составление формальной грамматики, недетерминированный конечный автомат. Построение конечного автомата, программное моделирование работы конечного автомата. Граф детерминированного автомата, Синтаксическая диаграмма. Блок-схемы, примеры разбора строк.
курсовая работа [486,2 K], добавлен 19.11.2010Понятие, последовательность построения и схемная реализация цифрового автомата. Описание форм представления функций алгебры логики. Принципы минимизации функций выходов и переходов автомата, их перевода в базис. Сведенья о программе Electronics Workbench.
курсовая работа [2,0 M], добавлен 27.10.2010Разработка управляющего автомата процессора с жесткой логикой в САПР Quartus II. Построение схемы функциональной микропрограммы команды "Исключающее ИЛИ" в размеченном виде. Унитарное кодирование состояний автомата. Запись функций переходов и выходов.
курсовая работа [671,3 K], добавлен 04.11.2014Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Синтез цифрового автомата с комбинационной частью на логических элементах. Реализация спроектированного автомата в виде иерархического блока со схемой замещения на библиотечных компонентах в режиме SPICE–проектов. Разработка абстрактных символов.
курсовая работа [831,2 K], добавлен 23.09.2013Важный частный случай недетерминированного конечного автомата. Проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Составление формальной грамматики, блок-схемы и программы, моделирующей работу конечного автомата.
курсовая работа [210,8 K], добавлен 05.12.2013Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012Определение функций выходных сигналов и сигналов возбуждения. Построение функциональной схемы управляющего автомата. Способы выполнения операции умножения с фиксированной и с плавающей запятой. Получение функциональной ГСА. Кодирование состояния автомата.
курсовая работа [60,9 K], добавлен 15.02.2011Оптимізація схеми мікропрограмного автомата Мура за рахунок нестандартного подання кодів станів. Аналіз методів синтезу автомата та аналіз сучасного елементного базису. Використанні особливостей автомата для зменшення площини матричної схеми автомата.
презентация [357,0 K], добавлен 16.10.2013Разработка функциональной схемы управляющего микропрограммного автомата. Построение графов автомата для модели Мили и Мура. Кодирование состояний для модели Мура на D-триггерах. Алгоритм умножения чисел в дополнительном коде с простой коррекцией.
курсовая работа [764,0 K], добавлен 27.08.2012
