Выбор функционально полной системы логических элементов

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

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

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

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

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

 

Построение функциональной схемы автомата

На основании полученных выражений для булевых функций возбуждения памяти автомата и булевых функций выходов автомата строится комбинационная схема функций возбуждения памяти КС1 и комбинационная схема формирования выходных сигналов автомата (КС2 или КС3). Элементы памяти подключаются к построенным комбинационным схемам как показано на рис. 3.1.

 

Пример канонического метода структурного синтеза

Пример 3.1. Синтезировать автомат Мили S, заданный совмещенной таблицей переходов и выходов (табл. 3.11). В качестве элементарных автоматов памяти использовать Т -триггеры, комбинационные схемы реализовать в булевом базисе.

 

Таблица 3.11 Совмещенная таблица переходов и выходов автомата Мили S

 

 

	a 1	a 2	a 3	a 4
z 1	a 2 / w 1	a 2 / w 1	a 1 / w 2	a 1 / w 4
z 2	a 4 / w 5	a 3 / w 3	a 4 / w 4	a 3 / w 5

 

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

Так как у абстрактного автомата S четыре состояния, то структурный автомат S будет иметь два элемента памяти T ₁ и T ₂. Два абстрактных входных сигнала (z ₁, z ₂) и пять выходных сигналов (w ₁, w ₂, w ₃, w ₄, w ₅) требуют один входной (x) и три выходных канала (y ₁, y ₂, y ₃).

Результаты кодирования состояний, входных и выходных сигналов автомата S представлены в табл.3.12, 3.13, 3.14.

В общем случае кодирование произвольное, но две различные буквы одного алфавита должны кодироваться различными векторами. Заменив в совмещенной таблице переходов и выходов автомата Мили S (табл. 3.11) состояния, входные и выходные сигналы их кодами, получим совмещенную таблицу переходов структурного автомата Мили (табл. 3.15).

 

Таблица 3.12 Кодирование состояний автомата S		Таблица 3.13 Кодирование входных сигналов автомата S		Таблица 3.14 Кодирование выходных сигналов автомата S
A Q 1 Q 2 a 1     a 2     a 3     a 4		z x z 1   z 2		w y 1 y 2 y 3 w 1       w 2       w 3       w 4       w 5

Таблица 3.15 Совмещенная таблица переходов и выходов структурного автомата S
x	Q 1 Q 2
	01 / 000	01 / 000	00 / 010	00 / 011
	10 / 100	11 / 010	10 / 011	11 / 100

 

На следующем этапе производится построение булевых функций возбуждения памяти и функций выходов:

(3.7)

где Q1, Q2 – функции обратной связи от памяти автомата к его КС,

T1, T2 ‑ функции возбуждения элементов памяти автомата,

- функции выходов.

Найдем функции возбуждения памяти T ₁ и T ₂. Для этого воспользуемся таблицей переходов Т -триггера (см. табл. 3.4). Учитывая, что T ₁ = 1 и T ₂ = 1 только в случае перехода соответствующего триггера из нулевого состояния в единичное и наоборот, используя структурную таблицу переходов автомата (см. табл. 3.15), получим таблицу функций возбуждения памяти (табл. 3.16). Например, при переходе автомата S из состояния 00 в состояние 10 под действием входного сигнала 1 (первый столбец, вторая строка табл. 3.15), на входы его памяти должен поступить векторный сигнал функции возбуждения 10. Занесем этот результат в соответствующее место таблицы функций возбуждения (табл. 3.16) – на пересечении первого столбца и второй строки. Поскольку функции возбуждения памяти T ₁ и T ₂ зависят от тех же переменных x, Q ₁, Q ₂, столбцы и строки табл. 3.15 и табл. 3.16 отмечены одинаково. Аналогичным образом для остальных переходов в табл. 3.15 получим всю таблицу функций возбуждения памяти автомата S.

 

Таблица 3.16 Функции возбуждения памяти автомата S
x	Q 1 Q 2

 

Перейдем от табл.3.15 и 3.16 к табл. 3.17. Последняя представляет собой более привычную для нас таблицу истинности системы булевых функций (3.6).

 

Таблица 3.17 Таблица истинности булевых функций возбуждения памяти и функций выходов
x	Q 1	Q 2	T 1	T 2	y 1	y 2	y 3

 

Из табл.3.17 имеем:

(3.8)

Ясно, что табл. 3.17 можно не строить, а выражения (3.7) получить непосредственно по табл. 3.15 и 3.16. Не будем рассматривать вопросы минимизации комбинационных схем автомата, непосредственно по выражениям (3.8) построим логическую схему автомата S на элементах И, ИЛИ, НЕ (рис. 3.4).

 

 

Рис. 3.5. Логическая схема автомата Мили S

 

Следует отметить, что при синтезе автоматов на D -триггерах процесс построения функций возбуждения памяти может быть упрощен. Как видно из табл. 3.7, состояние, в которое переходит D -триггер, совпадает с поступившим на его вход сигналом. В связи с этим таблица функций возбуждения памяти синтезируемого автомата S будет полностью совпадать со структурной таблицей переходов этого автомата (см. табл. 3.15).

 

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

 

Таблица 3.18 Отмеченная таблица переходов автомата Мура S 1
	w 3	w 2	w 3	w 1
	a 1	a 2	a 3	a 4
z 1	a 1	‑	a 1	a 4
z 2	a 2	a 3	‑	a 1
z 3	‑	a 4	a 4	a 2

 

Решение. Закодируем входные и выходные сигналы и состояния автомата S ₁. Три абстрактных входных сигнала (z ₁, z ₂, z ₃) и три выходных сигнала (w ₁, w ₂, w ₃) требуют два входных (x ₁, x ₂) и два выходных (y ₁, y ₂) канала. Так как в абстрактном автомате четыре состояния, то структурный автомат будет иметь два RS -триггера T ₁ и T ₂. Q ₁, Q ₂ – код состояния автомата S ₁. Результаты кодирования представлены в табл. 3.19 – 3.21.

 

Таблица 3.19 Кодирование входных сигналов автомата S 1

Таблица 3.20 Кодирование выходных сигналов автомата S 1

Таблица 3.21 Кодирование состояний автомата S 1

 

z	x 1	x 2		w	y 1	y 2		A	Q 1	Q 2
z 1				w 1				a 1
z 2				w 2				a 2
z 3				w 3				a 3
								a 4

Заменив в табл. 3.18 состояния, входные и выходные сигналы их кодами, получим структурную таблицу переходов автомата Мура S ₁ (табл. 3.22).

Комбинационные схемы структурного автомата Мура S ₁ реализуют функции:

(3.9)

где R_i, S_i – функции возбуждения элементов памяти автомата.

 

	Таблица 3.22 Отмеченная таблица переходов структурного автомата S 1		Таблица 3.23 Функции возбуждения памяти автомата S 1
y 1 y 2	0 0	1 0	0 0	0 1		x 1 x 2	Q 1 Q 2
Q 1 Q 2 x 1 x 2	0 0	0 1	1 1	1 0		0 0	0 1	1 1	1 0
0 0	0 0	–	0 0	1 0		0 0	0-0-	–		-00-
0 1	0 1	1 1	–	0 0		0 1	0-10	10-0	–	010-
1 0	–	1 0	1 0	0 1		1 0	–		-001

 

Выражения для функций выходов y ₁, y ₂ получим непосредственно из табл. 3.22:

; . (3.10)

Таблицу функций возбуждения памяти (табл.3.23) строим на основании структурной таблицы переходов (табл. 3.22). Поскольку в RS -триггере имеются два входных канала, на пересечении строк и столбцов в таблице функций возбуждения памяти будем указывать значения четырех функций: S ₁, R ₁, S ₂, R ₂. Функция входов RS -триггера приведена в табл. 3.3. Эта таблица дает систему подстановок при переходе от таблицы переходов структурного автомата к таблице его функций возбуждения. Прочерк (–) означает, что переход не зависит от сигнала на данном входе. Функции возбуждения триггеров не полностью определенные, так как набор входных сигналов x ₁=1 и x ₂=1 никогда на вход автомата не поступает.

Из табл. 3.23 получаем выражения для функций S_i, R_i:

(3.11)

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

Рис. 3.6. Диаграммы Вейча для определения

функций возбуждения RS -триггеров автомата S ₁

 

Выполнив совместную минимизацию системы булевых функций, получим:

(3.12)

По выражениям (3.10) и (3.12) построим логическую схему автомата Мура S ₁ на элементах И, ИЛИ, НЕ (рис. 3.6).

 

 

Рис. 3.7. Логическая схема автомата Мура S ₁

 

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

 

Гонки в автомате

 

Переход автомата из одного состояния в другое осуществляется за счет изменения состояния элементов памяти Q ₁, Q ₂,..., Q_I, которое производится сигналами возбуждения j ₁, j ₂,..., j _I (см. рис. 3.1), вырабатываемыми в комбинационной схеме КС1 и поступающими на входы триггеров. Сигналы возбуждения поступают на входы триггеров не одновременно, так как логические цепи их реализующие, возможно не идентичные по количеству используемых в них логических элементов, характеризуются различным временем задержки сигнала. К тому же триггеры имеют различное время переключения. Из-за различия во временных характеристиках триггеры изменяют свои состояния не одновременно.

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

Например, при переходе автомата a_m в состояние a_s под действием входного сигнала x (рис. 3.7, а), автомат может оказаться в некотором промежуточном состоянии a_k или a_l. Если затем при том же входном сигнале автомат из a_k и a_l перейдет в состояние a_s, то такие состязания являются допустимыми или некритическими. Если же в этом автомате есть переход, например из a_k в a_j ¹ a_s под действием того же сигнала x (рис.3.7, б), то автомат может перейти в a_j, а не в a_s и правильность его работы тем самым будет нарушена. Гонки, приводящие автомат в устойчивое состояние, не соответствующее закону функционирования, называются критическими.

Рис. 3.7. Состязания между элементами памяти: а – некритические, б – критические

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

 

Методы устранения гонок

В схемах на рис. 3.4 и 3.6 гонки устраняются путем ограничения длительности сигнала С, поступающего в цепь синхронизации. Этот способ устранения гонок называется способом импульсной синхронизации. Если длительность импульса t_c меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме КС1, то к моменту перехода в промежуточное состояние a_k (рис.3.7,б) сигнал С равен нулю, что и исключает гонки. Естественно, что такой способ устранения гонок приемлем только в том случае, если элементы памяти могут переключаться под действием импульсов с длительностью t_c.

Другой способ ликвидации гонок заключается в разделении во времени процессов выработки сигналов возбуждения и процесса переключения состояний. Такого рода разделение достигается использованием двойной (двухступенчатой) памяти (рис. 3.8). При использовании двойной памяти синхронизация автомата производится с помощью двух последовательностей синхронизирующих импульсов C ₁ и C ₂, причем C ₁ × C ₂ = 0.

 

Рис. 3.8. Организация двойной памяти

Первая ступень памяти состоит из триггеров Т 1, связанных с комбинационной схемой КС1 автомата, и называется памятью возбуждений. Вторая ступень состоит из триггеров Т 2, с выходов которых снимаются сигналы обратной связи, определяющие текущее состояние автомата. По сигналу С ₁ в комбинационной части автомата вырабатываются сигналы возбуждения j, которые устанавливают триггеры Т 1 памяти возбуждений в состояние, соответствующее следующему состоянию автомата. Поскольку С ₂ = 0, то состояние триггеров второй ступени при этом не изменяется. По сигналу С ₂ = 1 состояние Т 1 переписывается в Т 2, и происходит тем самым переключение автомата в новое состояние. При этом С ₁ = 0 и сигналы возбуждения принимают нужные значения, тем самым исключается возможность переключения триггеров памяти возбуждений при переключении сигналов в цепи обратной связи. Следующий синхроимпульс С ₁ подается через время, достаточное для окончания переходных процессов в комбинационной схеме КС1. Далее процесс повторяется.

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

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

Наряду с аппаратными способами для устранения гонок используются специальные методы противогоночного кодирования состояний автомата. Некоторые из них рассмотрены в [3]. Частным случаем противогоночного кодирования является соседнее кодирование.

Гонки в автомате исключаются, если при любых переходах изменяется состояние только одного элемента памяти. Способ кодирования состояний, при котором соседние состояния автомата кодируются наборами, различающимися состоянием только одного элемента памяти, называется соседним кодированием. Пример автомата с соседним кодированием состояний приведён на рис.3.9. на каждом переходе в автомате вырабатывается только один сигнал возбуждения [9].

 

Рис.3.9. Граф, допускающий соседнее кодирование

 

Соседнее кодирование не всегда возможно. На рис. 3.10 приведены два графа, которые не могут быть закодированы соседними кодами. Сформулируем требования к графу автомата, допускающему соседнее кодирование:

- в графе автомата не должно быть циклов с нечетным числом вершин (рис. 3.10, а);

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

При этом под состояниями второго порядка понимаются два состояния, путь между которыми по графу автомата состоит из двух ребер, независимо от ориентации (рис. 3.11, б).

Рис. 3.11. Графы, не допускающие соседнего кодирования

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

Синхронизация автоматов

В рассмотренных выше автоматах вместо физического времени рассматривалось абстрактное время или номер такта. Однако автомат как реальное устройство представляет собой динамическую систему – совокупность физических элементов, состояния которых изменяются в реальном физическом времени [7]. Смена состояний осуществляется не мгновенно, а связана с некоторым переходным процессом. Физические системы можно рассматривать как конечные автоматы, если исключить из рассмотрения время, в течение которого схемы и входные сигналы находятся в переходном режиме, и выделить только те моменты времени, когда состояние схемы и ее выходов неизменны, то есть при достижении устойчивых состояний. Тогда номера этих моментов времени можно идентифицировать с номерами шагов алгоритма, а интервал между этими моментами времени можно назвать тактом работы автомата.

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

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

Таким образом, такт работы определяет время пребывания автомата в одном состоянии a_i и равен

Т = Т_УА + Т_ОА,

Т_УА – затраты времени на управление, зависят от длительности переходных процессов в управляющем автомате;

Т_ОА – интервал времени, необходимый для выполнения микроопераций и вычисления логических условий в операционном автомате.

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

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

Т_ОА = max (t ₁, t ₂,, t_M),

где t ₁, t ₂,, t_M – время выполнения микроопераций y ₁, y ₂,…, y_M.

Поскольку микрооперации y ₁, y ₂,…, y_M обычно выполняются за промежуток времени меньший самой продолжительной микрооперации, то из-за постоянства такта возникают потери времени.