Вариант 13

Ссылки сюда (1) →

Генерация ГСА

Введение

Микропрограмма представляет собой направленный граф и бывает трех типов:

1. содержательная граф-схема алгоритма (ГСА);
2. закодированная ГСА;
3. отмеченная ГСА.

Содержательная ГСА содержит описания микроопераций в терминах устройств ОБ. В каждом ОБ указывается непосредственно содержание выполняемой микрооперации.
Содержательные алгоритмы строятся на начальном этапе проектирования, имеет хорошую наглядность, однако имеет громоздкое описание и занимают значительное место, поэтому в дальнейшем она преобразуется в закодированную схему алгоритма. Переход от содержательной ГСА к закодированной весьма прост. Каждой операции присваивается свой символ по порядку, в виде y1, y2,… Основной задачей работы служит разработалка алгоритма для генерации ГСА. Далее написать программу для рисования по данному алгоритму ГСА.

Основные понятия и определения теории булевых функций

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

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

Общий вид таблицы истинности

x1	x2	.....	xn-1	xn	F
0	0	.....	0	0	F(00...00)
0	0	.....	0	1	F(00...01)
0	0	.....	1	0	F(00...10)
0	0	.....	1	1	F(00...11)
...	...	...	...	...	...
1	1	.....	1	1	F(11...11)

Среди функций одной переменной наибольший интерес представляет функция – отрицание (инверсия) переменной. Такая функция называется элементарной булевой функцией одной переменной. Кроме функции к числу элементарных относится 7 булевых функций, зависящих от двух переменных и  :

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

Заключение

Был разработан алгоритм в результате которого генерировалась матрица смежности. Так же в программной среде Qt была написана программа для рисования по полученной матрице смежности псевдослучайной ГСА.

Список литературы

1. Баранов С.И. Синтез микропрограммных автоматов. – Л. Энергия, 1979.
2. Скляров В.А., Баранов С.И., Синтез автоматов на матричных БИС. – Наука и техника, 1984.
3. Жмакин А.П., Архитектура ЭВМ. Уч.пособие. Санкт Петербург, БХВ-Петербург, 2006.
4. Цилькер Б.Я. ,Орлов С.А.. Организация ЭВМ и систем: Учебник для вузов. – СПб: Питер,2004.

1. Лабораторные работы (MediaWiki)