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

Курсовой проект по дисциплине

«Теория автоматов»

«Разработка операционного устройства»

Санкт-Петербург 2009 г.

Аннотация

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

В данной работе проводится проектирование операционного устройства, реализующего операцию: получение операнда A (1:24); получение операнда B (1:24); выдачу результата C (1:24); алгебраическое вычитание для чисел с фиксированной точкой в простых дополнительных кодах. Используется канонический метод синтеза комбинационных схем, управляющий автомат разрабатывается с жесткой логикой.

Любой сложный преобразователь дискретный информации может быть представлен в виде совокупности операционных устройств (ОУ) и интерфейса (сопряжения этих устройств).

Функцией ОУ является выполнение фиксированного множества операций F={f₁, f₂., f_G} над множеством входных слов D={d₁, d₂,… d_H} для вычисления слов R = {r₁, r₂,…, r_Q}, которые являются результатами операций из множества F. В течение определенного отрезка времени устройство может реализовать только одну операцию R=f_g(D), которая определяется кодом операции (номером) g=1, 2., G. Функцию ОУ можно представить в виде R=(D), где

ОУ объединяются в структуру с помощью цепей, по которым передаются электрические сигналы. Одна цепь передает в один момент времени бит информации (01). Совокупность цепей, связывающих два ОУ и алгоритм, определяющий порядок передачи информации между ОУ, называется интерфейсом. Обычно ОУ представляют в виде двух автоматов: операционного автомата (ОА) и управляющего автомата (УА). ОА выполняет действия над словами информации — хранение, реализацию МКО и вычисление ЛУ — и, таким образом, является исполнительной частью ОУ. УА генерирует последовательность управляющих сигналов, которая определена микропрограммой и соответствует значениям ЛУ и, следовательно, задает порядок выполнения МКО в ОА.

На рисунке 1 представлена упрощенная структура ОУ. D — множество входных слов, R — множество выходных слов, Y — множество микроопераций, X — множество логических условий, g — код операции f_g.

Рис. 1. Упрощенная структура ОУ

1. Определение функций операционного устройства

1.1 Анализ алгоритма заданной операции

Алгоритм операции:

1. Начало.

2. Слову П (1) присвоить значение «0».

3. Изменить знак вычитаемого на противоположный.

4. Образовать дополнительные коды слов, А и В.

5. Слову С присвоить значение суммы слов, А и В.

6. Знаковые разряды слов, А и В равны?

ДА: перейти к п. 7,

НЕТ: перейти к п. 9.

7. Знаковые разряды слов С и, А равны?

ДА: перейти к п. 8,

НЕТ: перейти к п. 10.

8. Имеется особый случай переполнения?

ДА: перейти к п. 10,

НЕТ: перейти к п. 9.

9. Образовать прямой код результата и перейти к п. 11.

10. Слову П (1) присвоить значение «1» и перейти к п. 11.

11. Конец.

Для проектирования ОУ, необходимо было удостовериться в правильности алгоритма, для этого была осуществлена проверка (смотри таблицу 1).

Таблица 1. Проверка алгоритма

операционный устройство логика алгебраический

Результаты сверены для всех случаев, алгоритм работает верно.

1.2 Функциональная микропрограмма работы ОУ

Алгоритм выполнения операции представлен в виде содержательного графа микропрограммы (Рис. 2).

В таблице 2 приводятся описания слов, с которыми оперирует микропрограмма, представленная ранее (смотри рисунок 2).

Таблица 2. Описание слов в микропрограммах

Рис. 2. Содержательный граф микропрограммы

1.3 Определение функции операционного автомата

Каждая функциональная микропрограмма M_g, где g = 1, 2, …, G, определяющая алгоритм выполнения операции f_gF, вводит множество слов S_g, микроопераций Y_g и логических условий X_g. Множество S_g, Y_g, X_g характеризуют функцию ОА частично, позволяя определить средства, достаточные для реализации только одной операции f_g.

На основе функциональной микропрограммы работы ОУ составляются таблицы микроопераций и логических условий (таблицы 3 и 4).

Таблица 3. Объединенный список микроопераций

Таблица 4. Объединенный список логических условий

1.4 Определение функции управляющего автомата

По отношению к управляющему автомату МКО и ЛУ представляются как элементарные символы, которые автомат интерпретирует в виде управляющих сигналов Y={y₁, y₂, …, y_M} и воспринимает как осведомительные сигналы X={x₁, x₂, …, x_L}.

