устройство для решения систем линейных алгебраических уравнений

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

1. УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее n вычислительных модулей первого типа (где n - порядок системы линейных уравнений), каждый из которых содержит умножитель, вычитатель, узлы задержки с первого по третий, два регистра, первый и второй триггеры, группы элементов И с первой по девятую, группы элементов ИЛИ с первой по четвертую, элементы И с первого по пятый и первый и второй элементы НЕ, причем первый и второй настроечные входы устройства подключены соответственно к первому и второму настроечным входам первого вычислительного модуля первого типа, информационный выход i-го вычислительного модуля первого типа (i = ) подключен к информационному входу (i + 1)-го вычислительного модуля первого типа, первый и второй настроечные выходы i-го вычислительного модуля первого типа подключены соответственно к первому и второму настроечным входам (i + 1)-го вычислительного модуля первого типа, информационный выход n-го вычислительного модуля первого типа подключен к выходу устройства, синхровход которого подключен к синхровходам всех вычислительных модулей первого типа, отличающееся тем, что, с целью повышения точности вычисления за счет выбора ведущего элемента по столбцам матрицы, введен вычислительный модуль второго типа, причем информационный вход устройства подключен к информационному входу вычислительного модуля второго типа, третий и четвертый настроечные выходы устройства подключены соответственно к третьему и четвертому настроечным входам первого вычислительного модуля первого типа, пятый настроечный вход устройства подключен к пятым настроечным входам j-х вычислительных модулей первого типа (j = ), шестой и седьмой настроечные входы устройства подключены соответственно к первому и второму настроечным входам вычислительного модуля второго типа, информационный выход которого подключен к информационному входу первого вычислительного модуля первого типа, третий и четвертый настроечные выходы i-го вычислительного модуля первого типа подключены соответственно к третьему и четвертому настроечным входам (i + 1)-го вычислительного модуля первого типа, синхровход устройства подключен к синхровходу вычислительного модуля второго типа, а в каждый вычислительный модуль первого типа введены делитель, коммутатор, узлы задержки с четвертого по седьмой, триггеры с третьего по седьмой, группы элементов И с десятой по двенадцатую, элементы И с шестого по четырнадцатый, пятую группу элементов ИЛИ, два элемента ИЛИ и элементы НЕ с третьего по пятый, при этом в каждом вычислительном модуле первого типа информационный вход модуля подключен к первым входам элементов И первой и второй групп, выходы которых подключены соответственно к первым входам элементов ИЛИ первой и второй групп, выходы которых подключены к информационным входам первых регистров соответственно первого и второго узлов задержки, выход первого регистра первого узла задержки подключен к первым входам вычитателя, делителя и элементов И третьей группы, выходы элементов И третьей группы подключены к первым входам элементов ИЛИ третьей группы, вторые, третьи и четвертые входы которых подключены соответственно к выходам элементов И четвертой, пятой и шестой групп, а выходы - к информационному входу второго регистра первого узла задержки, выход K-го регистра первого узла задержки (K = ) подключен к информационному входу (K + 1)-го регистра первого узла задержки, выход n-го регистра первого узла задержки подключен к первым входам элементов И седьмой группы, выходы которых подключены к первым входам элементов ИЛИ четвертой группы, вторые входы которых подключены к выходу элементов И восьмой группы, а выходы - к информационному выходу модуля, вторые входы элементов ИЛИ первой группы подключены к выходам элементов И девятой группы, первые входы которых подключены к первому входу умножителя и выходу первого регистра, информационный вход которого подключен к выходу делителя, а синхровход - к выходу первого элемента И, вторые входы элементов ИЛИ второй группы подключены к выходам элементов И десятой группы, первые входы которых подключены к выходу (n + 1)-го регистра второго узла задержки, выход первого регистра которого подключен к второму входу делителя, информационному входу второго регистра второго узла задержки и второму входу умножителя, выход которого подключен к второму входу вычитателя, выход которого подключен к первым входам элементов И четвертой и одиннадцатой групп и первому входу коммутатора, выход l-го регистра второго узла задержки подключен к информационному входу (l + 1)-го регистра второго узла задержки (l = ), выходы элементов И одиннадцатой и двенадцатой групп подключены соответственно к первым и вторым входам элементов ИЛИ пятой группы, выходы которых подключены к информационному входу второго регистра, синхровход которого подключен к выходу второго элемента И, а выход - к первым входам элементов И пятой и восьмой групп и второму входу коммутатора, первые, вторые и третьи выходы которого подключены соответственно к первым входам элементов И шестой группы, первым входам элементов И двенадцатой группы и первому входу третьего элемента И, выход которого подключен к первому входу первого элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И, а выход - к информационному входу первого триггера третьего узла задержки, выход i-го триггера которого (j = ) подключен к информационному входу (j + 1)-го триггера третьего узла задержки, а прямой выход (n + 1)-го триггера подключен к первому входу четвертого элемента И, четвертый настроечный вход модуля подключен к первому входу второго элемента ИЛИ, выход которого подключен к информационному входу первого триггера четвертого узла задержки, выход l-го триггера которого (l = 1) подключен к информационному входу (l + 1)-го триггера четвертого узла задержки, выход n-го триггера четвертого узла задержки подключен к четвертому настроечному выходу модуля, пятый настроечный вход которого подключен к первому входу пятого элемента И, выход которого подключен к второму входу второго элемента ИЛИ, первый настроечный вход модуля подключен к первым входам шестого, седьмого и восьмого элементов И, к входу первого элемента НЕ и информационному входу первого триггера пятого узла задержки, выход K-го триггера p-го узла задержки (K = , p = ) подключен к информационному входу (K + 1)-го триггера p-го узла задержки, второй настроечный вход модуля подключен к вторым входам шестого и седьмого элементов И, первому входу девятого элемента И, входу второго элемента НЕ и информационному входу первого триггера шестого узла задержки, третий настроечный вход вычислительного модуля подключен к третьему входу шестого элемента И, первому входу десятого элемента И, входу третьего элемента НЕ и информационному входу первого триггера седьмого узла задержки, выходы (2n + 2)-х триггеров пятого, шестого и седьмого узлов задержки подключены соответственно к первому, второму и третьему настроечным выходам модуля, выход шестого элемента И подключен к входу четвертого элемента НЕ и вторым входам элементов И второй группы, выход четвертого элемента НЕ подключен к вторым входам элементов И десятой группы и второму входу четвертого элемента И, выход третьего элемента НЕ подключен к вторым входам восьмого и девятого элементов И, к первому входу одиннадцатого элемента И и третьему входу седьмого элемента И, выход которого подключен к вторым входам элементов И первой и третьей групп и информационному входу первого триггера, выход которого подключен к первому входу первого элемента И, выход второго элемента НЕ подключен к вторым входам десятого и одиннадцатого элементов И и третьему входу восьмого элемента И, выход которого подключен к вторым входам элементов И третьей и девятой групп, второму входу пятого элемента И и информационному входу второго триггера, прямой выход которого подключен к вторым входам элементов И восьмой группы, а инверсный выход - к вторым входам элементов седьмой группы, выход первого элемента НЕ подключен к третьим входам девятого, десятого и одиннадцатого элементов И и первому входу двенадцатого элемента И, выход которого подключен к вторым входам элементов И первой группы и информационному входу третьего триггера, выход которого подключен к вторым входам элементов И четвертой группы, выход пятого элемента НЕ подключен к четвертым входам девятого, десятого и одиннадцатого элементов И, выход девятого элемента И подключен к вторым входам элементов И первой группы и информационному входу четвертого триггера, выход которого подключен к вторым входам второго элемента И и элементов И одиннадцатой группы, выход десятого элемента И подключен к вторым входам элементов И первой группы и информационному входу пятого триггера, выход которого подключен к вторым входам элементов И шестой и двенадцатой групп и вторым входам второго и третьего элементов И, выход одиннадцатого элемента И подключен к первым входам тринадцатого и четырнадцатого элементов И, прямой выход (n + 1)-го триггера третьего узла задержки подключен к второму входу тринадцатого элемента И, а инверсный выход - к второму входу четырнадцатого элемента И, выход которого подключен к информационному входу шестого триггера, выход которого подключен к вторым входам элементов И четвертой группы, выход тринадцатого элемента И подключен к вторым входам элементов И первой группы и информационному входу седьмого триггера, выход которого подключен к вторым входам элементов И пятой и одиннадцатой групп и к первому входу второго элемента И, синхровход модуля подключен к синхровходам всех регистров первого и второго узлов задержки, всех триггеров с третьего по седьмой узлов задержки, с первого по седьмой триггеров, к вторым входам первого и второго элементов И, четвертый настроечный вход модуля подключен к входу пятого элемента НЕ и второму входу двенадцатого элемента И.

