Синтез микропрограммного управляющего автомата

Введение

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

Применение моделей в «Теории автоматов» не ограничивается какой-либо частной областью, а возможно для решения проблем практически в любой области исследования.

1 Постановка задачи

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

2 Описание используемого алгоритма умножения Разобьем заданный алгоритм умножения на 2 части и рассмотрим каждую в отдельности.

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

2.2 Умножение чисел в дополнительном коде с автоматической коррекцией Результатом умножения является число в ДК со знаком. Сомножители участвуют в операции со знаковыми разрядами, при этом знаковые разряды рассматриваются как числовые. При умножении анализируются сразу две смежные цифры множителя по следующим правилам:

если цифра множителя, на которую надо умножить в данном такте, равна единице, а цифра соседнего младшего разряда множителя равна нулю (10), то множимое надо вычитать из предыдущей частной суммы;

если цифра множителя, на которую надо умножить в данном такте, равна нулю, а цифра соседнего младшего разряда множителя равна единице (01), то множимое надо складывать с предыдущей частной суммой;

если анализируемые цифры совпадают (00, 11), то никаких операций не производится.

Второй способ при умножении чисел в ДК с автоматической коррекцией никакими особенностями не обладает.

2.3 Умножение чисел с плавающей запятой с характеристикой Числа с ПЗ в ЭВМ представляются так, как представлено на рисунке 1.

Знак порядок мантисса (характеристика)

Рисунок 1 — Представление чисел с ПЗ

Если под число выделено четыре байта, то в первом разряде находится знак мантиссы, в следующих восьми — порядок, и в оставшихся двадцати трех — мантисса.

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

При умножении чисел с ПЗ в порядках может возникнуть ПРС.

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

2.4 Численный пример

Множимое:C=-75=-1 001 011

Представление с ПЗ: С=1 0100 1 101 010 000

Множитель:D=22=10 110

Представление с ПЗ: D=0 0010 10 110 000 000

Умножение мантисс чисел приведено в таблице 1.

Таблица 1

Складываем характеристики чисел:

характеристика С: 0100

характеристика D: 0010

коррекция характеристики: 1000

коррекция при округлении: 1011

характеристика Y: 1001

Представление с ПЗ: Y=1 1001 10 011 000 111

Нормализуем: Y=1 1000 110 001 111

Произведение: Y=-11 001 110 010=-1650

3 Обоснование и выбор функциональной схемы операционной части устройства и определение микроопераций и логических условий

Операционный автомат содержит следующие элементы (приложение А):

8^и разрядный регистр RG1 для хранения характеристик;

25^и разрядный сдвиговый регистр RG2 для хранения множителя;

47^и разрядный сдвиговый RG3 для хранения множимого;

47^и разрядный сдвиговый регистр RG4 для хранения частных сумм;

8^и разрядный сумматор SM1 для сложения характеристик;

47^и разрядный сумматор SM2 для сложения множимого с частными суммами;

обратный 8^и разрядный счетчик СТ1 для хранения характеристик и работы с ними;

обратный 5^и разрядный счетчик СТ2 для управления циклом умножения;

47^и разрядный двухплечевой мультиплексор для получения инвертированного или неинвертированного множимого;

8^и разрядный элемент «и» для обнаружения возможности нормализации результата;

5^и разрядный элемент «и» для управления циклом;

2 схемы сложения по модулю два и 2-х входовой элемент «и» для выявления нулевых операндов;

2 схемы сложения по модулю два и 2-х входовой элемент «или-не» для выявления ПРС;

1 схема сложения по модулю 2 и 2-х входовой элемент «или» для управления нормализацией результата;

1 схема сложения по модулю 2 для работы с 2-мя разрядами множителя;

1 D-триггер для хранения старшего разряда характеристики 1-го операнда;

1 RS-триггер для хранения признака ПРС;

инвертор для коррекции полученной характеристики;

усилитель-формирователь для выдачи результата на выходную шину;

