Получение условий работы синтезируемого дискретного устройства

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

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

Построение и минимизация первичной таблицы переходов-выходов

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

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

При построении первичной таблицы переходов-выходов надо руководствоваться следующими правилами:

1) Каждой строке таблицы соответствует одно устойчивое состояние (устойчивый такт), который будем обозначать цифрой в кружочке (a). Цифра устойчивого такта соответствует номеру строки. Неустойчивый такт обозначаем цифрой без кружка;

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

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

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

5) В потенциальных автоматах переход из неустойчивого состояния в устойчивое всегда осуществляется при постоянном входном наборе за счет изменения состояний элементов памяти.

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

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

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

Пример 3.1 Спроектировать схему управления шаговым искателем (Z). Схема должна иметь входные сигналы «Пуск» (кнопка А) и «Стоп» (кнопка В). Шаговый искатель должен включаться в работу только после нажатия и отпускания кнопки А. Остановка осуществляется нажатием кнопки В. Из словесной формулировки получаем программу работы (Таблица 3.1), где а, b – входные сигналы (соответственно «Пуск» и «Стоп»); z – выходной управляющий сигнал для шагового искателя.

Таблица 3.1

a b
z

Видим, что проектируемое ДУ должно иметь память, так как при комбинации входных сигналов 00 значение выхода может быть различным – 0 и 1.

Строим первичную таблицу переходов-выходов (Таблица 3.2). В первой клетке (исходное состояние) ставим (1) – устойчивый такт. Далее по программе включается А (а= 1), осуществляется переход вдоль первой строки к столбцу «10», ставим такт 2, а от него вдоль столбца переходим к устойчивому такту (2) – строка 2. Далее отпускает А (а= 0), осуществляется переход к столбцу 00, ставим такт 3, а затем переходим к устойчивому такту (3) – строка 3. Именно к такту 3, а не к (1), так как значения выходного сигнала z в этих состояниях (00) разные: в строках 1 и 2 z =0, а в строке 3 z =1 (согласно программе работы). Далее срабатывает В (b =1), осуществляется переход к столбцу «01» (такт 4) и к строке 4 – устойчивый такт (4), при этом z =0.

Таблица 3.2

N	a b	z

	(1)		-
		(2)	-	-
	(3)		-
		-	-	(4)

Далее В отпускает (b =0), происходит возврат к устойчивому такту (1), через неустойчивый такт 1 в столбце «00». Именно к (1), так как и состояние входных сигналов, и значение выходного сигнала (z =0) после выключения В соответствуют строке 1.

Итак, правильная программа выполнена, необходимо в каждой строке рассмотреть неправильные (не по программе) изменения состояний входных сигналов. В строке 1 может сработать не А, а В, тогда идет переход от «00» к «01». Это состояние будет соответствовать такту (4), сработал элемент В (b =1), z =0, поэтому ставим здесь неустойчивый такт 4. Аналогично в строке 3, в столбце «01» проставляем неустойчивый такт 2.

Заметим, что переход в строках происходит при изменении значения только одного сигнала. В строках 2, 3, 4 кроме правильных могут быть переходы вдоль строк к столбцу «11», но по словесной формулировке такого состояния (нажаты сразу обе кнопки – «Пуск» и «Стоп») быть не может.

Ставим прочерки или оставляем пустые клетки.

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

Рисунок 3.1

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

Строим первичную таблицу переходов (Таблица 3.4). Первые 4 строки заполняются последовательно. Переход от устойчивого такта 4 при изменении состояния входных сигналов с 10 на 00 должен идти к такту 5, а не к такту 1 (как казалось бы), так как выходной набор должен быть по программе 01, а при такте (1) он равен 00.

Таблица 3.3

x ₁ x ₂	z ₁ z ₂

Таблица 3.4

N	x ₁ x ₂	z ₁	z ₂

	(1)
		(2)
			(3)
		(4)
	(5)
				(6)
			(7)
		(8)

В восьмой строке от устойчивого такта (8) переход идет к такту 1 и далее к такту (1), так как и состояние входных сигналов, и состояние выходных сигналов, требуемых по программе, и первой строки таблицы совпадают. После такта (6) переходить к такту (3) нельзя, так как далее следует такт (4) с другими выходами.

Минимизация первичной таблицы переходов

Каждая строка таблицы переходов соответствует конкретному состоянию ДУ, которое определяется состоянием элементом памяти (ЭП).Максимальное число состояний ДУ S= 2 ^k, где К – количество элементов памяти. Очевидно, что число строк первичной таблицы N £ S, т.е. N £2 ^k. Значит, от числа строк первичной таблицы переходов зависит количество элементов памяти ДУ.

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

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

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

Всевозможные случаи совместимых состояний показаны в таблице 3.5.

Таблица 3.5

Строка № 1	Строка № 2	Объединенная
(a)	a	(a)
(a)	-	(a)
a	a	a
a	-	a

В минимизированной таблице переходов в каждой строке может быть по нескольку устойчивых тактов. При объединении совместимых строк значения выходных сигналов во внимание не принимаются. Заметим, что это справедливо, если синтезируется автомат Мили, функция выходов которого имеет вид: Z (t) = j [ X (t), Y (t)], так как при одном и том же состоянии памяти Y (t) различные выходные наборы Z (t) могут быть обеспечены за счет разных входных наборов X (t). Для автомата же Мура, у которого Z (t) = j [ Y (t)], к непротиворечивым строкам можно отнести только строки с одинаковыми выходными наборами. С целью объединения максимального числа строк первичной таблицы строится диаграмма объединений по следующим правилам:

= с каждой строкой первичной таблицы переходов сопоставляется точка на плоскости с тем же номером;

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

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

Объединенные строки обозначаются буквами a, b, c … (Рисунок 3.2).

Рисунок 3.3

Рисунок 3.2

Построим диаграмму объединений для примера 3.1 (Рисунок 3.3) и минимизированную таблицу переходов (Таблица 3.6), в которой будут лишь 2 строки a и b.

Таблица 3.6

N	a b

a	(1)		-	(4)
b	(3)	(2)	-

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

Построим диаграмму (Рисунок 3.4) объединений и минимизированную таблицу переходов (Таблица 3.7) для примера 3.2, которая содержит три строки.

Таблица 3.7

x₁x₂

(1)

(2)

(5)

(4)

(3)

(8)

(7)

Рисунок 3.4

(6)

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

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

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

2) Выходные наборы, соответствующие эквивалентным состояниям, совпадают.

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

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

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

Пример 3.3 Определим эквивалентные состояния ДУ, заданного первичной таблицей переходов – выходов (Таблица 3.8).

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

Таблица 3.8

N	x ₁ x ₂	Выход
				z ₁	z ₂
	(1)
				(2)
	(3)
		(4)
		(5)
	(6)
				(7)
			(8)
		(9)
				(10)

При входном наборе 10 ДУ перейдет в устойчивое состояние 5, если в качестве исходного взять состояние 1, и в устойчивое состояние 4, если в качестве исходного взять состояние 3. При входном наборе 01 ДУ перейдет в устойчивое состояние 2, если в качестве исходного взять состояние 1, и в устойчивое состояние 7, если в качестве исходного взять состояние 6. Таким образом, устойчивое состояние 1 неэквивалентно 3-му и 6-му устойчивым состояниям и из рассмотрения исключается.

Для пары состояний 3 и 6 третий признак также не выполняется, так как для состояния 3 не определен переход при входном наборе 01, а для состояния 6 не определен переход при входном наборе 10. Однако, если произвести доопределение первичной таблицы на указанных переходах и ввести в строке 3 неустойчивое состояние 7 при входном наборе 01 и неустойчивое состояние 4 в строке 6 при входном наборе 10, мы добьемся полной эквивалентности устойчивых состояний 3 и 6. Исключим из таблицы строку 6, а вместо неустойчивого состояния 6 в строке 5 зададим переход в оставшееся эквивалентное состояние 3. Преобразованная таким образом первичная таблица изображена в виде табл. 3.9. Убеждаемся, что больше в исходной таблице эквивалентных устойчивых состояний нет.

Таблица 3.9

N	x ₁ x ₂	Выход
				z ₁	z ₂
	(1)
				(2)
	(3)
		(4)
		(5)
				(7)
			(8)
		(9)
				(10)

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

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

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

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

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

Для двоичных элементов памяти их минимальное число К_min определяется из выражения

где N – число состояний памяти ДУ, то есть число строк вторичной (минимизированной) таблицы переходов.

Так, для примера 3.2 вторичная таблица переходов (Таблица.3.7) содержит N= 3 строки. Значит, память автомата может быть построена не менее чем на двух элементах, т.е. К_min= 2. Если N= 5, то очевидно, К_min= 3 и т.д.

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

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

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

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

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

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

Определение всех переходов

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

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

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

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

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

Для примера 3.1 (Таблица 3.6) имеются только обязательные переходы:

a ® b – по столбцу 10, такт 2 переходит в (2);

в ® а – по столбцу 01, такт 4 переходит в (4).

Для примера 3.2 (Таблица 3.7) также имеются лишь обязательные переходы:

а ® в – по столбцу 11, такт 3 ® (3);

в ® c – по столбцу 01, такт 6 ® (6);

с ® а – по столбцу 00, такт 1 ® (1).

Пример 3.4 Пусть получено минимизированная таблица переходов некоторого ДУ (Таблица 3.10). Выпишем все переходы. От строки а по столбцу 01 имеется обязательный переход к строке в (4 ® (4)). Запишем аb. От строки b по столбцу 10 имеется обязательный переход к строке с (5 ®(5)) и по столбцу 00 возможный переход к строке а либо непосредственно, либо через строку с (сначала переходит в с, а затем с переходит в а). Это записывается следующим образом:

N	x₁x₂

a	(1)	(2)	(3)
b			-	(4)
c		(5)		(6)

Таблица 3.10

Переходы в одном столбце соединяются знаками дизъюнкции (а a_c), а переходы разных столбцов соединяются знаками конъюнкции. От строки с по столбцу II имеется обязательный

переход к строке а и по столбцу 00 – возможный переход в а a_в.

Запишем:

Итак, получили все переходы:

Построение диаграммы переходов

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

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

Диаграмма переходов для примера 3.1 (Рисунок 3.5) отражает 2 обязательных перехода. Диаграмма переходов для примера 3.2 (Рисунок 3.6) отражает 3 обязательных перехода. Для примера 3.3 строим диаграмму для обязательных переходов (Рисунок 3.7) и проверяем, удовлетворяет ли она возможным переходам. Убеждаемся, что удовлетворяет, дополнительных линий в диаграмму вводить не нужно.

Рисунок 3.6

Рисунок 3.7

Рисунок 3.5

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

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

Так, для примера 3.2 комбинация состояний ЭП для строки b должна быть «соседней» (отличатся состоянием только одного элемента) для строк а и с, а строки с – для строки а.

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

y ₄ y ₃

y ₃

y ₂

y ₂ y ₁

y ₁

база y ₄ y ₃ y ₂ y ₁ 4 эл-та

база y ₃ y ₂ y ₁ 3 эл-та

база y ₂ y ₁ 2 эл-та

1 эл-т

Рисунок 3.8

Карты Карно могут быть на различное число элементов, например, на 1, на 2, на 3, на 4 и т.д. (Рисунок 3.8). Каждый квадрат карты Карно имеет свой код (определенное состояние элементов) при выбранной базе. Соседние квадраты имеют соседний код.

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

Для «вхождения» диаграммы переходов в карту Карно необходимо в клетках карты расставить номера строк (а, в, с, …) таким образом, чтобы строки, между которыми есть переходы, были соседними (в соседних квадратах). Строку а целесообразно помещать в исходный квадрат (с ВС, равным 0). Если обеспечить все переходы «соседством» не удается, то нужно вводить дополнительные строки. Количество элементов карты Карно определяет и количество элементов памяти. Так, для примера 3.1 очевидно, что карта Карно нужна на один элемент (Рисунок 3.9 а).

y ₂

Из матрицы Карно очевидно, что ДУ должно иметь 1 ЭП и кодировка строк таблицы должна быть такой: а ® 0, в ® 1. Для примера 3.2 берем карту Карно на два элемента (Рисунок 3.9 б). Видим, что тремя строками а, в, с «войти» в матрицу, обеспечив соседство нужных строк, не удается. Для обеспечения перехода с ® а необходимо ввести дополнительную строку d. Получаем при базе у ₁ у ₂код строк:

а ®00;

y ₁

в ®01;

1 эл-т

с ® 11;

база y ₂ y ₁

d ® 10.

б)

а)

Рисунок 3.9

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

при изменении состояния только одного элемента памяти.

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

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

Для примера 3.1 число строк реализуемой таблицы (как следует из карты Карно) равно числу строк минимизированной – дополнительных строк нет (Таблица 3.11). Расставим в полученной таблице все переходы от а к b (по такту 2) и от b к а (по такту 4).

Для примера 2 реализуемая таблица перехода содержит два элемента памяти – у ₁и у ₂(Таблица 3.12) и будет иметь 4 строки. Строки а, b, с совпадают с одноименными строками минимизированной таблицы. Строка d служит для обеспечения перехода от с к а по столбцу 00. Значит, в строке d, в столбце 00, нужно поставить неустойчивый такт 1.

Таблица 3.11

	y	a b

a		(1)	2	-	(4)
b		(3)	(2)	-

Таблица 3.12

	y₁ y₂	x₁x₂

a	00	(1)	(2)	3	-
b		(5)	(4)	(3)	6
c		1	(8)	(7)	(6)
d			-	-	-

После этого расставим все переходы (стрелки) от неустойчивых тактов.

Таблица переходов-выходов имеет такой же вид, как и реализуемая таблица переходов, но вместо номеров тактов в ее клетках проставляются состояния элементов памяти в следующий момент времени у (t+ 1) (в числителе) и значения выходных сигналов z (t) (в знаменателе).

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

Напомним, что в таблице переходов-выходов должны быть указаны база и ВС клеток.

Состояния элементов памяти у (t+ 1) в устойчивых тактах соответствуют состояниям ЭП той строки у (t), в которой находится устойчивый такт. Например, если строка имеет код 011, то значения у (t+ 1) состояний элементов памяти для всех устойчивых тактов данной строки равны 011.

Физически это означает, что в устойчивых тактах состояния ЭП синтезируемого ДУ в моменты времени t и t+ 1 должны совпадать, лишь при этом условии не последует изменения внутреннего состояния ДУ.

Вместо номера неустойчивого такта следует проставить значения состояний ЭП у (t+ 1), соответствующие комбинациям их состояний в той строке, к которой осуществляется переход от рассматриваемого неустойчивого такта. Действительно, для осуществления перехода ДУ к очередному внутреннему состоянию необходимо чтобы в предыдущем внутреннем состоянии были созданы условия для такого перехода.

Значения выходных сигналов (проводимостей цепей исполнительных элементов) берут из первичной таблицы переходов.

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

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

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

1) Значения выходных сигналов ДУ в неустойчивых тактах безразличны.

В таком случае клетки, соответствующие неустойчивым тактам, по выходным

сигналам остаются незаполненными.

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

Тогда значения выходных сигналов в неустойчивых тактах должны соответствовать

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

номера.

3) Состояния выходных сигналов ДУ должны изменяться как можно позже при изменении входных сигналов.

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

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

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

Построим таблицу переходов-выходов для примера 3.1 (Таблица 3.13). Сначала строим бланк таблицы. Затем на основании реализуемой таблицы переходов проставляем в таблице переходов-выходов, в клетках устойчивых тактов (1), (2), (3), (4) в числителе, значение элемента памяти у (t+ 1) по его значению у (t) в данной строке, т.е. по коду строки. С остальными клетками поступаем по правилам, изложенным выше. Из клетки с ВС=2 переход идет в клетку с ВС=6, значит, в клетке 2 ставим у (t+ 1)=1, что соответствует состоянию у (t)=1 строки, в которой расположена клетка 6. Из клетки с ВС=5 переход идет в клетку с ВС=1, следовательно в клетке 5 записываем у (t+ 1)=0, что соответствует у (t)=0 клетки 1.

