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

Информация - Компьютеры, программирование

Другие материалы по предмету Компьютеры, программирование

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



 

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

 

z0

0

0

00

0

1

00

1

0

00

1

0

10

1

1

01

0

0

11

0

1

01

1

0

01

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, составить таблицу входов и выходов комбинационной схемы автомата и выполнить минимизацию булевых функций, соответствующих выходам и состояниям автомата;

д) разработать л

s