Операнды разрядностью 4 байта поступают по входной шине в операционный автомат. Характеристика множителя записывается в регистр RG1, мантисса — в регистр RG2. Затем информация из RG1 заносится в СТ1, а также старший разряд RG1 записывается на триггер T1. Далее, с шины в RG3 записывается мантисса множимого, а регистр RG1 записывается его характеристика. После этого содержимое регистра RG1 складывается с информацией на СТ1, и результат записывается в СТ1. Инициализируется счетчик СТ2 (11 000) и начинается цикл умножения. После умножения, если нужно и возможно, производится нормализация.

Для организации работы необходимо, чтобы УА подавал в ОА управляющие сигналы, реализующие следующие МО:

у0 — занесение характеристики в RG1;

у1 — занесение множителя в RG2, сброс Т2, RG4, СТ1, инициализация СТ2;

у2 — занесение множимого в RG3;

у3 — запись информации в CT1;

у4 — сдвиг RG2 вправо, сдвиг RG3 влево, уменьшение СТ1 на 1;

у5 — управление мультиплексором (если у5=1, то подключается плечо А, в противном случае — В), единица переноса в SM2;

у6 — запись информации в RG4;

у7 — сдвиг RG4 влево, уменьшение СТ1 на 1;

у8 — выдача результата на выходную шину;

у9 — установка триггера T1;

Из ОА в УА необходимо передавать осведомительные сигналы о состоянии ОА, которые определяются следующими логическими условиями (ЛУ):

Х — проверка наличия операндов на входной шине;

р0 — произошло ПРС;

р1 — если равно 0, то один или оба операнда равны 0;

р2 — конец цикла;

р3 — если равно 0, то следует произвести нормализацию результата;

р4 — старший из двух анализируемых разрядов множителя;

р5 — результат сложения по модулю 2 двух анализируемых разрядов множителя;

Z — проверка возможности выдачи результата на выходную шину;

4. Разработка содержательной граф-схемы алгоритма

Работа автомата начинается с получения данных через входную шину. Данные записываются в регистры RG1, RG2 и RG3 (блоки 1−2, 4−5). Кроме того, производится суммирование характеристик (блоки 3 и 6). Затем выполняется проверка на нулевой операнд (блок 7). Выполняется проверка на ПРС (блок 8). Затем, если ПРС не произошло, производится анализ разрядов множителя (блоки 9−10):

если р5=1, то анализируется р4 (старший из анализируемых разрядов множителя):

если р4=1, то следует произвести вычитание множимого из частных сумм (блок 12);

если р4=0, то следует произвести прибавление множимого к частным суммам (блок 11);

— если р5=0, то ни вычитания, ни сложения не производится;

После этого выполняются сдвиги регистров и изменение счетчика (блок 13), а затем проверка на окончание цикла умножения (блок 14). Далее следует проверка, следует ли нормализовать мантиссу (блоки 15−16). Затем — проверка возможности выдачи результата на выходную шину и, собственно, выдача результата (блоки 17−18).

Содержательная ГСА приведена в приложении Б.

5. Построение отмеченной граф-схемы алгоритма

Для разметки ГСА каждой совокупности микроопераций, находящихся в операторных вершинах, ставятся в соответствие управляющие сигналы Y1… Yn. Эти сигналы являются выходными сигналами УА и обеспечивают выполнение требуемых действий в соответствии со списком МО операционного автомата. Совокупности МО для каждой операторной вершины образуют МК, список которых приведен в таблице 2.

Таблица 2

Каждой условной вершине содержательной ГСА ставится в соответствие один из входных сигналов управляющего автомата X1… Xm, список которых приведен в таблице 3.

Таблица 3

Далее в полном соответствии с содержательной ГСА строится отмеченная ГСА, условным вершинам которой приписывается один из входных сигналов УА, а операторным вершинам — одна из МК (приложение В).

Получаем ГСА, размеченную для модели Мили символами a₀…a₇, для модели Мура символами b₀…b₁₁.

6. Построение графов автомата для моделей Мили и Мура

На основе отмеченной ГСА построены графы автомата для модели Мили (приложение Г) и для модели Мура (приложение Д).

Граф автомата Мили имеет 8 вершин, соответствующих состояниям автомата a₀,…, a₇. Дуги его отмечены входными сигналами, действующими на каждом переходе, и набором выходных сигналов, вырабатываемых УА на данном переходе.