Таблица 3.13

	2² у

a		0/0 ⁰	1/0 ²	¾ ³	0/0 ¹
b		1/1 ⁴	1/0 ⁶	¾ ⁷	0/0 ⁵

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

На основании реализуемой таблицы переходов (Таблица 3.12) и первичной таблицы переходов-выходов строим таблицу переходов–выходов для примера 2 (Таблица 3.14).

Таблица 3.14

S_i (t) y ₁ y ₂	x ₁ x ₂

	00/00 ⁰	00/00 ²	01/10 ³	¾ ¹
	01/01 ⁴	01/11 ⁶	01/10 ⁷	11/10 ⁵
	10/00 ¹²	11/10 ¹⁴	11/10 ¹⁵	11/10 ¹³
	00/00 ⁸	¾ ¹⁰	¾ ¹¹	¾ ⁹	y ₁ y ₂(t+ 1) / z ₁ z ₂(t)

Отметим еще раз, что в обозначениях столбцов таблицы переходов-выходов записываются комбинации значений входных сигналов, а в обозначениях строк – комбинации состояний элементов памяти, которые соответствовали им при решении задачи кодирования. В клетках таблицы в числителе проставляются комбинации состояний элементов памяти, а в знаменателе – комбинации значений выходных сигналов, соответствующие состояниям элементов памяти и значениям входных сигналов тех строк и столбцов на пересечении которых находится данная клетка.

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

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

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

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

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

Если синтезируется контактное ДУ или, если в качестве элементов памяти при синтезе ДУ используются линии задержки на одни такт, то таблица переходов-выходов (относительно элементов памяти) однозначно описывает условия функционирования схемы управления памятью. Тогда таблица возбуждений ЭП дискретного устройства совпадает с таблицей переходов-выходов (для элементов памяти). Это следует из того, что в таком случае значения сигналов u ₁, u ₂, …,u_l, управляющих памятью ДУ (подаваемых на элементы памяти), всегда совпадают с состояниями элементов памяти в следующем такте, т.е.

u (t) = у (t+ 1).

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

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

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

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

1) Выбирается тип элементов памяти.

2) Строится координатная сетка таблицы возбуждений соответствующая таблице переходов-выходов синтезируемого ДУ.

3) По таблице переходов-выходов (для элементов памяти) выбирается в одной строке пара состояний ДУ S_i (t) и S_i (t+ 1).

4) Пара состояний ДУ <S_i (t), S_i (t+ 1)> разбивается на пары состояний элементов памяти

< у ₁(t), у ₁(t+ 1)>, < у ₂(t), у ₂(t+ 1)>, …, < у_k (t), у_k (t+ 1)> - по числу элементов памяти.

5) По таблице переходов или таблице входов используемого элемента памяти определяются для каждой пары < у_i (t), у_i (t+ 1)> входные сигналы u_i (t) переводящие i -й элемент памяти из состояния у_i (t) в состояние у_i (t+ 1).

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

7) Пп. 3-6 выполняются для всех заполненных клеток таблицы переходов-выходов.

Изложенную методику построения таблицы возбуждений поясним на примере.

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

Напомним, что элемент памяти – триггер с раздельными входами (RS - триггер) – это логический элемент с двумя устойчивыми состояниями (Рисунок 3.10), имеющий два входа: единичный вход u ¹ и нулевой вход u ⁰. При значениях u ¹ = 1, u ⁰ = 0 триггер принимает состояние 1 (у = 1), а при значениях u ¹= 0, u ⁰ = 1 – состояние 0 (у = 0). При входном наборе u ¹ =u ⁰ = 0 состояние триггера не изменяется и сохраняется равным его предыдущему значению. Входной набор u ¹ =u ⁰ = 1 не используется.

