3. Операционный автомат

Программная инженерия (бакалавриат)

Фундаментальная информатика и информационные технологии (бакалавриат)

Литература: [1, стр. 38, 60 – 62, 81 – 89], [2, стр. 714 – 716] , [3, стр. 606]

Исходными данными для разработки структуры операционного автомата являются:

• описание входных и выходных слов, т. е. множеств и ;

• список подмножества операций из множества , которые должны выполняться над словами.

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

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

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

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

Таким образом, процесс разработки операционного автомата можно представить состоящим из пяти этапов:

1. определение форматов входных и выходных данных (слов);

2. разработка блок-схем алгоритмов выполняемых операций;

3. разработка структуры операционного автомата, т. е. определение элементов и организация связей между ними;

4. определение множества микроопераций, выполняемых в операционном автомате;

5. определение множества логических условий, формируемых в операционном автомате.

1. Пример проектирования операционного автомата

В качестве примера рассмотрим разработку операционного автомата АЛУ, реализующего операцию деления чисел, представленных в формате с фиксированной запятой в прямом двоичном коде. Проектирование операционного автомата будем проводить в соответствии с алгоритмом, приведенным в конце предыдущего раздела.

Определение форматов данных

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

• (zero) – признак нулевого результата;

• (sign) – признак отрицательного результата;

• (overflow) – признак переполнения.

Алгоритм операции деления разрабатывается для 16-разрядных двоичных чисел, представленных в формате с фиксированной запятой в прямом двоичном коде. Знак числа сохраняется в его старшем (нулевом) бите.

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

• – первый операнд (делимое);

• – второй операнд (делитель);

• – результат операции (частное); в процессе выполнения алгоритма переменная используется для хранения остатка;

• – переменная, в которой в процессе деления накапливаются цифры частного.

Здесь биты , и являются знаковыми.

Разработка алгоритма деления

При выполнении деления чисел, представленных в прямых двоичных кодах, удобнее делить модули чисел, поскольку знак результата не зависит от соотношения модулей делимого и делителя, а определяется в соответствии с выражением

. (1.1)

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

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

Блок-схема алгоритма деления чисел без восстановления остатка представлена на рис. 1.2. Алгоритм предусматривает формирование знака результата в соответствии с формулой (1.1) и временное сохранение его в переменной (блоки 2 – 4). После этого знаки операндов обнуляются (блок 5) и выполняется деление модулей чисел и .

На первом этапе выполняется пробное вычитание делителя из делимого (блок 5). Поскольку знаки операндов положительные, появление единицы в знаковом бите разности означает, что и можно продолжать деление. Если же , то деление невозможно. Поэтому формируется признак переполнения (блок 8) и выполнение алгоритма завершается (блок 16).

В процессе определения цифр частного роль очередного остатка играет переменная . Независимо от знака остатка она копируется в переменную , которая затем увеличивается в два раза путем сдвига влево на один разряд (блок 9). В зависимости от знака остатка формируется очередная цифра частного и принимается решение о действии на следующем шаге – вычесть делитель из сдвинутого остатка или прибавить к нему (блоки 10 – 12). После вычитания или сложения проводится сдвиг частного влево на один разряд (блок 13). Тем самым освобождается последний разряд числа для очередной цифры частного. Затем изменяется счетчик цифр частного (блок 13) и проверяется условие выхода из цикла – получение шестнадцати цифр частного, включая и самую первую цифру – «0 целых» (блок 14).

На последнем этапе вычисленное значение частного копируется из переменной в переменную , а знак частного копируется из переменной в знаковый бит переменной (блок 15). На этом алгоритм деления числа на число завершается (блок 16).

Разработка структуры операционного автомата

Анализ алгоритма деления чисел, представленного на рис. 1.2, позволяет разработать структуру операционного автомата. Учитывая действия, которые требуется выполнить для реализации алгоритма, включим в состав операционного автомата следующие элементы:

• два 16-разрядных регистра Рг A и Рг B для хранения исходных операндов и , а также промежуточных результатов, причем регистр Рг A должен обеспечивать возможность сдвига своего содержимого влево;

• 16-разрядный регистр Рг C для хранения результата арифметической операции сложения или вычитания; в процессе выполнения алгоритма в этом регистре будет формироваться остаток , а на последнем этапе в него будет помещен результат частное ;

• 16-разрядный регистр Рг D с возможность сдвига своего содержимого влево для хранения частного в процессе его формирования;

• 16-разрядный параллельный двоичный сумматор Сум/Выч для выполнения операций сложения и вычитания двоичных чисел;

• 4-разрядный счетчик Сч n по модулю 16 для выполнения обратного счета цифр частного ;

• триггер переполнения Тг O для хранения признака переполнения разрядной сетки;

• триггер знака Тг s для временного хранения знака частного;

• схема сравнения на предмет равенства знаковых битов операндов и ;

• дешифратор DC "0" нулевой комбинации в битах C[1] – C[15], формирующий признак нулевого результата.

Связи между перечисленными выше элементами, а также управляющие ими микрооперации показаны на рис. 1.3, а в табл. 1.1 приведен полный список микроопераций и логических условий. Очевидно, что любые действия, обозначенные в операторных блоках блок-схемы алгоритма, представленной на рис. 1.2, могут быть реализованы в структуре разработанного операционного автомата (см. рис. 1.3).

Теперь определим, какая последовательность микроопераций должна быть реализована в разработанной структуре, чтобы выполнилась операция деления в соответствии с алгоритмом, изображенным на рис. 1.2. Простейшим решением является сохранение схемы алгоритма и замена содержимого операторных блоков соответствующими микрооперациями, а содержимое условных вершин – соответствующими логическими условиями.

Таблица 1.1