Граф автомата Мура имеет 12 вершин, соответствующих состояниям автомата b₀,…, b₁₁, каждое их которых (кроме фиктивных) определяет наборы выходных сигналов y₀,…, y₈ УА, а дуги графа отмечены входными сигналами, действующими на данном переходе.

7. Выбор и обоснование функциональной схемы управляющего автомата и типов элементов памяти

Рассмотрим некоторые варианты возможных структурных схем УА, предложенные в [2]:

классическая структура УА пригодна для реализации любого УА, но она не является минимальной с точки зрения цены КС;

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

структура УА на основе сдвигового регистра с выбором унитарного кодирования внутренних состояний целесообразно использовать только в тех случаях, когда число разрядов кода ненамного меньше числа внутренних состояний, иначе возникнут значительные затраты на память автомата, которые поглотят выигрыш от уменьшения цены КС;

структура на основе счетчика выгодна, когда граф проектируемого автомата имеет большое количество последовательных (стандартных) переходов и незначительное число нестандартных;

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

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

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

Для кодирования состояний автомата Мура потребуется 4 разряда. Поэтому для реализации управляющего автомата на основе модели Мура потребуется 4-х разрядный регистр и дешифратор.

8. Кодирование внутренних состояний автомата В управляющем автомате в качестве ЭП могут использоваться как D-триггеры, так и RS-триггеры. Также могут использоваться и счетчики.

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

Для RS-триггеров лучше использовать соседнее кодирование, так как именно этот способ минимизирует число переключений ЭП.

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

8.1 Кодирование состояний для модели Мили на D-триггерах Составим инверсную таблицу переходов (см. таблицу 4) и закодируем состояния четырехразрядными двоичными числами, в которые будет входить наименьшее число единиц.

Таблица 4

Как видно из таблицы 4, состояние a₀ с наибольшим числом переходов в него кодируется 000. Состояния с меньшим числом переходов обозначаются кодом с одной единицей, затем с двумя и до тех пор, пока все состояния графа не будут закодированы.

8.2 Кодирование состояний для модели Мура на D-триггерах Составим инверсную таблицу переходов (см. таблицу 5) и закодируем состояния четырехразрядными двоичными числами, в которые будет входить наименьшее число единиц.

Таблица 5

8.3 Кодирование состояний для модели Мили на RS-триггерах Составим матрицу переходов М и произведем кодирование состояний автомата.

1) K (a₀)=000

K (a₁)=001

2) =2B={1}

C₁={011, 101}

K (a₂)=011

3) =3B={2}

C₂={111, 010}

K (a₃)=111

4) =4B={3, 0}

C₃={101, 110}

C₀={100, 010}

W₁₀₁=1+2=3

W₁₁₀=1+2=3

W₁₀₀=2+1=3

W₀₁₀=2+1=3

K (a₄)=101

5) =5B={4}

C₄={100}

K (a₅)=100

6) =7B={4, 0}

C₄={}

C₀={010}

K (a₇)=010

7) K (a₆)=110

8.4 Кодирование состояний для модели Мура на RS-триггерах Составим матрицу переходов М и произведем кодирование состояний автомата.

1) K (b₀)=0000

2) K (b₁)=0001

3) 2) =2B={1}

4) C₁={0011,0101,1001}

5) K (b₂)=0011

3) =3B={2}

C₂={1011,0111,0010}

K (b₃)=0010

4) =4B={2,3}

C₂={1011, 0111}

C₃={1010, 0110}

W₁₀₁₁=1+2=3

W₀₁₁₁=1+2=3

W₁₀₁₀=2+1=3

W₀₁₁₀=2+1=3

K (b₄)=1011

5) =5B={4, 0}

C₄={1111, 1001, 1010}

C₀={1000, 0100}

W₁₁₁₁=1+4=5

W₁₀₀₁=1+2=3

W₁₀₁₀=1+2=3

W₁₀₀₀=2+1=3

W₀₁₀₀=4+1=5

K (b₅)=1001

6) =6B={5}

C₅={1101, 1000}

K (b₆)=1101

