Цифровое устройство для логарифмирования двоичных чисел
(ii) 448459
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик (61) Зависимое от авт. свидетельства (22) Заявлено 02.03.72 (21) 1755374/18-24 с присоединением заявки № (32) Приоритет
Опубликовано 30.10.74. Бюллетень № 40
Дата опубликования описания 23.06.75 (51) М. Кл. G 06 1 7/38
Государственный комитет
Совета Министров СССР ло делам изобретений (53) УДК 681.325.5 (088.8) и открытии (72) Авторы изобретения (71) Заявитель
А. M. Оранский и Б. В. Немытов
Белорусский ордена Трудового Красного Знамени государственный университет им. В. И. Ленина
L (54) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ ЛОГАРИФМИРОВАНИЯ
ДВОИЧНЫХ ЧИСЕЛ
Изобретение относится к вычислительной технике, в частности к специализированным вычислительным устройствам, и предназначено для преобразования двоичных чисел по логарифмической зависимости. Это устройство может быть применено для нахождения логарифмов по основанию двух чисел, представленных двоичным кодом.
Известно, что на выполнение длинных операций умножения и деления в ЭЦВМ затрачивается значительно больше времени чем на выполнение операций суммирования. Для ускорения реализации длинных операций (умножения, деления, извлечения квадратных корней, возведения в степень) целесообразно использовать предварительное логарифмирование операндов, производство над ними более простых, коротких операций с последующим потенцированием результата. В этом случае такие операции как деление и умножение сводятся к алгебраическому суммированию преобразованных операндов.
Благодаря этому существенно повышается эффективность вычислительного процесса и обеспечивается уменьшение аппаратурных затрат при конструировании специализированных вычислителей, предназначенных для решения лекальных задач управления, контроля, регулирования, однако вычисление логарифмов обычным программным методом занимает значительное время. Табличный метод логарифмирования является наиболее быстродействующим, но требует запоминающего устройства больших объемов.
Известно устройство для преобразования двоичных кодов, предназначенное для логарифмирования и потенцирования двоичных кодов. Оно имеет простую конструкцию и надежность в работе, однако не обеспечивает
1р высокой точности вычислений.
Цель изобретения — повышение быстродействия и точности выполнения операции логарифмирования.
Это достигается тем, что в устройство, кро15 ме регистра, сдвигающего регистра и схемы управления, введены триггер, схемы «ИЛИ» и
«И» и запоминающий блок, причем выход сдвигающего регистра соединен с входом первого сумматора, выход которого связан с вхо20 дом сдвигающего регистра, другие выходы первого сумматора соединены с входом схемы
«ИЛИ», с входом схемы «И» и первым ходом управления; выход схемы «ИЛИ» связан с вторым входом схемы управления и другим входом схемы «И»; выход схемы «И» соединен с третьим входом схемы управления, выходы которого подключены соответственно к входам управления триггера, запоминающего блока, обоих сумматоров и регистров, а выход
ЗО запоминающего блока соединен с входом ре448459
I0
25 (2) При этом гистра, выход которого подключен к входу второго сумматора.
На чертеже показана блок-схема предлагаемого устройства.
Сумматор 1 соединен со сдвигающим регистром 2, выход которого подключен к входу сумматора; другими выходами сумматор связан с входом схемы «ИЛИ» 3, входом схемы
«И» 4 и входом схемы 5 управления, выход схемы «ИЛИ» 3 соединен с вторым входом схемы управления и другим входом схемы
«И» 4. Выход схемы «И» 4 подключен к третьему входу схемы управления. Выход запоминающего блока 6 связан с входом регистра 7, выход которого соединен с входом второго сумматора 8. Выход схемы управления подключен к входам сдвигающего регистра 2, регистра 7, запоминающего блока 6, триггера 9, сумматора 1 и сумматора 8.
В табл. 1 и 2 показаны состояния сумматоров и сдвигающего регистра для случаев определения логарифмов чисел х=7,844 и х=0,123 соответственно. Числа в устройстве представляются в форме с фиксированной запятой, обмен информацией между отдельными блоками осуществляется параллельным кодом.
Известно, что двоичное число х в нормализованной форме имеет вид х=х, 2и, где х — мантисса нормализованного числа (при этом 0,5 Логарифмирование дает log, õ = log, õ, + и. Отсюда видно, что логарифм числа х равен сумме логарифма мантиссы этого числа хо и значения показателя степени у двойки, численно равного количеству сдвигов числа х при его нормализации, т. е. при приведении его к виду (1). Можно выбрать такую последовательность значений логарифмов а, = log,(1+ 2 — ), а, = log,(1+ l, 2 ),..., а =1од,(1+.-" 2 — ), что для любого значения мантиссы хо находится такая последовательность ь р, (з, ...,, при j oo (при ;=(0,1}), что определяемая ими сумма стремится к значению log,õ, = — Q log,(1+ "-,"2 f). (3) f 1 log,(1+ (f 2 ) (; (1+ 2 f). f=i Применением признаков сходимости Даламбера или Коши к ряду Q log,(1+2 — f) подf--1 тверждает сходимость исходного ряда. Зо Алгоритм определения необходимой последовательности ь, ..., - находится потенцированием уравнения Х1 — -. xP 8 (1+ ) 2 1). (4) f=l Подбор, значений ; (/= 1, 2, 3,..., и) производится с помощью сумматора и сдвигающего регистра последовательным образованием произведений xp(1+2 — ); xp(1+2 — ); xp(1+2 — ) xp(1+2 ) ... (1+2 ") и анализом их значений с помощью логических элементов устройства. Устройство работает в два этапа: этап нормализации числа х и приведения его к виду (1) и этап определения значений х, по уравнению (4). При этом справедливо х; =- х« = хо П (1 + cf 2 ). /=1 в случае х«(1 в уравнении (4) сомножитель (1+2 — «) сохраняется, а из запоминающего блока в сумматор 4 заносится константа ૠ— — log (1+ 2 «). Если же xk)1, то обращения к запоминающему блоку для извлечения константы и, не происходит, а в уравнении (4) сомножитель (1+2 — ") заменяется н следующий очередной (1 +2-(«+1)) В исходном состоянии ячейки сумматоров и регистров находятся в нулевом положении. В cgMMBTop 1 заносится двоичное число х. Схема «ИЛИ» 3 анализирует состояние разрядов сумматора 1, отведенных для записи целой части числа и находящихся слева от двоичной .запятой. В зависимости от значения целой части числа х схема «ИЛИ» 3 воздейст-. вует на вход схемы управления, с выхода которой поступает соответствующий сигнал на вход триггера 9 и устанавливает его либо в минус (целая часть числа х=0), либо в плюс (целая часть числа х)0). Операция нормализации числа х осуществляется следующим образом. Необходимость нормализации и направление сдвига числа х в сумматоре 1 определяется схемами 3 и 4. Если целая часть числа хФО, то как минимум на один или несколько входов схемы «ИЛИ» 3, у которой количество входов соответствует количеству ячеек сумматора 1, отведенных для целой части числа х, поступает сигнал, соответствующий единичному состоянию одной или нескольких ячеек сумматора. Выходной сигнал схемы «ИЛИ» подается на вход схемы 5 управления, с ее выхода поступают импульсы, производящие сдвиг числа х в сумматоре 1 вправо до тех пор, пока старший значащий разряд числа х займет первую справа от запятой ячейку сумматора 1. Выход этого разряда сумматора соединен с входом схемы управления и при появлении единицы в этом разряде схема управления прекращает подачу импульсов сдвига, 448459 НапраалеНИ>7Ерг,7(! г Сумматор 111,110!10000000 =ю 000, r jl t f or t oooo = x g + оао, 11111l71f 0000 а па, о!11110 1оа а +ааг, î r» r поп 1000 +11f, l1DÎ000f0100 îot,àîfflоа 1100 4.11!, lгfooooofàlo оаг, аоагго roof 10 + 111, f f t r 0000010f аог, aooororojart f11 1rг!10V îпаll7 001, 00000000flol 11 f, 11 f 111110l701 000,111f г f111110 + 0 0 o, Îoo000000 r 11 0 + oor, aooaooa0or0j +111 11111!1!1101 001 паоооооопогп +1!1,11! t f t f f 10 Со держи мое C l7 i7" e P: H а 77 ра8леггие гггргг7а С у л !.7 а 777 а р ааа,ааolllrfÎitÎ = х о оп, 1111101!папа = Xg! 2 1 + 0ÎD, f f1I f01tl70OO оап,а!!! 1! D»аап >701>; 17 -.DCO 100!7 + 111 . !!ааааа. О!па аа, ОО1110011100 + 111, ! ОО аоа fÎfo | 3, Оог,Door!a!oar!a 4 !!, 11f rààaaàior V Dfy DODD!Dr oià!1 +1«,ff! 100аааfo DOt, ОО ОРОО гa I 10 f + 1. I,ll!!1100000i + 00D, г!1111101110 + 000, ОDDÎÎoajlfli 001,000000001!0I 111, г!г!11110001 + аоо,ttf!«i!, tta О ОО, OOÎÎÎl70l7oirr 1(г + 001,ааааОааОа!01 fft, if!i!It t «Of oof, DoDDDaD0DfIt0 г !1,1»11l fir f10 + ааг,оааоаопоааап + ill,11tl1f1ll11r aaD>1l if f f f11f t oot, апоапа !о !10! + 1i r 11! !1! о 00001 000, !f1! 11101110 + 000,00000001! 1 fr oot, аааппооппооп +1f1 rf111f111f1l г апп, 11111 fl t l!11 С а держи г"1ое C о О и е а нз кг и и р ezucmP апп,oaooaooooooo OOO,DDOODODOO0OO Оао,п»1!10 t D oo 111,110000010!0D 11 t, 111 а и пап f0 10 t l t, 111 f DD0OD f01 111, t f t l !ïàààîãã t11, f f l i11Îaol7l71 ааа, Оапапаа! f 11! 11f ttfff f ffDDOf апа,ooaoooaoofff f1f, f f j 11! f f !Of 111, t » I г 1111110 f1t 111!1111!111 (, ддигагагц и и регистр 000, Оаааааааааап Оаа, аооооаоооооо 000,0ri i> lll i f000 г l l > f I l700 OO ra l ao гt f, l 1000001010 1f l, гггаооао гп г ill, 1» ! Оаааага ! 71, 11! г 11000001 аоо, аапаапаг! 111 111, l f l! 111f 0001 000 ÎDÎDÎÎÎOD 1jj>1!i! iI riiraj 111, f1I 1 !11!1> 111,11f 1 f1! 11! 11 TаХлица ! С!7 дер жи ма е Сумматор г. оап,ппапппппоооп Orr, Оаааааааааап orr,оаппО0апоп0п + 0D0 D00000000000 агг,аапооааоппоа + 000,00оопоаапо00 + а!f,oooaоаооппао 4 о па, Опоаопппапаа а»,oooooooooooo + оаа,ааоаааапаопа О оапоппоааооо + oo0,0îïooîaî0oï0 а !1, аапааааааоаа + 1f f, !»110100010 =Кк ÎfD,1»110 гааа!о Оаа,пааоппаопоаа ага,f11 tlolooofo ll!, r t f r t l tOfOOf =l7Ig 010,1! ! О па!о!1 опа,ааоппаопоопо а!о,г! г гааа!о!1 поп, апаппаппапоо D10, f r1f1Îa01Îf1 Ког х = >97! (1>>) Та а 7ица 2 СУ t I (ZI77OÐ Ф 000 ОплаОООООООО 011, паааааааоппп Ог>,аапаппаааааа Dri ОООООООООООО 0 п, ООО.7ОООО ОООО 0 if > ОООООООООООО агг, ОООО ОООООООО „ 0ri,ааОООООООООО ООО,DDDDDIDI 1110 = >аО Оrr,ООООО10 «rro п11 Опаааго !!Iiî Пап,ОПаООПО!О!!! = Кг а», 000001! f0 jar огг,aaaoo f r io roi Dj1> O00OD11f 010f огl.оппапгггolor йУдХ =-ХРГЯ (IVt) 448459 Если целая часть числа х равна нулю, возможны два случая в зависимости от значения (1 или О) старшего разряда дробной части числа. Когда этот разряд равен единице, с выхода этой ячейки сигнал поступает на вход схемы управления как запрещающий для импульсов сдвига. Операция нормализации не производится, так как число х представлено в нормализованной форме, Во втором случае с этого разряда сумматора (находящегося в нулевом состоянии) сигнал запрета на вход схемы управления не поступает и с ее выхода на вход сумматора 1 подаются импульсы, производящие сдвиг числа х влево до появления единицы в ячейке сумматора, отведенной для старшего разряда дробной части числа х. При появлении единицы в этом разряде на вход схемы управления поступает сигнал запрета, соответствующий окончанию процесса нормализации числа. Количество сдвигов при нормализации числа х подсчитывается старшими разряда ми сумматора 8, находящимися слева от двоичной запятой. Разряды сумматора 8, находящиеся справа от запятой, предназначены для фиксирования значения мантиссы логарифма числа х. На этом заканчивается первый этап работы устройства. Второй этап работы устройства состоит из ряда последовательных шагов, каждый из которых обеспечивает постепенное наращивание членов произведения уравнения (4). Первый шаг: мантисса нормализованного числа х из сумматора 1 переписывается в сдвигающий регистр 2 с сохранением содержимого сумматора. Содержимое регистра 2 сдвигается вправо на один разряд и подсуммируется к содержимому сумматора 1. х, =- х, + хо 2 — = х, (1 + 2 — ), При х (1, что анализируется схемой «ИЛИ» 3, из запоминающего блока производится выборка первой константы а, =log (1+2 — ), значение которой заносится в регистр 7 и передается в сумматор 8 в прямом коде, если число х, логарифм которого определяется, меньше единицы, как в дополнительном коде при х) l. Преобразование в дополнительный код производится в регистре 7. Если результат су ммирования х ) 1, то выборки первой кони анты а не происходит. Направление второго шага определяется значением хь которое анализируется схемой «ИЛИ» 3. Если х«1, то содержимое сумматора 1, равное хо(1+2 — ), передается в регистр 2 и сдвигается вправо на два разряда. После этого содержимое регистра 2, равное хо. (1+2 — ) 2 —, передается на сумматор 1 для подсуммирования. В результате в сумматоре 1 оказывается число х, = x, (1 + 2 — ) (1 + 2 з ). Если содержимое сумматора 1 после первого шага х оказывается больше единицы, то в 65 уравнении (4) член (1+2 ) должен быть заменен следующим за ним членом (1+2 ) .. Для этого содержимое регистра 2 хо 2 — сдвигается вправо на один разряд и полученное значение х 2 — вычитается из содержимого сумматора 1 хо:хо(1+2 ) хо 2 =хо(1+2 ). Третий шаг по аналогии с вторым шагом начинается с анализа результата, полученного на втором шаге, Если хз(1, следует выборка из запоминающего блока очередной константы а —— log (1+ 2 — ) и передача ее в сумматор 8, а содержимое сумматора 1 вводится в регистр 2 и сдвигается на три разряда вправо с последующим подсуммированием с содержимым сумматора для получения следующего значения х; х, = хо (1 + 2 ) (1 + 2 — ) (1 + 2 — з или х, == х,(1+2 )(1+2 ) Если в результате второго шага получено хз)1, ранее хранившееся в регистре 2 число хо (1+2 — ) 2 — (при х (1) или хо2 — (при х) 1) сдвигается вправо еще .на один разряд и подсуммируется к содержимому сумматора 1 хз = хо (1 + 2- ) (I + 2 — ) — хо (1 + 2 ) Х Q 2 з = хо (! + 2 ) (1 + 2-з ) или Хо — Хо(1+2 ) Хо 2-з — Хо(1+2 — ) Последующие шаги происходят аналогично описанным и начинаются с анализа содержимого сумматора 1,:полученного при предыдущем шаге. После выполнения всех шагов вычисления в сумматоре 8 фиксируется значение (1о зх . Для обеспечения высокой точности вычислений количество шагов следует брать равным 1 (длине разрядной сетки регистров). При этом длина разрядной сетки сумматора 1 составляет величину I+f, где f — часть длины разрядной сетки для представления целой части числа х. В этом случае длина разрядной сетки сумматора 8 не должна быть меньше Ent(log>(f+I ) )+1 разрядов для характеристики логарифма и l разрядов мантиссы. В табл. 3 приведен ряд констант для устройства с 1=12. Погрешность з при вычислении логарифма состоит из погрешности при определении и погрешности р при суммировании P констант log (1+2 1) из-за неточности их представления, где P — количество шагов вычисления. Погрешность при определении ; состоит из погрешностей А> и Л . Погрешность Л, возникает из-за ограниченности разрядной сетки ,регистра 2, в результате чего при сдвиге содержимого регистра часть разрядов может выйти за его пределы, что при каждом шаге может внести погрешность, не превышающую единицы младшего разряда. Погрешность А> возникает от замены бесконечного произведения (4) конечным, ограниченным =Р. 448459 Значения констант Константы 0,100101011100 0,010100100111 0,001010101011 0,000101101000 0,000010110100 0,000001011110 0,000000110000 0,000000010111 0,000000001100 0,000000000101 0,000000000011 «,=1од,(1+2 ) а,=log,(1-+2 ) аз=1од,(1+2 ) а — log (1-1-2 4) я,=log,(1+2 ) ,=log,(1-1-2 ) а,=log,(1+2 ) аз=log (1+2 а) а — — 1ода (1+ 2 ) «„=log,(I 2 — гo) а — — !обад(1+2 и) Предмет изобретения tcp — (aP+n+1) Т, У = >gг" Составитель А. Оранский Техред 3. Таранеико Корректор Л. Орлова Редактор Т. Рыбалова Заказ 1103/10 Изд. М 1223 Тираж 624 Подписное ДНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж-35, Раушская наб., д. 4/5 Типография, пр. Сапунова, 2 Полную погрешность можно оценить выражением е (р. + Ь, + 4 = 1,5 (2 — Р+ P.2 — ). Среднее время вычисления логарифма составляет где Т вЂ” период тактовых импульсов; и — количество сдвигов при нормализации числа х. Так, например, для устройства с разрядной сеткой в 24 разряда (/= 10, 1= 14) абсолютная погрешность вычислений а(0,0013, а среднее время вычисления наибольшего числа х, которое можно записать в сумматор 1 с данной разрядной сеткой, составляет порядка сотни тактов. Для вычисления логарифма с погрешностью, не превосходящей а=0,0013, на универсальной ЦВМ с использованием библиотеки стандартных программ необходимо около 2500 так5 тов. Предлагаемое устройство имеет более высокое быстродействие по сравнению с известными. Цифровое устройство для логарифмирования двоичных чисел, содержащее регистр, сдвигающий регистр и схему управления, вы15 ход которой соединен с управляющим входом регистра и сдвигающего регистра, отл ичающ е е с я тем, что, с целью .повышения быстродействия и точности, оно содержит триггер, схему «И», схему «ИЛИ», два сумматора и 20 запоминающий блок причем выход сдвигающего регистра соединен с входом первого сумматора, выход этого сумматора соединен с входом сдвигающего регистра, другие выходы первого сумматоры соединены с входом схе25 мы «ИЛИ», с входом схемы «И» и первым входом схемы управления; выход схемы «ИЛИ» соединен с вторым выходом схемы управления и другим входом схемы «И»; выход схемы «И» соединен с третьим входом схе30 мы управления, выходы которой соединены соответственно с входами управления триггера, запоминающего блока, обоих сумматоров и регистров, а выход запоминающего блока соединен с входом регистра, выход которого под35 ключен к входу второго сумматора.
