Канонические уравнения автоматной функции

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

Обратимся к диаграмме Мура для автоматной функции . Пусть в момент времени автомат находился в состоянии ,

 

Рис. 5.

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

Пусть в момент переменная описывает значение входного сигнала, описывает значение состояния, - значение выходного сигнала, тогда

Эти уравнения называются каноническими уравнениями автоматной функции в векторной форме. Функция называется функцией выходов, – функцией переходов. Если задано начальное состояние автомата , автомат называется инициальным. – класс эквивалентности, к которому относится корень занумерованного дерева, часто =0, но это не обязательное требование.

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

В предыдущем параграфе мы рассматривали автоматную функцию, вырабатывающую одну выходную последовательность Не меняя рассуждений и лишь усложнив запись, можно считать, что автомат имеет выходов и вырабатывает выходную последовательность Запишем канонические уравнения в скалярной форме для этого более общего случая.

.

 

Пример 4. Получим канонические уравнения автоматной функции, рассмотренной в примере 1.

Построим сначала каноническую таблицу. Вес этой функции равен , поэтому . В левой части канонической таблицы стоят переменные и , в правой части – функции и , значения которых берем с усеченного дерева (рис. 3) или с диаграммы Мура (рис. 4). Если было равно (корень дерева) и входной сигнал был , то и переходим в состояние . Если было равно 1, то по дуге, соответствующей входному сигналу переходим снова в состояние , но . Сняв информацию со всех дуг усеченного дерева, получим таблицу.

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

 

 

 

Пример 5. Построить канонические уравнения для автоматной функции, имеющей один вход и один выход:

Построим сначала информативное дерево,

 

 

Рис. 6.

Найдем вес функции , построим усеченное дерево (рис. 7).

 

Рис. 7.

Диаграмма Мура для этой функции изображена на рис. 8 сплошной линией

Рис. 8.

Закодируем состояния , , и построим каноническую таблицу:

 

Функции , , заданы на 6 наборах из 8, так как набор принимает только 3 значения. Доопределим наши функции на наборах (011) и (111) таким образом, чтобы получить наиболее простые формулы для их задания. Такое доопределение означает, что мы ввели дополнительное состояние и две дуги, которые на диаграмме Мура (рис.8) изображены пунктиром. Введенное состояние будет недостижимым, т.к. нет ни одной дуги, входящей в эту вершину графа, и не скажется на функционировании автомата, хотя вид полученных уравнений может быть различным. Запишем канонические уравнения:

.

В общем случае функции , задаются на наборах длины . Доопределив их на недостающих, мы получим булевы функции и система канонических уравнений примет вид:

 

Пример 6. Построить диаграмму Мура, каноническую таблицу и канонические уравнения для функции . (Здесь означает бесконечную последовательность 1).

Построим информативное дерево

 

Рис. 9

Рис. 10

Состояние в корне обозначим 0 (хотя это не обязательно), вершины первого яруса порождают одинаковые поддеревья, отличные от основного дерева, обозначим их 1. Вершины третьего яруса порождают одинаковые поддеревья, отнесем их ко второму классу эквивалентности. Итак, вес дерева равен 3. Соответствующее усеченное дерево приведено на рис. 10, диаграмма Мура – на рис. 11.

 

Рис. 11

Каноническая таблица для этой функции имеет вид

 

Выделенные пунктиром строчки, соответствующие недостижимому состоянию 3, заполним произвольным образом.

Для функций и переменная, – фиктивная.

запишем в виде ДНФ:

.

 

Пример 7. Построить канонические уравнения функции , если есть – цифра после запятой в двоичном разложении числа 5/7.

Двоичный код числа будет не зависит от , зависит только от момента времени: , и эта последовательность периодически повторяется. Поэтому можно сразу строить усеченное дерево (рис. 12) и диаграмму Мура (рис. 13).

 

Рис. 12

Рис. 13

Каноническая таблица для этой функции имеет вид

Мы получаем простые канонические уравнения

 

Пример 8. Найти вес автоматной функции, заданной диаграммой Мура. Состояние 4 – недостижимое состояние, поэтому эту вершину вместе с выходящими дугами можно убрать.

Рис. 14

Построим дерево; состояние 1~2, 5~0~3 и вес равен 2.

Рис. 15

Построили усеченное дерево веса 2 и приведенную (без лишних вершин) диаграмму Мура

Рис. 16