 |
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк
[26]
Например, для автомата, граф которого изображен на рис.3.8, матрица соединений может быть представлена в виде (3.9).
Рис.3.8. Граф конечного автомата к примеру разбиения на
подавтоматы
2 | 5 | 1 | 3 | 6 | 0 | 4 | |
0 | 2/0 | 0/1 | 0 | 1/1 | 0 | 0 | 2 |
0/1 | 0 | 0 | 1/0 | 2/1 | 0 | 0 | 5 |
0 | 0 | 1/W2/0 | 0 | 0/0 | 0 | 0 | 1 |
0 | 0 | l/0v2/l | о/о | 0 | 0 | 0 | 3 |
0 | 0 | 0 | 0/lv2/0 | 1/0 | 0 | 0 | 6 |
0 | 0 | 0 | 0 | 0 | 0/1 | l/0v2/l | 0 |
0 | 0 | 0 | 0 | 0 | 1/OvO/l | 0 | 4 |
Из (3.9) следует, что Sj={2, 5} составляет преходящий подавтомат, S2={1, 3, 6} - тупиковый подавтомат и S3={0,4} - изолированный подавтомат. Если начальное состояние принадлежит множеству S2, то можно упростить автомат, исключив состояние SjUS3={2, 5, 0, 4}, а в случае принадлежности начального состояния множеству 8з автомат упрощается исключением состояний S1U S2={f2, 5, 1, 3, 6}.
3.9. СИНТЕЗ КОНЕЧНЫХ АВТОМАТОВ
Синтез конечного автомата заключается в построении такого автомата , который бы имел заданные характеристики. Фактически реализация конечного автомата сводится к синтезу соответствующей комбинационной
схемы, преобразующей входные переменные x(h) с учетом внутренних состояний s(h) в выходные переменные y(h) и следующие внутренние состояния s(h+l) в соответствии с заданными выходной v(h) и переходной функциями \\f(h+I) [2]. Для сохранения состояния s(h+l) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти. Поскольку логические элементы, на которых реализуются комбинационные схемы, а также элементы памяти имеют два устойчивых состояния,
соответствующих логической "1" и "О", то для их работы требуются входные символы (переменные), имеющие два состояния - логического "0" и "1". При этом необходимо осуществить преобразование общей таблицы переходов автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств X, S, Y пронумерованы порядковыми числами, начиная с нуля , то им соответствуют коды , представляющие собой двоичные эквиваленты этих чисел. Так, для автомата, граф которого изображен на рис.3.9, общая таблица переходов представлена в таблице 3.5.
Преобразуем таблицу 3.5 в таблицу 3.6 - таблицу соответствия, и затем в таблицу 3.7 -таблицу соответствия в двоичном алфавите.
Таблица 3.5 Общая таблица переходов
x(h) | 0 | 1 |
s(h) | y/(h+l)/v(h) | |
0 | 1/1 | 2/1 |
1 | 2/0 | 1/1 |
2 | 0/1 | 2/0 |
ТаблицаЗ.6
Таблица соответствия
x(h) | ООО | 1 1 1 |
s(h) | 0 1 2 | 0 1 2 |
ф+1) | 120 | 2 1 2 |
v(h) | 1 0 1 | 1 0 1 |
Таблица 3.7
Таблица соответствия в двоичном алфавите
x(h) | 000 | 111 |
ы f sMk) | 0 1 0 | 0 1 0 |
S(h) i s2=(h) | 00 1 | 00 1 |
v~ , ;) (W=(h+1) | 100 | 0 1 0 |
щп+1) < I y/2=(h+l) | 0 1 0 | 1 0 1 |
v(h) | 1 0 1 | 1 1 0 |
Представим функцию переходов y/(h+l)=x*s булевой функцией, записанной в СДНФ:
y/jfh + 1) = Sj(h + 1) = xSjS2 v xs,s2
y/2(h + 1) = s2(h + l) = xs1s2 vxSjS2 vxs1s2
(3.10)
Функцию выходов v(h)=X*S представим булевой функцией в СКНФ:
v(h) = y(h) = (xvsj v s2)(x v st v s2)
(3.11)
Из (3.10),(3.11) видно, что комбинационная схема (КС) должна иметь три входа, соответствующие входной переменной x(h) и переменным состояниям Sj(h), s2(h), а также три выхода, соответствующие переменным состояниям S](h+1), s2(h+l) и переменной выхода y(h). Таким образом, структурная схема рассматриваемого конечного автомата примет вид, показанный на рис.3.10 , где ЭП - элементы памяти, а его принципиальная схема - вид, показанный на рис.3.11, где в качестве ЭП используются RS триггеры [10-12].
Рис.3.10. Структурная схема конечного автомата