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

 

Изобретение относится к вычислительной технике и может использоваться при обработке изображений в фотограмметрии . Цепь изобретения - повышение быстродействия устройства. С этой целью в устройство, содержащее блок 1 памяти коэффициентов, блок 2 памяти неизвестных, распределитель 5 импульсов, умножитель 4 и накапливающий сумматор 3, введены вычитатели 6-9, коммутаторы 10, 11, регистры 13, 14, блок 12 буферной памяти, блок 15 сравнения, умножитель 16 и группу 17 элементов ИЛИ. 1 з.п. ф-лы, 3 нл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АBTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4182812/24-24 (22) 14.01.87 (46) 23.07.88. Бюп. 9 27 (71) Институт технической кибернетики

AH БССР (72) Е.В.Чернухо, И.П.Кудерко и А.С.Лакерник (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 564638, кл. G 06 F 15/32, 1975.

Авторское свидетельство СССР

Ф 811276, кл. G 06 Г 15/32, 1979. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ

ЛИНЕЙНЫХ УРАВНЕНИЙ

„„ЯБ„„1411776 А1 (д1) 4 G 06 Г 15/32, 15/6,2 = ---.— (57) Изобретение относится к вычислительной технике и может использоваться при обработке изображений в фотограмметрии. Цель изобретения — повышение быстродействия устройства. С этой целью в устройство, содержащее блок 1 памяти коэффициентов, блок 2 памяти неизвестных, распределитель 5 импульсов, умножитель 4 и накапливающий сумматор 3, введены вычитатели

6-9, коммутаторы 10, 11, регистры 13, 14, блок 12 буферной памяти, блок 15 сравнения, умножитель 16 и группу

17 элементов ИЛИ. 1 з,п. ф-лы, 3 ил.

1411776

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

Цель изобретения — повышение быстродействияия ус тр ойства, HA фиг. 1 приведена схема устройства; на фиг. 2 — схема распределителя импульсов; на фиг. 3 — схема блока 10 б уф ер ной памя ти .

Устройство для решения системы ли нейных уравнений содержит блок 1 па, мяти коэффициентов, блок 2 памяти неизвестных, накапливающий сумматор 3, 15 блок 4 умножения, распределитель 5 импульсов, с первого по четвертый блоки 6-9 вычитания, первый 10 и второй 11 коммутаторы, блок 12 буферной памяти, первый 13 и второй 14 регист- 20 ры, блок 15 сравнения, умножитель 16 и группу из а элементов ИЛИ 17, где а — разрядность неизвестных.

Распределитель 5 импульсов содержит первый триггер 18, второй триг- 25 rep 19, элемент И 20, генератор 21, тактовых импульсов, счетчик 22, узел

23 постоянной памяти, элемент ИЛИ 24.

Блок 12 буферной памяти содержит мультиплексор 25, первый 26, второй 30

27, третий 28 регистры, сдвигающий регистр 29, первый 30 и второй 31 элементы ИЛИ, первый 32 и второй 33. элементы задержки.

Устройство позволяет решать следую-35 щую систему линейных уравнений:

I1t«, х = х — ---(sgnA) °

4

6 у = у — — — (sgnB).

4 1

z = z — — —;(sgnC) .

1

---(х-х ) а о

1 — -(z-z ) с . о

Ь

1 — -(z-z ) с о

1 — -(х-х ) . а о

8х х = х —.

8у

У = У

6z

z = z

Далее выполняется первый шаг и так до выполнения условия 18! -6

Устройство для решения системы линейных уравнений работает следующим образом.

Перед началом работы устройства все многоустойчивые элементы находятся в нулевом состоянии, перед началом работы производится запись коэффициентов (3) в блок 1 памяти коэффициентов, а в блок 2 памяти неизвестных заносятся начальные значения х, 11 11 у, z, 1. С подачей сигнала Запуск в распределитель 5 импульсов, который поступает íà S-вход триггера 18, последний устанавливается в единичное состояние. Сигнал с единичного выхода триггера 18 поступает на D-вход триг40 (2) А х+В.у+С ° z+D = 0

6 = А х+В у+С z+D.

1 1 а о b - с (х-х )=--"(у-уо)=: (z-z ) (l) Решением системы линейных уравнений (1) и (2) является точка пересечения прямой (1) и плоскости (2) с заданными коэффициентами

А,В,С,D 1/a,1/Ь,1/с,1,хo yo х . (3) Устройство реализует следующий ал- 50 горитм вычисления корней системы.

На первом шаге определяется невязка точки приближения решений относительно плоскости

При этом производится проверка условия окончания вычислений: где ь — чисюГо, величина которого определяет точность получаемого решения.

При не выполнении условия окончания вычислений определяются новые значения неизвестных

На втором шаге с учетом результата первого шага определяются невязки точки приближения решений относительно прямой:

В результате дальнейших вычислений определяются новые значения неизвестных

1411 176

t гера 19 и вход элемента И 20, чем разрешается прохождение тактовых импульсов с генератора 21 на вход счетчика 22, в зависимости от состояния которого формируются управляющие сиг-, налы с узла 23 постоянной памяти, Кроме того, сигнал с единичного выхода триггера 19 поступает на управляющие входы коммутаторов !О и 11, чем 10 разрешается выполнение первого шага.

По первому тактирующему импульсу, поступающему на вход- счетчика 22, !

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

23 постоянной памяти из блока 2 памяти неизвестных, который также представляет собой ЗУ регистрового типа, считывается начальное значение неизвестной х, которое через коммутатор

10 поступает на вход блока 4 умножения. По следующему тактовому импульсу 35 по сигналу с выхода а узла 23 постоянной памяти распределителя в блоке 4 умножения осуществляется вычисление произведения А.х, которое через коммутатор 11 поступает на вход накапливающего сумматора 3, где по сигналу с выхода б узла 23 постоянной памяти осуществляется вычисление суммы А х+

+ О. При поступлении следующих импульсов на счетчик 22 по адресным и управляющим сигналам с узла 23 постоянной памяти распределителя вычисления произведений В ° у, С ° z D ° 1 происходит аналогично описанному. В результате в сумматоре 3 вычисляется ! значение 8 = А х + В у + С z + D являющееся невяЛкой точки приближения решения относительно плоскости.

Значение поступает в блок 15 сравнения, где по сигналу с выхода В узла

23 постоянной памяти распределителя

5 проверяется условие окончания вычислений.

Возможны два случая.

Условие 181< 8 выполняется, при этом с блока 15 сравнения в распределитель 5 поступает сигнал, который устанавливает триггер 18 и 19 и счетчик 22 в исходное состояние.

Условие i 61 с б не выполняется. В этом случае по импульсу, поступающему на вход счетчика 22, на выходах узла 23 постоянной памяти устанавливается адрес ячейки блока 1 памяти коэффициентов, и сигнал "Считывание", по которому извлекается знаковый разряд коэффициента А, который поступает на вход умножителя 16, на другом входе которого находится значение невязки 8 . В умножителе 16 знаковые разряды невязки и коэффициентов А перемножаются, а остальные разряды невязки проходят без изменений на вход блока 9 вычитания, тем самым выполняется операция по вычислению произведения 6 (sgn А). На входе блока 9 вычитания нумерация разрядов числа

8 (sgn А) сдвинута на два разряда вправо. В результате такого сдвига осуществляется деление на четыре, таким образом, в блок 9 вычитания поступает число

6 (вр А)

Одновременно с сигналом с выхода

5 на соответствующих выходах узла 23 постоянной памяти устанавливается сигнал "Считывание" и адрес ячейки блока 2 памяти неизвестных, при этом значение неизвестной х записывается в регистр 14, с выхода которого поступает в блок 9 вычитания. По сигналу с выхода g, узла 23 постоянной памяти осуществляется вычисление нового значения неизвестной х. По следующему тактовому импульсу на соответствующих выходах узла 23 постоянной памяти устанавливается адрес ячейки блока 2 памяти неизвестных и сигнал

"Запись" на седьмом выходе узла 23 постоянной памяти, в результате осуществляется запись нового значения не. известной х в блок 2 памяти неизвестных.

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

I го выхода узла 23 постоянной памяти

5 1411 г триггер 19 устанавливается в единичное состояние, и единичный сигнал с выхода триггера 19 поступает на управляющие входы коммутаторов 10 и 11, 5 которые коммутируют поступающую на входы информацию для выполнения второго шага, т. е. запрещается прохождение сигналов с блока 2 памяти неизвестных, а прохождение сигналов с бло-10 ка 6 вычитания разрешается.

По тактовому импульсу, поступающему на счетчик 22, формируются адресные и управляющие сигналы и поступают из узла 23 постоянной памяти распреде-15 лителя 5 импульсов в блок 1 памяти кое эффициентов, где извлекается значение коэффициента хр, а из блока 2 памяти неизвестных значение неизвестного х, которые поступают на вход блока 6 вы- 20 читания. По сигналу с выхода q узла

23 постойнной памяти в блоке 6 вычитания определяется разность х-хо, которая через коммутатор 10 поступает в блок 4 умножения. Одновременно с 25 сигналом с выхода узла 23 постоянной памяти по адресным сигналам и сигналу ".Считывание" с первого выхода узла 23 постоянной памяти иэ блока 1 памяти коэффициентов извлекается значение коэффициента i/à. Далее по следующему тактовому импульсу сигналом с выхода а узла 23 постоянной памяти в блоке 4 умножения определяется значение произведения 1/а (х-х ), которое поступает на вход мультиплексора 25 блока 12 буферной. памяти, При нулевом сигнале с четвертого выхода регистра 29 сдвига значение произведения 1/a- (х-хр) поступает на вход регистра 26. По поступлению сигнала с выхода е узла 23 постоянной памяти распределителя 5 на вход регистра 29 сдвига иа первом выходе последнего появляется единичный сигнал, который, пройдя элемент ИЛИ 30„осуществляет запись значения 1/а ° (х-x ) в регистр 26.

Аналогично определяется значение произведения 1/Ь /у-у„). Затем сигнал с выхода е узла 23 постоянной памяти поступает на вход регистра 29 сдвиIIpH 9 ТоМ едииичныи си гнал c BTo рого выхода регистра 29 сдвига через элемент ИЛИ .31 и элемент 33 задерж55 ки разрешает перезапись содержимого регистра 26 в регистр 27, и далее через элемент 32 задержки, время задержки которого больше, чем у элемента

