Многоканальное устройство дляРЕшЕНия СиСТЕМ лиНЕйНыХ АлгЕбРАичЕС-КиХ уРАВНЕНий Советский патент 1981 года по МПК G06F17/12 

Изобретение относится к вычислительной технике и может быть применено при построении специализированных и проблемно ориентированных процессов лля решения систем линейных алгебраических уравнений (СЛАУ), Известно.цифровое устройство для решения систем уравнений, построенное на базе интеграторов и содержащее интеграторы коэффициентов, интеграторы свободного члена и интегра торы неизвестных, причем/ выходы ин теграторов коэффициентов каждого столбца соединены с входами интеграторов свободного члена того же столб ца, выходы которых подключены к входам ижгеграторов неизвестных того же столбца и входам интеграторов коэффициентов соответствующих строк Недостатками данного устройства являются большое количество оборудования, обусловленное наличием в устройстве сложных блоков-интеграторов и низкое быстродействие, посколь ку интеграторы обладают инерционностью и вместо исходного алгебра.ического в устройстве решается эквивалентное дифференциальное уравнение с большим временем достижения установившегося состояния. Известно также цифровое устройство для решения СЛАУ, содержащее регистры свободного члена, регистры неизвестных, сумматоры, множительные устройства, схемы совпадения,. схемы сравнения и схемы приема 2. Недостатком этого устройства является большое количество оборудования, так как оно содержит большое число сложных блоков типа сумматоров, множительных блоков. Наиболее близким по технической сущности к предлагаемому является устройство, содержащее сумматоры, реверсивные счетчики, сдвиговые регистры, управляющие входы сдвиговых регистров соединены с управляющей шиной, а выходы - с первыми входами соответствующих сумматоров, объединенных в п-столбцов и п последовательно соединенных одноразрядных сумматоров, управляющие входы одноразрядных сумматоров каждой строки соединены с входом соответствующего реверсивного счетчика, блок анализа, элементы И, ИЛИ, выход п-го одноразрядного сумматора каждого столбца соединен с первым входом элемента ИЛИ, выход элемента ИЛИ соединен с входом (п+1)-го

сдвигового регистра, выход знакового разряда (п+1)-го сдвигового реп JTpa связан с первым входом блока анализа, выход которого соединен с входом еоответствующегЬ реверсивного счетчика, выход (п+1)-го сдвигового регистра соединен с вторым входом блока анализа и через первый элемент И - с вторым входом элемента .ИЛИ и с вторым входом первого одноразрядного Сумматора соответствующего столбца, вторые, входы элементов И всех столбцов и управляющие входы реверсивных счетчиков соединены с управляющей шиной 3.

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

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

На чертеже схематически представлено устройство.

Устройство содержит блоки 1 памяти, сумматоры-2 и 3, реверсивные счетчики 4, триггеры.5 и 6, шифраторы . 7 и 8,

Устройство работает следующим образом.

В 1-ые блоки 1 памяти заносятся коды коэффициентов решаемой СЛАУ,. в Сумматоры 2 заносятся коды свободных членов, а сумматоры 3 и реверсивные счетчики 4устанавливаются в нулевое состояние. Триггеры 5 устанавливаются в состояние,соответствующее знаку невязки, вычисляем мой в сумматорах 2 (на первой итерации это знак свободного члена М- ) . Из блоков 1 памяти через шифраторы 8, управляемые сигналами от триггеров 5 на входы сумматоров 3 поступают коды коэффициентов соответствующих, столбцов матрицы СЛАУ со сдвигом на 6 разрядов влево

( С 1 - Р, Р - разрядность), т.е. в сумматорах 3 вычисляются значения невязок в соответствии со следующей формулой

5 ,a,jU,i«V,

cKfl

где - значение невязок в сумматоре 3 на предыдущей итераЦИИ

U.J- - сигналы состояния триггеров 5, соответствующие знакам невязок t в сумматорах 2; J

,если

Г если ewVo;

q - основная система счисления; fW- значения невязок в сумматорах 2.

