Множительное устройство

Введение

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

1. Разработка алгоритма умножения В разработке алгоритма умножения можно выделить следующие составные элементы:

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

Мн10 Мн4 Мн24

45,3010 231,1034 11 00 01, 01 10 00 2/4

Мт10 Мт4 Мт24

55,1410 313,0204 00 10 01, 01 01 00 2/4

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

Мн = 1, 11 00 01 01 10 00 0, 10 00

Мт = 0, 00 01 00 10 11 10 0, 10 00 .

3) Перемножение двух чисел с плавающей запятой сводится к сложению порядков, формированию знака произведения и перемножению мантисс сомножителей.

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

ПМн = 0, 10 00

+ПМт = 0, 10 00

ППр = 0, 01 11

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

ЗнМн ЗнМт = 1 0 = 1

Перемножение мантисс приведено в Таблице 1.1:

Таблица 1.1

Таблица 1.1(окончание)

Произведение до округления Mн*Mт = 1,11 01 00 10 10 10 00

Для округления добавим к седьмому разряду 11.

Произведение после округления: Мн*Мт = 1,11 01 00 10 10 01 01

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

(Mн Mт)10 = - (2 45 + 1 44 + 3 43 + 1 40 + 1 40) = - 2497,25 10

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

Mн10 Mт10 = 55,14 (-45,30)= - 2497,84 210

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

= - 2497,842 — (- 2497,25) = - 0,592

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

= / (Мн Мт) =0,592 / 2497,842 = 0,24 (= 0,024%)

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

2. Разработка структурной схемы При разработке устройства умножения использование непосредственно четверичной системы затруднительно. Поэтому четверичные цифры кодируються двоичными эквивалентами (диадами) так, что перемножение одной четверичной цифры на другую заменяется перемножением их двоичных эквивалентов. В связи с этим для получения четверичного разряда произведения строится отдельная схема — одноразрядный четверичный умножитель (ОЧУ)(Рис 2.1.), на входы которого поступают диады Мн и Мт.

Для суммирования необходим одноразрядный четверичный сумматор (ОЧС), на входы которого поступают диады четверичных цифр с учетом их сдвига влево. На выходе ОЧС (Рис 2.2.) формируются четверичные цифры произведения, представленные двоичными эквивалентами. Младший разряд произведения как и старший формируется без суммирования, однако в старший разряд поступает единица переноса из младшего разряда. С учетом этого структура ОЧС старшего разряда может быть несколько проще ОЧС других разрядов.

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

Знак произведения формируется сложением по модулю 2 знаков Мн и Мт. Порядок произведения вычисляется сложением дополнительных кодов порядков сомножителей.

Рис 2.1. Схема ОЧУ Рис 2.2. Схема ОЧС множительный устройство система счисление Временные затраты на умножение шестиразрядных сомножителей определяются в основном затратами на образование частичных произведений, получаемых на выходах ОЧС, и примерно равны Ту = 6 (сдв + очу + 6очс), (2.1)

где

очс — время формирования единицы переноса в ОЧС;

очу — время умножения на одном ОЧС;

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

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

Для хранения в памяти машины отсылается, как правило, лишь n разрядов произведения. При отбрасывании n младших разрядов произведения производиться округление путем добавления половины основания системы в (n+1) разряд. Если в этом разряде цифра равна или больше половины основания системы счисления, то возникает единица переноса в n разряд. При таком способе округления максимальная абсолютная ошибка округления определяется как

max = 24−74Pmax = 217, (2.2)

а наибольшая относительная ошибка равна

max = 24−74Pmax/4−14Pmax = 2−11 0.0005 = 0.05, (2.3)

где Pmax — наибольший порядок произведения, равный 1510.

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

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

Рис 3.1.1 Схема ОЧУ Составим таблицу истинности из 16-ти двоичных наборов (Таблица 3.1.1).

Таблица 3.1.1

Таблица истинности для ОЧУ

Расчет производится расчетно-табличным методом.

На первом шаге осуществляется запись функции в аналитеческом виде. Второй шаг — полученная на шаге 1 форма является совершенной дьзъюнктивной (конъюнктивной) нормальной формой (СДНФ (СКНФ)). Шаг три — производится склейка и/или поглощение. Если элементы функции являются изолированными, т. е. не подлежат склейке и поглощению, то СДНФ (СКНФ) будет являться сокращенной дьзъюнктивной (конъюнктивной) нормальной формой (сДНФ (сКНФ)). На четвертом шаге строится таблица с количеством строк равным количеству импликант (имплицент) в сДНФ (сКНФ) +1 и количеством столбцов равным количеству конституент единицы (нуля) в СДНФ (СКНФ) функции +1. В названиях строк, начиная со второй, записываются импликанты (имплиценты) тупиковой формы. В названиях столбцов, начиная со второго, записываются конституенты СДНФ (СКНФ) функции. Условными знаками помечаются оставшиеся свободные клетки таблицы, если соответствующая строке импликанта (имплицента) является собственной частью конституенты из соответствующего столбца.

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

Запишем СДНФ для P1.

(3.1.1)

сДНФ будет иметь вид:

(3.1.2)

Таблица 3.1.2

Определение тупиковой формы

