Цифровое устройство для логарифмирования двоичных чисел Советский патент 1974 года по МПК G06F7/38 

1

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

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

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

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

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

Это достигается тем, что в устройство, кроме регистра, сдвигающего регистра и схемы управления, введены триггер, схемы «ИЛИ и «И и запоминающий блок, причем выход сдвигающего регистра соединен с входом первого сумматора, выход которого связан с входом сдвигающего регистра, другие выходы первого сумматора соединены с входом схемы «ИЛИ, с входом схемы «И и первым ходом управления; выход схемы «ИЛИ связан с вторым входом схемы управления и другим

входом схемы выход схемы «И соединен с третьим входом схемы управления, выходы которого подключены соответственно к входам управления триггера, запоминающего блока, обоих сумматоров и регистров, а выход

запоминающего блока соединен с входом регистра, выход которого подключен к входу второго сумматора.

На чертеже показана блок-схема предлагаемого устройства.

Сумматор 1 соединен со сдвигающим регистром 2, выход которого подключен к входу сумматора; другими выходами сумматор связан с входом схемы «ИЛИ 3, входом схемы «И 4 и входом схемы 5 управления, выход схемы «ИЛИ 3 соединен с вторым входом схемы управления и другим входом схемы «И 4. Выход схемы «И 4 подключен к третьему входу схемы управления. Выход запоминающего блока 6 связан с входом регистра 7, выход которого соединен с входом второго сумматора 8. Выход схемы управления подключен к входам сдвигающего регистра 2, регистра 7, запоминающего блока 6, триггера 9, сумматора 1 и сумматора 8.

В табл. 1 и 2 показаны состояния сумматоров и сдвигающего регистра для случаев определения логарифмов чисел А: 7,844 и ,123 соответственно. Числа в устройстве представляются в форме с фиксированной запятой, обмен информацией между отдельными блоками осуществляется параллельным кодом.

Известно, что двоичное число х в нармализованной форме имеет вид

,-2/г,(1)

где X-мантисса нормализованного числа (при этом 0,). Логарифмирование дает

og.,x - Qg.,.(2)

Отсюда видно, что логарифм числа х равен сумме логарифма мантиссы этого числа х и значения показателя степени у двойки, численно равного количеству сдвигов числа х при его нормализации, т. е. при приведении его к виду (1).

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

«. Iog,(l + 2-), а, log,(l 4- ,-2-2 ),. ..,

« log,(,

что для любого значения мантиссы Хо находится такая последовательность |ь |2, |з. |г при (при ,l}), что определяемая ими сумма стремится к значению

(3)

Iog -21og.(l + r2-)

При этом

оооэ