33 задержки, разрешает запись значения 1/Ь ° (у-у ) в регистр 26. Содержимое регистров 27 и 26 поступает на входы блока 7 вычитания. Одновременно с сигналом с выхода е по адресным и управляющему сигналам с выходов узла 23 постоянной памяти иэ блока 2 памяти неизвестных считывается значение неизвестной х, которое записывается в регистр 13.

По управляющему .сигналу с выхода узла 23 постоянной памяти Распределителя 5 импульсов в блоке 7 вычитания определяется значение невязки

8„ которое поступает на вход блока

8 вычитания. На входе последнего нумерация разрядов сдвинута на один разряд вправо, таким образом, осуществляется деление на два. Затем по сигналу с выхода узла 23 постоянной памяти вычисляется новое значение неизвестной х = х — 8 x/2, По очередному тактовому импульсу, поступающему на счетчик 22 распределителя 5 импульсов на соответствующих выходах узла 23 постоянной памяти, формируются адресные сигналы и сигнал "Запись", по которому значение неизвестной х записывается в блок 2 памяти неизвестных.I

Аналогично описанному определяется значение произведения 1/с (z-z ).

При этом сигнал с выхода е узла 23 постоянной памяти поступает на ре.-н гистр 29 сдвига, в результате чего единичный сигнал с третьего выхода последнего разрешает перезапись содержимого регистра 2? в регистр 28, далее поступая через. элемент ИЛИ

