Xreferat.com » Рефераты по информатике и программированию » Синтез комбинацонных схем и конечных автоматов, сети Петри

Синтез комбинацонных схем и конечных автоматов, сети Петри

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 ,


.


Требуется:

а) построить таблицы переходов, выходов и общую таблицу переходов автомата;

б) минимизировать автомат по числу состояний с использованием таблиц, полученных ранее;

в) построить граф минимизированного автомата и выписать для него матрицу переходов;

г) переходя ко двоичному представлению входа X, выхода Y и состояния S, составить таблицу входов и выходов комбинационной схемы автомата и выполнить минимизацию булевых функций, соответствующих выходам и состояниям автомата;

д) разработать логическую схему автомата в базисе И – НЕ, реализуя элементы памяти на триггерах и задержках.


2.2 Теоретические сведения

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

Различают синхронные и асинхронные автоматы. У асинхронных смена выходных сигналов y(tj) может происходить только в моменты изменения входных x(tj) , у синхронных – в моменты времени, определяемые дополнительным синхронизирующим сигналом c(t) .

Определим множества, которым могут принадлежать входные и выходные сигналы (условимся обозначать tj как j):

– множетва входных и выходных сигналов.

Тогда выражения


(2.2.1)

определяют входной и выходной алфавиты автомата.

Пусть . Тогда если y(j) = λ(x(j)), то этот автомат является, очевидно, комбинационной схемой.


Введём дополнительную переменную для того, чтобы охарактеризовать состояние автомата в каждый момент времени j:

(2.2.2)


В том случае, если X, Y и S – конечные множества, то и сам автомат называют конечным.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: