Таблица 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).

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

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

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

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

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

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

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