Курсовая работа: Синтез цифровых схем арифметических устройств

Оглавление

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

Исходные данные к курсовому проекту

Разработка алгоритма умножения

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

Синтез преобразователя множителя

Логический синтез одноразрядного четверичного умножителя-сумматора

Логический синтез одноразрядного четверичного сумматора

Синтез МПА делителя

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

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

По исходным данным необходимо разработать:

1. Алгоритм выполнения операции умножения, для чего потребуется:

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

- представить числа в форме с плавающей запятой;

- произвести перемножение чисел по алгоритму “Г” в дополнительных разрядах на два разряда одновременно;

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

2. Алгоритм выполнения операций сложения и вычитания.

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

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

- логический синтез комбинационного одноразрядного четверичного сумматора (ОЧС) на основе составленной таблицы истинности для суммы слагаемых с учетом переноса из младшего разряда, используя при этом алгоритм извлечения (Рота), и оценить эффективность минимизации;

- логический синтез одноразрядного комбинационного четверичного умножителя-сумматора (ОЧУС), путем минимизации переключательных функций по каждому выходу схемы. Минимизация выполняется с применением карт Карно-Вейча с последующей оценкой эффективности минимизации;

- логический синтез комбинационной схемы преобразователя множителя (ПМ);

- построить функциональную схему ОЧС на мультиплексорах;

- построить функциональную схему ПМ и ОЧУС в заданном базисе;

5. Определить время умножения на один разряд и на n разрядов множителя.

6. Разработать алгоритм выполнения операции деления.

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

- построить граф связности автомата;

- разметить его для синтеза автомата Мура;

- построить таблицу переходов автомата;

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

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

Исходные данные к курсовому проекту

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

1. Исходные операнды - десятичные числа с целой и дробной частью, над которыми производится операция умножения (36,39 & 53,25).

2. Алгоритм выполнения операции умножения Г.

3. Метод ускоренного умножения на базе которого строится умножитель:

- умножение закодированного двоично-четверичного множимого на 2 разряда двоичного множителя одновременно в дополнительных кодах;

Преобразование множителя в обоих случаях производится для исключения из процесса умножения диады множителя 11.

4. Двоичные коды четверичных цифр множимого для работы в двоично-четверичной системе счисления (представляется кодом: 0₄ - 00, 1₄ - 11, 2₄ - 01, 3₄ - 10) . Множитель представляется обычным весомозначным кодом: 0₄ - 00, 1₄ - 01, 2₄ - 10, 3₄ - 11 .

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

- умножитель 2-го типа строится на базе ОЧУС, ОЧС и регистра результата.

6. Способ минимизации и логический базис для аппаратной реализации ОЧС и ОЧУС (функционально полный базис представлен функцией x₁ + x ₂ :

Таблица 1. Таблица истинности:

ОЧС реализуется на мультиплексорах).

7. Алгоритм выполнения операции деления:

- деление с восстановлением остатков;

8. Класс синтезируемого микропрограммного автомата: Мура.

9. Логический базис для аппаратной реализации делителя, как управляющего автомата: ПЛМ и триггеры для организации цепи обратной связи (Т -триггеры).

Разработка алгоритма умножения

1. Перевод сомножителей из десятичной системы счисления в четверичную:

МНОЖИМОЕ

36 | 4 0,39 Мн₄ =210,1203

36 9 | 4 4

0 8 2 1,56 Мн_2/4 = 011100,11010010

1 4

2,24

4

0,96

4

3,84

4

3,36

МНОЖИТЕЛЬ

53| 4 0,25 Мт₄ = 311,1

52 13 | 4 4 Мт_2/4 = 110101,01

1 12 3 1,00

1

2. Запишем сомножитель в форме с плавающей запятой в прямом коде:

Мн = 0,01110011010010 Р_мн = 0,0010 +03 закодирован по заданию

Мт = 0,11010101 Р_мт = 0,0011 +03 незакодирован по заданию

[Мт]_д = Мт = 0,3111₄ = 0,11010101_2/4

[Мт]_дп = 0,101010101_2/4

Мн = 0,2101203

[-Мн]_д = 3,1232131

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

Порядок произведения будет равен:

Р_мн = 0.0010₊ 03

Р_мт = 0.0011 03

Р = 0.1101 12

результат закодирован в соответствии с заданием на кодировку множимого.

Знак произведения определяется суммой по модулю два знаков сомножителей, т.е.:

зн Мн + зн Мт = 0 + 0 = 0.

Для умножения мантисс необходимо предварительно преобразовать множитель, чтобы исключить диаду 11(3₄ ), заменив ее на триаду 101.

Перемножение мантисс по алгоритму «Г» приведено втаблице 2:

[Мт]_дп = 0,101010101_2/4

Мн = 0,2101203

[-Мн]_д = 3,1232131

Таблица 2. Умножение по алгоритму “Г”.

4. После окончания умножения необходимо оценить погрешность вычислений. Для этого полученное произведение (Мн*Мт₄ =013210121133 Р_Мн*Мт = 6) приводится к нулевому порядку, а затем переводится в десятичную систему счисления:

Мн*Мт₄ = 132101,21133 Р_Мн*Мт = 0;

Мн*Мт₁₀ = 1937,5927734375.

Результат прямого перемножения операндов дает следующее значение:

Мн₁₀ *Мт₁₀ = 36,39 * 53,25 = 1937,7675.

Абсолютная погрешность:

D = 1937,7675 - 1937,5927734375 = 0,17473.

Относительная погрешность:

D 0,17473

d = = = 0,00009017 (d = 0,00901%)

Мн*Мт 1937,7675

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

В случае отрицательного множимого:

[Мт]_дп = 0,101010101_2/4

Мн = - 0,2101203

[Мн]_д = 3,1232131

[-Мн]_д = 0,2101203

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

Структурная схема строится на основе следующих блоков

· Многоразрядный регистр сдвига

сдвиг

Dn Q1

С Qn

S1

S2

“+1”

Предназначен для хранения и сдвига n-разрядного значения числа. Регистр имеет n информационных входов D1 – Dn , управляющий вход разрешения записи в регистр С , управляющие входы сдвига содержимого регистра влево S1 и вправо S2 , управляющий вход добавления 1 к содержимому регистра “+1”, и n выходов Q1- Qn . Все управляющие функции выполняются при поступлении 1 на соответствующий управляющий вход.

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

· Одноразрядный четверичный умножитель - сумматор (ОЧУС)

R

P2 Р1

ОЧУС

ОЧУС

к старшему

ОЧУС

Мн Мт

ОЧУС предназначен для получения одной четверичной цифры путем перемножения диады множимого (Мн) и диады множителя (Мт), и прибавления к полученному результату переноса от младшего ОЧУС (P1).

Если устройство работает как сумматор, то оба слагаемых последовательно (за 2 такта) заносятся в регистр множимого, а на управляющий вход ФДК F₂ поступает «1». На выходах ФДК формируется дополнительный код первого слагаемого с учетом знака. Первое слагаемое без изменений должно быть записано в регистр результата, поэтому управляющие сигналы, поступающие на входы «h» всех ОЧУС, позволяют переписать на выходы ОЧУС разряды первого слагаемого без изменений. Если на вход «h» поступает «0», то ОЧУС перемножает разряды Мн и Мт и добавляет к полученному результату перенос из предыдущего ОЧУС.

Если устройство работает как умножитель, то множимое и множитель помещаются в соответствующие регистры, а на управляющий вход ФДК F₂ поступает «0». Диада множителя поступает на входы ПМ.

Т.к. на входы ОЧУС из регистра Мт не могут прийти коды «3», в таблице истинности работы ОЧУС будут содержаться 16 безразличных входных наборов.

После ОЧУС частичные произведения складываются между собой в ОЧС (на первом такте идет сложение с нулем).

Частичные суммы хранятся в регистре результата.

· Одноразрядный четверичный сумматор (ОЧС)

S

P2 P1

А В

Предназначен для суммирования двух четверичных цифр и прибавления к полученной сумме единицы переноса от предыдущего ОЧС. Формирует единицу переноса в следующий ОЧС.

В ОЧС первое слагаемое складывается с нулем, записанным в регистре результата, и переписывается без изменений в регистр результата. На втором такте второе слагаемое из регистра множимого через цепочку ОЧУС попадает на входы ОЧС и складывается с первым слагаемым, хранящимся в регистре результата. Сумма хранится в регистре результата. Если устройство работает как сумматор, никаких сдвигов содержимого регистров не производится.

· Многоразрядный формирователь дополнительного кода (ФДК)

Знак Yn Y1

f1

f2

Знак Xn X1

Предназначен для получения дополнительного кода многоразрядного четверичного числа. ФДК имеет n двоичных входов (Х1-Хn), n двоичных выходов (Y1-Yn), отдельный вход для знака преобразуемого числа, а также управляющие входы (f1) и (f2). При подаче управляющего сигнала (“1”) на вход f1 ФДК формирует дополнительный код числа в сооответствии с его знаком. При подаче управляющего сигнала (“1”) на вход f2 ФДК формирует двойной дополнительный код числа. Принцип работы ФДК в зависимости от управляющих сигналов см. в табл.3.

Таблица 3. Работа ФДК.

Синтез преобразователя множителя

Задачей ПМ является исключить из множителя диады 11, заменив их на триады. Регистр множителя является сдвиговым, после каждого такта умножение его содержимое сдвигается на 2 двоичных разряда, и в конце умножения регистр обнуляется. Выход 3 ПМ переходит в единичное состояние, если текущая диада содержит отрицание ( 01 ). В этом случае инициализируется управляющий вход F₁ формирователя дополнительного кода (ФДК), и на выходах ФДК формируется двойной дополнительный код множимого (умножение на -1).

На выходах 1,2 ПМ формируются диады преобразованного множителя, которые поступают на входы ОЧУС вместе с диадами множимого. На трех выходах ОЧУС формируется результат умножения диад Мн * Мт + перенос из предыдущего ОЧУС. Максимальной цифрой в диаде преобразованного множителя является двойка, поэтому перенос, формируемый ОЧУС ,может быть только двоичным:

3 * 2 = 1 2

max maх max

Мн Мт перенос

Табл.4. Таблица истинности преобразователя множителя.

Исходя из выше изложенной таблицы синтезируется схема.

Преобразователь множителя.

Структурная схема устройства приведена на рисунке в приложении. Она содержит регистры: множимого (Рг Мн), множителя (Рг Мт), результата (Рг Рез), формирователи дополнительного кода (ФДК) , 16 блоков ОЧС, 15 блоков ОЧУС и преобразователь множителя (ПМ).

Устройство умножения работает следующим образом:

Исходные сомножители записываются в регистры ( Рг Мн, Рг Мт) Рг Рез обнуляется.

С выходов ФДК на входы ОЧУС поступают по 2 двоичные цифры. Результат операции поступает в ОЧС, где суммируется с содержимым Рг Рез и записывается снова в Рг Рез.

После проведения этих операций происходит сдвиг Рг Мн , Рг Мт .

Если на вход “h” подаётся “1” то ОЧУС становятся “прозрачными” и устройство работает как сумматор благодаря ОЧС. Слогаемые последовательно (за 2 такта) заносятся в регистр множимого.

Временные затраты на умножение сомножителей определяются в основном затратами на образование частичных произведений, получаемых на выходах ОЧУС, и примерно равны:

Ту = 8(tсдв + tПМ + tФДК + 15tОЧУС + 16tОЧС), где:

tОЧС- время формирования единицы переноса в ОЧС

tОЧУС – время умножения на одном ОЧУС

tсдв -время сдвига множимого (множителя)

tПМ – время задержки в преобразователе множителя

tФДК – время задержки на ФДК

На самом деле, операции выполняются параллельно в нескольких узлах, и время задержки будет определятся наибольшей составляющей (либо 15tОЧУС, либо 15tОЧУС, в зависимости от конкретной реализации).

Логический синтез одноразрядного четверичного умножителя-сумматора

ОЧУС - это комбинационное устройство, имеющее 6 входов (2 разряда из регистра МН, 2 разряда из регистра Мт, вход переноса и управляющий вход h) и 3 выхода. Принцип работы ОЧУС описывается с помощью таблицы истинности (табл.5).

Разряды множителя закодированы : 0 - 00; 1 - 01; 2 - 10; 3 - 11.