2. Устройство по п. 1, отличающееся тем, что вычислительный модуль второго типа содержит два узла задержки, регистр, узел сравнения, четыре триггера, шесть групп элементов И, девять элементов И, две группы элементов ИЛИ, четыре элемента ИЛИ и четыре элемента НЕ, причем информационный вход модуля подключен к первым входам элементов И первой и второй групп, узла сравнения и информационному входу регистра, вторые входу элементов И первой группы подключены к выходу первого элемента НЕ, а выходы - к первым входам элементов ИЛ первой группы, вторые входы которых подключены к выходам элементов И второй группы, вторые входы которых подключены к выходу второго элемента НЕ, а третьи входы - к выходу первого элемента И, информационному входу первого триггера, первому входу первого элемента ИЛИ, первым входам элементов И третьей группы и первому входу второго элемента И, второй вход которого подключен к вторым входам элементов И третьей группы, входу второго элемента НЕ, первому входу третьего элемента И и к выходу (n + 1)-го триггера первого узла задержки, а выход - к первому входу второго элемента ИЛИ, второй вход которого подключен к выходу третьего элемента И, а третий вход - к выходу четвертого элемента И, выход второго элемента ИЛИ подключен к синхровходу регистра, выход которого подключен к второму входу узла сравнения, к первым входам элементов И четвертой группы, третьим входам элементов И третьей группы и первым входам элементов И пятой группы, вторые входы которых подключены к выходу второго триггера, а выход - к первым входам элементов ИЛИ второй группы, выход которых подключен к выходу модуля, первый настроечный вход которого подключен к входу третьего элемента НЕ, первым входам пятого и шестого элементов И, второй настроечный вход модуля подключен к входу четвертого элемента НЕ, второму входу пятого элемента И и первому входу седьмого элемента И, выход третьего элемента НЕ подключен к второму входу седьмого элемента И и первому входу первого элемента И, выход четвертого элемента НЕ подключен к вторым входам первого и шестого элементов И, выход пятого элемента И подключен к первому входу третьего элемента И, второму входу первого элемента ИЛИ и информационному входу третьего триггера, выход шестого элемента И подключен к третьим входам элементов и первой группы, вторым входам элементов И четвертой группы, первым входам четвертого и восьмого элементов И, информационному входу четвертого триггера, выход седьмого элемента И подключен к третьему входу первого элемента ИЛИ и информационному входу второго триггера, выход первого, третьего и четвертого триггеров подключены соответственно к первому, второму и третьему входам третьего элемента ИЛИ, выход которого подключен к первым входам элементов И шестой группы, выходы которых подключены к вторым входам элементов ИЛИ второй группы, выход узла сравнения подключен к второму входу четвертого элемента И, входу первого элемента НЕ, третьим входам элементов И четвертой группы и второму входу восьмого элемента И, выход которого подключен к первому входу четвертого элемента ИЛИ, второй вход которого подключен к выходу третьего элемента И, второй вход которого подключен к выходу первого элемента ИЛИ, выход четвертого элемента ИЛИ подключен к информационному входу первого триггера первого узла задержки, выход j-го триггера которого (j = ) подключен к информационному входу (j + 1)-го триггера, выходы элементов или первой группы подключены к информационному входу первого регистра второго узла задержки, выход j-го регистра которого подключен к информационному входу (j + 1)-го регистра, выход (n + 1)-го регистра второго узла задержки подключен к вторым входам элементов И шестой группы, синхровход модуля подключен к синхровходам всех регистров и триггеров, к третьим входам второго и четвертого элементов И и второму входу третьего элемента И, третьи и четвертые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И третьей и четвертой групп.

