Устройство для вычисления элементарных функций

Устройство для вычисления элементарных функций

Иллюстрации

Показать все

Реферат

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и в автоматизированных системах научных исследований, в частности при вычислении функции вида (y/x)ⁿ.

Известны устройства для вычисления элементарных функций [А.с. 330449 СССР Устройство для получения частного, 1972 г.], а также [А.с. 1755650 A1 Устройство для вычисления функций, 1994 г.].

Недостатком первого является невозможность возведения в степень отношения двух величин (т.е. частного двух чисел), а недостатком второго - невозможность нахождения частного и возведения его в степень одновременно (т.е. за время одной операции).

Наиболее близким по технической сущности является устройство для вычисления элементарных функций [А.с. 697994 СССР Устройство для вычисления элементарных функций, 1979 г.], служащее для возведения в степень n частного (n - натуральное число).

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

Информационный выход второго регистра сдвига соединен со вторым входом первого сумматора-вычитателя, а выход блока элементов И соединен со вторым входом второго сумматора-вычитателя. Кроме того, третья входная шина 10 соединена с входом третьего сумматора-вычитателя 6.

Недостатком этого устройства является низкое быстродействие.

Задачей настоящего изобретения является повышение технической эффективности.

Технический результат настоящего изобретения - повышенное быстродействие устройства при вычислении натуральной степени отношения (частного) двух величин без снижения точности вычисления.

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

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

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

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

Предложенное устройство для вычисления элементарных функций вида (y/x)ⁿ промышленно применимо, поскольку его техническая реализация возможна с использованием типовых элементов микроэлектронной техники (интегральные логические микросхемы).

На фиг.1 приведена структурная схема устройства для вычисления элементарных функций.

Заявленное устройство содержит первый, второй и третий 1, 2 и 3 регистры сдвига; первый, второй и третий 4, 5 и 6 сумматоры-вычитатели; блок 7 элементов И; первую, вторую и третью 8, 9, 10 входные шины устройства; первую, вторую, третью и четвертую 11, 12, 13, 14 выходные шины.

Для повышения быстродействия устройства используется блок ограничения числа итераций 15, содержащий четвертый регистр 16, счетчик итераций 17, генератор серии импульсов 18 и четвертый сумматор-вычитатель 19, выход которого соединен с четвертой выходной шиной 14.

При этом информационные выходы регистров сдвигов 1, 2, 3 соединены с первыми выходами одноименных сумматоров-вычитателей 4, 5, 6, выходы которых соединены со входами одноименных регистров сдвига 1, 2, 3 и одноименными выходными шинами 11, 12, 13 устройства, разрядные выходы второго регистра сдвига 2 соединены со входом блока элементов И 7, управляющий вход которого соединен с первой входной шиной 8 устройства, вторая 9 и третья 10 входные шины соединены соответственно с управляющими входами первого 4, второго 5 и третьего 6 сумматоров-вычитателей.

Информационный выход второго регистра сдвига 2 соединен со вторым входом первого сумматора-вычитателя 4, а выход блока элементов И 7 соединен со входом второго сумматора-вычитателя 5, кроме того, третья входная шина 10 соединена со входом третьего сумматора-вычитателя 6.

Выход блока ограничения числа итераций 15 является четвертой выходной шиной 14 устройства. В самом блоке 15 организованы следующие связи: информационный и управляющий входы четвертого сумматора-вычитателя 19 связаны с выходами счетчика итераций 17 и генератора серии импульсов 18, соответственно, входы которых, в свою очередь, связаны со второй входной шиной 9 и с первой выходной шиной 11, соответственно.

Достоверность достижения поставленной цели изобретения - повышение технической эффективности устройства - подтверждается математическим обоснованием того факта, что окончательный результат вычислений сформирован намного раньше, чем заканчиваются k итераций, где k - разрядность чисел y и x. Это происходит из-за того, что уже после p сдвигов (p<k) содержимое второго регистра сдвига 2 больше не изменяется, так как к нему подсуммируется нуль. А результат вычисления функции (y/x)ⁿ уже содержится во втором регистре сдвига 2. Математически установлено, что s i = q i ∑ 1 i i ⋅ n ⋅ q i , где s_i - суммарное количество сдвигов содержимого второго регистра 2 до i-й итерации и на i-ой итерации, n - показатель степени в выражении реализуемой функции, а q_i - величина, теоретически с одинаковой вероятностью равная либо 0, либо 1 (см. далее).