Разряды множимого закодированы : 0 - 00; 1 - 11; 2 - 01; 3 - 10.

Управляющий вход h определяет тип операции: 0 - умножение закодированных цифр, поступивших на информационные входы, и добавление переноса; 1 - вывод на выходы без изменения значения разрядов, поступивших из регистра множимого.

Табл. 5

В таблице выделено 16 безразличных наборов, т.к. на входы ОЧУС из разрядов множителя не может поступить код 11.

Таблица 6. Шестнадцать безразличных наборов для ОЧУС.

Таблица 7. Единичные наборы для выхода Q1 ОЧУС:

Таблица 8. Карта Карно-Вейча для единичных наборов выхода Q1 ОЧУС:

Q1 = X1 H + P1 X1 Y2 + P1 Y2 H + P1 X1 H =

= X1(H + P1 Y2) + P1 H(Y2 X1)

Таблица 9. Единичные наборы для выхода Q2 ОЧУС:

Таблица 10. Карта Карно-Вейча для нулевых наборов выхода Q2 ОЧУС:

Q2=(X2+H)*(P1+X2+Y1)*(P1+Y1+Y2+H)*(X1+X2+Y2)*(P1+X1+Y1+Y2+H)* *(P1+X1+X2+Y2+H)*(P1+X1+Y1+H)

Таблица 11. Единичные наборы для выхода переноса ОЧУС P2:

Таблица 12. Карта Карно-Вейча для единичных наборов выхода переноса ОЧУС P:

P = X1 X2 Y1 H + X1 X2 Y1 H + P1 X1 X2 Y2 H =

= H X2 X1 (Y1 + P1 Y2) + X1 X2 Y1 H = H(X1 X2 Y1 + X1 X2(Y1 + P1 Y2))

Эффективность минимизации определяется коэфицентом минимизации. Он расчитывается по следующей формуле:

Цена исходного покрытия

Коэф.=-----------------------------------------

Цена минимального покрытия

Таблица 13. Коэфициент минимизации.

Логический синтез одноразрядного четверичного сумматора

ОЧС - это комбинационное устройство, имеющее 5 входов (2 разряда одного слагаемого, 2 разряда второго слагаемого и вход переноса) и 3 выхода. Принцип работы ОЧС описывается с помощью таблицы истинности (табл.3).

Разряды обоих слагаемых закодированы: 0 - 00; 1 – 11; 2 - 01; 3 - 10.

Таблица истинности функционирования ОЧС строится для пяти переменных, четыре из которых (А1, А2, В1, В2) являются выходами ОЧУС, а пятая – межразрядный перенос из ОЧС смежного старшего разряда устройства умножения. Четверичная цифра суммы как диада S1S2 в таблице истинности образуется с учётом принятого кодирования четверичных цифр.

Табл. 14

Безразличные наборы в таблице истинности отсутствуют т.к. со старших выходов ОЧУС могут прийти коды 0, 1, 2 и 3.

Таблица 15. Единичные наборы для выхода переноса P ОЧС.

Таблица 16. Единичные наборы для выхода S1 ОЧС.

Таблица 17. Единичные наборы для выхода S2 ОЧС.

Алгоритм Рота для выхода переноса ОЧС

Отыскание множества L-экстремалей

Z0={Æ}; C0=L;

Множество С0: 11101; 00101; 01010; 01011; 01100; 01101; 01111; 10001;

10010; 10011; 10100; 10101; 10110; 10111; 11011.

Кубы, образовавшиеся в этой таблице, образуют множество A1. Множество C1 получаем по формуле: C1=A1È(C0-Z0)

Множество C1: x1101; 1x101; 1110x; 0x101; x0101; 0101x; 01x11; x1011; 0110x; x1100; 011x1; 100x1; 10x01; 1001x; 10x10; 10x11; 1x011; 1010x; 101x0; 1x100; 101x1; 1011x.

Множество C2: xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx.

Множество С3 – пустое (склеивание не дало новых кубов более высокой размерности).

Множество простых имплекант Z: 0101x; 01x11; x1011; 011x1; 1x011; xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx.

Отбросим те кубы из множества Z, которые покрываются другими.

