Устройство для вычисления рекуррентных соотношений Советский патент 1991 года по МПК G06F17/10 G06F17/17 

N17-1

Ј а(щ,0)Ш 0 N1-1

x(mi - щ, та},...

а (т, N2-1) х (пщ-т, та-Ма+ 1):

-п ni 0

k 1Na, j 1N1,

sO,k,j) 0,p(i,k,J)1,u(i, k,)1, 0{l,k,J)-1.2(l,k,J) 0.

f (l + 1,k,J) Ci(l1,klJ)-l(l,k-1,J) + + f(l,k,J-1),

d(l,k,j) l(i, k-l,j),

Ci(i ,k,j) a(k-1, j-1),

C2(1, k,j)1

f (1, k, 0) 0,

I (i, k, j) d (1-1, k, j) x (l-j-k, j-k+ I),

l(l, 1,J)-d(M,1,J)-x(l-J-1,J-1+0,

I eg (max (Mi, N1)) - i) sg (Mi - Q,

mi l-j-1,ma j-1+I,

f (l+1,k,J) a(k-1,J-1) x(-j-k, j-k+D + + f(l,k.J-1),

где I 0,1,..., Ma - 1 и определяет номер вычисляемой строки элементов y(mi, ma) матрицы выходных отсчетов;

Mv- 1

- 2i b (m, Ma-1)y(mi-n i, ma-Ma+ 1):

n 0

,Ma-1; j Ni+ 1. NI-J Mi+ 1,

s(i, k,j) 0, p(i,k,j)1,u(i,k,j) 1.o(i,k,J)1,

z 0, k, j) 0,

f(H-1,k, j)Ci(l,k,j) (i,k-1,j)-t + f(l,k,J-1),

d(i,k,J) l(l, k-1,J),

Ci(l , k,j) b(k,j-1),

Ca01,k,j)1,

f (i+1, k, N1) a (k-1, Ni-1) x (i-Ni- -k, Ni-k+l) + f(i, k, Ni-1),

I(i1k,j) d(i-1,k,j),

I (1,1,j) d(i-1,1,j) y(i-j-Ni,J-Ni-1+l),

I sg (max (Mi, N1) - ) sg (Mi-i),

mi l-j-1, ma I - 1 + I,

f (1+1, k, j) b (k, j-1) у (l-J-Ni-1-k, J-Ni- -1-k+l) + f(l,k,J-1),

где ,1,0..., и определяет номер вычисляемой строки элементов y(mi,ma) матрицы выходных отсчетов;

Ni и Mi - число столбцов в матрицах входных и выходных отсчетов соответственно;

NZ и Ма число строк в матрицах входных и выходных отсчетов соответственно (для простоты рассуждения полагаем, что NI Mi и N2 Ма).

Из блока 20 на аходы режимов вычислительных модулей поступают соответствующие коэффициенты, которые соединяют через коммутатор 16k.j+1 второй вход умножителя 14k.j+1 с выходом регистра 9k.j; через коммутатор 17k+1.j второй вход умножителя 15k+1.j с выходом регистра 10k.j; через коммутатор 18k+1.j вход регистра 10k+1.j с выходом регистра 10k.j; через коммутатор 17(1 .j) второй вход умножителя 15(1.j) с выходом 7.j устройства; через коммутатор 18(1 .J) вход регистра 10(1 J) с входом 7J устройства.

Вычисление значений

N1-1 2 а(ш,0) x(mi-ni, ma)П1 0 М1-1N1-1

-2 Ь(щ, 1) -yOni-rn, ma)- Ј b(1,0)x

ni 0щ -О

xy(mi-1, та),

2, a (m, N2-2)x(mi-ni,m2-N2+2) П1 0 Ml-1

- 2) b(ni,Ma-2)y(mi-ni, ma-Ma+2)П1 0

-b(Mi-1,0) y(mi-Mi, ma):

k l7Mr:i, J Ni + Mi + 2,

s(l, k+1, Nh + Mi + 2) 0, s(l, 1,Ni+ + Mi+2)-1,

p-(i, k,Ni+Mi+2) 1, u (I, k, N1 + + M2 + 2)1,

