Автоматное моделирование алгоритмов.
Для наглядного представления алгоритма используют блок-схемы в виде ориентированного графа. Основными элементами такого графа являются блоки "операторы" и "предикаты" и дуги, указывающие возможные пути на графе. Кроме того, есть единственный блок "начало", из которого исходит единственная дуга и единственный блок "конец", из которого не исходит ни одна дуга (см. рис 2.17).
Рис. 2.17 Компоненты блок-схемы алгоритма.
Каждый шаг алгоритмического процесса - это этап в обработке информации блоками "оператор" или "предикат" и передача результатов в очередной блок. В блоке "оператор" выполняются функциональные преобразования информации (например, арифметические операции, хранение или передача информации) и результаты передаются по единственной дуге на выход. В блоке "предикат" проверяются условия (например, арифметические или логические) и результаты передаются по одной из двух дуг выхода: "да" или "нет", что определяет выбор пути на графе алгоритма.
Важной особенностью блок-схемы является то, что связи, которые она описывает, не зависят от того являются ли операции элементарными или представляют собой самостоятельные алгоритмы.
Для автоматного моделирования необходимо рассматривать раздельно процессы обработки информации и выбора маршрута на графе алгоритма. Для решения первой задачи создают операционный автомат, а для решения второй - управляющий.
Автоматное моделирование процесса обработки информации можно рассматривать на макроуровне, когда каждый блок "оператор" представляет собой самостоятельный алгоритм, и на микроуровне, когда каждый блок "оператор" представляет элементарную операцию. Первый подход нашел применение в проектировании дискретных устройств, работающих в асинхронном режиме, второй - в проектированию вычислительных комплексов, работающих в синхронном режиме.
Схема взаимодействия операционного и управляющего автоматов показана на рис. 2.18.
Рис. 2.18 Операционный и управляющий автоматы.
Операционный автомат для разнообразной обработки операндов содержит цепи приема операндов, регистры операндов и результатов, цепи выдачи результатов, преобразователи кодов, сумматор, схемы сдвига, анализа полученных результатов (рис. 32).
Операционные автоматы делятся на блочные и многофункциональные, синхронные и асинхронные, на автоматы обратного и дополнительного кодов, на автоматы двоичной, десятичной систем исчисления и другие.
В блочном автомате для каждой операции предусмотрен соответствующий блок, в многофункциональном автомате единая структура перестраивается с учетом каждой операции.
В автомате с синхронным управлением на любую операцию затрачивается одинаковое время ( время самой продолжительной операции), в автомате с асинхронным управлением время каждой операции различно.
ОА имеет определенные характеристики: набор операций, точность расчетов, быстродействие, код, систему счисления и другие.
В дискретные моменты времени по каналу 1 на вход операционного автомата поступает обрабатываемая информация, а по каналу 2 снимают результаты ее обработки. По каналу 3 в управляющий автомат поступает сообщение об исполнении шага алгоритма и о результатах проверки условий, а по каналу 4 в операционный автомат - управляющее воздействие для исполнения очередного шага алгоритма. По каналу 5 в управляющий автомат поступает команда для исполнения оператора, а по каналу 6 - сообщение об его исполнении.
Управляющие цифровые автоматы (УЦА) делятся на: автоматы с микропрограммным управлением и автоматы с жёсткой логикой (ЖЛ). Первые автоматы можно называть автоматами с программируемой логикой (ПЛ).
Структурная схема любого УА выглядит так, как показано на рис.33. Она состоит из трех частей: запоминающей части с дешифратором, схемы формирования сигналов возбуждения триггеров запоминающей части, схемы формирования выходных сигналов.
В дальнейшем вторая и третья части будут для упрощения именоваться входной и выходной частями соответственно.
ЗУ с дешифратором содержит триггерный регистр, на котором могут размещаться всевозможные числа, соответствующие требуемым состояниям.
Дешифратор расшифровывает число в нужный сигнал состояния, индекс которого совпадает с величиной числа.
Входные сигналы, множество которых обозначено через Х, сигналы состояний, множество которых обозначен через S, используются для формирования сигналов возбуждения триггеров как для автоматов Мили, так и для автоматов Мура, а также для формирования выходных сигналов автоматов Мили.
Для формирования выходных сигналов автоматов Мура достаточно только сигналов состояний