Описание изобретения к патенту

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для решения систем линейных алгебраических уравнений.

Целью изобретения является повышение точности вычисления за счет выбора ведущего элемента по столбцам матрицы.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 - структурная схема устройства для случая n= 3 и m= 1; на фиг. 3 - схема вычислительного модуля второго типа; на фиг. 4 - схема вычислительного модуля первого типа; на фиг 5 - схема коммутатора.

Устройство для решения систем линейных алгебраических уравнений (фиг. 1) содержит информационный вход 1, настроеные входы 2-8, синхровход 9, вычислительный модуль 10 второго типа, вычислительные модули 11_i (i= ) первого типа и выход 12.

Вычислительный модуль 10 второго типа (фиг. 3) содержит информационный вход 13, первый 14 и второй 15 настроечные входы, синхровход 16, первый узел 17 задержки, регистр 18, узел 19 сравнения, второй узел 20 задержки, триггеры 21-24, группы 25-30 элементов И, элементы И 31-39, группы 40 и 41 элементов ИЛИ, элементы ИЛИ 42-45, элементы НЕ 46, 47, 48₁ и 48₂ и выход 49.

Вычислительный модуль 11 первого типа (фиг. 4) содержит информационный вход 50, первый 51, второй 52, третий 53, четвертый 54 и пятый 55 настроечные входы, синхровход 56, четвертый 57 и первый 58 узлы задержки, регистр 59, второй узел 60 задержки, регистр 61, третий узел 62 задержки, делитель 63, умножитель 64, вычитатель 65, коммутатор 66, триггеры 67-73, пятый 74, шестой 75, седьмой 76 узел задержки, группы 77-88 элементов И, элементы И 89-101, группы 102-106 элементов ИЛИ, элементы ИЛИ 107 и 108, элементы НЕ 109-113, элемент 114, информационный выход 115, первый 116, второй 117, третий 118 и четвертый 119 настроечные выходы.

Коммутатор 66 (фиг. 5) содержит первый 120 и второй 121 входы, узел 122 сравнения, группы элементов И 123-126, группы элементов ИЛИ 127 и 128, элемент НЕ 129, первый 130, второй 131 и третий 132 выходы.

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

A^j+1= _, где b^j= a^j-1, если ( ^j-1, ^j-1 )= (1, 1)V

( ^j-1, ^j-1, ^j-1 )= (1, 0, 1)V

( ^j-1, ^j-1, ^j-n-2 )= (0, 0, 1),

^j= _,

где a^j - значение на информационном входе на j-м такте вычислительного модуля;

^jи^j - значения соответственно на первом и втором настроечных входах на j-м такте вычислительного модуля;

A^j+1 - значение на выходе на (j+1)-м такте вычислительного модуля.

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

U^j+2n+2= U^j ;

V^j+2n+2= V^j;

W^j+2n+2= ^j;

