Прикладная теория цифровых автоматов

Подадим полученное выражение согласно с заданным базисом ИЛИ-НЕ.

Для реализации функции  по последнему выражению необходимо один элемент 2И, два элемента 3И, один элемент 2ИЛИ, один элемент3ИЛИ и один элемент 2ИЛИ-НЕ.

Как видно из полученной схемы для ее реализации необходимы элементы с  = 2ИЛИ-НЕ 6 (в отличие от  исходной  с = 4ИЛИ-НЕ 5) и ранг схемы увеличился до 4, что приводит к увеличению задержки срабатывания схемы. Но, как известно, чем проще элементы, тем меньше вероятность сбоя.

Построим функциональную схему, что реализует выражение:

 

 

 

Рис. 1. Функциональная схема, полученная на основании факторного алгоритма согласно с заданным базисом ИЛИ-НЕ.

 

Анализ комбинационных схем  методом  p-алгоритма.

При данном методе,  ищутся наборы входных переменных, обеспечивающих заданное значение на выходе КС. Наборы, обеспечивающие на выходе КС логическую 1, образуют так называемое  единичное покрытие  .  Аналогично, входные наборы,  обеспечивающие на выходе КС логический 0,  образуют нулевое покрытие .  Рассмотрим покрытия для  логического элементов (см.таблица 11) , выполняющего  функцию . 

                                            Таблица 11

№ элемента	Функция	Входы
1	НЕ
2	НЕ
3	2ИЛИ-НЕ
4	3ИЛИ
5	2ИЛИ-НЕ
6	3ИЛИ
7	2ИЛИ-НЕ

 

Анализа КС (рис 2. ) методом p - алгоритма представлен в табл. 12. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии     для     обеспечения      заданного    значения       выходного       сигнала. Поэтому, при замене одного из значений в строке соответствующим покрытием, все остальные значения для других переменных в этой строке должны присутствовать совместно с этим покрытием.

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

 

Рис. 2. Схема  функции.

Получение единичного покрытия

                                                                                 Таблица 12

X1	X2	X3	X4	X5	e1	e2	e3	e4	е5	e6	e7	Оператор
-	-	-	-	-	-	-	-	-	-	-	1	-----------
-	-	-	-	-	-	-	-	-	-	-	0	2ИЛИ-НЕ
-	-	-	-	-	-	-	-	0
-	-	-	-	х	-	-	х	-	1			3ИЛИ
-	-	-	-	х	-	-	1		х
-	-	-	-	1			х		х
-	-	-	1	-	-	0						2ИЛИ-НЕ
-	-	-	-	-	0
-	х	х	1									3ИЛИ
-	х	1	х
-	1	х	х
-	-	0										2ИЛИ-НЕ
0
-	-	-	0									НЕ
0												НЕ

 

    

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Расчет и построение ГСА

Граф-схема алгоритма состоит  их четырех блоков E, F, G,H и вершин “BEGIN” и “END”. Каждый блок имеет два входа (А, В) и два выходы (C, D). Блоки E, F, G,H выбираем на основании чисел А=39, В=42, С=07, А+В+С=93 по таким правилам:

• блок Е имеет схему блока по номеру А(MOD 5);
• блок Е имеет схему блока по номеру B(MOD 5)
• блок Е имеет схему блока по номеру C(MOD 5)
• блок Е имеет схему блока по номеру А+B+C(MOD 5)

Блоки E, F, G, H соединяются между собой согласно со структурной схемой графу, что имеет вид:

N (MOD 4), где N- две последний цифры номера зачетной книжки.

Тип триггера выбирается по значению числа A (MOD 4):

• Мили – RS;
• Мура – D.

Определив номера блоков и структуру  граф-схемы алгоритма (ГСА). По этим данным построили ГСА см. рис. 3 (Приложение 1).

Серия интегральных микросхем для  построения принципиальных схем синтезированных  автоматов будут использоваться КР153

Синтез микропрограммных автоматов по граф-схеме алгаритма.

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

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

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

Абстрактный  синтез микропрограммного  автомата по ГСА осуществляется в  два этапа:

1. Получение отмеченной ГСА.

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

 

Проектируем руководящий автомат  Мили.

