Теория автоматов
Решение задач, с использованием карт Карно, а также синтез-автомата Мили. Условия работы комбинационного устройства. Синтезирование функциональной логической схемы устройства в базисе ИЛИ-НЕ, применяя методы минимизации заданной логической функции.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 08.01.2021 |
| Размер файла | 290,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ОГЛАВЛЕНИЕ
Введение
Задание
Библиографический список
ВВЕДЕНИЕ
Теория автоматов как научная дисциплина возникла в пределах теории управляющих систем (теоретической кибернетики) в середине ХХ века, в период начавшегося бурного развития средств электронной вычислительной техники и соответствующих областей математического знания. Потребовалась разработка теоретической базы для решения проблем, возникавших при проектировании реальных цифровых ЭВМ, а также в процессе построения и исследования гипотетических систем, таких как нейронные сети. В качестве моделей последних рассматривались конечные автоматы.Развитие информационных технологий вывело сферу приложения теории автоматов далеко за рамки моделирования аппаратных средств цифровой электроники, расширив ее до фундаментальных основ современной теоретической информатики. Сегодня абстракции и модели, разработанные в теории автоматов, востребованы такими научными дисциплинами как теория формальных грамматик, математическая лингвистика, теория логических моделей, математическая логика и формальные аксиоматические системы, теория кодирования, теория вычислительной сложности и другими. Наиболее тесно теория автоматов связана с теорией алгоритмов и, в частности, с таким ее разделом как теория абстрактных машин. В настоящее время существует ряд изданий учебного и учебно-методического назначения, в названиях которых содержится словосочетание «теория автоматов». Нередко эти издания носят синтетический характер, объединяя под одной обложкой как элементы самой теории автоматов, так и фрагменты перечисленных выше научных областей, в которых аппарат данной теории находит мощное и вполне оправданное применение. Цель настоящего проекта-научится решать задачи различными методами, с использованием карт Карно а также синтез автомата Мили. В разделе 1 рассмотрены условия работы комбинационного устройства. В раздел 2 произведен синтез автомата Мили.
ЗАДАНИЕ 1
комбинационное устройство логический карно мили
Условия работы комбинационного устройства, имеющего четыре входа () и один выход , заданы таблицей истинности (табл. 1.1).
Требуется синтезировать функциональную логическую схему устройства в базисе ИЛИ-НЕ, применяя методы минимизации заданной логической функции с помощью алгебраических преобразований и с использованием карт Карно.
Таблица 1.1
Таблица истинности комбинационного устройства
|
№ варианта |
Х1 |
Х2 |
Х3 |
Х4 |
F0 |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
F8 |
F9 |
|
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
2 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
3 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
4 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
5 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|
6 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
7 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
8 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
|
9 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
10 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
11 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
12 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
|
13 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
|
14 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
15 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
Решение
Поскольку в таблице истинности количество наборов входных переменных, при которых значение функции равно 1, меньше, чем количество наборов, при которых значение функции равно 0, представим ФАЛ в СДНФ.
Правило составления записи структурной формулы в виде СДНФ заключается в том, что для каждой строки таблицы истинности, в которой значение функции равно «1», записывается минтерм - конъюнкция (логическое произведение) всех входных переменных, а затем производится логическое сложение минтермов. Если значение какой-либо входной переменной в строке таблицы истинности равно нулю, то такая переменная записывается в минтерме в инверсном виде.
Для заданной функции получим следующую СДНФ:
Минимизация ФАЛ заключается в нахождении минимальных нормальных форм ее записи (МДНФ или МКНФ), имеющих минимальное число вхождений входных переменных и минимальное число термов в функции.
Минимизируем ФАЛ с помощью алгебраических преобразований исходной формулы. Воспользуемся законом склеивания и скомбинируем следующие слагаемые: первое и третье, второе и третье, пятое и шестое. Таким образом, в результате выполненных алгебраических преобразований исходной ФАЛ получили искомую минимальную форму МДНФ:
.
Далее минимизируем ФАЛ методом карт Карно. Карта Карно заполняется следующим образом: в каждой клетке проставляется значение функции, которое она принимает на наборе значений переменных, являющихся ее координатами. При представлении функции в СДНФ в каждой клетке, координаты которой соответствуют минтерму, для которого функция принимает единичное значение, указывается значение «1», значение «0» при этом на картах обычно не отражается.
На рис. 1.1 представлена карта Карно для исходной ФАЛ.
Минимизация ФАЛ заключается в объединении соседних клеток (при этом клетки, лежащие на границах карты, также являются соседними по отношению друг к другу), содержащих единичные (для получения МДНФ) или нулевые (для получения МКНФ) значения, в замкнутые области. Каждая область должна представлять собой прямоугольник с числом клеток . Области могут пересекаться, и одни и те же клетки могут входить в разные области. Это позволяет исключить одну переменную при объединении двух клеток, или две переменные при объединении четырех соседних клеток, или три переменные при объединении восьми клеток карты Карно. При охвате клеток замкнутыми областями следует стремиться к минимальному числу областей, каждая из которых содержала бы возможно большее число клеток.
Рисунок 1.1 - Карта Карно
Для исходной функции мы получили четыре области (см. рис. 1.1). Таким образом, МДНФ имеет вид:
,
что совпадает с результатом, полученным при помощи алгебраических преобразований.
Для записи полученных в результате минимизации ФАЛ в базисе ИЛИ-НЕ используют закон де Моргана (закон дуальности), согласно которому инверсия дизъюнкций переменных равна конъюнкции инверсий этих переменных и, наоборот, инверсия конъюнкции переменных равна дизъюнкции инверсий этих переменных:
;
Для представления функции в базисе ИЛИ-НЕ необходимо произвести двойную инверсию над каждой конъюнкцией, а также двойную инверсию над всей функцией и, используя закон де Моргана преобразовать инверсию конъюнкций в дизъюнкцию инверсий. В результате получим:
Для технической реализации ФАЛ используется количество логических элементов типа ИЛИ-НЕ, равное числу инверсий в ее алгебраическом выражении. В нашей задаче для реализации ФАЛ требуется 12 логических элементов ИЛИ-НЕ. Так как любой из этих логических элементов должен иметь по определению число входов не менее двух, то при наличии инверсии только одной переменной, эта переменная подается на оба входа логического элемента ИЛИ-НЕ.
На рис. 1.2 представлена техническая реализация функции на логических элементах ИЛИ-НЕ.
Рисунок 1.2 - Техническая реализация функции на логических элементах ИЛИ-НЕ
ЗАДАНИЕ 2
Провести синтез автомата Мили, функционирование которого описывается заданными таблицами переходов и выходов (см. табл. 2.1 и 2.2). Изобразить граф синтезируемого автомата. Задавая произвольную двоичную последовательность (входное слово), определить соответствующую двоичную выходную последовательность (выходное слово) автомата. Построить структурную схему синтезированного автомата в базисе И, ИЛИ, НЕ.
Таблица 2.1
Таблица переходов
|
Входной сигнал |
Состояние |
||||
|
0 |
|||||
|
1 |
Таблица 2.2
Таблица выходов
|
Входной сигнал |
Состояние |
||||
|
0 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
1 |
1 |
Три последних цифры шифра - 427. В двоичной системе счисления 427 представляется как 110101011. Оставив правые 8 цифр, получаем 10101011. Эти значения были занесены в таблицу выходов (табл. 2.2) слева направо и сверху вниз.
Решение
Представим функционирование автомата в виде графа (см. рис. 2.1).
Рисунок 2.1 - Граф
Задавая произвольную двоичную последовательность (входное слово) 1010, определим соответствующую двоичную выходную последовательность (выходное слово) автомата.
В начальный момент времени автомат находится в состоянии . Входной сигнал переводит его в состояние (см. рис. 2.1), при этом . Сигнал переведет автомат из состояния в состояние , при этом . Сигнал переведет автомат из состояния в состояние , при этом . Сигнал переведет автомат из состояния в состояние , при этом .
Таким образом, задавая входное слово 1010, мы получили выходное слово 1111.
Заданный по условию задачи автомат имеет четыре состояния. Поскольку число различных состояний триггеров равно , то для реализации данного автомата достаточно двух триггеров, т.е. .
Кодирование состояний автомата произведем в соответствии с табл. 2.3.
Таблица 2.3
Кодирование состояний автомата
|
Состояние автомата |
Состояние триггеров |
||
|
А0 |
0 |
0 |
|
|
А1 |
0 |
1 |
|
|
А2 |
1 |
0 |
|
|
А3 |
1 |
1 |
Далее заполним таблицу функционирования автомата (табл. 2.4), заданного графом, представленным на рис. 2.1.
Рассмотрим подробнее заполнение таблицы функционирования автомата Мили. В первых трех ее столбцах записываются все возможные сочетания кодов входного сигнала и состояния автомата. Для заданного входного сигнала и состояния автомата по графу находится значение выходного сигнала, которое записывается в последнем столбце таблицы, и следующее состояние автомата, в которое он переходит. Код этого состояния заносится в четвертый и пятый столбцы таблицы.
Таблица 2.4
Таблица функционирования автомата Мили
|
Входной сигнал |
Предыдущее состояние |
Сигнал состояния |
Сигналы управления триггерами |
Выходной сигнал |
||||||
|
0 |
0 |
0 |
0 |
1 |
0 |
* |
1 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
* |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
1 |
* |
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
1 |
* |
0 |
* |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
* |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
* |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
Столбцы с 6 по 9 отведены для записи сигналов управления триггерами. Управление триггерами осуществляется подачей сигналов на входы очистки (вход ) и установки (вход ). Эти сигналы для каждого триггера определяются сравнением их состояний в момент времени - и в последующий момент времени - . Например, во второй строке табл.2.4 , . Это означает, что второй триггер переводится из состояния «0» в состояние «1».Для этого должен быть подан сигнал «1» на вход и «0» на вход . В шестой строке табл.2.4 , а , следовательно, для перевода этого триггера из состояния «1» в состояние «0» необходимо подать сигнал «0» на вход и «1» на вход .
В тех случаях, когда предыдущее и последующее состояния триггера совпадают, (триггер хранит предыдущее состояние), то на оба входа (очистки и установки) можно подать сигнал «0» (, ), или на определенный вход триггера может подаваться сигнал подтверждения состояния триггера , (установка «1») или , (очистка или установка «0»). В подобных случаях, когда логический уровень сигнала управления безразличен («0» или «1»), в соответствующие клетки табл.2.4 заносится символ *.
Для построения комбинационного устройства, формирующего сигналы управления триггерами (), найдем их минимальные формы, используя метод минимизирующих карт (рис. 2.2).
Рисунок 2.2 - Минимизирующие карты для
Для построения комбинационного устройства, формирующего выходной сигнал , найдем его минимальную форму, используя метод минимизирующих карт (рис.2.3).
Рисунок 2.3 - Минимизирующая карта для
Рассматривая и как не полностью определенные логические функции аргументов и , запишем МКНФ этих функций:
;
; .
Представим функцию в виде МДНФ:
.
Используя полученные логические выражения и выбрав в качестве базиса логические элементы И, ИЛИ, НЕ, вычерчиваем структурную схему синтезируемого автомата, представленную на рис. 2.4.
Рисунок 2.4 - Структурная схема автомата
Для обеспечения правильной работы схемы автомата необходимо предусмотреть синхронизацию его функционирования во времени. Для этого в схеме (рис. 2.4) предусмотрен сигнал синхронизации , который в моменты времени разрешает подачу управляющих сигналов с выхода комбинационного устройства на входы триггеров, выполненных по двухступенчатой схеме. Запись информации в триггеры первой ступени, образованной триггерами и , происходит по высокому уровню синхросигнала , а в триггеры второй ступени ( и ) - по низкому уровню синхросигнала. На выходе автомата информация будет изменяться по отрицательному фронту синхросигнала . Это соответствует алгоритму работы синхронного двухступенчатого (MS) RS-триггера.
ЗАКЛЮЧЕНИЕ
Проектирование релейной защиты и автоматики для данной подстанции было произведено согласно действующим нормативным техническим документам и неоднократно проверенным методикам расчета. На этом основании можно утверждать, что релейная защита и автоматика подстанции будет верно функционировать в течение запланированного срока службы при выполнении требований по монтажу и эксплуатации цепей и оборудования подстанции.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Схемы принципиальные электрические распределительных устройств подстанций 35-750 кВ. Типовые решения. - http://www.fskees/about/standards_organization.html.
2. Правила устройства электроустановок. - СПб.: Изд-во ДЕАН, 2011. - 928 с.
3. Нормы технологического проектирования подстанций переменного тока с высшим напряжением 35-750 кВ. - http://www.fsk-ees.ru/upload/docs/56947007-29.240.10.028-2009.pdf
4. Положение о технической политике ОАО «ФСК ЕЭС». - http://www.fsk-ees.ru/upload/docs/ETP_FSK_EES_2014_02_06.pdf
5. Каталог выпускаемой продукции ООО «Нефтекамский завод». - http://mir-blagovestie.ru/news/2012-04-02/novost-1
6. Каталог выпускаемой продукции ООО «Электрозащита» http://www.elz.ru/pkx.htm
7. Разрядная таблица стационарных аккумуляторных батарей Varta vb. - http://atonn.ru/data/Akkun_Varta/varta_gel_2v.pdf
Размещено на Allbest.ru
...Подобные документы
Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Разработка функциональных схем основных узлов сумматора-умножителя. Минимизация функции алгоритмом Рота. Поиск простых импликант. Минимизация картами Карно-Вейча. Эффективность минимизации. Логический синтез комбинационного устройства с шестью входами.
контрольная работа [36,3 K], добавлен 31.03.2013- Определение аппаратного обеспечения компьютера. Синтез логических схем на элементах 2И-НЕ и 2-ИЛИ-НЕ
Определение состава аппаратной части компьютера Samsung NP355V4C-S01RU с помощью программного обеспечения и стандартных средств Windows. Построение логической структуры. Синтез комбинационного устройства в базисах логических элементов И-НЕ, ИЛИ-НЕ.
курсовая работа [648,0 K], добавлен 10.12.2013 Разработка функциональной схемы управляющего микропрограммного автомата. Построение графов автомата для модели Мили и Мура. Кодирование состояний для модели Мура на D-триггерах. Алгоритм умножения чисел в дополнительном коде с простой коррекцией.
курсовая работа [764,0 K], добавлен 27.08.2012Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012Мнемоническая и кодированная форма структурной таблицы. Функции возбуждения триггеров, параметры комбинационных блоков. Синтез комбинационной схемы центрального аппарата методом карт Карно и аналитическим: сравнительное описание и оценка эффективности.
курсовая работа [1,6 M], добавлен 10.02.2014Построение карт Карно. Переход от булевых выражений к функциональным схемам. Минимизация заданной функции. Схемная реализация факторизированного покрытия. Перевод схемы в универсальный базис. Соединение транзисторов с нагрузкой в цепи коллектора.
курсовая работа [468,7 K], добавлен 01.12.2014Проект цифрового устройства для передачи сообщения через канал связи. Разработка задающего генератора, делителя частоты, преобразователя кода, согласующего устройства с каналом связи, схемы синхронизации и сброса, блока питания; оптимизация автомата.
курсовая работа [3,4 M], добавлен 05.02.2013Устройство управления и синхронизации в структуре микропроцессора. Порядок синтеза конечного автомата (КА) для устройства управления ЭВМ. Алгоритм функционирования КА, заданный с помощью графа, функции переходов. Состояние триггеров в микросхеме.
методичка [1019,0 K], добавлен 28.04.2009Понятие автомата как дискретного преобразователя информации, особенности его состояний. Синтез конечных автоматов, их задания и структурных анализ. Построение синтеза функций возбуждения элементарных автоматов. Комбинационный синтез конечных автоматов.
курсовая работа [336,4 K], добавлен 01.06.2014Общая структура и принцип функционирования синхронного управляющего автомата. Анализ граф схемы алгоритма управляющего автомата и детализация блока памяти. Структурный синтез логического преобразователя и разработка электрической функциональной схемы.
курсовая работа [222,6 K], добавлен 19.02.2013Общая схема D-триггера и цифрового автомата Мили. Построение входных и выходных преобразователей в соответствии с таблицами кодирования входных и выходных сигналов. Составление таблиц переходов и выхода состояния автомата Мили. Выбор серии микросхем.
курсовая работа [525,4 K], добавлен 04.11.2012Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Актуальность задачи. Разработка функциональной схемы устройства. Радиолокационная установка (РЛУ). Микропроцессорная часть. Обоснование алгоритма работы устройства. Разработка управляющей программы устройства. Схема алгоритма. Пояснения к программе.
курсовая работа [193,9 K], добавлен 18.10.2007Строение схемы микропроцессора: все устройства, необходимые для приема из памяти, хранения, и выполнение команд, заданных согласно варианту режима адресации. Описания языка Ассемблера и его функции. Основные функции макропроцессора, варианты построения.
курс лекций [44,1 K], добавлен 06.03.2009Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Реализация работы автомата подачи звонков в учебном заведении с использованием персонального компьютера. Создание файла прошивки для устройства. Сборка собственной схемы. Симулирование полученного устройства. Алгоритмы работы программы, ее листинг.
курсовая работа [1,2 M], добавлен 28.04.2014Синтез и детерминизация, алгоритм минимизации автоматов–распознавателей. Машина Тьюринга как универсальный тип абстрактного преобразователя. Моделирование систем и событий с помощью сетей Петри. Методы синтеза структурных автоматов на базе триггеров.
учебное пособие [2,3 M], добавлен 17.06.2014Определение функций выходных сигналов и сигналов возбуждения. Построение функциональной схемы управляющего автомата. Способы выполнения операции умножения с фиксированной и с плавающей запятой. Получение функциональной ГСА. Кодирование состояния автомата.
курсовая работа [60,9 K], добавлен 15.02.2011Построим содержательные графы выполнения трёх команд языка Ассемблера. Команда умножения двоичных чисел без знака mul. Команда преобразования типов cwde. Логическая команда xor. Синтез канонического автомата. Синтез М-автомата. Управляющие сигналы.
реферат [35,7 K], добавлен 18.11.2004
