Синтез комбинацонных схем и конечных автоматов, сети Петри
СОДЕРЖАНИЕ Введение ………………………………………………………………6 1 Синтез комбинационных схем 1.1 Постановка задачи ……………………………………………… 7 1.2 Теоретические сведения …………………………………………7 1.3 Расчёты и полученные результаты ……………………………..9 1.4 Выводы по разделу………………………………………………13 2 Синтез конечных автоматов 2.1 Постановка задачи ……………………………………………… 14 2.2 Теоретические сведения …………………………………………14 2.3 Расчёты и полученные результаты …………………………… 16 Выводы по разделу……………………………………………… 20 3 Сети Петри 3.1 Постановка задачи ……………………………………………… 21 3.2 Теоретические сведения ……………………………………… 21 3.3 Расчёты и полученные результаты …………………………… 26 3.4 Выводы по разделу……………………………………………… 31 Заключение …………………………………………………………. 32 Литература ………………………………………………………… 33 Приложение А ……………………………………………………… 34 ВВЕДЕНИЕ Работа посвящена синтезу дискретных устройств с “памятью” (конечных автоматов) и “без памяти” (комбинационных схем), а также анализу реально протекающих процессов с помощью сетей Петри. В первой части рассмотрена минимизация булевых функций, заданных в виде СДНФ, с помощью двух различных способов : карт Карно и метода склеивания Квайна – МакКласки. Полученные в виде минимизированных ДНФ функции были приведены к базисам, состоящим всего из одной функции : И – НЕ и ИЛИ – НЕ , а затем реализованы в виде комбинационных схем на соответствующих логических элементах. Во второй части заданный по условию в функциональном виде конечный автомат был минимизирован по числу состояний. Для полученного автомата был построен граф состояний. Затем, перейдя к двоичному представлению входных, выходных сигналов и сигналов состояния, в автомате были выделены элементы памяти и комбинационная часть, которая затем была минимизирована по числу переменнных. Автомат был реализован в базисе И – ИЛИ – НЕ с использованием D - триггера и задержки. В третьей части была проанализирована заданная сеть Петри с помощью двух способов: матричного и основанного на построении дерева покрываемости, а также написана программа для её моделирования. 1 Синтез комбинационных схем Постановка задачи Для двух булевых функций, построенных по варианту задания в виде (1.1.1) , (1.1.2) где gi, zi – десятичные числа из диапазона от 0 до 15 в двоичном виде, сделать следующее: а) представить F1 и F2 в виде СДНФ. б) минимизировать (по количеству переменных в ДНФ) F1 с помощью карт Карно, F2 – методом Квайна-МакКласки. в) реализовать в виде комбинационной схемы на логических элементах F1 – в базисе И – НЕ, F2 – в базисе ИЛИ – НЕ, предварительно приведя F1 и F2 к соответствующим базисам. gi и zi вычислять по выражениям: (1.1.3) (1.1.4) при g0 = A, z0 = B . Параметр изменять от 1 до тех пор, пока не будет получено 9 различных значений gi и zi. Теоретические сведения. Булевой алгеброй называется множество S объектов A, B, C…, в котором определены две бинарные операции (логическое сложение – дизъюнкция(+) и логическое умножение – конъюнкция(∙)) и одна унарная операция(логическое отрицание()). Оно обладает следующими свойствами: а) Для A, B, C S , (замкнутость); (коммутативные законы); (ассоциативные законы); (дистрибутивные законы); (свойства идемпотентности); в том и только том случае, если (свойство совместимости); S содержит элементы 1 и 0 такие, что для всякого элемента ; для каждого элемента A класс S содержит элемент Г (дополнение элемента A, часто обозначаемое символами Ā или 1- A ) такой, что , . В каждой булевой алгебре (законы поглощения), (законы склеивания), (двойственность, законы де Моргана). Если даны n булевых переменных X1, X2,…, Xn, каждая из которых может быть равна любому элементу булевой алгебры, то булевой функцией называется выражение (1.2.1) В каждой булевой алгебре существует ровно различных булевых функций n переменных. Система булевых функций называется полной (базисом), если любая функция может быть представлена в виде суперпозиции функций выбраной системы. Под критерим минимизации (упрощения) булевых функций будем понимать достижение минимума букв в записи функции. Введём понятие многомерного куба. Любую булеву функцию n переменных, заданную в ДНФ или СДНФ, можно отобразиь на n-мерном кубе, построенном в ортогональном базисе n булевых переменных. Каждое слагаемое в ДНФ или СДНФ представляется гиперплоскостью соответствующей размерности: если оно представляет собой конъюнкцию n переменных – точка, n-1 переменных – прямая, n-2 переменных – плоскость и т.д. Элементы n-мерного куба, имеющие s измерений, назовём s-кубами. Комплекс K(y) кубов функции y=ƒ(x1,x2,…,xn) есть объединение Ks(y) множеств всех её кубов. Отсутствующие в конъюнкциях переменные будем обозначать через x. Расчёты и полученные результаты. По варианту задания находим gi и zi: i gi zi 0 5 0 1 1 6 2 8 2 3 5 9 4 13 6 5 11 14 6 4 12 7 3 5 8 13 4 9 13 14 10 8 14 11 9 9 12 5 10 13 7 6 Неповторяющиеся значения gi: 5, 1, 8, 13, 11, 4, 3, 9, 7. Неповторяющиеся значения zi: 0, 6, 2, 9, 14, 12, 5, 4, 10. Таким образом, для F1 получаем выражение , (1.3.1) для F2: . (1.3.2) Для минимизации первой функции применяем метод карт Карно. Карта Карно – прямоугольник с 2n клетками, каждой из которых соответствует своя конъюнкция из n переменных и их отрицаний (дополнений). Проставляя единицы в соответствующих клетках, выбираем затем минимальную из всех возможных комбинацию покрытий. Применим карту Карно к заданной функции: x3x4 00 01 11 10 00 1 1 01 1 1 1 x1x2 11 1 10 1 1 1 Рисунок 1.2.1 – карта Карно На основании выбранной комбинации покрытий выписываем минимизированное выражение для функции F1: . (1.3.3) Для второй функции применяем метод Квайна-МакКласки. На первом шаге алгоритма выписываем комплекс K0-кубов заданной функции, упорядоченных по возрастанию количества единиц: 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 K0 = 0 1 0 0 1 0 1 0 1 (1.3.4) 0 0 0 1 0 1 0 0 0 . Второй этап основан на операции склеивания. Каждый из кубов проверяется на “склеиваемость” со всеми остальными. Склеивающиеся кубы должны различаться не более чем в одном разряде. Склеенный разряд в дальнейшем обозначается как x. Куб, участвовавший в операции склеивания, соответствующим образом помечается. Поскольку таких кубов мало, будем отмечать не участвовавшие в операции склеивания кубы. В результате получаем комплекс K1-кубов, также упорядоченный по возрастанию количества единиц в разрядах: 0 0 0 x 0 0 x x 1 1 0 x x 0 1 1 1 1 x 1 K1 = x 0 1 1 0 x 0 1 1 x (1.3.5) 0 0 0 0 x 0 0 0 0 0 . Повторяем вышеописанную операцию для комплекса K1-кубов, после чего удаляем из полученного комплекса K2-кубов повторяющиеся: 0 0 x x x x 0 x x x x x x 1 1 x x 1 K2 = x x 1 1 x x = x 1 x (1.3.6) 0 0 0 0 0 0 0 0 0 Те кубы, которые не участвовали в операциях склеивания, называются импликантами – это кандидаты на то, чтобы попасть в итоговую ДНФ. Для них составляем таблицу покрытий K0-кубов. Импликанта считается покрывающей K0-куб, если они совпадают при x, принимающем произвольное значение. K0 z 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 Импликанты 1001 + 010x + + 0xx0 + + + + xx10 + + + + x1x0 + + + + Таблица 1.3.1 – Покрытия K0-кубов Существенной импликантой, или экстремалью, называется такая импликанта, которая в единственном числе покрывает хотя бы один из K0-кубов. Из таблицы следует, что все импликанты являются экстремалями. Следовательно, они все войдут в запись функции в виде сокращённой ДНФ: . (1.3.7) Комбинационная схема – это дискретное устройство, каждый из выходных сигналов которого в момент времени tm определяется так: yj(tm) = ƒ ( x1(tm), x2(tm),…,xn(tm)) , (1.3.8) где . Видно, что выходной сигнал в m-й момент времени определяется только комбинацией входных сигналов в данный момент и не зависит от их предыдущих значений. Поэтому комбинационную схему можно реализовать на логических элементах, выполняющих операции из определённого базиса булевых функций. Приведём F1 к базису И – НЕ, а F2 – к базису ИЛИ – НЕ: (1.3.9) . (1.3.10) Получив выражения для функций, приведённых к соответствующим базисам, можно нарисовать комбинационные схемы, реализующие эти функции, на элементах одного вида: для первой функции это будут И – НЕ-элементы, для второй – ИЛИ – НЕ :
Рисунок 1.3.1 – Схема на И – НЕ-элементах
Рисунок 1.3.2 – Схема на ИЛИ – НЕ-элементах 1.4 Выводы по разделу В первой части были рассмотрены примеры минимизации (упрощения) булевых функций двумя разными способами. Была практически показана возможность приведения функций двух аргументов к базису, состоящему всего из одной функции. Были построены комбинационные схемы, иллюстрирующие полученные результаты. Выгода рассмотренных преобразований функций становится очевидной при их практической реализации на стандартизованных электронных микросхемах. 2 Синтез конечных автоматов 2.1 Постановка задачи Конечный автомат задан своими уравнениями переходов и выходов: s(j+1) = [2∙s(j) + x(j) + B] mod 8 , y(j) = [ s(j) + x(j) + A] mod 2 , .
Внимание, отключите Adblock
Вы посетили наш сайт со включенным блокировщиком рекламы! Ссылка для скачивания станет доступной сразу после отключения Adblock!
Рефераты по информатикеСОДЕРЖАНИЕ Введение ………………………………………………………………6 1 Синтез комбинационных схем 1.1 Постановка задачи ……………………………………………… 7 1.2 Теоретические сведения
Оценок: 393 (Средняя 5 из 5)
Наверняка у вас есть товары или услуги, продажа которых приносит вам максимальную прибыль. Для быстрого старта в сети вам необходимо создание посадочной страницы (одностраничного сайта), на которой будет размещена информация о маржинальных товарах/услугах интернет магазина. За 8 лет опыта разработки конверсионных страниц мы выработали оптимальную структуру, которая позволит привлекать через landing page больше продаж. На такую структуру «одевается» ваш контент — фирменный стиль, тексты, фотографии, уникальные торговые предложения, после чего страница выходит в свет. Разработка лендинга и запуск в сети — до 7 рабочих дней. Стоит отметить, что в разработку самой посадочной страницы входит и написание копирайтером продающих текстов для вашего бизнеса, чтобы каждый посетитель страницы захотел совершить покупку именно у вас. Результат: качественно разработаная продающая посадочная страница, которая готова приносить вам новых клиентов.