Таким образом, функция управляющего автомата (УА) — это операторная схема микропрограммы, функциональными операторами которой являются символы y₁, y₂, …, y_M отождествляемые с МКО, а в качестве ЛУ используются булевы переменные x₁, x₂, …, x_L.

На основе функциональной микропрограммы работы ОУ и таблиц микроопераций и логических условий (смотри таблицы 3 и 4) составляется закодированная граф — схема управляющего автомата, представленная на рисунке 3. В данной граф — схеме в операторные и условные вершины вместо микроопераций и логических условий записываются их обозначения.

Функция УА определяется совокупностью закодированного графа микропрограммы, который соответствует содержательной граф — схеме.

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

Рис. 3. Закодированная граф-схема УА

2. Синтез функциональной схемы операционного автомата

2.1 Разработка структурной схемы ОА

Исходной информацией для разработки структурной схемы ОА являются:

§ описание типов слов, используемых в микропрограмме (таблица 2).

§ список МКО (таблица 3).

§ список ЛУ (таблица 4).

Все слова (переменные), кроме вспомогательных, должны сохранять свое значение неограниченно долго, вплоть до присвоения им нового значения. Такие переменные являются переменными с памятью в отличие от вспомогательных переменных — переменных без памяти. Переменные с памятью соответствуют всем внутренним (L) словам.

Каждой переменной с памятью ставится в соответствие регистр операционного автомата той же разрядности, что и переменная, причем i-й разряд регистра соответствует i-му разряду переменной. Регистру присваивается идентификатор соответствующего ему слова.

Для рассматриваемого варианта задания структурная схема ОА будет содержать четыре регистра — A (1:24), B (1:24), C (1:24) и П (1).

Каждой переменной без памяти ставится в соответствие шина, имеющая разрядность переменной и предназначенная для параллельной передачи слов.

Для каждого регистра определяется множество микроопераций Y_S и логических условий X_S. На основании анализа микроопераций Y_S и логических условий производится выделение всех полей регистра S. В одно поле включаются те разряды регистра S, которые преобразуются микрооперациями Y_S одинаково.

В таблице 5 содержатся все данные, необходимые для построения структурной схемы ОА, реализующей операцию.

Таблица 5. Элементы структуры ОА

Опираясь на таблицу 5, в которой представлены множества микроопераций, логических условий, а также выделены поля слов — операндов, построена структурная схема ОА (Рис. 4).

Выходные цепи регистров A, B, C и П объединены в шину S, с которой поступают сигналы на входные сигналы комбинационных схем, реализующих микрооперации и вычисляющих логические условия. Если ?_I — тривиальная булева функция, то логическое условие интерпретируется цепью, выходящей из соответствующего разряда регистра S (например, ЛУ x₁). Предполагается, что по шине S передаются как прямые, так и инверсные значения слов, хранимых в регистрах.

Словами, описанными в таблице 2, как входные (I), ставятся в соответствие входы d₁ и d₂ структурной схемы. Каждый вход соединяется с регистром шиной, исходящей из входа.

Словам, описанным как выходные (O), ставятся в соответствие выходы r структурной схемы.

Управляемые шины отмечаются сигналом y_m, инициирующим микрооперацию y_m.

Рис. 4. Структурная схема ОА

2.2 Синтез функциональной схемы ОА

Синтез ОА проводится раздельно для каждого разряда и сводится к построению комбинационных схем, реализующих функции возбуждения D триггеров регистров. Для этого необходимо четко знать, какие микрооперации выполняются в блоке, какие логические условия вычисляются в нем и какие поля выделены. Это видно из таблицы 5.

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

2.2.1 Синтез регистра A

МКО: y_A, y₄

y_A: A (1:24):= d₁(1:24)

y₄: A (1:24):= A (1).A (2:24) + 1

Поля: А (1), А (2:23), А (24).

Синтез поля A (1)

y_A: A (1):= d₁(1)

Заполняется каноническая таблица 6 для нахождения функции возбуждения триггера.

V_D=d₁(1).

Таблица 6. Каноническая таблица для определения V_D

y₄: A (1):= A (1)

V_D=A (1)

Окончательным результатом данного этапа работы является синтез функциональной схемы, для определения значения функции возбуждения элемента памяти A (1) регистра A, которая синтезируется по следующему выражению:

Функциональная схема поля A (1) представлена на рисунке 5а, а на рисунке 5б представлено ее условное обозначение.

а) б)

Рис. 5. Функциональная схема операционного элемента A (1) регистра, А (а); условное изображение операционного элемента А (1) (б)

Синтез поля A (2:23)

y_A: A (i):= d₁(i), где i = {2; 23}

Синтез аналогичен синтезу поля А (1).

