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

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

Необходимое число разрядов кода q определяется также как при кодировании синхронного автомата, т.е. q_min = ┐log₂k┌, q_max = k, где k – число состояний автомата.

 

Способ кодирования соседними кодами.

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

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

 

01/0

00/0

11/1

Рис. 6.7

 

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

 

01/0

00/0

11/1

Рис. 6.8

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

 

 

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

Это кодирование состояний унитарным кодом.

В данном способе кодирования состояние s_i кодируется кодом, содержащим одну единицу в i - том разряде.

Для исключения состязаний элементов памяти при переходе из s_i в s_j на этом переходе вводится транзитное состояние, которое кодируется кодом, содержащим две единицы в i и j разрядах (рис. 6.9).

 

s1

s13

y1y2y3

s3

Рис. 6.9

 

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

Пример универсального способа кодирования.

После кодирования унитарным кодом состояний автомата, заданного графом на рис. 6.3:s₁ = 100, s₂ = 010, s₃ = 001 и введения транзитных состояний получается граф на рис. 6.10.

100/0

010/0

001/1

X1x2

y1y2y3/z

Рис. 6.10

Если в качестве элемента памяти задан D-триггер, то при построении его функций возбуждения необходимо обеспечить его переходы: 0 1 и 1 1. Например, для реализации двенадцатого перехода (номер перехода на pис. 6.10 обведен) надо в функцию возбуждения первого триггера включить конъюнкцию y_{1 2 3}, а для реализации первого перехода из состояния: s₁ = 100 в транзитное состояние с кодом 110, необходимо второй триггер установить в единицу, для этого в функцию возбуждения второго триггера надо включить конъюнкцию x₁x₂y₁, как только y₂ = 1 конъюнкция y_{1 2 3} примет значение ноль и этим сбросит первый триггер в ноль - так будет реализован второй переход, т.е. из транзитного с кодом 110 автомат перейдет в состояние s₂ = 010. Последовательно просматривая все переходы в графе (pис. 6.10), формируются конъюнкции, которые включаются в соответствующие функции возбуждения. Под каждой конъюнкцией указан номер перехода, который она обеспечивает:

 

y ’ _D1 = _{1 2}y₂ V _{1 2} y₃ V y_{1 2 3};

y ’ _D2 = x₁ x₂ y₁ V ₁ x₂ y₃ V x₁ x₂ y₃ V ₁ y_{2 3};

y ’ _D3 = x_{1 2} y₁ V _{1 2} y₃;

z = y₃.

 

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

 

y1

x1

y2

y3

x2

y’D1

y’D2

y’D3

t0

t1

t2

t3

t4

t5

Рис. 6.11

 

Пусть в момент времени t₀ автомат находится в состоянии s₁, y₁y₂y₃ = 100, а входные сигналы x₁x₂ = 01. Функции возбуждения триггеров имеют следующие значения y ’ _D1 = 1, y ’ _D2 = 0, y ’ _D3 = 0 и это подтверждает состояние 100, до момента t₁.

В момент t₁ меняется x₁ и к моменту t₂ становится y ’ _D2 = 1, а это к моменту времени t₃ устанавливает триггер y₂ = 1; в интервале t₃ и t₄ получается транзитное состояние 110. Изменение y₂ меняет значение y ’ _D1: 1 0, которое в свою очередь устанавливает в момент t₅ триггер y₁ = 0, после t₅ автомат находится в устойчивом состоянии 010, т.е. в s₂.

При переходе из s₁ в s₂ последовательно меняется вначале y₂ и затем y₁. Это обеспечивает отсутствие состязаний между ними.

 

Если в качестве элемента памяти задан RS-триггер, то при построении его функций возбуждения необходимо обеспечить его переходы: 0 1 и 1 0. Например, для реализации первого перехода (pис. 6.10) из состояния: s₁ = 100 в транзитное состояние 110, необходимо второй триггер установить в единицу, для этого в функцию возбуждения входа S второго триггера надо включить конъюнкцию x₁x₂y₁. Далее для реализации второго перехода из транзитного 110 в состояние s₂ = 010 необходимо первый триггер сбросить в ноль, для этого в функцию возбуждения входа R первого триггера надо включить конъюнкцию x₁x₂ y₂. Последовательно просматривая все переходы в графе (pис. 6.10), формируются конъюнкции, которые включаются в соответствующие функции возбуждения:

 

