Материал: Методичка Дзержинский

2e-1<m = |A| ≤ 2e;

2r-1<n = |Q| ≤ 2r;

2s-1<k = |B| ≤ 2s.

Очевидно, что e, r, s равны соответственно числу разрядов в двойном представлении чисел m, n, k.

2. Кодирование состояний, входных и выходных символов исходного автомата проводим следующим образом: каждому a A взаимнооднозначно ставим в соответствие булев вектор размерности e: x(a)=x1…xe. Аналогично каждому q Q и каждому b B ставим взаимнооднозначно в соответствие булев вектор α(q)= α1…αr и

z(b)=z1…zs.

Отметим, что кодирование состояний, входных и выходных символов можно провести многими способами. При этом некоторые булевы вектора могут оказаться неиспользованными.

Эта таблица содержит 2e+r строк и e + 2r + s столбцов. В первых e+r столбцах выписаны все булевы вектора длинны e+r в порядке возрастания их номеров. Каждый такой вектор соответствует паре (x, α), где x – код входного символа, α – возможный код некоторого состояния.

4.Заполнение последних r+s столбцов таблицы:

Для каждой пары (a, q) a A, q Q, находим код x(a) и α (q). По таблице автомата определяем G(a, q) = q’ и F(a, q) = b. Затем находим

код α(q’) = α’1, α’2…α’r и код z(b) = z1…zs. В строку таблицы соответствующую набору x1, x2…xe, α1…αr записываем набор α’1, α’2…α’r

z1, z2…zs.

6

5. В результате выполнения пункта 4 может оказаться, что не все строки в таблице будут заполнены. Это произойдёт в том случае, если хотя бы одно из чисел n, k не является степенью 2 таким образом функции g1…gr, f1…fs окажутся не полностью определёнными, т.е. на некоторых наборах их значения не определены. Тогда мы их доопределяем произвольным образом так, чтобы получаемые полностью определённые функции удовлетворяли тем или иным условиям оптимальности, например, представлялись минимальными ДНФ.

Замечание: Один и тот же автомат может быть задан разными системами булевых функций. Это следует, во-первых, из того, что кодирование состояний и входных символов можно производить различными способами, и, во-вторых, доопределение функцией g1,…,gr, f1,…,fs также производится неоднозначно.

Каноническая система булевых функций будет иметь вид

(*)

g1(t) = g1(x1(t),…,xe(t), q1(t-1),…,qr(t-1))

…

gr(t) = gr(x1(t),…,xe(t), q1(t-1),…,qr(t-1)) z1(t) = g1(x1(t),…,fe(t), q1(t-1),…,qr(t-1))

…

zr(t) = zr(x1(t),…,fe(t), q1(t-1),…,qr(t-1))

Реализация конечных автоматов схемами.

Если автомат задан канонической системой булевых функций, то его можно реализовать в виде схемы из функциональных элементов и элементов задержки. Система функций реализуемых функциональными элементами предполагается полной. Эти схемы называются логическими сетями (ЛС) или синхронными логическими сетями (СЛС) или комбинационными схемами. Они строятся по тем же правилам, что и схемы из функциональных элементов, но добавляется правило введения обратной связи которое состоит в том, что в каждом контуре содержится хотя бы один элемент задержки.

Опр. Состояние комбинационной схемы в момент времени t – это совокупность состояний эл. задержек.

Утверждение: Произвольный конечный автомат может быть реализован в виде СЛС, причем количество элементов задержки равно наименьшему целому числу, которое превосходит log2|Q|

7

Чтобы построить комбинационную схему из элементов данного базиса с задержками описываемую системой канонических уравнений (*), обозначим qi(t) через qi , qi(t-1) через qi * , xj(t) через xj zk(t) через zk

Получим систему

(**)

qi = qi(x1,…,xe, q’1,…,q’r) zk = fk(x1,…,xe, q’1,…,q’r) i = 1,…r

k = 1,…s

