Цифровое устройство для решения системы линейных уравнений

(61) Дополнитель авт, свид-в аЯвлено 22.03.76 (2) 2337295/1851) М, Кл С О 6 Р 1 Ы 32 присоединением заявкиооударственный комнтет Совета Инннстрое СССР ао делам нзооретенкй н открытий. Лебецев удового Красного Знаменгражданской авиации ий ордена Т ут ииженеро 71) Заявител тнст 4) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ тствуюшенформацив соответсгуппе управ информационным вх го решающего блок ный вхоц которого вующему выхоцу в соотве етий и трпоц юч второ Изобретение относится к области цифровой вычиспитепьной техники и может быть использовано при построении специализированных и клавишных вычислительных машин, предназначенных цпя решения эацач метоцами матричной алгебры.Известно устройство 1), соцержашее схемы набора элементов матриц, арифметяческое устройство, генератор импульсов, программное и коммутирующее устройство, 10 блок управления, устройство вывода и инцикации, схемы ИЛИ, И.Нецостатками такого устройства явпяются малое быстроцействие и ограниченные функциональные возможности.Наиболее близким к изобретению по технической сущности и цостигаемому результату является устройство 2, соцержащее матрицу решающих блоков, арифметический блок, блок управления, блок вывоца и инцикации, первый программный блок и элемент ИЛИ, причем первый выхоц арифметического блока соецинен с первым вхоцом блока вывоца и инцикации, первый вхоц блока управления соецинен 25 со вторым выхоцом арифметического блока, первый вхоц которого подключен к первому выхоцу блока управления, второй выхоц которого соецинен с первым управляющим вхоцом кажцого иэрешающихблоков, третий выхоц блока управленияпоцкпючен ко второму управляющему вхоцу кажцого из п решающих блоков, первый информационный вхоц кажцого из Мрешающих блоков соецинен с третьим выхоцом арифметического блока, а выхоцывсех и решающих блоков через элементИЛИ поцкпючены ко второму вхоцу арифметического блока, четвертый выхоа блокауправления соецинен с первым и вторымвхоцами первого программного блока, первый и второй выхоцы которого поцкпюченыко второму и третьему вхоцу блока вывоца и инцикации, каждый из выхоаов первой группы управляющих выхоцов первогопрограммного блока соединен со вторымпяюших выхоцов первого программного бпока.Оцнако это устройство имеет ограни.ченные функциональные возможности и недостаточную быстроту вычисления.Цепь изобретения - повышение быстроцейс твия.Это цостигается тем, что в прецпагаемое устройство введены блок постоянной памяти, бпок оперативной памяти, блок сравнения, блок ввоца коэффициентов, вто рой программный бпок, цопопнитепьный эпемент ИЛИ, цопопнитепьная матрица И решающих блоков, причем первый информационный вхоц кажцого изрешающих2блоков цопопнитепьной матрицы поцкпючен 15 к четвертому Выхоцу арифметического бпока, второй информационный вхоц - к соответствующему выходу в первой группе управпяющих выходов второго программного бпока, третий информационный вхоц - к соответствующему выхоцу во второй группе управляющих выхоцов второго программного бпока, первый управпяющий вхоц - к пятому выхоцу блока управления, второй управпяющий вхоц - к шестому выхоцу бпо 5 ка управления, а выхоц через цопопнитепьный элемент ИЛИ - к третьему входу арифметического блока, четвертый вхоц которого соединен с первым выхоцом блока ВВОца коэффициентОВ Второй Выход кОтО рого поцкпючен ко второму вхоцу блока управпения, третий выхоц бпока ввода коэффициентов соецинен с первым вхоцом бпока оперативной памяти, а четвертый выхоц поцкпючен к третьему и четвертому вхоцам первого программного блока, первый и второй выхоцы которого через блок сравнения соецинены с третьим Вхоцом бпока управления, сецьмой выход которого поцкпючен к первому и второму вхоцам второго программного бпока, а восьмой выхоц блока управления соецинен со вторым вхоцом блока оперативной памяти, выхоц которого поцкпючен к пятому вхоцу арифметического блока, шестой вход кого рого соецинен с выхоцом бпока постоянной памяти, а пятый выход арифметического блока поцключен ко вхоцу бпока постоянной памяти; кроме того кажцый из 2 И решающих блоков содержит цва элемента И, элемент НЕ, регистр и эпемент ИЛИ, причем первый управпяющий вхоц решающего блока соеци ен с первым вхоцом первого эпемента И, второй и третий вхоцы которого соецинены со вторым и третьим информационными входами решающего блока и первым и вторым входами второго элемен та Итретий вход которого подключек к первому информационному вхоцу решающего бпока, четвертый вхоц второго эпемента И соецинен со вторым управляющим вхоцом решающего блока и первым входом элемента НЕ, выхоц которого соецинен с первым вхоцом эпемента ИЛИ, второй вхоц которого поцкпючен к выхоцу второго эпемента И, а выхоц элемента ИЛИ через регистр соецинен со вторым вхоцом элемента НЕ и с четвертым вхоцом первого элемента И, выхоц которого поцкпючен к выхоцу решающего бпока; кажцый из программных блоков соцержит счетчик строк и счетчик столбцов, причем первый и второй выхоцы счетчика строк первого программного блока соецинены с первым и третьим вхоцами первого программного бпока, первый Выхоц которого поцкпючен к выхоцу счетчика строк этого бпока, первый и второй вхоцы счетчика стопбцов первого программного блока соецинены со вторым и четвер тым вхоцами э тог о программного блока, второй выхоц которого поцключен к Выходу счетчика столбцов первого программного бпока, первый и второй вхоцы второго программного блока соединены соответственно со вхоцом счетчика строк и счетчика стопбцов в этом блоке.Структурная схема устройства прецставпена на чертеже.Цифровое устройство цпя решения системы линейных уравнений соцержит матрицу 1 решающих бпоков, арифметический бпок 2, бпок управления 3, бпок 4 вывоца и инцикации,. первый программный блок 5 второй программный блок 6 цопопнитепьную матрицу 7 решающих блоков, бпок 8 сравнения, блок 9 ввоца коэффициентов,. бпок 10 постоянной памяти, бпок 1 1 оперативной памяти, счетчик 12 строк, счетчик 13 столбцов, решающий бпок 14, ретистр 15, первый элемент.И 16, элемент НЕ 17 элемент ИЛИ 18, второй эпемент И 19 элемент ИЛИ 20, цопопнитепьный элемент ИЛИ 21.Устройство работает спецуюшим образом. С помощью блока 9 Ввоца коэффициентов набираются построчно коэффициент за коэффициентом матрицЫНабор этих коэффициентов произвоцится, например, на цифровой кпавиатуре, которая также может иметь кпавиши строк и столбцов. При наборе первой строки счетчик 12 строк первого программного блока 5 устанавпивается в первое состояние, при наборе первого коэффициента счетчик 13 столбцов.первого программного бпока 5 устанавпивается в то же в первое состояния по сигнапам, поступающим с блока 9 Ввоца ко234 5 624 эффициентов. В этот момент счетчик 12строк и счетчик 13 столбцов соответственно вырабатывают сигналы, поступающие на вхоцы второго элемента И 19 решающего блока 14 матрицы 1 решающихблоков. Таким образом происхоцит выбор,5ячейки, куда должен быть занесен элементтаблицы множителей. При наборе коэффициента на блоке 9 ввода коэффициентовв нем вырабатываются сигналы, кото 1 Орые поступают в блок управления 3 (блок управления 3 может быть микропрограммным устройством управления), Блок управления 3 начинает работать по определенной программе, вырабатывая ми 15 крокоманцы. Происходит прием коэффициента в арифметический блок 2, который обрабатывает и запоминает коэффициент.Арифметический бпок 2 выполняет операцию деления и по опрецепенным микрс 20 командам поступающим с блока управления 3, передает элемент таблицы множителей в выбранную ячейку. Элемент таблицы множителей поступает на второй элемент И 19, на который также поступает25 микрокоманца с блока управления 3, При совпацении сигналов и микрокоманцы происхоцит запись элемента через элемент ИЛИ в регистр 15, гце этот элемент хранится при помощи циклической перезапи 30 си через элемент НЕ 17 и элемент ИЛИ 18, Микрокомвнца, постуиившвя на элемент И 19 разрешает запись, в тоже время она запрещает перезапись элемента в регистр 15, который в нем находился ранее, своим поступлением на вхоц элемента НЕ 17.При наборе следующего коэффициента строки счетчик 13 столбцов первого программного блока 5 устанавливается во второ рое положение и вырабатывает сигнал, поступающий на элемент И 19 соответствующей ячейки, Туда же поступает сигнал со счетчика 12 строк, Точно также коэффициент поступает в арифметический блок4 2, который. выполняет целение и передает в выбранный решающий блок 14 матрицы 1 ячейку по микрокоманце, поступающей с блока управления 3. Затем заносится таким же образом все коэффициенты цо П -го первой строки.Далее выполняется второй швг.При ввоце коэффициента счетчик 12 строк первого программного блока 5 устанавливается во второе положение, а счетчик 13 столбцов в первое положение, соответственно выбирается в решающем блоке 14 матрицы 1 ячейка. Арифметический блок 2 вычисляет значение, которое засыпается в выбранную ячейку способом, опи-ро санным выше. При ввоце следующего коэффициента счетчик 13 столбцов устанавливается в положение 2", выбирается соответствующая ячейка в матрице 1, в которую цопжен записаться элемент. Арифметический блок 2 проиэвоцит вычисления.Далее вводятся коэффициенты третьей строки и т.ц, цо б -ой строки. Как вицно из описанного элемента каж цой строки обрабатываются совершенно одинаково. Кажцая строка обрабатывается также одинаково, только с ростом 11 (количества строк) растет количество циклов обработки.Дпя различия обработки элементов в строке в устройство введен блок 8 сравнения. Он сравнивает соцержимое счетчика 12 строк и счетчика 13 столбцов первого программного блока 5. Когца зги счетчики равны, идет обработка первой группы элементов. Если счетчик 12 строк меньше счетчика 13 столбцов, го вецегся обработка элементов второй группы элементов, если наоборот, то вецется обработка третьей группы элементов. Ре- з;пьтат сравнения с блока сравнения 8, передается в блок управления 3, который вырабатывает опрецеленные микрокоманцы цля арифметического блока 2, Арифметический блок 2 выполняет операции сложения, вычитания, умножения и деления, накоппения и алгебраического сложения. Набор этих операций обеспечивает весь вычислительный процесс, Микропрограммы, выполняющие эти операции, могут быть "зашиты" в матрицах микропрограмм и микрокоманц. Эти микрокоманцы могут служить как микропоцпрограммы цпя основных микропрограмм решения системы уравнений.Таким образом все коэффициенты системы записаны в матрицу 1 и получена таблица множителей.Дпя решения системы уравнения нужно в устройстве иметь известные вектора.Дпя этого в устройство ввецеч блок 11 оперативной памяти, в который с блока 9 ввоца коэффициентов ввоцятся коэффициенты известных векторов. Ввоц осуществляется по микрокоманцам, поступающим с блока управления 3, который запускается по ввоцу известного вектора. Блок 11 оперативной памяти может прецставпять собой стековые регистры, количество которых равно поряцку системы.Из полученной. таблицы множителей, которая записана в матрице 1 решающих блоков, можно выбрать любую специальную матрицу и произвести их умножение. Умножение матриц произвоцится обычнымспособом; строка оцной матрицы умножается на столбец другой матрицы.В устройстве прецусмогрен спучай вычиспения вектора В, когда известен,вектор Х. В этом спучае произвоцится образование специальных матриц, а весь про 5 цесс умножения матриц анапогичеи выше описанному. Такое обратное решение может быть использовано цпя проверки правильности решения системы уравнений.Таким образом, применение предлагаемого устройства цпя решения системы линейных уравнений аппарагурным способом с учетом принципа микропрограммирования позвопипо повысить быстроцействие с небольшими аппарагурными затратами, Устройство является цостаточно эффективным цпя решения системы линейных уравнений, При использовании мегоца прямых решений на основе разпожения матрицы на треугопьнлые множигепи цостигается20 существенное сокращение времени вычислений и объема памяти. В этом и закпючается основное преимушество прецпагаемого устройства по сравнению с цругими устройствами решения систем пинейных25 уравнений.формупа изобретения1. Цифровое усгройство цпя решения системы пинейных уравнений, соцержащее матрицу решающих бпоков, арифметический блок, бпок управления, блок вывоца и ин-. цикации, первый программный блок и эпемент ИЛИ, причем. первый выхоц арифмегитеского бпока соецинен с первым вхоцом блока вывоца и инцикации, первый вхоц блока управления соецинен со вторым выхоцом арифметического биска, первый вход которого поцкпючен к первому выходу бпо 40 ка управпенич, второй выхоп, которого соецинен с первым управпяющим входом ажцого из П решаютцих бпоков, третий выход2бпока управления поцкпючен о второму управляющему входу кажцого из ц реша 2 45 ющих бпоов, первый информационный вхоц кажцого из и решающих бпоков соецинен2с третьим выхопом арифметического бпока, а выхоцы всех И решающих бпоков через элемент ИЛИ поцкпючены ко вгоро 50 му входу арифметического блока, четвертый выход бпока управпения соецинен с первым и вторым вхоцамц первого программного бпока, первый и второй выхоцы которого поцпючены ко второму и гре 55 тьему входу биска вывоца и инцикации, каждый из выходов первой группы управляющих выхоцов первого программного бпока соединен со вторым информационным входом соответствующего решающего блока, третий информационный вхоц которого иоцкпючен к соответствующему выходу во второй группе управпяющих выхоцов первого программного блока, о т и и ч а ю - щ е е с я тем, что, с цепью повышения быстроцействия, в него ввецены бпок постоянной памяти, блок оперативной памяти, бпок сравнения, бпок ввоца коэффициентов, второй программный бпок, цопопнитепьный элемент. ИЛИ, цопопнитепьная матрица И решающих бпоков, причем первыййинформационный вход кажцого из И решающих блоков цопопнитепьной матрицы поцкпючен к четвертому выхоцу арифметического бпока, второй информационный вход - к соответствующему выхоцу в первой группе управляющих выхоцов второго программного бпока, третий информационный вхоц - к соответствующему выходу во второй группе управляющих выхоцов второго программного блока, первый управпяющий вход - к пятому выхоцу блока управления, второй управпятощий вход - к шестому выходу бпока управпения, а выхоц через цопопнитепьный эпемент ИЛИ - к третьему вхоцу арифметического бпока, четвертый вхоц которого соецинен с первым выхоцом блока ввоца коэффициентов, второй выхоц которого поцкпючен ко второму вхоцу блока управпения, третий выхоц блока ввоца коэффициентов соецинен с первым вхоцом бпока оперативной памя" ги, а четвертый выхоц подключен к третьему и четвертому вхоцам первого программного бпока, первый и второй выхоцы которого через блок сравнения соединены с третьим вхоцом бпока управпения, седьмой выхоц которого поцкпючен к первому и второму вхоцам второго программного бпока, а восьмой выхоц блока управления соединен со вторым вхоцом блока оперативной памяти, выхоц которого поцкпючен к пятому входу арифметического блока, шестой вхоц которого соецинен с выхоцом бпока постоянной памяти, а пятый выхоц арифметического блока поцкпючен ко входу бпока постоянной памяти.2. Устройство по и. 1, о г п и ч а юц е е с я тем, что кажцый из 2 и решающих бпоков соцержит цва элемента И, эпемент НЕ, регистр и эпеменг ИЛИ, причем первый управляющий вхоц решающего блока соединен с первым входом первого элемента И, второй и третий вхоцы когорого соединены со вторым и третьим информационными вхоцами решаюптего блоа и первым и вторым вхоцами вгорого элемента И, третий вхоц которого иоцкпючен к первому информационному вхоцу ре:шающего бпока, четвертый вхоц второго эпемента И соецинен с вторым управляющим вхоцом решающего бпока и первым вхоцом эпемента НЕ, выхоц которого соецинен с первым вхоцом элемента ИЛИ5 второй вхоц которого поцкпючен к выхо цу второго эпемента И, а выхоц элемента ИЛИ через регистр соединен со вторым вхоцом апемента НЕ и с четвертым вхоцом первого эпемента И, выхоц которого16 поцкпючен к выхоцу решающего блока.3, Устройство по п. 1, о т п и ч а ющ е е с а тем, что кажцый из программных бпоков соцержит счетчик строк и счетчик стопбдов, причем первый и второй15 вхоцы счетчика строк первого программного бпока соецинены с первым и третьим вхоцеми первого программного блока, первый выхоц которого поцкпючен к выхоцусчетчика строк этого бпока, первый и второй входы счетчика стопбцов первого программного бпока соецинены со вторым и.четвертым вхоцами этого программногобпока, второй выхоц которого поцкпючен.к выхоцу счетчика стопбцов первого протраммного бнока, первый и второйвхоцывторого программного бпока соеаиненысоответственно со входом счетчика строки счетчика стоцбцов в этом бпоке. Источники информации, принятые во внимание при экспертизе: 1. Авторское свицетецьство СССР М 294144, кп. Су 06 Р 15/32, 1968. 2. Авторское свицетепьство СССР М 404090, кп. Я 06 Р 15/32, 1970.,624234.аз 5189/39ЦНИИП 826 Поцписное ного комитета Совета Мин изобретений и открытий Ж, Раущская наба. 4 Тиражосуиарст ов СССР пенам осква,11303 ипиап ППП "Паген Ужгороц, уп. Проектная Сосгавигепь Б, Тарасов актор Н. Каменская Техреду Е. Лавидович Корректор, С, Гардспнях