Исследование и логическое проектирование конечного автомата

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

Рубрика Математика
Вид курсовая работа
Язык русский
Дата добавления 18.11.2015
Размер файла 681,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Уфимский государственный авиационный технический университет филиал в г. Ишимбае.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине

Математические основы дискретно-логических систем

Исследование и логическое проектирование конечного автомата

Содержание

Введение

1. Построение таблицы поведения автомата

2. Построение графа

3. Кодирование данных

4. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции ш

5. Определение булевой функции для реализации функции ц

6. Составление логической схемы автомата

Заключение

Введение

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

Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров

где:

Q -- конечное множество состояний автомата;

q0 -- начальное состояние автомата ();

F -- множество заключительных (или допускающих) состояний, таких что ;

У -- допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

д -- заданное отображение множества во множество подмножеств Q:

(иногда д называют функцией переходов автомата).

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

Конечные автоматы подразделяются на детерминированные и недетерминированные:

- детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

- недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

1) существуют переходы, помеченные пустой цепочкой е;

2) из одного состояния выходит несколько переходов, помеченных одним и тем же символом.

Одна из областей эффективного использования конечного автомата (КА) - разработка игровых программ. Другая предметная область - системы управления и/или функционирования в реальном времени. В этих областях в полной мере присутствуют элементы, которые сложно реализовать при обычных подходах. Это - параллельный характер работы составных частей системы, их синхронизация в реальном времени. В таких областях обычно применяются специализированные системы проектирования. В их основу положена, примененная и в КА-технологии, концепция микроядра, которое реализует параллельные механизмы среды функционирования.

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

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

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

Преимущества, обеспечиваемые применением конечных автоматов, заметнее всего проявляются в случае приложений для мобильных устройств, требующих экономного расходования экранного пространства, памяти, вычислительной мощности и других ресурсов.

Постановка задачи

Для выполнения данной курсовой работы необходимо выполнить несколько следующих этапов:

1. Составить таблицу поведения автомата.

Эта таблица составляется с помощью начальных данных, заданных в форме фрагментов четырех таблиц с соответствующим вариантом.

2. Нарисовать граф.

Граф рисуется по результатам, полученным из таблицы поведения. Но, чтобы не перегружать рисунок графа многочисленными переходами, можно разбить его на фрагменты. Количество фрагментов должно совпадать с количеством состояний. Затем, нужно построить таблицу соединений, с помощью которых сигнал переходит из одного состояния в другое.

3. Произвести кодирование данных.

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

4. Найти систему булевых функций для возбуждения JK-триггеров, реализующих функции ш.

Составляем таблицу по данным таблицы поведения в кодах и схемы работы JK-триггера. По полученным в ней значениям записываем функции UTi, которые необходимо будет максимально упростить (склеить). Так же следует найти одинаковые элементы (конъюнкты или дизъюнкты) в различных формулах UTi.

5. Определить булеву функцию для реализации функции ц.

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

6. Составить логическую схему автомата, используя комбинационные автоматы и JK-триггеры.

Необходимо составить две схемы: первая формирует функцию ш на JK-триггерах, вторая - формирует функцию ц. В них должны использоваться следующие элементы: конъюнкты, дизъюнкты и триггеры. Количество конъюнктов для первой схемы не должно превышать 20 штук.

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

1. Построение таблицы поведения автомата

автомат дискретный преобразователь триггер

Такая таблица состоит из строк - текущих состояний q1, q2, …, q12 и столбцов - символов входного алфавита x1, x2, x3, x4. В ячейки данной таблице записывают по два значения через дробь: первое значение - это значение очередных состояний автомата , в которые он переходит для каждой пары ; второе значение - это значения символов выходного алфавита , которые генерирует автомат для каждой пары .

Данные в таблицу поведения мы заносим из индивидуального задания по таблицам 1, 2, 3 и 4 в соответствии с нужным вариантом.

