Цифровое устройство для решения системы линейных уравнений Советский патент 1980 года по МПК G06F17/16 

1 .- Изобретение относится к области цифровой вычислительной техники и может быть использовано ггри ггостроении специализированных и клавишных , .вычислительных махчин, предназначенных для решения задач методами матричной алгебры. Известны устройства , содержащие схемы набора элементов матриц, арифметическое устройство, генератор импульсов, программное и коммутирующее устройство, блок управления, уст ройство вывода и индикации, блоки установки размерности матрицы, определения знаков членов определителей, равных нулю, элементы ИЛИ и И 1. Однако в этих устройствах процесс вычисления заканчивается на стадии раскрытия и вычисления определителя, их функциональные возможности ограни чены, они имеют малое быстродействие вычисления. Наиболее близким по технической сущности к предложенному является цифровое устройство для решения системы линейных уравнений, содержсцдее первую и вторую матрицу решающих бло;ков, каждая из которых содержит п решающих блоков/ арифметический блок блок управления блок вывода и индикации, два программных олока, блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввода коэффициеНтов, два элемента ИЛИ. Каждый решающий блок содержит два элемента И, элемент НЕ, регистр и элемент ИЛИ. Каждый программный блок содержит счетчик столбцов и счетчик строк 2 . Однако это устройство требует больших аппаратурных затрат при решении системы линейных уравнений высокого порядка. : Цель изобретения - упрощение устройства. . Это достигается введением дополнительных элементов в цифро.вое устройство для решения системы линейных уравнений, содержащее первую и вторую матрицы решающих блоков, арифметический блок, 6.ЛОК управления, блок индикации, первый и BTopoi программные .блоки, блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввода коэффициентов, элементы ИЛИ, причем первый выход арифметического блока соединен с.первым входом блока индикации. Первый вход блока управления соединен со вторым выходом арифметического блока, педвый вход котЬрого подключен к перврму выходу блока управления, второй

