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

Неповторяющиеся значения 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 ,

 .

Требуется:

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

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

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

г) переходя ко двоичному представлению входа  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 – конечные множества, то и сам автомат называют конечным.

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

                                                                            (2.2.3)

Записанный таким образом автомат называется автоматом Мили. Ясно, что это – более информативная форма записи по сравнению с автоматом Мура:

                                                                         (2.2.4)

Способы задания автоматов.

Во - первых, автомат может быть задан непосредственно уравнениями вида (2.2.3) или (2.2.4).

Во - вторых, уравнения (2.2.3) и (2.2.4) могут быть представлены в табличной форме. Табличный аналог первого уравнения в (2.2.3) называется таблицей переходов, второго – таблицей выходов.

В - третьих, таблицы переходов и выходов можно объединить в одну. Содержимое каждой клетки представляет собой дробь: над косой чертой вписывается соответствующее значение из таблицы переходов, под косой чертой – значение из таблицы выходов. Полученная таким образом таблица называется общей таблицей переходов и выходов конечного автомата.

Граф автомата – это сигнальный граф, вершины которого обозначают состояния автомата, на дугах отражены условия перехода из состояния в состояние и значения выходных сигналов в виде дроби: над косой чертой – x(j), под ней – y(j).

Страницы: 1, 2, 3, 4, 5