y ’ _S1 = _{1 2} y₂ V _{1 2} y₃;

 

y ’ _S2 = x₁ x₂ y₁ V ₁ x₂ y₃ V x₁ x₂ y₃;

y ’ _S3 = x_{1 2} y₁;

y ’ _R1 = x₁ x₂ y₂ V x_{1 2} y₃;

y ’ _R2 = _{1 2} y₂;

y ’ _R3 = _{1 2} y₃ V ₁ x₂ y₃ V x₁ x₂ y₃;

 

z = y₃.

 

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

Пусть в момент времени t₀ автомат находится в устойчивом состоянии s₁, y₁y₂y₃ = 100, а входные сигналы x₁x₂ = 01. Функции возбуждения триггеров имеют следующие значения: y ’ _R1 = 0, y ’ _S1 = 0, y ’ _R2 = 0, y ’ s₂ = 0 и это подтверждает состояние 100, до момента t₁.

В момент t₁ меняется x₁: 0 1 и к моменту t₂ изменяет y ’ _D2 = 1, а это к моменту времени t₃ устанавливает триггер y₂ = 1; в интервале t₃ и t₄ получается транзитное состояние 110. Далее изменение y₂ меняет значение y ’ _D1: 1 0, которое в свою очередь устанавливает в момент t₅ триггер y₁ = 0, после t₅ автомат находится в состоянии 010, т.е. в состоянии s₂.

При переходе из s₁ в s₂ последовательно меняется вначале y₂ и затем y₁. Это обеспечивает отсутствие состязаний между ними.

 

y1

x1

y2

x2

y’R1

y’S1

y’R2

t0

t1

t2

t3

t4

y’s2

t5

t6

Рис. 6.12

 

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

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

По логическому функционированию элементы памяти (триггеры) делятся на следующие типы: RS, JK, D и T.

По принципу записи и считыванию информации схемы триггеров делятся:

1. в зависимости от наличия или отсутствия сигнала синхронизации:

a. асинхронные;

b. синхронные;

2. в зависимости от времени записи новой информации, и ее появление на выходе триггера:

a. триггеры без логической задержки;

b. триггеры с логической задержкой.

 

Триггером с логической задержкой называется триггер, который меняет своё состояние по окончанию сигнала вызвавшего это изменение.

На рис. 6.13 -6.16 приведены временные диаграммы работы всех четырех вариантов логических схем RS-триггера.

В триггерах без логической задержки изменение состояния происходит по фронту информационного сигнала (рис. 6.13) или по фронту синхросигнала (рис. 6.14), а в триггерах с логической задержкой по “спаду” информационного сигнала (рис. 6.15) или “спаду” синхросигнала (рис. 6.16).

 

 

Асинхронный RS-триггер

без логической задержки.

R

S

q

 

 

Рис. 6.13

 

 

Асинхронный RS-триггер

с логической задержкой.

R

S

q

 

 

Рис. 6.15

 

Синхронный RS-триггер

без логической задержки.

R

S

q

С

Рис. 6.14

 

 

Синхронный S-триггер

с логической задержкой

R

S

q

С

Рис. 6.16

Построение асинхронного RS - триггера без логической задержки из логических элементов потенциального типа.

RS-триггер из логических элементов ИЛИ-НЕ.

На рис. 6.17 приведена схема, так называемой, “бистабильной ячейки” из элементов ИЛИ-НЕ, которая может находиться в одном из двух состояний. Пусть на одном из выходов схемы, который обозначим – q, значение логический ноль, а на другом, который обозначим – , значение логической единицы. После подачи на входы схемы тестовых последовательностей и построения временной диаграммы (рис. 6.18) видно, что это схема является RS-триггером, так как подача 0 0 на входы схемы не меняет значения на её выходах, а подача на входы 1 1 дает на выходах 0 0, т.е. схема перестает быть триггером и следовательно набор
1 1 не допустим. Верхний вход является R-входом, а нижний S-входом. Условное обозначение триггера (рис. 6.19).

 

R

S

q

0 0 0 1

0 1 0 1

0 0 1 1 0

1 1 0 0 1 1

 

Рис. 6.17

 

 

R

S

q

Рис. 6.18

 

T

S

R

q

 

Рис.6.19

 

 