y₄: A (i):=

Заполняется каноническая таблица 7 для нахождения функций возбуждения триггера и функций переноса.

Таблица 7. Каноническая таблица для определения V_D и P (i-1)

Аналитическое выражение для искомых функций имеет вид:

Окончательным результатом данного этапа работы является синтез функциональной схемы для определения значения функции возбуждения элемента памяти A (i) регистра A и функции переноса P (i-1), которые синтезируются по следующим выражениям:

Функциональная схема поля A (i) представлена на рисунке 6а, а на рисунке 6б представлено ее условное обозначение.

а) б)

Рис. 6. Функциональная схема операционного элемента A (i) регистра, А (поле, А (2:23)) (а); условное изображение операционного элемента А (i) (б)

Для поля A (2) не нужно вырабатывать функцию переноса. Функциональная схема поля A (2) представлена на рисунке 7а, а на рисунке 7б представлено ее условное обозначение.

а) б)

Рис. 7. Функциональная схема операционного элемента A (2) регистра, А (а); условное изображение операционного элемента А (2) (б)

Синтез поля A(24)

y_A: A (24):= d₁(24)

Синтез аналогичен синтезу поля А (1).

y₄: A (24):= A (24)

Заполняется каноническая таблица 8 для нахождения функции возбуждения триггера и функции переноса.

Таблица 8. Каноническая таблица для определения V_D и P (23)

Аналитическое выражение для искомых функций имеет вид:

Окончательным результатом данного этапа работы является синтез функциональной схемы для определения значения функции возбуждения элемента памяти A (24) регистра A и функции переноса P (23), которые синтезируется по следующим выражениям:

Функциональная схема поля A (24) представлена на рисунке 8а, а на рисунке 8б представлено ее условное обозначение.

a) б)

Рис. 8. Функциональная схема операционного элемента A (24) регистра, А (а); условное изображение операционного элемента А (24) (б)

2.2.2 Синтез регистра B

МКО: y_В, y_2,y₃

y_B: B (1:24):= d₂(1:24)

y₂: B (1):= B (1)

y_3: B (1:24):= B (1).B (2:24) + 1

Поля: B (1), B (2:23), B (24).

Синтез поля B(1)

y_B: B (1):= d₂(1)

Синтез аналогичен синтезу поля А (1)

V_D=d₂(1).

y₂: B (1):= B (1)

Заполняется каноническая таблица 9 для нахождения функции возбуждения триггера

Таблица 9. Каноническая таблица для определения V_D

Окончательным результатом данного этапа работы является синтез функциональной схемы для определения значения функции возбуждения элемента памяти B (1) регистра B, которая синтезируется по следующему выражению:

Функциональная схема поля B (1) представлена на рисунке 9а, а на рисунке 9б представлено ее условное обозначение.

а) б)

Рис. 9. Функциональная схема операционного элемента B (1) регистра B (а); условное изображение операционного элемента B (1) (б)

Синтез полей В (2:23) и B (24) производится аналогично синтезу блока, А с заменой нескольких аргументов в функциях возбуждения: на; на; на .

Условное изображение операционного элемента B (2:23) изображено на рисунке 10, а B (24) на рисунке 11, B (2) на рисунке 12.

Рис. 10. Условное изображение операционного элемента B (2:23)

Рис. 11. Условное изображение операционного элемента B (24)

Рис. 12. Условное изображение элемента B (2)

2.2.3 Синтез регистра С

МКО: y₅, y₇

y₅: C (1:24):= A (1:24) + B (1:24)

y₇: C (1:24):= C (1).C (2:24) + 1

Поля: С (1), C (2:23), C (24)

Синтез поля C(1)

y₅: C (1):= A (1) B (1)P (1)

Заполняется каноническая таблица 10 для нахождения функции возбуждения триггера.

Таблица 10. Каноническая таблица для определения V_D

V_D= A (1) B (1)P (1)=

y_7: С (1)=С (1)

V_D=C (1)

Окончательным результатом данного этапа работы является синтез функциональной схемы для определения значения функции возбуждения элемента памяти C (1) регистра C, которая синтезируется по следующему выражению:

Функциональная схема поля C (1) представлена на рисунке 13а, а на рисунке 13б представлено ее условное обозначение.

a)

б)

Рис. 13. Функциональная схема операционного элемента C (1) регистра C (а); условное изображение операционного элемента C (1) (б)

Синтез поля C (2:23)

y_5: ,

где i = {2; 23}

Заполняется каноническая таблица 11 для нахождения функций возбуждения триггера и функций переноса.

