Хороший материал для К.Р. и так почитать

Как видно, выполнение операции 3 уменьшает число единиц в строках матрицы Х′. Операции 2 и 3 повторяются до тех пор, пока в каждой строке матрицы Х′число единиц будет не более чем k.

4. Для i-й строки матрицы Х′ в получаемую систему уравнений вносится уравнение Ki = zi1 zi2 ... zi p (i = 1, 2, … , т), где т – число строк матрицы

Х′, zi j (j = 1, 2, … , p) – литерал, соответствующий столбцу, с единицей в i-й

строке матрицы Х′, р – число единиц в i-й строке матрицы Х′.

В результате выполнения описанных действий получим систему уравнений, описывающую ту часть синтезируемой схемы, которая реализует элементарные конъюнкции из заданной системы ДНФ.

17.2. Реализация дизъюнкций

Для реализации дизъюнкций выполняются следующие действия, в основном подобные тем действиям, которые выполнялись при реализации конъюнкций.

1.Путем транспонирования матрицы Y получается матрица Y′.

2.В матрице Y′ отыскивается минор, содержащий только единицы и образованный не более чем k столбцами и как можно большим числом строк.

3.Все единицы матрицы Y′, входящие в полученный минор, заменяются нулями, в матрицу Y′ добавляется столбец gj + 1, где j – число столбцов, которое

кданному моменту приобрела матрица Y′ в результате выполнения рассматриваемых действий. Этот столбец имеет единицы в строках минора и нули – в остальных строках. В формируемую систему уравнений вносится

соответствующий столбцу, входящему в выделенный минор.

Так же, как в предыдущем процессе, операции 2 и 3 повторяются до тех пор, пока в каждой строке матрицы Y′число единиц будет не более чем k.

4. Для i-й строки матрицы Y′ в получаемую систему уравнений вносится уравнение уi = zi1 zi2 ... zi p (i = 1, 2, … , т), где т – число строк матрицы

Y′, zi j (j = 1, 2, … , p) – литерал, соответствующий столбцу, с единицей в i-й

строке матрицы Y′, р – число единиц в i-й строке матрицы Y′.

В результате выполнения описанных действий получим систему уравнений, описывающую ту часть синтезируемой схемы, которая реализует дизъюнкции.

131

17.3. Пример

Для демонстрации описанного метода зададим базис элементов с числом входных полюсов 2 и возьмем в качестве примера систему ДНФ, заданную следующей парой матриц:

В результате преобразования матрицы Х получим следующую матрицу:

В этой матрице замечаем минор, образованный строками 1, 2 и столбцами х1, х2. Выполняя пункты 2 и 3 процесса реализации конъюнкций, получаем следующие матрицу и уравнение:

Повторяя те же действия, получаем следующие матрицы и уравнения:

132

В последней матрице все строки имеют ровно по две единицы. Им

соответствуют уравнения K1 = x1 g1, K2 = g1 g4, K3 = x4 g2, K4 = g2 g5, K5 = x1 g3,

K6 = x4 g3.

133

Результатом транспонирования матрицы Y является матрица

Эта матрица имеет только один минор с единицами, содержащий более одной строки. Он образован строками у1, у3 и столбцами K1, K3. Для уменьшения числа единиц в строке у2 берем однострочный минор со столбцами K2, K3. В результате получаем следующую матрицу и соответствующие уравнения:

Полное описание схемы представляется следующей системой уравнений:

134

Значением функции Ψ(a, q) является состояние q+, в которое переходит автомат из состояния q, если на вход его подан символ а. Значением функции Φ(a, q) является выходной символ, выдаваемый автоматом в состоянии q при поступлении на его вход символа а, а значением функции Φ(q) автомата Мура – выходной символ b, который выдает автомат, находясь в состоянии q. Если значения функций Ψ(a, q) и Φ(a, q) определены для любой пары значений аргументов а и q, а в модели Мура функция Φ(q) определена для всех значений q, то автомат является полностью определенным, или полным автоматом. Иногда приходится иметь дело с не полностью определенным, или частичным

автоматом, у которого эти функции могут быть определены не везде.

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

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

В асинхронном автомате переход из состояния в состояние происходит за некоторый конечный промежуток времени, в течение которого не должен меняться входной сигнал. При действии любого входного сигнала автомат приходит в некоторое устойчивое состояние, из которого он не выходит до конца действия данного сигнала. При этом должно выполняться требование прямого перехода, которое формально выражается следующим образом: если Ψ(a, qi) = qj, то Ψ(a, qj) = qj. Иногда допускается выполнение следующей цепочки переходов: Ψ(a, qi) = qr, Ψ(a, qr) = qs, … , Ψ(a, qt) = qj, Ψ(a, qj) = qj.

