Устройство для вычисления полинома

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советскнк социалистических

Республик

К АВТОРСКОМУ СВИ ТВЛЬСТВУ (61) Дополнительное к авт. санд-ву (22) Заявлено 250180 (2!) 2875340/18-24 (5 ) N с присоединением заявки Йо(23) Приоритет

006 F 7/544

Государственный комнтет

СССР по делам изобретений н открытнй

Опубликовано 301181 Бюллетень М 44 (53) ÍÆ 81. 3 (088. 8) Дата опубликования описания Зц11.81 (72) Авторы изобретения

A. Х. Ганитулин,. Б. Г. Зибиров и Г А. Поля 1 (71) Заявитель (54) УСТРОИСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМА

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

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

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

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

Недостаток указанного устройства состоит в низком быстродействии, обусловленном последовательным выполнением шагов суммирования приращений и доведением результата суммирования до однорядного кода.

Наиболее близким к предлагаемому является устройство для параллельного вычисления полинома, содержащее запоминанхцее устройство, группа выходных шин которого соединена с третьей группой входных шин первого коммутатора, группа выходных шин коммутатора содержит подгруппы вы20 ходных шин, подключенных ко входам активных регистров, группы выходных шин регистров соединены с соответствуницими входами умножителей, )ыходы регистров подключены к соответствующим входам второго коммутатора, группа выходных шин умножителей соединена с группой входных шин второго коммутатора, группы выходных шнн регистров подключены к группам входных шин второго коьмутатора, первая группа

885997 выходных шин второго коммутатора подключена к первой группе входных шин первого коммутатора, вторая группа выходных шин второго коммутатора подключена к группе входных шин сумматоров, выходы которых соединены соответственно со второй и четвеРтой груп-, пой входных шин первого коммутатора. третья группа выходных шин второго коммутатора подключена к пятой группе входных шин первого коммутатора.

Выходные управляющие шины устройства управления подключены к управляющим запоминающего устройства первого и второго коммутаторов (3).

Недостатком описанного устройства является большое время вычисле- 15 ния полинома.

Цель изобретения — повышение быстродействия.

Поставленная цель достигается тем, что в устройство, содержащее блок па- Щ мяти, два коммутатора, входной коммутатор, два выходных коммутатора, три регистра, сумматор и регистр результата, причем выход блока памяти соединен с первым входом входного коммутатора, первый выход входного коммутатора соединен с управляющим входом первого регистра, второй выход входного коммутатора соединен с информационными входами второго и третьего регистров, выходы первого и второго регистров соединены соответственно с первым и .вторым входами первого коммутатора, выход третьего регистра соединен с первым входом второго коммутатора, первый выход второго выход- З5 ного коммутатора соединен со входом сумматора, выход которого соединен с информационным входом регистра результата, дополнительно введены блок управления, первый и второй преобразо- 4Q ватели кода частичных произведений в двухрядный код, первая и вторая .группы элементов И, первая, вторая и третья группы входных и первая и вторая группы выходных регистров, 45 каждая из которых состоит из двух регистров, причем информационные входы регистров первой группы входных регистров соединены с выходом первого выходного коммутатора, информацион- О ные входы регистров второй группы входных регистров соединены с первым выходом входного коммутатора и втбрым выходом второго выходного коммутатора, информационные входы регистров третьей группы входных регист- 55 ров соединены с третьим выходом второго выходного коммутатора, выходы регистров первой группы входных регистров соединены с третьим входом первого коммутатора, выходы регист- 4О ров второй и третьей группы входных регистров соединены соответственно со вторым и третьим входами второго коммутатора, первый, второй и третий выходы первого коммутатора и первый ф5 выход второго коммутатора подключены к первому, второму, третьему и четвертому входам соответственно элементов И первой группы, выходы элементов которой соединены со входами первого преобразователя кода частичных произведений в двухрядный код, первый, второй, третий выходы второго коммутатора и первый выход первого коммутатора подключены к первому, второму, третьему и четвертому входам соответственно элементов И второй группы, четвертые выходы первого и второго коммутаторов и выходы элементов И второй группы соединены со входами второго преобразователя кода частичных произведений в двухрядный код, выходы первого и второго преобразователей кода частичных произведений в двухрядный код соединены c > информационными входами регистров со-. ответственно первой и второй групп выходных регистров, выходы которых соединены соответственно с первыми входами первого и второго выходных коммутаторов, первый выход блока управления соединен со входом блока памяти, второй — со вторым входом второго выходного коммутатора, третий и четвертый — соответственно со вторым и третьим входами входного коммутатора, пятый — со вторым и третьим входами соответственно первого и второго выходных коммутаторов, шестой — с четвертым входом второго выходного коммутатора, седьмой и восьмой — с четвертыми и пятыми входами соответственно первого и второго коммутаторов, девятый — c управляющими.входами всех регистров, десятый и одиннадцатый — с шестыми и седьмыми входами соответственно первого и второго коммутаторов, двенадцатый выход блока управления соединен с восьмым входом второго коммутатора.

