ПТЦА - Прикладная теория цифровых автоматов (стр. 16 из 20)
2) множеством выходных слов R={r1,...,rQ}, представляющих результаты операций;
3) множеством внутренних слов S={s1,...,sN}, используемых для представления информации в процессе выполнения операций. Можно считать, что входные и выходные слова совпадают с определенными внутренними DÍS, RÍS.
4) множеством микроопераций Y={ym}, реализующих преобразование S=jm(s) над словами информации, где jm – вычисляемая функция;
5) множеством логических условий X={xi}, где xi=yi(si) и yi – булева функция;
T.o. функция ОА задана, если заданы (определены) множества D, R, S, Y, X. Время не является аргументом функции ОА. Функция устанавливает список действий-микроопераций и логических условий, которые может выполнять автомат, но никак не определяет порядок следования этих действий во времени. Т.е. функция ОА характеризует средства, которые могут быть использованы для вычислений, но не сам вычислительный процесс.
Порядок выполнения действий во времени определяется в форме функций управляющего автомата.
Функция управляющего автомата – это операторная схема алгоритма ( микропрограммы), функциональными операторами которой являются символы у1,...,уm, отождествляемые с микрооперациями, и в качестве логических условий используются булевы переменные х1,...,хL. Операторная схема алгоритма наиболее часто представляется в виде граф-схемы алгоритма (ГСА). ГСА определяет вычислительный процесс последовательно во времени, устанавливая порядок проверки логических условий х1-хL и порядок следования микроопераций у1-уm.
СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ И МИКРОПРОГРАММ
Наиболее наглядно изображать микропрограммы и алгоритмы в виде ориентированного графа, т.н. граф схемы алгоритма (ГСА). Кроме наглядности это дает возможность использовать для анализа и преобразования микропрограмм эффективные методы теории графов. При графическом описании отдельные функции алгоритмов (микрооперации) отображаются в виде условных графических изображений, т.н. вершин. В ГСА обычно используют вершины следующих типов:
- вершина «начало» имеет один выход, входов не имеет. Обозначает начало микропрограммы.
- вершина «конец» имеет любое число входов, выходов не имеет. Обозначает конец микропрограммы.
- операторная вершина имеет любое число входов, один выход. Внутри операторной вершины записывается одна микрокоманда - совокупность микроопераций, допускающих совместное (т.е. одновременное) выполнение.
- условная вершина имеет любое число входов и 2 выхода. Внутри условной вершины записывается булевое выражение, в зависимости от значения которого осуществляется выбор направления дальнейшего выполнения микропрограммы.
- особый вид условной вершины - ждущая - имеет множество входов, 2 выхода, 1 из которых заведен на вход. При попадании в ждущую вершину выход из нее возможен только при выполнении условия Х.
Граф микропрограммы состоит из совокупности перечисленных вершин и дуг, соединяющих выходы одних вершин с входами других. Соединение вершин и направление дуг графа определяют исходя из алгоритма операции, описываемого графом, и структуры операционного автомата.
Сама микропрограмма и ее граф должны быть корректны, т.е. отвечать следующим условиям:
1. В графе должна быть только одна начальная и одна конечная вершина.
2. В любую вершину графа должен вести по крайней мере один путь из начальной вершины.
3. Из каждого выхода любой вершины графа должен существовать по
крайней мере один путь в конечную вершину.
4. При всех возможных значениях логических условий и используемых слов должен существовать путь из начальной вершины в конечную.
Пример ГСА представлен на рисунке:
ГСА на рис.43 называется содержательной, т.к. внутри вершин записаны в явном виде микрооперации и логические условия. Если же каждую микрооперацию обозначить символами Yi, a логические условия через Xi, то получится так называемая кодированная ГСА (рис.44 ). Для правильного восприятия микропрограммы, заданной в виде кодированной ГСА, необходимо знать соответствия между Yi, Xi и содержанием соответствующих микроопераций и логических условий.
Для записи микроопераций внутри вершин используется так называемый Ф-язык. Подробно с зтим языком можно ознакомиться в последующих курсах «Схемотехника ЭВМ», «Теория и проектирование ЭВМ». Здесь же мы рассмотрим только основные положения этого языка.
В этом языке существуют двоичные константы и переменные: 0010 - константа, A(1:4) - четырехразрядное слово - четырехразрядная двоичная переменная. Например, A(1:4)=1010 означает, что в первом разряде слова A будет 1, во втором - 0 и т.д. A(2:3) - часть слова A, размещенная во втором и третьем разрядах.
Наиболее употребительные операции Ф-языка:
присваивание - A( 0:3 ): = 1000, B( 1:4 ): = A( 5:8 ) и т.д.
инвертирование - A( 0:3 ): = ^ B( 1:4 )
конкатенации - С( 0:6 ): = A( 0:3 ). B( 1:3 )
Пример 1. A( 0:3 ): = 1100 B( 1:4 ): = A( 0:3 ) ® B( 1:4 ): = 1100
2. B( 1:4 ): = 0101 A( 0:3 ): = ^B( 1:4 ) ® A( 0:3 ): = 1010
3. A( 0:3 ): = 1101 B( 1:3 ): = 110 C( 0:6 ): = A( 0:3 ). B( 1:3 ) ® C(0:6):=1101110
Запись вида A(2) означает, что здесь рассматривается второй разряд слова A, т.е. это бит, записанный во втором разряде слова A.
При выполнении операций присваивания необходимо соблюдать равенство разрядов в словах слева и справа от знака присваивания. Операции сложения, логического сложения и т.д. в Ф-языке записываются обычным способом через оператор присваивания:
C(0:n):=A(0:n)+B(0:n)
D(0:n):=A(0:n)vB(0:n) и т.д.
ОПЕРАЦИОННЫЕ ЭЛЕМЕНТЫ
Согласно принципа микропрограммного управления, любая сложная операция распадается на ряд микроопераций, которые выполняются ОА. Различные микрооперации выполняются элементарными ОА - так называемыми операционными элементами (ОЭ), которые являются составными частями основного ОА.
Под операционным элементом понимают устройство, реализующее одну из следующих функций или их произвольную комбинацию:
· хранение слова информации С;
· выполнение некоторых микроопераций, в результате которых вычисляется новое значение слова С;
· вычисления логического условия, зависящего от слова С;
Т.о. функция ОЭ определена, если заданы:
· описание хранимого или вычисляемого слова;
· описание множества микроопераций, выполняемых этим элементом;
· описание вычисляемых этим элементом логических условий.
Для построения ОА ОЭ соединяются между собой с помощью цепей передачи слов информации от выходов одних элементов к входам других.
В зависимости от выполняемых микроопераций ОЭ делятся на разновидности: шина, регистр, счетчик, сумматор, схема сравнения, дешифратор, шифратор и т.д.
Шина - это совокупность цепей, предназначенных для передачи слова информации. Условное обозначение шины представлено на рис.45.
Шины, изображенные на рис.45 называются неуправляемыми шинами.
Управляемые шины представлены на рис.46.
Под действием управляющего сигнала у управляемая шина выполняет микрооперации: у=0 : B(0:3):=0 , y=1 : B(0:3):=A(0:3)
Т.е. при y=1 осуществляется операция передачи. Разрядность шины может быть произвольная, но обычно это 8, 12, 16, 24, 32 и т.д.
Регистр - это операционный элемент, служащий для запоминания слов и обеспечивающий в общем случае выполнение следующих микроопераций:
· установка регистра в 0 (сброс);
· прием слова из другого регистра, шины и т.д.;
· передача слова на другой регистр, шину и т.д.;
· преобразование кодов хранимых слов в инверсные коды;
· сдвиг хранимого слова влево или вправо на требуемое число разрядов.
Регистр, выполняющий такие микрооперации, называется многофункциональным. Т.к. регистр предназначен для хранения информации, то он содержит элементы памяти, в качестве которых используются триггеры. Количество триггеров определяет разрядность регистра. Будем обозначать регистр в виде прямоугольника с указанием разрядности (рис.47 ).
Регистр может состоять из отдельных подрегистров, имеющих самостоятельное значение (рис.48.). На рис.48 представлен регистр, хранящий число в форме с плавающей запятой. В этом регистре три подрегистра: для хранения знака Рг(0), характеристики Рг(1:7), мантиссы Рг(8:31) числа.
Регистр может выполнять ряд микроопераций, например:
Регистр, который выполняет микрооперацию у4 (сдвиг вправо) или у5 (сдвиг влево) называются регистром сдвига.
Сумматор - операционный элемент, выполняющий суммирование кодов чисел. В зависимости от кодов чисел различают сумматоры прямого, обратного, дополнительного кодов. Кроме того, сумматоры бывают комбинационными и накапливающими.
Комбинационный сумматор вырабатывает выходные сигналы суммы и переноса, определяемые комбинацией цифр слагаемых, одновременно поданных на входы сумматора. Данный сумматор не обладает памятью и после снятия сигналов с входов выходные сигналы также исчезают.