Символ (*/*) в ячейках обозначает, что переход из одного состояния в другое и значение символа на выходе из состояния неопределены.

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

Таблица 1 Таблица поведения

Xi q[ф]

x1

x2

x3

x4

q1

*/1

*/1

q5/0

q6/0

q2

*/1

q2/*

q6/0

q7/0

q3

*/1

q1/0

q7/0

q8/0

q4

q1/*

q2/0

q8/0

q9/*

q5

q1/0

q3/0

q9/*

q10/*

q6

q2/0

q4/0

q10/*

q11/*

q7

q3/0

q5/*

q11/*

q12/1

q8

q4/0

q6/*

q12/1

*/1

q9

q5/*

q7/*

*/1

*/1

q10

q6/*

q8/1

*/1

*/1

q11

q7/*

*/1

*/1

*/*

q12

q8/*

*/1

*/*

q5/0

2. Построение графа

Выбираем центральное состояние и вокруг него располагаем все остальные. Затем по таблице поведения автомата расставляем переходы (стрелки) из центрального состояния в другие, подписывая их.

Если вместо очередного состояния автомата стоит знак * (например, */1), то данное значение можно использовать для всех недостающих состояний.

По построенным графам составляем таблицу соединений состояний автомата, где строки - это текущее состояние , а столбцы - очередное состояние .

Размещено на http://www.allbest.ru/

Рисунок 1 Фрагмент графа перехода с вершиной-истоком q2

Размещено на http://www.allbest.ru/

Рисунок 2 Фрагмент графа перехода с вершиной-истоком q3

Размещено на http://www.allbest.ru/

Рисунок 3 Фрагмент графа перехода с вершиной-истоком q4

Размещено на http://www.allbest.ru/

Рисунок 4 Фрагмент графа перехода с вершиной-истоком q5

Размещено на http://www.allbest.ru/

Рисунок 5 Фрагмент графа перехода с вершиной-истоком q6

Размещено на http://www.allbest.ru/

Рисунок 6 Фрагмент графа перехода с вершиной-истоком q7

Размещено на http://www.allbest.ru/

Рисунок 7 Фрагмент графа перехода с вершиной-истоком q8

Размещено на http://www.allbest.ru/

Рисунок 8 Фрагмент графа перехода с вершиной-истоком q9

Размещено на http://www.allbest.ru/

Рисунок 9 Фрагмент графа перехода с вершиной-истоком q10

Размещено на http://www.allbest.ru/

Рисунок 10 Фрагмент графа перехода с вершиной-истоком q11

Размещено на http://www.allbest.ru/

Рисунок 11 Фрагмент графа перехода с вершиной-истоком q12