( где U^j, V^j, ^j и _j - значение соответственно на первом, втором, третьем и четвертом настроечных входах на j-м такте вычислительного модуля, U^j, V^j, W^j и E^j - значения соответственно на первом, втором, третьем и четвертом настроечных выходах на j-м такте вычислительного модуля,

где f^j= d^j-1-b^j-1 c^j-1, если ₅^j-1= (0, 1, 0, 0)V

₆^j-1 = (0, 0, 1, 0) V ₇^j-1 = (0, 0, 0, 0, 1),

b^j-1= d^j-2/d^j-n-4, если ₂^j-2= (1, 1, 0),

, и 0





,

_Pj ₌ , где

^j₁= ^j₁⁺¹= (u^j, v^j, ^j)= (1,1,1), ,

^j₂= ^j₂⁺¹= (u^j, v^j, ^j)= (1,1,0), ,

^j₃= ^j₃⁺¹= (u^j, v^j, ^j)= (1,0,0), ,

^j₄= ^j₄⁺¹= (u^j, ^j)= (0,1), ,

^j₅= ^j₅⁺¹= (u^j, v^j, ^j,^j)= (0,1,0,0), ,

^j₆= ^j₆⁺¹= (u^j, v^j, ^j,^j)= (0,0,1,0), ,

^j₇= ^j₇⁺¹= (u^j, v^j, ^j,^j,^j-n-1)= (0,0,0,0,1), , где a^j - значение на информационном входе на j-м такте вычислительного модуля;

A^j+1 - значение на информационном выходе на (j+1)-м такте вычислительного модуля.

Рассмотрим работу вычислительных модулей второго и первого типа.

Вычислительный модуль 10 второго типа работает в четырех режимах, которые задаются комбинацией управляющих сигналов и , подаваемых соответственно на входы 14 и1 5.

В первом режиме ( , )= (1, 1), на выходе элемента И 35 формируется единичный сигнал, который открывает элемент И 32. При этом через элементы И 32 и ИЛИ 42 тактовый импульс подается на синхровод регистра 18, что обеспечивает запись в регистр 18 элемента а, подаваемого на вход 13. Узел 17 задержки содержит n+1 последовательно соединенных регистров. Информация из регистров 17_i(i= ) записывается в регистры 17_i+1. Триггер 21 устанавливается в единичное состояние, единичный сигнал с выхода которого через элемент ИЛИ 45 открывает элементы И группы 29. Содержимое регистра 17_n через элементы И группы 29 и ИЛИ группы 40 выдается на выход 49 вычислительного модуля 10. В триггерах 20_j (j= ) происходит циклическая перезапись информации (элемент И 39 открыт).

Во втором режиме ( , )= (1, 0), на выходе элемента И 36 формируетя единичный сигнал, который открывает элементы И 31, 34 и подается на входы элементов И группы 26. Входной элемент а, подаваемый на вход 13, сравнивается по модулю с содержимым регистра 18 в узле 19 сравнения. Если < Рег. 18 > a, то на выходе узла 19 сравнения формируется нулевой сигнал, который открывает элементы И группы 25.

Входной элемент а через элементы И группы 25 и или группы 41 записывается в регистр 17₁. Содержимое регистров 17_i (i= ) записывается в регистры 17_i+1. Кроме того, нулевой сигнал с выхода узла 19 сравнения через элементы И 34 и ИЛИ 43 записывается в триггер 201. Содержимое триггеров 20_i (i= ) записывается в триггеры 20_i+1.

Если < Рег. 18 > < a, то на выходе узла 19 сравнения формируется единичный сигнал, который подается на входы элементов И 31 и 34 и элементов И группы 26. Содержимое регистра 18 через элементы И группы 26 и ИЛИ группы 41 записывается в регистр 17₁. Входное данное а записывается в регистр 18 (тактовый импульс через элементы И 31 и ИЛИ 42 подается на синхровход регистра 18). Единичный сигнал с выхода узла 19 сравнения через элементы И 34 и ИЛИ 43 записывается в триггер 20₁. Триггер 22 устанавливается в единичное состояние, что обеспечивает выдачу содержимого регистра 17_n+1 на выход 49.

В третьем режиме ( , )= (0, 0). На выходе элемента И 38 формируется единичный сигнал, который подается на вход элемента И 33 и на входы элементов И групп 27 и 30. Если триггер 20_n+1 находится в единичном состоянии, то элемент И 33 открывается и разрешается запись входного данного а в регистр 18. Кроме того, открываются элементы И группы 27 и через элементы И группы 27 и ИЛИ группы 41 содержимое регистра 18 записывается в регистр 17₁. Информация из регистров 17_i(i= ) записывается в регистры 17_i+1. Если триггер 20_n+1 находится в нулевом состоянии, то на выходе элемента НЕ 48₂ формируется единичный сигнал, который открывает элементы И группы 30. Входное данное записывается в регистр 17₁ через элементы И групп 30 и ИЛИ группы 41. На выход 49 вычислительного модуля 10 выдается содержимое регистра 17_n+1.

В четвертом режиме ( , )= (0, 1). При этом на выходе элемента И 37 формируется единичный сигнал, который через элемент ИЛИ 44 открывает элемент И 39, что обеспечивает циклическую запись информации в триггерах 20_i (i= ). Информация из регистров 17_i (i= ) записывается в регистры 17_i+1. Триггер 23 устанавливается в единичное состояние и открываются элементы И группы 28. Содержимое регистра 18 выдается через элементы И группы 28 и ИЛИ группы 40 на выход 49 вычислительного модуля.

Вычислительный модуль 11 первого типа работает в семи режимах, которые задаются комбинацией внешних управляющих сигналов u, v, , и внутреннего управляющего сигнала , который формируется только в седьмом режиме работы в результате сравнения чисел по модулю на выходе 132 узла сравнения в коммутаторе 66 (фиг. 5). Соответствующие значения управляющих сигналов u^j, v^j, ^j, ^j и ^j на j-м такте определяют управляющие сигналы _i^j+1= _i^j= (u^j, v^j, ^j, ^j, ^j), (i= 1,7), где i - номер режима работы, которые подаются на соответствующие логические элементы вычислительного модуля 11. Причем управляющий сигнал _i^j обеспечивает запись данных в регистр или триггер на j-м такте, а управляющий сигнал _i^j+1 - на (j+1)-м такте. На вход 55 постоянно подается единичный сигнал.

Управляющие сигналы u, v, и подаются соответственно на входы 51, 52, 53 и 54 и выдаются соответственно на выходы 116, 117, 118 и 119. Причем сигналы u, v и задерживаются на 2n+2 тактов соответственно триггерами 74_i, 75i_, 76i (i= ) соответствующих узлов 74, 75 и 76 задержки, а сигнл задерживается на n тактов триггерами 57_i (i= ) узла 57 задержки.

Первый режим работы вычислительного модуля 11 задается управляющими сигналами ₁^j= (u^j, v^j, ^j)= (1, 1, 1) (значение управляющего сигнала на режим работы не влияет). На выходе элемента И 95 формируется единичный сигнал ₁, на выходе элемента НЕ 111 - нулевой сигнал , которые подаются соответственно на входы элементов И групп 87, 88 и элемента И 94. При этом входной элемент a^j, подаваемый на вход 50, записывается в регистр 60₁ узла 60 задержки на n+1 тактов через элементы И группы 87 и ИЛИ группы 106. Информация из регистров 60_i (i= ) записывается в регистры 60_i+1. Аналогисчно информация записывается и в триггеры 57_i (i= ) и 61_i (i= ).

Второй режим работы задается управляющими сигналами ^j₂⁺¹= ^j₂= (1,1,0) . Управляющие сигналы ₂^j и ₂^j+1 формируются соответственно на выходах элемента И 96 и триггера 67. Управляющий сигнал ₂^j подается на входы элементов И групп 77 и 79. Управляющий сигнал ₂^j+1 подается на вход элемента И 89, обеспечивая прохождение тактового импульса для записи информации в регистр 61 на (j+1)-м такт. Входной элемент a^j через элементы И группы 77 и ИЛИ группы 102 записывается в регистр 58₁ узла 58 задержки на n тактов. Содержимое регистров 58_i (i= ) записывается в регистры 58_i+1. На выходе делителя 63 формируется значение a^j/a^j-1, которое на (j+1)-м такте записывается в регистр 61. Управляющий сигнал ^j записывается в триггер 57₁. Информация в регистрах 60_i (i= ) циклически переписывается. Аналогично записывается информация и в триггерах 57_i (i= ) и 62_i (i= ).

Третий режим работы определяется управляющими сигналами ₃^j= ₃^j+1= (u^j, v^j, ^j)= (1,0,0). Уп-равляющие сигналы ₃^jи ₃^j+1 формируются соответственно на выходах элемента И 97 и триггера 68. Сигнал ₃^jподается на входы элементов И групп 78, 79 и на вход элемента И 91. Сигнал ₃^j+1 подается на вход элементов И группы 86, а сигнал ₃^j+1 - на вход элементов И группы 80. При этом в регистр 58₁ записывается содержимое регистра 61 через элементы И 78 и ИЛИ группы 102. Содержимое регистра 59 через элементы И группы 86 и ИЛИ группы 104 выдается на (j+1)-м такте на выход 115. Единичный сигнал, подаваемый на вход 55, через элементы И 91 и ИЛИ 107 устанавливает триггер 57₁ в единичное состояние. Информация из триггера 57_i (i= ) записывается в триггер 57_i+1. Аналогично информация циклически переписывается в регистрах 60_i(i= ) и триггерах 62_i (i= ).

В четвертом режиме работы подаются управляющие сигналы ₄^j= ₄^j+1= (u^j, ^j)= (0,1) (сигналы u^jи^jна режим работы не влияют). На выходах элемента И 98 и триггера 69 формируются соответственно управляющие сигналы ₄^jи₄^j+1. Управляющий сигнал ₄^j подается на входы элементов И группы 77, управляющий сигнал ₄^j+1 - на входы элементов И группы 81. При этом входной элемент a^j записывается в регистр 58₁. На выходе умножителя 64 формируется произведение <Рег. 60₁><Рег. 61>, которое подается на вход вычитателя 65. На второй вход последнего подается содержимое регистра 58₁ и на его выходе формируется значение <Рег. 58₁>-<Рег. 60₁><<Рег. 61>, которое на (j+1)-м такте через элементы И группы 81 и ИЛИ группы 103 записывается в регистр 58₂. Информация из регистров 58_i (i= ) записывается в регистры 58_i+1. Содержимое регистра 58_n через элементы И группы 80 и ИЛИ группы 104 ( ₃= 1) выдается на выход 115. Аналогично информация записывается в регистры 60_i (i= ) и триггеры 57_i (i= ) и 62_i (i= ).

Пятый режим работы задается управляющими сигналами ₅^j= ₅^j+!= (u^j, v^j, ^j, ^j)= (0,1,0,0, ). На выходах элемента И 99 и триггера 70 формируется соответственно сигналы ₅^j и ₅^j+1. Управляющий сигнал ₅^j подается на входы элементов И группы 77 При этом в регистр 58₁записывается входной элемент a^j, на выходе вычитателя 65 формируется значение <Рег. 58₁>-<Рег. 60₁><Рег. 61>, которое на (j+1)-м такте по управляющему сигналу ₅^j+1 через элементы И группы 83 и ИЛИ группы 106 записывается в регистр 59 (элемент И 90 открыт и тактовый импульс подается на синхровход регистра 59). На выход 115 выдается содержимое регистра 58_n ( = 1). Аналогично осуществляется запись информации в регистры 58_i (i= ), 60_i (i= ) и триггеры 57_i (i= ) и 62_i(i= ).

В шестом режиме работы подаются управляющие сигналы ₆^j= ₆^j+1= (u^j, v^j, ^j, ^j)= (0, 0, 1, 0). На выходе элемента И 100 формируется сигнал ₆^j, на выходе триггера 71 - сигнал ₆^j+1. Управляющий сигнал ₅^j+1 подается на входы элементов И группы 84 и на вход элемента И 90. Сигнал подается на входы элементов И группы 77. Сигнал ₆^j подается на входы элементов И групп 82, 85 и на входы элементов И 90 и 93. При этом в регистр 58₁ записывается входной элемент a^j, на выходе вычитателя 65 формируется значение A= <Рег. 58₁>-<Рег. 60₁><Рег. 61> которое подается на первый вход коммутатора 66, на второй вход которого подается содержимое B регистра 59. Если B A , то на первом выходе коммутатора 66 выдается значение A, на втором выходе - значение B и на третьем выходе - сигнал ^j= 0. На (j+1)-м такте по сигналу ₆^j+1 значение A записывается через элементы И группы 82 и ИЛИ группы 103 в регистр 58₂, значение B записывается через элементы И группы 85 и группы ИЛИ 105 в регистр 59 и сигнал ^j = 0 - через элементы И 93 и ИЛИ 108 в триггер 62₁. Если B < A , то на первом выходе коммутатора 66 выдается значение B, на втором выходе - значение A и на третьем выходе - сигнал ^j= 1. На (j+1)-м такте по сигналу ₆^j+1значение B записывается в регистр 58₂, значение A - в регистр 59 и сигнал = 1 - в триггер 62₁. Содержимое 58_n выдается на выход 115 ( = 1). Аналогично информация записывается в регистры 58_i (i= ), 60_i(i= ) и триггеры 57_i (i= ), 62_i (i= ).

Седьмой режим работы определяется управляющими сигналами ₇^j= ₇^j+1= (u^j, v^j, ^j, ^j, ^j)= = (0,0,0,0,1). Сигнал ₇^j формируется на выходе элемента И 101, сигнал ₇^j+1 - на выходе триггера 72, сигнал ₇^j+1- на выходе триггера 73. Сигнал ₇^j подается на входы элементов И группы 77, сигнал ₇^j+1 - на входы элементов И групп 83 и 84 и на вход элемента И 90, сигнал ₇^j+1- на входы элементов И группы 81. При этом в регистр 58₁ записывается элемент aⁱ, на выходе вычитателя 65 формируется значение A= <Рег. 58₁>-<Рег. 60₁><Рег. 61> содержимое регистров 58_i (i= ) записывается в регистры 58_i+1, содержимое регистра 58_n выдается на выход 115 ( = 1). Если триггер 61_n+1 в нулевом состоянии ( 0), то = 1 и значение A записывается в регистр 58₂ на (j+1)-м такте через элементы И группы 81 и ИЛИ группы 103. Если триггер 61_n+1 в единичном состоянии, то ₇^j+1= 1, значение A записывается в регистры 59 на (j+1)-м такте через элементы И группы 84 и ИЛИ группы 105, содержимое B регистра 59 через элементы И группы 83 и ИЛИ группы 103 записывается в регистр 58₂.

Коммутатор 66 (фиг. 5) работает следующим образом. На входы 119 и 120 подаются соответственно значения A и B. Если B A , то на выходе узла 122 сравнения формируется единичный сигнал, на выходе элемента НЕ 129 - нулевой сигнал ( = 0), элементы И групп 125 и 126 закрыты, а групп 123 и 124 открыты, значение A через элементы И группы 123 и ИЛИ группы 127 подается на выход 130, а значение B через элементы И группы 124 и ИЛИ группы 128 - на выход 131. Если B < A , то на выходе узла 122 сравнения формируется нулевой сигнал, элементы И групп 123 и 124 закрыты, а элементы И групп 126 и ИЛИ группы 128 подается на выход 131, а значение B через элементы И группы 125 и ИЛИ группы 127 на выход 130 и = 1.

В основу работы устройства для решения систем линейных алгебраических уравнений вида A₁ X= A₂, где A₁= (a_ij), i, j= , A₂= (a_ij), i= , j= , X= (x_ij), i= , j= , положен метод Гаусса-Жордана с частичным выбором ведущего элемента по столбцам матрицы в виде следующих рекуррентных соотношений:

b_1j= a_1j, j= , ,

i= :

если b a , то a^(o)_ij= a_ij, j= , иначе a^(o)_ij= b_1j,b_1j= a_ij, j= ; a^(o)_1j= b_1j, j=

k = :

a^(k_ik⁾= a^(k_ik^-1), i= ;

a^(k_kj⁾= a^(k_kj^-1)/a^(k_kk⁾, j= ;

b^(k)_k+1,j= a^(k-1)_K+1,j-a^(k)_k+1,ka^(k_kj⁾, j= ;

i =

c^(k_ij⁾= a^(k_ij⁺¹⁾-a^(k_ik⁾a^(k_kj⁾, если b то a^(k_ij⁾ = C^(k_ij⁾, j =

иначе a^(k_ij⁾= b^(k)_k+1,j, b^(k)_k+1,j= C_ij, j= ;

a^(k)_k+1,j= b^(k)_k+1,j, j= ;

a^(k_ij⁾= a^(k_ij^-1)-a^(k_ik⁾a^(k_kj⁾,i= , j= (эта операция при k= 1 не выполняется),

a^(k)_n+k,j= a^(k_kj⁾, j= ;

a^(k)_n+1,j= b^(k)_k+1j, j= ;

k = :

a^(k_kk⁾= a^(k_kk^-1);

a^(k_kj⁾= a^(k_kj^-1)/a^(k_kk⁾, j= ;

a^(k_ik⁾= a^(k_ik^-1), i= ;

a^(k_ij⁾= a^(k_ji^-1)-a^(k_ik⁾a^(k_kj⁾, i= , j= ;

a^(k)_n+k,j= a^(k_kj⁾, j= ;

x_ij= a⁽ⁿ⁾_n+i,n+j, i= , j=

Рассмотрим работу устройства.

На вход 1 устройства подаются элементы a_ij в моменты времени ta_ij= i+(n+1)j-n-1, i= , j= . На входы 5 и 6 подаются соответственно управляющие сигналы и , принимающие значение 0 или 1. Первый режим работы вычислительного модуля 10 задается комбинацией сигналов ₁= (, )= (1,1), второй режим - ₂(1, 0), третий режим - ₃= (0, 0) и четвертый режим - ₄= (0, 1). Организация ввода управляющих сигналов _i^t (i= ), где t - номер такта, следующая:

(вторая группа повторяется n+m-2 раз, т. е. всего подается одна первая группа и n+m-1 вторых групп).

На входы 2, 3 и 4 подаются соответственно управляющие сигналы u, v и , принимающие значение 0 или 1. На входы 2, 3 и 4 подаются следующие комбинации сигналов u, v и : ₁= (u, v, )= (1, 1, 1), ₂= (1, 1, 0), ₃= (0, 1, 0), ₄= (0, 0, 1), ₅ = (1, 0, 0) и ₆ = (0, 0, 0). Организация ввода управляющих сигналов _i (i= ) следующая:



. . . (третья группа повторяется n+m-3 раз, т. е. всего подается одна первая группа, одна вторая группа и n+m-2 третьих групп). На вход 7 постоянно подается нулевой сигнал, на вход 8 - единичный сигнал.

Элементы xij формируются на выходе 12 устройства в моменты времени

t_xij= 2n(n+1)+i+j(n+1)-1.

Последний элемент x_nm формируется на (2n²+m(n+1)+3n-1)-м такте. Период ввода элементов a_ij очередной задачи решения систем линейных алгебраических уравнений равен (n+1)(n+m) тактом.

Рассмотрим работу устройства для случая n= 3 и m= 1 (фиг. 2). Пусть требуется решисть систему линейных алгебраических уравнений вида



Входные и выходные данные, состояния регистров и триггеров вычислительных модулей 10, 11₁, 11₂ и 11₃ приведены в табл. 1-4.

Вчислительный модуль 10 обеспечивает выбор ведущего элемента по столбцам матрицы, т. е. перемещает строки так, чтобы строка, содержащая максимальный элемент первого столбца, была первой. С первого по третий такты выбирается ведущий элемент (а_макс= а₃₁= 2), который записывается в регистр 18, и на третьем такте в триггер 201 записывается значение = 1. На последующих тактах в соответствии с приведенным алгоритмом работы вычислительного модуля 10 происходит перемещение местами элементов первой и третьей строк исходной матрицы. На выходе 49 формируются элементы исходной матрицы в моменты времени

(i= , j= ).

В вычислительном модуле 11₁ с пятого по седьмой такты в регистры 60_i (i= 1, n+1) записываются элементы a^(o)_i1 (i= ), которые на последующих тактах циклически переписываются. На девятом такте формируется элемент a⁽¹⁾₄₂= a⁽¹⁾₁₂= a^(o)₁₂/a^(o)₁₁= 3/2, который записывается на девятом такте в регистр 61. На десятом такте формируется элемент a⁽¹⁾₂₂= a^(o)₂₂-a^(o)₂₁ a⁽¹⁾₁₂= 2-0 3/2= 2, который записывается на одиннадцатом такте в регистр 59. На одиннадцатом такте формируется элемент a⁽¹⁾₃₂= a^(o)₃₂-a^(o)₃₁ a⁽¹⁾₁₂= 2-1 3/2= 1/2, который записывается в регистр 58₂ на двенадцатом такте, и в триггер записывается сигнал = 0, так как a<a. На тринадцатом такте в регистр 58₂ записывается элемент а⁽¹⁾₄₂= 3/2. Элементы а⁽¹⁾₂₂, а⁽¹⁾₃₂ и а⁽¹⁾₄₂ выдаются на выход 115 соответственно на двенадцатом, тринадцатом и четырнадцатом тактах. На тринадцатом такте формируется элемент а⁽¹⁾₄₃= а⁽¹⁾₁₃= а^(о)₁₃/a^(o)₁₁= 0/2= 0, который на четырнадцатом такте записывается в регистр 61. На четырнадцатом такте формируется элемент a⁽¹⁾₂₃= а^(о)₂₃-а^(о)₂₁ а⁽¹⁾₁₃= 1-0 0= 1, который на пятнадцатом такте записывается в регистр 59. На пятнадцатом такте формируется элемент а⁽¹⁾₃₃= а^(о)₃₃-а^(о)₃₁ а^(о)₁₃= 0-1 0= 0, который на шестнадцатом такте записывается в регистр 58₂, так как триггер 62₄ находится в нулевом состоянии ( = 0). На семнадцатом такте элемент а⁽¹⁾₄₃= 0 записывается в регистр 58₁. Элементы а⁽¹⁾₂₃, а⁽¹⁾₃₃ и а⁽¹⁾₄₃выдаются на выход 115 соответственно на шестнадцатом, семнадцатом и восемнадцатом тактах. Аналогично формируются элемет a⁽¹⁾₄₄= a⁽¹⁾₁₄= a^(o)₁₄/a^(o)₁₁= 4/2= 2 (записывается в регистр 61 на восемнадцатом такте), элемент a⁽¹⁾₂₄= a^(o)₂₄-a^(o)₂₁ a⁽¹⁾₁₄= 5-0 2= 5 (записывается в регистр 58₂ на двадцатом такте), элемент a⁽¹⁾₃₄= a^(o)₃₄-a^(o)₃₁ a⁽¹⁾₁₄= 3-1 2= 1 (записывается в регистр 58₂ на двадцать первом такте). Элемент а⁽¹⁾₄₄= 2 записывается в регистр 58₁ на двадцатом такте. Элементы а⁽¹⁾₂₄, а⁽¹⁾₃₄ и а⁽¹⁾₄₄ выдаются на выход 115 соответственно на двадцатом, двадцать первом и двадцать втором тактах.

В вычислительном модуле 11₂ с тринадцатого по пятнадцатый такты записываются в регистры 60_i (i= ) элементы a⁽¹⁾_i2 (i= ), которые на последующих тактах циклически переписываются. На семнадцатом такте формируется элемент а⁽²⁾₅₃= а⁽²⁾₂₃= а⁽¹⁾₂₃/а⁽¹⁾₂₂= 1/2, который на восемнадцатом такте записывается в регистр 61. На восемнадцатом такте формируется элемент а⁽²⁾₃₃= а⁽¹⁾₃₃-а⁽¹⁾₃₂ а⁽²⁾₂₃= -1/4, который записывается в регистр 59 на девятнадцатом такте. Элемент а⁽²⁾₄₃= а⁽¹⁾₄₃-а⁽¹⁾₄₂ а⁽²⁾₂₃= 0-3/2 1/2= -3/4 формируется на девятнадцатом такте, который записывается в регистр 58₂ на двадцатом такте. Также на двадцатом такте в регистр 58₁ записывается элемент а⁽²⁾₅₃= 1/2. Элементы а⁽²⁾₃₃, а⁽²⁾₄₃ и а⁽²⁾₅₃ задаются на выход 115 соответственно на двадцатом, двадцать первом и двадцать втором тактах. На двадцать первом такте формируется элемент а⁽²⁾₅₄= а⁽²⁾₂₄-а⁽¹⁾₂₄а⁽¹⁾₂₂= 5/2, который записывается на двадцать втором такте в регистр 61. На двадцать втором такте формируется элемент а⁽²⁾₃₄= а⁽¹⁾₃₄-а⁽¹⁾₃₂ а⁽²⁾₂₄= 1-1/2 5/2= -1/4 , который записывается в регистр 59 на двадцать третьем такте. Элемент а⁽²⁾₄₄= а⁽¹⁾₄₄-а⁽¹⁾₄₂ а⁽²⁾₂₄= -7/4 формируется на двадцать третьем такте и на двадцать четвертом такте записывается в регистр 58₂. Элемент а⁽²⁾₅₄ записывается на двадцать четвертом такте в регистр 58₁. Элементы а⁽²⁾₃₄, а⁽²⁾₄₄ и а⁽²⁾₅₄ выдаются на выход 115 соответственно на двадцать четвертом, двадцать пятом и двадцать шестом тактах. Состояние триггера 62₄ (значение ) на режим работы вычислительного модуля 11₂ не влияет, так как комбинация управляющих сигналов (u, v, , )= (0, 0, 0, 0) на входах 51, 52, 53 и 54 соответственно отсутствует.

В вычислительном модуле 11₃ двадцать первого по двадцать третий такты в регистры 60_i (i= ) записываются элементы а⁽²⁾₃₃, а⁽²⁾₄₃ и а⁽²⁾₅₃, которые на последующих тактах циклически переписываются. На двадцать пятом такте формируется элемент а⁽³⁾₆₄= а⁽³⁾₃₄= а⁽²⁾₃₄/а⁽²⁾₃₃= 1, который записывается в регистр 61 на двадцать шестом такте. Элемент а⁽³⁾₄₄= а⁽²⁾₄₄-а⁽²⁾₄₃ а⁽³⁾₃₄= -7/4+3/4 1= -1 формируется на двадцать шестом такте и записывается в регистр 58₂ на двадцать сельмом такте. На двадцать седьмом такте формируется элемент a⁽³⁾₅₄= a⁽²⁾₅₄-a⁽²⁾₅₃ a⁽²⁾₃₄= 5/2-1/2 1= 2, который записывается на двадцать восьмом такте в регистр 58₂. Состояние триггера 62₄ (значение ) не влияет на режим работы вычислительного модуля 11₃ (отсутствует комбинация входных сигналов (u, v, , )= = ( 0, 0, 0, 0). Элементы х₁= а⁽³⁾₄₄= -1, х₂= а⁽³⁾₅₄= 2 и х₃= а⁽³⁾₆₄= 1 выдаются на выход 115 соответственно на двадцать восьмом, двадцать девятом и традцатом тактах.

Таким образом, предлагаемое устройство по сравнению с прототипом обладает более высокой точностью вычисления за счет возможности выбора ведущего элемента. В прототипе не выбирается ведущий элемент и возможны случаи давления на нуль или числа, близкие по величине к нулю. Это приводит к неработоспособности прототипа.