Блок управления содержит генератор импульсов, элемент ИЛИ, счетчик и двадцативосьмивыходной элемент задержки, причем выход генератора импульсов соединен со входом элемента задержки и первым входом элемента

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

На фиг.1 представлена блок-схема предлагаемого устройства, на фиг.2 блок управления.

Устройство содержит блок 1 памяти, блок 2 управления, входной коммутатор 3, регистры 4,5 и б, группы

7, 8 и 9 входных регистров, группы элементов И 10 и 11, выходной коммутатор 12, преобразователь 13 кода частичных произведений в двухрядный 20 код, сумматор 14, регистры 15 и 16, коммутаторы 17 и 18, преобразователь

19 кода частичных произведений в двухрядный код, группы 20 и 21 выходных регистров, выходной коммутатор 22, 25 регистр 23 результата, выходы блока управления 24-35, регистры 36-43.

Блок управления содержит генератор 44 импульсов, элемент 45 задержки, элемент ИЛИ 46 и счетчик 47.

В устройстве вычисляется по схеме

Горнера полином одиннадцатой степени

Р(Х)=(Со+Х (С1+Х С2+Х (С +Х (С4+Х C<))))) ЙУ

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

Устройство работает следующим об- 40 разом.

В исходном состоянии в блоке 1 памяти размещены значение аргумента х и коэффициенты с1(1 =0,5), необходимые для вычислений значения поли- 45 нома. В регистрах 4-6 и 23, группах

7, 8 и 9 входных регистров, группах

20 и 21 выходных регистров — нулевая информация. По сигналу "Пуск" генератор 44 одиночных импульсов выдает импульс, который поступает на вход элемента 45 задержки и одновременно через элемент ИЛИ 46 — на счетчик 47 для формирования адреса. Сформированный в счетчике 47 адрес и управляющий сигнал пуска блока 1 памяти с первого выхода элемента 45 задержки поступают s блок 1 памяти для считывания аргумента х. Прием считанного аргумента х в первый регистр

4 и во вторую группу 8 входных ре- 40 гистров осуществляется по управляющему сигналу, формируемому на втором выходе элемента 45 задержки и поступающему на второй вход входного коммутатора

3.IIo управляющему сигналу,сформиро- 65 ванному на третьем выходе элемента

45 задержки и поступающему на входы первого и второго коммутаторов

17 и 18, содержимое первого регистра 4 и второй группы 8 входных регистров передается соответственно на первый и второй входы второй группы элементов И 11, в которой осуществляется формирование матрицы частичных произведений х х. Полученная матрица частичных произведений: поступает на входы второго преобразователя 19 кода, где сворачивается до двухрядного кода с последующей записью во вторую группу 21 выходных регистров.

Одновременно с формированиемдвух-. рядного кода произведения х ° х производится считывание констант с с и их прием во второй и третий регистры

5 и б соответственно. Это осуществляется по сигналам, получаемым на четвертом, пятом, шестом выходах 45 задержки. Сигналом, возникающим на четвертом выходе элемента 45 задержки, производится формирование в счетчике