RS-триггер из логических элементов И-НЕ

На рис. 6.20 приведена схема “бистабильной ячейки” из элементов И-НЕ, которая может находиться в одном из двух состояний. Пусть на одном из выходов схемы, который обозначим – q, значение логический ноль, а на другом, который обозначим – , значение логической единицы. После подачи на входы схемы тестовых последовательностей и построения временной диаграммы (рис. 6.21) видно, что это схема является RS-триггером, с инверсными входами так как подача 0 0 на входы схемы дает на выходах 1 1, т.е. схема перестает быть триггером и следовательно набор 0 0 не допустим, а входной набор 1 1 не меняет значения на её выходах.. Верхний вход является -входом, а нижний -входом. Условное обозначение триггера (рис. 6.22).

&

&

q

1 0 1 1

1 1 1 0

0 0 1 1

1 1 0 0

Рис. 6.20

 

q

Рис. 6.21

 

T

S

R

q

 

Рис. 6.22

 

Элементы памяти с установочными входами.

Для того чтобы перед началом работы схема триггера находилась в нужном состоянии, в схему вводятся дополнительные, так называемые установочные входы R₀ и S₀ для элементов ИЛИ-НЕ (рис. 6.23), ₀ и ₀ для элементов И-НЕ (рис. 6.24). Они отличаются от информационных входов только тем, что нужные значения подаются на входы только перед началом работы триггера. После установки триггера в требуемое состояние они меняются на значение, не влияющие на дальнейшую работу триггера. На рис. 6.25 и рис. 6.26 указаны сигналы устанавливающие триггеры в нулевоё состояние, т.е. q = 0. На рис. 6.27 и рис. 6.28 даны условные обозначения триггеров с установочными входами.

 

R

S

q

R0 0

S0 0

Рис. 6.23

 

R0

S0

 

Рис. 6.25

 

&

&

q

0 0

0 0

Рис. 6.24

 

0

0

 

Рис.6.26

R0

R

S

S0

T

R0

SR

R

S0

T

q

q

 

Рис. 6.27 Рис. 6.28

 

 

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

Синхронизация позволяет:

1. исключить влияние временных смещений сигналов триггера на его разных информационных входах;

2. позволяет обеспечить одновременное изменение состояний различных элементов памяти.

S

R

C

∆

Рис. 6.29

На рис. 6.29 приведен пример исключение временного смещения входных сигналов на величину ∆. Для асинхронного триггера это привело бы к недопустимой ситуации – подачи на входы RS-триггера двух единиц одновременно. Введение сигнала синхронизации позволяет это исключить.

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

1. сигнал синхронизации по длительности должен быть короче информационного сигнала;

2. сигнал синхронизации должен быть во времени сдвинут от изменения информационного сигнала на величину ∆, обеспечивающую устойчивую работу триггера (рис. 6.30).

Информационный сигнал не должен меняться при C = 1.

T

C

∆1

∆2

∆1, ∆2 >0

Рис. 6.30

 

Синтез синхронного D - триггера без логической задержки.

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

На рис. 6. 31 граф и таблица переходов автомата Мура (табл. 6.4), задающих синхронный D-триггер

Таблица 6.4

 

DC q

0/0

1/1

DC

DC

Рис. 6.31

На рис. 6. 32 изображена структурная схема синтезируемого D-триггера.

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

R0

R

S

S0

T

КC

С

D

q

Рис. 6.32

 

q(t) →q(t+1)	S R
0 → 0	0 *
0 → 1	1 0
1 → 0	0 1
1 → 1	* 0

Рис. 6.33

 

Таблица 6.5

 

DC q
	0*	0*		0*
	*0		*0	*0

По таблице переходов (табл. 6.4), используя матрицу переходов RS-триггера (рис. 6. 33), строится таблица функций возбуждения (табл. 6.5).

Далее по этой таблице строятся карты Карно для функций возбуждения: y’_S (табл. 6.6) и y’_R (табл. 6.7). После минимизации получаются следующие выражения для функций возбуждения RS-триггера в базисе ИЛИ-НЕ:

y’_S = DC = = V ; y’_R = C = C = D V .

 

 

y’R

y’S

Таблица 6.6 Таблица 6.7

D C

D C

q		*		*	*

	*	*		*

 

 

q

 

