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

 

Союз Советских

Социалистических

Республик

О П И С А Н И Е (,,) 830400

ИЗО6РЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6l ) Дополнительное к авт. свид-ву— (22) Заявлено 08. 08. 79 (21) 2813926/18-24 с присоединением заявки М— (23) Приоритет (SI)M K .

G 06 F 15/36

Гфсудврственньв камхтет

СССР

IIo делам хзюбретанхй и аткрнтай (53) УДК 681.3 (088. 8) Опубликовано 15 05 81 ° Бюллетень М 18

Дата опубликования описания 1 7 . 05 .81 (72) Автор изобретения

В. В. Яковлев

Ленинградский ордена Ленина институт инжвнеров" ." " (7! ) Заявитель (54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

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

l5

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

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

В. этом устройстве процесс вычислений организован в последовательном виде. При этом в динамическом запо45

3 8304 минающем устройстве(ЗУ) хранятся все коэффициенты 4 „ 4 и свободные члены

Wq> (i, j=1,2,3...,ï) . Процесс" считывания из динамического ЗУ организован так, что на первый блок ключей пере5 даются в первом такте синхронизации и чисел fb„ (r=1,2...,п), во втором такте и коэффициентов cN (j=l,2...ð), в третьем такте и коэффициентов с, (1=1,2...,п) и т.д. В блоке преобра- 1о зователей число-вероятность осуществляется в каждом такте параллельное преобразование и этих чисел в бинарные символы, вероятности появления которых численно равны величинам пре- 15 образуемых чисел. После этого символы записываются в блок регистров сдвига, состоящий из и регистров сдвига. После заполнения регистров вероятностными отображениями, что фиксируется во времени процессом переполнения счетчика, происходит выполнение очередной итерации 41.

Недостатком этого устройства является низкое быстродействие при вы- 25 числении корней системы линейных алгебраических уравнений, что связано с тем,что длительность каждой итерации определяется временем заполнения всех разрядов блока регистров сдвига 5р и вероятностными отображениями чисел,9 о . Другими словами каждая К-я итерация выполняется за и тактов частоты генератора тактовых импульсов. 35

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

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

50 которого соединен с управляющими входами второго и третьего блоков ключей, генератор случайных чисел, выход которого соединен с управляющим входом преобразователей число-вероятность, 55 генератор тактовых импульсов, выход которого соединен с управляющим входом первого блока ключей, входом синхронизации блока регистров сдви00 4 га и входом генератора случайных чи сел, блок задержки, входы которого соединены с соответствующим выходами блока сложения, а выходы — с соответствующими входами блока умножения, дополнительно содержит первый и второй блоки ьнверторов элемент И, первый и второй элементы ЗАПРЕТ разрешающие входы которых соединены с выходом генератора тактовых импульсов, входы первого блока инверторов соединены с соответствующими выходами блока задержки, а выходы — с соответствующими входами первой группы входов элемента И, входы входного блока инверторов соединены с соответ-. ствующими выходами блока преобразователей число-вероятность, а выходы— с соответствующими входами второй группы входов элемента И, выход которого соединен с запрещающими входами первого и второго элементов ЗАПРЕТ, выход первого элемента ЗАПРЕТ соединен с управляющим входом блока динамического запоминания устройства, а выход второго элемента ЗАПРЕТ вЂ” со входом счетчика.

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

Устройство содержит блок 1 динамического запоминания, вход 2 управления блока динамического запоминания, первый элемент ЗАПРЕТ 3, генератор 4 тактовых импульсов, генератор 5 случайных чисел, счетчик 6,запрещающий вход 7, первого и второго логических элементов ЗАПРЕТ, первый блок 8 ключей, блок 9 преобразователей число-вероятность, блок 10 регистров сдвига, второй элемент 11 ЗАПРЕТ, второй блок 12 ключей, блок 13 умножения, блок 14 сложения, блок 15 интегрирования, третий блок 16 клю" чей, блок 17 задержки, первый Фюк

18 инверторов, элемент И 19, второй блок 20 инверторов.

Выходы блока I динамического запоминания соединены с выходами первого блока 8 ключей, выходы которого соединены с входами блока 9 преобразователей число-вероятность, выходы которого подключены к входам второго блока 20 инверторов и к входам блока 10 регистров сдвига, выходы которого соединены с входами второго блока 12 ключей, выходы которого соединены с входами блока 13 умножения, выходы которого подключены к входам

8304 блока 14 сложения, выходы которого соединены с входами блока 17 задержки и с входами блока 15 интегрирования, выходы которого соединены с входами третьего блока 16 ключей, управляющий вход которого соединен с управляющим входом второго блока 12 ключей с выходом счетчика 6. Выход генератора 4 тактовых импульсов соединен с управляющим входом первого О блока 8 ключей, входом синхронизации блока IO регистров сдвига, с разрешающими входами первого и второго логических элементов ЗАПРЕТ 3 и 11 и с входом генератора 5 случайных IS чисел, выход которого подключен к управляющему входу блока 9 преобразователей число-вероятность. Выход первого логического элемента ЗАПРЕТ 3 соединен с входом 2 управления бло- 2о ка 1, а запрещающий вход — с запрещающим входом второго логического элемента ЗАПРЕТ 11 и выходом логического элемента И 19, первая группа входов которого подключена к выходам 25 первого блока 18 инверторов, входы которого соединены с выходами блока

