Цифровое устройство для логарифмирования двоичных чисел

п 11 44849 ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических(22) Заявлено 02,03.72 (21) 1755374/18-2 061 7/38 51) М. прис инением заявкиГосударственныи комитет Совета Министров СССР(088,8) оам изобретениии открытий ликования описания 23.06.75 2) Авторы изобретен 1) ЗаявительА. %. Оранский и Б. В. Немытовена Трудового Красного Знамени государственныйуниверситет им. В. И, Ленина Белорусский о Е 1 Г ффЙт К ФМИ РОВАН ИЯ 4) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ ЛО ДВОИЧНЫХ ЧИСЕЛИзобретение относится к вычислительной технике, в частности к специализированным вычислительным устройствам, и предназначено для преобразования двоичных чисел по логарифмической зависимости, Это устройство может быть применено для нахождения логарифмов по основанию двух чисел, представленных двоичным кодом.Известно, что на выполнение длинных операций умножения и деления в ЭЦВМ затрачивается значительно больше времени чем на выполнение операций суммирования, Для ускорения реализации длинных операций (умножения, деления, извлечения квадратных корней, возведения в степень) целесообразно использовать предварительное логарифмирование операндов, производство над ними более простых, коротких операций с последующим потенцированием результата, В этом случае такие операции как деление и умножение сводятся к алгебраическому суммированию преобразованных операндов.Благодаря этому существенно повышается эффективность вычислительного процесса и обеспечивается уменьшение аппаратурных затрат при конструировании специализированных вычислителей, предназначенных для решения лекальных задач управления, контроля, регулирования, однако вычисление логарифмов обычным программным методом занимает значительное время. Табличный метод логарифмирования является наиболее быстродействующим, но требует запоминающего устройства больших объемов.Известно устройство для преобразованиядвоичных кодов, предназначенное для логарифмирования и потенцирования двоичных кодов. Оно имеет простую конструкцию и надежность в работе, однако не обеспечивает 10 высокой точности вычислений.Цель изобретения - повышение быстродействия и точности выполнения операции логарифмирования,Это достигается тем, что в устройство, кро ме регистра, сдвигающего регистра и схемыуправления, введены триггер, схемы ИЛИ и И и запоминающий блок, причем выход сдвигающего регистра соединен с входом первого сумматора, выход которого связан с вхо дом сдвигающего регистра, другие выходыпервого сумматора соединены с входом схемы ИЛИ, с входом схемы И и первым ходом управления; выход схемы ИЛИ связан с вторым входом схемы управления и другим 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(хо(1).Логарифмирование дает1 од,х =1 од,х, +и. Отсюда видно, что логарифм числа х равенсумме логарифма мантиссы этого числа хо изначения показателя степени у двойки, численно равного количеству сдвигов числа х приего нормализации, т. е. при приведении егок виду (1).Можно выбрать такую последовательностьзначений логарифмова,:1 од,(1+2 - 1), а = 1 од (1+ 1, 2 ).,а = 1 од, (1 + "; 2 1),что для любого значения мантиссы хо находится такая последовательность ь 2, з,Ь при 1 ос (при = (О,Ц), что определяемая ими сумма стремится к значению 1 од,х, = -1 од,(1+ "-.,"2 - 1), (3) /=1, 1 од,(1+ 1 "2-) ((1+ 2 - 1),Применением признаков сходимости Даламбера или Коши к ряду1 од,(1+2 - 1) под=1тверждает сходимость исходного ряда,Зо 35 40 45 50 55 60 65 Алгоритм определения необходимой последовательности ь 2, ,находится потенцированием уравнения х - .хо Й(1+у 2 ) (4) =1 Подбор, значений ; (1= 1, 2, 3 п) производится с помощью сумматора и сдвигающего регистра последовательным образованием произведений хо(1+2 - ); х,(1+2 - ); х,(1+2 - ) х,(1+2 - )(1+2 - ") и анализом их значений с помощью логических элементов устройства.Устройство работает в два этапа: этап нормализации числа х и приведения его к виду (1) и этап определения значений х, по уравнению (4). При этом справедливо х; =- х = хо П (1 + с 1 2 - ).(1+2 - ) сохраняется, а из запоминающего блока в сумматор 4 заносится константа а, = 1 од,(1+ 2 - ф).Если же хй)1, то обращения к запоминающему блоку для извлечения константы а, не происходит, а в уравнении (4) сомножитель (1+2 - ") заменяется н следующий очередной (+2-(1+1В исходном состоянии ячейки сумматоров и регистров находятся в нулевом положении. В сумматор 1 заносится двоичное число х. Схема ИЛИ 3 анализирует состояние разрядов сумматора 1, отведенных для записи целой части числа и находящихся слева от двоичной запятой. В зависимости от значения целой части числа х схема ИЛИ 3 воздействует на вход схемы управления, с выхода которой поступает соответствующий сигнал на вход триггера 9 и устанавливает его либо в минус (целая часть числа х=О), либо в плюс (целая часть числа х)0).Операция нормализации числа х осуществляется следующим образом.Необходимость нормализации и направление сдвига числа х в сумматоре 1 определяется схемами 3 и 4. Если целая часть числа хФО, то как минимум на один или несколько входов схемы ИЛИ 3, у которой количество входов соответствует количеству ячеек сумматора 1, отведенных для целой части числа х, поступает сигнал, соответствующий единичному состоянию одной или нескольких ячеек сумматора. Выходной сигнал схемы ИЛИ подается на вход схемы 5 управления, с ее выхода поступают импульсы, производящие сдвиг числа х в сумматоре 1 вправо до тех пор, пока старший значащий разряд числа х займет первую справа от запятой ячейку сумматора 1. Выход этого разряда сумматора соединен с входом схемы управления и при появлении единицы в этом разряде схема управления прекращает подачу импульсов сдвига,+аат,п 11 таас тсюц +11 1, 11 аююоо та то о опт,аоттгоаг 1 тос-,1е и Со держи мое Годер Науграсууе- СдЮигаувиийугиеуггрйа рюгисуутр С У 1 Ут а Утг ц Р оао,юаат 11 ттюгга : д;оаа, т 1111 О т увюпа = х+ тт у, 1 тт тпююю вОт ттт, 1Оаааютс+ ают, ОООО татас 1 + ту, тууаапюато Овт юю цоп в та У 01+ 111, тттт ттт г т ттт 1 а 12 ООО ттгтттттттгт Сумматор Оат,споаюа 1 сттотпас,саююааюаоюао аоа,сааюповооопо ООО,О 1111 пт 1000 тгт,;спасоОтав 111, ттт Оюоаа тцтп тг , 1 угюоааатот ттг, тттгтааоюцгг 11, тгтгттююсюат ааа,ююовюаатт ттт 11 11 тттт 1 тююпг Оса,воааоссоаттт ттт,ттгтттгттта 1 ттт,тутУто гтг, тттгтттттттт аао, Ооппюсаоопап пап, Оаппооасцооооао, а тт тат таюв т т т,та овцс та 1 ца 1 т, т г тпвоаотаус гтт,ттттааааотог тут, тттгггвовоцт впп,ппвоввс 111 1 1, 1 тт т 1 т 1 тсювт аао,псоаассвсттт ту,тт г т т 1 1 1 11 ют ттт, 111111111110 111,11 ттттттттт 1 аХлица 1 Содержимое Сумматор Ф сап,павппсаооаоп атт, апацоцццавоо атт,пвповювоооцо448459 Если целая часть числа х равна нулю, возможны два случая в зависимости от значения (1 или 0) старшего разряда дробной части числа. Когда этот разряд равен единице, с выхода этой ячейки сигнал поступает на вход схемы управления как запрещающий для импульсов сдвига. Операция нормализации не производится, так как число х представлено в нормализованной форме,Во втором случае с этого разряда сумматора (находящегося в нулевом состоянии) сигнал запрета на вход схемы управления не поступает и с ее выхода на вход сумматора 1 подаются импульсы, производящие сдвиг числа х влево до появления единицы в ячейке сумматора, отведенной для старшего разряда дробной части числа х. При появлении единицы в этом разряде на вход схемы управления поступает сигнал запрета, соответствующий окончанию процесса нормализации числа.Количество сдвигов при нормализации числа х подсчитывается старшими разряда ми сумматора 8, находящимися слева от двоичной запятой. Разряды сумматора 8, находящиеся справа от запятой, предназначены для фиксирования значения мантиссы логарифма числа х. На этом заканчивается первый этап работы устройства.Второй этап работы устройства состоит из ряда последовательных шагов, каждый из которых обеспечивает постепенное наращивание членов произведения уравнения (4), Первый шаг: мантисса нормализованного числа х из сумматора 1 переписывается в сдвигающий регистр 2 с сохранением содержимого сумматора. Содержимое регистра 2 сдвигается вправо на один разряд и подсуммируется к содержимому сумматора 1.х, =х,+х, 2 -=х,(1+2 - ),При х(1, что анализируется схемой ИЛИ 3, из запоминающего блока производится выборка первой константы сс=1 одг(+2 - ), значение которой заносится в регистр 7 и передается в сумматор 8 в прямом коде, если число х, логарифм которого определяется, меньше единицы, как в дополнительном коде при х)1. Преобразование в дополнительный код производится в регистре 7. Если результат суммирования х 1)1, то выборки первой конс 1 анты а не происходит. Направление второго шага определяется значением хь которое анализируется схемой ИЛИ 3. Если х 1(1, то содержимое сумматора 1, равное хо(+2 - ), передается в регистр 2 и сдвигается вправо на два разряда. После этого содержимое регистра 2, равное х, (1+2 - ) 2 - , передается на сумматор 1 для подсуммирования, В результате в сумматоре 1 оказывается числох, - х,(1-1-2 -)(1+2-г),Если содержимое сумматора 1 после первого шага х оказывается больше единицы, то в 8уравнении (4) член (1+2 - ) должен быть заменен следующим за ним членом (1+2 - ). Для этого содержимое регистра 2 хо 2 -сдвигается вправо на один разряд и полученное значение х 2 -вычитается из содержимого сумматора 1х,= хо(1+2 ) хо 2 - г =хо(1+2 - г) Третий шаг по аналогии с вторым шагомначинается с анализа результата, полученного на втором шаге, Если хг(1, следует выборка из запоминающего блока очередной константы аг=1 одг(1+2 - ) и передача ее в сумматор 8, а содержимое сумматора 1 вводится в регистр 2 и сдвигается на три разряда вправо с последующим подсуммированием с содержимым сумматора для получения следующего значения х;20 хз = - хо(1+2-)(1+2-г)(1+2- илихз =-хо(1+2 )(1+2-)Если в результате второго шага полученохг)1, ранее хранившееся в регистре 2 число хо(1+2 - ) 2 -(при х(1) или хо 2 -(при х)1) сдвигается вправо еще .на один разряд и подсуммируется к содержимому сумматора 1х, = х, (1 + 2- ) (1 + 2 -) - х, (1 + 2 -) ХХ 2 - з = х, (1 + 2) (1 + 2-з ) илихэ: - хо (1 + 2 г ) хо 2 : хо (1 + 2 -) Последующие шаги происходят аналогичноописанным и начинаются с анализа содержи мого сумматора 1, полученного при предыдущем шаге.После выполнения всех шагов вычисленияв сумматоре 8 фиксируется значение 1 одгх.Для обеспечения высокой точности вычисле ний количество шагов следует брать равным 1(длине разрядной сетки регистров). При этом длина разрядной сетки сумматора 1 составляет величину 1+, где- часть длины разрядной сетки для представления целой части чис ла х. В этом случае длина разрядной сеткисумматора 8 не должна быть меньше Еп 11 одг(1+1)1+1 разрядов для характеристики логарифма и 1 разрядов мантиссы.В табл. 3 приведен ряд констант для устрой.50 ства с 1=12.Погрешность я при вычислении логарифмасостоит из погрешности при определениии погрешности р при суммировании Р констант очаг(1+2 - 1) из-за неточности их представле ния, где Р - количество шагов вычисления.Погрешность при определении ; состоитиз погрешностей Л 1 и Лг, Погрешность Л, возникает из-за ограниченности разрядной сетки ,регистра 2, в результате чего при сдвиге со держимого регистра часть разрядов можетвыйти за его пределы, что при каждом шаге может внести погрешность, не превышающую единицы младшего разряда, Погрешность Лг возникает от замены бесконечного произведе ния (4) конечным, ограниченным =Р,448459 10 Значения констант Константы 0,100101011100 0,010100100111 0,001010101011 0,000101101000 0,000010110100 0,000001011110 0,000000110000 0,000000010111 0,000000001100 0,000000000101 0,000000000011Корректор Л. Орлова Редактор Т. Рыбалова Заказ 1103/10 Изд, М 1223 Тираж 624 Подписное ДНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж.35, Раушская наб., д. 4/5Типография, пр, Сапунова, 2 Полную погрешность можно оценить выра- жением е(р+ , + Ь, = 1,5(2 - Р+ Р 2 - ).Среднее время вычисления логарифма сос- тавляет где Т - период тактовых импульсов;и - количество сдвигов при нормализации числа х.Так, например, для устройства с разрядной сеткой в 24 разряда (=10, 1=14) абсолютная погрешность вычислений а(0,0013, а среднее время вычисления наибольшего числа х, которое можно записать в сумматор 1 с данной разрядной сеткой, составляет порядка сотни тактов. Для вычисления логарифма с погрешностью,не превосходящей а=0,0013, на универсальной ЦВМ с использованием библиотеки стандартных программ необходимо около 2500 так тов. Предлагаемое устройство имеет болеевысокое быстродействие по сравнению с известными. Цифровое устройство для логарифмирования двоичных чисел, содержащее регистр, сдвигающий регистр и схему управления, вы ход которой соединен с управляющим входомрегистра и сдвигающего регистра, отл ичающ е е с я тем, что, с целью повышения быстродействия и точности, оно содержит триггер, схему И, схему ИЛИ, два сумматора и 20 запоминающий блок причем выход сдвигающего регистра соединен с входом первого сумматора, выход этого сумматора соединен с входом сдвигающего регистра, другие выходы первого сумматоры соединены с входом схе мы ИЛИ, с входом схемы И и первымвходом схемы управления; выход схемы ИЛИ соединен с вторым выходом схемы управления и другим входом схемы И; выход схемы И соединен с третьим входом схе мы управления, выходы которой соединены соответственно с входами управления триггера, запоминающего блока, обоих сумматоров и регистров, а выход запоминающего блока соединен с входом регистра, выход которого под ключен к входу второго сумматора.