47 адреса констант, который вместе с управляющим сигналом с пятого выхода элемента 45 задержки поступает в блок 1 памяти. Прием считанных констант с, с во второй и третий регистры 5 и б осуществляется по управляющему сигналу, приходящему на третий вход входного коммутатора 3 с шестого выхода элемента 45 задержки.

По управляющему сигналу, сформированному на седьмом выходе элемента 45 задержки и поступающему на вход выходного коммутатора 12, двухрядный коД произведения х х передается из второй выходной группы 21 регистров во вторую группу 8 входных регистров. На этом заканчивается подготовительный этап.

Далее начинается итерационный процесс вычисления значения полинома по формуле

Р(Х) = Х(с„+Х (с„+Х с ))+Х (С3+Х (С4+Х С6 ))I полученной из исходной формулы (1) °

Процесс вычисления значения полинома включает итерации первого, второго, третьего и четвертого вида.

Сначала выполняются итерации первого вида, затем второго и т.д. По управ- ляющему сигналу, формируемому на восьмом выходе элемента 45 задержки и поступающему на первый и второй коммутаторы 17 и 18, начинается выполнение первой итерации первого вида. В реI зультате на первую и вторую группы элементов И 10, 11 через второй коммута тор 18 со второй группы 8 входных регистров поступает х> (в виде двухрядного кодар, а со второго и третьего регистров .5 и б через первый и второй коммутаторы 17 и 18 соответственно поступают коэффициенты с и,с, 885997 а также результаты выполнения предше» ствующей итерации (равные нулю для первой итерации) из первой и третьей групп 7 и 9 входных регистров.На вы-... ходе первой и второй групп элементов

И 10, 11 полУчаются матрицы частичных произведений, представляющие с .х, 0 ix и с . х, 0 х 2соответственно.

Первая матрица частичных произведений поступает на вход первого преобразователя 13 кода, а вторая — на вход второго преобразователя 19 кода, где они преобразуются в двухрядные коды и заносятся, соответственно, в первую и вторую группы 20 и 21 выходных регистров. По сигналу, формируемому на двенадцатом выходе элемента 45 задерж-15 ки и поступающему на входы первого и второго выходных коммутаторов 22 и 12, 1 одержимое первой и второй групп 20

21 выходных регистров передается со- ответстненно в первую и третью группы )Q

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

5 и б соответственно. Это осуществляется по управляющим сигналам, формируемым на девятом, десятом, одиннадцатом выходах элемента задержки 45.

Вторая итерация первого вида ана-.: логична первой итерации и заключается н умножении йа х результатов выполнения предшествующей итерации и коэффициентов с с, преобразования матрицы частичных произведений в двухрядный код, прием их соответствен но н первую и третью группы 7 и 9 входных регистров как результатов выполнения текущей итерации, а также 40 считывание коэффициентов с, с9 из блока 1 памяти и прием их во второй и третий регистры 5 и б соответственно.

После выполнения всех итераций 45 первого вида по сигналу, сформированному на выходе 33 блока 2 управления и поступающему на входы первого и

