Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 43 стр.

    Глава 3. Минимизация систем канонических
                   уравнений
      В данном разделе рассматриваются вопросы минимизации систем
канонических уравнений, являющихся математической моделью как
детерминированных, так и недетерминированных автоматов.
      При формализации алгоритма функционирования автомата на
начальных языках, в первую очередь, составляется формальное описание
словесного алгоритма и проверяется его адекватность с помощью
моделирования. При этом не особенно обращается внимание на возможную
избыточность описания. Так при использовании языка ОСА в описании
могут быть, например, избыточные операторные и условные вершины. При
реализации алгоритма желательно устранение этой избыточности, т. к. она
ведет, как правило, к увеличению стоимости реализации. В связи с этим
после синтеза СКУ ее необходимо минимизировать.
      Минимизация СКУ включает два этапа. Один из них используется для
минимизации каждого из уравнений СКУ за счет минимизации булевых
функций, представляющих собой ДНФ частных входных сигналов, входящих
в уравнения СКУ перед одинаковыми предшествующими событиями. Такая
минимизация может быть выполнена с использованием известных методов
минимизации булевых функций. В примере детерминированной СКУ,
построенной в предыдущем разделе, такая минимизация выполнялась.
Второй этап минимизации СКУ связан с минимизацией числа событий,
представленных в СКУ. В качестве основного метода минимизации числа
событий СКУ в данном пособии рассматривается метод минимизации на
основе определения эквивалентного разбиения событий. Кроме этого метода
будет рассмотрен еще один метод минимизации СКУ, который базируется на
использовании дополнительной информации о входных сигналах,
называемой «учет распределения сдвигов» [23-26]. Этот метод в раде случаев
приводит как к минимизации числа событий, так и минимизации частных
входных сигналов в СКУ.
      В том случае, если СКУ недетерминирована, ее минимизацию
целесообразно выполнить до операции детерминизации, т. к. в противном
случае детерминизация может потребовать большой объем работ. По этой же
причине, если функционирование автомата задано на языке ОСАП, то
минимизацию НД СКУ целесообразно выполнять отдельно для каждой
частной СКУ, формализующей события в соответствующей ветви алгоритма.
      Прежде чем приступить к выполнению основных этапов минимизации
СКУ необходимо убедиться, что исходная СКУ не содержит недостижимых
событий. Для этого необходимо по исходной СКУ построить прямую
таблицу переходов, которая должна строиться по такой же процедуре, что и
прямая таблица переходов при детерминизации НДА, т. е. построение

                                                                        43