и третий ёыходы которого соединены соответственно с первыми управляющими входами ка)(дого решающего блока первой и второй матриц. Четвертый и пятый выходы блока управления соединены соответственно со вторыми управляющими входами каждого решаюше го блока первой и второй матриц. Тре.тий и.четвертый выходы ариЛметйческого блока подключенысортветственно к п-ёрвым информацйоШым входам каждого решающего, блока первой и второй матриц. Второй и третий входы арифметического блока соединены соответственно через первый и второй элемен ты ИЛИ с выходами решающих блоков первой и второй матриц, шестой выход блока управленйя соединен с пер1вым и вторым входами первого программного .блока, первый и второй выходы которого подключены ко BTopof4y и третьему .входу блока индикации. Второй информацйонный вхой каждого решающего блока первой матрицы подключен к соотвотствуюшему выходу из первой группы выходов второго программного блока. Трётий информационный вход каждого решающего блока первой матрицы подключен к соответствукниему выходу из второй группы выходов второго программного блока, первый и BTOpcft ьах6ды которого соединены соответственно с первым и вторым входами блока, сравнения. Выход блока сравнения по.цключен к третьему входу блока управления, седьмой выход которого подключен к первому и второму входам второго программного блока. Четвер.тый вход арифметического блока соединен с первым выходом блока ввода коэффициентов, второй выход которого подключен к второму входу блока управления. Третий выход блока нГвода коэффициентов соединен с первым входом блока оперативной памяти. Четвертый выход подключен к третьему и чет вертому входам первого программного блока. Пятый выход подключен к третьему и четвертому входам второго программного блока. Восьмой выход блока управления соединен со вторым входом блока оперативной;памяти, выход которого подключен к пятому входу арифметического блока, (аест.ой вход которогосоединен с выходом ,блока- постоянной памяти, вхОд которого подключен к пятому выходу арифметического блока. В устройство введены третья матрица ремающих блоков, тре тйй элемент ИЛИ, при:чем дев ятый выход . блоКё;Тправ -лШйя подключён к первОМу управляющему входу каждого решаюи1его блока третьей матрицы, первый информационный вход которого со единён о Шестым выходом арйфмет т чёского блока. Выхода всех petaakjfmx блоков третьей матрицы через третий

элемент ИЛИ подключены к седьмому входу арйфмеГйчёского блока. Второй

информационный вход каждого решающего блока третьей матрицы подключен к соответствующему выходу из первой (J группы выходов второго программного блока. Третий информационный вход подключен к соответствующему выходу из второй группы выходов второго программного блока. Второй управляюашй

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

, Блок-схема устройства представлена на чертеже.

5 Дифровоё устройство для решения системы линейных уравнений с разреженной матрицей содержит матрицу 1 решающих блоков, матрицу 2 решающих . блоков, матрицу 3 решающих блоков,

0 арифметический блок 4, блок 5 управления-, блок биндикации, программные бло/ш 7 и 8, блок 9 постоянной памяти, блок 10 оперативной памяти, блок, 11 сравнения, блок 12 ввода коэффи5 ЦиентОв, элементы. ИЛИ 13-15, к.аждая матрица 1 состоит из 10 решающих блоков 1б.

Устройство работает следугацим образ Ом.

Q С помощью блока 12 ввода коэффициентов набираются построчно коэффициент за коэффициентом матрицы Н. Набор этих коэффициентов производится, например, на цифровой клавиатуе которая имеет клавиши строк и

столбцов. По сигналам, поступающим . с блока 12 программный блок 7 выра- батывает сигналы Y и Z,поступающие на входы решающего блока 16 матрицы Н. Таким образом, произошел выбор

0 ячейки С , куда заносится преобразованный на арифметическом блоке 4 коэффициент . При наборе коэффициента h запускается блок 5 управления, который работает по микропро5 грамме преобразования коэффициентов матрицы по методу разложения матрищл на треугольные множители с записью этих коэффициентов в виде таблицы множителей в матрицу 1, коэффициент

0 h поступает в арифметический блок 4, преобразуется .и поступает в ячейку С решбиощего блока 16 матрицы 1. Туда же поступает микрокоманда с блока 4. управления. При совпадении сигг налОв Y 2 и микрокоманды происходит запись элемента h в соответствующем решаквдем блоке 16. Ввод последующих коэффициентов подматрицы Н осуществляется аналогично BbiLle описанному, только программный блок 7 вырабатывает соответствующие координатные сигналы У и Я, которые выбирают соответс;тву ачие решающие блоки 16 С Мат1рйцы 1. Для определения обработки коэффициентов h в строке матри11Ы Н

5 служит блок 11 сравнения. Он сравнивает содержимое счетчиков строк и столбцов первого программного блока б. Когда эти счетчики равны идет обработка диагональных элементов Мат-, рицы Н,, Если счетчик строк меньше , счетчика столбцов, то ведется обработка коэффициентов вьиче главной диагонали матрицы, если счетчик строк больше счетчика столбцов, то ве;;ется обработка коэффициентов, распбложенных ниже главной диагонали маСгрИцы. Результаты сравнения с блока , 1, сравнения передаются в блок 5 управления, который вырабатывает опредеJrieHHHe микрокоманды, необходимые для арифметического блока 4, который ведет обработку коэффициентов. Блок 4 выполняет операции сложения, вычитания умножения, деления, накопления ;и алгебраического сложения, которые обеспечивают весь вычислительный процеСс. Микропрограммы, выполняющие |эти операции, МО гут быть зашиты в матрицах микропрограмм и микроко- манд. Эти микропрограммы служат как

МЙКРОПОДПРОграммы для основных Ь1ИК-..

ропрограмм решения системы линейных уравнений. После в.вода всех коэффициентов матрицы Н на блоке 12 нажимается, например, клавиша И. По этой команде запускается блок 5 управления, который работает по микропрограмме обращения матрицы Н в обратную матрицу Н. Для рбращения матри№1 используется метод прямых , решений с использованием разложения

на треугольные множители. Этот метод быстродействующий и по аппаратурным

затратам экономичный. Обращение матрицы Н заключается в том, что из полученной матрицы коэффициентов матрицы 1 выбирается треугольная матрица, которая поэлементно переписывается в матрицу 2 решающих блоков через элемент ИЛИ 13 и арифметический блок 4. При этом блок .5 управления работает по микропрограмме перезаписи матрицы, вырабатывая определенные микрокоманды для выборки коэффициентов из решаЮ1чих блоков 16 матрицы 1 и пересылки их в решающие блоки 16 матрицы 2, устанавливая при этом счётчики строк и столбцов программных блоков 7 и 8 в соответствующие состояния. Далее производится матричйая операция умножения матрицы 2 на матричные треугольные множители матрицы 1. Результирующая матрица накапливается в матрице 2. Умножение матриц производится традиционнЕлм способом .строка одной матрицы умножается на столбец другой матрицы. При умножении матриц коэффициенты вызываются в арифметический блок 4 через элемент ИЛИ 13 и элемент ИЛИ 14 и происходит их умножение с алгебраическим накоплением. Обратная матриц ца Н накапливается в матрице 2 решающих блоков. При обрагчении матриг

цы Н програггмные блоки 7 и 8 работают по программе, вырабатывая соответ- ствуюшие сигналы Х( Z и vl Z . Далее на блоке 12 нажимается клавиша Н , что означает, что в матрицу 1 5 решающих блоков вводятся коэффициенты верхней подматрицы Н . Ввод коэфЛициеНтов осуществляется описанным выше способом, когДа осуществляется ввод подматрицы Н ., Нажимается клаQ виша умножить , и происходит операция матричного умножения Н на . Матричное произведение Н Н- . . А хранится в матрице 1. Нажатием клавиши Q осуществляется вйод Q части известного вектора, которая 5 соответствует части матрицы Н .Ввод Q поэлементно осуществляется в блок 10 оперативной памяти, по микрокоманде с блока 5 управления. После этого нажимается клавиша умножить и 0 происходит матричное умножение матрицы 1 на известный вектор О. Получается произведение н н; Q в виде вектора размерностью Q. . Полученный вектор Н для накопления 5 засылается в блок 9 постоянной памяти, где накапливается вектор Q . Нажатием клав шчиф запускается блок 5 управления и происходит занесение коэффициентов подматрицы Ф в матрицу 0 2 решаю11их блоков через арифметический блок 4 с блока 12. Занесение коэффициентов происходит вышеописанным способом. После этого нажимается клавиша умножить и происходит опера, ция матричного умножения матрищл 4 на матрицу 2. Полученное матричное произведение Н, хранит . ся в матрице 1. Подматрица связи Vf -

единичная матрица при включении устройства находится в дополнительной матрице 3 решающих блоков. Далее осуществляется матричная операция сложения V7 с-Н н;|ф KC. Результат операции величина К накапливается в матрице 3. Вызов коэффициентов мат5 трицы 3 решающих блоков на арифметический блок 4 осуществляется по микрокомандам с блока 5 управления, поступающим на управляющие входы решающих блоков 16 матрицы 3 через элемент 0 ИЛИ 15 при выработке соответствующих сигналов Yt и Z программным блоком 8. Пересылка коэфАипиентов в матрицу 3 с арифметического блока 4 осуществляется по микрокоманде, поступающей с блока 5 управления на вход соответствующего решающего блока 16 матрицы 3. Далее осуществляется ввод второй части исходной-матрицы Н, т.е. осуществляемся последовательный ввод - подматриц Hj, Н,, Q,,, ф, и проделываются все матричные операции с эти- ми подматрицами описанным выше способом. Последовательность нажатий клавиш остается без изменения. После выполнения всех рассмотренных выгае операций в блоке 9 постоянной памяти-накопится выражение Н .+ Н QU. QCIS матрице 3 накопится результат W - Н н; ф + Н. йФ, Осуществляя ввод последуюсдах частей исходной матршда Н по подмат-. рйцам Н , Q I i до последней Q, ф где N 12 и части Н осуществив все матричные операции опи санным вы1че способом, получим окончательные результаты QC + -+ . |гсй.н-/о + Н2Н20г + Qj. накапливается в блоке 9, :- We - ( н;, Н7Х J 2 ... + + Н„ ) с -2( Н- ) , .накаплив.ается в матрице 3. - . . Для на овден1}Я неизвестного, .векторасвязйХ.нажимается; клавиши По команде с блока 11 ввода запускает ся. блок 5 уп авления, котррйй вырабатываёт микрокомандыперезаписи ..из матрицы 3 в матрицу 1 решающих бло ков, чтобы выйти на микроподпрограм: My обращения матрицы, .т. е. К Ъбраща ется.в.К- . Для оОрйщения исполь уётся метод прямых решений с йспользова нием разложения матрицы на треугольные множители. .Обращение .идет вышебписанным способом, когда находилась об ратная матрица H;J. Далее происходит матричная операция умножения К Qj. .:/ Х. Для. ЭТС1ГО.поэлементно на ариф,метический блок 4 вызывается Qc из блока 9 постоянной памяти и К из мат рицы i решающих .блоков через элемент ИЛИ 13. Результат вектора х,. накапли.вается в блоке 9. После нахождений вектора Х неизвестнйй векто | X находится по ча.ст.Я;М.. Нажимается, напримёр, клавиша ф , по которой запускается блок 5 управления и происходит /.зан.ёсёниекоэффициентов подматрицы ф в матрицу 2 решающих блоков через арифметический блок 4с блока 12. За/йёсёнйе/коэффициентов происходит аналогично вьпиеописаннсму. По нажатий клавиши множить происходитМатрйч на:я операция умйожения на арифметическом блоке 4 с вызовом поэлементно Ф и матрицы 2 и блока 9, Результат накапливается в блоке 9. При наж&тии клавиши О осуществляем ввод 0 - часть известного вектора в блок10 оператив«ой па.мяти. После ввода происходит вычитание Q - Ф Q . Вычитание происходит в арифметическом блоке 4 с вызовом элементов вектораиз блока 10 и вектора ф Х. .из Яблока 9. Результат вычитания засылается в блок 9 п остоянной памяти. Далее осуществляется вВод подма:трицы Н в матрицу 1, который рассматрйва ется выше. Находится обратная матрица Н, которая записывается в матрице 1. После этого нажимается клавиша умножить, по которой происходит матричная операция умножения матрицы 1 на блок 9 постоянной памяти. Блок 5 .управления работает по микропрограм ме умножения. На арифметическом блоке выполняется выражение H; Q Х езультат вектора х. записывается в лок 9. Численное значение найденно- го вектора К./передается в блок 6 индикаций .Осуществляется ввод последуюциx частей матрицы Н по подматриам ф , Q.J и H.J до последней части , Q1 и Н JJ и после произведения всех атричных операций и вычислений опианным выше способом, получаются се численные .значения вектора Полученные результаты решения исходной системы уравнения по частям печатаются на бумажной ленте или высвечиваются на цифровом табло. Решение системы линейных уравне-.. НИИ по частям значительно сокращает аппаратурные затраты. Предложенное устройство дает возможность решить практическилюбую большую систему линейных уравнений с разряженной матрицей в малом аппаратурном о.бьеме. Исходную матрицу Н можно разбить на лю-. бое число подматриц Н , Hg, ... , HN, . и порядок подматриц можно взять прЪизвольныМ. в устройстве максимальный порядок подматриц равен 10, т. е, все матрицы 1, 2 и дрпр.лнительная матрица имеют размерность 10 х 10 решающих блоков. Устройство в этом объеме обеспечивает решение любой большой системы .линейных уравнений высокого порядка с разр еженной матрицей. Суммарный аппаратурный экономический эффект составляет 28480руб. Кроме того, сокращаются различные материалы, цеховые и заводские расходы. Значительно.сокращаются монтажные работы. ..;. .... Формула изобретения Цифровое устройство для решения системы линейных уравнений, содержащее первую и вторую матрицы рёшаклдих блоков, арифметический блок, блок управления, блок индикации, первый и второй программные блоки, блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввода коэффициентов, элементы ИЛИ, причем пер.вый Выход арифметического блока соединен с первьзм входом блока индикации, первый вход блока управления соединен, со вторым выходом арифметичес кого блока, первый вход .которого подключен к первому .выходу блока управления, второй и третий выходы которого соединены соответственно с первыми управляющими входами каждого решающего блока первой и -второй матриц, четвертый и пять1й выходы блока управления соединены соответственно со втОрБпии управляющими входами каждого решакяцего блока первой и второй матриц, третий и четвертый выходы арифме тического блока подключен соотвё1 ственно к первым информационным входам каждого решающего блока первой и второй матриц, второй и третий входы арифметического блока соединены соответственно через первый и второй элементы ИЛИ с выходами решающих блоков первой и второй матриц, шестой выход блока управления соединен е ne{)BQiM 1Г вторым входами первого nporpaNMHOrO блока, первый и второй выходы которого подключен ко второму и третьёЩ входу блока индикации, второй информационный вход каждого решающего блока первой матрицы подключен к соответствующему выходу из первой группы выходов второго пр ограммного блока, третий информационный вхоД каждого решающего блока первой матрицы подключен к соответствующему выходу из второй группы выходов второго программного блока, первый и второй выходы которого соединены соответствёняо с первым и вторым входами блока сравнения, выход блока сравнения подключен к третему входу блока управления, седьмойвыход которого подключен к первому и второму входам вторбгд программного блока, четвертый вход : арифметического блока соединен с первым выходом блока ввода коэффициентов второй выход которого подключен к вто рому входу блока управления,третий вь ход блока ввода коэффициентов соедине с первым входом блока оперативной памяти,четвертый выход подключен к третьему и четвертому входам пёрвОгОпро граммного блока, пятый выход подключен к третьему и четвертому бхоцам второго программного блока, восьмой выход .блока управления соединен со вторым входом блока оперативной памяти, выход которого подключён к пятому входу арифметического блока, шестой вход которого соединен с выходом к а постоянной памяти, вход которого подключен к пятому выходу арифметического блока, о т л и ч а ю щ е е с я тем, что,с целью S/nipoliteHHlj уст ойства, бн6 сЪдержит третью матрицу решающих блоков, третий элемент ИЛИ, причем девятый выход блока управления подключен к первому управляющему входу каждого решающего блока третьей матрицы, первый информационный вход которого соединен с шестом выходом арифметического блока, выходы всех решающих блоков третьей матрицы через третий элемент ИЛИ подключены к седьмоу входу арифметического блока, второй информационный вход каждого peaiaranero блока третьей матрицы подключен к соответствующем выходу из первой группы выходов второго программного блока, третий информационный БХОД подключен к соответствующему выходу из второй группы выходов второго программного блока, второй управляющий вход каждого решающего блока третьей матрицы подключен к десятому выходу блока управления. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 404090, М.Кл. G 06 Р 15/32, 1973. 2.Заявка № 2337295, 1976, по которой принято решение о выдаче авторского свидетельства (прототип) .