Методика синтеза Хафмена-Глушкова

1. Задание КА в формализованном виде (автоматная таблица, граф переходов, регулярное выражение, регулярная грамматика, источник).

2. Минимизация числа состояний автомата, детерминация источника.

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

4. Реализация системы логических уравнений схемой из логических элементов, взятой из функционально-полного базиса (ФПБ).

Пример: Синтез DL триггера.

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

, ,, ,

Недостатки схемы синтеза Хафмена-Глушкова:

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

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

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

Оценка сложности программной реализации автоматов

Операционный автомат — это КА с задаваемой из вне функцией переходов и выходов.

A=D*K d:D*K*Q®Q , l:D*K*Q ®R

Задавая К мы можем выполнять различные операции.