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

(19 51)5. 0 06 Е 15/324 ОПИСАНИЕ ИЗОБРЕТК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(71) Ленинградский институт авиационного ,. приборостроения(56) Авторское свидетельство СССР В 1179367, кл. 6 06 Р 15/324, 1983.Авторское свидетельство СССР Ь 1324035, кл. 6 06 Р 15/32, 1986, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ(57) Изобретение относится к цифровой вычислительной технике, в частности к специализированным процессорам. Цель изобретения - расширение класса решаемых задач, Устройство содержит матрицу размером пп регистров 1 для хранения коэффициентов (и - порядок систем), матрицы размером пхп первых 9 и вторых 10 групп элементов И, и сумматоров 4, и сдвиговых регистров 3 невяэок для хранения результатов итераций, и сумматоров 15 неизвестных и и сдвиговых регистров 2 неизвестных для формирования решения системы, генератор 5 импульсов, счетчик 11, первый 13 и второй 14 элементы И, позволяющие переходить к вычислению очередных цифр неизвестных при уменьшении значений невязок в сдвиговых регистрах 16 на величину, определяемую и первыми 22 и и вторыми 20 группами элементов, и группами 21 элементов ИЛИ, сумматором 17 старших разрядов, регистром 19 старших разрядов и регистром 18Я порядка системы. 1 ил.Изобретение относится к вычислительной технике и может быть применено в системах регулирования, управляющее воздействие в которых определяется путем решения систем линейных алгебраических уравнений, а также при построении специализированных и проблемно-ориентированных процессоров.Цель изобретения - расширение класса решаемых систем уравнений.На чертеже представлена структурная схема устройства.Устройство содержит матрицу пкп регистров 1 коэффициентов, и сдвиговых регистров 2 неизвестных, п сдвиговых регистров 3 невяэок, п сумматоров 4, генератор 5 импульсов, вход б коэффициентов устройства, вход 7 невязок устройства, выход 8 устройства, первую матрицу пкп групп элементов И 9, вторую матрицу пп групп элементов И 10, счетчик 11, вход 12 начальной установки и запуска устройства, первый элемент И 13, второй элемент И 14, и сумматоров 15 неизвестных, и сдвиговых регистров 16, сумматор 17 старших разрядсв, регистр 18 порядка системы, регистр 1 ь старших разрядов, вторую группу элементов И 20; группу п элементов ИЛИ 21, первую группу элементов И 22, вход 23 порядка системы устройства.Алгоритм работы устройства для решения систем алгебраических уравнений вида АХ - В порядка п основан на методе минимизации ноомы вектора невязок ЬХ 1" )РВанф2 лй где 9выбирается так О,если 0,5 е", Ъ ;1, если 0,5 е" 1 . еслиф Ъ)ы 2,тоО,если 0,75 е 1 ;к - 1)1, если 0,75 е," 1Целое п)к такое, что2г "я"Иго; Ф=ъ+2 си 4 к- (оси(ск 4с к) ск), 2 ик1, и;Зс 0,1,2 Начальные условияе 1) " -Ь: х-О,Разряды в сдвиговом регистре обозначеныследующим образом;1,2,3,где 1 - знаковый разряд;2 - первый разряд;3 - второй разрядУстройство работает следующим обра 1 О зомПепед началом вычислений в регистры1 коэффициентов по входу 6 коэффициентовзаписываются коэффициенты системы уравнений, по входу 7 невязок всдвиговые реги 15 стры 3 невязок и сдвиговые регистры 16записываются свободные члены системы, ав регистр 18 порядка системы по входу 23порядка записывается число и/г, где и -порядок системы. После записи по входу 12начальной установки и запус а в счетчик 11информации его выход переноса обнуляется, что позволяет запуститься генератору 5импульсов, Каждым импульсом с прямоговыхода генератора 5 импульсов синхрони 25 зируется запись в сдвиговые регистры 3 невяэок и сдвиговые регистры 16 значенийрезультатов итераций с выходов соответствующих сумматоров 4, на входы которыхподаются со сдвиговых регистров 16 пред 30 ыдущие невязки, При помощи сумматора 17старших разрядов и регистра 19 старшихразрядов сравнивается количество сдвиговых регистров 3 невязок, имеющих ненулевые старшие разряды. Если это количество35 не превосходит и/г, то с помощью схемы,построенной на группах элементов И 20, 22,ИЛИ 21, на сумматоры 4 через группы элементов И 9, 10 поступают коэфФициентыпри наличии единичных значений в двух40 старших значащих разрядах сдвиговых регистров 16. Если количество сдвиговых регистров 3 невязок, имеющих ненулевыестаршие разряды, превосходит п/г, то насумматоры 4 коэффициенты поступают та 45 ким же образом, но при наличии единичногозначения в одном старшем значащем разряде сдвиговых регистров 16. При условии, чтовсе старшие разряды в сдвиговых регистрах16 обнулены, импульсом с инверсного выхо 50 да генератора 5 импульсов через второйэлемент И 14 происходит сдвиг в сдвиговыхрегистрах 3 невязок и сдвиговых регистрах,1 б и добавление по счетному входу счетчика11 к его содержимому и 1"; а импульсом с55 прямого выхода через первый элемент И 13- сдвиг в сдвиговых регистрах 2 неизвестных, При,этом на первые входы сумматоров,15 неизвестных из сдвиговых регистров 2неизвестных подаются значения предыду 1689961 610 15 20 щих приближений неизвестных, а на вторые входы сумматоров 15 неизвестных подается приращение "1", если число сдвиговых регистров 3 с нулевыми старшими разрядами больше и/г и два старших значащих разряда сдвиговых регистров 16- единичные, либо один старший разряд единичный, в противном случае, Полученные новые приближения неизвестных записываются в сдвиговые регистры 2 неизвестных и при обнулении первых разрядов всех сдвиговых регистров 16 происходит сдвиг влево на один разряд содержимого сдвиговых регистров 2 неизвестных,После окончания вычислений, когда на выходе переноса счетчика 11 появится единичное значение, блокирующее работу генератора 5 импульсов, решение системы считывается из устройства на выход 8,Формула изобретения Устройство для решения систем линейных алгебраических уравнений, содержащее матрицу п,е регистров коэффициентов, п сдвиговых регистров невяэок, и сдвиговых регистров неизвестных, п сумматоров, генератор импульсов, счетчик, первую и вторую матрицы Ю групп элементов И, и сумматоров неизвестных, первый и второй элементы И, причем первые входы элементов И (1, 1)-х групп первой и второй матриц соединены соответственно с прямыми и инверсными выходами (1,-го регистра коэффициента матрицы (1, ) - 1, й) информационный вход 1-го сдвигового регистра невязок соединен с выходом 1-го (1 = сумматора, первые входы которого соединены с выходами элементов И групп )-й строки первой и второй матриц, выход)-го сумматора неизвестного соединен с информационным входом )-го сдвигового регистра неизвестного, выход которого соединен с первым входом )-го сумматора неизвестного, прямой выход генератора импульсов соединен с входами записи всех сдвиговых регистров невязок и первым входом первого элемента И, выход которого соединен с входами сдвига всех сдвиговых регистров неизвестных, выходы которых яв щются выходом устройства, ин.версный выход генератора импульсов соединен с первым входом второго элемента И, выход которого соединен с входами сдвига 25 30 35 40 45 50 всех сдвиговых регистров неаязок и счетным входом счетчика, выход переполнения которого соединен с входом блокировки генератора импульсов, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач, в него введены сумматор старших разрядов, регистр старших разрядов, первая и вторая группы и элементов И, группа п элементов ИЛИ, и сдвиговых регистров,регистр порядка системы, причем прямые выходы старших значащих разрядов )-х 0- 1, и) сдвиговых регистров невязк и выход регистра порядка системы соединены соответственно с входами сумматора старших разрядов, выход которого соединен с информационным входом регистра старших разрядов, пряь,ой и инверсный выходы знакового разряда которого соединены с первыми входами соответственно элементов ИЛИ группы и элементов И первой группы,выходы элементов И первой группы соединены с вторыми входами элементов ИЛИ группы, выходы которых соединены с первыми входами элементов И второй группы, выходы которых соединены с младшими разрядами вторых входов соответствующих сумматоров неизвестных и с вторыми входами элементов И групп соответствующего столбца первой и второй матриц, прямые выходы первыхразрядов сдвиговых регистров соединены с вторыми входами элементов И второй группы, а прямые выходы вторых разрядов сдвиговых регистров соединены с вторыми входами соответствующих элементов И первой группы, третьи входы элементов И групп первой и второй матриц соединены соответственно с прямыми и инверсными выходами знаковых разрядов сдвиговых регистров, выходы которых соединены с вторыми входами сумматоров, выходы котооых соединены с информационными входами сдвиговых регистров, инверсные выходы первых разрядов которых соединены с входами первого и второго элементов И, прямой выход генератора импульсов соединен с входами записи сдвиговых регистров, выход второго. элемента И соединен с входами сдвига . сдвиговых регистров, инверсные выходы знаковых разрядов которых соединены со знаковыми разрядами вторых входов соответствующих сумматоров неизвестных.