СИНТЕЗ  АВТОМАТА  МИЛИ

На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a₁, a₂,.. по следующим правилам:

1) символом а₁ отмечают вход вершины, следующей за начальной, а также вход конечной вершины;

2) входы всех вершин следующих за операторными, должны быть отмечены;

3) входы различных вершин, за  исключением конечной, отмечаются  различными символами;

4) если вход вершины отмечается, то только одним символом.

Ясно, что для проведения отметок  потребуется конечное число символов а₁,...,a_m. Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа - перехода к графу или таблицам переходов-выходов. ГСА, отмеченной для автомата Мили, представлен на рис.4 (Приложение 2).

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

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

На основании отмеченной ГСА  можно построить таблицу переходов-выходов. Для микропрограммных автоматов таблица переходов-выходов строится в виде списка и различаются прямая и обратная таблицы. Для данного автомата прямая таблица представлена в табл. 13., обратная - в табл. 14.

 

                               Таблица 13                                                  Таблица 14

 

Am	As	X	Y		Am	As	X	Y
а1	а2	1			а22	а1
а2	а5				а23
	а7				а24			-
а3	а4	1			а1	а2	1
а4	а5				а10	а3		у3,у6
	а6				а3	а4	1
а5	а6	1			а12
а6	а8				а2	а5
	а9				а4
а7	а9	1			а4	а6
а8	а10	1			а5		1
а9	а11	1			а2	а7
а10	а3				а6	а8
	а11				а6	а9
	а12				а7		1
а11	а12				а8	а10	1
	а13				а9	а11	1
а12	а4				а10
	а16				а10	а12
а13	а16	1			а11
а14	а15	1			а11	а13
а15	а17				а22	а14
	а18				а14	а15	1
	а20				а24
а16	а17	1			а12	а16
а17	а18				а13		1
	а19				а15	а17
а18	а21				а16		1
	а22				а15	а18
а19	а21	1			а17
а20	а22	1			а17	а19
а21	а23	1			а15	а20
а22	а1				а18	а21
	а14				а19		1
	а24				а18	а22
а23	а1				а20		1
	а24				а21	а23	1
а24	а15				а22	а24
	а1		-		а23

 

 

Эвристический алгоритм кодирования.

Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе  T,  RS,  JK-триггеров.  Для данных типов триггеров (в отличие от D-триггеров!) на  каждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата.

Введем некоторые определения.

Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из а_i и а_j или наоборот.

Обозначим q(i, j) число всевозможных переходов автомата из а_i в а_j. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребра р(i, j) = q(i, j) + q(j, i).

Введем функцию  w(i, j) = р(i, j)× d(i, j),  где d(i, j) – число компонентов, которыми коды состояний а_i в а_j отличаются друг от друга (т.е. кодовое расстояние между кодами а_i в а_j).

       Функция w(i ,j) имеет простой физический смысл. Переход автомата из а_i в а_j (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаются  коды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем   ребрам, соединяющим состояниям  а_i и а_j  (их  число p(i, j)!) всего переключится количество триггеров, равное p(i, j)×d(i ,j) =w(i ,j).

Но тогда функция   показывает, сколько всего переключается триггеров при прохождении автомата по всем возможным переходам. Функция w показывает, сколько всего единиц в функции возбуждения, т.е. позволяет оценивать сложность комбинационной схемы автомата. W можно рассматривать как некую целевую функцию, минимум которой определит такое кодирование, при котором комбинационная схема наиболее простая. Кстати, минимальное кодовое расстояние между различными состояниями равно 1 и если удается закодировать все состояния соседним кодированием, то очевидно, что w будет минимально возможным и равным ,  т.е.  суммарному числу переходов для автомата.

Из выражения для w следует,  что переход из а_i в а_i, для которого d(i,i)=0,  не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).

 

 

Эвристический алгоритм состоит из следующих шагов.

 

1. Строим  матрицу , состоящую из всех пар номеров (i, j), для которых р(i, j) ¹ 0 (т.е. в автомате есть переход из а_i в а_j или наоборот) и i<j. Для каждой пары в матрице указываем  ее  вес р(i, j), совпадающий с весом ребра соединяющего а_i и а_j.