Преобразование Мура в Миля

Понятие эквивалентности автоматов

Два автомата, у которых входные и выходные алфавиты одинаковы или между буквами этих алфавитов можно установить взаимно однозначное соответствие, то их называют эквивалентными если любое входное слово оба автомата перерабатывают в одни выходные, при условии что автоматы находились в начальном состоянии.

A_r = <P_r, W_r, S_r, s_0r, φ_r, ψ_r>

A_l = <P_l, W_l, S_l, s_0l, φ_l, ψ_l>

A_r – автомат Мура задан, необходимо найти эквивалентное ему автомат Миля. A_l

1) P_l = P_r

2) W_{l =} W_r

3) S_{l =} S_r

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

S_l <= S_r

4) s_0l = s_0r

5) в Мура S_r(t+1) = φ_r(S_r(t), P_r(t))

в Миле S_l(t+1) = φ_l(S_r(t), P_l(t))

следовательно φ_l(S_iP_j) = φ(S_jP_j)

Новое состояние как в Муре так и в Миле зависит от предыдущего состояния и предыдущего входного сигнала.

Так как во время преобразования Мура в Миля уже установлены условия 1 и 3, то функция переходов при одном и том же воздействии автомата Миля должна совпадать с функцией переходов автомата Мура при тех же воздействиях.

W_l(t+1) = ψ_l(S_l(t), P_l(t))

W_r(t+1) = ψ_r(S_r(t+1)) = ψ_r(φ_r(S_r(t), P_r(t))

W_l(t+1) = W_r(t+1)

В автомате Миля новое выходное значение зависит от старых состояний и выходного сигнала.

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

S_r(t+1) = φ_r (S_r(t), P_r(t))

Определяется через старое состояние, то подставим

S_r(t+1).

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

Техника преобразований.

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

Пример:

P₂

Автомат Мура

Автомат Миля

Обратный переход.

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

Пример

т.е. нужно получить:

Пример 2:

тогда происходит расщепление состояний:

При переходе от автомата Миля к Муру – аналогично как и в предыдущем переходе должны совпадать все алфавиты и все функции.

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

В общем случае при переходе к автомату Мура число состояний может увеличиваться.

Если одно и тоже устройство описывается моделями автоматов Мура и Миля, то в модели на основе автомата Мура устройство может иметь больше число состояний.

Автомат Миля:

Автомат Мура:

Частичные или не полностью определенные автоматы.

Пусть P = {P₀, P₁, …, P_n} – входной алфавит

P^* - множество всех слов в алфавите P

P^*_g – множество допустимых слов

P^*_g <= P^*

P^*_з = P^* / P^*_g - множество запрещенных слов

P^* и P^*_g – слова одной и той же длины

Автомат называется частичным, если

1) множество запрещенных слов не пусто или

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

P_1, P₁, P₂, P₁

W₀, W₁, *, W₀

, W₀,

, W₁,

Условие 1 приводит к тому, что в таблице переходов автомата будут прочерки – отсутствующие переходы.

Условие 2 приводит к тому, сто в значениях выходах таблицы будут находиться «*».

Пример: автомат Миля.

