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

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

Иллюстрации

Показать все

Реферат

 

описании

ЙЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДИТИЛЬСТВУ (61) Дополнительное к авт, свнд-ву (22) Заявлено 22.О3.76 (21) 2337295/18-24 с присоединением заявки № (23) Приоритет (43) Опубликовано 15.09.786юллетень ¹ 34 (45) Дата опубликования описания 01.08.78

Сомма Советских

С@циалмстимеских

Республик ((l i 624234

Я (51) М, Кл

С Об V 15/32

Государственный комитет

Совета Министров СССР оо делам нзооретеикй н открытий (53) УДК 681 325 (088. 8) (72) Авторы изобретения

П. А. Лебедев и Л. Я. Нагорный

Киевский ордена Трудового Красного Знамени институт инженеров гражданской авиации (71) Заявитель (54) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ

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

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

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

Наиболее близким к изобретению по технической сущности и цостигаемому результату является устройство (2J, соцержащее матрицу решающих блоков, арифметический блок, блок управления, блок вывоца и инцикацни, первый программный блок и элемент ИЛИ, причем первый выхоц арифметического блока соецинен с первым вхоцом блока вывоца и инцикацни, первый вхоц блока управления соецинен со вторым выхоцом арифметического блока, первый вхоц которого поцкпючен к первому выхоцу блока управления, второй выхоц которого соецинен с первым управляюшим входом каждого иэ rt решающих блоков, третий выхоц блока управления поцкпючен ко второму управляющему вхоцу кажцого из и решающих блоков, первый информационный вхоц кажцого из К решающих блоков соецинен с третьим выхоцом арифметического блока, а выхоцы всех и решающих блоков через эпемен r, ИЛИ поцкпючены ко второму вхоцу арифметического блока, четвертый выход блока управления соецинен с первым и вторым вхоцами первого программного блока, первый и второй выхоцы которого поцкпючены ко второму и третьему вхоцу блока выво ца и инцикации, кажцый из выходов первой группы упра вляющих выхоцов первого программного блока соединен со вторым информационным входом соответствующего решающего блока, третий информационный ехоп которого подключен в соответст вующему выхоцу во второй группе управ

624234 пяющих выхоцов первого программного бпока.

Оцнако это устройство имеет ограни.ченные функциональные возможности и недс статочную быстроту вычисления. цепь изобретения - повышение быстроцейс твия.

Это цостигается тем, что в прецпагаемое устройство введены блок постоянной памяти, бпок оперативной памяти, блок сравнения, блок ввоца коэффициентов, вто- 1О

poN программный бпок, цопопнитепьный эпемент ИЛИ, цопопнитепьная матрица И решающих блоков, причем первый информационный вхоц каждого из решающих

2 блоков цопопнитепьной матрицы поцкпючен 15 к четвертому выхоцу арифметического бпока, второй информационный вхоц — к соогветствующему выхоцу в первой группе управпяющих BbIxonoa второго программного бпока, третий информационный вхоц — к соответствующему выхоцу во второй группе управляющих выхоцов второго программного бпока, первый управпяющий axon— к пятому выхоцу блока управления, второй управпяющий вхоц — к шестому выхоцу бпо- 5 ка управления, а выхоц через цопопнитепьный элемент ИЛИ вЂ” к третьему входу арифметического блока, четвертый ахоп которого соединен с первым выхоцом блока ввода коэффициентовг второй выход Koro» рого поцкпючен ко второму вхоцу блока управпения, третий выхоц бпока ввоца коэффициентов соецинен с первым вхоцом бпока оперативной памяти, а четвертый выхоц поцкпючен к третьему и четвертому вхоцам первого программного блока, первый и второй выхоцы которого через блок сравнения соецинены с третьим вхоцом бпока управления, сецьмой выход которого поцкпючен к первому и второму вхоцам второго программного бпока, а восьмой выхоц блока управления соецинен со вторым вхоцом блока оперативной памяти, выхоц которого поцкпючен к пятому вхоцу арифметического блока, шестой ахоп кого- 45 рого соецинен с выхоцом бпока постоянной памяти, а пятый выхоц арифметического блока поцключен ко вхоцу бпока постоянной памяти: кроме того кажцый из 2 и решающих блоков содержит цва элемента

И, элемент НЕ, регистр и эпемент ИЛИ, причем первый управпяющий вхоц решающего блока соеци ен е первым вхоцом первого эпемента И, второй и третий вхоцы которого соецинены со вторым и третьим информационными входами решающего блока и первым и вторым входами aroporo элемен ra И„третий вход которого подключек к первому информационному вхоцу решающего бпока, четвертый ахоп второго эпемента

И соецинен со вторым управляющим вхоцом решающего блока и первым вхоцом элемента НЕ, выхоц которого соецинен с первым вхоцом эпемента ИЛИ, второй вхоц которого поцкпючен к выхоцу второго эпемента И, а выхоц элемента ИЛИ через регистр соецинен со вторым вхоцом элемента НЕ и с четвертым вхоцом первого элемента И, выхоц которого поцкпючен к выхоцу решающего бпока; кажцый из программных блоков соцержит счетчик строк и счетчик столбцов, причем первый и второй выхоцы счетчика строк первого программнсго блока соецинены с первым и третьим вхоцами первого программного бпока, первый выхоц которого поцкпючен к выхоцу счетчика строк этого бпока, первый и второй вхоцы счетчика стопбцов первого программного блока соецинены со вторым и четвер тым вхоцами э тог о программного блока, второй выхоц которого поцключен к выхоцу счетчика столбцов первого программного бпока, первый и второй вхоцы второго программного блока соецинены соответственно со вхоцом счетчика строк и счетчика стопбцов в этом бпоке.

Структурная схема устройства прецставпена на чертеже. цифровое устройство цпя решения системы линейных уравнений соцержит матрицу

1 решающих бпоков, арифметический бпок

2, бпок управления 3, бпок 4 вывоца и инцикации,. первый программный блок 5, второй программный блок 6, цопопнитепьную матрицу 7 решающих блоков, бпок 8 сравнения, блок 9 ввоца коэффициентов,. бпок 10 постоянной памяти, бпок 11 оперативной памяти, счетчик 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 ввода коэффициентов в нем вырабатываются сигналы, кото10 рые поступают в блок управления 3 (блок управпения 3 может быть микропрограммным устройством управления).

Бпок управпения 3 начинает работать по определенной программе, вырабатывая ми15 крокоманды. Происходи т прием коэффидиента в арифметический блок 2, который обрабатывает и запоминает коэффициент.

Арифметический бпок 2 выпопняет операцию депения и по опредепенным микрс 20 командам, поступающим с бпока управпения 3, передает эпеменг таблицы множителей в выбранную ячейку. Зпеменг табпицы множигепей поступает на второй эпемент И 19, на который также поступает

25 микрокоманда с бпока управления 3. При совпадении сигнапов и микрокоманды происходит запись элемента через эпемент

ИЛИ в регистр 15, где этот элемент хранится при помощи цикпической перезапи30 си через эпемент НЕ 17 и элемент ИЛИ

18. Микрокоманда, постуиившая HG эпемент И 19 разрешает запись, в тоже время она запрещает перезапись элемента в регистр 15, который в нем находипся

?5 ранее, своим поступпением на вход элемента НЕ 17.

При наборе следующего коэффициента строки счетчик 13 стопбцов первого программного бпока 5 устанавпиввется во вто40 рое положение и вырабатывает сигнап, поступающий на эпемент И 19 соответствующей ячейки, Туда же поступает сигнал со счетчика 12 строк. Точно также коэффициент поступает в арифметический блок

2, который. выполняет деление и передает в выбранный решающий бпок 14 матрицы

1 ячейку по микрокоманде, поступающей с блока управпения 3. Затем заносится таким же образом все коэффициенты Qo

Vl -го первой строки.

Далее выпопняется второй швг.

При вводе коэффициента счетчик 12 строк первого программного бпока 5 устанавпиваегся во второе попожение, а счетчик 13 столбцов в первое попожение, соответственно выбирается в решающем блоке 14 матрицы l ячейка. Арифметический бпок 2 вычисляет значение, которое засыпается в выбранную ячейку способом, опи-60 санным выше. При вводе спедующего коэффициента счетчик 13 стопбцов усганавпивается в попожение 2, выбирается соответствующая ячейка в матрице 1, в которую допжен записаться эпемент. Арифметический бпок 2 производит вычиспения.

Двпее вводятся коэффициенты третьей строки и т.д. до Vl -ой строки.

Как видно из описанного эпементв каж« дой строки обрабатываются совершенно одинаково. Каждая строка обрабатывается также одинаково, топько с ростом 11. (копичества строк) растет копичество цикпов обработки.

Дпя разпичия обработки эпеменгов в строке в устройство введен бпок 8 сравнения. Он сравнивает содержимое счетчика 12 строк и счетчика 13 стопбцов первого программного бпока 5. Когда эти счетчики равны, идет обработка первой группы эпеменгов. Еспи счетчик 12 строк меньше счетчика 13 стопбцов, го ведется обработка эпементов второй группы эпементов, еспи наоборот, то ведется обработка третьей группы эпеменгов. Pe- з;пьтат сравнения с бпока сравнения 8, передается в бпок управпения 3, который вырабатывает опредепенные микрокоманды для арифметического блока 2. Арифметический блок 2 выполняет операции спожения, вычитания, умножения и депения, накоппения и апгебраического спожения. Набор этих операций обеспечивает весь вычиспитепьный процесс. Микропрограммы, выпопняюшие эти операции, могут быть "зашиты в матрицах микропрограмм и микрокоманд.

Эти микрокомвнды могут спужигь как микроподпрограммы дпя основных микропрограмм решения системы уравнений.

Таким образом все коэффициенты системы записаны в матрицу 1 и попучена таблица множителей.

Дпя решения системы уравнении нужно в устройстве иметь известные вектора.

Дпя этого в устройство введеч бпок 11 оперативной памяти, в который с блока 9 ввода коэффициентов вводятся коэффициенты известных векторов. Ввод осуществпяется по микрокомандам, поступающим с бпока управпения 3, который запускается по вводу известного вектора. Бпок 11 оперативной памяти может представпять собой стековые регистры, копичество которых равно порядку системы.

Из попученной; табпицы множитепей, которая записана в матрице 1 решающих бпоков, можно выбрать пюбую специальную матрицу и произвести их умножение.

Умножение матриц производится обычным

624234 способом: строка оцной матрицы умножается на стопбец другой матрицы.

В устройстве прецусмогрен спучай вычиспения вектора В, когца известен .вектор X. В этом спучае произвоцится образование специапьных матриц, а весь про5 цесс умножения матриц анапогичен выше описанному. Такое обратное решение может быть Bcllollr GoBBHo,цпя проверки правильности решения системы уравнений.

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

Устройство является цостаточно эффективным цпя решения системы линейных уравнений. При использовании мегоца прямых решений на основе разпожения матрицы на треугопьные множигепи цостигается

20 существенное сокращение времени вычислений и объема памяти. В этом и закпючается основное прс-имущество прецпагаемого устройства по сравнению с цругими устройствами решения систем пинейных

25 уравнений.

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

1. Цифровое устройство цпя решения системы пинейных уравнений, соцержащее матрицу решающих бпоков, арифметический блок, бпок управпения, блок вывоца и ин-. цикации, первый программный блок и эпемент ИЛИ, причем. первый выхоц арифметического бпока соецинен с первым входом бпока вывоца и инцикации, первый вход блока управпения соецинен со вторым выхоцом арифметического биска, первый вхоц которого подключен к первому выходу бпо40 ка управпения, второй выхоц которого соецинен с первым управпяюшим вхоцом «ажцого из П решающих бпоков, Ipenrn выхоц

2 блока управления поцкпючен «о второму управляющему входу кажцого нз ц реша2 45 ющих бпо«ов, первый информационный вхоц кажцого из и решающих бпоков соединен

2 с третьим выходом арифметического блока, а выхоцы всех р решающих бпоков через элемент ИЛИ подключены ко вгоро50 му вхоцу арифметического блока, четвертый выход бпока управпения соединен с первым и вторым вхоцами первого прог раммного бпока, первый и второй выходы которого поц«пючены ко второму и гре 55 тьему axoqy блока вывода и инцикации, каждый.из выходов первой группы управляющих выхоцов первого программного бпоI

KB соединен со вторым информационным входом соответствующего решающего блока, третий информационный вхоц которого иодкпючен к соответствующему выхоцу во второй группе управпяющих выхоцов первого программного блока, о т и и ч а ю— щ е е с я тем, что, с цепью повышения быстроцействия, в него ввецены бпок постоянной памяти, бпок оперативной памяти, бпок сравнения, бпок ввоца коэффициентов, второй программный бпок, цопопнитепьный элемент. ИЛИ, цопопнитепьная матрица и решающих бпоков, причем первый и информационный вхоц кажцого из И решающих бпоков цопопнигепьной матрицы поцкпючен к четвертому выхоцу арифметического бпока, второй информационный вхоц — к соответствующему выхоцу в первой группе управляющих выхоцов второго программного бпока, третий информационный вхоц — к соответствующему выходу во второй группе управляющих выхоцов второго программного бпока, первый управпяющий вход — к пятому выхоцу блока управления, второй управпяющий вхоц — к шестому выходу блока управпения, а выхоц через цопопнигепьный эпемент ИЛИ— к гре тьему вхоцу ар ифме гического бпока, четвертый ахоп которого соецинен с первым выхоцом бпока ввоца коэффициентов, второй выхоц которого поцкпючен ко второму вхоцу блока управпения, третий выхоц блока ввоца коэффициентов соецинен с первым вхоцом бпока оперативной памя ги, а четвертый выхоц поцкпючен к тре» гьему и четвертому вхоцам первого программного блока, первый и второй выхоцы которого через блок сравнения соединены с третьим вхоцом бпока управпения, сець»мой выхоц которого поцкпючен к первому и второму вхоцам второго программного бпока, а восьмой выхоц блока управления соецинен со вторым вхоцом блока оперативной памяти, выхоц которого поцкпючен к пятому вхоцу арифметического блока, шестой вхоц которого соецинен с выхоцом бпока постоянной памяти, а пятый выхоц арифметического блока поцкпючен ко входу бпока постоянной памяти.

2. Устройство rlo II ° 1г о г ll H B а Io»

III е е с я тем, что кажцый из 2 и решающих бпоков соцержит цва элемента И, элемент НЕ, регистр и эпеменг ИЛИ, причем первый управляющий вхоц решающего блока соединен с первым входом первого элемента И, второй и третий вхоцы которого соединены со вторым и третьим информационными вхоцами решающего бло«а и первым и вторым BxoQBMII вгорого элемента И, третий вхоц когорсчо иодкпючен к первому информационному входу ре624234

1О

:шающего бпока, четвертый вхоц второго эпемента И соецинен с вторым управляющим вхоцом решающего бпока и первым вхоцом эпемента НЕ, выхоц которого соецинен с первым вхоцом элемента ИЛИ

I 5 второй вхоц которого поцкпючен к выхо- цу второго эпемента И, а выхоц элемента

ИЛИ через регистр соединен со вторым вхоцом апемента НЕ и с четвертым вхоцом первого эпемента И, выхоц которого

16 поцкпючен к выхоцу решающего блока.

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

t5 вхоцы счетчика строк первого программного бпока соецинены с первым и третьим вхоцеми первого программного блока, первый выхоц которого поцкпючен к выхоцу счетчика строк этого бпока, первый и второй вхоцы счетчика стопбцов первого npot раммного бпока соецинены со вторым и. четвертым вхоцами этого программного бпока, второй выхоц которого поцкпючен. к выхоцу счетчика стопбцов первого прог раммного бнока, первый и второй вхоцы второго программного бпока соеаинены соответственно со входом счетчика строк и счетчика стонбцов в этом бпоке.

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

1. Авторское свицетецьство СССР

¹ 294144, кп. Су 06 Р 15/32, 1968.

2. Авторское свицетепьство СССР

М 4О4ООО, кп. Я О6 Р 15/32, 197О.

Составитепь Б. Тарасов

Рецактор Н. Каменская Техреду Е. Лавипопич Корректор, С. Гараснних

Заказ 5189/39 Тираж 826 Поцписное

ЦНИИПИ 1 осуиарственного комитета Совета Министров СССР по пенам изобретений и открытий

113О35, Москва, Ж-35, Раущская наб., ц. 4/5

Филиал ППП "Патент", r. Ужгороц, уп. Проектная, 4