18.2. Представления автомата

Конечный автомат удобно представлять таблицей переходов и таблицей выходов. Строкам этих таблиц соответствуют состояния автомата, столбцам – входные символы. На пересечении строки, соответствующей состоянию q, и

137

столбца, соответствующего входному символу а, в таблице переходов записывается значение Ψ(a, q), а в таблице выходов – значение Φ(a, q). Другими словами, в первом случае в клетке таблицы указывается состояние, в которое автомат переходит из состояния q при поступлении на его вход символа а, а во втором случае – выходной символ, который при этом выдает автомат. Табл.18.2 и табл.18.3 представляют собой пример описанного представления автомата Мили, у которого А = {a1, a2, a3, a4}, В = {b1, b2} и

Q = {q1, q2, q3}.

Зная начальное состояние автомата и входную последовательность, нетрудно получить по этим таблицам соответствующую последовательность выходных символов. Приведем пример такого соответствия для автомата, заданного табл. 18.2 и 18.3, на вход которого поступила последовательность символов а1, а2, а2, а1, а3, а4, а1, а4 при начальном состоянии q1. Покажем также состояния, которые проходит автомат:

Автомат Мура представляется одной таблицей переходов, к которой добавлен один столбец со значениями функции выходов (табл. 18.4).

Можно свести таблицу переходов и таблицу выходов автомата Мили в одну таблицу, которую называют таблицей переходов и выходов. Такая таблица для автомата, заданного в виде табл. 18.2 и табл. 18.3, имеет вид табл. 18.5.

Более наглядным при небольшом числе состояний является представление автомата в виде графа поведения автомата, который представляет собой ориентированный граф. Его вершины соответствуют состояниям автомата, а дуги – переходам между состояниями. При этом дуга помечается всеми входными символами, которые вызывают соответствующий переход, и выходными символами, сопровождающими данный переход (в случае автомата Мили). В случае автомата Мура выходными символами помечаются вершины, соответствующие состояниям, в которых находится автомат при выдаче данных символов. На рис. 18.1 изображены графы переходов автоматов, заданных табл. 18.4 и 18.5.

138

Рис. 18.1. Примеры графов поведения: а) автомата Мура; б) автомата Мили

Еще одним способом представления автомата является матрица поведения, представляющая собой квадратную матрицу, строки и столбцы которой помечаются состояниями автомата. В случае автомата Мура на пересечении строки qi и столбца qj матрицы поведения записываются входные символы, переводящие автомат из состояния qi в состояние qj, а строки помечаются также и выходными символами. В случае автомата Мили элементы матрицы поведения, кроме входных символов, вызывающих соответствующие переходы, содержат выходные символы, которые сопровождают эти переходы. Если из состояния qi нет перехода в состояние qj, то на пересечении строки qi и столбца qj ставится прочерк. Для рассмотренных автоматов ниже представлены матрицы поведения, причем первая из них – матрица поведения автомата Мура, вторая – матрица поведения автомата Мили.

139

18.3. Связь между моделями Мили и Мура

Всякое отображение входных последовательностей в выходные может быть реализовано как с помощью модели Мили, так и с помощью модели Мура. Определим преобразование, переводящее любой автомат Мили в эквивалентный ему автомат Мура, а также преобразование, переводящее любой автомат Мура в эквивалентный ему автомат Мили.

Пусть задан автомат Мура М = (A, B, Q, Ψ, Φ) и требуется получить

эквивалентный ему автомат Мили М = (A , B , Q , Ψ , Φ ).

Очевидно, А = А и В = В. Положим Q = Q и Ψ = Ψ, а Φ определим следующим образом. Пусть Ψ(a, q) = q′ и Φ(q′) = b, где q, q′ Q, a А и b В. Это означает, что автомат, будучи в состоянии q, отвечает на входной символ а выходным символом b, который выдается в следующий момент времени, когда автомат окажется в состоянии q′. Следовательно, можно считать, что Φ (а, q) = b. Автомат Мура и эквивалентный ему автомат Мили представлены в табл. 18.6 и 18.7 соответственно.

Пусть теперь задан автомат Мили М = (A, B, Q, Ψ, Φ) и требуется получить эквивалентный ему автомат Мура М = (A , B , Q , Ψ , Φ ). Как и в предыдущем случае, имеем А = А и В = В. Определим Q следующим образом. Рассмотрим все такие пары вида (q, b), где q Q, b B, что для каждой (q, b) имеется такая пара (a, q′), что Ψ(a, q′) = q и Φ(a, q′) = b (a A, q′ Q). Каждой паре (q, b) поставим в соответствие состояние q Q и определим функции Ψ и Φ следующим образом:

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

140