Pj	P1	P2	P3
Si
S0	S2/W1	---	---
S1	---	S2/*	S2/W2
S2	---	S0/W3	S3/W1
S3	---	S0/W1	S0/W3

В таблице присутствует как 1 так и второе условие.

		P1 / W1
	P2 / W1

Второе условие по графу видно явно, а первое нет.

Для проверки условия 1 нужно в каждой вершине проверить наличие переходов по каждой букве входного алфавита.

Так для состояния «S₀» есть переход только по P₁ и отсутствует P₂ и P₃

Синтез конечных автоматов.

Синтез состоит из двух этапов.

1) Абстрактный синтез

2) Структурный синтез

Абстрактный синтез конечных автоматов.

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

Исходные данные задаются в виде алфавитного оператора. Алфавитный оператор называется оператор, устанавливающий соответствия между входными и выходными словами, которые перерабатывает автомат.

Индексы указывают на номера машинного такта, а не на различие между буквами.

P = {0, 1}

W = {0, 1}

P₀ P₁ P₂ P₃ W₀ W₁ W₂ W₃

0 0 0 0 0 0 0 0

0 0 0 1 0 0 1 0

0 1 0 0 0 1 0 0

1 0 0 0 1 0 0 0

Алфавит операций называется автоматным, если он удовлетворяет следующим условиям:

1) Однозначно отображает входные слова в выходные

2) Удовлетворяет условию полноты, т.е. представляет все входные последовательности входящие в допустимый набор P_g^*

3) Оператор сохраняет длину преобразованного слова

4) Оператор осуществляет преобразование одинаково локальных отрезков входного слова в совпадающие начальные отрезки выходных слов.

Утверждение:

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

Для полученного автоматного алфавитного оператора из не автоматного используют 2 операции: выравнивание и пополнение. Операция выравнивания используется, если нарушено условие автоматности оператора и заключается в добавлении нового пустого символа e справа во всех последующих или слева к выходной.

Явно восстанавливаем 3 условие автоматности оператора.

Пример:

P0	P1	W0	W1
		e
		e
		e
		e

Нарушено 3 условие – длина выходного слова меньше длины входного, поэтому слева к выходному слову добавляют пустой символ e.

После пополнения выходной алфавит будет выглядеть: W = {0, 1, e}

P = {0, 1}

W = {0, 1} – изначально

Операция пополнения используется если нарушено 4 условие и заключается в добавлении пустого символа e справа к входной последовательности и слева к выходной одновременно.

P0	P1	P1	W0	W1	W2
		e	e
		e	e
		e	e
		e	e

Вначале P = {0, 1}

W = {0, 1}

Стало P = {0, 1, e}

W = {0, 1, e}

Начальный отрезок из одной буквы 0 в исходном операторе в первой строке преобразовывается в 0 а во втором в 1, следовательно нарушено 4 условие, поэтому к входному слову слева и к выходному слева дописывается пустой символ e, при этом изменяется входной и выходной алфавиты.

А операторы могут быть заданы двумя способами: табличным и графическим.

Пример:

P₀ P₁ P₂ W₀ W₁ W₂

0 0 e₁ e₁ 0 0

0 0 e₂ e 0 1

Если в операции пополнения используют несколько пустых символов e (e₁ , e₂ , …), то можно восстановить первое условие автоматности.

P₀ P₁ W₀ W₁

0 0 0 0

0 0 0 1

Табличный способ устанавливает соответствие между входными и выходными последовательностями в форме таблицы.

В графическом способе оператор представляется в виде нагруженного дерева входными последовательностями.

Пусть от вершины к листу дерева соответствует одному входному слову.

Входные буквы помечают дуги между вершинами дерева. Выходное слово также присутствует на пути из корня к листу. Число ярусов дерева соответствует длине входного слова.

Построение дерева входных последовательностей.

Пусть задан входной алфавит:

1) Фиксирована вершина, которая называется корнем дерева

2) Из вершины проводят n дуг, каждая из которых помечается буквой входного алфавита.

3) Строится n вершин

4) Из каждой вершины проводят n дуг и так далее

5) Последняя вершина – лист – называется конечной вершиной.

На дереве каждому символу P соответствует свой символ W_i

Чтобы построить автомат нужно: для полученного автомата по автоматному алфавитному оператору необходимо выполнить следующие действия:

1) Представить алфавит операций или представить в виде дерева входных последовательностей.

2) Отметить все вершины дерева символами соответствия автомата, при этом корень пометить начальным состоянием, а все листья конечными.

3) Для полученного автомата Мура вершины отметить символами выходных букв

Для полученного автомата Мили отметить дуги символами выходных букв

4) Все конечные вершины объединяются в одну

5) Найти эквивалентное состояние и объединить их между собой.

Нестрогое определение автомата

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

		Pi
		Pj

6) Для получения автомата многократного действия совмещаются вершина конечная с начальной.

Автомат, который после переопределения входного слова готов к приему следующего, называется автоматом многократного действия.

Пример:

P0	P1	P2	W0	W1	W2

1) Строим дерево

алфавит:

P = {0, 1}

W = {0, 1}

a)

b)

S = {S₀, S₁, S₂, S₃, S₄, S₅, S₆, S_k }

c) Строим автомат Миля.

0 / 1

d) Объединяем S_k

e) S₃ = S₄ - эквивалентно

S₅ = S₆

S_3,4 = S_5,6

S₁ = S₂

f) Автомат многократного действия

Теcт:

t0	t1	t2		ti
S0	S1	S2	S0	Si
				Pi
				Wi

Si / Pi
S0	S1/0	S1/0
S1	S2/0	S2/0
S2	S0/1	S0/0

Абстрактный этап синтеза конечного автомата состоит из следующих подъэтапов:

1) Преобразование алфавитного оператора к автоматному виду.

2) Построение абстрактного автомата по полученному автоматному алфавитному оператору.

3) Минимизация числа состояний абстрактного автомата.

Структурный этап синтеза автоматов.

Исходными данными для структурного этапа являются:

1. Абстрактный автомат, заданный виде графа или табличных переходов и выходов.
2. Система логических элементов, на которых необходимо реализовать автомат.
3. Тип элемента памяти, на котором реализуется автомат.
4. Требования, предъявляющиеся к схеме автомата по сложности и (или) быстродействию и так далее.

Результатом этапа является функциональная схема на заданных логических элементах.

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

КУ – комбинационный узел

БП – блок памяти

ЭП – элемент памяти

X₁…X_m – коды (в совокупности код одной буквы входного алфавита)

Z₁…Z_m – код выходной буквы

Y₁…Y_k – код состояния автомата

Y₁¹…Y_k¹

1) X₁…X_m – входные переменные структурного автомата, которые обозначают коды символов входного алфавита.

2) Z₁…Z_m – выходные переменные структурного автомата, которые обозначают разряды кодов символов выходного алфавита.

3) Y₁…Y_k – внутренние переменные структурного автомата, которые обозначают разряд кода символов состояний.

4) Y₁¹…Y_k¹ – функции возбуждения элементов памяти структурного автомата.

Между переменными абстрактного и структурированного автоматов существует взаимнооднозначное и структурное соответствие.

Входные алфавиты.

Абстрактная	Структурная
P = {P1…Pn}	X = {δ1, δ2,…, δn} – множество кодовых комбинаций на входе
P1≡ δ1 – букве соответствует код Pn≡ δn
W = {W1,…,Wl}	Z = {β1, β2…, βl} – множество кодовых комбинаций выходных переменных
W1 ≡ β1 We ≡ βe
S = {S1,…Sm}	Y = {γ1,…, γm} – множество кодовых комбинаций внутри переменной соответствующей состоянию
S1 ≡ γ1 Sm ≡ γm
Sj = φ(Si,Pk)	y1 = φ1^1(γ1, δ1) … yk = φk^1(γi, δi)
Функция перехода Автомат Мура: Wj = ψ(Sj)	Z1 = ψ (γj) … Zm = ψ^1m (γj)
Автомат Миля Wj = ψ(Sj, Pk)	Z1 = ψ^11 (γj, γi) … Zm = ψ^1m (γj, γi)

γ_j, β₁, δ₁ – конкретные значения кодовых комбинаций.

Основные этапы структурного синтеза.

1. Кодирование входного и выходного алфавитов (если требуется).
2. Кодирование информации может быть опущены, так как в исходных дпнных входы и выходы могут быть закодированы.
3. Кодирование состояний абстрактного автомата.

Существует много способов кодирования состояний.

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

Если автомат имеет m состояний, то длина кода может быть от log₂m до m.

1. Закодированные значения входных и выходных состояний подставляют в таблицу переходов и выходов и получают кодированную таблицу переходов и выходов, которые описывает уже структурный автомат.
2. На основе кодированной таблицы строится система Булевой функции для возбуждения элементов памяти и выходов автомата.
3. Совместно минимизируется полученная система булевых функций (пример Карты Карно).
4. Построение блока памяти на логических элементах.
5. Построение функциональной схемы всего автомата на заданных логических элементах.

Типы памяти.

Триггер – это двоичный элемент памяти. В качестве элементов памяти используется двоичные элементы – триггеры, которые имеют два устойчивых состояния.

Элемент памяти как правило имеет два выхода: прямой и инверсный.

Значение на прямом выходе соответствует коду состояния триггера и как правило выходному сигналу триггера.

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

Автомат обладает полной системой переходов, если любых пар S_i и S_j можно указать сигнал вызвавший переход из S_i в S_j.

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

Основные типы триггеров.

Существует 4 основных логических типа триггера:

два одновходовых: «D», «T»

два двухвходовых: «RS», «JK»

1. «D» триггер или триггер задержки (delay)

Графическое обозначение:

это автомат Мура (дуги – значения D)

Выходные значения во всех значениях будут совпадать с кодом состояния и будут обозначаться буквой q.

W(q)	P(D)
S(q)

Для триггеров удобно использовать иную форму таблицы переходов.

q^t à q^t+1	D
0 à 0
0 à 1
1 à 0
1 à 1

Эта таблица упрощается и приводится к виду:

0 à 0 т.е. значение D пишется над стрелкой.

0 à 1

1 à 0

1 à 1

1. «T» триггер (Toggle - кувыркаться)

Триггер меняет свое состояние (Т = 1)

q / T

q^t à q^t+1	T
0 à 0
0 à 1
1 à 0
1 à 1

0 à 0

0 à 1

1 à 0

1 à 1

1. «RS» триггер

R – reset – сбрасывает в 0 (00 – хранение предыдущего состояния)

S – set – установка в 1 (11 - запрещена)

R = 1 – сброс

S = 1 – установка

R = S = 0 – хранение

R = S = 1 – запрещена.

* - безразлично чему равен сигнал

q / RS
				--
				--

«--» - запрещенные комбинации

q^t à q^t+1	RS
0 à 0	*0
0 à 1
1 à 0
1 à 1	0*

*0

0 à 0

0 à 1

1 à 0

0*

1 à 1

1. «JK» триггер (jump – установка 1, kill - сброс)

J = 1 K = 0 – установка

J = 0 K = 1 – сброс

J = K = 0 - хранение

J = K = 1 – инверсия

1)

0*

00 – хранение

01 - сброс

2) 0 à 1

1*

10 – установка

11 - инверсия

3) 1 à 1

*0

4) 1 à 0

*1

q / JK

q^t à q^t+1	JK
0 à 0	0*
0 à 1	1*
1 à 0	*1
1 à 1	*0

0*

0 à 0

1*

0 à 1

*1

1 à 0

*0

1 à 1

Пример структурного синтеза синхронного автомата.

Автомат называется синхронным, если его состояние меняется в строго определенные моменты времени.

Эти моменты времени определяется с помощью специальных синхронизаций сигналов.

тип логического элемента:

«И» «НЕ»

тип памяти RS

Нужно получить минимум затрат, т.е. минимум логических элементов.

Этапы:

P = {0,1}

W = {0,1}

Кодирование производить не надо. т.к. они уже кодированы.

Триггер – 1 разряд

log₂3 = 2, т.е. для кодирования нужно минимум два разряда

Закодируем произвольно

q₀ q₁

S₀ = 0 1

S₁ = 1 1

S₂ = 1 0

Представим исходный автомат виде таблицы переходов и выходов.

Si / Pi
S0	S1 /0	S1 /0
S1	S2 /0	S2 /0
S2	S0 /1	S0 /0

Вместо состояний приводим в таблице их коды и получаем кодированную таблицу переходов и выходов

Xi / q0q1
0 1	11 /0	11 /0
1 1	10 /0	10 /0
1 0	01 /1	01 /0

RS

*0

0 à 0

0 à 1

1 à 0

0*

1 à 1

Xi / q0q1
0 1	01,0* /0	01,0* /0
1 0	0*,10 /0	0*,10 /0
1 1	10,01 /1	10,01 /0

Данная таблица называется таблица функций возбуждения и выходов.

Вместо кодов состояний в ней приводится значение на входе триггеров, которые приведут триггер в требуемое состояние.

В данной таблице представлены 5 булевых функций: R₀, S₀, R₁, S₁,Z₀

R0			------------q1
		------------q0
	---
X0 -	---

S0			------------q1
		------------q0
	---		*
X0 -	---		*

R1			------------q1
		------------q0
	---
X0 -	---

S1			------------q1
		------------q0
	---			*
X0 -	---			*

Z0			------------q1
		------------q0
	---
X0 -	---

В результате:

R₀ = ^q₁ (^ - отрицание)

S₀ = q₁

R₁ = q₀q₁

S₁ = ^q₁

Z₀ = ^q₁^X₁

В результате получается окончательная схема:

C – синхронизация

В начальном состоянии триггеры должны быть закодированы (установлены в начальное состояние S₀) т.е. q₀ – сброс

S₁ – установка

При с = 0 функции возбуждения непосредственно на входах триггеров равны 0

Это соответствует режиму хранения двух триггеров, следовательно автомат находится (остается) в том же состоянии и не осуществляет переход.

При с = 1 получаем

R₀¹ = R₀

S₀¹ = S₀

R₁¹ = R₁

S₁¹ = S₁

т.е. непосредственно на входы триггера поступает синтезированная функция возбуждения и триггеры переключаются, т.е переходят из состояния в состояние в автомате и получаем на выходе q_i новые входы.

Длительность с = 1 должна быть достаточной, чтобы сработал «и» на входе триггеров и переключились сами триггеры.

В тот момент времени, когда переключились триггеры, входные сигналы R и S не должны изменяться в противоположном случае поведение триггера может оказаться непредсказуемым.

С другой стороны в это время меняется значение q_i и они по обратной связи поступают на вход триггера, т.е. могут привести к изменению значений R_i, S_i

Следовательно длительность сигнала с должна быть ограничена сверху так, чтобы новые значения q_i не успели поступить на входы R_i, S_i (т.е. с – достаточно короткое).

Корректное значение z можно получить лишь тогда, когда q и x неизменные, т.е. после окончания их переключения и завершения всех переходных процессов в схеме, а это происходит при с = 0.

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

После переключений состояние уже будет новое, следовательно z уже не будет, S – уже новое, следовательно выходной сигнал Z будет соответствовать не предыдущему состоянию, а уже новому, следовательно вначале надо получить z а затем сменить состояние.

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

Сам же переход из состояния в состояние произойдет при появлении с=1.

`Временная диаграмма.

К моменту t₀ автомат должен быть установлен в начальное состояние S₀, т.е. q₀ = 0, q₁ = 1. Функции возбуждения со штрихом равны 0, т.к. С= 0. Выходной сигнал Z = 0.

Ничего не меняется до момента t₁, т.к. никакие сигналы (входные) не изменены. Появление С = 1 в момент t₁ приводит (стрелки) и формирует S₀¹ = 1, который устанавливает триггер q₀ в 1, а это в свою очередь формирует R₁ = 1, которое должно появиться после момента t₂.

В момент t₂ срабатывает S₀¹, после t₂ автомат находится в состоянии S₁, т.к. q₀ и q₁ = 1.

До q₀ ничего не происходит, т.к. смена q₀ на его значение не влияет. От t₃ до t₄ новый переход автомата, который окажется в состоянии S₂ при этом новое значение ^q₁ = 1, сформирует Z = 1, на интервале t_5, t₆ автомат вернется в состояние S₀.

Длительность сигнала С = 0 должно быть достаточно для формирования новых функций возбуждения на входах элементов «и», а также для формирования выходного сигнала «Z».

В данной схеме очень жесткое требование на синхросигнал, особенно при С =1.

Это может привести к нереализованности такого генератора синхросигналов.

Этап минимизации автомата при абстрактном синтезе.

Минимизация полностью определенного автомата.

Постановка задачи:

Задан полностью определенный автомат A имеющий e – число состояний, необходимо построить эквивалентный ему автомат «A» c числом состояний «e¹», причем e¹ <= e.

Минимизация состоит в поиске эквивалентных состояний в автомате A и их объединений.

Два состояния S¹ и S¹¹ называются эквивалентными, если любую входную последовательность автомат перерабатывает в одинаковые выходные последовательности, в независимости от того какой из двух состояний S¹ или S¹¹ выбраны в качестве начального.(S¹≡S¹¹).

Отношение эквивалентности, определенное на множестве состояний обладает свойствами:

1. Рефлексивность

S¹≡S¹

1. Симметричность

S¹≡S¹¹ => S¹¹≡S¹

1. Транзитивность

S¹≡S¹¹

S¹≡S¹¹¹

S¹¹≡S¹¹¹

Отношение эквивалентности разбивает множество C_i на классы эквивалентности

S=C₁ÚC₂ ÚC₃Ú…ÚC_q

C_i <= S

Пересечение классов эквивалентности представляет собой пустое множество.

Пример:

Состояние Si ≡ Sk – не очевидно

Эквивалентный автомат будет:

Существует два необходимых условия эквивалентности состояний:

1. Два состояния называются эквивалентными, если в этих состояниях вырабатываются одинаковые выходные символы (Мура) или при переходе из этих под воздействием любых одинаковых входных символов вырабатываются одинаковые выходные символы (Миля).

ψ¹(S¹) = ψ¹¹(S¹¹) (Мура)

ψ¹(S¹,P_k) = ψ¹¹(S¹¹,P_k) (Миля).

1. Два состояния являются эквивалентными, если под воздействием любого одинакового входного символа переход осуществляется в эквивалентное состояние, т.е.

S_i≡S_j

ψ¹(S¹,P_k) = S_i

ψ¹¹(S¹¹,P_k) = S_j

Алгоритмы минимизации на основе треугольной матрицы.

Изначально нам задан автомат, имеющий L состояний.

1. Строится треугольная матрица без диагональных элементов, столбцы которого нумеруются символами состояний с 1 по L-1, а строки со второй по L.
2. Клетки матрицы с координатами i,j представляют отношение эквивалентностей между состояниями S_i, S_j и заполняются следующим образом:

a) если для S_i, S_j невыполнимо условие 1 эквивалентности, то в клетку ставят «X»

b) если выполняется заведомо два условия для S_i, S_j (переходы осуществляются в одно и то же состояние для второго условия) – клетка оставляется пустой либо ставится «▼»

c) если для пары состояний S_i, S_j выполняется 1 условие, но не известно выполняется ли второе, т.к. переходы осуществляется в разное состояние, то в клетку записывают номера состояний от эквивалентности которых зависит эквивалентность данных.

1. Заполненная треугольная матрица, последовательно просматривающаяся по клеткам, в которых записаны состояния и если известно, что вписанная в клетку состояние не эквивалентны, то в этой клетки ставят «X».

Рассмотрение матрицы осуществляется до тех пор пока не перестанут появляться новые пары неэквивалентных состояний.

1. Выписываются все пары эквивалентных состояний (там где не стоит X) и строят из них классы эквивалентностей. Каждому классу эквивалентности ставится в соответствие символ нового состояния и переписывают таблицу переходов входов и выходов путем объединения одинаковых строк.

Пример минимизации:

P = {a,b,c}

W = {1,2}

S = {1,2,3,4,5,6,7,8}

Si / Pk	a	b	c
	4/1	2/2	5/1
	5/2	1/1	4/2
	3/2	5/1	4/2
	5/1	8/2	4/2
	7/1	2/2	1/1
	1/1	3/2	4/2
	5/1	3/2	7/2
	3/2	5/1	6/2

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

1 ≡ 5

3 ≡ 8

4 ≡ 6

4 ≡ 7

6 ≡ 7

Классы эквивалентности:

C₁ = {1, 5}

C₂ = {2}

C₃ = {3, 8}

C₄ = {4, 6, 7}

Получили 4 класса эквивалентности.

Далее перепишем:

C₁ – 1

C₂ – 2

C₃ - 3

C₄ – 4

Получим:

Si / Pk	a	b	c
	4/1	2/2	5/1
	1/2	1/1	4/2
	3/2	1/1	4/2
	1/1	3/2	4/2
	4/1	2/2	1/1
	1/1	3/2	4/2
	1/1	3/2	4/2
	3/2	1/1	4/2

Объединяем строчки: получим

Si / Pk	a	b	c
	4/1	2/2	5/1
	1/2	1/1	4/2
	3/2	1/1	4/2
	1/1	3/2	4/2

Минимизация числа состояний частичного автомата.

Два частичных автомата называются совместимыми, если

1. Они имеют одинаковый набор или множество допустимых входных слов.
2. Любое допустимое входное слово оба автомата перерабатывают в непротиворечие выходные слова, при условии что оба автомата находились в начальном состоянии.

Два выходных слова называется непротиворечивыми, если все символы, которые определены в выходном слове (первом) совпадает со всеми символами, которые определяются в выходном втором слове.

Пример:

Следовательно должны быть непротиворечивые выходные слова.

Два состояния S_i, S_j частичного автомата называются совместимыми, если любое допустимое входное слово автоматом перерабатывается в непротиворечивое выходное слово в независимости от того какое из этих двух состояний было взято в качестве начального.

Отношение совместимости обладает следующими свойствами:

1. Рефлективностью S_i ∞ S_i – совместимо само с собой
2. Симметричностью S_i ∞ S_j à S_j ∞ S_i
3. Нетранзитивно S_i¹ ∞ S_i

S_i¹¹ ∞ S_i но не следует, что S_i¹ ∞ S_i¹¹

Отношение совместимости разбивает множество состояний на классы совместимости Q₁ v Q₂ v … v Q_k, их объединение представляет собой алфавит состояний. Q_i ∩ Q_j ≠ 0, т.е. пересечение двух классов совместимости не обязательно является пустым множеством, а следовательно одно и тоже состояние может оказаться нескольких классах совместимости. В общем случае число классов совместимости больше чем аналогичное число классов эквивалентности, но может и превышать число исходных состояний. Цель минимизации – уменьшить число состояний, а следовательно уменьшить число классов совместимости. Простым классом совместимости называют множество, содержащее попарно совместимые состояния. Максимальным классом совместимости называют простой класс, который не является подмножеством ни одного из наборов других классов. Условие совместимости состояний автомата:

1) Для любого входного символа функция выхода, если она определена для двух состояний должно совпадать (автомат Мили), либо для данных состояний должна совпадать (автомат Мура) ψ (S¹) = ψ (S¹¹) – Мура, ψ (S¹, P_k) = ψ (S¹¹, P_k) – Мили

2) Для любого входного символа P_k, если функция перехода для двух состояний определена, то переход осуществляется в одно и то же состояние, либо в совместимое.

a)

b)

во втором случае в отличие от первого S¹ не совместимо с S¹¹

Минимизация частичного автомата.

Она заключается в уменьшении числа состояний путем объединения совместимых состояний.

Алгоритм минимизации:

1) Строится матрица и ищутся пары совместных состояний

2) Находим max классы совместимости, например, с помощью дерева, которое разбивает искомый алфавит состояний на основе признака несовместимости пар состояний

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

4) Проверяется полнота путем построения таблицы покрытий

5) Проверяется замкнутость путем нахождения подмножества состояний следующих за исходными классами совместимости. Это выполняется на пример с помощью дерева переходов. Если условие замкнутости не выполняется, то можно сузить классы совместимости путем удаления состояний, которые вызвали незамкнутость, при этом не должна нарушиться полнота, затем выбрать новый минимальный класс совместимости и выполнить все проверки и затем расширить число классов совместимости, добавив в них подмножество, которое получилось путем следования из исходных классов и вызвано незамкнутостью. И в первом и во втором случаях необходимо заново проверять замкнутость.

6) Каждому классу совместимости присваивается новый символ состояния.

7) Переписывается таблица переходов, причем новое состояние записывается так, чтобы не нарушилась замкнутость и склеиваются совместимые строки.

Пример минимизации частичного автомата:

P = {a, b, c, d, e}

S = {1, 2, 3, 4, 5, 6, 7}

W = {00, 01, 10, 11}

Si / Pk	a	b	c	d	e
	1/00	5/*1	---	---	6/**
	5/*0	4/0*	---	---	---
	4/11	---	---	---	6/00
	6/*1	6/00	---	2/0*	---
	---	7/0*	---	4/*0	---
	---	---	6/*0	---	2/10
	---	2/**	1/00	---	---

Получили следующие пары совместимости:

1 ≡ 6

1 ≡ 7

2 ≡ 5

2 ≡ 6

3 ≡ 4

3 ≡ 5

3 ≡ 7

4 ≡ 6

4 ≡ 7

5 ≡ 6

Строим дерево классов:

C₁ = {1, 6}

C₂ = {1, 7}

C₃ = {2, 5, 6}

C₄ = {3, 4, 7}

C₅ = {3, 5}

C₆ = {3, 6}

Выбираем множество классов C₁, C₃, C₄, C₆

В зависимости от того какие новые состояния мы припишем старому мы получаем разные автоматы, но все они будут иметь одинаковое количество состояний.

Абстрактный этап синтеза конечного автомат. (неканонический метод).

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

Алгоритм перехода от граф схемы микропрограммы к автомату Мура.

1. Начальная и конечная вершины помечаются начальным состоянием.
2. Все операторные вершины граф-схемы помечаются индивидуальными символами состояний автомата, в независимости от микропрограмм находящихся в этих вершинах.
3. Строится n+1 вершина графа(n – число операторных вершин в алгоритме), каждая вершина помечается символом состояния и микрокомандой из операторной вершины в качестве выходного сигнала.
4. Вершину S_i соединяем с S_j дугой на которой в качестве входного сигнала приводят код логического условия, которые допускают переход из оператора помеченного S_i в оператор помеченный S_j.

Пример:

P = {P₀, P₁, P₂, P₃}

S = {S₀, S₁, S₂, S₃, S₄}

W = { W₀, W₁, W₂, W₃}

Автомат полностью определен, следовательно перейдем к автомату Мили:

Учет взаимодействия проекционного и управляющего автоматов.

Алгоритм получения.

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

С другой стороны наличие прочерков в таблице переходов частичного автомата может позволить получить более компактный автомат после минимизации.

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

Для построения частичного автомата необходимо получить наборы X возможных в каждом состоянии. Для этого необходимо знать:

1) Множество наборов X, которые может получить автомат на вход, когда он находится в начальном состоянии S₀ – будем обозначать U₀

2) Как каждая микрооперация влияет на значение логических условий.

Алгоритм получения частичного автомата.

1. Строится дерево переходов и для каждого состояния определяется набор X. Построение дерева заканчивается, когда автомат попадает в состояние уже просмотренное и множество логических условий более не пополняется.
2. Из таблицы переходов полностью определенного автомата исключают переходы по несуществуемым наборам логических условий.

Пример:

Si / XiXj
S0	S1 / 010	S1 / 010	S1 / 010	S1 / 010
S1	S1 / 010	S4 / 001	S3 / 011	S0 / 001
S3	S0 / 100	S0 / 100	S0 / 100	S0 / 100
S4	S1 / 010	S0 / 100	S1 / 010	S0 / 100

Предположим U₀ = {1, 1}

Yi / Xi	X1	X2
Y0
Y1	⌐	Z
Y2

Строим дерево переходов:

Если вырабатывается микрокоманда из двух микроопераций, то возможны следующие результаты X_i:

1) Если на X_i действует только одна из двух микроопераций, то новое значение X_i соответствует этому единственному воздействию.

2) Если на X_i действует обе микрооперации, то

a)Эти микрооперации приводят к одному и тому же значению, то новому значению X_i приводится в соответствии с воздействием этих микроопераций.

b) Если микрооперации могут привести к разным X_i то X_i приписывается значение Z.

Множество входных значений.

U₀ = {11, 00}

U₁ = {ZZ}

U₃ = {0Z}

U₄ = {01}

Далее удаляем несуществующие входные сигналы из таблицы переходов:

Si / XiXj
S0	S1 / 010	---	---	S1 / 010
S1	S1 / 010	S4 / 001	S3 / 011	S0 / 001
S3	S0 / 100	S0 / 100	---	---
S4	---	S0 / 100	---	---

S₃ совместимо с S₄

Si / XiXj
S0	S1 / 010	---	---	S1 / 010
S1	S1 / 010	S4 / 001	S3 / 011	S0 / 001
S3	S0 / 100	S0 / 100	---	---

Кодирование состояний синхронного автомата.

Кодирование состояний автомата может изменять различные параметры окончательной схемы, такие как:

a) затраты

b) быстродействие

c) потребляемая мощность

d) взаимные наводки

Существует масса вариантов кодирования состояний от L_min = log₂k

L_max = k

где k – число состояний

L – число разрядов

Рассмотрим три известных способа кодирования, каждый из которых позволяет улучшить тот или иной параметр

1 способ – способ учитывающий соседство состояний.

2 способ – способ минимизирующий число переключений при переходах.

3 способ – универсальный способ кодирования.

Кодирование соседними кодами.

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

S¹ и S¹¹ – соседи первого рода

S_i и S_j – соседи второго рода (не обязательно ⌐x, главное чтобы сигнал был одинаковым)

Степень соседства S¹ и S¹¹ =1

Соседи первого и второго рода кодируют соседними кодами. Метод эвристический и не обеспечивает гарантии минимума системы.

Пример:

Пусть задан D – триггер в качестве элемента и 2 состояния, которые являются соседями первого рода S¹ и S¹¹

S¹ - закодировали (q₁q₂q₃…q_n-1⌐q_n) – 11…10

S¹¹ - закодировали (⌐q₁q₂q₃…q_n-1⌐q_n) – 01…10

Предположим, что под воздействием входного сигнала x, который вызывает переход в общее состояние некоторый триггер должен перейти из 0 в 1.

При кодировании соседей первого рода соседними кодами происходит склеивание конъюнкции в функции возбуждения триггеров.

Пример:

Кодируем соседей второго рода.

Пусть в качестве элемента памяти используется D триггер

0à1 есть для D₃

D₃ = ⌐q₁⌐q₂⌐q₃x₁ v q₁⌐q₂⌐q₃x₁ v q₁⌐q₂⌐q₃⌐x_{1 =} ⌐q₂⌐q₃x₁ v q₁⌐q₂⌐q₃⌐x₁ – выражение упрощается благодаря соседним кодам S¹ и S¹¹

D₂ = ⌐q₁⌐q₂⌐q₃⌐x₁ v q₁⌐q₂⌐q₃⌐x₁ = ⌐q₂⌐q₃⌐x₁

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

Задан автомат, построим инверсную таблицу переходов:

		Pi /Si
---	S2, S4	S0
S0	S3	S1
S3	S0, S1	S2
S1	---	S3
S0, S1	---	S4

т.е. соседями первого рода будут: S_2, S₄ (2 – степень родства)

S_0, S₁ (1) – соседи второго рода.

Минимальное число разрядов при кодировании = 3, точнее 5 состояний, следовательно карты Карно на 8 клеток.

				---------	q2
			---------		q1
		S2	S4	S0	S1
	|				S3
	q3

Si	q3	q2	q1
S0
S1
S2
S3
S4

Минимизация числа переключений элементов памяти.

Расстояние между кодами по Хеминингу – это число разрядов, в которых эти коды различаются между собой.

Алгоритм кодирования:

1) Определяем множество пар состояний, между которыми существует переход M.

2) Выбирается любая пара состояний, между которыми есть переход, один из них кодируется всеми нулями, а другой нулями и одной единицей.(00…01)

3) Из множества M удаляются пары состояний, которые уже закодированы M\(S_i S_j), если станет равным 0, то процесс завершается.

4) Берем любую пару в которой одно состояние уже закодировано, а другое нет (*, S_q) S_q - незакодированное состояние, * - состояние закодировано. Далее кодируем это состояние.

5) Выбираем множество пар из M куда входит S_q (M_q)

6) Из M_q выбираем все закодированные состояния (B_q)

7) Строим множество кодов, имеющих расстояние d, с каждым кодом из состояния B_q

8) Для каждого кода из всех множеств C^d_q определяется сумма расстояний по Хеммингу с каждым кодом из B_q Выбирается код, имеющий минимальную сумму и этот код приписывается C_q Деле возврат к пункту 3.

Пример:

1) Пары состояний M = {(1,2),(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

2) {1,2} => S₁ = 000 S₂ = 001

3) M = {(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

4) {2,4}

q=4

5) M_q = {(2,4),(3,4),(4,5)}

6) B_q = {2}

7) C¹₄ = {101,011}

8) 101 + 001 = 100 d =1

011 + 001 = 010 d =1

S₄ = 101

3) M = {(2,3),(2,4),(2,5),(3,4),(4,5),(1,5)}

4) {2,5} q=5

5) M_q = {(2,5),(1,5),(4,5)}

6) B_q = {2,4,1}

7) C¹₅ = {011}

C¹₅ = {(111),(100)}

C¹₅ = {(100),(010)}

8) 011 + 001 = 010

011 + 101 = 110

011 + 000 = 110

111 + 001 = 110

111 + 101 = 010

111 + 000 = 111

100 + 001 = 101

100 + 101 = 001

100 + 000 = 100

010 + 001 = 011

010 + 101 = 111

010 + 000 = 010

S₅ = 100

3) M = {(2,3,(3,4) }

4) {2,3} q=3

5) M_q = {(2,3),(3,4)}

6) B_q = {2,4}

7) C¹₅ = {011}

C¹₅ = {(111)}

C¹₅ = {(100),(010)}

8) 011 + 001 = 010

011 + 101 = 110

111 + 001 = 110

111 + 101 = 010

S₃ = 011

3) M = {0 } – конец цикла.

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

Универсальный способ кодирования (для синхронного автомата).

При данном способе кодирования используется унитарный код (1 из N), который содержит 1 единицу, а остальные 0. В этом случае число разрядов совпадает с числом состояний автомата. В данном способе кодирования число разрядов максимально возможно, большее число разрядов бессмыслимо, следовательно это приводит к большему числу триггеров. С другой стороны может значительно упроститься комбинационный узел формирующий функции возбуждения и его функционирование можно описать прямо по графу без минимизации булевых функций.

Для D триггера:

D₂ = q₁⌐q₂q₃⌐x₁ – любой код

D₂ = q₁⌐x₁ - унитарный код

Для унитарного кода опущены ⌐q₂⌐q₃, так как если q₁ = 1, то это однозначно подразумевает q₂ = q₃ = 0. Более того q₁ = 1 невозможно ни для одного из оставшихся состояний автомата.

Пример:

0à1 0à1

D₁ = q₅x v q₃x

5à1 3à1

0à1

D₂ = q₁⌐x

1à2

0à1 0à1 0à1

D₃ = q₁x v q₂x v q₄x

1à3 2à3 4à3

0à1 1à1

D₄ = q₂⌐x v q₄⌐x

2à4 2à4

0à1

D₅ = q₃⌐x

3à5

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

R = 1, когда 1à0 обязательно

R = 1, когда 0à0 можно

S = 1, когда 0à1 обязательно

S = 1, когда 1à1 возможно

Для RS триггера сначала записываются функции обязательные, а там где возможно чтобы функция была равна 1 дописывают лишь в случае упрощения.

RS

*0

0 à 0

0 à 1

1 à 0

0*

1 à 1

1à0 1à0

R₁ = q₁⌐X v q₁X = q₁

1à2 1à3

0à1 0à1

S₁ = q₅X v q₃X = X(q₁ v q₃)

5à1 3à1

В функции R_1, S₁ входит обязательная конъюнкция, обеспечивающая переход 1à0 для R₁ и 0à1 для S₁. В R₁ можно добавить конъюнкции переходов из 0à0, т.к. при этом R=* и может быть доопределено до 1. Упростить R=q - можно добавить только ⌐q₁, однако при унитарном кодировании инверсное значение ⌐q не используется, а следовательно переходы 0à0 добавленные в R₁ только усложнят функцию.

Аналогично для S₁ можно добавить конъюнкции соответствующие переходу 1à1, такой переход возможен, только если присутствует петля вокруг S₁, в примере ее нет, значит получим окончательное значение R₁ S_1.

1à0 1à0

R₂ = q₂⌐X v q₂X = q₂

2à4 2à3

0à1

S₂ = q₁⌐X

1à2

1à0

R₃ = q₃

3à1

3à5

0à1 0à1 0à1

S₃ = q₁X v q₂X v q₄X = X(q_{1 v} q₂ v q₄)

1à3 2à3 4à3

1à0

R₄ = q₄X

4à3

0à1 1à1

S₄ = q₂⌐X v q_4⌐X = q₂

2à4 4à4

R₅ = q₅X

S₅ = q3⌐X

Автомат с дешифратором.

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

Каждому состоянию соответствует два кода с минимальным и максимальным числом разрядов, недостаток схемы – дополнительные затраты виде дешифратора.

Два кода, предписанных одному состоянию, связаны между собой функцией дешифратора.

При кодировании состояний предполагаем наличие дешифратора.

В данном случае 2à4 (2 входа, 4 выхода)

Каждому состоянию соответствует два входа.

При записи функции возбуждения в данном случае аргументами являются Y_i и X_i, а переходы триггера 0à0; 0à1; 1à0; 1à1 рассматриваются относительно q_i/

Рассмотрим D и RS триггера:

В качестве элемента памяти используется 2 D триггера.

На D подаем 1 при переходе 0à1; 1à1

0à1 0à1 1à1 0à1 1à1

D₁ = Y0⌐X v Y₀X v Y₁⌐X v Y₂⌐X v Y₃⌐X = Y₀ v ⌐X (Y_{1 v} Y₂ v Y₃)

1à2 1à4 2à4 3à2 4à4

0à1 0à1 1à1 1à1

D₂ = Y₁X v Y₁⌐X v Y₃X v Y₃⌐X = Y₁ v Y₃

2à3 2à4 4à3 4à4

Далее RS триггер (R₁ – сброс 1 разряда)

1à0 1à0 0à0

R₁ = Y₁X v Y₃X v Y₂X

2à3 4à3 3à1

0à1 0à1 1à1 1à1 0à1

S₁ = Y0⌐X v Y₂⌐X v Y1⌐X v Y₃⌐X v Y₀X = ⌐X (Y₀ v Y₂) v Y₀X

1à2 3à2 2à4 4à4 1à4

1à0 1à0 0à0

R₂ = Y₂X v Y₂⌐X v Y0⌐X = Y₂

3à1 3à2 1à2

0à1 0à1 0à1 1à1 1à1

S₂ = Y0X v Y₁⌐X v Y1X v Y₃X v Y3⌐X = Y₀X v Y₁

1à4 2à4 2à3 4à3 4à4

Асинхронные автоматы.

Ранее рассматривались:

т.е.раньше неявно присутствовал синхроимпульс.

Наличие синхроимпульса позволяло осуществлять переход, при отсутствии его автомат остается в текущем состоянии.

По существу синхроимпульс является дополнительным входным сигналом. Входные сигналы можно разделить в зависимости от наличия синхроимпульса:

1. Синхронизируемое

С – синхроимпульс

Пример:

Разновидностью данного сигнала является импульсный сигнал

1. Потенциальный сигнал

Новое входное значение появляется после изменений предыдущего значения, т.е. длительности 0 и 1 могут быть разными.

Асинхронным автоматом называется автомат, изменение состояния которого могут происходить в произвольные моменты времени, и эти моменты времени определяются сменой входного сигнала.

Тип автомата определяется типом входного сигнала.

Если входной сигнал потенциален, то автомат асинхронный, в противном случае – синхронный. При асинхронной реализации автомата для обеспечения устойчивой его работы все его состояния должны быть устойчивыми (аналогично петли СИ в синхронном автомате).

Состояние S_i называется устойчивым, если при переходе в это состояние под воздействием входного сигнала P_k автомат остается в этом состоянии до тех пор, пока входной сигнал не станет отличаться от P_k.

Автомат будет асинхронным, если уже на абстрактном уровне все его состояния - устойчивы.

Пример асинхронного автомата:

Составим таблицу переходов:

W	S/X1X2
	S1	S1	S1	S3	S2
	S2	S1	S2	S2	S2
	S3	S1	S2	S3	S2

0 – устойчивое состояние (петля)

Проверка устойчивости:

S₁ à S₃ (двигаемся по строке, а потом по столбцу)

Для проверки является ли автомат асинхронным (по таблице переходов) вначале выделяем переходы соответствующие петлям вокруг состояний.

В каждой строке с номером I обводим состояние S_i, затем проверяется устойчивость переходов из каждого состояния.

Например переход S₁ à S₃ проверяется следующим образом:

1) Смотрится в строке с текущем состоянием под воздействием входного сигнала в какое состояние он должен перейти (горизонтальное движение стрелки)

2) Затем в столбце соответствующим данному сигналу ищется состояние, в которое переходит автомат, но отмеченное кружком (движение вертикальное).

3) Если все переходы попадают в отмеченное состояние, то все состояния устойчивы и автомат может быть асинхронным.

Этапы синтеза асинхронного автомата.

Этап синтеза относится к асинхронному автомату также используется и в асинхронном, однако есть и отличие.

На этапе абстрактного синтеза нужно добавить следующие действия:

1) Осуществить перекодировку входных и выходных символов для обеспечения распознаваемости соседних одинаковых сигналов.

2) На этапе переходе от алфавитного оператора и автомату необходимо обеспечить все состояния автомата устойчивости.

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

Пример перекодирования входных и выходных символов:

P = {a,b} W = {a,b,c}

Вид входного сигнала:

P¹ = {a, a¹, b, b¹} W = {a, b, c, c¹}

На исходной временной диаграмме до перекодирования не различимы входные сигналы между I и II интервалом и III и IV. Выходной сигнал не различим между II и III интервалами.

На структурном этапе синтеза отличие следующие:

1) Иной тип элемента памяти, который используется в автомате.

2) Отличие в способе кодирования состояний автомата.

3) Иной метод синтеза комбинационного узла.

1. Кодирование состояний асинхронного автомата.

Цель кодирования – обеспечить устойчивую работу асинхронного автомата, затем устранение так называемого явления состязания памяти.

Состязание элементов памяти

a) τ₁ = τ₂ à 01à10

b) τ₁ > τ₂ à 01à00à10

c) τ₁ < τ₂ à 01à11à10

Это явление называется состязанием элементов памяти.

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

Если в примере q₁ и q₂ имеют задержки τ₁ и τ₂, то между ними могут быть соотношение, либо a либо b либо c, в этом случае переход из S_i в S_j будет иметь варианты a,b,c. В случае b и c появляются дополнительные состояния 00 и 11, именно такие переходы через дополнительные состояния называются состязанием элементов памяти.

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

Если же состязание приводит к переходу в незапланированное неустойчивое состояние, а потом и к переходу в верное устойчивое состояние, то такое состояние является некритическим.

Рассмотрим пример:

Закодируем в предыдущем графе 3 состояния следующим образом:

S/q	q1	q1
S1
S2
S3

тогда автомат будет:

	Pi / Si

Рассмотрим 00à11

q₁q₂

(τ₁ τ₂)

1. Пусть τ₁ > τ₂

00à01- - >11

Состязание критическое, из-за задержки автомат оказывается в состоянии 01, для которого входной сигнал 10 является устойчивым или приводит к устойчивости, и переходит в состояние 11 не произойдет.

1. τ₁ < τ₂

10 10

00 à 10 à 11

Состязание не критическое.

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

2. Способы кодирования асинхронного автомата.

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

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

Существует 2 способа кодирования:

1) Соседними кодами

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

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

2) Кодирование унитарным кодом

При данном способе кодирования состояние S_i кодируется кодом, в котором устанавливается 1 в I разряде.

Для отсутствия состязаний элементов памяти на каждом переходе из S_i в S_j устанавливают транзитное состояние и кодируют его кодом, в котором 2 единицы в i и j разрядах.

Данный способ кодирования позволяет записать функции возбуждения прямо по графу, причем они будут не сложными.

Закодируем состояние из примера:

S₁ = 100

S₂ = 010

S₃ = 001

D триггер (там где установка в 1)

D₁ = ⌐X₁⌐X₂q₃ v ⌐X₁⌐X₂q₂ v q₁⌐q2⌐q3

S₃à S1/₃ S₂à S1/₂ S₁à S₁

S_1/3à S₁ S₁₂à S₁ S₁à S1/₂

S₁à S1/₃

D₂ = X₁X₂q₁ v ⌐X₁X₂q₃ v X₁X₂q₃ v q₁q₂⌐q₃

S₁à S1/₂ X₂q₃ X₂q₃ S₂àS₂

S1/₂à S₂ S₃à S₂₃ S₃à S₂₃ S₂à S₁₂

S₂₃à S₂ S₂₃à S₂

D₃ = X1⌐X2q1 v ⌐q₁⌐q₂q₃

S₁à S1/₃ S₃à S₃

S₁₃à S₃

Нарисуем временную диаграмму:

Предположим, что автомат находится в состоянии S₁, q₁,q₂,q₃ = 100, а входные сигналы X₁ X₂ = 01, функции возбуждения триггера дают следующие значения D₁ = 1, D₂ = 0, D₃ = 0, что подтверждает состояние 100, до момента t₀ схема устойчива.

Схема X₁ в момент t₀ изменяет D₂, которое устанавливает к моменту t₁ и вызывает изменение q₂ к моменту времени t₂; на интервале t₂ и t₃ получаем состояние 110, т.е. S₁₂. Смена q₂ сбрасывает D₁, которое в свою очередь переводит q₁ в ноль (момент t₄), после t₄ автомат находится в состоянии 010, т.е. в состоянии S₂.

При переходе из S₁ в S₂ последовательно меняется вначале q₂ и затем q₁. Это обеспечивало отсутствие состязаний элементов памяти, с другой стороны затянуло переход из S₁ в S₂, т.е. снизило быстродействие.

Запишем функции возбуждения для RS триггера.

В отличие от D триггера RS должны меняться, когда он сбрасывается и переходит в 1.

R = 1 – сброс

1à 0

S = 1 – установка

0 à 1

R = 1

0 à 0

S = 1

1 à 1

S₁ = q₃⌐X₁⌐X₂ v q₂⌐X₁⌐X₂

S₃à S1/₃(0à1) S₂àS1/₂ (0à1)

S1/₃à S₁(1à1) S1/₂à S₁(1à1)

R₁ = q₂X₁X₂ v q₃X₁⌐X₂

S1/₂à S₂(1à0) S1/₃àS₃ (1à0)

S₂à S₂ (0à0) S₂à S₃(0à0)

S₂ = q₁X₁X₂ v q₃X₂

S₁à S1/₂(0à1) S₃àS2/₃ (0à1)

S1/₂à S₂(1à1) S2/₃à S₂(1à1)

R₂ = q₂⌐X₁⌐X₂

S1/₂à S₁(1à0)

S₁à S₁ (0à0)

S₃ = q₁X₁⌐X₂ = q₁⌐ q₂⌐ q₃X₁⌐X₂ v q₁⌐q₂q₃X₁⌐X₂

S₁à S1/₃(0à1) (0à1)

S1/₃à S₃(1à1)

Два разряда q₁q₂ 10 определяют 2 состояния S₁ и S₁₃, один разряд q₁ = 1 определяет 3 состояния S₁,S₁₃,S₁₂, т.е. состояние S₁ и транзитное от него. В записи для S₃ присутствует также X₁, ⌐X₂ , что однозначно удаляет состояние S₁₂ следовательно, вместо q₁⌐q₂, можно записать только q₁ и выражение q₁X₁⌐X₂ будет определять только 2 состояния S₁ S₁₃.

R₃ = q₃⌐X₁⌐X₂ v q₃X₂

S₃à S₁(1à0) S2/₃àS₂(1à0)

S₁à S₁(0à0) S₂ àS₂(0à0)

Рассмотрим временную диаграмму S₁àS₂

q1	q2	q3	X1	X2

Следовательно S₃ = 0, R₃ = 0

Классификация по логическому функционированию делят на RS, JK, D, T.

По принципу записи и считыванию информации.

Триггеры делят:

a) В зависимости от наличия или отсутствия синхросигнала (синхронные и асинхронные)

b) В зависимости от времени записи новой информации и ее появление на выходе делят на триггеры с задержкой(с разделением процессов записи и считывания) и триггеры без задержки (без разделения) процессов записи и считывания.

В триггерах с задержкой новое значение появляется на выходе по окончанию сигнала, который произвел запись этого нового значения.

На примере RS триггера:

1. Асинхронный

a) без задержки

b) с задержкой

1. Синхронный

a) без задержки

b) с задержкой

Реализация асинхронного RS триггера на логических элементах.

В качестве элемента памяти воспользуемся асинхронным D триггером.

Приведем таблицу переходов D триггера:

0 à 0 т.е. значение D пишется над стрелкой.

0 à 1

1 à 0

1 à 1

Следовательно

Это абстрактный закодированный автомат, представленный RS триггер.

Код состояния совпадает со значением выходного сигнала Q.

RS/q
			--
			--

Нарисуем карты Карно

			------------R
		------------S
			--
Q -			--

тогда Q = S v ⌐RQ = ⌐⌐(S v ⌐RQ) = ⌐(⌐S * ⌐(RQ))

или

			------------R
		------------S
			--
Q -			--

тогда Q = (Q v S) ⌐R = ⌐(⌐(Q v S) v R)

Подавая различные разрешенные комбинации на входы триггера, убеждаемся что второй выход является ⌐Q. На запрещенных комбинациях на прямом и инверсных выходах мы получаем одно и тоже, либо 0, либо 1 все зависит от использованной элементной базы.

Рассмотрим 1 триггер (с инверсными входами).

Временная диаграмма:

T ⌐S à Q = τ (задержка)

T ⌐S à ⌐Q = 2 τ

При появлении ⌐S = 0, сигнал поступает на верхний элемент и на триггер и устанавливает Q в 1 и лишь затем ⌐Q становится равным 0.

Аналогично при появлении ⌐R = 0 вначале устанавливается ⌐Q в 1, а затем Q в 0.

Рассмотрим второй триггер:

T (S à ⌐Q) = T (R à Q) = τ

T (S à Q) = T (R à ⌐Q) = 2 τ

Установочные входы в триггерах.

Функционально вход R и R₀, а также S и S₀ аналогичны, однако в схемах на RS входы заводят функции возбуждения а R₀ S₀ выводят наружу в качестве установочных, на которые перед началом функционирования автомата полают сигнал, устанавливающий автомат в состояние S₀.

Синхронные элементы памяти.

Синхронизация позволяет исключить влияние временных смещений входных сигналов триггера и позволяет обеспечить одновременность изменений выходных сигналов элементов памяти.

Требования на синхросигнал:

Предположим, что триггер Q находится в 0 и подается J = K = 1.

Триггер должен перейти в 1, однако если J появится раньше чем K, при отсутствии синхросигнала, он установит триггер в 1.

Появление через ∆ сигнала K=1 установит 11 на входах и триггер сбросится.

Наличие синхросигнала позволяет триггеру реагировать только в момент синхросигнала, когда J=K=1 и в этом случае триггер перейдет 0à1 один раз.

Так как синхросигнал поступает на все триггеры одновременно, то все они реагируют и выдают сигнал на выходе одновременно.

Требования, предъявляемые к синхросигналу.

1. Синхросигнал должен появиться после входного сигнала
2. Синхросигнал должен заканчиваться раньше синхросигнала:

Синтез синхронного RS триггера.

В качестве основы используем асинхронные RS триггеры:

Так как данный вид триггера получен на элементах «или - не», то и комбинационный узел реализуем на тех же самых элементах.

CD/Q

получим:

CD/Q
	*0	*0		*0
	0*	0*	0*

			------------С
		------------D
	*	*		*
Q -

			------------С
		------------D
Q -	*	*	*

R = C⌐D = ⌐(⌐C v D)

S = CD v ⌐(⌐C v ⌐D)

Условное обозначение:

Временная диаграмма:

В момент времени t₀ сигнал R₀ непосредственно воздействует через установочные входы на RS триггер.

В момент t₁ появляется сигнал R₁ , однако триггер был в нуле и следовательно изменений не произошло.

В момент t₂ появляется сигнал S, который устанавливает ⌐Q в 0, а затем Q в 1.

Повторный сигнал ⌐S в t₃ лишь подтверждает Q = 1, а ⌐Q = 0.

В момент времени t₄ появившийся сигнал R сбрасывает триггер.

t (⌐С àQ₌₁) = 3 τ

t (⌐С àQ₌₀) = 2 τ

max (t (⌐С àQ)) = 3 τ

Синтез триггера с задержкой.Реализация асинхронного T триггера.

Появление сигнала T = 1 записывает новое значение триггера Q = 1, однако на выходе это значение появляется лишь после исчезновения сигнала T = 1.

Это можно организовать, используя два разряда, один из которых показывает значение внутри триггера (q₁), а второй (q₂) совпадает с Q.

q₁ q₂

0 0

0 1

1 0

1 1

тогда q₁ q₂ - 4 комбинации

q₁ ≠ q₂ – в моменты времени, когда происходит запись нового значения в триггер

Данный триггер представим виде автомата Мура, который имеет 4 вершины:

Это абстрактный автомат.

Составим таблицу переходов:

q1q2 /T

Перейдем к структурному автомату:

⌐R⌐S

*1

0 à 0

0 à 1

1 à 0

1*

1 à 1

Строим таблицу функции возбуждения:

q1q2 /T
	*1, *1	10, *1
	*1, 01	*1, 1*
	1*, 1*	01, 1*
	1*, 10	1*, *1

Q = q₂, поэтому в таблице не приводят значение выходного сигнала.

Строим 4 карты Карно:

⌐R1			---T
		*
	-----	*	*
-----
q1	q2

⌐R2			---T
		*	*
	-----
-----
		*
q1	q2

⌐S1			---T
	-----
-----	*
	*	*
q1	q2

⌐S2			---T
	-----		*
-----	*	*
q1	q2

⌐R₁ = (⌐q₂ v ⌐T) = ⌐(q₂T)

⌐S₁ = (q₂ v ⌐T) = ⌐(⌐q₂T)

⌐R₂ = (q₁ v T) = ⌐(⌐q₁⌐T)

⌐S₂ = (⌐q₁ v T) = ⌐(q₁⌐T)

Условное обозначение триггера:

TT – два триггера внутри.

При реализации триггера на «или - не» берут RS триггер также построенный на «или – не» данный триггер имеет прямые значения R и S, следовательно при переходе к таблицы функций возбуждения необходимо приводить не инверсные, а прямые значения R и S.

В начальный момент времени t = 0, следовательно разрешена перезапись из 1 триггера во второй, следовательно их значения совпадают; 0 на установленном входе ⌐R₀ воздействует на оба триггера одновременно. Вначале установятся в 1 ⌐q₁ и ⌐q₂, а затем q₁ и q₂.

Появление t = 1 устанавливает либо ⌐S₁ либо ⌐R₁ в 0, в зависимости от значений ⌐q₁ и q₂ соответственно. Этот 0 (например) на ⌐S₁ переводит в 1 ⌐q₁, а затем ⌐q₁ переходит в 0. Инверсия сигнала T = 1 запрещает перезапись, устанавливаются ⌐S₂ и ⌐R₂ в 1. Когда T перейдет в 0 ⌐R₁ и ⌐S₁ станет = 1 и запись в первый триггер будет запрещена. Одновременно разрешается перезапись из 1 триггера во 2 и второй триггер устанавливается в соответствии с 1 - подобные структуры называются двухступенчатыми или MS(Master, Slave).

Исключение состязаний элементов памяти в синхронных автоматах.

Явление состязания элементов памяти рассматривается в асинхронном автомате. Устранение данного влияния в синхронных автоматах основано на применении триггеров с внутренней задержкой. В нашем курсе – это двухступенчатые триггеры, построенные по структуре MS. В этом случае структурный автомат будет выглядеть следующим образом:

C₁ = C C₂ = ⌐C  

К моменту времени t₀ триггеры должны быть установлены в начальное состояние и на вход поданы значения X_i.

К моменту t₁ должны быть сформированы функции возбуждения φ₁ и φ_k, t₁ – t₂ – запись нового значения в триггер 1 ступени. В это время происходит состязание элементов памяти только 1 ступени. Так как на входах комбинационного узла ничего не меняется (запись во 2 ступени запрещена, т.к. t₂ = 0), то данное состязание является не критическим.

Длительность сигнала С₁ должна быть достаточна для записи информации во все триггеры 1 ступени. К моменту t₃ на входах 2 ступени должны быть установлены новые значения. В интервале времени t₃ t₄ происходит запись во 2 ступень, и появляются новые значения на выходах элементов памяти автомата. В данном интервале происходит состязание элементов памяти 2 ступени. Это состязание также не критическое, так как С₁ = 0 и запись нового состояния в элементы памяти запрещена. Длительность С₂ = 1 должна быть достаточна для записи во все триггеры второй ступени. Во время С₂ изменяется Q_i, которые поступают на вход комбинационного узла и вызывают его срабатывание. Следовательно, целесообразно в это время менять и X_i. Интервал (t₄ – t₅) представляет собой интервал, в котором срабатывает комбинационный узел и формируются Y_j и φ_j, так как к моменту времени С₁ = 1 на выходах комбинационного узла значения стабильны, то при С₁ = 1 можно считывать значения Y.

Часто вместо двух синхроимпульсов используют прямое и инверсное значение одного. При этом, например, при С = 1 срабатывает (например) 1 ступень, при С = 0 вторая. Тогда длительность С = 1 определяется временем срабатывания триггеров 1 ступени, а С = 0 – сумма времен второй ступени и Комбинационного узла.

Пример:

Временная диаграмма:

Рассчитаем параметры сигнала синхронизации

С = 1 – запись в первую ступень

t_C=S = τ + 2 τ = 3 τ

2 τ – время сбрасывания двух внутренних триггеров, τ – время срабатывания элементов и на входах M триггеров

t_C=0 = t_тр + t_ку = 3τ + τ = 4 τ

T = 7 τ

Структура автоматов на ПЛМ и ПЗУ.

Используя ПЛМ и ПЗУ можно использовать только комбинационные узлы.

Обе микросхемы можно рассмотреть как устройство:

Матрицы И, ИЛИ – программируемые. На вход И матрицы И поступают прямые и инверсные значения входных переменных, на выходе получаем конъюнкции произвольного содержания от входных переменных. Выходы матрицы И называются термами.

В ПЗУ k = 2ⁿ, причем все термы разные.

В конъюнкцию ПЗУ входят все переменные, следовательно в ПЗУ матрица И представляет собой дешифратор, т.е. матрица И непрограммируемая, а содержит все возможности для конъюнкций.

В ПЛМ k < 2ⁿ. Матрица И программируема, причем на нескольких выходах можно получать одно и тоже. При реализации комбинационных схем на ПЗУ и ПЛМ заключается в распределении контактов на ПЗУ и ПЛМ между аргументами и функциями и второе в «прошивке» ПЗУ и ПЛМ.

Таблица прошивки для ПЗУ аналогична таблицы истинности функции. Таблица прошивки ПЛМ аналогична интервальной прошивке при совместной минимизации функций.

Пример: для ПЗУ.

an	…	a1	a0	Q0	…	Qm
	…				…
	…				…
	…				…
	…				…
	…				…

Здесь a_i – входы ПЗУ, Q_i- выходы.

Для ПЛМ:

an	…	a1	a0	Q0	…	Qm
	…		z	v		v
z	…	z		v
z	…				v	v
	…	z	z	v	v
…	…	…	…	…	…	…
	…	z		v

Условное графическое обозначение:

При нехватки числа выходов:

При нехватки термов:

Y_j = Y_j¹ v Y_j¹¹

Y_k = Y_k¹ v Y_k¹¹

Явление рисков в комбинационных узлах.

1)

2)

τ зависит от температуры, от расположения в микросхеме, влажности, давления…

t _{з min} < t _з< t _{з max}

До сих пор логические элементы мы рассматривали как элементы, обладающие бесконечным быстродействием, т.е. задержка = 0 (это модель 1).

Реально элементы имеют конечное значение задержки, поэтому модель логического элемента должна быть представлена следующим образом (2, где τ – задержка элемента).

ЛЭ – логическая функция элемента

t _з или τ зависит от многих параметров (ранее описанных).

Значение t_з может изменяться и во времени. Оно имеет значение от t _{з min} до t _{з max};

t _{з max} – паспортное значение на выпускаемый элемент

t _{з min} - для элементов не гарантировано.(t _{з min} = t _{з max} /1,5 – примерно из практики)

Из-за разброса t _з значений у реальных логических элементов возникает так называемые риски, статические и динамические. Риски ^{возникают} при смене входных переменных с одной комбинации на другую. При этом если на обеих комбинациях на выходе должно быть одно и тоже, то может возникнуть статический риск, что проявляется в появлении кратковременного ложного значения между двумя правильными – это статический риск.

Пусть узел реализует f (x¹ ) и существует 2 набора значений переменных δ₁ и δ₂, таких что f (δ₁ ) = f (δ₂ ), тогда если при смене набора δ₁ на δ₂ на выходе схемы появляется значение, отличное от f (δ₁ ), то говорят что в схеме имеет место статический риск.

Статические риски бывают:

a) статический риск в «1»

b) статический риск в «0»

t₁ – момент смены набора δ₁ на δ₂

Пример:

t _з¹ > t _з²

t _з³ = 0

если t₃¹ <= t₃², то статический риск отсутствует (статический риск в «1»)

Если на двух наборах функция имеет разное значение и переход от одного значения ко второму осуществляется не за 1 шаг, то это динамический риск.

Пусть существует f (x ¹) и два набора δ₁ и δ₂, такие что f (δ₁ ) ≠ f (δ₂ ), если при замене входного набора δ₁ на δ₂ на выходе схемы получают следующую последовательность

f (δ₁ ) àf (δ₂ ) àf (δ₁ ) àf (δ₂ ), то говорят что в схеме имеет место динамический риск. Существует динамический риск при переключении 0 à 1 и динамический риск 1 à 0.

F = (⌐x₁x₂ v x₁x₃) (⌐x₁x₄ v x₅)

t _з¹ < t _з²< t _з³

t _з⁴ = t _з⁵ = t _з⁶ = 0

Исключение влияние рисков.

1. В схемах синхронизации (синхронные автоматы) явление риска исключают за счет выбора периода и длительности синхроимпульса. Период синхросигнала должен быть больше времени срабатывания любой последовательности элементов в схеме. В это время все явления риска завершаются.
2. В асинхронных схемах необходимо строить комбинационные узлы без рисков.

Построение схем без риска.

На комбинационные узлы и схемы накладывают следующие ограничения

1) На входе узла при смене набора переменных может поменяться не более одной переменной.

2) Глубина схемы не должна быть более двух, т.е. схема имеет не более двух ярусов.

Эти два ограничения автомата устраняет явление динамического риска. При двухъярусной схеме возможно два варианта представления функции, описывающий данную схему ДНФ и КНФ. ДНФ: F = k₁ v k₂ v k₃ v… k_n

Если на выходах всех элементов «И» нули, то функция = 0, если новое значение функции тоже должно = 0, то и на всех элементах «И» опять должны быть 0. Для возникновения риска между двумя 0 на выходе должна быть 1. Чтобы 1 была кратковременна на выходе «ИЛИ» она должна быть кратковременна на выходе элемента «И». Однако такого быть не может, т.к. на входе меняется всего одна переменная, причем один раз, а элемент «И» представляет собой первый ярус схемы.

Вывод: в двухъярусной схеме, построенной по ДНФ, статический риск в 0 отсутствует.

КНФ:

По аналогичной причине в данной схеме отсутствует статический риск в «1»

Предположим, что на входе схемы X_i существует только в прямом или инверсном виде.

ДНФ: Разобьем группу элементов & на 2 подгруппы a и b.

На вход A X_i не поступает, в отличие от B

Если на выходе группы A хотя бы одна 1, то функция равна 1, при смене X_i значение A не меняется, т.е. на том же выходе останется 1 и в независимости от того меняется B 1à0 или 0à1 на выходе схемы обеспечивается единицей на выходе конъюнкторов группы A, если же все выходы A нулевые, то смена любая на B приведет к смене значений на выходе функций и статического риска не будет.

Аналогично для КНФ:

Аналогично, если на выходе группы A 0, то он удержит 0 на выходе в независимости от группы элементов B. Если на выходе группы A 1, то любое изменение на B повторит на выходе B, риск отсутствует, следовательно, если X_i входит в прямом или инверсном виде, то получили отсутствие риска в независимости от формы схемы (ярусность).

ДНФ:

y(δ₁) = y(δ₂) = 1

1) A(δ₁) = A(δ₂) = 1 – риска нет

2) A(δ₁) = A(δ₂) = 0 – возможен риск

a) B(δ_i) = 0 C(δ_i) = 1

b) B(δ_i) = 0 C(δ_i) = 1

КНФ:

y(δ₁) = y(δ₂) = 0

3) A(δ₁) = A(δ₂) = 0 – риска нет

4) A(δ₁) = A(δ₂) = 1 – возможен риск

c) B(δ_i) = 0 C(δ_i) = 1

d) B(δ_i) = 1 C(δ_i) = 0

Если в двухъярусной схеме X_i входит как в прямом так и в инверсном виде, то возможно возникнет статический риск.

ДНФ:
Разобьем конъюнкции на три группы, A,B,C, причем в группе A X_i не входит, в группу B X_i входит только в прямом виде, а в группу С X_i входит только в инверсном виде.

Пусть имеется две кодовые комбинации, отличия X_i, такие что y(δ₁) = y(δ₂) = 1

a) Если A(δ₁) = A(δ₂) = 1, следовательно риска нет на выходе схемы, так как при смене X_i 1 с выхода группы A обеспечивает 1 на выходе y вне зависимости от значения на выходе B и C.

b) Если A(δ₁) = A(δ₂) = 0, то 1 обеспечивается вначале благодаря группе C, а затем группе B, либо наоборот. В этом случае все зависит от задержки элементов групп B и C.

Пусть 1 обеспечивается вначале группой B, а затем группой C и задержка B > заданной C

τ_B > τ_C

τ_B <= τ_C

Если в схеме возможен риск, то идея построения схемы без риска заключается в обеспечении на комбинациях δ₁ δ₂ на выходе группы A 1.

Алгоритм построения схемы без рисков по ДНФ.

Пусть задана функция n переменных

1. Выбирается номер переменной i=1
2. Представляется искомая функция как сумма трех блоков

f(x¹) = A v B (x_i) v C(x¹_i)

1. Для x_i определяем пары наборов δ₁ δ_2, на которых функция равна 1 и которая отличается только значением x_i.
2. Для каждой полученной пары δ₁ δ₂ определяем значения на выходах группы конъюнкции A

Если A(δ₁) = A(δ₂) = 1, то риск отсутствует, если A = 0, то для пары образуем конъюнкцию, которая сохраняет значение 1 на обоих наборах δ₁ и δ₂ и не зависит от x_i.

1. Увеличиваем i на 1 и конец, если I больше n, иначе возвращаемся в пункт2.

Пример:

Есть функция трех переменных.φⁱ(x₁,x₂,x₃) = ⌐x₁⌐x₃ v x₂x₃

i = 1 – риска нет

i = 2 – риска нет

i = 3

B = x₂x₃

C = ⌐x₁x₃

A = 0

*
	*
		x3

B = 1 C = 0

B = 0 C = 1

Следовательно δ₁ = 011, δ₁ = 010

Следовательно A = ⌐x₁x₂, тогда окончательно φ(x₁,x₂,x₃) = ⌐x₁⌐x₃ v x₂x₃ v ⌐x₁x₂

Существует два способа для определения конъюнкций, исключающих явление риска:

1. С помощью операции обобщенного склеивания

если часть функции y¹ = RX_i v S⌐X_i = RS v RX_i v S⌐X_i

в примере R = x₂, S = ⌐x₁

1. С помощью карт Карно

В карте Карно симметричные клетки отличаются только одним разрядом x_i, следовательно если в симметричной клетке 1, а она входит в разное покрытие, то возможен риск и эти 1 надо объединить введя дополнительное покрытие.

				---------	x2
			---------		x1
	|
	x3

КНФ

Схему аналогично представлена виде A,B,C блоков, причем в группе A x_i не входит в группу B и C входит в прямом и инверсном виде. Риск возможен только если с выхода группы на двух комбинациях получается на двух комбинациях 1. В этом случае 0 на выходе обеспечивается на комбинации δ₁ группы B, а на комбинации δ₂ группы С или наоборот.

если τ_B > τ_C то получаем:

если τ_B <= τ_C то получаем:

Идея построения схемы без риска – по КНФ, формирование на выходе группы 0 на комбинациях δ₁ и δ₂

Алгоритм построения схемы без риска.

1. i = 1 – номер переменной
2. f (x¹) = A*B(x_i)*C(⌐x_i)
3. Нахождение δ₁ и δ₂ отличающиеся только x_i таких, на которых A = 1
4. Для найденной пары δ₁ и δ₂ находится дизъюнкция, которая на двух наборах = 0, и в которую не входит x_i, вводим эту дизъюнкцию в функцию.
5. i = i + 1, пока i<=n возвратиться во второй пункт.

Пример:

Есть функция трех переменных.φⁱ(x₁,x₂,x₃) = (⌐x₁ v x₃)*(x₂ v ⌐x₃)

i = 1 – риска нет

i = 2 – риска нет

i = 3

B = ⌐x₁ v x₃

C = x₂ v ⌐x₃

A = 1

	*
*
		x3

B = 0 C = 1

B = 0 C = 0

Следовательно δ₁ = 100, δ₁ = 101

Следовательно A = ⌐x1 v x2, тогда окончательно

φ(x₁,x₂,x₃) = ⌐x1 v x2₁ v x₃)*(x₂ v ⌐x₃)*(⌐x₁ v x₂)

Дополнительную дизъюнкцию для группы A можно получить двумя способами:

1) Обобщенное склеивание

(R v x_i)*(S v ⌐x_i) = (R v S)*(R v x_i)*(S v ⌐x_i)

в примере R = ⌐x₁, S = x₂

2) Карты Карно, поиск осуществляется симметричных нулей.

				---------	x2
			---------		x1
	|
	x3

При структурном синтезе асинхронного автомата необходимо строить комбинационные узлы без риска.

Дата добавления: 2014-01-06