Из блоков 1 памяти через шифрато0 , управляемые-сигналами от триггеров б, на входы вычисления сумматоров 2 поступают коды коэффициентов соответствующих строк матрицы СЛАУ со сдвигом на Е разрядов влево (Е 5 другие входы вычитания сумматоров 2 поступают единицы С-го разряда в соответствии со знаками невязок, зафиксированных в триггерах 5, т.е. в сумматорах 2 вычисляются значения невязок в соответствии со

следующей формулой

,.jUifc,-4M

- - значения невязок в сумматорах 2 на к-ой -итерации;

.

fJtl сигналы состояния триггеров . 6, соответствующие знакам невязок €.J в сумматорах 3;

-И

6СЛМ ,

еслм .

. Одновременно с этим, в реверсивных счетчиках 4 происходит формирование кодов искомых неизвестных по следующим зависимостям

Y(+-|) а-2 0 , - -f + U,j- q ,

т.е. в 6-ые разряды реверсивных счетчиков 4 прибавляется иливычитается единица, в зависимости от состояний триггеров 6. Коды коэффициентов строк .- ( 1,2... ,,п)

о решаемой системы уравнений д Ь (i 1,2,,.,,п) хранятся в соответствующих блоках памяти. Перед решением задачи в сумматоры заносятся коды свободных членов , реверсивные счетчики устанавливаются в нулевое состояние. На первой итерации в триггерах фиксируются знаки свободных членов, затем к кодам, содержащимся в сумматорах и являю5 шихся невязками для первой Итерации прибавляются и вычитаются в зависимости от состояния триггеров коды коэффициентов соответствующих строк, сдвинутые на t разрядов ( Б 1 - Р, где Р - разрядность представления чисел в устройстве) в сторону младших -разР55ДОВ.

Одновременно в 6-ый разряд реверсивных счетчиков прибавляется или вычитается единица в зависимости от состояния .триггеров, т.е. в соответствии со знаками невязок. На каждой (к + 1)-ой и-иерацкк вы числения невязок в сумматорах производят в соответствии с фо рмулами

р (),ск -е . W i -i :( Г где .q - основание системы счисления;и - состояние триггеров 5 tta

к-ой итер.ации, причем ,.1 - -(,если О,

+-1,если €. о.

Вычисление искомых не известных на (к+1)-ой итераций производится по фЪрмуле

Х.К+1 + Uf .q«

Метод простой итерации для решения СЛАУ, одной из модификаций которого является реализуемый в устройстве алгоритм сходится, в том случае если коэффициенты решаемой СЛАУ удовлетворяют следующим условиям aiil .2 , т.е. диагональные коэффициенты решаемой СЛАУ ёольше п абсолютной величине суммы всех остальных коэффициентов в строке или столбце матрицы коэффициентов 1 . Однако широкий класс , к которому сводятся задачи, возникающие в прикладной механике/ при обработке экспериментальной информации/ определении коэффициентов корреляции, в задачах теории поля ;И математической физики и ряде других научно-технических задач, не удовлетворяют приведенным выше ограничениям и имеют коэффициенты в диагонали матрицы меньше по абсолютной величине других коэффициентов в строке или столбце,Такие задачи не могут быть решены в известном устройстве.

Предлагаемое устройство реализуе такой алгоритм, который не зависит

|от коэффициентов матрицы СЛАУ,поэтому устройство по своим возможностям приближается к универсальной ЭВМ в рамках решения СЛАУ, но обладает более высокой производительностью и эффективностью обработки информации, что позволяет реализовать быстродействующие и дешевые вычислительные устройства и использовать ах в системах обработки информации в реальном масштабе времени.

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

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

5 системы уравнений, в каждьгй канал введены второй триггер и сумматор, и вторая группа шифраторов, выходы которых соединены с входами второго сумматора, выход которого через

0 второй триггер соединен с входом реверсивного счетчика и с входами .шифраторов первой группы, первые входы шифраторов второй группы в кгокдом кангше соединены с второй груп5пой выходов блоков памяти .соответствующих каналов, вторые входы шифраторов второй группы соединены с выходами первых триггеров соответствующих каналов, выходы первых триг0геров соединены с входом первого суглиатора соответствующего канала.

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

1.Майоров Ф.В Электронные циф- о

5 ровые интегрирующие машины, М., Машгиз, 1962, с. 86-88.

2.Евреинов Э.В. и Прангишвилм И.В. Цифровые автоматы с перестраиваемой структурой {однородные

0 среды), м;, Энергия, 1972,с.195.

3.Авторское свидетельство СССР 543943, кл. G 06 F 15/32,.1975 (прототип).