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

Союз Сфветскик СоциалистическихРеспублик оц 885997(Я)М, Кл,з с присоединением заявки Йо(23) Приоритет 806 Г 7/544 Государственный комнтет СССР по делам изобретений н отквытнВДата опубликования описания 3011,81.ЙЗ 1) Заяви ИСЛЕНИЯ ПОЛИН УСТРОИСТ иращений, накаплидешифратор, коммук вычисления кода и ин о ма ии блок Изобретение относится к вычислительной технике, в частности к арифметическим устройствам, и может бытьиспользовано в цифровых электоронныхвычислительных машинах и специализированных вычислителях для вычислениятригонометрических функций, представленных полиномами.Известно устройство для вычисления тригонометрических функций, содержащее сдвиганкцие регистры, элементы И, элементы ИЛИ, преобразователи прямого кода в дополнительный,последОвательные комбинационные сумматоры, схемы выдачи, триггеры, двоичный счетчик, схему сравнения, счетчик итераций, дешифратор, схему задания констант, схему управления 111,Недостатком известного устройстваявляется низкое быстродействие, обусловленное последовательным выполнением шагов итераций и представлениемрезультатов выполнения промежуточныхшагов и представлением результатоввыполнения промежуточных шагов однорядным кодом,Известно также устройство для вычисления функций синуса и косинуса,которое содержит счетчик аргумента,формирователь кода начального приращения, регистр првающий сумматор,татор кодов, бло. угла, блок, выдач ф рсравнения 2.Недостаток указанного устройствасостоит в низком быстродействии, обусловленном последовательным выполнением шагов суммирования приращенийи доведением результата суммирования до однорядного кода,Наиболее близким к предлагаемому является устройство для параллельногО вычисления полинома, содержащее запоминащцее устройство, группавыходных шин которого соединена стретьей группой входных шин первогокоммутатора, группа выходных шинкоммутатора содержит подгруппы вы 20 ходных шин, подключенных ко входамактивных регистров, группы выходныхшин регистров соединены с соответствуницими входами умножителей, ыходырегистров подключены к соответствующим входам второго коммутатора, группа выходных шин умножителей соединена с группой входных шин второго коммутатора, группы выходных шнн регистров подключены к группам входных шинЗО второго коьмутатора, первая группавыходных шин второго коммутатора подключена к первой группе входных шинпервого коммутатора, вторая группавыходных шин второго коммутатораподключена к группе входных шин сумматоров, выходы которых соединены соответственно со второй и четвертой груп-,пой входных шин первого коммутатора.третья группа выходных шин второгокоммутатора подключена к пятой группе входных шин первого коммутатора.Выходные управляющие шины устройствауправления подключены к управляющимзапоминающего устройства первого ивторого коммутаторов 3,Недостатком описанного устройства является большое время вычисления полинома.Цель изобретения - повышение быстродействия.Поставленная цель достигается тем,что в устройство, содержащее блок па- Щмяти, два коммутатора, входной коммутатор, два выходных коммутатора, трирегистра, сумматор и регистр результата, причем выход блока памяти соединен с первым входом входного коммутатора, первый выход входного коммутатора соединен с управляющим входомпервого регистра, второй выход входного коммутатора соединен с информационными входами второго и третьегорегистров, выходы первого и второгорегистров соединены соответственнос первым и вторым входами первогокоммутатора, выход третьего регистрасоединен с первым входом второго коммутатора, первый выход второго выход- Зного коммутатора соединен со входомсумматора, выход которого соединен синформационным входом регистра результата, дополнительно введены блок управления, первый и второй преобразователи кода частичных произведенийв двухрядный код, первая и втораягруппы элементов И, первая, втораяи третья группы входных и первая ивторая группы выходных регистров,каждая из которых состоит из двух регистров, причем информационные входырегистров первой группы входных регистров соединены с выходом первоговыходного коммутатора, информацион-ные входы регистров второй группывходных регистров соединены с первым выходом входного коммутатора ивтбрым выходом второго выходногокоммутатора, информационные входы регистров третьей группы входных регист-ров соединены с третьим выходом второго выходного коммутатора, выходырегистров первой группы входных регистров соединены с третьим входомпервого коммутатора, выходы регист- Щров второй и третьей группы входныхрегистров соединены соответственно совторым и третьим входами второго коммутатора, первый, второй и третийвыходы первого коммутатора и первый 5 выход второго коммутатора подключенык первому, второму, третьему и четвертому входам соответственно элементов И первой группы, выходы элементов которой соединены со входами первого преобразователя кода частичныхпроизведений в двухрядный код, первый, второй, третий выходы второгокоммутатора и первый выход первогокоммутатора подключены к первому,второму, третьему и четвертому входам соответственно элементов И второй группы, четвертые выходы первогои второго коммутаторов и выходы элементов И второй группы соединены совходами второго преобразователя кодачастичных произведений в двухрядныйкод, выходы первого и второго преобразователей кода частичных произведений в двухрядный код соединены синформационными входами регистров со-.ответственно первой и второй группвыходных регистров, выходы которыхсоединены соответственно с первымивходами первого и второго выходныхкоммутаторов, первый выход блока управления соединен со входом блока памяти, второй - со вторым входом второго выходного коммутатора, третийи четвертый - соответственно со вторым и третьим входами входного коммутатора, пятый - со вторым и третьим входами соответственно первогои второго выходных коммутаторов, шестой - с четвертым входом второговыходного коммутатора, седьмой ивосьмой - с четвертыми и пятыми входами соответственно первого и второго коммутаторов, девятый - с управляющими.входами всех регистров, десятый и одиннадцатый - с шестыми иседьмыми входами соответственно первого и второго коммутаторов, двенадцатый выход блока управления соединенс восьмым входом второго коммутатора. Блок управления содержит генератор импульсов, элемент ИЛИ, счетчик и двадцативосьмивыходной элемент задержйт, причем выход генератора импульсов соединен со входом элемента задержки и первым входом элемента ИЛИ, второй,.третий и четвертый входы которого соединены соответственно с четвертьм,девятым и четырнадцатым выходами элемента задержки, выход элемента ИЛИ, соединен с первым входом счетчика, второй вход которого соединен с двадцать восьмым выходом элемента задержки, выход счетчика подключен к первому выходу блока управления и первому, шестому, десятому и пятнадцатому выходам элемента задержки, второй выход блока управления соединен с двадцать седьмым выходом элемента задержки, третий - со вторым, четвертый - с шестым, одиннадцатым и шестнадцатым выходами элемента задержки, пятый - с двенадцатым, семнаДцатым, двадцать пер-вым, двадцать третьим и двадцать пятым, шестой - с седьмым, седьмойс третьим, восьмой - с восьмым и тринадцатым, девятый - сдвадцать восьмым, десятый - с восемнадцатым, одиннадцатый - с двадцатьшестым, двенадцатый выход блока управления соединен с двадцатым, двадцать вторым и двадцать четвертымвыходами элемента задержки,На фиг,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.В устройстве вычисляется по схемеГорнера полином одиннадцатой степени Р (х) (со+х (с+хСс+х (с+х (с 4+х сЮ Этот полинам может быть использован для вычисления, например,. функции синуса с относительной погрешностью не более 0,5 10 9.Устройство работает следующим об разом.В исходном состоянии в блоке 1 памяти размещены значение аргумента х и коэффициенты с 1(1:0,5), необходимые для вычислений знаи поли нома. В регистрах 4-6 и 23, группах 7, 8 и 9 входных регистров, группах 20 и 21 выходных регистров - нулевая информация. По сигналу "Пуск" генератор 44 одиночных импульсов выдает импульс, который поступает на вход элемента 45 задержки и одновременночерез элемент ИЛИ 46 - на счетчик 47 для формирования адреса. Сформированный в счетчике 47 адрес и управляющий сигнал пуска блока 1 памяти с первого выхода элемента 45 задержки поступают в блок 1 памяти для считывания аргумента х. Прием считанного аргумента х в первый регистр 4 и во вторую группу 8 входных ре гистров осуществляется по управляющему сигналу, формируемому на втором выходе элемента 45 задержки и поступающему на второй вход входного коммутатора З.По управляющему сигналу,сформиро ванному на третьем выходе элемента 45 задержки и поступающему на входы первого и второго коммутаторов 17 и 18, содержимое первого регистра 4 и второй группы 8 входных регистров передается соответственно на первый и второй входы второй группы элементов И 11, в которой осуществляется формирование матрицы частичных произведений хх. Полученная матрица частичных произведений: поступает на входы второго преобразователя 19 кода, где сворачивается до двухрядного кода с последующей записьюво вторую группу 21 выходных регистров.Одновременно с Формированием двухрядного кода произведения хх пооизводится считывание констант сс 5 и их прием во второй и третий регистры 5 и б соответственно. Это осуществляется по сигналам, получаемым на четвертом, пятом, шестом выходах 45 задержки. Сигналом, возникающим на четвертом выходе элемента 45 задержки, производится формирование в счетчике 47 адреса констант, который вместе с управляющим сигналом с пятого выхода элемента 45 задержки поступает в блок 1 памяти. Прием считанных констант с, с во второй и третий регистры 5 и б осуществляется по управляющему сигналу, приходящему на третий вход входного коммутатора 3 с шестого выхода элемента 45 задержки. По управляющему сигналу, сформированному на седьмом выходе элемента 45 задержки и поступающему на вход выходного коммутатора 12, двухрядный коД произведения х х передается из второй выходной группы 21 регистров во вторую группу 8 входных регистров. На этом заканчивается подготовительный этап. Далее начинается итерационный процесс вычисления значения полинома по Фор- муле полученной из исходной формулы (1)Процесс вычисления значения поли- нома включает итерации первого, второго, третьего и четвертого вида.Сначала выполняются итерации первого вида, затем второго и т.д. По управ- ляющему сигналу, формируемому на восьмом выходе элемента 45 задержки и поступающему на первый и второй коммутаторы 17 и 18, начинается выполнение первой итерации первого вида. В ре зультате на первую и вторую группы элементов И 10, 11 через второй коммута тор 18 со второй группы 8 входных регистров поступает хф (в виде двухрядного кода 1, а со второго и третьего регистров .5 и б через первый и второй коммутаторы 17 и 18 соответственно поступают коэффициенты с и,с, 885997ных регистрон результатов выполнения последней итерации первого вида к, и 2, иэ второго и третьего регистррон 5 и б коэффициентов с и с э соответственно. На выходах групп элементов И 10, 11 формируется многорядные коды, представляющие матрицы час" тичных произведений с Х, 2,х и с х, 2 . х соответственно, которые преобразуются в двухрядные коды с помощью первого и второго преобразователей 13 и 19 кода, заносятся в первую и вторую группы 20 и 21 выходных регистров и по сигналу, сформированному на.выходе 28 блока 2 управления и поступающему на входы первого и второго выходных коммутаторов 22 и 12, принимаются н первую и третью группы 7 и 9 входных регистров соответственно,Содержанием каждой из трех итерацийтретьего вида является умножение результата предшествующей итерации на х фи вычисление выражениях (с+к(с 4+х с,Выполнение произвольной итерации . третьего. вида начинается по сигналу, формируемому на выходе 35 блока 2 управления и поступающему на вход второго коммутатора 18. По этому сигналу через второй коммутатор 18 на вторую группу элементов И 11 выдается содержимое второй и третьей групп 8 и 9 входных регистров.Матрицы частичных произведений,форйируемых на выходе второй группы элементов И 11,с помощью второго преобразователя 19 кода сворачиваются до двухрядного кОда и подаются во вторую группу 21 выходных регистров. А посигналу, поступающему на вход второго выходного коммутатора 12 с выхода 28 блока 2 управления, содержимое второй группы 21 выходных регистров подается в третью группу 9 входных регистров .Содержанием единственной итерации четвертого вида является получение значения полинома Выполнение. итерации начинается по сигналу, поступающему с выхода 34 блока 2 управления на входы первого и второго коммутаторов 17 и 18. По этому сигналу содержимое первой и тре-.; тьей групп 7 и 9 входных регистров, в которых содержатся, соответственно, значенияХ (Соим(с+х фСи х(сь+х (с 4 хфСР-С Х+7.,дХ,60 выполнение итерации нторого вида осуществляется путем подачи на первую и вторую группы элементов И 10, 11 иэ первого регистра 4 значения х, из первой и третьей групп 7 и 9 вход- Я поступает на входы второго преобразователя 19 кода через первый и вто а также результаты выполнения предше ствующей итерации ( равные нулю для первой итерации) из первой и третьей групп 7 и 9 входных регистров.На вы-,. ходе первой и второй групп элементов И 10,. 11 получаются матрицы частичных произведений, представляющие с х 2, Ох и с х, 0 х 2 соответственно. Первая матрица частичных произведений поступает на вход первого преобразователя 13 кода, а вторая - на вход второго преобразователя 19 кода, где они преобразуются в двухрядные коды и заносятся, соответственно, в первую и вторую группы 20 и 21 выходных регистров, По сигналу, формируемому на двенадцатом выходе элемента 45 задержки и поступающему на входы первого и второго выходных коммутаторов 22 и 12, одержимое первой и второй групп 2021 выходных регистров передается со- ответстненно в первую и третью группы 20 7 и 9 входных регистров как результат выполнения текущейитерации. Одновременно с преобразованием матриц частичных произведений в двухрядные коды иэ блока 1 памяти производится 25 считывание констант с , с 4 и их прием во второй и третий активные регистры 5 и б соответственно. Это осуществляется по управляющим сигналам, форми" руемым на девятом, десятом, одиннадцатом выходах элемента задержки 45.Вторая итерация первого вида ана-. логична первой итерации и заключается н умножении йа хрезультатов выполнения предшествующей итерации и коэфФициентов с с,4 преобразования матрицы частичных произведений в двухрядный код, прием их соответствен но н первую и третью группы 7 и 9 входных регистров как результатов выполнения текущей итерации, а также 40 считывание коэффициентов с с 9 из блока 1 памяти и прием их во второй и третий регистры 5 и б соответственно.После выполнения всех итераций 4 первого вида по сигналу, сформированному на выходе 33 блока 2 управления и поступающему на входы первого и Второго коммутаторон 17 и 18, начи" нается выполнение по двум параллельным ветвям одной итерации второго вида, заключающейся н умножении на х результатов выполнения последней итерации перного вида и коэффициентов55 Р(х) -Х (Со+Х(С+Х С +Х (С+х СС 4+ХфСЭсои одгруппы число рой коммутаторы 17 и 18, сворачивает ся до двухрядного кода и по сигналу, поступающему с выхода 25 блока 2 управления на вход второго выходного коммутатора 12, подается на сумматор 14. Полученный на выходе сумматора 14 однорядный код, представляющий значение вычисляемого полинома, записывается в регистр 23 результата. На выходе 32 блока 2 управления формируется сигнал, обеспечивающий установку в исходное нулевое состояние всех регистров.Таким образом, предлагаемое устройство позволяет повысить быстродействие, Действительно, время вычисления полинома в известном устройстве равноЪ =8 са+7 к+16 стг+7 сум+З сел ф где с - время выборки иэ блокапамяти ОЬ 5; - время задержки в коммутаторе;- время срабатывания тригге" тг время умножения в умножителе, с - время сложения в сумматосл,ре. Принимая с =с , с -2 с , с =ск и тг и Выз;Т =64 с+7 с+Зс . где с, - время задержки в элементе И, Таким образомТ =64 сп+7 см+ЗсВремя вычисления полинома в предлагаемом устройстве определяется соотношениемТу =4 с 8,+20 с+20 сг+7 сп+8 спмк +сл где С мк - время преобразования многорядного кода в двухрядный. Принимая также с, =сп, с =2 с , стг и ф Еы и спмк =20 сп, получимТу=231 сп+с Выигрыш во времени определяется отношением Т 64 с +7 с +ЗсТу 2 31 сп+ с л йолагая время умножения равным ,=(а)сл (в -, разность операндов), а время сложения для сумматора со сквозным переносом равным с=2 сп (а)+4 сп, получаемТйп сп+70 свсп фТу =233 сп+2 вс и, Тогда выигрыш, достигаемый при вычислении полинома при ю =32 разрядам, получается равным Ц -1- - П- "47 ф Т14150 сТ" 297 сЕсли испольэовать сумматор сквозным групповым переносом новременным переносом внутри то ъс = - 26 +2 где Сл Я и и ) разрядов в группе . Принимая с =4, получаем Ыщ - = 316 Тп 4024 сп Ту 249 сп Формула изобретения Устройство для вычисления полинома, содержащее блок памяти, два коммутатора, входной коммутатор, двавыходных коммутатора, три регистра,сумматор и регистр результата, причем выход блока памяти соединен спервым входом входного коммутатора,первый выход входного коммутатора сое О динен с управляющим входом первогорегистра, второй выход входного коммутатора соединен с информационнымивходами второго и третьего регистров, выходы первого и второго регистров соединены соответственно с первым и вторым входами первого коммутатора, выход третьего регистра соединен с первым входом второго коммутатора, первый выход второго выходного коммутатора соединен со входомсумматора, выход которого соединенс информационным входом регистра результата, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, в него введены блок уп равления, первый и второй преобразователи кода частичных произведений в двухрядный код, первая и вторая группы элементов И, первая, вторая и третья группы входных и пер вая и вторая группы выходных регистров, каждая из которых состоит издвух регистров, причем информационные входы регистров первой группывходных регистров соединены с вы ходом первого выходного коммутатора,информационные входы регистров вто-рой группы входных регистров соединены с первым выходом входного коммутатора и вторым выходом второго вы"ходного коммутатора, информационныевходы регистров третьей группы входных регистров соединены с третьимвыходом второго выходного коммутатора, выходы регистров первой группывходных регистров соединены с третьимвходом первого коммутатора, выходырегистров второй и третьей группывходных регистров соединены соответственно со вторым и третьим входамивторого коммутатора, первый, второй 5 О и третий выходы первого коммутатораи первый выход второго коммутатораподключены к первому, второму, третьему и четвертому входам соответст-венно элементов И первой группы, вы ходы элементов которой соединены совходами первого преобразователя кодачастичных произведений в двухрядныйкод, первый, второй, третий выходывторого коммутатора и первый выход до первого коммутатора подключены к первому, второму, третьму и четвертомувходам соответственно элементов Ивторой группы, четвертые выходы первого и второго коммутаторов и выход ды элементов И второй группы соеди 885997 12нены со входами второго преобразователя кода частичных произведений в двухрядный код, выходы первого и второго преобразователей кода частичных произведений в двухрядный код соединеаюс информационными входами регистров соответственно первой и второй групп выходных регистров, выходы которых соединены соответственно с первыми входами первого и второго выходных коммутаторов, первый выход блока управления соединен со входом блока памяти, второй - со вторым входом второго выходного коммутатора,. третий и четвертый - соответственно со вторым и третьим входами входного коммутатора, пятый - со вторым и 5 третьим входами соответственно первого и второго выходных коммутаторов, шестой - с четвертым входом второго выходного коммутатора, седьмой и восьмой-с четвертыми и пятыми входами . Я .соответственно первого и второго коммутаторов, девятый - с управляющими входами всех регистров, десятый и одиннадцатый - с шестыми и седьмыми входами соответственно первого и вто- р рого коммутаторов, двенадцатый выход блока управления соединен с восьмым входом второго коммутатора.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что,. блок управления содержит генератор импульсов, элемент ИЛИ, счетчик и двадцативосьмивыходной элемент задержки, причем выход генератора импульсов соединен со входом элемента задержки и первым входом элемента ИЛИ, второй, третий, и четвертый входы которого соединены соответственно с четвертым, девятыми четырнадцатым выходами элементазадержки, выход элемента ИЛИ соединенс первым входом счетчика, второй входкоторого соединен с двадцать восьмымвыходом элемента задержки, выход счетчика подключен к первому выходу блокауправления и первому, шестому, десятому и пятнадцатому выходам элементазадержки, второй выход блока управления соединен с двадцать седьмым выходом элемента задержки, третий - совторым, четвертый - с шестым, один"-.надцатым и шестнадцатым выходамиэлемента задержки, пятый - с двенадцатым, семнадцатым, двадцать первым,двадцать третьим и двадцать пятым,шестой - с седьмым, седьмой - стретьим, восьмой " с восьмым и тринадцатым, девятый - с двадцать восьмым, десятый - с восемнадцатым,одиннадцатый - с двадцать шестымдвенадцатый выход блока управлениясоединен с двадцатым, двадцать вторым и двадцать четвертым выходамиэлемента задержки. Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССРР 474811, кл. С 06 Г 15/34, 1975.2. Авторское свидетельство СССР9 616638, кл. 6 06 Г 15/34, 1978.3, Пьявченко О.Н., Сурженко И.Ф.И,Ромм Я.К., Метод распараллеливаниясхемы Горнера и его приложение кцифровым вычислительным устройствам;Автоматика и вычислительная техника,1978, вып.5, с,73-78 1 поототип).885997 Составитель А.ЗоринТехред Т.Маточка . Корректо ахтар И.Михеева 748 Подписного комитета СССР .й и открытийРа 3 ааская наб.; д,4/5 аказ 10544/7 Тираж ИПИ Государственно по делам изобретен 035, Москва, Ж-У 5 филиал ППП "Батентф, г.Ужгород, ул.Проектн