С помощью операции пересечения находим L-экстремали образованные на множестве N.

N={Æ}

Кубы на множестве L: 01010; 00101; 01100; 10001; 10010.

L-экстремали: 0101x; xx101; x110x; 10xx1; 10x1x.

Найдём кубы из L не покрытые L-экстремалями.

Из оставшегося Z (за исключением L-экстремалей) выберем кубы которые покроют остаток множества L.

Тупиковые формы: 01x11, 011x1 & 1x10x, 101xx

Минимизированная переключательная функция для выхода переноса ОЧС C_min :

0101x; xx101; x110x; 10xx1; 10x1x; 01x11; 101xx.

Алгоритм Рота для выхода S1 ОЧС

C0=L; Z0=0;

Множество С0: 00001; 00011; 00100; 00110; 01001; 01011; 01100; 01110; 10000

10010; 10101; 10111; 11000; 11010; 11101

C1=A1È(C0-Z0)

Множество C1: 000x1; 0x001; 0x011; 001x0; 0x100; 0x110; 010x1; 011x0; 100x0; 1x000; 1x010; 101x1; 1x101; 1x111; 110x0; 111x1.

Множество C2: 0x0x1; 0x1x0; 1x0x0; 1x1x1.

Множество С3 – пустое.

Множество простых имплекант Z: 0x0x1; 0x1x0 1x0x0; 1x1x1.

С помощью операции пересечения находим L-экстремали образованные на множестве N.

Так как N={Æ} то всё Z образовано на множестве L.

Кубы на множестве L: 0x0x1; 0x1x0; 1x0x0; 1x1x1.

L-экстремали: 0x0x1; 0x1x0; 1x0x0; 1x1x1.

Проверим, не осталось ли кубов из L не покрытых L-экстремалями.

Все L-экстремали, и только они входят в C_min : 0x0x1; 0x1x0; 1x0x0; 1x1x1.

Алгоритм Рота для выхода S2 ОЧС:

С0=L; Z0=0;

Множество С0: 00001; 00010; 00110; 00111; 01000; 01011; 01100; 01101; 10010; 10011; 10100; 10111; 11000; 11001; 11101.

Множество C1:

00x10 x0010 0011x x0111 01x00 x1000 0110x x1101 1001x 10x11 1100x 11x01

C1=A1È(C0\Z0)

Множество С2 - пустое

Множество простых имплекант Z: 00001; 01011; 10100; 11110; 00x10; x0010;

0011x; x0111; 01x00; x1000; 0110x; x1101; 1001x; 10x11; 1100x; 11x01.

Кубы на множестве L: 00001; 01011; 10100; 11110.

L-экстремали: 00001; 01011 10100; 11110.

Тупиковые формы: 00x10, x0111, 01x00, x1101, 1001x, 1100x

C_min =00001; 01011 10100; 11110, 00x10, x0111, 01x00, x1101, 1001x, 1100x

Эффективность минимизации определяется коэфицентом минимизации. Он расчитывается по следующей формуле:

Цена исходного покрытия

Коэф.=-----------------------------------------

Цена минимального покрытия

Таблица 13. Коэфициент минимизации.

Синтез МПА делителя

Автомат должен управлять делением с восстановления остатка. Блок-схема этого алгоритма приведена ниже:

Y0 – суммирование делимого и двойного дополнительного кода делителя.;

Y1 – занесение нуля в регистр частного, восстановление остатка (суммирование делимого и делителя);

Y2 – занесение единицы в регистр частного;

Y3 – сдвиг регистра суммы и частного влего, наращивание точности частного;

X1 – проверка знакового разряда регистра суммы (0 – положительное, 1 - отрицательное);

X2 – проверка достижения точности вычисления;

По условию задачи делитель необходимо синтезировать в виде управляющего автомата Мура. Разметка ГСА в этом случае происходит по следующему алгоритму:

1. Меткой a1 отмечаются первая и последняя вершины.

2. Метками a2..am отмечаются все операторные вершины.

По отмеченной ГСА строится таблица переходов:

По построенной таблице сформируем таблицу истинности для настройки ПЛМ:

По полученной таблице построим автомат, в качестве памяти используя T-триггеры.