Следовательно тупиковая форма имеет вид:

(3.1.3)

(3.1.4)

Очевидно что тупиковая форма в данном случае будет иметь тот же вид, что и сДНФ, т. е.:

(3.1.5)

Расчет для выхода P3.

(3.1.6)

(3.1.7)

Таблица 3.1.3

Расчет тупиковой формы

Т.к. все необходимые столбцы и строки оказались вычеркнутыми, то тупиковая форма сохранит вид сДНФ:

(3.1.8)

Расчет выхода P4.

(3.1.9)

(3.1.10)

Таблица 3.1.4

Расчет тупиковой формы

Все необходимые столбцы и строки оказались вычеркнутыми, соответственно тупиковая форма:

(3.1.11)

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

(3.1.12)

(3.1.13)

(3.1.14)

(3.1.15)

Четыре получившиеся тупиковые формы могут быть легко реализованы при помощи заданного логического базиса: дизъюнктор, сумматор по модулю 2, генератор единицы.

Для упрощения реализации проведем некоторые преобразования:

(3.1.16)

(3.1.17)

(3.1.18)

(3.1.19)

Преобразованные таким образом выражения можно реализовать в заданном логическом базисе с минимальными временными затратами.

3.2 Логический синтез одноразрядного четверичного сумматора Одноразрядный четверичный сумматор (ОЧС) производит суммирование поступающих из ОЧУ двух диад и одной диады переноса. При этом на выходах появляются диада переноса из младшего разряда и диада результата, записываемая непосредственно в аккумулятор. В работе ОЧС проявляется особенность, состаящая в том, что в четверичный разряд X1X2 не может поступать значение равное 34. Это объясняется тем, что при перемножении максимально возможных значений (3434) в результате получается значение 214, т. е. значение 34 в разряд X1X2 никогда не поступит. Второй особенностью ОЧС является то, что четверичный разряд входного переноса X5X6 не может принимать значения равные 24 и 34. Это объясняется тем, что в первом ОЧС отсутствует входной перенос. Следовательно максимально возможное значение будет равно 124, а на выходном переносе соответственно 14. В последующих ОЧС добавление 14 входного переноса все равно будет давать на выходном переносе значение не превышающее 14. Таким образом в выходной перенос могут попадать или 04 или 14.

Т.к. в блоке ОЧС три входа, состоящих из двух двоичных цифр каждый, то фактически на входы поступают 6 двоичных значений. Следовательно таблица истинности будет состоять из 64 двоичных наборов, причем на 40 из них выходные значения будут неопределены, что в дальнейшем скажется на реализации ОЧС в указанном логическом базисе. Неопределенные значения будут использованы для максимально возможной минимизации функций, а значения функций будут заменяться на 0 или 1 в зависимости от возникшей ситуации.

Рис 3.2.1 Схема ОЧС Таблица истинности для ОЧС, содержащая 64 набора (Таблица 3.2.1).

Таблица 3.2.1

Таблица истинности для ОЧС

— набор неопределен.

Метод минимизации — диаграммы Вейча. Диаграмма Вейча может быть построена непосредственно по таблице истинности. Т.к. в данном случае таблица состоит из наборов из шести аргументов, то количество столбцов и строк будет равно 23 = 8. При использовании обычных двоичных чисел в нумерации строк и столбцов соответствующие им наборы логических аргументов в смежных клетках не являются соседними, поэтому для нумерации строк и столбцов используем код Грея, особенностью которого является разница между кодами соседних чисел только в одном двоичном разряде. Для обозначения столбцов используются младшие 23 аргументы, а для обозначения строк оставшиеся логические аргументы. Минимизация заключается в выделении смежных 2i клеток содержащих 0 или 1 в виде прямоугольника. Результат будет иметь ранг на i меньший чем ранг первоначальной функции и в него войдут те логические элементы которые не изменяют свое значение во всех наборах выделенных клеток многоугольника. Наилучшие результаты минимизации получаются при наибольших возможных значениях i, при этом одна и таже клетка должна входить в различные выделенные прямоугольники минимальное количество раз.

Минимизируем функцию P1 по конституентам единицы. будем обозначать наборы на которых значение функции не определено (Таблица 3.2.2).

Таблица 3.2.2

Диаграмма Вейча

По диаграмме Вейча легко определить, что тупиковая форма будет иметь вид:

(3.2.1)

Минимизируем функцию P2 по конституентам единицы (Таблица 3.2.3).

Таблица 3.2.3

Диаграмма Вейча

Очевидно, что тупиковой формой будет являться 1, т. е.

(3.2.2)

Минимизируем функцию P3 по конституентам единицы (Таблица 3.2.4).

Таблица 3.2.4

Диаграмма Вейча

Тупиковая форма будет иметь вид:

(3.2.3)

Минимизируем функцию P4 по конституентам единицы (Таблица 3.2.5).

Таблица 3.2.5

Диаграмма Вейча

Тупиковая форма будет иметь вид:

(3.2.4)

Логический базис в котором эти функции должны быть реализованы содержит коньюнктор и инвертор.

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

(3.2.5)

(3.2.6)

(3.2.7)

(3.2.8)

Реализация ОЧУ и ОЧС показана на функциональной схеме схеме.

Заключение

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