Оглавление
Постановка задачи
Исходные данные к курсовому проекту
Разработка алгоритма умножения
Разработка структурной схемы устройства
Синтез преобразователя множителя
Логический синтез одноразрядного четверичного умножителя-сумматора
Логический синтез одноразрядного четверичного сумматора
Синтез МПА делителя
Постановка задачи
Курсовой проект предполагает синтез цифровых схем арифметических устройств, выполняющих операции сложения, вычитания, умножения и деления над числами, представленными в форме с плавающей запятой в двоичной и двоично-четверичной системах счисления.
По исходным данным необходимо разработать:
Алгоритм выполнения операции умножения, для чего потребуется:
/>перевести исходные числа из десятичной системы счисления в двоично-десятичную;
представить числа в форме с плавающей запятой;
произвести перемножение чисел по алгоритму “Г” в дополнительных разрядах на два разряда одновременно;
оценить погрешность вычисления после перевода результата в исходную систему счисления.
Алгоритм выполнения операций сложения и вычитания.
Структурную схему комбинированного устройства (сложение и умножение), содержащую узлы для действия над мантиссами и порядками, и определить время умножения с учетом временных задержек в комбинационных схемах.
Функциональные схемы основных узлов проектируемого сумматора-умножителя в заданном логическом базисе. Для этого провести:
логический синтез комбинационного одноразрядного четверичного сумматора (ОЧС) на основе составленной таблицы истинности для суммы слагаемых с учетом переноса из младшего разряда, используя при этом алгоритм извлечения (Рота), и оценить эффективность минимизации;
логический синтез одноразрядного комбинационного четверичного умножителя-сумматора (ОЧУС), путем минимизации переключательных функций по каждому выходу схемы. Минимизация выполняется с применением карт Карно-Вейча с последующей оценкой эффективности минимизации;
логический синтез комбинационной схемы преобразователя множителя (ПМ);
построить функциональную схему ОЧС на мультиплексорах;
построить функциональную схему ПМ и ОЧУС в заданном базисе;
Определить время умножения на один разряд и на n разрядов множителя.
Разработать алгоритм выполнения операции деления.
Функциональную схему делителя, представив его как управляющий автомат, для чего необходимо:
построить граф связности автомата;
разметить его для синтеза автомата Мура;
построить таблицу переходов автомата;
определить переключательные функции выходных сигналов и сигналов обратной связи;
построить функциональную схему делителя на базе программируемой логической матрицы и заданных триггеров.
Исходные данные к курсовому проекту
В качестве исходных данных к курсовому проекту задается следующее:
Исходные операнды — десятичные числа с целой и дробной частью, над которыми производится операция умножения (36,39 & 53,25).
Алгоритм выполнения операции умножения Г.
Метод ускоренного умножения на базе которого строится умножитель:
умножение закодированного двоично-четверичного множимого на 2 разряда двоичного множителя одновременно в дополнительных кодах;
Преобразование множителя в обоих случаях производится для исключения из процесса умножения диады множителя 11.
Двоичные коды четверичных цифр множимого для работы в двоично-четверичной системе счисления (представляется кодом: 4— 00, 14— 11, 24— 01, 34— 10). Множитель представляется обычным весомозначным кодом: 4— 00, 14— 01, 24— 10, 34— 11.
Тип синтезируемого устройства умножения, определяемый основными структурными узлами, на базе которых строится умножитель:
умножитель 2-го типа строится на базе ОЧУС, ОЧС и регистра результата.
/>Способ минимизации и логический базис для аппаратной реализации ОЧС и ОЧУС (функционально полный базис представлен функцией x1 +x2 :
/>
Таблица 1. Таблица истинности:
X1
X2
1
не 1
1
1
1
1
1
1
1
1
ОЧС реализуется на мультиплексорах).
Алгоритм выполнения операции деления:
деление с восстановлением остатков;
Класс синтезируемого микропрограммного автомата: Мура.
Логический базис для аппаратной реализации делителя, как управляющего автомата: ПЛМ и триггеры для организации цепи обратной связи (Т -триггеры).
Разработка алгоритма умножения
Перевод сомножителей из десятичной системы счисления в четверичную:
МНОЖИМОЕ
36 |4 0,39 Мн4 =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 Мт4 = 311,1
52 13|44Мт2/4 = 110101,01
1 123 1,00
1
Запишем сомножитель в форме с плавающей запятой в прямом коде:
Мн = 0,01110011010010 Рмн = 0,0010 +03 закодирован по заданию
Мт = 0,11010101 Рмт = 0,0011 +03 незакодирован по заданию
[Мт]д = Мт = 0,31114 = 0,110101012/4
[Мт]дп = 0,1010101012/4
Мн = 0,2101203
[-Мн]д = 3,1232131
Умножение двух чисел с плавающей запятой на 2 разряда множителя одновременно в дополнительных кодах сводится к сложению порядков, формированию знака произведения, преобразованию разрядов множителя с целью исключения диады 11, и перемножению мантисс сомножителей.--PAGE_BREAK--
Порядок произведения будет равен:
Рмн = 0.0010+ 03
Рмт= 0.0011 03
Р = 0.1101 12
результат закодирован в соответствии с заданием на кодировку множимого.
Знак произведения определяется суммой по модулю два знаков сомножителей, т.е.:
зн Мн + зн Мт = 0 + 0 = 0.
/>/>/>Для умножения мантисс необходимо предварительно преобразовать множитель, чтобы исключить диаду 11(34), заменив ее на триаду 101.
Перемножение мантисс по алгоритму «Г» приведено втаблице 2:
[Мт]дп = 0,1010101012/4
Мн = 0,2101203
[-Мн]д = 3,1232131
Таблица 2. Умножение по алгоритму “Г”.
Четверичная с/с
ЗНАК
РЕГИСТР РЕЗУЛЬТАТА
ДЕЙСТВИЯ
0.
000000000000
0.
000000000000
+0
0.
000000000000
0.
021012030000
+Мн>>1
.
021012030000
3.
331232131000
-Мн>>2
10.
012310221000
0.
000210120300
+Мн>>3
10.
013121001300
0.
000021012030
+Мн>>4
0.
013202013330
0.
000002101203
+Мн>>5
0.
013210121133
Рез. В доп коде
0.
013210121133
Рез. В пр. коде
132101,21133
1937,5927734375
10 с/с
После окончания умножения необходимо оценить погрешность вычислений. Для этого полученное произведение (Мн*Мт4=013210121133 РМн*Мт = 6) приводится к нулевому порядку, а затем переводится в десятичную систему счисления:
Мн*Мт4 = 132101,21133 РМн*Мт = 0;
Мн*Мт10 = 1937,5927734375.
Результат прямого перемножения операндов дает следующее значение:
Мн10*Мт10 = 36,39 * 53,25 = 1937,7675.
Абсолютная погрешность:
D = 1937,7675 — 1937,5927734375 = 0,17473.
Относительная погрешность:
D 0,17473
/>/> ( = 0,00901%)
Мн*Мт 1937,7675
Эта погрешность является суммарной, накопленной за счет приближенного перевода из 10 с/с в четверичную обоих сомножителей, а также за счет округления полученного результата произведения.
В случае отрицательного множимого:
[Мт]дп = 0,1010101012/4
Мн = — 0,2101203
[Мн]д = 3,1232131
[-Мн]д = 0,2101203
Четверичная с/с
ЗНАК
РЕГИСТР РЕЗУЛЬТАТА
ДЕЙСТВИЯ
0.
000000000000
0.
000000000000
+0
0.
000000000000
3.
312321310000
+Мн>>1
3.
312321310000
0.
002101203000
-Мн>>2
3.
321023113000
3.
333123213100
+Мн>>3
10.
320212332100
3.
333312321310
+Мн>>4
10.
320131320010
3.
333331232131
+Мн>>5
10.
320123212201
Рез. В доп коде
1.
3 – 4=1
013210121133 продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
xx101
x110x
1x10x
10xx1
10x1x
xx101
x110x
x1101
1x10x
1x101
1110x
10xx1
10101
1x101
10101
10x1x
101x1
1y1yx
101xx
10x11
101xx
10101
1x10x
1010x
101x1
1011x
Множество С3 – пустое (склеивание не дало новых кубов более высокой размерности).
Множество простых имплекант Z: 0101x; 01x11; x1011; 011x1; 1x011; xx101; x110x; 1x10x; 10xx1; 10x1x; 101xx.
Отбросим те кубы из множества Z, которые покрываются другими.
Z#z 0101x 01x11 x1011 011x1 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx
0101x _ 01111 11011 011x1 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx
01x11 01010 _ 11011 01101 1x011 xx101 x110x 1x10x 10xx1 10x1x 101xx
x1011 01010 01111 _ 01101 10011 xx101 x110x 1x10x 10xx1 10x1x 101xx
011x1 01010 11011 _ 10011 1x101 1110x 1x10x 10xx1 10x1x 101xx
x0101 x1100
1x011 01010 01101 _ 1x101 1110x 1x10x 101x1 1011x 101xx
x0101 x1100 10x01 10x10
xx101 01010 10011 _ 11100 1x100 10111 1011x 1011x
x1100 10001 10x10 101x0
x110x 01010 10011 10101 _ 10100 10111 1011x 1011x
x0101 10001 10x10 101x0
1x10x 01010 10011 _ 10111 1011x 1011x
00101 01100 10001 10x10 10110
10xx1 01010 00101 01100 10100 _ 10110 10110
10x10
10x1x 01010 00101 01100 10100 _
10001
101xx 01010 00101 01100 10001 _
10010
01010 00101 01100 10001 10010
С помощью операции пересечения находим L-экстремали образованные на множестве N.
Z#(Z-z)ÇL 01010 00101 01100 10001 10010
11101 O O O O O
00101 O 00101 O O O
01010 01010 O O O O
01011 O O O O O
01100 O O 01100 O O
01101 O O O O O
01111 O O O O O
10001 O O O 10001 O
10010 O O O O 10010
10011 O O O O O
10100 O O O O O
10101 O O O O O
10110 O O O O O
10111 O O O O O
11011 O O O O O
11100 O O O O O
N={Æ}
Кубы на множестве L: 01010; 00101; 01100; 10001; 10010.
L-экстремали: 0101x; xx101; x110x; 10xx1; 10x1x.
Найдём кубы из L не покрытые L-экстремалями.
L#E11101 00101 01010 01011 01100 01101 01111 10001 10010 10011 10100 10101 10110 10111 11011 11100
0101x 11101 00101 01100 01101 01111 10001 10010 10011 10100 10101 10110 10111 11011 11100
xx101 01100 01111 10001 10010 10011 10100 10110 10111 11011 11100
x110x 01111 10001 10010 10011 10100 10110 10111 11011
10xx1 01111 10010 10100 10110 11011
10x1x 01111 10100 11011
01111 10100 11011
Из оставшегося Z (за исключением L-экстремалей) выберем кубы которые покроют остаток множества L. продолжение
--PAGE_BREAK--
(Z\E)Ç(L#E)01111 10100
01x11 01111 O
x1011 O O
011x1 01111 O
1x011 O O
1x10x O 10100
101xx O 10100
Тупиковые формы: 01x11, 011x1 & 1x10x, 101xx
Минимизированная переключательная функция для выхода переноса ОЧС Cmin:
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
C0*C0
00001
00011
00100
00110
01001
01011
01100
01110
10000
10010
10101
10111
11000
11010
11101
00001
00011
000x1
00100
00y0y
00yyy
00110
00yyy
00y1y
001x0
01001
0x001
0y0y1
0yy0y
0yyyy
01011
0y0y1
0x011
0yyyy
0yy1y
010x1
01100
0yy0y
0yyyy
0x100
0y1y0
01y0y
01yyy
01110
0yyyy
0yy1y
0y1y0
0x110
01yyy
01y1y
011x0
10000
y000y
y00yy
y0y00
y0yy0
yy00y
yy0yy
yyy00
yyyy0
продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
10101
1x111
y0y11
yxyy1
yxy11
y011y
yx1yy
yx11y
y1y11
y111y
10y1y
1xyyy
1xy1y
10111
1x1x1
110x0
yy0xy
y100y
y101y
yyyx0
y1y00
y1y10
y10xy
y1yx0
1x0x0
11000
11010
1yyxy
11y0y
11y1y
111x1
yyyx1
y1y01
y1y11
yy1xy
y110y
y111y
y1yx1
y11xy
1yyxy
11y0y
11y1y
1x1x1
11101
11111
11yxy
Множество C2: 0x0x1; 0x1x0; 1x0x0; 1x1x1.
C2*A2
0x0x1
0x1x0
1x0x0
0x0x1
0x1x0
0xyxy
1x0x0
yx0xy
yxyx0
1x1x1
yxyx1
yx1xy
1xyxy
Множество С3 – пустое.
Множество простых имплекант Z: 0x0x1; 0x1x0 1x0x0; 1x1x1.
Z#Z
0x0x1
0x1x0
1x0x0
1x1x1
0x0x1
-
0x1x0
1x0x0
1x1x1
0x1x0
0x0x1
-
1x0x0
1x1x1
1x0x0
0x0x1
0x1x0
-
1x1x1
1x1x1
0x0x1
0x1x0
1x0x0
-
-
0x0x1
0x1x0
1x0x0
1x1x1
С помощью операции пересечения находим L-экстремали образованные на множестве N.
Z#(Z-z)ÇL 0x0x1 0x1x0 1x0x0 1x1x1
00001 00001 O O O
00011 00011 O O O
00100 O 00100 O O
00110 O 00110 O O
01001 01001 O O O
01011 01011 O O O
01100 O 01100 O O
01110 O 01110 O O
10000 O O 10000 O
10010 O O 10010 O
10101 O O O 10101
10111 O O O 10111
11000 O O 11000 O
11010 O O 11010 O
11101 O O O 11101
11111 O O O 11111
Так как N={Æ} то всё Z образовано на множестве L. продолжение
--PAGE_BREAK--
Кубы на множестве L: 0x0x1; 0x1x0; 1x0x0; 1x1x1.
L-экстремали: 0x0x1; 0x1x0; 1x0x0; 1x1x1.
Проверим, не осталось ли кубов из L не покрытых L-экстремалями.
L#E 00001 00011 00100 00110 01001 01011 01100 01110 10000 10010 10101 10111 11000 11010 11101 11111
0x0x1 00100 00110 01100 01110 10000 10010 10101 10111 11000 11010 11101 11111
0x1x0 10000 10010 10101 10111 11000 11010 11101 11111
1x0x0 10101 10111 11101 11111
1x1x1
Все L-экстремали, и только они входят в Cmin: 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.
C0*C0
00001
00010
00110
00111
01000
01011
01100
01101
10010
10011
10100
10111
11000
11001
11101
00001
00010
000yy
00110
00yyy
00x10
00111
00yy1
00y1y
0011x
01000
0y00y
0y0y0
0yyy0
0yyyy
01011
0y0y1
0y01y
0yy1y
0yy11
010yy
01100
0yy0y
0yyy0
0y1y0
0y1yy
01x00
01yyy
01101
0yy01
0yyyy
0y1yy
0y1y1
01y0y
01yy1
0110x
10010
y00yy
x0010
y0y10
y0y1y
yy0y0
yy01y
yyyy0
yyyyy продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
00001 00010 00110 00111 01000 01011 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110
01011 00010 00110 00111 01000 01100 01101 10010 10011 10100 10111 11000 11001 11101 11110
10100 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101 11110
11110 00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101
00010 00110 00111 01000 01100 01101 10010 10011 10111 11000 11001 11101
--PAGE_BREAK--
X2
T1
T2
T3
Y0
Y1
Y2
Y3
D1
D2
D3
-
-
1
-
1
1
1
1
-
1
1
1
1
-
-
1
1
-
-
1
1
1
1
-
1
1
1
1
1
-
1
1
1
1
По полученной таблице построим автомат, в качестве памяти используя T-триггеры.