УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ Российский патент 2015 года по МПК G06F7/544 G06F7/552 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и в автоматизированных системах научных исследований, в частности при вычислении функции вида (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{\displaystyle \sum _1^{i}i}\cdot n\cdot 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 q_i 0 1 1 0 0 1 1 1 1 0 0 2 $$p_i=q_i{\displaystyle \sum _1^{i}in{q}_i}$$ 0 4 6 6 0 12 14 16 18 0 0 $$x_i\cdot 2^{-p_i}$$ 697 87 12 12 12 0 0 0 0 0 0 3 $$p_i=q_i{\displaystyle \sum _1^{i}in{q}_i}$$ 0 6 9 0 0 18 21 24 27 0 0 $$x_i\cdot 2^{-p_i}$$ 697 11 1 1 1 0 0 0 0 0 0

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

На первом этапе величина y/x (y>x>0) представляется в виде произведения $$\frac{y}{x}={\displaystyle \prod _{i=1}^s{\left(1+2^{-i}\right)}^{q_i}}$$ , где q_i=0 или 1, i - номер итерации, равный 1, 2, …, s, где s определяется из условия: s равно минимальному i (номер итерации), для которого справедливо неравенство $${\displaystyle \sum _1^{i}i\cdot n\cdot q_i\ge k}$$ .

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

$$\begin{array}{l}{y}_1=2\left(y-x\right),{\text{ y}}_{\text{i}+\text{1}}=2\left(y_i-q_i\cdot x_i\right);\\ x_1=x,{\text{ x}}_{\text{i}+\text{1}}=x_i+q_i\cdot 2^{-i}\cdot x_i;\left(\text{1}\right)\end{array}$$

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

$$q_i=\{\begin{array}{l}1,{\text{ если y}}_{\text{i}}\ge x_i\hfill \\ 0.{\text{ если y}}_{\text{i}}<x_i\hfill \end{array}$$ .

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

$$\begin{array}{l}{x}_{a_i+1}^{\left(i\right)}=x^{\left(i\right)}+2^{-i}\cdot x^{\left(i\right)},\text{ i}=\text{s,}\dots \text{,2,1}\\ {\text{x}}_{\text{0}}^{\text{s}}=1,{\text{ x}}_{\text{0}}^{\left(\text{i-1}\right)}=x_{q_i}^{\left(i\right)},{\text{ a}}_{\text{i}}=0,1,\dots ,Q_i\left(\text{2}\right)\end{array}$$

Тогда в конце цикла получают $$x_{a_1}^{\left(1\right)}={\left(y/x\right)}^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^{\left(s\right)}=1$$ . Очередная i-я итерация начинается с того, что в устройство управления по выходной шине 13 поступает значение младшего разряда регистра 3. Если этот разряд равен нулю, то производится сдвиг регистра 3 вправо на один разряд и переход к следующей (i-1)-й итерации. В противном случае из устройства управления по входным шинам 8 и 9 поступают сигналы, формирующие величину $${\text{x}}_{{\text{a}}_{\text{i}}+\text{1}}^{\left(\text{i}\right)}={\text{x}}_{{\text{a}}_{\text{i}}}^{\left(\text{i}\right)}+{\text{2}}^{-\text{i}}\cdot {\text{x}}_{\text{a}}{}_{\text{i}}$$ в регистре 2, а по входной шине 10 поступает величина "-1", которая прибавляется к младшему разряду регистра 3, с помощью сигнала, поступающего со входной шины 9 на управляющий вход сумматора-вычитателя 6. Накопление в регистре 2 происходит до тех пор, пока младший разряд регистра 3 не обнулится. На этом очередная итерация заканчивается. Описанный процесс повторится s раз (i=s, …, 2, 1), после чего в регистре 2 образуется величина $$x_{Q_1}={\left(y/x\right)}^n$$ , которая может быть считана с выходной шины 12. Заметим, что величина (s<k) запоминается в регистре 3 на первом этапе вычисления функции $$x_{Q_1}={\left(y/x\right)}^n$$ .

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

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