17 задержки и с входами блока 13 умножения. Вторая группа входов логического элемента И 19 соединена с вы- 30 ходами второго блока 20 инверторов, входы которого подключены к выходам блока 9 преобразователей число-вероятность. Выход второго логического элемента ЗАПРЕТ 11 соединен с входом з5 счетчика 6. где t — длительность тактового интервала генератора тактовых импульсов.

Появление сомножит"ля (ni в (2) связано с необходимостью заполнения регистров сдвига в блоке 10.

В предлагаемом устройстве время вычислений существенно снижается за счет того, что не в каждой итерации требуется полного заполнения регист- ров сдвига в блоке 10. Действительно как видно из (1 ) в случае, если все

j отображения хЖ =0 и ф " =О, то х(К+"1=0, и таким образом ясно, что дальнейшее заполнение регистров лишено смысла и можно перейти к следующей итерации, т.е. снова преобразовать ф в бинарные случайные симУстройство работает следующим образом.

По первому импульсу (такту) из генератора 4 тактовых импульсов, первые и чисел (;(1=1,2.л.n) через первый блок ключей 8 передаются на блок

9, состоящий из и преобразователей число-вероятность где осуществляет\

45 ся их преобразование в бинарные случайные символы (0 или 1) с вероятностями появления, численно равными величинам соответствующих преобразуемых чисел („.. Эти символы далее записываются в первые разряды каждого из иразрядных регистров сдвига блока IO.

Одновременно в счетчик 6 емкостью п добавляется единица. По следующему такту генератора тактовых импульсов на выходы блока 1 поступают и чисел (j=1,2..„n) которые после преобразования в блоке 9 преобразователей число-вероятность записываются в

GO 6 виде вероятностных отображений в первые разряды каждого из регистров сдвига блока IO, причем ранее написанная в них информация передается во вторые разряды регистров. Содержимое счетчика 6 увеличивается на единицу.

Этот проц сс длится до тех пор, пока

Я не будут заполнены все и разрядов регистров блока 10 регистров сдвига, причем ранее записанная в них информация передается во вторые разряды регистров. Содержимое счетчика 6 увы личивается на единицу. При этом происходит переполнение счетчика 6. По сигналу переполнения осуществляется передача содержимого регистров блока

10 на блок 13 умножения. При этом как и в схеме известного устройства происходит. реализация зависимости (,К1) (К+1) + „(К) ) i =("1 1 М 3 !

5=1 где К вЂ” номер итерации;

Х вЂ” значение корня системы ли1 нейных алгебраических уравнений и-го порядка; (3 — приведенные коэффициенты

11) 1 этой системы.

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

Очевидно, что время вычисления этих оценок равно

Т= кп (2) Формула изобретения

7. 83040 волы. Если в этом случае вероятностные отображения 1 оказываются нуле. выми, то вновть итерация завершается после одного такта генератора тактовых импульсов и т.д. до появления хотя бы одного ненулевого вероятностного отображения из вектора Ъ; . При

;:этом если все отображения Х..=О и (к (К+ ) 3 отображения (Ь„ =О, то на выходе ло- . гического элемента И 19 присутствует i0 сигнал — логическая 1, который по запрещающему входу 7 первого и второго логических элементов ЗАПРЕТ 3 и 11 препятствует перемещению информации в блоке 1 динамического запоминания и is добавлению приращении в счетчик 6.

Вероятностное устройство для решения систем линейных алгебраических уравнений, содержащее последовательно соединенные блок динамического запоминания, первый блок ключей, блок 25 преобразбвателей число-вероятность, блок регистров сдвига, второй блок ключей, блок умножения, блок сложения, блок интегрирования, третий блок ключей, выход которого является вы- 30 ходом устройства, счетчик, выход которого,соединен с управляющими входами второго и третьего блоков ключей, генератор случайных чисел, выход которого соедйнен с управляющим вхо- 35 дом блока преобразователей число-вероятность, генератор тактовых импульсов, выход которого соединен с управляющим входом первого блока ключей, входом синхронизации блока регист0 8 ров сдвига и входом генератора слу-. чаиных чисел, блок задержки, входы которого соединены с соответствующими выходами блока сложения, а выходыс соответствующими, входами блока умножения, о т л и ч а ю.щ е е с я тем, что, с целью увеличения быстродействия, оно содержит первый и второй блоки инверторов, элемент И, первый и второй элементы ЗАПРЕТ, разрешающие входы которых соединены с выходом генератора тактовых импульсов, входы первого блока инверторов соединены с соответствующими выходами блока задержки, а выходы — с соответствующими входами первой группы элементов

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

И, выход которого соединен с запрещающими входами первого и второго элементов ЗАПРЕТ, выход первого элемента ЗАПРЕТ соединен с управляющим входом блока динамического запоминания устройства, а выход второго элемента

ЗАПРЕТ вЂ” со входом счетчика.

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

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

В 481042, кл. G 06 С 7/34, 1975.

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

У 633024, кл. G 06 F 15/36, 1978.

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

У 629541, кл. G 06 G 7/34, 1978.

4. Федоров P.Ô., Яковлев В.В.

Добрис Г.В. Стокастическйе преобразователи информации, Л., "Машиностроение", 1978, рис. 123 (прототип).

830400

Составитель О. Майоров

Редактор И. Касарда Техред И.Асталош Коррект

Заказ 3804/87 Тираж 745 Подписное

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

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

Филиал ППП Патент", r. Ужгород, ул. Проектная, 4