Устройство для обращения матриц

Устройство для обращения матриц

Реферат

 

Изобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для обращения n x n - матриц. Цель изобретения - сокращение аппаратурных затрат. Цель достигается тем, что устройство содержит линейку из n + 1 вычислительных модулей, два информационных входа, три настроечных входа и группу выходов. В основу работы устройства положена параллельно-поточная организация вычислений. 4 ил., 4 табл.

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов. Цель изобретения сокращение аппаратурных затрат. На фиг.1 представлена структурная схема устройства для обращения матриц; на фиг. 2 структурная схема устройства для обращения (3х3) матриц; на фиг.3 функциональная схема первого вычислительного модуля; на фиг.4 функциональная схема k-го вычислительного модуля, k=2, n+1. Устройство для обращения матриц (фиг.1) содержит первый информационный вход 1, второй информационный вход 2, первый настроечный вход 3, второй настроечный вход 4, третий настроечный вход 5, первый вычислительный модуль 6, k-й вычислительный модуль 7_i(i= ) синхровход 8 и выходы группы 9. Первый вычислительный модуль (фиг.3) содержит первый информационный вход 10, второй информационный вход 11, первый настроечный вход 12, второй настроечный вход 13, третий настроечный вход 14, синхровход 15, узел 16 вычисления обратной величины числа, регистры 17 и 18, триггеры 19, 20 и 21, группы 22, 23 и 24 элементов И, группу 25 элементов ИЛИ, информационный вход 26, первый информационный выход 27 и второй настроечный выход 28. К-й вычислительный модуль (фиг.4) содержит первый информационный вход 29, второй информационный вход 30, первый настроечный вход 31, второй настроечный вход 32, синхровход 33, регистры 34-37, умножитель 38, вычитатель 39, группы элементов И 40-45, группы элементов ИЛИ 46 и 47, триггеры 48 и 49, элементы И 50 и 51, элементы ИЛИ 52, элемент ИЛИ-НЕ 53, элемент НЕ 54, узел задержки 55, регистры узла задержки 56_i(i=) первый информационный выход 57, второй информационный выход 58, третий информационный выход 59, первый настроечный выход 60 и второй настроечный выход 61. В основу работы устройства для обращения nхn-матриц положен метод Гаусса-Жордана, который представляется следующими рекуррентными соотношениями (В= А^-1); К=K= . a⁽⁰_ij⁾= a_ij, i,j= а_in+i^(i-1)=1, а_{i+j n+i}^(i-1)=0, i ; j а_КК^(К)=1/а_КК^(К-1) a^(K_Kj⁾= a^(K_iK^-1), i a^(K_Kj⁾= a^(K_Kj^-1)a^(K_KK⁾, j а_ij^(К)=а_ij^(К-1)-а_iК^(К)а_Кj^(К), i= , j a= a b_ij=а_n+in+j⁽ⁿ⁾ При описании работы устройства в обозначении а^(К) индекс (К) указывает номер рекуррентного шага, а в обозначении а^К индекс к такт работы устройства. Логика работы вычислительных модулей 6 и 7 приведена соответственно в табл.1 и 2. Вычислительный модуль 6 работает в шести режимах. В первом режиме на настроечные входы 12, 13 и 14 подаются соответственно разряды 0, 0 и 1, которые устанавливают триггеры 19, 20 и 21 соответственно в состояние 0, 0 и 1. При этом группы 23, 24 элементов И закрыты нулевыми сигналами, подаваемыми с выходов соответственно триггеров 19 и 20, а группа 22 элементов И открыта единичным сигналом с прямого выхода триггера 21. Через открытую группу 22 элементов И и группу 25 элементов ИЛИ с выхода регистра 17 значение V выдается на выход 26. Второй режим работы вычислительного модуля 6 задается разрядами 1, 0 и 0, которые подаются соответственно на входы 12, 13 и 14. При этом триггер 9 устанавливается в единичное состояние, а триггеры 20 и 21 в нулевое состояние. Открыта только группа 24 элементов И, через которую значение 1/а с выхода вычисления обратной величины числа 16 (значение а записано в регистре 18) подается на вход группы 25 элементов ИЛИ, с выхода которой значение 1/а подается на выход 26. В третьем режиме работы разрядами 0, 1 и 0 соответственно, подаваемому на входы 12, 13 и 14, устанавливаются триггеры 19 и 20 в нулевое состояние, а триггер 20 в единичное состояние, и он открывает группу элементов И 23. С выхода регистра 18 значение а через группу 23 элементов И и группу 25 элементов ИЛИ подается на выход 26. Описанные три режима работы первого вычислительного модуля отражены в табл. 1. Аналогично описанным трем режимам легко проследить, что при наборе управляющих разрядов 0, 0, 0 на выходе 26 нулевое значение, а при наборе 1,0,1 и 0,1,1 на выходе 26 значение V, поступившее на вход 10. Вычислительный модуль 7 работает в трех режимах. В первом режиме на входы 31 и 32 подаются соответственно разряды 1 и 0, триггер 48 устанавливается в единичное состояние, а триггер 49 в нулевое, в регистр 34 записывается значение V, а в регистр 35 значение а. При этом открыты только группы 40, 41 элементов И и элемент И 50. Через группу 41 элементов И с выхода регистра 35 значение а подается на вход группы 46 элементов ИЛИ. На первый вход умножителя 38 подается с выхода регистра 34 значение V, а на его второй вход значение а с выхода группы 45 элементов ИЛИ и на выходе умножителя 38 формируется значение аV, которое подается на вход регистра 36. Значение с выхода регистра 34 подается через группу элементов И 40 на выход 57. Во втором режиме работы разрядами 0 и 1, подаваемыми соответственно в состояние 0 и 1. При этом открываются группы элементов И 40, 42, 43, 44. В регистры 34 и 35 записываются соответственно значения V' и а' (в регистре 36 в предыдущем такте записано значение R₁=аV по сигналу разрешения записи с выхода элемента И 50). На выходе умножителя 38 формируется значение V'R₁/R₁ содержимое регистра 36), а на выходе вычитателя 39 значение а'-V'R₁, которое через открытую группу 44 элементов И и группу 47 элементов ИЛИ подается на выход 59 и на вход узла задержки 55, который задерживает значение а'-V'R₁ на n-2 тактов и выдает его на выход 58 ОБ 7. Значение V' с выхода регистра 34 через группу элементов И 40 подается на выход 57. Третий режим работы задается нулевыми разрядами, которые устанавливают триггеры 48 и 49 в нулевое состояние. При этом открываются группа элементов И 45 и элемент И 51. На выходе элемента И 51 формируется сигнал разрешения записи, и в регистр 37 записывается значение R₁-аV, хранимое в регистре 36, которое через группу элементов И 45 и группу элементов ИЛИ 47 подается на выход 58 с задержкой на n-2 тактов узлом задержки 55 и на выход 59. Организация входного потока элементов а_ij, единичных и нулевых значений приведена в табл.3. На вход 2 устройства приведенные значения подаются последовательно по строкам с первой по 2n-ю строки. Рассмотрим работу устройства для обращения (3х3) матриц (фиг.2). В табл. 4 приведены состояния регистров, триггеров и формируемые значения на выходах вычислительных модулей устройства. С первого по двенадцатый такты в устройстве осуществляется доставка элемента а₁₁^(о) в вычислительный модуль 6, аналогичным образом на соответствующих тактах доставляются остальные элементы а_ji^(k) в вычислительные модули в соответствии с табл.4. С тринадцатого такта по двадцать седьмой такт реализуется вычислительный процесс обращения (3х3)-матрицы (табл. 3). Элементы а₁₁=а₁₄⁽³⁾, а₂₁=а₂₄⁽³⁾, а₃₁=а₃₄⁽³⁾ формируются на выходе 59 вычислительного модуля 7₁ соответственно на 23-м, 24-м и 25-м тактах. Элементы а₁₂=а₁₅⁽³⁾, а₂₂⁽³⁾=а₂₅⁽³⁾, а₃₂=а₃₅⁽³⁾ формируются на выходе 59 вычислительного модуля 7₂ соответственно на 24-м, 25-м и 26-м тактах. Элементы а₁₃= а₁₆⁽³⁾, а₂₃=а₂₆⁽³⁾, а₃₃=а₃₆⁽³⁾ формируются на выходе 59 вычислительного модуля 7₃ соответственно на 25-м, 26-м и 27-м тактах. Обращение (nхn)-матрицы устройством выполняется на 2n²+3n тактов.

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

УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ, содержащее n+1 вычислительных модулей (n размерность обращаемой матрицы), причем первый информационный вход первого вычислительного модуля является первым информационным входом устройства, первый информационный выход i-го вычислительного модуля подключен к первому информационному входу (i+1)-го вычислительного модуля синхровход устройства подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью сокращения аппаратурных затрат, первый, второй и третий настроечные входы устройства подключены соответственно к первому, второму и третьему настроечным входам первого вычислительного модуля, первый и второй настроечный выходы i-го вычислительного модуля подключены соответственно к первому и второму настроечным входам (i+1)-го вычислительного модуля, второй информационный вход устройства подключен к второму информационному входу (n+1)-го вычислительного модуля, второй информационный вход i-го вычислительного модуля подключен к второму информационному выходу (i+1) вычислительного модуля, i-й выход группы устройства подключен к третьему информационному выходу (i-1)-го вычислительного модуля, причем первый вычислительный модуль выполнен с возможностью реализации функций U^j+1=^j; V^j+1=^j; где (^j, ^j, ^j) значения соответственно на первом, втором и третьем настроечных входах вычислительного модуля на j-м такте; U^j, V^j значения соответственно на первом и втором настроечных выходах вычислительного модуля на j-м такте; V^j_вх, a^j значения соответственно на первом и втором информационных входах вычислительного модуля на j-м такте, V^j_вых значение на информационном выходе вычислительного модуля на j-м такте, k-й вычислительный модуль выполнен с возможностью реализации функции U^j+1=^j; V^j+1=^j; V^j+1_вых=V^j_вх, если (^j, ^j) = (1,0); V^j+1_вых=V^j_вх; где a^j_вх значения на втором информационном входе вычислительного модуля на j-м такте; a^j_вых и b^j_вых значения соответственно на втором и третьем информационных выходах вычислительного модуля на j-м такте; p и m некоторые числа, определяемые алгоритмом вычислений, причем

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8