Синтез блока управления операции сложения в арифметико-логическом устройстве

Синтез блока управления операции сложения в арифметико-логическом устройстве

СОДЕРЖАНИЕ

Введение

. Техническое задание

. Общая последовательность сложения чисел с ПТ

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

. Алгоритм сложения чисел в АЛУ

. Разработка функциональной схемы блока управления

.1 Общая последовательность разработки

.2 Формализация задания

.3 Выбор типа автомата

.4 Разметка схемы алгоритма

.5 Составление таблиц переходов и выходов

.6 Кодирование состояний

.7 Составление кодированной таблицы переходов и выходов

.8 Выбор типа триггера

.9 Преобразование таблицы переходов в таблицу функций возбуждения триггеров

.10 Запись функций возбуждения и функций выходов в СДНФ

.11 Минимизация функций возбуждения и функций выходов

.17 Граф

Заключение

Литература

Введение

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

По разработанной блок-схеме описание работы автомата проще всего составлять в виде графа переходов. Вид графа зависит от того, проектируется автомат Мура или автомат Мили:

Автомат Мили                                                   Автомат Мура

y_t = f₁(x_t, z_t) y_t+1 = f_t(z_t+1)

z_t+1 = f₂(x_t, z_t) z_t+1 = f₂(x_t, z_t)

Автомат Мили (англ. Mealy machine) - конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы.

Автомат Мили можно описать пятеркой (Q, X, Y, f, g), где Q - множество состояний автомата,- множество входных символов,- множество выходных символов,= f(Q,X) - функция состояний,=g(Q,Y) - функция выходных символов.

