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

Изобретение относится к области цифровой вычислительной техники и может использовано при построении специализированных и клавишных вычиспитель- ных машин, прецнааначенных цля решения задач методами матричной алгебры. Известно устройство 1 , соцержащее схемы набора элементов матриц, арифметическое устройство, генератор импульсов программное и коммутирующее устройство блок управления, устройство вывоца и инцикации, схемы ИЛИ, И. Недостатками такого устройства являются малое быстродействие и ограниченные функциональные возможности, Наиболее близким к изобретению по технической сущности и постигаемому ре зультату является устройство 2 , содер жащее матрицу решак)щих блоков, арифметический блок, блок управления, блок вывода и индикации, первый программный блок и элемент ИЛИ, причем первый выход арифметического блока соединен с первым входом блока вывода и индикации, первый вход блока управления соединен СО вторым выходом арифметического блока, первый вход которого подключен к первому выходу блока управления, второй выход которого соединен с первым управляющим входом каждого из rt решающих блоков, третий выход блока управления подключен ко втсэрому управляющему входу каждого из М решающих блоков, первый информационный вход каждого из К решающих блоков соединен с третьим выходом арифметического блока, а выходы всех П решающих, блоков через элемент ИЛИ подключены ко второму входу ари(} метического блока, четвертый выход блока управления соединен с первым и вторым входами первого программного блока, первый и второй выходы которого подключены ко второму и третьему входу блока выво да и индикации, каждый из выходов первой группы управляющих выходов первого программного блока соецинен со вторым информационным входом соответствующего решающего блока, третий информационный вход которого подключен в соответствующему выходу во второй группе угфавпяющих выхоцов первого программного блока. Оцнадо этоустройство имеет ограниченныефункциональные возможноеги и недостаточную быстроту вычиспения. Цепь изобретения - повышение быстро- цействия. Это цостигаегся тем, что в прецпага- емое устройство введены бгок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввоца коэффициентов, второй программный блок, дополнительный элемент ИЛИ, пополнительная матрица п решанэщих блоков, причем первый информационный вхоц кажаого из w решающих блоков дополнительной матрицы подключен к четвертому выхоцу арифметического бпо второй информационный вход - к соответствующему выхоцу в первой группе уп равляющих выхоцов второго программного блока, третий информационный вхоц к соответствующему выхоцу во второй группе управляющих выхоцов второго программного блока, первый управляющий вхоц - к пятому выхоцу блока управления, второй управляющий вхоц - к шестому выхоцу бпо ка управления, а выход через дополнитель ный элемент ИЛИ - к третьему входу ари фметического блока, четвертый вхоц которого соединен с первым выхоцрм блока ввоца коэффициентов, второй выход которого подключен ко второму входу блока управления, третий выхоц блока ввода коэффициентов соединен с первым вхоцом блока оперативной памяти, а четвертый выхоц подключен к третьему и четвертому входам первого программного блока, первый и второй выходы которого через блок сравнения соединены с третьим входом блока управления, седьмой выход которого подключен к первому и второму входам второго программного блока, а восьмой выход блока управлершя соединен со вторым входом блока оперативной памяти, вы ход которого подключен к пятому входу арифметического блока, щестой вход которого соединен с выходом блока постоянной памяти, а пятый выход арифметического блока подключен ко входу блока постоянной памяти: кроме того каждый из 2 Я решаюашх блоков содержит два элемента И, элемент НЕ, регистр и элемент ИЛИ, причем первый управлявощйй вход решающего блока соединен с первым входом первого элемента И, второй и третий входы которого соединены со вторьш и третьим информационными вхоцами решающего блока и первым и вторым вхоцами второго элемента И, третий вход которого подключек к первому информационному входу решающего 6 44 блока, четвертый вход второго элемента И соединен со вторым управляющим входом решающего блока и первым входом элемента НЕ, выход которого Соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, а выход элемента ИЛИ через регистр соединен со вторым входом элемен та НЕ и с четвертым входом первого элемента И, выход которого подключен к выходу решающего блока; каждый из программных блоков содержит счетчик строк и счетчик столбцов, причем первый и второй выходы счетчика строк первого программного блока соединены с первым и третьим входами первого программного блока, первый выход которого подключен к выходу счетчика строк этого блока, первый и вто- рой входы счетчика столбцов первого программного блока соединены со вторым и четвертым входами этого программного блока, второй выход которого подключен к выходу счетчика столбцов первого программного блока, первый и второй входы второго программного блока соединены соответственно со входом счетчика строк и счетчика столбцов в этом блоке. Структурная схема устройства пр.едсгавлена на чертеже. Цифровое устройство для решения системы линейных уравнений содержит матрицу 1 решающих блоков, арифметический блок 2, блок управления 3, блок 4 вывода и индикации,, первый программный блок 5, второй программный бпок 6, дополнительную матрицу 7 решающих блоков, блок 8 сравнения, блок 9 ввода коэффициентов, блок 1О постоянной памяти, блок 11 оперативной памяти, счетчик 12 строк, счетчик 13 столбцов, решающий блок 14, ре- гистр 15, первый элемент .И 16, элемент НЕ 17, элемент ИЛИ 18, второй элемент И 19, элемент ИЛИ 2О, дополнительный элемент ИЛИ 21. Устройство работает следующим образом. - С помощью блока 9 ввода коэффициентов набираются построчно коэффициент за коэффициентом матрицы,.Набор этих коэффициентов производится, например, на цифровой клавиатуре, которая также может иметь клавиши строк и столбцов. При наборе первой строки счетчик 12 строк-первого программного блока 5 устанавливается в первое состояние, при наборе первого коэффициента счетчик 13 столбцов.первого программного блока 5 устанавливается в то же в первое состояние по сигналам, поступающим с блока 9 ввода ко- эффициенгов. В этот момент счетчик 12 строк и счетчик 13 столбцов соответсгвенно вырабатывают сигналы, поступающие на вхоцы второго эпемента И 19 ре шающего бпока 14 матрицы 1 решающих блоков. Таким образом происходит выбор ячейки, купа должен быть занесен элемент таблицы множителей. При наборе коэффициента на блоке 9 ввода коэффициентов в нем вырабатываются сигналы, которые поступают в блок управления 3 (блок управления 3 может бытьмикропрограммным устройством управления). Бпок управпения 3 начинает работать по опрецеленной программе, вырабатывая микрокоманцы. Происходит прием коэффициента в арифметический блок 2, который обрабатывает и запоминает коэффициент. Арифметический блок 2 выполняет операцию целения и по определенным микрокомандам, поступающим с блока управления 3, передает элемент таблицы множителей в выбранную ячейку. Элемент табли цы множителей поступает на второй элемент И 19, на который также поступает микрокоманда с блока управления 3. При совпадении сигналов и микрокоманды происходит запись элемента через элемент ИЛИ в регистр 15, где этот элемент хра нится при помощи циклической перезаписи через элемент НЕ 17 и элемент ИЛИ 18. Микрокоманда, поступившая на элемент И 19 разрешает запись, в тоже время она запрещает перезапись элемента в регистр 15, который в нем находился ранее, своим поступпевием на вход элемента НЕ 17. При наборе следующего коэффициента строки счетчик 13 столбцов первого прог раммного блока 5 устанавливается во вто рое положение и вырабатывает.сигнал, поступающий на элемент И 19 соответствующей ячейки, Туда же поступает сигнал со счетчика 12 строк. Точно также коэффициент поступает в арифметический блок 2, который выполняет деление и передает в выбранный решающий блок 14 матрицы 1 ячейку по микрокоманде, поступающей с блока управления 3. Затем заносится таким же образом все коэффициенты до И -го первой строки. Далее выполняется второй щаг. При вводе коэффициента счетчик 12 строк первого программного блока 5 уста навливается во второе положение, а счет- чик 13 столбцов в первое положение,. соответственно выбирается в решающем бло ке 14 матрицы 1 ячейка. Арифметический блок 2 вычисляет значение, которое засылается в в,ыбранную ячейку способом, опи- санным выше. При вводе следующего коэффициента счетчик 13 столбцов устанавливается в положение 2, выбираегс а соответствующая ячейка в матрице 1, в которую должен записаться элемент. Арифметический блок 2 производит вычисления. Далее вводятся коэффициенты третьей строки и т.д. до rt -ой строки. Как видно из описанного элемента каждой строки обрабатываются совершенно одинаково. Каждая строка обрабатывается также одинаково, только с ростом t (количества строк) растет количество циклов обработки. Для различия обработки элементов в строке в устройство введен бпок 8 сравнения. Он сравнивает содержимое счетчика 12 строк и счетчика 13 столбцов первого программного блока 5. Когда эти счетчики равны, идет обработка первой группы элементов. Если счетчик 12 строк меньше счетчика 13 столбцов, то ведется обработка элементов второй группы элементов, если наоборот, то ведется обработка третьей группы эпементов. Рез льтат сравнения с блока сравнения 8, передается в блок управления 3, который вьфабатывает определенные микрокоманды для арифметического блока 2. Арифметический блок 2 выполняет операции сложения, вычитания, умножения и деления, накопления и алгебраического сложения. Набор этих операций обеспечивает весь вычислительный процесс. Микропрограммы, выпоп- н$пощие эти операции, могут быть зашиты в матрицах микропрограмм и микрокоманд. Эти микрокоманды могут служить как микроподпрограммы для основных микропрограмм решения системы уравнений. Таким образом все коэффициенты системы записаны в матрицу 1 и получена таблица множителей. Для решения системы уравнения нужно в устройстве иметь известные вектора. Для этого в устройство введен блок 11 оперативной памяти, в который с блока 9 ввода коэффициентов вводятся коэффициенты известных ве ;торов. Ввод осуществляется по микрокомандам, поступающим с блока управпения 3, который запускает ся по ввоцу известного вектора. Блок 11 оперативной памяти может прецставпять собой стековые регистры, количество которых равно порядку системы. Из полученной; таблицы множителей, ко- торая записана в матрице 1 решающих блоков, можно выбрать любую специальную матрицу и произвести их умножение. Умножение матриц производится обычным способом: строка одной матрицы умножается на столбец п-ругой матрицы. В устройстве прецусмотрв спучай вычисления вектора В, когца известен .векгор X В этом случае произвоаится образование специапьных матриц, а весь процесс умножения матриц аналогичен выше описанному. Такое обратное решение может быть испопьаовано ,цпя проверки пра випьности решения системы уравнений. Таким образом, применение преапагаемого устройства цпя решения системы пи нейных уравнений аппаратурным способом с учетом принципа микропрограммирования аозвопипо повысить быстроцействие с небольшими аппаратурными затратами. Устройство явпяется цостаточно эффектнаным цпя решейия системы пиней 1ых уравнений. rijJH испопьзовании мегоца прямых решений на основе разложения матрицы на треугольные множитепи цоотигается существенное сокращение времени вычислений и объема памяти. В этом и заключается основное преимущество прецпагае- мого устройства по сравнению с другими устройствами решения систем линейных уравнений. Формула изобретения 1. Цифровое устройство цля решения системы линейных уравнений, содержащее матрицу решающих блоков, арифметически блок, блок управления, блок вывоца и инаикации, первый программный блок и элемент ИЛИ, причем, первый выхоц арифме™ гического блока соецинен с первым вхоцо блока, вывоца и инцикации, первый вхоц блока управления соецинен со вторым вы- хоцом арифметического блока, первы.й вхо которого поцключен к первому выхоцу бло ка управления, второй выход со- ецинен с первым управляющим вхоцом каж цого из rt решающих блоков, третий выхо блока управления поцключен ко второму управляющему.вхоцу ка кцого из YI решающих блоков, первый информационный вхо кадсцого из И решающих блоков соецине с третьим выхоцом арифметического блока, а выхрцы всех к решающих блоков через элемент ИЛИ поцкпючены ко второ му вхоцу арифметического блока, четвертый выход блока управления соединен с первым и вторым вхоцами первого программного бло.ке, первый и второй выхоцы которого поцключены ко второму и третьему вхоцу блока вывода и инцикации, каждый из выходов первой группы управля ющих выхоцов первого программного блока соецинен со вторым информационным вхоаом соответствующего решающего блока, третий информационный вхоц которого подключен к соответствующему выхоцу во второй группе управляющих выхоцов первого программного блока, отличающееся тем, что, с целью повышения быстроцействия, в него ввецаны блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввоца коэффициентов, второй программный блок, цопопни- гельный элемент. ИЛИ, цополнительвая мат- рица П решающих блоков, причем первый информационный вхоц кажцого из И решающих блоков дополнительной матрицы подключен к четвертому выхоцу арифметического блока, второй информационный вход - к соответствующему выходу в первой группе управляющих выхоцов второго программного блока, третий информационный вхоц - к соответствующему выходу во второй группе управляющих выхоцов второго программного блока, первый управ пшощий вхоц - к пятому выхоцу блока управпения, второй управляющий вход - к шестому выхоцу блока управления, а вы- хоц через дополнительный элемент ИЛИ - к третьему вхоцу арифметического блока, четвертый вхоц которого соединен с первым выхоцом блока ввоца коэффициентов, второй выход которого поцключен ко второму вхоцу блока управления, третий выхоц блока ввода коэффициентов соединен с первым вхоцом блока оперативной памяти, а четвертый выход подключен к третьему и четвертому входам первого прог раммного блока, первый и второй выходы которого через блок сравнения соединены с третьим вхоцом блока управления, седьмой выхоц которого поцключен к первому и второму входам второго программного блока, а восьмой выход блока управления соединен со вторым входом блока оперативной памяти, выхоц которого подключен к пятому вхоцу арифметического блока, шестой вход которого соединен с выходом блока постоянной памяти, а пятый выход, арифметического блока подключен ко входу блока постоянной памяти. 2. Устройство по п. 1, о т л и ч а ющ е е с я тем, что каждый из 2 Иг решающих блоков содержит два элемента И, элемент НЕ, регистр и элемент ИЛИ, причем первый управляющий вхоц решающего блока соединен с первым входом первого элемента И, второй и третий входы которого соединены со вторым и третьим информационными вхоцами решающего блока и первым и вторым входами второго элемента И, третий вход KOTopoiX) поакпю-чен к первому информацией но Njy fie,шающего блока, четвертый вхоц второго элемента И соединен с вторым управпяю- щим вхоцом решающего блока и первым рхоцом элемента НЕ, выхоц которого со- с первым входом элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, а выход элемента ИЛИ через регистр соединен со вторым входом элемента НЕ и с четвертым входом первого элемента И, выход которого подключен к выходу решающего блока.

3. Устройство по п. 1, о т л и ч а ющ е е с я тем, что каждый из программных блоков содержит счетчик строк и счетчик столбцов, причем первый и второй входы счетчика строк первого программного блока соединены с первым и третьим входами первого программного блока, первый выход которого подключен к выходу счетчика строк этого блока, первый и второй входы счетчика столбцов первого про1 раммного блока соединены со йтор)ым и четвертым входами этого программного бпока, второй выход которого подключен к выходу счетчика столбцов первого программного блока, первый и второй входы второго программного блока соединены соответственно со входом счетчика строк и счетчика столбцов в этом блоке.

Источники информации, принятые во внимание при экспертизе:

1,Авторское свидетельство СССР NO 294144, кл. Q Об Р 15/32, 1968.

2.Авторское свидетельство СССР № 4О4О9О, кл. q Об F 15/32, 197О.