Второго коммутаторон 17 и 18, начинается выполнение по двум параллель- 5О ным ветвям одной итерации второго вида, заключающейся н умножении на х результатов выполнения последней итерации перного вида и коэффициентов с (и с 55

Г г. =с х+г X„. (I

z" =сeх+2qp<<

d0

Выполнение итерации нторого вида осуществляется путем подачи на первую и вторую группы элементов И 10, 11 иэ первого регистра 4 значения х, из первой и третьей групп 7 и 9 входных регистров результатов выполнения последней итерации первого вида z<,g и . " иэ второго и третьего регистр рон 5 и б коэффициентов с и с э соответственно. На выходах групп элементов И 10, 11 формируется многорядные коды, представляющие матрицы час" тичных произведений с . Х, z <-х и с .х, ", < ° x соответственно, которые преобразуются в двухрядные коды с помощью первого и второго преобразователей 13 и 19 кода, заносятся в первую и вторую группы 20 и 21 выходных регистров и по сигналу, сформированному на.выходе 28 блока 2 управления и поступающему на входы первого и второго выходных коммутаторов 22 и 12, принимаются н первую и третью группы 7 и 9 входных регистров соответственно.

Содержанием каждой из трех итераций третьего вида является умножение резуль тата предшествующей итерации на х и вычисление выражения

x (с +к (с4+х с )), Выполнение произвольной итерации . третьего. вида начинается по сигналу, формируемому на выходе 35 блока 2 управления и поступающему на вход второго коммутатора 18. По этому сигналу через второй коммутатор 18 на вторую группу элементов И 11 выдается содержимое второй и третьей групп

8 и 9 входных регистров.Матрицы частичных произведений, формируемых на выходе второй группы элементов И 11,с помощью второго преобразователя 19 кода сворачиваются до двухрядного кОда и подаются во вторую группу 21 выходных регистров. A по сигналу, поступающему на вход второго выходного коммутатора 12 с выхода 28 блока 2 управления, содержимое второй группы 21 выходных регистров подается в третью группу 9 входных регистров .

Содержанием единственной итерации четвертого вида является получение значения полинома

Р(х)=Х(со+х (С +х С ))+Х (С +х (С4+х c@3, Выполнение. итерации начинается по сигналу, поступающему с выхода 34 блока 2 управления на входы первого и второго коммутаторов 17 и 18. По этому сигналу содержимое первой и тре-.; тьей групп 7 и 9 входных регистров, в которых содержатся, соответственно, значения

Х(Со Х (С +Х С )) и x(cy4x (G4RFCg))p поступает на входы второго преобразователя 19 кода через первый и вто

885997

10 первый выход входного коммутатора соеров, выходы первого и второго регист мутатора, первый выход второго выходмутатора и вторым выходом второго вывходом первого коммутатора, выходы регистров второй и третьей группы входных регистров соединены соответственно со вторым и третьим входами второго коммутатора, первый, второй и третий выходы первого коммутатора и первый выход второго коммутатора подключены к первому, второму, третьему и четвертому входам соответст- венно элементов И первой группы, выходы элементов которой соединены со входами первого преобразователя кода частичных произведений в двухрядный код, первый, второй, третий выходы второго коммутатора и первый выход первого коммутатора подключены к первому, второму, третьму и четвертому входам соответственно элементов И второй группы, четвертые выходы первого и второго коммутаторов и выходы элементов И второй группы соеди55

65 рой коммутаторы 17 и 18, сворачивает Формула изобретения ся до двухрядного кода и по сигналу, поступающему с выхода 25 блока 2 управления на вход второго выходного Устройство для вычисления полинокоммутатора 12, подается на сумматор ма содеРжащее блок памЯти, два ком14. Полученный на выходе сумматора мутатора, входной коммутатор. два

14 однорядный код, представляющий 5 выходных коммутатора, три регистра, значение вычисляемого полинома, засумматор и регистр результата, приписывается в регистр 23 результата. чем выход блока памяти соединен с .На выходе 32 блока 2 управления форпервым входом входного коммутатора, мируется сигнал, обеспечивающий уста:новку в исходное нулевое состояние f0 динен с управляющим входом первого всех регистров. регистра, второй выход входного комТаким образом, предлагаемое уст- утатора соединен с информационными ройство позволяет повысить быстровходами второго и третьего регистдействие. Действительно, время вычисления полинома в известном устройст- f5 Ров соединены соответственно с пеРве равно вым и вторым входами первого комму+27с +16с +7t +Зс

8с Я к тГ ) м сh татора, выход третьего регистра соегде t — время выборки иэ блока динен с первым входом второго компамяти )

8Ь!Е ного коммутатора соединен со входом

К ...торе; сумматора, выход которого соединен — время срабатывания тригге- с информационным входом регистра реТГ pgг зультата, о т л и ч а ю щ е е с я время умножения в умножитем, что, с целью повышения быстро м» теле действия, в него введены блок уп» ремя сложения в суммато- 25 равления, первый и второй преобраСЛ, ре. зователи кода частичных произведеПринимая с =с с, -2сд t =с„ ний в двухрядный код, первая и втоК П ТГ П и получим " и . Вык и

Т =64 t +7с.„. +3t рая группы элементов И, первая, втоlI = lI . СУМ. ССЛ рая и третья группы входных и пергде сп - время задержки в элементе И, 3О вая и вторая группы выходных регистТаким образом ров, каждая из которых состоит из

Тп =64 сп+7сУм.+3 ссл ° двух регистров, причем информационВремя вычисления полинома в пред- ные входы регистров первой группы лагаемом устройстве определяется со- входных регистров соединены с вы35 ходом первого выходного коммутатора, сцыю. ск сГГ си+ спмк + cht информационные входы регистров вто-„

Т =4с +20с +20с где С„„ — время преобразования мис- рой группы входных регистров соедигорядного кода в двух- нены с первым выходом входного комрядный. тг=2t> ° эы = 4() ходкого коммутатора, информационные

Il Т =231с +с входы регистров третьей группы входных регистров соединены с третьим

Выигрыш во времени определяется от- выходом второго выходного коммутатоношением Тл 64t +7t +3t ра, выходы регистров первой группы у 231сп+с л входных регистров соединены с третьим fToaataa время умножения равным

45 ,=(m-1)t h (m -. разность операндов), . а время сложения для сумматора со сквозным переносом равным t „ =2сп (m-1)+4tII, получаем

4П ся+70сп -8mtI, °

S0

Т)=233с„+2всп, Тогда выигрыш, достигаемый при вычислении полинома при vn =32 разрядам, получается равным

\4-1 --.= — П- 4 7 °

Т 14150t

Тч 29 ) си