Автомат Мура

Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура (англ. <#"669994.files/image002.gif">,

где S, X и Y - конечные непустые множества, а δ и λ - отображения вида:

и

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:

(Отображения δ и λ получили названия, соответственно функции переходов и функции выходов автомата A).

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата.

Автомат Мили

В автомате Мили (англ. Mealy machine) функция выходов λ определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата. Таким образом, можно дать следующее определение:

Конечным детерминированным автоматом типа Мили называется совокупность пяти объектов

,

где S, X и Y - конечные непустые множества, а δ и λ - отображения вида:

и

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:

(Отображения δ и λ получили названия, соответственно функции переходов и функции выходов автомата A).

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата.

1. Техническое задание:

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

Исходные данные: Тип автомата - автомат Мура

Тип триггера - T-триггер

2. Общая последовательность сложения чисел с ПТ

При сложении определяется сумма

С = А + В, где:

А - слагаемое;

В - слагаемое;

С - сумма.

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

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

3. Структурная схема АЛУ

Структурная схема АЛУ строится в соответствии с общей последовательностью операции сложения. АЛУ имеет типовую структуру, представленную на рисунке 2.

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

Для определения признака результата должны использоваться схемы, которые объединяются в общую схему формирования признаков результата.

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

Шина данных

Регистр А: Сигнал начала операции

Регистр В: Управляющие сигналы

Сигнал готовности ПК ДК ПК ДК

Признаки результата

4. Алгоритм сложения чисел в АЛУ

Алгоритм сложения составляется в соответствии с общей последовательностью сложения и структурной схемой АЛУ. Микропрограмма сложения чисел в АЛУ в виде схемы алгоритма представлена на рисунке 3. Здесь под микропрограммой понимается последовательность микроопераций. Микрооперация - элементарная операция, для управления которой достаточно одного управляющего сигнала.

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

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

Выполнение операции начинается с того, что числа А и В последовательно считываются из оперативной памяти и записываются в регистры РгА и РгВ (операторы 2 и 3).

Для сложения двух чисел с ПТ необходимо, чтобы их порядки были одинаковы. После извлечения чисел из ОП, вычисляется разность порядков dP (оператор 4). Если dP не равно 0, то необходимо выравнивание порядков (оператор 6). Для помещения чисел в сумматор, необходимо учитывать знак чисел, для представления их в соответствующем коде (прямой или дополнительный). Операторы 7, 8 и 9 выполняют эту функцию: Если А<0 и В<0, то оба числа отправляем в сумматор в дополнительном коде (ДК) - оператор 11. Если А<0, а B>0 то число В заносится в сумматор в прямом коде (ПК) - оператор 10. Если А>0,а В<0, то число А заносится в сумматор в ПК, а В в ДК - оператор 13. Если А>0 и B>0 то оба числа заносятся в сумматор в ПК - оператор 12. Оба числа поступают на входы сумматора одновременно, при этом на выходах сумматора формируется значение суммы, которое записывается в регистр сумматора.

После сложения необходимо провести нормализацию результата (оператор 14). Для уменьшения погрешности выполняем округление результата (оператор 15). Полученная сумма анализируется в схеме формирования признака результата (оператор 16). Если число отрицательное (оператор 17) то результат преобразовывается в ПК и записывается в ОП (операторы 18 и 19), если нет, то результат просто заносится в ОП (оператор 19).

Приведённая схема является упрощённой

автомат переход возбуждение триггер

5. Разработка функциональной схемы блока управления

.1 Общая последовательность разработки

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

-    Формализация задания

-       Выбор типа автомата

-       Разметка схемы алгоритма

-       Составление таблицы переходов и выходов автоматов

-       Кодирование состояний

-       Составление кодированной таблицы переходов и выходов

-       Выбор типа триггеров

-       Преобразование таблицы переходов в таблицу функций возбуждения триггеров

-       Запись функций возбуждения и функций выходов в СДНФ

-       Минимизация функций возбуждения и функций выходов

-       Выбор типа логических элементов

-       Преобразование функций переходов и выходов

-       Построение функциональной схемы блока управления

-       Проверка правильности работы блока управления

.2 Формализация задания

При задании автомата микропрограммой количество входных сигналов равно числу различных условных операторов микропрограммы. В данном случае число условных операторов равно 5(операторы 8, 9 - одинаковы).

Для упрощения записи логических функций на рисунке 3 приняты следующие обозначения:

-  K - сигнал кода операции;

-        P - проверка разности порядков

- A - проверка знака числа А;

-  B - проверка знака числа В;

-        S - проверка знака результата.

Тогда входными сигналами блока управления являются сигналы K, P, A, B, S, каждый из которых может принимать значение 0 или 1.

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

При анализе микропрограммы можно установить, что безусловные операторы 2, 3, 4, 6, 14, 15, 17, 18, 19 содержат по одной микрооперации, а операторы 10, 11, 12, 13 - по две совместимых микрооперации. Однако операторы 10, 11, 12, 13 содержат повторяющиеся микрооперации. Кроме того, начальному оператору соответствует выходной сигнал, который сообщает о готовности блока управления к выполнению операции. Таким образом, общее число выходных сигналов равно 14. Обозначение выходных сигналов и соответствующие им микрооперации приведены в таблице 1.

Таблица 1

.3 Выбор типа автомата

Заданием предусмотрена реализация блока управления в виде автомата Мура

5.4 Разметка схемы алгоритма

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

1.      Начальный и конечный операторы помечаются символами начального состояния ().

.        Безусловные операторы помечаются символами последовательно пронумерованных состояний , , …

Размеченная схема алгоритма представлена на рисунке 5. Как видно по результатам разметки, автомат имеет 14 состояний (, , … ,Q₁₃).

.5 Составление таблицы переходов и выходов

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

В каждой клетке таблицы указывается новое состояние. Для сокращения размеров таблицы следует учесть, что при входном сигнале K = 0 автомат может находиться только в состоянии . Таблица переходов и выходов автомата приведена в виде таблицы 2.

Таблица 2

.6 Кодирование состояний

Принимаем естественный способ кодирования. Число элементов памяти при этом будет равно

n = (N) ­,

где: n - число элементов памяти;

N - число S состояний автомата;

­ - знак округления в большую сторону до целого.

При N = 14 получим:

n = ( 14) ­ = 4.

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

® 0000 ®  ® 0111 ®

® 0001 ®  ® 1000 ®

® 0010 ®  ® 1001 ®

® 0011 ®  ® 1010 ®

® 0100 ®  ® 1011 ®

® 0101 ®  ® 1100 ®

® 0110 ®  ® 1101 ®

5.7 Составление кодированной таблицы переходов и выходов

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

5.8 Выбор типа триггера

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

Таблица 3

.9 Преобразование таблицы переходов в таблицу функций возбуждения триггеров

Приведем преобразование таблицы переходов в таблицу функций возбуждения для

T - триггеров. Эта таблица имеет вид таблицы 4.

Таблица 4

5. 10 Запись функций возбуждения и функций выходов в СДНФ

Функции возбуждения T - триггера:

- - - - - - - - - - - - - - - - - - - - -

T₀ = (kpabs v kpabs)  v ( kpabs v kpabs v kpabs v kpabs) v

kv kv

-

kv k

- - - - - - - - - - - - - - - - - - - - - - - -

T₁ = (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v

kpabs v kpabs v kpabs v

- - - - - - - - - - - - - - -

kpabs v kpabs v kpabs) v (kpabs v kpabs v kpabs v kpabs)

v

- - - - - -

kv kv kv kv k

- - - - - - - - - - - - - - - - - - - -

T₂ = (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v

kpabs v kpabs v

- - - - - - - - - - - - - - - - - -

kpabs v kpabs) v (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v

kpabs v

- - - - - - - - - - - -)v kv kv kv kv k

- - - - - - - - - - - - - - - - - - -₃ = (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v

kpabs v kpabs v kpabs v

- - - - - - - - - - - - - - - - - - - - - - - -)  v (kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v kpabs v

kpabs) v

- - - - - - - - - - - - - - - - -v kv kv kv kv kv k

v

- - - -

kv k

Выражения в скобках можно упростить методом непосредственных преобразований. В результате получим следующие выражения:

- - - - - - - - - - - - -

T₀ = kpabv kabv kv kv kv k

- - - - - - - - - - - - -₁ = (kpb v kp v ka) v kabv kv kv k

v k v

-

- - - - - - - - - - - - -₂ = (kab v kab v kp) v (kab v kab)v kv kv

kv

- - -v k

- - - - - - - - - - - - - - - - -₃ = (kpb v kb) v kbv ksv kv kv k

v

- - - - - - - - - - -v kv kv kv kv k

Функции выходов:

_ _ _ _ _ _ _

Y₀=  Y₇= q¹q²q³q⁴ v

_ _ _ _ _ _ _ _

Y₁= Y₈=Ú

_ _ _ _ _

Y₂= Y₉=

_ _ _ _

Y₃= Y₁₀=

_ _ _ _

Y₄= Y₁₁=

_ _ _ _ _ _

Y₅=q¹q²q³q ⁴ v  Y₁₂=

_ _ _ _ _

Y₆= Ú  Y₁₃=

5.11  Минимизация функций возбуждения и функций выходов

Для окончательной минимизации функций используется метод Карно. При минимизации следует учесть, что все функции являются не полностью определенными, так как в таблице переходов не использованы состояния Q₁₄ и Q₁₅ .

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

Диаграммы Карно для функций T₀ , T₁ , T₂ , T₃ представлены на рисунках 15.12, 15.13, 15.14, 15.15.

В результате минимизации получим следующие выражения для функций T - триггеров:

T₀ = kpabv kabv k q²q³v k q¹q²q⁴ v k q¹q²q⁴

T₁ = kpbv kpv kav kabv k q²q⁴v k q²q³v k

q¹q³q⁴

T₂ = kabv kabv kpv kab v kabv k ²q³ vq¹q²q⁴ v k q¹q²q⁴

T₃ = kpb v kb v kb v ks v k q²q⁴v k q¹q³v k ³q⁴v k q²q³q⁴

5.12 Граф

Заключение

В результате выполнения задания синтезирован блок управления операции сложении в АЛУ.

Блок управления построен на основе автомата и имеет минимальный аппаратурный состав и обеспечивает формирование выходных сигналов при любых сочетаниях сигналов на входах блока.

Литература

1. Горнец Н.Н., Рощин А.Г., Соломенцев В.В. Организация ЭВМ и систем - М:2006

2.      Рощин А.Г., Половов Р.М. Тексты лекций по дисциплине "Теория автоматов" Ч.1.- М.

.        Рощин А.Г., Половов Р.М. Тексты лекций по дисциплине "Теория автоматов" Ч.2.- М.

.        Юхнов В.И.. Тексты лекций по дисциплине "Теория автоматов" СКФ МТУСИ 2010

.        Юхнов В.И. Методическое указание к курсовой работе СКФ МТУСИ 2010