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

00 1 1

01 1 1 1

x₁x₂

11 1

10 1 1 1

Рисунок 1.2.1 – карта Карно

На основании выбранной комбинации покрытий выписываем минимизированное выражение для функции F₁:

. (1.3.3)

Для второй функции применяем метод Квайна-МакКласки.

На первом шаге алгоритма выписываем комплекс K⁰-кубов заданной функции, упорядоченных по возрастанию количества единиц:

0 0 0 0 0 1 1 1 1

0 0 1 1 1 0 0 1 1

K⁰ = 0 1 0 0 1 0 1 0 1 (1.3.4)

0 0 0 1 0 1 0 0 0 .

Второй этап основан на операции склеивания. Каждый из кубов проверяется на “склеиваемость” со всеми остальными. Склеивающиеся кубы должны различаться не более чем в одном разряде. Склеенный разряд в дальнейшем обозначается как x. Куб, участвовавший в операции склеивания, соответствующим образом помечается. Поскольку таких кубов мало, будем отмечать не участвовавшие в операции склеивания кубы. В результате получаем комплекс K¹-кубов, также упорядоченный по возрастанию количества единиц в разрядах:

0 0 0 x 0 0 x x 1 1

0 x x 0 1 1 1 1 x 1

K¹ = x 0 1 1 0 x 0 1 1 x (1.3.5)

0 0 0 0 x 0 0 0 0 0 .

Повторяем вышеописанную операцию для комплекса K¹-кубов, после чего удаляем из полученного комплекса K²-кубов повторяющиеся:

0 0 x x x x 0 x x

x x x x 1 1 x x 1

K² = x x 1 1 x x = x 1 x (1.3.6)

0 0 0 0 0 0 0 0 0

Те кубы, которые не участвовали в операциях склеивания, называются импликантами – это кандидаты на то, чтобы попасть в итоговую ДНФ. Для них составляем таблицу покрытий K⁰-кубов. Импликанта считается покрывающей K⁰-куб, если они совпадают при x, принимающем произвольное значение.

Таблица 1.3.1 – Покрытия K⁰-кубов

Существенной импликантой, или экстремалью, называется такая импликанта, которая в единственном числе покрывает хотя бы один из K⁰-кубов.

Из таблицы следует, что все импликанты являются экстремалями. Следовательно, они все войдут в запись функции в виде сокращённой ДНФ:

. (1.3.7)

Комбинационная схема – это дискретное устройство, каждый из выходных сигналов которого в момент времени t_m определяется так:

y_j(t_m) = ƒ ( x₁(t_m), x₂(t_m),…,x_n(t_m)) , (1.3.8)

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

Приведём F₁ к базису И – НЕ, а F₂ – к базису ИЛИ – НЕ:

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

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

Конечный автомат можно также описать с помощью матрицы переходов. Это аналог графа в табличной форме. Она представляет собой квадратную матрицу размерности число состояний число состояний, в которой отражены условия перехода из состояния в состояние аналогично изображённым на графе.

Общее определение конечного автомата:

M = (X, Y, S, δ, λ), (2.2.5)

где X – входной алфавит, Y – выходной алфавит, S – множество состояний, δ – функция переходов, λ – функция выходов.

Пусть имеется два автомата: M и M’.

Если для любого существует по крайней мере одно , эквивалентное ему, то говорят, что M’ покрывает M: M’ ≥ M.

Если одновременно M’ ≥ M и M ≥ M’, то M ~ M’ . Получаем эквивалентные автоматы. В этом случае невозможно различить M и M’ по их реакции на входные сигналы.

Существуют два основных положения определения понятия эквивалентности состояний:

а) состояния s_i и s_j явно различны, если соответствующие им строки в таблице выходов разные;

б) состояния s_i и s_j явно эквивалентны, если соответствующие им строки в общей таблице переходов автомата одинаковы или становятся таковыми при замене s_i на s_j или наоборот.

Минимизация (упрощение) автоматов основано на понятии эквивалентных автоматов. Под минимизацией автомата будем понимать сокращение числа его состояний.

2.3 Расчёты и полученные результаты.

Построение таблиц переходов, выходов и общей таблицы переходов и выходов на основе заданных уравнений автомата Мили очевидно:

Таблица 2.3.1 – Таблица выходов автомата

Таблица 2.3.2 – Таблица переходов автомата

Таблица 2.3.3 – Общая таблица переходов и выходов автомата