Устройство для обращения 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, вычислительные блоки 7_i (i ), узел сдвигающих регистров 8_i (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 задержки, регистры 30_i (i ) и 32_i (i ) узлов задержки, умножитель 33, вычитатель 34, узел 35 вычисления обратной величины числа, триггеры 36, 37 и 38, сдвигающие регистры 39, 40 и 41, триггеры 42_i (i ), 43_i (i ) и 44_i (i ) сдвигающих регистров, блоки 45-54 элементов И, блоки 55-58 элементов ИЛИ, элементы И 59-63, элементы НЕ 64 и 65, первый 66 и второй 67, третий 68 и четвертый 69 выходы.

В основу работы устройства положен метод Гаусса-Жордана, который представляется следующими рекуpрентными соотношениями: B A^-1; a⁽⁰_ij⁾ a_ij, i,j a^(i-1)_i,n+i 1, a^(i-1)_i+j,n+i 0, i , j k a_kk^(k) 1/a_kk^(k-1) a^(k_ik⁾ a^(k_ik^-1), i a^(k_kj⁾ a^(k_kj^-1)a^(k_kk⁾, j a^(k_ij⁾ a^(k_ij^-1)-a^(k_ik⁾a^(k_kj⁾, i a^(k)_k+n,j a^(k_kj⁾, j
b_ij a_n+i,n+j^(n).
Вычислительный модуль обладает возможностью выполнения функций вида
U^{j+n+3 j};
V^{j+n+3 j};
W^{j+n+3 j}, где ^j, ^j и ^j значения на первом, втором и третьем входах режима вычислительного модуля на j-м такте
U^j, V^j и W^j значения на втором, третьем и четвертом выходах вычислительного модуля на j-м такте,
F^j+1
F^j+n+2 a^j, если ( ^{j j j}) (1,0,1)v(0,0,1), где a^j значение на информационном входе вычислительного модуля на j-м такте;
b^j+1 a^j/a^j-z при ( ^{j j j}) (1,0,0) v (1,0,1);
с^j+1 a^j при (^{j j j}) (1,1,0);
P
z n + 1;
F^j значение на выходе вычислительного модуля на j-м такте.

Вычислительный модуль работает в шести режимах.

В первом режиме на входы 2, 3 и 4 подаются соответственно управляющие сигналы ( ) (1,1,0). При этом триггеры 36, 37 и 38 устанавливаются соответственно в состояния "1", "1" и "0", на выходе элемента И 59 формируется единичный сигнал, который открывает блок 45 элементов И. Элемент а, подаваемый на вход 21, через блок 45 элементов И и блок 55 элементов ИЛИ по заднему фронту тактового импульса записывается в регистр 28. Содержимое регистра 30_i (i ) переписывается в регистр 30_i+1. Управляющие сигналы ( ) выдаются соответственно на выходы 67, 68 и 69 с задержкой на n + 3 тактов.

Во втором режиме подаются управляющие сигналы ( ) (1,0,0). При этом на выходе элементов И 61 и НЕ 64, 65 формируется единичный сигнал, открываются блоки 46, 47, 48, 50 элементов И и элемент И 63. Элемент a_kj^(k-1) _, подаваемый на вход 21, через блок элементов 46 И по заднему фронту тактового импульса записывается в регистр 26. Содержимое регистра 30_i (i=1,n-1 ) переписывается в регистр 30_i+1, а содержимое а_kk^(k-1) регистра 30_n в регистр 30₁ через блок 47 элементов И и блок 55 элементов ИЛИ. На входе узла 35 вычисления обратной величины числа формируется значение a_kk^(k) 1/a_kk^(k-1), которое подается на первый вход умножителя 33 через блок 50 элементов И и блок 57 элементов ИЛИ, на второй вход умножителя 33 подается с выхода регистра 26 элемент а_kj^(k-1) через блок 48 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение а_kj^(k) a_kj^(k-1) a_kk^(k), которое записывается на следующем такте по переднему фронту тактового импульса в регистр 27 (регистр 27 построен на однотактовых триггерах).

В третьем режиме подаются управляющие сигналы ( ) (0,0,0). На выходе элемента И 60 и элементов НЕ 64, 65 формируется единичный сигнал, открываются блоки 46, 47, 49, 51 и 52 элементов И. На вход 21 подается элемент a_ij^(k-1) и записывается в регистр 26. В регистре 27 хранится элемент a_kj^(k). В регистрах 28 и 30_i (i 1,n ) происходит циклическая перезапись (в регистр 28 записывается элемент а_ik^(k). На первый вход умножителя 33 подается элемент a_ik^(k) с выхода регистра 28 через блок 51 элементов И и блок 57 элементов ИЛИ. На второй вход умножителя 33 подается элемент а_kj^(k) с выхода регистра 27 через блок 49 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение а_ik^(k) a_kj^(k), которое подается на первый вход вычитателя 34, на второй вход которого подается значение а_ij^(k-1) с выхода регистра 26. На выходе вычитателя 34 формируется значение a_ij^(k)= a_ij^(k-1) a_ik(^k) a_kj^(k), которое через блок 52 элементов И и блок 58 элементов ИЛИ выдается на выход 66.

В четвертом режиме подаются управляющие сигналы ( ) (0,1,0). При этом в регистрах 28 и 30_i (i ) информация циклически переписывается (блок 47 элементов И открыт). Содержимое a_kj^(k) регистра 27 через открытый блок 53 элементов И (на выходе элемента И 62 единичный сигнал) и блок 58 элементов ИЛИ выдается на выход 66.

В пятом режиме подаются управляющие сигналы ( ) (1,0,1). На вход 21 подается число, равное единице и записывается регистр 26 (блок 46 элементов И открыт). В регистрах 28 и 30_i (i 1,n ) информация циклически перезаписывается (блок 47 элементов И открыт). В регистр 28 записывается элемент а_kk^(k-1), с выхода которого подается на узел 35 вычисления обратной величины числа. Значение а_k,k+n^(k) 1/a_kk^(k-1) с выхода узла 35 вычисления обратной величины числа через открытый блок 50 элементов И (на выходе элемента И 61 единичный сигнал) и блок 57 элементов ИЛИ подается на первый вход умножителя 33, на второй вход которого подается единица с выхода регистра 26 через открытый блок 48 элементов И и блок 56 элементов ИЛИ. На выходе умножителя 33 формируется значение а_k,k+n^(k) 1/a_kk^(k-1), которое записывается в регистр 27 на следующем такте (элемент И 63 открыт, что обеспечивает прохождение тактового импульса на вход синхронизации регистра 27). С выхода регистра 26 единица на следующем такте записывается в регистр 32₁ (блок 54 элементов И открыт).

В шестом режиме подаются управляющие сигналы ( ) (0,0,1). Нулевое число подается на вход 21 и записывается в регистр 26. На первый и второй входы умножителя 33 подаются соответственно элемент a_ik^(k) с выхода регистра 28 и элемент а_k,k+n^(k) с выхода регистра 27. На выходе умножителя 33 формируется значение а_ik^(k) a_k,k+n^(k), которое подается на первый вход вычитателя 34, на второй вход которого подается нулевое значение с выхода регистра 26. На выходе вычитателя 34 формируется значение а_ik^(k) a_k,k+n^(k), которое подается на выход 66. Работает устройство следующим образом.

На вход 1 подаются элементы a_ij в моменты времени
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)² 1]-й такт.

Элемент обратной к А матрицы b_ij выдается на выходе 20 в моменты времени
t= (n/m 1)(n + 1)² + (m 1)(n + 3) + i + (n + 1)j.

Период ввода элементов матриц очередной задачи обращения в поточном режиме составляет (n/m)(n + 1)² тактов.

Для обеспечения поточного режима при обращения L матриц на вход 5 подается управляющий сигнал равный нулю в моменты времени t _{= 0} (l 1)z + i, где z (n + 1); i 1,(n+1)² l 1,L номер обращенной матрицы, равный единице в моменты времени
t _{= 1}= (l 1)z + (n + 1)² + i, i 1,(n+1)²(n/m-1).

При 0 блок 12 элементов И и элементы И 14, 15 и 16 закрыты, элементы а_ij, подаваемые на вход 1, через блок 13 элементов ИЛИ подаются на информационный вход вычислительного модуля 7₁.

При 1 блок 12 элементов И и элементы И 14, 15 и 16 открыты, на инфоpмационный вход вычислительного модуля 7₁ подаются элементы а_ij с выхода регистра 8_p через блок 12 элементов И и блок 13 элементов ИЛИ. Управляющие сигналы и подаются на настроечные входы вычислительного модуля 7₁ соответственно с выходов сдвигающих регистров 9, 10 и 11 через соответствующие элементы И 14, 15 и 16 и элементы ИЛИ 17, 18 и 19.

Таким образом исключается искажение информации по цепи обратной связи.

Формула изобретения

УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ N X N МАТРИЦ, содержащее m вычислительных модулей, где m целое число, m < n, n порядок матрицы, причем первый - четвертый выходы i-го вычислительного модуля, где i 1, m-1, подключены соответственно к информационному входу, к первому третьему входам режима (i + 1)-го вычислительного модуля, первый выход m-го вычислительного модуля подключен к выходу результата устройства, синхровход которого подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью сокращения аппаратурных затрат, оно содержит узел сдвигающих регистров, три сдвигающих регистра, блок элементов И, блок элементов ИЛИ, три элемента И и три элемента ИЛИ, причем информационный вход устройства подключен к первому входу блока элементов ИЛИ, второй вход и выход которого подключены соответственно к выходу блока элементов И и к информационному входу первого вычислительного модуля, первый третий входы режима устройства подключены соответственно к первым входам первого третьего элементов ИЛИ, выходы которых подключены соответственно к первому третьему входам режима первого вычислительного модуля, первый выход m-го вычислительного модуля подключен к информационному входу узла сдвигающих регистров, выход переноса узла сдвигающих регистров подключен к первому входу блока элементов И, четвертый вход режима устройства к второму входу блока элементов И и к первым входам первого третьего элементов И, второй четвертый выходы m-го вычислительного модуля подключены соответственно к информационным входам первого третьего сдвигающих регистров, выходы переноса которых подключены соответственно к информационным входам первого третьего сдвигающих регистров, выходы переноса которых подключены соответственно к вторым входам первого третьего элементов И, выходы которых подключены соответственно к вторым входам первого третьего элементов ИЛИ, синхровход устройства подключен к входам сдвига всех сдвигающих регистров и узла сдвигающих регистров, причем каждый вычислительный модуль содержит три триггера, пять сдвигающих регистров, умножитель, вычитатель, три регистра, узел вычисления обратной величины, два элемента НЕ, десять блоков элементов И и четыре блока элементов ИЛИ, причем в каждом вычислительном модуле информационный вход вычислительного модуля подключен к первым входам первого и второго блоков элементов И, выходы которых подключены соответственно к первому входу первого блока элементов ИЛИ и к информационному входу первого регистра, выход которого подключен к первым входам третьего и четвертого блоков элементов И и к первому информационному входу вычитателя, выход которого подключен к первому входу пятого блока элементов И, выход которого подключен к первому входу второго блока элементов ИЛИ, выход которого подключен к первому выходу устройства, первый вход режима которого подключен к первому входу первого элемента И и к информационному входу первого триггера, прямой выход которого подключен к информационному входу первого сдвигающего регистра и к первому входу второго элемента И, выход которого подключен к первым входам третьего и шестого блоков элементов И и к второму входу чертвертого блока элементов И, выход которого подключен к первому входу третьего блока элементов ИЛИ, выход которого подключен к первому информационному входу умножителя, выход которого подключен к второму информационному входу вычитателя и к информационному входу второго регистра, выход которого подключен к первым входам седьмого и восьмого блоков элементов И, выход последнего подключен к второму входу третьего блока элементов ИЛИ, выход первого элемента И подключен к второму входу первого блока элементов И и входу первого элемента НЕ, выход которого подключен к первому входу девятого блока элементов И, выход которого подключен к второму входу первого блока элементов ИЛИ, выход которого подключен к информационному входу третьего регистра, выход которого подключен к входу узла вычисления обратной величины, к информационному входу второго сдвигающего регистра и к первому входу десятого блока элементов И, выход которого подключен к первому входу четвертого блока элементов ИЛИ, выход которого подключен к второму информационному входу умножителя, выход третьего элемента И подключен к входу записи/считывания второго регистра, выходы переноса первого и второго сдвигающих регистров подключены соответственно к второму выходу устройства и второму входу девятого блока элементов И, выход узла вычисления обратной величины подключен к второму входу шестого блока элементов И, выход которого подключен к второму входу четвертого блока элементов ИЛИ, второй вход режима устройства подключен к информационному входу второго триггера, к второму входу первого элемента И и входу второго элемента НЕ, выход которого подключен к второму входу второго блока элементов И, прямой выход второго триггера подключен к информационному входу третьего сдвигающего регистра и к первому входу третьего элемента И, выход которого подключен к второму входу седьмого блока элементов И, выход которого подключен к второму входу второго блока элементов ИЛИ, выход переноса третьего сдвигающего регистра подключен к третьему выходу устройства, третий вход режима которого подключен к информационному входу третьего триггера, прямой выход которого подключен к информационному входу четвертого сдвигающего регистра и второму входу третьего блока элементов И, выход которого подключен к информационному входу четвертого сдвигающего регистра, выход переноса которого подключен к третьему входу второго блока элементов ИЛИ, инверсный выход первого триггера подключен к второму входу третьего элемента И и к первому входу четвертого элемента И, выход которого подключен к вторым входам пятого, восьмого и десятого блоков элементов И, инверсный выход второго триггера подключен к вторым входам второго и четвертого элементов И, выход переноса четвертого сдвигающего регистра подключен к четвертому выходу устройства, синхровход которого подключен к входам сдвига всех сдвигающих регистров, к второму входу третьего элемента И, к входам записи/считывания первого и третьего регистров.