Математическое моделирование показало, что s_i>k уже для итераций с номером i, в два-три раза менее, чем разрядность k второго регистра сдвига 2.

В качестве примера приведена таблица 1 с результатами хода итераций для контрольного примера y=994 и x=697 (взяты из номера а.с. - прототипа)

Таблица 1 - Результаты хода итераций для случая y=994 и x=697.
n	i	1	2	3	4	5	6	7	8	9	10	11
qi	0	1	1	0	0	1	1	1	1	0	0
2	p i = q i ∑ 1 i i n q i	0	4	6	6	0	12	14	16	18	0	0
x i ⋅ 2 − p i	697	87	12	12	12	0	0	0	0	0	0
3	p i = q i ∑ 1 i i n q i	0	6	9	0	0	18	21	24	27	0	0
x i ⋅ 2 − p i	697	11	1	1	1	0	0	0	0	0	0

Устройство может работать при произвольном основании системы счисления. В случае двоичной системы счисления оно работает по следующему алгоритму.

На первом этапе величина y/x (y>x>0) представляется в виде произведения y x = ∏ i = 1 s ( 1 + 2 − i ) q i , где q_i=0 или 1, i - номер итерации, равный 1, 2, …, s, где s определяется из условия: s равно минимальному i (номер итерации), для которого справедливо неравенство ∑ 1 i i ⋅ n ⋅ q i ≥ k .

Для этого используются итерационные соотношения:

y 1 = 2 ( y − x ) ,  y i + 1 = 2 ( y i − q i ⋅ x i ) ; x 1 = x ,  x i + 1 = x i + q i ⋅ 2 − i ⋅ x i ;                                                                      ( 1 )

где i - номер итерации, равный 1, 2, …, s.

