Устройство для вычисления рекуррентных соотношений

(51)5 0 06 Р 15/31, 15/353 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЪТИПРИ ГКНТ СССР ПИСАНИЕ ИЗОБРЕТЕНИЯ 5 К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(21) 4753726/24 (22) 15,09.89 (46) 07.10.91. Бюл, В 37 (71) Ленинградский электротехнический институт им, В.И.Ульянова (Ленина) (72) А.А.Валов и А,Л.Лынов (53) 681.32(088.8) (56) Авторское свидетельство СССР М 1226484, кл. 0 06 Г 15/3.1, 1986.Авторское свидетельство СССР М 1546993, кл. 0 06 Р 15/31, 17.11,87, (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ РЕКУРРЕНТНЫХ СООТНОШЕНИЙГ 1(57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем. Цель изобретения - расширение функциональных возможностей за счет вычисления рекуррентных соотношений, описывающих многоместные функции по схемам примитивной, совместной и возвратной рекурсии. Поставленная цель достигается за счет того, что в состав устройства входят К групп по . (., К- целые числа) вычислительных модулей 1.К.1 =1 К;1=1 А) в каждой группе, блок 2 управления и соответствующие связи между блоками устройства. 1 з,п, ф-лы, 2 ил.Изобретение относится к вычислительной технике и может быть использовано при построении специальных вычислительных :истем.Цель изобретения -расширение функциональных возможностей за счет вычисления рекуррентных соотношений, описывающих многоместные функции по схемам примитивной, совместной и возвратной рекурсий.На фиг. 1 представлена функциональная схема вычислительного устройства; на фиг. 2 - функциональная схема вычислительного модуля.Вычислительное устройство (фиг. 1) содержит К 1 вычислительных модулей 1,1.1,1.1,1, 1.2.1,., 1,2 Я,. 1,К.1,., 1,КЛ, блок 2 управления, первый К-й информационные выходы 3.1,., З.К устройства, информационные входы первой 4.1, 4.К, второй 5.1,л 5 Л, третьей 6.1 6,1 групп устройства, информационные входы четвертой группы 7.1 7.1 устройства, вход 8 выбора режима вычислений устройства.Каждый (Ц)-й вычислительный модуль (К=1К; )=11 ) (фиг. 2) содержит регистры 9.Ц, 10.кЛ, 11,Ц, 121,.), сумматор 13,Ц, первый 14,Ц и второй 15,Ц умножители, первый 16,Ц, второй 17,Ц и третий 18.Ц коммутаторы.Блок 2 управления содержит счетчик 19 и блок 20 памятиУстройство работает следующим образом.В исходном состоянии в регистры Я.Ц занесены исходные данные для вычисления требуемой функции, счетчик 19 находится в нулевом состоянии (режим записи исходных данных в регистры 9.Ц не рассматри.вается). На вход 8 выбора режима вычислений устройства поступает код режима. Этот код поступает на старшие адресные входы блока 20 и выбирает ту область в блоке 20, в которую помещена управляющая информация данным режимом, В режиме динамической перенастройки коммутаторов вычислительных модулей в процессе работы устройства .кодом режима разрешается работа счетчика 19, Изменение содержимого счетчика 19 изменяет адрес на вход блока 20 и, следовательно, управляющую информацию для коммутаторов, поступающую с выходов блока 20. Перед запуском устройства производится запись коэффициентов С 1(1, К , и С 2(1, Ксоответственно в регистры 11,Ц и 12.Ц (Ц)-го вычислительного модуля, Коэффициенты С 1(1", Ки С 2(, Кпоступают соответственно на информационные входы 5.) и 6.) устройства в следующей последовательности:С 1(1,Ц), С 1)2,Ц),.С 1(К,Ц);С 2(1,Ц), С 2(2,Ц) С 2(К,Ц).5 При этом на входы синхронизации регистров 11,Ц и 12.Ц поступают тактовые импульсы и происходит последовательнаяпередача (запись) коэффициентов С 1(1,Ц) иС 2(Л,3) от регистров 11.Ц и 12 Лс;3 (Ц)-го10 вычислительного модуля в регистры 11,К+1и 12,К+1.) (к+1.-го вычислительного модуляПосле К тактов поступление тактовых импульсов на регистры 11.Ц и 12 ЛЦ прекращается, и в них запоминаются коэффициенты15 С 1(1,Ц) и С 2(1,Ц)После запуска устройства на входы синхронизации регистров 9.Ц и счетный входсчетчика 19 начинают поступать тактовыеимпульсы. В зависимости от режима вычис 20 лений с той же частотой на информационные входы 4.К и 7.) устройства поступаютданные. По переднему фронту тактового импульса осуществляется запись в регистры9.Ц данных с выхода сумматора 13.Ц, а25 также увеличение содержимого счетчика 19(при разрешении счета). Через время, необходимое для срабатывания регистра 9.Ц исчетчика 19, на информационные входы устройства поступают данные, В каждом такте30 работы устройства в вычислительных модулях выполняются операции умножения исложения, Период следования тактовых импульсов должен превышать суммарное время срабатывания коммутатора, умножителя35 и сумматора,Число тактов работы устройства определяется видом вычисляемой функции,Устройство позволяет вычислять значения как одноместных функций (например,40 х, а", з 1 пх и др.), так и многоместных функций (например, двухмерная фильтрация), атакже выполнять умножение матрицы навектор, умножение матрицы на матрицу,Рассмотрим работу вычислительного45 устройства на некоторых примерах (в;-.,числение значений одноместных функций, умножение матрицы на вектор в предлагаемоми известном устройствах осуществляютсяаналогично и поэтому далее не оассматри 50 ваются),Фильтрация двухмерных (одномерных)сигналов.Как известно, двухмерный фильтр с бесконечной импульсной характеристиков55 (БИХ-фильтр) описывается следующимуравнением: й -1 й 2-у (п 1 п 2) =а (п 1,л 2) х (Я 1 -п 1 =О п 2 =ОЬ 83032 п 1 =.Опг =О 30 п 1 =О М 1-1 Мг:1- п 1, вг-пг - РЬ(П 1,пг) у (в 1- п 1, пг - п 2) (1) с начальными условиями у(п 1 п 2) = 0 и х(п 1,п 2)=0 при п 10 и п 2 О),При равенстве коэффициентов Ь(п 1,пг) уравнение (1) описывает двухмерный фильтр с конечной импульсной характеристикой (КИХ-фильтр).При йг = 1 и М 2 = 1 уравнение (1) описывает одномерный БИХ-фильтр.Перепишем уравнение (1) в следующем виде:й -1у(пз 1,гпг) =а (п 1,0) х(в 1 - П 1,пц)+п 1 =ОМ - 1+,.+ , Ь(п 1,Мг - 1)у(гп 1-п,вг -п 1 =ОМ 1 - 1- Мг+ 1 -Ь(п 1,0)у(гп 1-П 1,гпг). (2)п 1=ОДля простоты рассмотрения далее будем полагать й 2 = М 2.Процесс вычисления значений у (П 1,гпг) отражают следующие рекуррентные соотношения.Вычисление значений й - .1а (п 1,0)х(п 1 - п 1 пег) "п 1 =Ой - 1а (п 1, й 2 - 1) х (п 1 1-п 1 п 12-й 2+ 1) 1=1 й 2,) =1 й 1,з(1, К=0, р(1, К,=1, ц(1, К=1,0 (1,Ц) = 1, г (1, К= О,1 (+1, К = С 1(1, К(1, ( - 1, ++ ( К)-1)где 1- 0,1,.М 2 - 1 и определяет номервычисляемой строки элементов у(е 1, вг)матрицы выходных отсчетов; й 1 и М 1 - число столбцов в матрицахвходных и выходных отсчетов соответ:твенно;й 2 и Мг - число строк в матрицах вход 5 ных и выходных отсчетов соответственно(для простоты рассуждения полагаем, чтой 1 = М 1 и йг = М 2)Из блока 20 на входы режимов вычислительных модулей поступают соответствую 10 щие коэффициенты с (1, К , г(1, К , з (,Ц),р (1, с, , ц (1 с0 (.скоторые соединяют через коммутатор16,Ц+1 второй вход умножителя 14 Ц+1 свыходом регистра 9 Ц; через коммутатор15 17 с+1.) второй вход умножителя 151+1.) свыходом регистра 10 Ц; через коммутатор181+1,) вход регистра 101+1,) с выходом регистра 10 Ц; через коммутатор 1 бК.1 второйвход умножителя 14 И с входом 4.1 устрой 20 ства; через коммутатор 17(1. второй входумножителя 15(1, с входом 7.) устройства;через коммутатор 18(1. вход регистра10(1, с входом 7.) устройства,Вычисление значений25- 1а (п 1,0)М (п 11 п 1 п 12)п 1 =О М 1 -- ) Ь (п 1 1)у(п 1 - п 1, гпг) " Ч -а (п 1, йг - 1) х(в гп щг й 2+ 1) м- ) Ь (п 1, Яг - 1) у(п 13 г 11,1 пг М 2+ 1) п 1 =О 403; = 1, Мг - 1; ) .= й 1+й 1+ " "+ 1з(, ,=0, р(1, К=-1,ц(О,=-3, й 1 - +1) + (1,3, й 1-1),(1, К= б (-1, М, ,(1, 1,= б (1- 1, 1,= у (1-)-К ; ) -й 1- 1 + 1),= з 9 (щах (М 1, й 1) - 1) = зц (М 1-),55п 11= ) 1 гпг= 1+1 (+1, 3(,= Ь (с, ) - 1) у ( - )-К 1-1 - с, ) - и в- 1 - 1+1)+1(1, К ) - 1),где 1=0,1,ОМ 2 - 1 и определяет номер вычисляемой строки элементов у(щ 1,аг) матрицы выходных отсчетов;К 1 и М 1 - число столбцов в матрицах входных и выходных отсчетов соответственно;Кг и М 2 число строк в матрицах вход" ных и выходных отсчетов соответственно (для простоты рассуждения полагаем, что К 1 =- М 1 и Кг = Мг).Из блока 20 на входы режимов вычислительных модулей поступают соответствующие коэффициенты, которые соединяют через коммутатор 16 Ц+1 второй вход умно- жителя 14 Ц+1 с выходом регистра 91.); через коммутатор 171+1.) второй вход умножителя 151+1) с выходом регистра 10 Ц; через коммутатоо 1%+1,) вход регистра 10 к+Ц с выходом регистра 10 Ц; через коммутатор 17(1. второй вход умножителя 15(1, с выходом 7. устройства; через коммутатор 18(1. вход регистра 10(1, с входом 7.) устройства.Вычисление значенийМ 1 - 1Из блока 20 на входы режимов вычислительных модулей поступают соответствующие коэффициенты р(1, К К 1+М 1+3) и о(1, К К 1+М 1+3) (коэффициенты ц(, 1, К 1+М 1+3), 2(, К К 1+ М 1+3), з(1, К К 1+ М 1+ 3) и с(, К К 1+М 1+ +3) могут принимать любые значения), которые соединяют через коммутатор 16 К.К 1+ + М 1+3 второй вход умножителя 14 КК 1+М 1+3 с выходом регистра 91+1,К+ +М 1+3; через коммутатор 17.К,К 1+М 1+3 второй вход умножителя 15 к.К 1+М 1+3 с выходом регистра 9 КК 1+М 1+2.Вычисляемые значения у(е 1, аг) поступают с выхода 3,1 устройства, который соединен с выходом регистра 9(1.К 1+М 1+3).В исходном состоянии регистры 9 Ц и 10 Ц обнулены, а в регистрах 11 Ц и 12 Ц записаны соответствующие коэффициенты а(щ 1, п 12), Ь(п 11, п 12), После запуска устройства (1 =,О,= 1, 2,) на информационные входы 7.1 7.К 1 устройства поступают элементы х (гп 1, п 12) соответствующих строк матрицы входных отсчетов, на информационные входы 7,К 1+1.7.К 1+М 1+1 устройства поступают начальные значения у(а 1, вг) соответствующих строк матрицы выходных отсчетов. Причем поступление строк элементов х(в 1, вг) и у(п 11, гпг) на информационные входы 7,) устройства в зависимости от рассматриваемого входа сдвинуто по времени на)-1 тактов. Первое вычисленное значение у(гп 1, гпг) поступает с выхода 3.1 30 35 40 45 50 55 Из блока 20 на входы режимов вычислительных модулей поступают соответствующие коэффициенты сф, вс, К 1+М 1+2), ф, к, К 1++ М 1+2), 3 (1, К К 1+ М 1+2), р(1, К К 1+ М 1+2),о (1, К К 1+М 1+2), о(, К К 1+М 1+2), которыесоединяют через коммутатор 16с.К 1+М 1+2второй вход умножителя 14 М, К 1+М 1+2 свыходом регистра 9 М,К 1+М 1+1; через коммутатор 171+1,К 1+М 1+2 второй вход умножителя 151-1 К 1+ М 1+ 2 с выходом регистра1 ОК,К 1+ М 1+ 2; через коммутатор 181+1.К 1+устройства после М +М 1+3 тактов. После вычисления всех элементов у(гп 1, пц) рассматриваемой строки происходит увеличение 3на единицу и, следовательно, сдвиг строкматриц входных и выходных отсчетов, поступающих на информационные входы 7.)устройства. При этом значение становитсяопять равным 1, Затем, процесс вычисленияследующей стооки элементов у(в 1, в 2) повторяется аналогично рассмотренному, нотолько с элементами уже вычисленныхстрок матрицы выходных отсчетов.Умножение матрицы на матрицу.роизаедение матрицы А =а (о, 3размера ххц на матрицу В = О", а ,размером (Ихой) есть матрица С = 3 с(1, 1)размером (МхЯ), элемент с(1, 1 ) которойопределяется из следующего рекуррентного соотношения:с", ")= 1",")о", ",цПроцесс вычисления элемента с(1, 1 )11матрицы С в устройстве отражают следующие рекуррентные соотношения:1=1, М,) =1, М,з (3, К 3) = О, р (1, 1,.= 1, ц (1, К= 1,о(1, К=1,г(1, К =О,1 (1+1, 3 с, ) = С 1(1 3 с, Д) 1(1, 3 сЯ + 1(3 3(, ) - 1),С 1(1,К)= 1(1, ) (К= 1,)= ) ),С 2 (1", К,= 1, ф, К о) = О,3 (1, К Д = с 3 (1 - 1, К ,13,1,= с(1-1,1, = Ь, Р),(1 еж )1,)= К),1 (3+1, К ) = а (К ) Ь(1-3 с,+ ф, 3 с, 3-1),1 (1+1, 1, Й) = а(3 с, Й) Ь( - К Й) + т(3, КИ) = С(1-И-К,3) = С(13,3)(1-И= 1,К=1 ).Из блока 20 на входы режимов вычислительных модулей поступают соответствующие коэффициенты с 3(1, К ), г(1, К , э(1, К , р (3,К), ы(1, К,Д, о(1,КД, которые соединяютчерезкоммутатор 16 Ц+1 второй вход умножителя14 Ц+1 с выходом регистра 9 К,) (выходы регистров 9 М,И соединены с выходами З.К устройства); через коммутатор 171+1.) второйвход умножителя 15 К+1,) с выходом регистра 10 Ц; через коммутатор 181+1.) вход регистра 101+1.) с выходом регистра 10 Ц;через коммутатор 161.1 второй вход умножителя 141.1 с входом 4.1 устройства; черезкоммутатор 17(1,Д второй вход умножителя15(1.) с входом 7, устройства; через коммутатор 18(1. вход регистра 10(1. с входом7.) устройства,Вычисляемые значения элементов с(1,11Е ) М-й строки матрицы С поступают с выходов 3.1 устройства, которые соединены свыходами регистров 91 М5 10 15 20 25 30 35 40 45 50 55 В исходном состоянии регистры 9 Ц и 10 Ц обнулены, а в регистрах 11 Ц и 12 Ц записаны соответствующие коэффициенты С 1(1, К ) и Сг(1, К . После запуска устройства на инфоомационные входы 7.1 7.И устройства поступают элементы Ьо, 1 )л соответствующих строк матрицы В, Причем поступление строк элементов Ь(3, 1 ) на ин. 1 формационные входы 7,) устройства в зависимости от рассматриваемого входа сдвинуто от времени на ) - 1 тактов. Первое вычисленное значение элемента с(1, 1) первой строки матрицы С поступает с выхода 3.1 устройства после 3 ч тактов. Затем на следующем такте вычисляются значения элементов с(1, 2), с(2, 1) первой и второй строк матрицы С. На следующем такте вычисляются значения элементов с(1, 3), с(2, 2), с(3, 1) соответственно первой, второй и третьей строк матрицы С и т,д.Формула изобретения 1. Устройство для вычисления рекуррентных соотношений, содержащее блок управления и первую группу из 3 (3 - целое число) вычислительных модулей, причем первый выход 1-го ( = 1, . - 1) вычислительного модуля первой группы подключен к первому информационному входу (1+1)-го вычислительного модуля первой группы, второй выход которого подключен к второму информационному входу 1-го вычислительного модуля, первый выход 3:го вычислительного модуля первой группы подключен к второму информационному входу 3:го вычислительного модуля первой группы и является первым информационным выходом группы устройства, первь м информационным входом первой группы которого является первый информационный вход первого вычислительного модуля первой группы. третий и четвертый информационные входы 1-го (1=1, Ц вычислительного модуля первой группы являются 1-ми информационными входами соответственно второй и третьей групп устройства, причем управляющий вход 1-го вычислительного модуля подключен к выходу блока управления, вход выбора режима которого является входом выбора режима устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет вычисления рекуррентных соотношений, описывающих многоместные функции по схемам примитивной, совместной и возвратной рекурсий, в него введены (К - 1) ( К - целое число) групп из 3 вычислительных модулей в каждой группе, причем первый выход 1-го вычислительного модуля )-й (3=2, К) группы подключен к первому информационному входу (1+1)-го вычислительного модуля -йгруппы, второй информационный. выход которого подключен к второму информационному входу 1-го вычислительного модуля )-й группы, первый выход 1:го вычислительного модуля )-й группы подключен к второму и пятому информационным входам 1:го вычислительного модуля )-й группыи является )-м информационным выходом группы устройства, первый выход 1:го вычислительного модуля первой группы подключен к пятому информационному входу 1:го вычислительного модуля первой группы, третий и четвертый выходы 1-го вычислительного модуля К-й (К=1, К - 1) груПпы подключены соответственно к третьему и четвертому информационным входам 1-го вычислительного модуля (К+1)-й группы, пятый информационный ВХОД 1-Га вычислительнаГО мОДуля гп-й (п=1, К) группы подключен к,пятому выходу (1+1)-го вычислительного модуля в-й группы, а пятый выход 1-го вычислительного модуля К-й группы подключен к шестому информационному входу 1-га вычислитель- ноГО моДуля (К+1)-й руы, яй вод которого подключен к седьмому информационному входу 1-га вычислительного модуля К-й группы, восьмой информационный вход которого подключен к первому выходу 1-го вычислительного модуля (К+1)-й группы, первый выход 1-го вычислительного модуля К-й группы подключен к седьмому и восьмому информационным входам 1-го вычислительного модуля К-й группы, а шестой информационный вход 1-го вычислительного модуля первой группы является 1-м ин, формационным входом четвертой группы устройства, выход блока управления подключен к управляющему входу 1-га вычислительного модуля )-й группы. 2. Устройство по п.1, отл и ча ю щеес я тем, что вычислительный модуль содержит четыре регистра, сумматор, два умна- жителя и три коммутатора, выход г 1 ервого 5 10 15 20 25 30 35 40 коммутатора подключен к информационному входу первого регистра, выходы второго и третьего коммутаторов подключены к первым входам соответственно первого и второго умножителей, выходы которых подключены соответственно к первому и второму входам сумматора, выход которого подключен к информационному входу второго регистра, выход которого является первым выходом вычислительного модуля, управляющим входом которого являются соединенные между собой управляющие входы первого, Второго и третьего коммутаторов, первые информационные входы второго и третьего коммутаторов подключены к первому информационному входу вычислительнога модуля, Вторым информационным входом которого являются соединенные между собой второй информационный вход второго коммутатора и первый информационный вход первого коммутатора, выход которого является вторым выходом вычислительнога модуля, третьим и четвертым информационными входами которого являются информационные входы соответственна третьего и четвертого регистров, выходы которых подключены к вторым входам соответственна первого и второго умножителей и являются соответственно третьим и четвертым выходами вычислительного модуля, пятым выходам и пятым информационным входом которого являются соответственно выход первого регистра и второй информационный вход первого коммутатора, третий информационный вход которого соединен с третьим информационным входом второго коммутатора и подклочен к шестому информационному входу вычислительного модуля, седьмым и восьмым информационными входами которого являются соответственно второй и третий информационные входы третьего коммутатооа, а тактовые входы всех регистров подключены к тактовому входу устройства,1683032Составитель А,Барановедактор А.Козориз Техред М.Моргентал Корректор В.Гирн Заказ 3414 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКН113035, Москва, Ж, Раушская наб., 4/5зводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 1