`Размещено на http://www.allbest.ru/

Рисунок 12

Таблица 3 Таблица соединений

Q q[ф]

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q1

x3/0

x4/0

q2

x2/*

x3/0

x4/0

q3

x2/0

x3/0

x4/0

q4

x1/*

x2/0

x3/0

x4/*

q5

x1/0

x2/0

x3/*

x4/*

q6

x1/0

x2/*

x3/*

x4/*

q7

x1/0

x2/*

x3/*

x4/1

q8

x1/0

x6/*

x3/1

q9

x1/*

x2/*

q10

x1/*

x2/1

q11

x1/*

q12

x4/0

x1/*

3. Кодирование данных

Требуется произвести однозначное двоичное кодирование элементов множеств X, Y, Q. Первоначально для каждого множества требуется определить его мощность, т.е. число элементов. Затем, определить число бит необходимых для однозначного кодирования.

Так как у нас

X={x1, x2, x3, x4}, Y={0,1}, Q={ q1, q2, …, q12}, то для Х (т.е. (x1, x2)), для Y (т.е.(у)) и для Q (т.е. (q1, q2, q3, q4)).

В соответствии с полученными значениями мы запишем таблицу поведения в кодах. В ячейки данной таблицы вписаны закодированные состояния и значения выходных символов (например, 0110/1), причем символ */* остается неизменным.

Таблица 4

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

Таблица 5

x1

x2

x3

x4

00

01

10

11

Таблица 6. Таблица поведения автомата в кодах

x1

00

x2

01

x3

10

x4

11

q1

*/1

*/1

0100/0

0101/0

q2

*/1

0001/*

0101/0

0110/0

q3

*/1

0000/0

0110/0

0111/0

q4

0000/*

0001/0

0111/0

1000/*

q5

0000/0

0010/0

1000/*

1001/*

q6

0001/0

0011/0

1001/*

1010/*

q7

0010/0

0100/*

1010/*

1011/0

q8

0011/0

0101/*

1011/*

*/1

q9

0100/*

0110/*

*/1

*/1

q10

0101/*

0111/1

*/1

*/1

q11

0110/*

*/1

*/1

*/*

q12

0111/*

*/1

*/*

0100/0

4. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции ш

Составляем таблицу, где строки - код состояния, столбцы - код символа входного алфавита. Позициями таблицы являются сигналы на информационном входе соответствующего канала UJi. При помощи таблицы поведения в кодах и схемы работы JK-триггера заполняем данную таблицу.

Таблица 7 Таблица возбуждения памяти автомата для JK-триггера

00

01

10

11

0000

****

****

****

****

0100

****

0101

****

0001

****

****

000*

***0

010*

***0

011*

***1

0010

****

****

00*0

**1*

01*0

**0*

01*1

**0*

0011

00**

**11

00**

**10

01**

**00

10**

**11

0100

0*00

*1**

0*10

*1**

1*00

*1**

1*01

*1**

0101

0*0*

*1*0

0*1*

*1*0

1*0*

*1*0

1*1*

*1*1

0110

0**0

*10*

0**0

*01*

1**0

*10*

1**1

*10*

0111

0***

*100

0***

*011

1***

*100

****

****

1000

*100

1***

*110

1***

****

****

****

****

1001

*10*

1**0

*11*

1**0

****

****

****

****

1010

*1*0

1*0*

****

****

****

****

****

****

1011

*1**

1*00

****

****

****

****

****

1*11

Рисунок 13

5. Определение булевой функции для реализации функции ц

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

Данная таблица имеет одинаковое количество единиц и нулей. Здесь были выбраны нули. Сравниваем нуль с кодированными значениями. Записываем полученную формулу и упрощаем её.

Таблица 8 Таблица символов выходного алфавита

00

01

10

11

0000

1

1

0

0

0001

1

*

0

0

0010

1

0

0

0

0011

*

0

0

*

0100

0

0

*

*

0101

0

0

*

*

0110

0

*

*

0

0111

0

*

*

1

1000

*

*

1

1

1001

*

1

1

1

1010

*

1

1

*

1011

*

1

*

0

Рисунок 14

6. Составление логической схемы автомата

На основании полученных выражений функций возбуждения элементов памяти и функций выходов автомата можно перейти к построению логических схем. Первая схема формирует функцию ш на JK-триггерах. Вторая схема формирует функцию ц.

При построении схемы используем такие элементы: конъюнкт, дизъюнкт и триггеры. При совпадении нескольких конъюнктов или дизъюнктов, рисуется только один элемент и из него выходит сигнал в нескольких направлениях.

На схеме, формирующей функцию ш на JK-триггерах, введены дополнительные входы триггеров R, S и C. Сигнал, поданный на вход R, обеспечивает принудительный перевод триггеров в состояние «1», на вход S - в состояние «0». Сигнал, поданный на вход С, является синхронизирующим для всего автомата.

Рисунок 15

Рисунок 16

Заключение

Для выполнения данной курсовой работы необходимо было выполнить 6 следующих пунктов:

1. Построение таблицы поведения автомата.

2. Построение графа.

3. Кодирование данных.

4. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции ш.

5. Определение булевой функции для реализации функции ц.

6. Составление логической схемы автомата.

Отметим каждый из них и покажем, что они полностью выполнены:

1. Построение таблицы поведения автомата.

Первоначально исходные данные представлены в виде фрагментов четырех таблиц. Объединяя эти данные и транспонируя полученную таблицу, получим таблицу поведения автомата (Таблица 1. Таблица поведения).

После таблицы поведения и по ее данным построена таблица свободных переходов (Таблица 2. Таблица свободных переходов), которые при переходе из одного состояния могут применяться для любого другого состояния.

Данные таблицы полностью заполнены и проверенны, поэтому данный этап можно считать выполненным.

2. Построение графа.

По данным, взятым из первых двух таблиц (Таблице поведения и Таблице свободных переходов), должен быть построен граф. Но, чтобы не загромождать многочисленными переходами рисунок одного графа, было решено разбить его на фрагменты. Так как у нас дано 12 состояний, т.е. q1,q2,q3,…, q12, то и фрагментов графа перехода получилось тоже 12, каждый со своей вершиной-истоком. Затем по данному графу была составлена таблица соединений.

3. Кодирование данных.

Для того чтобы продолжить исследование автомата, необходимо было провести кодирование данных, так состояния q1,q2,q3,…, q12 получили следующие коды: 0000, 0001, …, 1011 (Таблица 4), а символы входного алфавита x1, x2, x3, x4 - 00, 01, 10, 11 (Таблица 5). Учитывая эти коды, была записана таблица поведения в кодах (Таблица 6. Таблица поведения автомата в кодах). На этом этап кодирования завершен.

4. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции ш.

По данным таблицы поведения в кодах и схемы работы JK-триггера заполняем новую таблицу (Таблица 7. Таблица возбуждения памяти автомата для JK-триггера).

Формулы были предельно упрощены до минимального количества конъюнктов (13 штук). Данный пункт исследования автомата можно считать выполненным.

5. Определение булевой функции для реализации функции ц.

В ячейки таблицы возбуждения памяти автомата были записаны символы выходного алфавита из таблицы поведения автомата. Так получили новую таблицу (Таблица 8. Таблица символов выходного алфавита). Затем, как и в пункте 6 записали функцию y, состоящую из 14 дизъюнктов. Но после ее упрощения (склеивания) получили дизъюнктов в количестве 7 штук.

6. Составление логической схемы автомата.

Проведя все исследования и вычисления, приступили к построению логической схемы автомата. Их у нас две. Первая схема формирует функцию ш на JK-триггерах. Вторая - формирует функцию ц.

В первую схему вошли, определенные выше, 13 конъюнктов, 4 дизъюнкта и 4 JK-триггера. Так же дополнительно были введены входы триггеров R, S и C. Во вторую схему вошли 7 дизъюнктов и 1 конъюнкт.

На этом построение логической схемы автомата завершено.

Закончив перечисленные выше пункты, исследование и логическое проектирование конечного частично определенного автомата можно считать выполненным. Осталось лишь провести проверку результатов путем частичной трассировкой автомата.

Размещено на Allbest.ru

...

Подобные документы

  • Построение таблицы поведения автомата и соответствующего графа. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции "пси". Определение булевой функции для реализации функции "фи". Составление логической схемы автомата.

    курсовая работа [96,7 K], добавлен 27.04.2011

  • Построение графа и таблицы поведения автомата. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции y. Определение булевой функции для реализации функции j. Составление логической схемы автомата, кодирование данных.

    курсовая работа [200,4 K], добавлен 27.04.2011

  • Составление таблицы истинности. Получение уравнений функций алгебры логики для заданных выходов. Реализация схемы логического автомата на электромагнитных реле РП-23, на диодной матрице. Реализация структурной схемы логического автомата, на микросхемах.

    курсовая работа [862,4 K], добавлен 12.12.2012

  • Описание абстрактных, структурных и частичных конечных автоматов. Работа синхронных конечных автоматов, содержащих различные типы триггеров, определение сигналов их возбуждения. Пример канонического метода структурного синтеза. Схема дверного замка.

    учебное пособие [19,6 M], добавлен 07.06.2009

  • Образование множеством функций системы ортонормированных функций, условия ортогональности для заданной системы. Разложение в тригонометрический и комплексный ряды Фурье пилообразного сигнала. Генерирование программного произвольного дискретного сигнала.

    контрольная работа [378,6 K], добавлен 14.01.2016

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

    контрольная работа [225,5 K], добавлен 18.02.2015

  • Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.

    учебное пособие [1,3 M], добавлен 20.08.2014

  • Огляд проблеми дискретного логарифмування в групі точок еліптичної кривої. Сутність та сфера використання методу Поліга-Хелмана. Особливості використання методу ділення точок на два. Можливі підходи і приклади розв’язання задач дискретного логарифмування.

    реферат [112,8 K], добавлен 09.02.2011

  • Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.

    курсовая работа [278,1 K], добавлен 21.02.2009

  • Криптографічні перетворення, що виконуються в групі точок ЕК. Проблема дискретного логарифму. Декілька методів, що використовуються для аналізу стійкості і проведення криптоаналізу. Опис та розв’язання логарифму методом Флойда, методом Полларда.

    контрольная работа [98,1 K], добавлен 08.02.2011

  • Основная идея метода конечных элементов. Пространство конечных элементов. Простейший пример пространства. Однородные граничные условия и функции. Построение базисов в пространствах. Свойства базисных функций. Коэффициенты системы Ритца–Галеркина.

    лекция [227,9 K], добавлен 30.10.2013

  • Поиск нулей функции - исследование и построение различных функций зависимостей. Исследование непрерывных процессов. Метод простой итерации. Итерационный процесс Ньютона, аналитическое задание системы уравнений и локализация области нахождения корня.

    реферат [54,1 K], добавлен 08.08.2009

  • Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.

    курсовая работа [701,9 K], добавлен 27.04.2011

  • Основные определения конечного автомата Мили, его специальные классы. Группы и полугруппы, определенные обратимым автоматом без ветвлений. Преобразования, определенные обратимым медленным автоматом конечного типа. Функции перехода без предельного цикла.

    дипломная работа [781,6 K], добавлен 10.06.2011

  • Побудова графічної схеми алгоритму та розмітка станів автомата, графа та кодування, структурної таблиці. Синтез комбінаційних схем для функцій збудження тригерів і вихідних сигналів. Представлення функції в канонічних формах алгебр Буля, їх мінімізація.

    курсовая работа [902,8 K], добавлен 27.08.2014

  • Використання методу Полларда для вирішення проблеми дискретного логарифмування, його складність і час обчислення рішення ECDLP. Аномальні криві й криві над розширеннями малого поля. MOV-атака та суперсингулярні криві над полем F. Метод спуску Вейля.

    реферат [269,5 K], добавлен 21.02.2011

  • Свойства дискретного преобразования Фурье, представленные в виде математических формул, которые наиболее адекватно соответствуют цифровой технике обработки информации. Алгоритм быстрого преобразования Фурье (БПФ), его значение для программирования.

    учебное пособие [223,6 K], добавлен 11.02.2014

  • Рассмотрение особенностей метода построения полного проверяющего теста для недетерминированных автоматов относительно неразделимости для модели "черного ящика" и разработка предложений по его модификации. Исследование условий усечения дерева преемников.

    курсовая работа [1,3 M], добавлен 20.08.2010

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

    презентация [128,9 K], добавлен 12.01.2014

  • Исследование методами математического анализа поведения функций при заданных значениях аргумента. Этапы решения уравнения функции и определения значения аргумента и параметра. Построение графиков. Сочетание тригонометрических, гиперболических функций.

    контрольная работа [272,3 K], добавлен 20.08.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.