[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

Реализация КА

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

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

• входные и выходные сигналы и внутренние состояния автомата кодируются двоичными кодами;
• по таблицам переходов и выходов составляются кодированные таблицы переходов и выходов - фактически табличное задание отображения F (см. рис. 2);
• по кодированным таблицам переходов и выходов проводится минимизация двоичных функций, и они реализуются в заданном базисе;
• решаются схемотехнические вопросы синхронизации - привязки моментов выдачи выходного сигнала и изменения состояния внутренней памяти к моментам поступления входных сигналов на вход автомата.

Рис. 3. Схема программы, реализующей поведение автомата примера 1

Рассмотрим реализацию автомата примера 1.
Входных сигналов два; мы их закодируем так: "2" <0>, "5" <1>.
Выходных сигналов (операций) шесть.
Закодируем их "у0" <000>; "y1" <001>; ..., "у5" <101>.
Внутренних состояний у автомата четыре.
Закодируем их "s0" <00>; "s1" <01>; "s2" <10>; "s3" <11>.
Структурная схема этого автомата после двоичного кодирования имеет следующий вид:

Таблица 2 - это кодированная таблица переходов и выходов автомата. Один двоичный разряд х кодирует два входных сигнала, пары двоичных разрядов ql, q2; Q1, Q2 кодируют соответственно текущее и следующее состояния, разряды z1, z2, z3 кодируют выходной сигнал.

Таблица 2

x	q1	q2	Q1	Q2	z1	z2	z3
0	0	0	0	1	0	1	0
0	0	1	1	0	0	0	1
0	1	0	1	0	0	0	0
0	1	1	0	1	0	1	0
1	0	0	1	1	1	0	0
1	0	1	0	0	0	1	1
1	1	0	0	0	0	1	1
1	1	1	1	1	1	0	1

Рис. 4. Функциональная схема, реализующая автомат примера 1. Выделены функциональный блок и блок памяти автомата. Семантика тактового импульса t: "наступило событие на входе автомата"

После минимизации в классе ДНФ получим аналитические выражения для всех двоичных функций, реализация которых показана на рис. 4. Блоки Т1 и Т2 - триггеры, которые запоминают двоичный сигнал до прихода следующего. Вход t в триггере - синхронизационный вход, разрешающий переключение триггера.
Сигнал на этом входе должен появляться в момент наступления события получения автоматом очередного входного сигнала от окружения. Этот же синхросигнал обеспечивает получение на выходе импульсного значения выходного сигнала У как реакцию на поступление сигнала на вход автомата.

Рисунок 4 дает схемную реализацию устройства, реализующего функционирование автомата примера 1. Если вход X автомата соединить с устройством считывания очередной оценки (два варианта этой оценки кодируются 0 и 1), а выход У после дешифрирования соединить с исполнительными устройствами, выполняющими, например, награждение сына, его наказание, включающими проигрывание похвалы или укоризны, то на эту схему можно возложить воспитание сына в соответствии с приведенным "умным" алгоритмом, принимающим во внимание историю его учебы.

Часто как входные, так и выходные сигналы автомата кодируются не произвольным образом: их кодировка обычно предопределена конкретным применением автомата. В то же время кодирование внутренних состояний автомата на логике то функционирования никак не сказывается (при любом кодировании состояний автомат будет реализовывать то же отображение входных последовательностей на входные). Однако различное кодирование может влиять на надежность устройства, скорость его переключения, простоту реализации логического блока и т. до сих пор ведутся исследования по проблеме оптимального кодирования состояний конечного автомата при различных критериях оптимальности. Например, в докладе, представленном на недавней конференции в Женеве, обсуждается проблема такого кодирования состояний автомата, которое дает реализацию с минимальной рассеиваемой мощностью в элементах памяти. Для этого на определенном типе входных последовательностей учитывается частота переключения между парами всех состояний и наиболее часто переключаемые пары состояний кодируются "близкими" по Хеммингу кодами. Это в среднем уменьшает число переключаемых триггеров при работе автомата.

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]