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

(Л

с:

4

tsaak

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

Цель изобретения - поэьпиение быстродействия устройства.

НА фиг, 1 приведена схема устройства; на фиг. 2 - схема распределителя импульсов; на фиг. 3 - схема блока буферной памяти.

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

S ,

где - чис;Го, величина которого определяет точность получаемого решения.

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

X X (sgnA);

У У -(sgnB).,

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

z

(sgnC) .

Ha втором шаге с учетом резупьта

точки приближения решений относител но прямой:

блок 4 умножения, распределитель 5 импульсов, с первого по четвертьй блоки 6-9 вычитания, первый 10 и второй 11 коммутаторы, блок 12 буферной памяти, первый 13 и второй 14 регист-20 первого шага определяются невязки

ры, блок 15 сравнения, умножитель 16 и группу из а элементов ИЛИ 17, где а - разрядность неизвестных.

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

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

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

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

X X

-l-(x-x,)-l-(y-yo)-i-(z-z,) (1)

, A-x-1-B-y+C-z+D О

(2)

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

A,B,C,D 1/а,1/Ь,1/с,1,х,у,гд. (3)

Устройство реализует следующий алгоритм вычисления корней системы.

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

& А Х+В.у+С «z+D.

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

z

(sgnC) .

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

точки приближения решений относительно прямой:

первого шага определяются невязки

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

X X

у у - -т;Sy

2

40

Z Z - -гSz

Т

Далее вьтолняется первый шаг и так до вьшолнения условия iSl -Б

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

Перед началом работы устройства все многоустойчивые элементы находятся в нулевом состоянии, перед началом работы производится запись коэффициентов (3) в блок 1 памяти коэффициентов, а в блок 2 памяти неизвестных заносятся начальные значения х, у, Z, 1. С подачей сигнала Запуск в распределитель 5 импульсов, кото- рьш поступает на S-вход триггера 18, последний устанавливается в единичное состояние. Сигнал с едини:чного выхода триггера 18 поступает на D-вход триг0

5

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

По первому тактирующему импульсу, поступакицему на вход счетчика 22, на первом выходе узла 23 постоянной памяти устанавливается сигнал Считывание, а на втором - пятом выходах - адрес ячейки блока 1 памяти коэффициентов, содержащего десять ячеек, представляюпщх собой запоминающее устройство регистрового типа. При этом на вход блока 4 умножения поступает коэффициент А. Одновременно с этим по сигналу Считывание с шестого выхода узла 23 постоянной памяти и адресу, который устанавливается на восьмом - десятом выходах узла 23 постоянной памяти, из блока 2 памяти неизвестных, который также представляет собой ЗУ регистрового типа, считывается начальное значение неизвестной X, которое через коммутатор 10 поступает на вход блока 4 умножения. По следующему тактовому импульсу по сигналу с выхода а узла 23 постоянной памяти распределителя в блоке 4 умножения осуществляется вычисление произведения А«х, которое через ком-

мутатор 11 поступает на вход накапливающего , сумматора 3, где по сигналу с выхода б узла 23 постоянной памяти осуществляется вычисление суммы А Х+ + 0. При поступлении следующих импульсов на счетчик 22 по адресным и управляющим сигналам с узла 23 постоянной памяти распределителя вычисления произведений В-у, C-z, D-l происходит аналогично описанному. В результате в сумматоре 3 вычисляется значение + B y + C-z + D,/ являющееся невяЗкой точки приближения решения относительно плоскости. Значение поступает в блок 15 сравнения, где по сигналу с выхода Ь узла 23 постоянной памяти распределителя 5 проверяется условие окончания вычислений.

Возможны два случая. Условие liSl.6 выполняется, при этом с блока 15 сравнения в распределитель 5 поступает сигнал, Kofo- рый устанавливает триггер 18 и 19 и счетчик 22 в исходное состояние. Условие I (Si сЕ не вьшолняется. В этом случае по импульсу, поступающему на вход счетчика 22, на выходах узла 23 постоянной памяти устанавливается адрес ячейки блока 1 памяти коэффициентов, и сигнал Считывание, по которому извлекается знаковьй разряд коэффициента А, который поступает на вход умножителя 16, на другом входе которого находится значение невязки S . В умножителе 16 знаковые разряды невязки и коэффициентов А перемножаются, а остальные разряды не- вязки проходят без изменений на вход блока 9 вычитания, тем самым выполняется операция по вычислению произведения 5 (sgn А) . На входе блока 9

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

тупает число

0

Одновременно с сигналом с выхода Ь на соответствующих выходах узла 23 постоянной памяти устанавливается

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

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

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

По тактовому импульсу, поступающему на счетчик 22, формируются адресные и управляющие сигналы и поступают

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

25

30

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

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

45

50

55

5j( , которое поступает на вход блока 8 вычитания. На входе последнего нумерация разрядов сдвинута на один разряд вправо, таким образом, осуществляется деление на два. Затем по сигналу с выхода узла . 23 постоянной памяти вычисляется новое значени неизвестной х х -5х/2,

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

. ;

Аналогично описанному определяетс значение произведения 1/C (z-Zp), При этом сигнал с выхода е узла 23 постоянной памяти поступает на гистр 29 сдвига, в результате чего единичный сигнал с третьего выхода последнего разрешает п ерезайись содержимого регистра 27 в регистр 28, далее, поступая через. элемент ИЛИ 31 на элемент 32 задерж1си, разрешает перезапись содержимого регистра 26, т.е. 1/Ь(у-ур), в регистр 27-и, поступая с элемента ИЛИ 31 через эле мент 32 задержки, разрешает запись значения произведения 1/с«(г-2д) в регистр 26. Значения произведений 1/Ь (у-Уо) и 1/c-(z-Zg) поступают на входы блока 7 вычитания соответст венно с регистров 27 и 26 блока реги стров.

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

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

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

25

30

2040

45

0

5

5j( , которое поступает на вход блока 8 вычитания. На входе последнего нумерация разрядов сдвинута на один разряд вправо, таким образом, осуществляется деление на два. Затем по сигналу с выхода узла . 23 постоянной памяти вычисляется новое значение неизвестной х х -5х/2,

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

. ;

Аналогично описанному определяется значение произведения 1/C (z-Zp), При этом сигнал с выхода е узла 23 постоянной памяти поступает на гистр 29 сдвига, в результате чего единичный сигнал с третьего выхода последнего разрешает п ерезайись содержимого регистра 27 в регистр 28, далее, поступая через. элемент ИЛИ 31 на элемент 32 задерж1си, разрешает перезапись содержимого регистра 26, т.е. 1/Ь(у-ур), в регистр 27-и, поступая с элемента ИЛИ 31 через элемент 32 задержки, разрешает запись значения произведения 1/с«(г-2д) в регистр 26. Значения произведений 1/Ь (у-Уо) и 1/c-(z-Zg) поступают на входы блока 7 вычитания соответственно с регистров 27 и 26 блока регистров.

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

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

Вычисление нового значения неизвестной Z осуществляется следующим образом. По адресным и управляющему сигналам происходит считьшание значения 2, которое по сигналу с выхода е узла 23 постоянной памяти записы- Бается в регистр 13, Одновременно с этим сигнал с выхода е поступает на регистр 29 сдвига блока 12 буферной памяти, в результате чего единичный сигнал с четвертого выхода регистра 29 сдвига поступает.на вход мультиплексора 25, тем самым разрешая прохождение информации с регистра 28, а также через элемент ИЛИ 31 и элемент 33 задержки разрешает перезапись .в регистр 27 содержимого регистра 26, и через элемент 32 задержки и элемент ИЛИ 30 разрешает запись в регистр 26 .содержимого регистра 28, Таким образом, на входы блока

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

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

Переход к выполнению первого шага осуществляется следующим образом. Еди ничный сигнал с выходам узла; 23 постоянной памяти распределителя 5 обнуляет сумматор 3 и, пройдя элемент Ида 24, устанавливает триггер 19 и счетчик 22 в исходное состояние, при этом коммутаторы 10 и 11 возвращаются в первоначальное положение.

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

iSlcg,

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

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

Сожителя подключен к входу вычитаемого Четвертого вычитателя, третий выход : аспределителя импульсов подключен к управляющим входам первого и второго 1соммутаторов, четвертый и пятый выходы распределителя импульсов подключены соответственно к синхровходу пер 1ЮГО умножителя и к синхровходу на- 1сапливающего сумматора, шестой выход )аспределителя импульсов подключен к синхровходу блока сравнения и к входу (;читьтания второго регистра, седьмой и восьмой выходы распределителя им- 1 1ульсов подключены соответственно к синхровходам первого и четвертого вы- Еитателей, девятый выход распределителя импульсов - к входам считывания первого регистра и блока буферной памяти, с десятого по двенадцатый выхо- ды. распределителя импульсов подключе- 1гы к синхровходям второго и третьего иычитателей и к входу установки в О накапливающего сумматора соответственно, вход величины точности решения системы уравнения устройства подключен к второму информационному входу блока сравнения.

Фце.г

Фиг.З