Вероятностное устройство для реше-ния систем линейных алгебраическихуравнений

Гесудврственнье кенхтет СССР аа делам хзюбретанхй и аткркте(72) Автор . изобретения В. В. Яковлев Ленинградский ордена Ленина институт инжнероВ"Й + р+ . . В.н.обртОЬЙ(54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Изобретение относится к вычислительной технике и может быть использовано при построении устройств для решения систем линейных алгебраических уравне" ний по методу итераций.Известны вероятностные устройства для решения систем линейных алгебраических уравненийсодержащие преобразователи число-вероятность, блоки умножения и сложения, генератор слу.0 чайных чисел, интеграторы корней, запоминающее устройство для хранения значений коэффициентов и свободных членов систем линейных алгебраических уравнений и-го порядка 1.13,Г 21 и Я.15Недостатком таких устройств является большая аппаратурная сложность, что вызвано необходимостью применения и схем для линейного преобразования число-вероятность.Наиболее близким техническим решением к предлагаемому является вероятностное устройство для решения систем линейных алгебраических уравнений,2.содержащее последовательно соединенные динамические запоминающее устройство, первый блок ключей, блок преобразователей число-вероятность блок регистров сдвига, второй блок ключей, блок умножения, блок сложения, блок интегрирования, третий блок ключей, управляющий вход которого соединен с управляющим входом второго блока ключей и с выходом счетчика, генератор тактовых импульсов, выход которого соединен с управляющим входом первого блока ключей, входом синхронизации блока- регистров сдвига и входом генератора случайных чисел, выход которого подключен к управляющему входу блока преобразователей число-вероятностьблок задержки, входы которого соединены с выходами блока сложения, а выходы - с входами блока умножения.В. этом устройстве процесс вычислений организован в последовательном виде. При этом в динамическом запо45 3 8304 минающем устройстве(ЗУ) хранятся все коэффициенты дф и свободные члены 1 ц (13=123 .и). Процесс"считывания из динамического ЗУ организован так, что на первый блок ключей пере 5 даются в первом такте синхронизации и чисел Ъ (1=1,2,и), во втором такте и коэффициентов о. (1=1,2 р), в третьем такте и коэффициентов с,(1=-12,и) и т,д. В блоке преобра о зователей число-вероятность осуществляется в каждом такте параллельное преобразование и этих чисел в бинарные символы, вероятности появления которых численно равны величинам пре образуемых чисел. После этого символы записываются в блок регистров сдвига, состоящий из и регистров сдвига. После заполнения регистров вероятностными отображениями, что фиксируется во времени процессом переполнения счетчика, происходит выполнение очередной итерации 41.Недостатком этого устройства является низкое быстродействие при вы числении корней системы линейных алгебраических уравнений, что связано с тем,что длительность каждой итерации определяется временем заполнения всех разрядов блока регистров сдвига 30 и вероятностными отображениями чисел,бо. Другими словами каждая К-я итерация выполняется за и тактов частоты генератора тактовых импульсов. 35 Цель изображения - увеличение быстродействия устройства.Поставленная цель достигается тем,. что вероятностное устройство для ре" шения систем линейных алгебраических уравнений, содержащее последовательно соединенные блок динамического запоминания, первый блок ключей, блок преобразователей число-вероятность, блок регистров сдвига, второй блок ключей, блок умножения, блок сложения, блок интегрирования, третий блок ключей, выход которого является выходом устройства, счетчик, выход50 которого соединен с управляющими входами второго и третьего блоков ключей, генератор случайных чисел, выход которого соединен с управляющим входом преобразователей число-вероятность,55 генератор тактовых импульсов, выход которого соединен с управляющим входом первого блока ключей, входом синхронизации блока регистров сдви 00 4га и входом генератора случайных чисел, блок задержки, входы которогосоединены с соответствующим выходамиблока сложения, а выходы - с соответствующими входами блока умножения, дополнительно содержит первыйи второй блоки ьнверторов элемент И,первый и второй элементы ЗАПРЕТ разрешающие входы которых соединены свыходом генератора тактовых импульсов, входы первого блока инверторовсоединены с соответствующими выходами блока задержки, а выходы - с соответствующими входами первой группы входов элемента И, входы входногоблока инверторов соединены с соответ-.ствующими выходами блока преобразователей число-вероятность, а выходы -с соответствующими входами второйгруппы входов элемента И, вьход которого соединен с запрещающими входами первого и второго элементов ЗАПРЕТ, выход первого элемента ЗАПРЕТсоединен с управляющим входом блокадинамического запоминания устройства,а выход второго элемента ЗАПРЕТ - совходом счетчика.1На чертеже представлена блок-схемаустройства.Устройство содержит блок 1 динамического запоминания, вход 2 управления блока динамического запоминания, первый элемент ЗАПРЕТ 3, генератор 4 тактовых импульсов, генератор 5 случайных чисел, счетчик 6,.запрещающий вход 7, первого и второгологических элементов ЗАПРЕТ, первыйблок 8 ключей, блок 9 преобразователей число-вероятность, блок 10 регистров сдвига, второй элемент 11 ЗАПРЕТ,второй блок 12 ключей, блок 13 умножения, блок 14 сложения, блок 15интегрирования, третий блок 16 клю"чей, блок 17 задержки, первый Фюк18 инверторов, элемент И 19, второй блок 20 инверторов,Выходы блока 1 динамического запоминания соединены с выходами первого блока 8 ключей, выходы которого соединены с входами блока 9 преобразователей число-вероятность, выходы которого подключены к входам второго блока 20 инверторов и к входамблока 10 регистров сдвига, выходы которого соединены с входами второгоблока 12 ключей, выходы которого соединены с входами блока 13 умножения,выходы которого подключены к входам8304 блока 14 сложения, выходы которогосоединены с входами блока 17 задержки и с входами блока 15 интегрирования, выходы которого соединены с входами третьего блока 16 ключей, управляющий вход которого соединен с управляющим входом второго блока 12ключей с выходом счетчика 6. Выходгенератора 4 тактовых импульсов соединен с управляющим входом первого 1 Облока 8 ключей, входом синхронизацииблока 1 О регистров сдвига, с разрешающими входами первого и второгологических элементов ЗАПРЕТ 3 и 11и с входом генератора 5 случайных 15чисел, выход которого подключен к управляющему входу блока 9 преобразователей число-вероятность, Выход первого логического элемента ЗАПРЕТ 3соединен с входом 2 управления блока 1, а запрещающий вход - с запрещающим входом второго логическогоэлемента ЗАПРЕТ 11 и выходом логического элемента И 19, первая группавходов которого подключена к выходам 25первого блока 18 инверторов, входыкоторого соединены с выходами блока17 задержки и с входами блока 13 умножения. Вторая группа входов логического элемента И 19 соединена с выходами второго блока 20 инверторов,входы которого подключены к выходамблока 9 преобразователей число-вероятность. Выход второго логического элемента ЗАПРЕТ 11 соединен с входом з 5счетчика 6.(14 У 35=1 где С - длительность тактового интервала генератора тактовыхимпульсов.Появление сомножит"ля(и в ( 2)связано с необходимостью заполнения регистров сдвига в блоке 10.В предлагаемом устройстве время вычислений существенно снижается за счет того, что не в каждой итерации требуется полного заполнения регист-ров сдвига в блоке 10, Действительно как видно из ( ) в случае, если все3отображения хЖ=0 и р =О, то х 0+"1=О, и таким образом ясно, что дальнейшее заполнение регистров лишено смысла и можно перейти к следующей итерации, т.е. снова преобразовать ф в бинарные случайные симУстройство работает следующим образом.По первому импульсу (такту) из генератора 4 тактовых импульсов, первые и чисел (;(1=1,2,л,п) через первый блок ключей 8 передаются на блок 9, состоящий из и преобразователей число-вероятность где осуществляет45 ся их преобразование в бинарные случайные символы (О или 1) с вероятностями появления, численно равными величинам соответствующих преобразуемых чисел 5. Эти символы далее записываются в первые разряды каждого из и- разрядных регистров сдвига блока 10.Одновременно в счетчик 6 емкостью п добавляется единица. По следующему такту генератора тактовых импульсов на выходы блока 1 поступают п чисел ф (=1,2 п) которые после преобразования в блоке 9 преобразователей число-вероятность записываются в СО 6виде вероятностных отображений в первые разряды каждого из регистров сдвига блока 10, причем ранее написанная в них информация передается во вторые разряды регистров. Содержимое счетчика 6 увеличивается на единицу. Этот проц .сс длится до тех пор, покаЯне будут заполнены все п разрядов регистров блока 10 регистров сдвига, причем ранее записанная в них информация передается во вторые разряды регистров, Содержимое счетчика 6 увы личивается на единицу, При этом происходит переполнение счетчика 6. По сигналу переполнения осуществляется передача содержимого регистров блока 10 на блок 13 умножения. При этом как и в схеме известного устройства происходит. реализация зависимости где К - номер итерации;Х - значение корня системы ли 1нейных алгебраических уравнений и-го порядка;О"3 - приведенные коэффициенты1)этой системы.Результат каждой итерации записывается в блок 15 интегрирования, где происходит статистическое усреднение, поступающих бинарных символов в каждой итерации и, таким образом, за К итераций вырабатывается несмещенная оценка корней Х системы алгебраических уравнений.Очевидно, что время вычисления этих оценок равноТ= кп (2)Формула изобретения 20 7 83040 волы. Если в этом случае вероятностные отображения 1 Ь оказываются нуле.выми, то вновть итерация завершается после одного такта генератора тактовых импульсов и т.д. до появления хотя бы одного ненулевого вероятностного отображения из вектора Ь,;, При ;:этом если все отображения Х.,=О и(К+) 3 отображения (Ь=О, то на выходе логического элемента И 19 присутствует О сигнал - логическая 1, который по запрещающему входу 7 первогои второго логических элементов ЗАПРЕТ 3 и 11 пре" пятствует перемещению информации в блоке 1 динамического запоминания и 5 добавлению приращении в счетчик 6. Вероятностное устройство для решения систем линейных алгебраических уравнений, содержащее последовательно соединенные блок динамического запоминания, первый блок ключей, блок 25 преобразователей число-вероятность, блок регистров сдвига, второй блок ключей, блок умножения, блок сложения, блок интегрирования, третий блок ключей, выход которого является вы- ЗО ходом устройства, счетчик, выход которого,соединен с управляющими входами второго и третьего блоков ключей, генератор случайных чисел, выход которого соедйнен с управляющим вхо дом блока преобразователей число-вероятность, генератор тактовых импульсов, выход которого соединен с управляющим входом первого блока ключей, входом синхронизации блока рйгист- фО 0 8ров сдвига и входом генератора случайных чисел, блок задержки, входыкоторого соединены с соответствующимивыходами блока сложения, а выходыс соответствующими. входами блока умножения, о т л и ч а ю .щ е е с я тем,что, с целью увеличения быстродействия, оно содержит первый и второй блоки инверторов, элемент И, первый ивторой элементы ЗАПРЕТ, разрешающиевходы которых соединены с выходом генератора тактовых импульсов, входыпервого блока инверторов соединены ссоответствующими выходами блока задержки, а выходы - с соответствующими входами первой группы элементовИ, входы второго блока инверторовсоединены с соответствующими выходами блока преобразователей число-вероятность, а выходы - с соответствующими входами второй группы элементаИ, выход которого соединен с запрещающими входами первого и второго элементов ЗАПРЕТ, выход первого элемента ЗАПРЕТ соединен с управляющим входом блока динамического запоминанияустройства, а выход второго элементаЗАПРЕТ - со входом счетчика.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРВ 481042, кл. 6 06 С 7/34, 1975,2, Авторское свидетельство СССРУ 633024, кл. О 06 Г 15/36, 1978.3. Авторское свидетельство СССРУ 629541, кл. 6 06 6 7/34, 1978,4. Федоров Р.Ф., Яковлев В,В.Добрис Г.В, Стокастическйе преобразователи информации, Л., "Машиностроение", 1978, рис. 123 (прототип).Составитель О, Майороведактор И. Касарда Техред И,Асталош Коррект илиал ППП Патент, г. Ужгород, ул. Проектна аказ 3804/87 ВНИИПИ по д 113035Тираж 745 Подписноеосударственного комитета ССам изобретений и открытийМосква, Ж-Э 5, Раушская наб.