31 на элемент 32 задержки, разрешает перезапись содержимого регистра 26, т.е. i/Ъ (у-у„), в регистр 27-и, поступая с элемента ИЛИ 31 через элемент 32 задержки, разрешает запись значения произведения 1/с ° (г-гр) в регистр 26. Значения произведений .

1fb (у-yo) и 1/с (z-z ) поступают на входы блока 7 вычитания соответственно с регистров 27 и 26 блока регистров.

Одновременно с этим по адресным сигналам и сигналу "Считывание" с выходов узла 23 постоянной памяти из блока 2 памяти неизвестных считывается значение неизвестной у, которое записывается в регистр 13. Дальней-, шие операции по вычислению нового

1411776 значения переменной у аналогичны описанным операциям по вычислению неизвестной х.

Вычисление нового значения неиз5 вестной z осуществляется следующим образом. По адресным и управляющему сигналам происходит считывание значения z которое по сигналу с выхода е узла 23 постоянной памяти записы- 10 вается в регистр 13. Одновременно с этим сигнал с выхода е поступает на

I регистр 29 сдвига блока 12 буферной памяти, в результате чего единичный сигнал с четвертого выхода регистра

29 сдвига поступает на вход мультиплексора 25, тем самым разрешая прохождение информации с регистра 28, а также через элемент ИЛИ 31 и элемент 33 задержки разрешает перезапись 20 .в регистр 27 содержимого регистра 26, и через элемент 32 задержки и элемент ИЛИ 30 разрешает запись в регистр 26 .содержимого регистра 28. Таким образом, на входы блока 25

