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

 

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)	0	1
	S(q)
0	0	0	1
1	1	0	1

 

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

 

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

 

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

 

0

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

1

0 à 1

0

1 à 0

1

1 à 1

 

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

 

 

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

 

 

q / T	0	1
0	0	1
1	1	0

 

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

 

0

0 à 0

1

0 à 1

1

1 à 0

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	00	01	10	11
0	0	1	0	--
1	1	1	0	--

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

 

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

*0

0 à 0

01

0 à 1

10

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	00	01	10	11
0	0	0	1	1
1	1	0	1	0

 

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	0	1
S0	S1 /0	S1 /0
S1	S2 /0	S2 /0
S2	S0 /1	S0 /0

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

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

RS

*0

0 à 0

01

0 à 1

10

1 à 0

0*

1 à 1

 

Xi / q0q1	0	1
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
	---	1	0	0
X0 -	---	1	0	0

 

S0			------------q1
		------------q0
	---	0	*	1
X0 -	---	0	*	1

 

R1			------------q1
		------------q0
	---	0	1	0
X0 -	---	0	1	0

 

S1			------------q1
		------------q0
	---	1	0	*
X0 -	---	1	0	*

 

Z0			------------q1
		------------q0
	---	1	0	0
X0 -	---	0	0	0

 

 

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

 

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.

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