Функции в правых частях системы (**) надо представить формулами над данным базисом. Строим функциональную схему из элементов данного базиса реализующую функции qi и zk (i = 1…r; k = 1…s) и имеющую входами переменные x1,…,xe , q’1,…,q’2.

Затем каждому выходу qj через свой элемент задержки (зi) подаём на соответствующий вход q’j. Получим искомую комбинационную схему с задержками (или синхронную логическую схему) реализующую исходный автомат.

Автоматы Мура.

Пусть M = {A, Q, B, G, F} – автомат Мура, т.е. у него функции выхода в канонической схеме зависят только от состояний z(t)=F(q(t-1)) и не зависит от входящего символа в данный момент времени. В случае авт. Мура в диаграмме Мура все стрелки, выходящие из состояния q помечена буквой a, той же выходной буквой, поэтому принято для этих автоматов выходную букву писать над состоянием, а не над стрелкой. Выходные буквы наз. Метками состояний. В автоматной таблице также удобнее выходные буквы располагать в отдельной строке, так как в каждом столбце, не зависимо от входного символа, выходной символ один и тот же.

Простейшим автоматом Мура является задержка. Все то, что делает автомат Мили, может делать и автомат Мура.

Утверждение: (теорема) Для любого автомата Мили существует, покрывающий его автомат Мура. (Т.е. существует автомат Мура, который может производить все автоматные отображения, которые производит исходный автомат.

Доказательство: Допустим у исходного автомата мн. Q={q1,…,qn}

8

A={a1,…,an}. Надо построить автомат Мура, который делает все тоже самое, что и исходный. Построим автомат Мура. M’ = { A, Q’, B, C’, F’}, у которого

Q’ = {q10…qr0, q11…qr1, …, q1n...qnr} |Q’| = r + rn

Функции определим следующим образом

F’’(qi0) = - F’(qij) = F(aj, qi) G’(ak, qi0) = qik G’(ak, qij) = qlk,

где l определяется из следующего условия:

ql = G(aj, qi)

Если исходный автомат находится в состоянии qi и на вход подается символ aj, то исходный автомат переходит в состояние ql = G(aj, qi). Построенный автомат Мура М’ покрывает исходный автомат М. Для всякого состояния qi автомата М, покрывающим для него состоянием является qi0 Q

Пусть α = ai1, ai2…ai9 A* любое входное слово F(qi, α) = ωk1, ωk2…ωk9 – выходное слово.

Рассмотрим соответствующее выходное слово автомата М’, если он находится в каждый момент времени в состоянии qi0 и покажем, что эти два слова совпадают, если прочерк не учитывать.

Рассмотрим работу этих автоматов.

Новый автомат выдает те же самые выходные символы, что и исходный, но с задержкой на один такт.

Основные соединения автоматов.

1. Тривиальные параллельные соединения автоматов — это совокупность 2х автоматов с независимыми входами и выходами.

Если

M1 = { A1, Q1, B1, C1, F1, G1 }

9

M2 = { A2, Q2, B2, C2, F2, G2 }

то у автомата М входной алфавит А = А1×А2, B = B1×B2, Q = Q1×Q2 Параллельное соединение автоматов, когда M1 = {A, Q1, B1, C1, F1,

G1} M2 = {A, Q2, B2, C2, F2, G2} у М : B = B1×B2, Q = Q1×Q2

2.Последовательные соединения.

A=A1; B=B2; Q=Q1×Q2

3.Соединения с обратной связью.

Имеется некоторый автомат М1 и автомат Мура М2. Некоторый вход у автомата М1 является выходом автомата Мура М2 и наоборот.

Замечание. Возможны модификации, при которых происходит более мелкое разбиение алфавитов.

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

Триггеры:

Автомат Мура называется полным (или совершенным), если возможны переходы из любого его состояния в любое другое с помощью подходящей входной буквы, и разные состояния дают различные выходы.

Полный автомат Мура с двумя состояниями называется триггером.

F(q) ≡ q

1.D-триггер (линия задержки) . RS -_триггер. JKтриггер.

D-триггер

Таблица 3

10