7 вычитания поступают значения 1/ск к(г-гр) и 1/а .(х-х ). Дальнейшая работа устройства аналогична описанной.

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

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

Переход к выполнению первого шага осуществляется следующим образом. Еди-35 ничный аигнал с выхода и узла 23 постоянной памяти распределителя 5 обнуляет сумматор 3 и, пройдя элемент

ИЛИ 24, устанавливает триггер 19 и счетчик 22 в исходное состояние, при 40 этом коммутаторы 10 и 11 возвращаются в первоначальное положение.

Описанные первый и второй шаги повторяются до выполнения условия 61(8.. 45

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

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

55 памяти коэффициентов, выход которого подключен к входу множимого первого умножителя, вход начальных значений

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

io сожителя подключен к входу вычитаемого

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

ы распределителя импульсов подключек синхровходам второго и третьего

ычитателей и к входу установки в "О" н акапливающего сумматора соответстенно, вход величины точности решения 25 истемы уравнения устройства подклюен к второму информационному входу ока сравнения.

2. Устроиство по п. 1, о т л и а ю щ е е с я тем, что блок буфер- gp ой памяти содержит мультиплексор, т и регистра, два элемента ИЛИ, сдвигающий регистр и два элемента задержк, при этом информационный вход бло" ка буферной памяти подключен к первому информационному входу мультиплексора, выход которого Подключен к информационному входу первого регистра, выход которого подключен к информационному входу второго регистра и к первому выходу блока буферной памяти, выход второго регистра подключен к информационному входу третьего регистра и к второму выходу блока буферной памяти, выход третьего регистра подключен к второму информационному входу мультиплексора, входу считывания блока буферной памяти подключен к . входу сдвига сдвигающего регистра, первый и второй выходы которого подключены к первым входам первого и второго элементов ИЛИ, третий выход сдвигающего регистра подключен к управляющему входу мультиплексора и к второму входу второго элемента ИЛИ, выход которого подключен к входам > первого и второго элементов задержки, четвертый выход сдвигающего регистра подключен к третьему входу второго элемента ИЛИ и к входу считывания третьего регистра, выход первого элемента задержки подключен к .второму входу первого элемента ИЛИ, выход которого подключен к входу считывания первого регистра, выход второго элемента задержки подключен к входу считывания второго регистра.

1411776

9.7

Составитель В.Смирнов

Редактор H.Áîáêîâà Техред А.Кравчук Корректор А.Обручар

Тираж 704 Подпис но е

ВПИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 3656/46

Производственно-полиграфическое предприятие, r. ужгород, ул. Проектная, 4