q i = { 1 ,  если y i ≥ x i 0.  если y i < x i .

Одновременно с выполнением действий на первом этапе формируются величины Q_i=n·q_i. На втором этапе вычисляется результат (y/x)ⁿ с помощью итерационных соотношений:

x a i + 1 ( i ) = x ( i ) + 2 − i ⋅ x ( i ) ,  i = s, … ,2,1 x 0 s = 1 ,  x 0 ( i-1 ) = x q i ( i ) ,  a i = 0 , 1 , … , Q i                                                                   ( 2 )

Тогда в конце цикла получают x a 1 ( 1 ) = ( y / x ) n .

Устройство работает следующим образом. На первом этапе вычисления производятся по соотношениям (1). В регистры 1 и 2 засылаются начальные значения y и x, а регистр 3, счетчик итераций 17 и сумматор-вычитатель 19 обнуляются. А в сумматор-вычитатель 19 заносится число n - степень в формуле. В регистр 16 также заносится степень n. На первой итерации вычисления из внешнего устройства управления по входной шине 9 на управляющий вход сумматора-вычитателя 4 поступает сигнал, формирующий разность (y-x), которая поступает с выхода сумматора-вычитателя 4 на вход регистра 1. Затем происходит сдвиг регистра 1 влево на один разряд. Таким образом, в регистрах 1 и 2 сформируются величины y₁=2(y-x) и x_i=x, регистр 3 готов к накоплению цифр Q_i. Кроме того, сигнал на входной шине 9 вычитает 1 из содержимого сумматора-вычитателя 19 (и так на каждой итерации).

На i-й итерации вычислений из устройства управления поступает сигнал, формирующий разность (y_i-x_i) в регистре 1.

Одновременно с этим на i-й итерации происходит сдвиг регистра 3 влево на один разряд. По выходной шине 11 в устройство управления поступает знак разности (y_i-x_i). Если разность отрицательна, то происходит восстановление величины y_i. Для этого из устройства управления по выходной шине 9 на управляющий вход сумматора-вычитателя 4 поступает сигнал, осуществляющий прибавление содержимого регистра 2 к содержимому регистра 1, после чего происходит сдвиг регистра 1 влево на один разряд и переход к (i+1)-й итерации. При положительной разности из устройства управления по входной шине 8 на управляющий вход блока 7 элементов И поступает сигнал, формирующий величину 2^-i·x_i на выходе этого блока. Одновременно формируется сигнал q_i=1. Он поступает на генератор серии из n импульсов (n задается регистром 16), которые вычитают n раз номер i-й итерации из содержимого сумматора-вычитателя 19. В дальнейшем, когда изменится знаковый разряд этого сумматора-вычитателя с 0 на 1, будет выдан сигнал по выходной шине 14 в устройство управления на прекращения итераций.

По входной шине 9 на управляющий вход сумматора-вычислителя 5 из устройства управления поступает сигнал, формирующий величину x_i+1=x_i+2^-i·x_i, в регистре 2. Одновременно с этим по входной шине 10 из устройства управления на второй вход сумматора-вычислителя 6 поступает величина "n", которая прибавляется к младшему разряду регистра 3 с помощью сигнала, поступающего с входной шины 9 на управляющий вход этого сумматора-вычитателя. При этом происходит также сдвиг регистра 1 влево на один разряд. На этом очередная итерация заканчивается. Процесс повторяется, таким образом, s раз (i=1, 2, …, s). Он прерывается досрочно по сравнению с прототипом (s<k) сигналом из блока ограничения числа итераций 15 по выходной шине 14 в устройство управления.

На втором этапе вычисления производятся в соответствии с соотношениями (2). Сначала в регистр 2 засылается величина x 0 ( s ) = 1 . Очередная i-я итерация начинается с того, что в устройство управления по выходной шине 13 поступает значение младшего разряда регистра 3. Если этот разряд равен нулю, то производится сдвиг регистра 3 вправо на один разряд и переход к следующей (i-1)-й итерации. В противном случае из устройства управления по входным шинам 8 и 9 поступают сигналы, формирующие величину x a i + 1 ( i ) = x a i ( i ) + 2 − i ⋅ x a i в регистре 2, а по входной шине 10 поступает величина "-1", которая прибавляется к младшему разряду регистра 3, с помощью сигнала, поступающего со входной шины 9 на управляющий вход сумматора-вычитателя 6. Накопление в регистре 2 происходит до тех пор, пока младший разряд регистра 3 не обнулится. На этом очередная итерация заканчивается. Описанный процесс повторится s раз (i=s, …, 2, 1), после чего в регистре 2 образуется величина x Q 1 = ( y / x ) n , которая может быть считана с выходной шины 12. Заметим, что величина (s<k) запоминается в регистре 3 на первом этапе вычисления функции x Q 1 = ( y / x ) n .

Устройство для вычисления элементарной функции (y/x)ⁿ, содержащее первый, второй и третий регистры сдвига, первый, второй и третий сумматоры-вычитатели, блок элементов И, информационные выходы регистров сдвига соединены с первыми входами соответствующих сумматоров-вычитателей, выходы которых соединены со входами соответствующих регистров сдвига и с соответствующими выходными шинами устройства, разрядные выходы второго регистра сдвига соединены со входами элементов И блока, управляющий вход которого соединен с первой входной шиной устройства, вторая и третья входные шины устройства соединены соответственно с управляющими входами первого, второго и третьего сумматоров-вычитателей и со вторым входом третьего сумматора-вычитателя, информационный выход второго регистра сдвига соединен со вторым входом первого сумматора-вычитателя, выход блока элементов И соединен со вторым входом второго сумматора-вычитателя, а третья входная шина соединена со входом третьего сумматора-вычитателя, отличающееся тем, что в устройство дополнительно введен блок ограничения числа итераций, состоящий из четвертого регистра, счетчика итераций, генератора серии импульсов, четвертого сумматора-вычитателя, выход которого образует дополнительную четвертую выходную шину, а его информационный и управляющий входы связаны с выходами счетчика итераций и генератора серии импульсов, соответственно, входы которых, в свою очередь, связаны со второй входной шиной и с первой выходной шиной, соответственно, кроме того, выход четвертого регистра связан с другим входом генератора серии импульсов.