Автоматное моделирование алгоритмов

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

Рис. 2.17 Компоненты блок-схемы алгоритма.

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

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

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

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

Схема взаимодействия операционного и управляющего автоматов показана на рис. 2.18.

Рис. 2.18 Операционный и управляющий автоматы.

В дискретные моменты времени по каналу 1 на вход операционного автомата поступает обрабатываемая информация, а по каналу 2 снимают результаты ее обработки. По каналу 3 в управляющий автомат поступает сообщение об исполнении шага алгоритма и о результатах проверки условий, а по каналу 4 в операционный автомат - управляющее воздействие для исполнения очередного шага алгоритма. По каналу 5 в управляющий автомат поступает команда для исполнения оператора, а по каналу 6 - сообщение об его исполнении.

Для моделирования управляющего автомата необходимо выполнить разметку блок-схемы алгоритма, определить множество входных сигналов и внутренних состояний, найти правила формирования выходных сигналов и переходов внутренних состояний. Ниже рассмотрены автоматные модели управляющего автомата на безе автоматов Мили и Мура.

Дата добавления: 2015-07-26; просмотров: 162; Нарушение авторских прав

Мы поможем в написании ваших работ!