Если испольэовать сумматор со

Ъ сквозным групповым переносом и одновременным переносом внутри группы, Ф

- — 2ь »21 где С - число ц)

Л Я ll » ) разрядов в группе »

Принимая f =4, получаем

Ы= — = »16

TII4024tn

Ту 249tп

885997

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

2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что,. блок управления содержит генератор импульсов, элемент ИЛИ, счетчик и двадцативосьмивыходной элемент задержки, причем выход генератора импульсов соединен со входом элемента задержки и первым входом элемента ИЛИ, второй, третий, и четвертый входы которого соединены соответственно с четвертым, девятым и четырнадцатым выходами элемента задержки, выход элемента ИЛИ соединен с первым входом счетчика, второй вход которого соединен с двадцать восьмым выходом элемента задержки, выход счетчика подключен к первому выходу блока управления и первому, шестому, десятому и пятнадцатому выходам элемента задержки, второй выход блока управления соединен с двадцать седьмым выходом элемента задержки, третий — со вторым, четвертый — с шестым, один"-. надцатым и шестнадцатым выходами элемента задержки, пятый — с двенадцатым, семнадцатым, двадцать первым, двадцать третьим и двадцать пятым, шестой - с седьмым, седьмой — с третьим, восьмой — с восьмым и тринад. цатым, девятый — с двадцать восьмым, десятый — с восемнадцатым, одиннадцатый - c двадцать шестым двенадцатый выход блока управления соединен с двадцатым, двадцать вторым и двадцать четвертым выходами элемента задержки.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

9 474811, кл. G 06 F 15/34, 1975.

2. Авторское свидетельство СССР

tt 616638, кл. G 06 F 15/34, 1978.

3. Пьявченко О.Н., Сурженко И.Ф.И, Ромм Я.К., Метод распараллеливания схемы Горнера и его приложение к цифровым вычислительным устройствам;Автоматика и вычислительная техника, 1978, вып.5, с.73-78 (прототип).

885997 г,Я

Составитель A.Çîðèí

Техред Т.Маточка, Корректор С.Щомак

Редактор И.Михеева

Филиал ППП "Патент", г.ужгород, ул.Проектная,4

Заказ 10544/70 Тираж 748 Подписное

ВНИИПИ ГосударсТвенного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-Т», Раущская наб.; д.4/5