2 log. (1 + у 2-/) 2 (1 + 2-0У 1/ 1

Применением признаков сходимости Далам00

бера или Кощи к ряду 2 1о&2(1 ) под/ 1тверждает сходимость исходного ряда.

Алгоритм определения необходимой последовательности li, 2, , Е; находится потенцированием уравнения

.x, П(.

(4)

Подбор .значений |j (/ 1, 2, 3,.. .,/г) производится с .помощью сумматора и сдвигающего

Ю регистра последовательным образованием произведений л;о(); Xo(l+2-i); Xo(l-f2-2); А:О( 1+2-1) () и анализом их значений с помощью логических элементов устройства.

15 Устройство работает в два этапа: этап нормализации числа X и приведения его к виду (1) и этап определения значений Xj по уравнению (4). При этом справедливо

оо

20Xj Xk x,(c.2-i).

в случае Xh. в уравнении (4) сомножитель (1+2-) сохраняется, а из запоминающего блока в сумматор 4 заносится констаНта

а, 10g,(l + 2-).

Если же xk, то обращения к запоминающему блоку для извлечения константы « не происходит, а в уравнении (4) сомножитель

() заменяется н следующий очередной (1 +2-(+1)).

В исходном состоянии ячейки сумматоров и регистров находятся в нулевом положении. В СумматСТр 1 заносится двоичное число х.

5 Схема «ИЛИ 3 анализирует состояние разрядов сумматора 1, отведенных для записи целой части числа и находящихся слева от двоичной запятой. В зависимости от значения целой части числа х схема «ИЛИ 3 воздейст-,

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

5 Операция нормализации числа х осуществляется следующим образом.

Необходимость нормализации и направление сдвига числа х в сумматоре 1 определяется схемами 3 и 4. Если целая часть числа

0 л: , то как минимум на один или несколько входов схемы «ИЛИ 3, у которой количество входов соответствует количеству ячеек сумматора 1, отведенных для целой части числа х, поступает сигнал, соответствующий единичному состоянию одной или нескольких ячеек сумматора. Выходной сигнал схемы «ИЛИ подается на вход схемы 5 управления, с ее выхода поступают импульсы, производящие сдвиг числа х в сумматоре 1 вправо до тех

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

Та5лии,а 1

ТаЗли.и,а Z

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

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

Количество сдвигов при нормализации числа X подсчитывается старщими разрядами сумматора 8, находящимися слева от двоичной запятой. Разряды сумматора 8, находящиеся справа от запятой, предназиачены для фиксирования значения мантиссы логарифма числа X. На этом заканчивается первый этап работы устройства.

Второй этап работы устройства состоит из ряда последовательных щагов, каждый из которых обеспечивает постепенное наращивание членов произведения уравнения (4). Первый щаг: мантисса нормализованного числа х из сумматора 1 переписывается в сдвигающий регистр 2 с сохранением содержимого сумматора. Содержимое регистра 2 сдвигается вправо на один разряд и подсуммируется к содержимому сумматора 1.

л:, г 0-f дго. 2-1 - „ (1 + 2-1).

11рил:1 1, что анализируется схемой «ИЛИ 3, из запоминающего -блока производится выборка первой константы ai Iog2(l+2), значение которой заносится в регистр 7 и передается в сумматор 8 в прямом коде, если число X, логарифм которого определяется, меньще единицы, как в дополнительном коде при . Преобразование в дополнительный код П| оизводится в регистре 7. Если результат суммирования , то выборки первой конгтанты «1 не происходит.

Направление второго шага определяется значением Xi, которое анализируется схемой «ИЛИ 3. Если , то содержимое сумматора 1, равное л;о(1-4-2-1), передается в регистр 2 и сдвигается вправо на два разряда. После этого содержимое регистра 2, равное дго-(1+2-1)-2-2, передается на сумматор 1 для подсуммирования. В результате в сумматоре 1 оказывается число

д:, д:„ (1+2-М (1+2-2).

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

уравнении (4) член (l+2-i) должен быть заменен следующим за ним членом (1+2-). Для этого содержимое регистра 2 Хо-2- сдвигается вправо на один разряд и полученное значение вычитается из содержимого сумматора I

х,х„(1+2-)-х,,а + 2-).

Третий шаг по аналогии с вторым шагом начинается с анализа результата, полученного на втором шаге. Если , следует выборка из запоминающего блока очередной «онстанты a2 log2(l+2) и передача ее в сумматор 8, а содержимое сумматора 1 вводится в регистр 2 и сдвигается на три разряда вправо с последующим подсуммированием с содержимым сумматора для получения следующего значения Xj

а+2-(1+2-2) (1+2-3 или д:з--- о (1+2-2) (1 + 2-3).

Если в результате второго шага получено

, ранее хранившееся в регистре 2 число

л;о( 1+2-1)2-2 (при.1:,1) или Xo2-2 (при .:)

сдвигается вправо еще на один разряд и иодсуммируется к содержимому сумматора 1

X, х,(+ 2-1)(1 + 2-2) X,(1 + 2-) X X 2-3 „ (1 + 2-(1 + 2-3 ) или

X, „ (1 + 2-2) - .to -2-3 „ (1 + 2-3).

Последующие шаги происходят аналогично описанным и начинаются с анализа содержимого сумматора 1, полученного при предыдущем шаге.

После выполнения всех шагов вычисления в сумматоре 8 фиксируется значение |log2.5c|. Для обеспечения высокой точности вычислеНИИ количество шагов следует брать равным / (длине разрядной сетки регистров). При этом длина разрядной сетки сумматора 1 составляет величину /+f, где f - часть длины разрядной сетки для представления целой части числа X. В этом случае длина разрядной сетки сумматора 8 не должна быть меньше (/+)+ разрядов для характеристики логарифма и / разрядов мантиссы. В табл. 3 приведен ряд констант для устройства с .

Погрешность е при вычислении логарифма состоит из погрешности при определении | и погрешности |д, при суммировании Р констант () из-за неточности их представления, где Р - количество шагов вычисления.

Погрешность при апределении |,- состоит из -погрешностей AI и AS. Погрешность AI возникает из-за ограниченности разрядной сетки регистра 2, в результате чего при сдвиге содержимого регистра часть разрядов может выйти за его пределы, что при каждом шаге может внести погрешность, не превышающую единицы младшего разряда. Погрешность Да возникает от замены бесконечного произведения (4) конечным, ограниченным Р.

Полную погрешность можно оценить выражением

1- + А, + Д,1,5(2- + Я-2-0. Среднее время вычисления логарифма составляет

t,f (P + n + l)-T,

где Т - период тактовых импульсов;

п - количество сдвигов при нормализации числа X.

Так, например, для устройства с разрядной сеткой в 24 разряда (, ) абсолютная погрешность вычислений ,0013, а среднее время вычисления наибольшего числа X, которое можно записать в сумматор 1 с данной разрядной сеткой, составляет порядка сотни тактов.

Для вычисления логарифма с погрешностью, не превосходяш,ей ,0013, на универсальной ЦВМ с использованием библиотеки стандартных программ необходимо около 2500 тактов. Предлагаемое устройство имеет более высокое быстродействие по сравнению с известными.

Предмет изобретения

10

Цифровое устройство для логарифмирования двоичных чисел, содержашее регистр, сдвигаюш,ий регистр и схему управления, выход которой соединен С управляюш.им входом регистра и сдвигающего регистра, отличающееся тем, что, с целью повышения быстродействия и точности, оно содержит триггер, схему «И, схему «ИЛИ, два сумматора и

запоминающий блок причем выход сдвигающего регистра соединен с входом первого сумматора, выход этого сумматора соединен с входом сдвигающего регистра, другие выходы первого сумматоры соединены с входом схемы «ИЛИ, с входом схемы «И и первым входом схемы управления; выход схемы «ИЛИ соединен с вторым выходом схемы управления и другим входом схемы выход схемы «И соединен с третьим входом схемы управления, выходы которой соединены соответственно с входами управления триггера, запоминающего блока, обоих сумматоров и регистров, а выход запоминающего блока соединен с входом регистра, выход которого подключен к входу второго сумматора.