Структурный синтез цифровых автоматов
Структурный синтез ЦА выполняется с привязкой к запоминающим элементам и внутренней структуре. Структурный синтез включает:
- кодирование входных, выходных сигналов и состояний автомата;
- выбор элементов памяти;
- получение булевых функций возбуждения запоминающих элементов и выходов автомата
- построение схемы автомата
В простейшем случае под кодированием понимают назначение всем символам алфавитов двоичных кодов. Как правило, длину кода выбирают исходя из количества букв в алфавите. Например, если у автомата три возможных входных значения, то каждое значение кодируется двумя битами, если 5, то уже тремя.
1-2 буквы – 1 бит
2-4 буквы – 2 бита
3-8 букв – 3 бита
и т.д.
При таком подходе к кодированию состояний автомата сложность КС1 и КС2 может быть далеко не оптимальной. А при переключении автомата из состояния в состояние следует стремиться к минимальному количеству переключаемых триггеров.
Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе 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 (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).
Рассмотрим применение эвристического алгоритма на конкретном примере автомата, заданного таблицами переходов и выходов (рис.41.). Для данного автомата можно построить ориентированный граф (без учета петель), представленный на рисунке 11.6. На каждом ребре указан его вес.