o(l,k, N1+ Mi+ 2)1,z (I, k, N1 + + Ma + 2) 0,

f(l+1, 1, N.i + Mi + 2) Ci(i1, 1, N1+ + Mi+2)d(i, 1, Ni+Mi+3) + f(J, 1, Ni+Mi+1),

f (1+1, k+1, Ni+Mi+2)-Ci(l1,k, N1+ + Mi+2) I (i, k, Mi+ Mi+ 2) + f (i, k+ 1, N1 +

+ M1+D.

Ci(l1,k,Ni+Mi+2) -b(k, o), Ci(P,

Ma-1,Ni + Mi + 2) 0,

C2(,Ni + Mi+2)1;

d(l, 1, Ni + Mi + 3)-f(l, 1,Ni+Mi+3),

f (l+1,M2-1,Ni + Mi + 2) f(l, M2-1,

Ni+Mi+1),

I (I, k, Ni + Mi+2)-d(M,k, Ni+Mi+2), I (I, 1,Ni+Mi+2) d(l-1, 1,Ni+Mi+2)

d(M, 1.N1+M1+3).

Из блока 20 на входы режимов вычислительных модулей поступают соответствующие коэффициенты q(i, k, Ni+ Vii-t-2),z(i,k, N1+ + М1+2), s(l, k, Ni+Mi+2). p(l, k, N1+Mi+2), u (i, k, Ni+Mi+2), o(i, k, Ni+Mi+2), которые соединяют через коммутатор 16.k.Ni+Mt+2 второй вход умножителя 14 k, Ni+Mi+2 с выходом регистра 9k.Ni+Mi+1; через коммутатор 17k+1.Ni+Mi+2 второй вход умножи- теля 15k- 1,Ni+ Mi+ 2 с выходом регистра 10k.Ni+ Mi+ 2; через коммутатор 18k+1.Ni+ +М1+2 вход регистра 10k+1.Ni+Mi+2 с выходом регистра 10k.Ni+Mi+2; через коммутатор 17(1.Ni+Mi+2) второй вход умнох ителя 15(1.NI+ Mi+ 2) с выходом коммутатора 18(1. NI+ Mi+ 3); через коммутатор 18(1.Ni+Mh+2) вход регистра 10(1.Ni+Mi+2) с выходом коммутатора 18(1.Ni+Mi+3).

Вычисление значений y(mi, m2), опреде- ляемых выражением (1):

k-1Mi-1,J Ni+Mi+3,

p(l, k, Ni+Mi+3) 0, о (i, k, Ni+Mi+3) 0.

f(i+1,k, Ni+Mi+3) f(J, k, Ni+Mi+2) + +f(l,k+1, Ni+Mi+3), Ci(l1, k, Ni+Mi+3) C2(l1, k, Ni+Mi+3) 1.

f (1+1, 1, Ni+Mi+3) y(l-Ni-Mt-3,D.

mi l-Ni-Mi-3, rn2 l

Из блока 20 на входы режимов вычислительных модулей поступают соответствующие коэффициенты p(i, k, Ni+Mi+3) и o(i, k, Wi+Mi+3)(коэффициенты q(i, k, Ni+Mi+3), z(l, k, N1+ Mi+3), s(i, k, N1+ Mi+ 3) и u(l, k, NI+MI+ +3) могут принимать любые значения), которые соединяют через коммутатор 16k.N1+ + Mi+З второй вход умножителя 14k.Ni+Mi+3 с выходом регистра 9k+1.N;t- +Mi+3; через коммутатор 17,k.Ni+Mi+3 второй вход умножителя 15k.Ni+Mi+3 с выходом регистра 9k.Ni+Mi+2.

Вычисляемые значения y(mi, ma) поступают с выхода 3,1 устройства, который соединен с выходом регистра 9(1.Ni+Mi+3). В исходном состоянии регистры 9k.j и

10k.j обнулены, а в регистрах 11k.j и 12k.j записаны соответствующие коэффициенты a(mi, m2), b(mi, m2). После запуска устройства (1 0, i 1, 2,...) на информационные входы7.1,...,7. устройства поступаютэлементы х (mi, ma) соответствующих строк матрицы входных отсчетов, на информационные входы 7.Ni+17.Ni+Mi+1 устройства поступают начальные значения y(mi, ma) соответствующих строк матрицы выходных

отсчетов. Причем поступление строк элементов x(mi, ma) и у(ггп, ma) на информационные входы 7.J устройства в зависимости от рассматриваемого входа сдвинуто по времени на J-1 тактов. Первое вычисленное значение y(mi, ma) поступает с выхода 3.1

устройства после Ni+Mi+З тактов. После вычисления всех элементов y(mi, 1712) рассматриваемой строки происходит увеличение Г на единицу и, следовательно, сдвиг строк матриц входных и выходных отсчетов, поступающих на информационные входы 7.J устройства. При этом значение становится опять равным 1. Затем, процесс вычисления следующей строки элементов y(mi, mz) повторяется аналогично рассмотренному, но только с элементами уже вычисленных строк матрицы выходных отсчетов. Умножение матрицы на матрицу.

Е|роизведение матрицы А I a (I11 ,)

/И I/HV ,ft

размера (MxN) на матрицу В lb(j,

.Щ

размером (NxS) есть матрица С |c(l, k) размером (MxS), элемент c(i, k) которой определяется из следующего рекуррентного соотношения:

с() (a(i,j)b(j.k).

Процесс вычисления элемента c(i , k ) матрицы С в устройстве отражают следующие рекуррентные соотношения:

k-1M,J 1N,

s(l,k,j) 0,p(l,k,j)1,u(i,k,j)1, o(l,k,j)1,

z(l,k,J) 0,

f (1+1, k, j) Ci(l k, I) l(i, k-1 j) + f(l. k, j-1),

Ci(i,k,j) f(lV) (k- il,j A

C2( ;k, j) 1,f(i, k,o) 0,

l(i,k,J) d(i-1,k,j),

I (I, 1,j)d(M,1,j) bO,kll),(i j, i k )

f (1+1, k, j) a (k, J) b(l-k, j) + f(l, k, J-1),

f (i+1, k, N) a(k, N) b(-k, N) + f(i, k, N-1) C(l-N-k. k) C(l. k)(l-N-k l, k k ).

Из блока 20 на входы режимов вычислительных модулей поступают соответствующие коэффициенты q(i, k, j), z(l, k, j), s(l, k, j), p (I, k, j), u(l,k,j), o(i,k,J), которые соединяют через коммутатор 16k,j+1 второй вход умножителя 14k.j+1 с выходом регистра 9k.j (выходы ре- гистров 9k.N соединены с выходами 3.k устройства); через коммутатор 17k+1.j второй вход умножителя 15k+1.J с выходом регистра 10k.J; через коммутатор 18k+1,j вход регистра 10k+1.j с выходом регистра 10k.j; через коммутатор 16k.1 второй вход умножителя 14k,1 с входом 4.k устройства; через коммутатор 17(1.j) второй вход умножителя 15(1.j) с входом 7.j устройства; через коммутатор 18(1.j) вход регистра 10(1.j) с входом 7.J устройства.

Вычисляемые значения элементов c(i , k) k-й строки матрицы С поступают с выходов 3.k устройства, которые соединены с выходами регистров 9k.N.

0

5

с Q 5

0

5

0

5

0

В исходном состоянии регистры 9k.J и 10k.j обнулены, а в регистрах Hk.j и 12k.J записаны соответствующие коэффициенты Ci(i, k, j) и CzO1, k, j). После запуска устройства на информационные входы 7.17.N устройства поступают элементы b(j, k) соответствующих строк матрицы В. Причем поступление строк элементов b(j, k) на информационные входы 7,j устройства в зависимости от рассматриваемого входа сдвинуто от времени на j-1 тактов. Первое вычисленное значение элемента с(1, 1) первой строки матрицы С поступает с выхода 3.1 устройства после N тактов. Затем на следующем такте вычисляются значения элементов с(1, 2), с(2, 1) первой и второй строк матрицы С. На следующем такте вычисляются значения элементов с(1,3), с(2,2), с(3, 1) соответственно первой, второй и третьей строк матрицы С и т.д.

Формула изобретения 1. Устройство для вычисления рекуррентных соотношений, содержащее блок управления и первую группу из L (L - целое число) вычислительных модулей, причем первый выход 1-го (i 1, L-1) вычислительного модуля первой группы подключен к первому информационному входу (i+1)-ro вычислительного модуля первой группы, второй выход которого подключен к второму информационному входу 1-го вычислительного модуля, первый выход L-ro вычислительного модуля первой группы подключен к второму информационному входу L-ro вычислительного модуля первой группы и является первым информационным выходом группы устройства, первым информационным входом первой группы которого является первый информационный вход первого вычислительного модуля первой группы, третий и етвертый информационные входы 1-го (, L) вычислительного модуля первой группы являются l-ми информационными входами соответственно второй и третьей групп устройства, причем управляющий вход 1-го вычислительного модуля подключен к выходу блока управления, вход выбора режима которого является входом выбора режима устройства, отличающеес ятем, что, с целью расширения функциональных возможностей за счет вычисления рекуррентных соотношений, описывающих многоместные функции по схемам примитивной, совместной и возвратной рекурсий, в него введены (К-1) (К - целое число) групп из L вычислительных модулей в каждой группе, причем первый выход i-ro вычислительного модуля j-й (, К) группы подключен к первому информационному входу (Ы)-го вычислительного модуля j-й

группы, второй информационный выход коорого подключен к второму информационному входу i-ro вычислительного модуля j-й группы, первый выход L-ro вычислительного одуля J-й группы подключен к второму и пятому информационным входам L-ro выислительного модуля j-й группыи является -м информационным выходом группы устройства, первый выход L-ro вычислительного модуля первой группы подключен к пятому информационному входу L-ro вычислительного модуля первой группы, третий и четвертый выходы 1-го вычислительного модуля К-й (, К-1) группы подключены соответственно к третьему и четвертому информационным входам 1-го вычислительного модуля (К-Н)-й группы, пятый ииформа- ционный вхрд 1-го вычислительного модуля rn-й (, К) группы подключен к пятому выходу (1+1)-го вычислительного модуля т-й группы, а пятый выход 1-го вычислительного модуля К-й группы подключен к шестому информационному входу 1-го вычислительного модуля (К+1)-й группы, пятый выход которого подключен к седьмому информационному входу 1-го вычислительного модуля К-й группы, восьмой информационный вход которого подключен к первому выходу 1-го вычислительного модуля (К+1)-й группы, первый выход 1-го вычислительного модуля К-й группы подключен к. седьмому и восьмому информационным входам 1-го вычислительного модуля К-й rpYnnbi, а шестой информационный вход 1-го вычислительного модуля первой группы является S-м ин- формационным входом четвертой группы устройства, выход блока управления подключен к управляющему входу 1-го вычислительного модуля j-й группы.

2. Устройство по п. 1, о т л и ч а ю щ е е- с я тем, что вычислительный модуль содержит четыре регистра, сумматор, два умножителя и три коммутатора, выход первого

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

второго коммутатора и первый информационный вход первого коммутатора, выход которого является вторым выходом вычислительного модуля, третьим и четвертым информационными входами которого

являются информационные входы соответственно третьего и четвертого регистров, выходы которых подключены к вторым входам соответственно первого и второго умно- жителей и являются соответственно

третьим и четвертым выходами вычислительного модуля, пятым выходом и пятым информационным входом которого являются соответственно выход первого регистра и второй информационный вход первого

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

«Si vi

n

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем. Цель изобретения - расширение функциональных возможностей за счет вычисления рекуррентных соотношений, описывающих многоместные функции по схемам примитивной, совместной и возвратной рекурсии. Поставленная цель достигается за счет того, что в состав устройства входят К групп по L(L, К- целые числа) вычислительных модулей 1.K.I (,K; ) в каждой группе, блок 2 управления и соответствующие связи между блоками устройства. 1 з.п, ф-лы, 2 ил.