Таблица 11. Каноническая таблица для определения V_D и Р (i-1)

Функцию переноса найдем с помощью карты Карно:

Аналитическое выражение для искомых функций имеет вид:

y₇: C (i):= P (i) C (i)

Заполняется каноническая таблица 12 для нахождения функций возбуждения триггера и функций переноса.

Таблица 12. Каноническая таблица для определения V_D и P (i-1)

Окончательным результатом данного этапа работы является синтез функциональной схемы для определения функции возбуждения элемента памяти C (i) и функции переноса P (i-1) регистра C, которые синтезируются по следующим выражениям:

Функциональная схема поля C (i) представлена на рисунке 14а, а на рисунке 14б представлено ее условное обозначение.

а) б)

Рис. 14. Функциональная схема операционного элемента C (i) регистра C (поле C (2:23)) (а); условное изображение операционного элемента C (i) (б)

Синтез поля С(24)

y₅: C (24):= A (24) B (24)

Заполняется каноническая таблица 13 для нахождения функции возбуждения триггера и функции переноса.

Таблица 13. Каноническая таблица для определения V_D и P (23)

Аналитическое выражение для искомой функции имеет вид:

y7: C (24):= C (24)

Заполняется каноническая таблица 14 для нахождения функции возбуждения триггера и функции переноса.

Таблица 14. Каноническая таблица для определения V_D и P (23)

Аналитическое выражение для искомой функции имеет вид:

Окончательным результатом данного этапа работы является синтез функциональной схемы для определения значения функции возбуждения, элемента памяти С (24) и функции переноса P (23) регистра С, которые синтезируются по следующим выражениям:

Функциональная схема поля С (24) представлена на рисунке 15а, а на рисунке 15б представлено ее условное обозначение.

а) б)

Рис. 15. Функциональная схема операционного элемента C (24) регистра C (а); условное изображение операционного элемента C (24) (б)

2.2.4 Синтез регистра П

МКО: ,

) П (1):= 0

) П (1):= 1

) П (1):=0

V_D = 0

) П (1):=1

V_D=1

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

Функциональная схема поля П (1) представлена на рисунке 16а, а на рисунке 16б представлено ее условное обозначение.

а) б)

Рис. 16. Функциональная схема операционного элемента П (1) регистра П (а); условное изображение операционного элемента П (1) (б)

2.3 Синтез функциональной схемы для вычисления логических условий

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

Таблица 15. Вычисление логических условий

Функциональная схема логических условий представлена на рисунке 17а, а на рисунке 17б ее условное обозначение.

а) б)

Рис. 17. Схема вычисления значений логических условий (а); условное изображение схемы (б)

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

Исходной информацией для синтеза УА является объединенная закодированная граф-схема работы УА. Синтез УА осуществляется в два этапа:

§ получение отмеченной граф — схемы УА.

§ построение графа автомата.

Конечный автомат можно разделить на автомат Мура и Мили. В данном курсовом проекте принято описать УА как автомат Мура. Число внутренних состояний автомата Мура равно 8, откуда количество двоичных разрядов для кодирования внутренних состояний соответственно равно log₂ 8 = 3. Следовательно, для построения автомата Мура потребуется три триггера. На рисунке 18 представлена разметка внутренних состояний автомата Мура.

Рис. 18. Разметка внутренних состояний автомата Мура

3.1 Структурная схема УА

Для построения структурной схемы УА необходимо произвести кодирование внутренних состояний памяти.

Количество Т — синхронных триггеров, необходимых для построения памяти УА, равно трем (см. выше). Кодировка представлена в таблице 16.

Таблица 16. Кодировка внутренних состояний триггеров

Кодирование производится путем замены индекса A_i на двоичный код, соответствующий номеру индекса.

Опираясь на таблицу внутренних состояний и закодированную граф-схему управляющего автомата строится граф, задающий работу УА (в данном курсовом проекте автомат Мура).

3.2 Функциональная схема УА

Окончательный результат функций возбуждения элементов памяти. Значениям A_i в уравнениях соответствуют выходы дешифратора.

Для первого триггера:

Минимизируем, используя карту Карно:

На основании полученного выражения строится схема КС1 (Рис. 20) управляющего автомата, которая реализует функцию возбуждения триггера.

Для второго триггера:

На основании полученного выражения строится схема КС2 (Рис. 21) управляющего автомата, которая реализует функцию возбуждения триггера.

Для третьего триггера:

Минимизируем, используя карту Карно:

На основании полученного выражения строится схема КС3 управляющего автомата, которая реализует функцию возбуждения триггера.

Заключение

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