На рис. 6.34 приведена схема синтезированного синхронного D- триггера из элементов ИЛИ-НЕ, а на рис. 6.35 его условное обозначение:

R

S

q

R0

S0

S0

C

R0

T

D

q

Рис. 6.34 Рис. 6.35

 

На рис. 6.36 приведена схема синтезированного синхронного D- триггера из элементов И-НЕ, а на рис. 6.37 его условное обозначение:

 

0

&

&

q

0

&

&

D

&

C

S0

C

R0

T

D

q

Рис. 6.36 Рис. 6.37

 

На рис. 6.38 приведена временная диаграмма работы синхронного D- триггера из элементов ИЛИ-НЕ (рис. 6.34).

 

R

S

q

t0

t1

t2

t3

t4

R0

S0

t0

Рис. 6.38

 

В момент времени t₀ сигнал R₀, ранее установивший в RS-триггер в 0, становится R₀ = 0 и RS-триггер начинает реагировать на сигналы подаваемые на информационные входы.

В момент t₁ появляется сигнал R = 1, однако триггер в состоянии 0 и следовательно смены состояния не происходит.

В момент t₂ появляется сигнал S = 1, который устанавливает = 0, а затем q = 1. Повторный сигнал S = 1 в момент t₃ лишь подтверждает состояние q =1.

В момент времени t₄ появившийся сигнал R = 1 устанавливает q = 0, а затем = 1, т.е. сбрасывает триггер в 0.

 

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

Триггером с логической задержкой называется триггер, который меняет своё состояние по окончанию сигнала вызвавшего это изменение, т.е. триггер меняет состояние по спаду информационного сигнала (рис. 6.39).

T

q

Рис. 6.39

Появление входного информационного сигнала T = 1 устанавливает новое состояние триггера q = 1, однако на выходе это значение появляется лишь после исчезновения сигнала T = 1. Эффект такой логической задержки можно организовать, используя два элемента памяти, т.е. для задания такого триггера используется автомат Мура, который имеет четыре состояния и соответственно граф - четыре вершины (рис. 6.40):

00/0

T

10/0

11/1

01/1

y1y2/q

Рис. 6.40

Tаблица переходов автомата (табл.6.8) и его структурная схема (рис.6.41):

Tаблица 6.8

 

q	T y1y2

 

КC

q

y2

y1

’R1

R

S

R

S

T

T

S1

R2

S2

T

T

1

y2

Рис.6.41

По таблице переходов (табл. 6.8), используя матрицу переходов RS-триггера (рис. 6. 42), строится таблица функций возбуждения (табл. 6.9).

Далее по этой таблице строятся карты Карно функций возбуждения

y’_S1 (табл. 6.10), y’_R1 (табл. 6.11) и y’_S2 (табл. 6.12), y’_R2 (табл. 6.13).

 

Таблица 6.9

 

q	T y1y2
		0*, 0*	0*, 10
		10, *0	0*, *0
		*0, *0	*0, 01
		01, 0*	*0, 0*

 

q(t) →q(t+1)	S R
0 → 0	0 *
0 → 1	1 0
1 → 0	0 1
1 → 1	* 0

 

Рис. 6. 42

 

 

Далее по этой таблице строятся карты Карно функций возбуждения:

y’_S1 (табл. 6.10), y’_R1 (табл. 6.11) и y’_S2 (табл. 6.12), y’_R2 (табл. 6.13):

 

Таблица 6.10

y’S1		T
		*	*
		*

y₁y₂

 

Таблица 6.11

y’R1		T
		*	*
			*

y₁y₂

 

Таблица 6.12

y’S2		T
		*	*
		*

y₁y₂

 

Таблица 6.13

y’R2		T
		*
	*	*

y₁y₂

 

 

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

y’_S1 = y₂ , y’_R1 = ₂ , y’_S2 = ₁ T, y’_R2 = y₁ T.

Для построения схемы Т-триггера в базисе И-НЕ в качестве элемента памяти используется базовый RS-триггер c инверсными входами. Выражения инверсных функций возбуждения RS-триггеров имеют вид:

 

y’_S1 = y₂ , y’_R1 = ₂ , y’_S2 = ₁ T, y’_R2 = y₁ T.

 

Схема Т-триггера на логических элементах И-НЕ (рис. 6. 43):

&

&

&

&

&

&

&

&

0

y2

2 2

y’S2

y’R2

y1