u ¹

u ⁰

Таблица переходов и таблица входов RS – триггера представлены на таблицах 3.15 и 3.16. Таблица входов легко получается из таблицы переходов. Она показывает какие сигналы надо подать на триггер, находящийся в состоянии y (t), чтобы он перешел в состояние y (t+ 1).

Рисунок 3.10

Таблица 3.16

Таблица 3.15

y (t)	u ¹ u ⁰

			---
			---
y (t)	y (t+ 1)

	0~
		~0

u ¹ u ⁰

y (t+ 1)

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

Таблица 3.17

S_i (t) y ₁ y ₂	x ₁ x ₂

	0~,0~ ⁰	0~,0~ ²	0~,10 ³	¾ ¹
	0~,~0 ⁴	0~,~0 ⁶	0~,~0 ⁷	10,~0 ⁵
	~0,01 ¹²	~0,~0 ¹⁴	~0,~0 ¹⁵	~0,~0 ¹³
	01,0~ ⁸	¾ ¹⁰	¾ ¹¹	¾ ⁹

Для пояснения методики выберем в таблице переходов-выходов (Таблица 3.14) любую клетку, например клетку с весовым состоянием 3. Она соответствует состоянию ДУ 01 в момент времени t+ 1, т.е. элемент памяти y₁ должен находиться в состоянии 0, а элемент памяти y ₂ – в состоянии 1.

В момент времени t состояние ДУ определяется кодом строки 00, в которой находится рассматриваемая клетка, то есть состояния элементов памяти y ₁и y ₂ равны 0.

Образуем пару состояний дискретного устройства:

< S_i (t), S_i (t+ 1)> = <00, 01>.

Разделяем эту пару состояний ДУ на две пары состояний элементов памяти – по числу элементов:

< у ₁(t), у ₁(t+ 1)> = <0,0>,

< у ₂ (t), у ₂(t+ 1)> = <0,1>.

Отсюда видно, что элемент памяти у₁ был в состоянии 0 и остается в нем, а элемент памяти у₂ меняет свое состояние с 0 на 1.

По таблице входов (Таблица 3.16) RS – триггера или по таблице переходов (Таблица 3.15) определяем входные сигналы u_i_. ¹, u_i_. ⁰, которые нужно подать на каждый элемент памяти, чтобы обеспечить указанные пары состояний:

= 0~

= 10.

Данная запись означает следующее. Для того, чтобы элемент памяти у₁, находящийся в момент времени t в состоянии 0, остался в этом же состоянии в момент времени t +1, на его единичный вход () должен быть подан сигнал 0, на нулевой вход () может быть подан любой сигнал: или 0, или 1 (безразличный вход), а для того, чтобы элемент памяти у ₂, находящийся в момент времени t в состоянии 0, перешел в момент времени t +1 в состояние 1, на его единичный вход () должен быть подан сигнал 1, а на нулевой вход () – сигнал 0. Найденные значения сигналов управления памятью

< u ₁¹ u ₁⁰(t), u ₂¹ u ₂⁰(t)> = <0~, 10>

записываются в таблице возбуждений (Таблица 3.17) в клетку с весовым состоянием 3.

Указанная процедура выполняется для всех заполненных клеток таблицы переходов-выходов (Таблица 3.14).

В результате получаем для синтезируемого ДУ таблицу возбуждений (Таблица 3.17).

Таким образом, в результате решения задачи синтеза ДУ получена структурная схема, приведенная на рисунке 3.11.

Блок памяти синтезируемого ДУ построен на двух триггерах с раздельными входами Т₁ и Т₂. Условия функционирования блока формирования выходных сигналов описываются таблицей переходов-выходов (Таблица 3.14) только для выходных сигналов. Условия функционирования блока управления памятью описываются таблицей возбуждений (Таблица 3.17), которая является таблицей соответствия, записанной в компактной форме для нескольких функций u ₁¹, u ₁⁰, u ₂¹, u ₂⁰.