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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 15/32, 15/6,2="- -0 НИЯ 1 еевВ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБР К АВТОРСКОМУ СВИДЕТЕПЬСТ(56) Авторское свидетельство СССРУ 564638, кл,. С 06 Р 15/32, 1975.Авторское свидетельство СССРВ 811276, кл. С 06 Р 15/32, 1979.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕЛИНЕЙНЫХ УРАВНЕНИЙ Бюп, В 27технической кибернетики ЯО 1411776 57) Изобретение относится к вычислиельной технике и может использоватья при обработке изображений в фоторамметрии. Цель изобретения - повыение быстродействия устройства. С той целью в устройство, содержащее лок 1 памяти коэффициентов, блок 2 амяти неизвестных, распределитель 5 мпульсов, умножитель 4 и накапливающий сумматор 3, введены вычитатели -9, коммутаторы 10, 11, регистры 13, 4, блок 12 буферной памяти, блок 15 равнения, умножитель 16 и группу 7 элементов ИЛИ, 1 з,п. ф-лы, 3 ил.гера 19 и вход элемента И 20, чем разрешается прохождение тактовых импульсов с генератора 21 на вход счетчика 22, в зависимости от состояния которого формируются управляющие сиг-, налы с узла 23 постоянной памяти, Кроме того, сигнал с единичного выхода триггера 19 поступает на управляющие входы коммутаторов О и 11, чем О разрешается выполнение первого шага. 20 По первому тактирующему импульсу,поступающему на вход счетчика 22,5на первом выходе узла 23 постояннойпамяти устанавливается сигнал "Считывание", а на втором - пятом выходах -адрес ячейки блока 1 памяти коэффициентов, содержащего десять ячеек,представляющих собой запоминающееустройство регистрового типа. Приэтом на вход блока 4 умножения поступает коэффициент А. Одновременно сэтим по сигналу "Считывание" с шестого выхода узла 23 постоянной памяти и адресу, который устанавливаетсяна восьмом - десятом выходах узла23 постоянной памяти, из блока 2 памяти неизвестных, который также представляет собой ЗУ регистрового типа,считывается начальное значение неизвестной х, которое через коммутатор10 поступает на вход блока 4 умножения. По следующему тактовому импульсу 35по сигналу с выхода а узла 23 постоянной памяти распределителя в блоке 4умножения осуществляется вычислениепроизведения А.х, которое через коммутатор 11 поступает на вход накапливающего сумматора 3, где по сигналус выхода б узла 23 постоянной памятиосуществляется вычисление суммы А х++ О, При поступлении следующих импульсов на счетчик 22 по адресным иуправляющим сигналам с узла 23 постоянной памяти распределителя вычисления произведений Ву, Сг, Р1происходит аналогично описанному. Врезультате в сумматоре 3 вычисляетсязначение 8 = А х + В у + С г + Рявляющееся невяЛкой точки приближе. ния решения относительно плоскости.Значение поступает в блок 15 сравнения, где по сигналу с выхода Ь узла23 постоянной памяти распределителя5 проверяется условие окончания вычислений,Возможны два случая,Условие 181 8 выполняется, приэтом с блока 15 сравнения в распределитель 5 поступает сигнал, который устанавливает триггер 18 и 19и счетчик 22 в исходное состояние.Условие 1 61 с б не выполняется. Вэтом случае по импульсу, поступающему на вход счетчика 22, на выходахузла 23 постоянной памяти устанавливается адрес ячейки блока 1 памятикоэффициентов, и сигнал "Считывание",по которому извлекается знаковый разряд коэффициента А, который поступает на вход умножителя 16, на другомвходе которого находится значение невязки 8 . В умножителе 16 знаковыеразряды невязки и коэффициентов А перемножаются, а остальные разряды невязки проходят без изменений на входблока 9 вычитания, тем самым выполняется операция по вычислению произведения 6 (зрп А). На входе блока 9вычитания нумерация разрядов числа6 (зп А) сдвинута на два разрядавправо. В результате такого сдвигаосуществляется деление на четыре, таким образом, в блок 9 вычитания поступает число6 (вп А)Одновременно с сигналом с выхода 5 на соответствующих вькодах узла 23 постоянной памяти устанавливается сигнал "Считывание" и адрес ячейки блока 2 памяти неизвестных, при этом значение неизвестной х записывается в регистр 14, с выхода которого поступает в блок 9 вычитания. По сигналу с выхода г узла 23 постоянной памяти осуществляется вычисление нового значения неизвестной х. По следующему тактовому импульсу на соответствующих выходах узла 23 постоянной памяти устанавливается адрес ячейки блока 2 памяти неизвестных и сигнал "Запись" на седьмом выходе узла 23 постоянной памяти, в результате осуществляется запись нового значения не известной х в блок 2 памяти неизвестных.Аналогично вычисляются новые значения неизвестных у, г Нахождение новых значений х, у, г сдвигает точку начального приближения в направлении плоскости, При поступлении очередного импульса сигналом с двадцатого вькода узла 23 постоянной памяти5 1411гтриггер 19 устанавливается в единичное состояние, и единичный сигнал свыхода триггера 19 поступает на управляющие входы коммутаторов 10 и 11,которые коммутируют поступающую навходы информацию для выполнения второго шага, т.е. запрещается прохождение сигналов с блока 2 памяти неизвестных, а прохождение сигналов с бло ка 6 вычитания разрешается.По тактовому импульсу, поступающему на счетчик 22, Формируются адресные и управляющие сигналы и поступаютиз узла 23 постоянной памяти распределителя 5 импульсов в блок 1 памяти коэффициентов, где извлекается значение коэффициента хр, а из блока 2 памятинеизвестных значение неизвестного х, которые поступают на вход блока 6 вычитания. По сигналу с выходаузла 23 постойнной памяти в блоке 6 вычитания определяется разность х-хо, которая через коммутатор 10 поступает в блок 4 умножения, Одновременно с 25 сигналом с выходаузла 23 постоянной памяти по адресным сигналам и сигналу Считывание" с первого выхода узла 23 постоянной памяти иэ блока 1 памяти коэффициентов извлекает О ся значение коэффициента 1/а. Далее по следующему тактовому импульсу сигналом с выхода а узла 23 постоянной памяти в блоке 4 умножения определяется значение произведения 1/а (х-хр), которое поступает на вход мультиплексора 25 блока 12 буферной. памяти., При нулевом сигнале с четвертого выхода регистра 29 сдвига значение произведения 1/а (х-хр) поступает на вход регистра 26, По поступлению сигнала с выхода е узла 23 постоянной памяти распределителя 5 на вход регистра29 сдвига иа первом выходе последнего появляется единичный сигнал, который, пройдя элемент ИЛИ 30 осуществляет запись значения 1/а(х-х ) в регистр 26.Аналогично определяется значение произведения 1/Ь /у-у). Затем сигнал с выхода е узла 23 постоянной памяти поступает на вход регистра 29 сдвига, при этом едииичныи сигнал с второго выхода регистра 29 сдвига через элемент ИЛИ .3 1 и элемент 33 задерж 55 ки разрешает перезапись содержимого регистра 26 в регистр 27, и далее через элемент 32 задержки, время задержки которого больше, чем у элемента 33 задержки, разрешает запись значения 1/Ь(у-у ) в регистр 26. Содержимое регистров 27 и 26 поступает на входы блока 7 вычитания. Одновременно с сигналом с выхода е по адресным и управляющему сигналам с выходов узла 23 постоянной памяти иэ блока 2памяти неизвестных считывается значение неизвестной х, которое записывается в регистр 13,По управляющему .сигналу с выходаж узла 23 постоянной памяти распределителя 5 импульсов в блоке 7 вычитания определяется значение невязки8, которое поступает на вход блока8 вычитания. На входе последнего нумерация разрядов сдвинута на одинразряд вправо, таким образом, осуществляется деление на два, Затем посигналу с выходаузла 23 постоянной памяти вычисляется новое значениенеизвестной х = х - 8 х/2,.По очередному тактовому импульсу,поступающему на счетчик 22 распределителя 5 импульсов на соответствующих выходах узла 23 постоянной памяти, Формируются адресные сигналы исигнал "Запись", по которому значение неизвестной х записывается вблок 2 памяти неизвестных.1Аналогично описанному определяетсязначение произведения 1/с(г-г ).При этом сигнал с выхода е узла 23постоянной памяти поступает на ре"нгистр 29 сдвига, в результате чегоединичный сигнал с третьего выходапоследнего разрешает перезапись содержимого регистра 2 в регистр 28,далее, поступая через. элемент ИЛИ31 на элемент 32 задержки, разрешаетперезапись содержимого регистра 26,т.е. 1/Ъ(у-у), в регистр 27-и,поступая с элемента ИЛИ 31 через эле"мент 32 задержки, разрешает записьзначения произведения 1/с(г-гр) врегистр 26, Значения произведений1/Ь (у-уо) й 1/с (г-гр) поступаютна входы блока 7 вычитания соответственно с регистров 27 и 26 блока регистров.Одновременно с этим по адреснымсигналам и сигналу "Считывание" свыходов узла 23 постоянной памяти изблока 2 памяти неизвестных считывается значение неизвестной у, котороезаписывается в регистр 13, Дальней-,шие операции по вычислению новогозначения переменной у аналогичны описанным операциям по вычислению неизвестной х.Вычисление нового значения неиз 5 вестной г осуществляется следующим образом. По адресным и управляющему сигналам происходит считывание значения г, которое по сигналу с выхода е узла 23 постоянной памяти записы О вается в регистр 13. Одновременно с этим сигнал с выхода е поступает нарегистр 29 сдвига блока 12 буферной памяти, в результате чего единичный сигнал с четвертого выхода регистра 29 сдвига поступает. на вход мультиплексора 25, тем самым разрешая прохождение информации с регистра 28, а также через элемент ИЛИ 31 и элемент 33 задержки разрешает перезапись 20 ,в регистр 27 содержимого регистра 26, и через элемент 32 задержки и элемент ИЛИ 30 разрешает запись в регистр 26 .содержимого регистра 28. Таким образом, на входы блока 25 7 вычитания поступают значения 1/с к(г-гр) и 1/а(х-х ). Дальнейшая работа устройства аналогична описанной. В результате вычислений во втором шаге определяются новые значение неиз ц вестных х, у, г, тем самым точка приближения сдвигается в сторону прямой. Затем выполняется первый шаг.Переход к выполнению первого шага осуществляется следующим образом, Единичный аигнал с выходаи узла 23 постоянной памяти распределителя 5 обнуляет сумматор 3 и, пройдя элемент ИЛИ 24, устанавливает триггер 19 и счетчик 22 в исходное состояние, при 40 этом коммутаторы 10 и 11 возвращаются в первоначальное положение.Описанные первый и второй шаги повторяются до выполнения условия81(б 45Формула изобретения1. Устройство для решения системы линейных уравнений, содержащее блок памяти коэффициентов, блок памяти неизвестных, распределитель импульсов, первый умножитепь, накапливающий сумматор, причем вход коэффициентов системы уравнений устройства подключен к информационному входу блока55 памяти коэффициентов, выход которого подключен к входу множимого первого умножителя, вход начальных значений переменных устройства подключен к информационному входу блока памяти неизвестных, вход запуска устройства подключен к входу запуска распределителя импульсов, первый и второй выходы которого подключены к входам н адреса и записи-чтения соответственно блока памяти коэффициентов и блока памяти неизвестных, о т л и ч а ю - щ е е с я тем, что, с целью увеличения быстродействия, оно содержит с первого по четвертый вычитатели, первый и второй коммутаторы, первьй и второй регистры, блок буферной памяти, блок сравнения, второй умножитель и группу из а элементов ИЛИ, где а - разрядность неизвестных, при этом выход блока памяти неизвестных подклюключен к входу уменьшаемого первого вычитателя, первому информационному входу первого коммутатора, к информационным входам первого и второго регистров и к выходу результата устройства, выход блока памяти коэффициентов подключен к входу вычитаемого, вычитателя и к входу множимого второго умножителя, выход первого вычитателя подключен к второму информационному входу первого коммутатора, выход которого подключен к вхо" ду,множителя первого умножителя, выход которого подключен к информационному входу второго коммутатора, первый выход которого подключен к информационному входу накапливающего сумматора, .выход которого подключен к входу множителя второго умножителя и к первому информационному входу блока сравнения, выход которого подключен к входу сброса распределителя импульсов, второй выход второго коммутатора подключен к информационному входу блока буферной памяти, первый и второй выходы которой подключены к входам умньшаемого и вычитаемого вто- рого вычитателя соответственно, выход которого подключен к входу уменьшаемого третьего вычитателя, выход первого регистра подключен к входу вычитаемого третьего вычитателя, выход которого подключен к первому входу группы элементов ИЛИ, выход второ" го регистра подключен к входу уменьшаемого четвертого вычитателя, выход которого подключен к второму входу группы элементов ИЛИ, выход которой подключен к информационному входу блока памяти неизвестных, выход второго ум Ножителя подключен к входу вычитаемого Четвертого вычитателя, третий выход распределителя импульсов подключен кравляющим входам первого и второгооммутаторов, четвертый и пятый выоды распределителя импульсов подклюены соответственно к синхровходу перого умножителя и к синхровходу наапливающего сумматора, шестой выход аспределителя импульсов подключен к инхровходу блока сравнения и к входу читывания второго регистра, седьмой и восьмой выходы распределителя им,ульсов подключены соответственно к инхровходам первого и четвертого выитателей, девятый выход распределиеля импульсов - к входам считывания ервого регистра и блока буферной паяти, с десятого по двенадцатый выхо О ы распределителя импульсов подключек синхровходам второго и третьего ычитателей и к входу установки в "О" н акапливающего сумматора соответстенно, вход величины точности решения 25 истемы уравнения устройства подклюен к второму информационному входуока сравнения.2. Устройство по и. 1, о т л и -а ю щ е е с я тем, что блок буфер- ЗО ой памяти содержит мультиплексор, ти регистра, два элемента ИЛИ, сдвигающий регистр и два элемента задержк, при этом информационный вход бло" ка буферной памяти подключен к первому информационному входу мультиплексора, выход которого Подключен к информационному входу первого регистра,выход которого подключен к информационному входу второго регистра и кпервому выходу блока буферной памяти,выход второго регистра подключен кинформационному входу третьего регистра и к второму выходу блока буферной памяти, выход третьего регистра подключен к второму информационному входу мультиплексора, входу считывания блока буферной памяти подключен к входу сдвига сдвигающего регистра, первый и второй выходы которого подключены к первым входам первогои второго элементов ИЛИ, третий выходсдвигающего регистра подключен к управляющему входу мультиплексора и квторому входу второго элемента ИЛИ,выход которого подключен к входампервого и второго элементов задержки,четвертый выход сдвигающего регистраподключен к третьему входу второгоэлемента ИЛИ и к входу считываниятретьего регистра, выход первого элемента задержки подключен к .второмувходу первого элемента ИЛИ, выход ко"торого подключен к входу считыванияпервого регистра, выход второго элемента задержки подключен к входу считывания второго регистра.Тираж 704 Подписное ВПИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5