7) =7B={5}

C₅={1000}

K (b₇)=1000

8) =8B={5,6,7}

C₅={}

C₆={0101, 1111, 1100}

C₇={1010}

W₀₁₀₁=2+1+3=6

W₁₁₁₁=2+1+3=6

W₁₁₀₀=2+1+1=4

W₁₀₁₀=2+3+1=6

K (b₈)=1100

9) =10B={5,8}

C₅={}

C₈={0100, 1110}

W₀₁₀₀=3+1=4

W₁₁₁₀=3+1=4

K (b₁₀)=1110

10) =11B={5,8,10,0}

C₅={}

C₁₀={0110, 1111}

C₈={0100}

C₀={}

W₀₁₁₀=2+4+2+1=9

W₁₁₁₁=4+2+2+1=9

W₀₁₀₀=1+3+1+2=7

K (b₁₁)=0100

11) =9B={8, 10, 11}

C₈={}

C₁₀={0110, 1111}

C₁₁={0101}

W₀₁₁₀=2+1+1=4

W₁₁₁₁=2+1+2=5

W₀₁₀₁=2+3+1=6

K (b₉)=0110

8.5 Кодирование состояний для модели Мили на счетчике Закодируем состояния таким образом, чтобы разность кодов между соседними состояниями составляла единицу (см. таблицу 6).

Таблица 6

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

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

9.1 Получение и минимизация логических уравнений для модели Мили на D-триггерах Структурная таблица переходов и выходов представлена в таблице 7.

Таблица 7

Из таблицы получим логические выражения для каждой функции возбуждения D-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний a_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

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

Цена комбинационной схемы по Квайну C=49.

9.2 Получение и минимизация логических уравнений для модели Мура на D-триггерах Структурная таблица переходов и выходов представлена в таблице 8.

Таблица 8

Из таблицы получим логические выражения для каждой функции возбуждения D-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний b_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

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

Цена комбинационной схемы по Квайну C=87.

9.3 Получение и минимизация логических уравнений для модели Мили на RS-триггерах Структурная таблица переходов и выходов представлена в таблице 9

Таблица 9

Из таблицы получим логические выражения для каждой функции возбуждения RS-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний a_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

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

Цена комбинационной схемы по Квайну C=45.

9.4 Получение и минимизация логических уравнений для модели Мура на RS-триггерах Таблица 10

Структурная таблица переходов и выходов представлена в таблице 10.

Из таблицы получим логические выражения для каждой функции возбуждения RS-триггера, а также для функций выходов как конъюнкции соответствующих исходных состояний b_m и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.

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

Цена комбинационной схемы по Квайну C=91.

9.5 Получение и минимизация логических уравнений для модели Мили на счетчике Структурная таблица переходов и выходов представлена в таблице 11.

Таблица 11

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

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

Цена комбинационной схемы по Квайну C=49.

10. Построение функциональной схемы управляющего микропрограммного автомата Сравнение вариантов моделей Мили и Мура показывает, что модель Мура в случаях для RS-триггеров и D-триггеров дает более сложную схему.

Наиболее оптимальной по аппаратурным затратам является модель Мили на RS-триггерах. Ее цена по Квайну составляет 45, поэтому построение функциональной схемы будем производить для нее.

Функциональная схема построена в основном логическом базисе в полном соответствии с приведенной для модели Мили системой логических уравнений для выходов и функций возбуждения ЭП. Кроме того, на схему подаются сигналы синхронизации C и начальной установки B.

Заключение

В ходе выполнения курсовой работы был разработан автомат, управляющий операцией умножения двоичных чисел с ПЗ в ДК с автоматической коррекцией. Были рассмотрены 5 вариантов построения управляющего автомата: 3 варианта для модели Мили (на D-триггерах, на RS-триггерах и на счетчике) и 2 варианта для модели Мура (на Dи на RS-триггерах). Оказалось, что наименьшую комбинационную схему дает модель Мили с использованием RS-триггеров. Причем, в схеме использован дешифратор на 3 разряда.

Приложение, А Функциональная схема операционного автомата

Приложение Б Граф автомата для модели Мили