Устройство для обращения n x n матриц
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для обращения n n-матриц. Цель изобретения - сокращение аппаратурных затрат. Цель достигается тем, что устройство содержит фиксированное число m вычислительных модулей, где m < n, причем каждый вычислительный модуль содержит три триггера, три параллельных регистра, пять сдвигающих регистров, умножитель, вычитатель, узел вычисления обратной величины числа, два элемента НЕ, пять элементов И, десять блоков элементов И и четыре блока элементов ИЛИ. 2 ил.
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для обращения (n x n)-матриц.
На фиг. 1 представлена структурная схема устройства для обращения (n x n)-матриц; на фиг. 2 схема вычислительного модуля. Устройство для обращения (n x n)-матриц (фиг. 1) содержит информационный вход 1, первый 2, второй 3, третий 4 и четвертый 5 входы режима, синхровход 6, вычислительные блоки 7i (i ), узел сдвигающих регистров 8i (i ), первый 9, второй 10 и третий 11 сдвигающие регистры, блок 12 элементов И, блок 13 элементов ИЛИ, первый 14, второй 15 и третий 16 элементы И, первый 17, второй 18 и третий 19 элементы ИЛИ и выход 20. Вычислительный модуль 7 (фиг. 2) содержит информационный вход 21, первый 22, второй 23 и третий 24 входы режима, синхровход 25, регистры 26, 27 и 28, узлы 29 и 31 задержки, регистры 30i (i ) и 32i (i ) узлов задержки, умножитель 33, вычитатель 34, узел 35 вычисления обратной величины числа, триггеры 36, 37 и 38, сдвигающие регистры 39, 40 и 41, триггеры 42i (i ), 43i (i ) и 44i (i ) сдвигающих регистров, блоки 45-54 элементов И, блоки 55-58 элементов ИЛИ, элементы И 59-63, элементы НЕ 64 и 65, первый 66 и второй 67, третий 68 и четвертый 69 выходы. В основу работы устройства положен метод Гаусса-Жордана, который представляется следующими рекуpрентными соотношениями: B A-1; a(0ij) aij, i,j a(i-1)i,n+i 1, a(i-1)i+j,n+i 0, i , j k akk(k) 1/akk(k-1) a(kik) a(kik-1), i a(kkj) a(kkj-1)a(kkk), j a(kij) a(kij-1)-a(kik)a(kkj), i a(k)k+n,j a(kkj), jbij an+i,n+j(n).
Вычислительный модуль обладает возможностью выполнения функций вида
Uj+n+3 j;
Vj+n+3 j;
Wj+n+3 j, где j, j и j значения на первом, втором и третьем входах режима вычислительного модуля на j-м такте
Uj, Vj и Wj значения на втором, третьем и четвертом выходах вычислительного модуля на j-м такте,
Fj+1
Fj+n+2 aj, если ( j j j) (1,0,1)v(0,0,1), где aj значение на информационном входе вычислительного модуля на j-м такте;
bj+1 aj/aj-z при ( j j j) (1,0,0) v (1,0,1);
сj+1 aj при (j j j) (1,1,0);
P
z n + 1;
Fj значение на выходе вычислительного модуля на j-м такте. Вычислительный модуль работает в шести режимах. В первом режиме на входы 2, 3 и 4 подаются соответственно управляющие сигналы ( ) (1,1,0). При этом триггеры 36, 37 и 38 устанавливаются соответственно в состояния "1", "1" и "0", на выходе элемента И 59 формируется единичный сигнал, который открывает блок 45 элементов И. Элемент а, подаваемый на вход 21, через блок 45 элементов И и блок 55 элементов ИЛИ по заднему фронту тактового импульса записывается в регистр 28. Содержимое регистра 30i (i ) переписывается в регистр 30i+1. Управляющие сигналы ( ) выдаются соответственно на выходы 67, 68 и 69 с задержкой на n + 3 тактов. Во втором режиме подаются управляющие сигналы ( ) (1,0,0). При этом на выходе элементов И 61 и НЕ 64, 65 формируется единичный сигнал, открываются блоки 46, 47, 48, 50 элементов И и элемент И 63. Элемент akj(k-1) , подаваемый на вход 21, через блок элементов 46 И по заднему фронту тактового импульса записывается в регистр 26. Содержимое регистра 30i (i=1,n-1 ) переписывается в регистр 30i+1, а содержимое аkk(k-1) регистра 30n в регистр 301 через блок 47 элементов И и блок 55 элементов ИЛИ. На входе узла 35 вычисления обратной величины числа формируется значение akk(k) 1/akk(k-1), которое подается на первый вход умножителя 33 через блок 50 элементов И и блок 57 элементов ИЛИ, на второй вход умножителя 33 подается с выхода регистра 26 элемент аkj(k-1) через блок 48 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение аkj(k) akj(k-1) akk(k), которое записывается на следующем такте по переднему фронту тактового импульса в регистр 27 (регистр 27 построен на однотактовых триггерах). В третьем режиме подаются управляющие сигналы ( ) (0,0,0). На выходе элемента И 60 и элементов НЕ 64, 65 формируется единичный сигнал, открываются блоки 46, 47, 49, 51 и 52 элементов И. На вход 21 подается элемент aij(k-1) и записывается в регистр 26. В регистре 27 хранится элемент akj(k). В регистрах 28 и 30i (i 1,n ) происходит циклическая перезапись (в регистр 28 записывается элемент аik(k). На первый вход умножителя 33 подается элемент aik(k) с выхода регистра 28 через блок 51 элементов И и блок 57 элементов ИЛИ. На второй вход умножителя 33 подается элемент аkj(k) с выхода регистра 27 через блок 49 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение аik(k) akj(k), которое подается на первый вход вычитателя 34, на второй вход которого подается значение аij(k-1) с выхода регистра 26. На выходе вычитателя 34 формируется значение aij(k)= aij(k-1) aik(k) akj(k), которое через блок 52 элементов И и блок 58 элементов ИЛИ выдается на выход 66. В четвертом режиме подаются управляющие сигналы ( ) (0,1,0). При этом в регистрах 28 и 30i (i ) информация циклически переписывается (блок 47 элементов И открыт). Содержимое akj(k) регистра 27 через открытый блок 53 элементов И (на выходе элемента И 62 единичный сигнал) и блок 58 элементов ИЛИ выдается на выход 66. В пятом режиме подаются управляющие сигналы ( ) (1,0,1). На вход 21 подается число, равное единице и записывается регистр 26 (блок 46 элементов И открыт). В регистрах 28 и 30i (i 1,n ) информация циклически перезаписывается (блок 47 элементов И открыт). В регистр 28 записывается элемент аkk(k-1), с выхода которого подается на узел 35 вычисления обратной величины числа. Значение аk,k+n(k) 1/akk(k-1) с выхода узла 35 вычисления обратной величины числа через открытый блок 50 элементов И (на выходе элемента И 61 единичный сигнал) и блок 57 элементов ИЛИ подается на первый вход умножителя 33, на второй вход которого подается единица с выхода регистра 26 через открытый блок 48 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение аk,k+n(k) 1/akk(k-1), которое записывается в регистр 27 на следующем такте (элемент И 63 открыт, что обеспечивает прохождение тактового импульса на вход синхронизации регистра 27). С выхода регистра 26 единица на следующем такте записывается в регистр 321 (блок 54 элементов И открыт). В шестом режиме подаются управляющие сигналы ( ) (0,0,1). Нулевое число подается на вход 21 и записывается в регистр 26. На первый и второй входы умножителя 33 подаются соответственно элемент aik(k) с выхода регистра 28 и элемент аk,k+n(k) с выхода регистра 27. На выходе умножителя 33 формируется значение аik(k) ak,k+n(k), которое подается на первый вход вычитателя 34, на второй вход которого подается нулевое значение с выхода регистра 26. На выходе вычитателя 34 формируется значение аik(k) ak,k+n(k), которое подается на выход 66. Работает устройство следующим образом. На вход 1 подаются элементы aij в моменты времени
t= i + (n + 1)j n 2. Кроме того, на вход 1 подается единичное значение на n(n + 1)-м такте, а нулевые значения подаются с [n(n + 1) + 1]-го такта по [(n + 1)n + n 1]-й такт. На управляющие входы 2, 3 и 4 подаются соответственно управляющие сигналы
( ) (1,1,0) с 0-го такта по n-й такт;
( ) (1,0,0) на (n + 1)-м такте;
( ) (0,0,0) с (n + 2)-го такта на 2n-й такт. Эта группа из n управляющих сигналов (1,0,0) и (0,0,0) повторяется еще n- 2 раза:
( ) (1,0,1) на n(n + 1)-м такте;
( ) (0,0,1) с [n(n + 1) + 1]-го такта по [(n + 1)2 1]-й такт. Элемент обратной к А матрицы bij выдается на выходе 20 в моменты времени
t= (n/m 1)(n + 1)2 + (m 1)(n + 3) + i + (n + 1)j. Период ввода элементов матриц очередной задачи обращения в поточном режиме составляет (n/m)(n + 1)2 тактов. Для обеспечения поточного режима при обращения L матриц на вход 5 подается управляющий сигнал равный нулю в моменты времени t = 0 (l 1)z + i, где z (n + 1); i 1,(n+1)2 l 1,L номер обращенной матрицы, равный единице в моменты времени
t = 1= (l 1)z + (n + 1)2 + i, i 1,(n+1)2(n/m-1). При 0 блок 12 элементов И и элементы И 14, 15 и 16 закрыты, элементы аij, подаваемые на вход 1, через блок 13 элементов ИЛИ подаются на информационный вход вычислительного модуля 71. При 1 блок 12 элементов И и элементы И 14, 15 и 16 открыты, на инфоpмационный вход вычислительного модуля 71 подаются элементы аij с выхода регистра 8p через блок 12 элементов И и блок 13 элементов ИЛИ. Управляющие сигналы и подаются на настроечные входы вычислительного модуля 71 соответственно с выходов сдвигающих регистров 9, 10 и 11 через соответствующие элементы И 14, 15 и 16 и элементы ИЛИ 17, 18 и 19. Таким образом исключается искажение информации по цепи обратной связи.
Формула изобретения