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

 

OllMCAHNK

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик

< >999063 (б! ) Дополнительное к авт. свид-ву(22)Заявлено 09.07.81 (21) 3338966/18-24 (53)M. Кл. с присоединением заявки,1те

G 06 F 15/36

Геаудеретеенны1 кемнтет

CCCI ве аенем нмеретеннй н ITNllilTNa (23) Приоритет

Опубликовано 23.02.83. Бюллетень Фе 7

{53) УДК 681. 335 (088.8) Дата опубликования описания 23.02.83 (72) Автор. изобретения

К.А.Бабордин

Институт проблем моделирования в энергетик

АН Украинской ССР (71) Заявитель

I (4) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЛУЧАЙНЫХ БЛУЖДАНИЙ

Изобретение относится к вычислительной технике и может быть использовано как специализированное вычислительное устройство, работающее совместно с ЦВМ, для решения задач математической физики методом

Монте-Карло.

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

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

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

Блок задания конфигурации области

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

3 О9906 связан с входом блока вычислен%я

<- орпинат

Епс < вычисления координат содерчт три умножитепя и три идентичные з мкнутые цепи, включающие в себя а, Р сумматоры, ключи и модули аналого" ,ой памяти„ связанные с входами блока задания конфигурации области.

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

RS-триггер. Входы этого . блока соенинены с входами блока вычисления координат (:2).

26

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

r:or,осы прапускания интеграторов блока моделирования изотропного век.— тора и частоты срабатывания аналоговых ключей блока вычисления координат. Кроме того, оно обладает нестабильностью времени выдачи результатов на каждом шаге случайной траеквЂ,oðèè, обусловленную реализующимся

-.ïîñîáîì выбора случайного направле н !r., которая приводит к усложнению управления работой устройства.

Цегью изобретения является повышение быстродействия и точности.

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

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

999063

На фиг.1 приведена блок-схема устройства для моделирования случайных блужданий; на .Фиг.2 - схема блока управления.

Устройство для моделирования случайных блужданий содержит генератор

1 случайных чисел, блоки 2-4 памяти, блоки 5-8 умножения, три сумматора

9- 11, блоки 12-14 памяти, три цифроаналоговых преобразователя 15-,17, блок 18 задания конфигурации области, аналого-цифровой преобразователь 19, блок 20 управления, информационные входы 21-23, выходы 24-26, сигнальный выход 27. Блок 18 задания конфигурации области содержите суммирующе-вычитающих усилителей 28, а также схему 29 выделения минимальной сос-тавляющей из нескольких входных переменных и компаратор 30,выходы которых являются соответственно первым и вторь м выходами блока 18. Генератор 1 случайных чисел имеет первый и второй

Р-разрядные выходы 31 и 32 и третий, четвертый, пятый одноразрядные выходы2

33, 34 и 35. Управляющим входом блока 20 является вход 36. Блок 20 управления содержит элемент И jj, генератор 38 тактовых импульсов„ двоичный счетчик 39, дешифратор 40, RS-триггер 41.

Работа устройства состоит в построении случайных траекторий в про:-цессе решения краевых задач методом

Монте=Карло. Случайные траектории .N должны начинаться в той точке облас. ти, в которой ищется решение задачи.

Причем сама оценка решения зависит от координат точек выхода этих траекторий на границу области. Время 46 получения результата существенно за- . висит от скорости моделирования траекторий. Координаты точек моделируемых траекторий вычисляются по формуле 4S

Для вычисления координат точек последовательности (1) используем соотношения

y,-X. „ 4(Р„. „1УИ сО Ч;

3; = „. „ g (P „) Ми +ajar М; ;=Z.„„ й(p„„) СОЭЦ, (И) в которых значения углов 1 и ф являются случайными величинами, причем угол, равномерно распределенный в интервале (О,ZtC), определяется по формуле

P = %с, где g — равномерно распределенная в интервале (0,1 ) случайная величина.

Закон распределения величины

QE (0,7L) определяется соотношением

cos i(= 1-2, где - равномерно распределенная в интервале (0,1) случайная величина.

Для вычисления значений sin f созЦ используют табличный способ.

Интервал (0,1) разбивают на И=2, Р-" частей и составляют таблицы значений функций sin((/2), cos (М/2) в точках, =(2k-1)/2М; k=1,..., Н, которые зайисывают в блоки постоянной памяти. Для получения случайных,величин sir,9, сов Щ берут Р -разрядное случайное число и, использовав его в качестве адресов выборки для обоих " блоков постоянной памяти, считают значения из соответствующих ячеек. Используют для записи таблиц з1п(® 92)

cos ® /2) блоки 2 и 3 постоянной памяти, адреса считывания из которых .Ф.а о пред еляют ся кодом разрядов выхода .

31 блока 1.

Р„.=Р„. +ш„-Д (р„. „); =1,2, (1)

r"e — последовательность единичм ных изотропных (равновероятных) векторов;

d(p)- минимальное расстояние от точки P до границы области.

Траектории обрываются в -окрест ности границы и координаты точки обрыва используются для вычисления оценки решения задач ..

Величина cos g,ðàâíoìåpío распре-. деленная в интервале (-1, 1) статистически эквивалентна величине

Е10, () где — равномерно распределенная в интервале (0,1) случайная величина;

ы дт1 р- знак, принимающий с одина. ковой вероятностью значения + или которое реализуют табличным способам, и аналогично описанному, т.е. строят таблицу зависимости значений з1пЦ>от р в точках 1 = .(2 <-1)/2М, согласно (4), которую записывают в постоянную,е память, используя блок 4 памяти. Лдрес. считывания определяется кодом.на вы" . ходе 32 генератора 1 случайных чисел.

Координатные приращения из (2) можно записать в виде 15

p++=p =Op, 7 9990

Для определения sin Ч применяют соотношение

° ВМ Ц> = ->/ 1 - <:05 1> Ж - Р

g („=Ь1 И „3(P„- „ >ЧИ 9 СО Ч1;

6 3 =5фи Й (К;,> ) Ми Ч> f Ми 9 ) > ь7.„ = 1р< d(p„„) соьФ где мЯъО; COS3»>0 > что дает воэможность производить опе.рации умножения без учета знаков сомножителей. Знаки приращений

s i с>п,> з1gn з < дп» можно присвоить .после того, как вычислены абсолюте ные значения- приращений, учитывая при этом, что вероятности положительных и отрицательных значений равны 3©

63 8 ней (например для трехсторонней призг мы )<и = 5 ). Задание конфигурации области производится установкой значений коэФфициентов передачи, равных а ; Ь, с а с1 по входам х, У, л, <1, соответствующих суммирующе-вычитающих усилителей 28. устройство для моделирования случайных блужданий работает следующим образом.

По сигналу управления, поступающему (либо от ЦВМ, либо с пульта one ратора).на вход 36, RS-триггер 4 1 переводится в единичное состояние и открывается дрступ тактовых импульсов на вход счетчика 39.

По сигналу С,>, возникающему в момент времени t на выходе дешифрато1 ра 40, в регистры 12-14 памяти запись>ва><)тся коды начальных координат х, у, z, подаваемые на входы устройства 2 1-23. Коды начальных координат, записанные в регистры блоков 12- 14 памяти, преобразуются с помощью цифро-аналоговых преобра-зователей 15-17 в напряжения, которые поступают на входы х у, г блока

18 задания: конфигурации области. .На выходе каждого из суммирующевычитающих усилителей 28 образуются напряжения, равные

Перед началом нахождения решения трехмерной краевой задачи с помощью предлагаемого устройства для моделирования случайных блужданий в заданной точке Ро= (х<>< jî О выпуклой области, образованной совокупностью Фп плоских граней, уравнения которых имеют вид

Ар+Ь <-С,+О =0; =<,й,,в, (5, 1 необходимо произвести задание конфи. гурации области. Для этого уравнение (5 ) записывается в нормализованной форме „+1 +С;, и --О, (6) где A. д..

0 = — 1- b ="-<- с.=

E ) Е) 3 Е

8; ;

-Ж )

Каждой из плоских граней, образующих границу, отводится по одному суммирующе-вычитающему усилителю 28, общее число которых ln равно числу гра6>=OPot о"- 2о+ j>> которые представляют расстояния от начальной точки, траектории

P0 = (>< у zo) до граней обра

О.> зующих ооласть. Установкой соответствующих знаков коэффициентов а

46

Ь, с, d передачи суммирующевычитающих усилителей 28 всегда можно сделать так, чтобы »се они были поло><ительными, пока траектория (1) находится внутри области.

Напряжения d с выходов суммируют ще-вычитающих усилителей 28 поступают на входы схемы 29 выделения минимальной составляющей из нескольких входных переменных, на выходе которой напряжение соответствует минимадьному расстоянию от точ>;и Ро=

<хр, ур, ер)др граней 6 P = Ь(Р ).

Напряжение с выхода схемы 29 выделения минимума прикладывается к входу аналого-цифрового преобразователя 19 и к первому входу компаратора 30, на второй вход которого подается напря жение, равное ширине приграничной

999063

9 полосы, в которой траектории обрываются.

В момент времени t< на трактирую. щий вход С,„ аналого-цифрового преобразователя 19 поступает управляющий импульс С с блока 20 управления, который инйциирует его работу.

В момент времени t на тактирующие входы триггеров генератора 1 случайных чисел поступает управляющий им- 16

:пульс С . По нему на выходах 31 3 r генератора вырабатываются соответственно два P --разрядных случайных числа и три одйоразряднйх случайных числа. Р-разрядные случайные числа, 1$ .поступая на адресные входы блоков 2-4 памяти, вызывают появление b информационных выходах этих блоков кодов значений / cosg/, s in 9/, s in 9, которые поступают на первые входы Ю блоков 5,6.и 8 умножения, На первый вход блока 7 умножения поступает код, образующийся на .выходе 32 генератора

1 случайных чисел.

В момент времени t4 на тактирующие 2$ входы регистров первого и второго сомножителей блока 8 умножения посту.пает сигнал С . Код произведения д(Р) sin Ч поступает на вторые входы блоков 5 и 6 умножения. 39

В момент врсмени на тактирующие входы регистров сомножителей блоков

5-7 умножения поступает сигнал С В результате на выходах этих блоков образуются коды произведений

d(Р„) эЧ (соМ), i(9o) S1 91ЧМ), д(ро)сова>. (q)

В момент времени t< на тактирующие входы регистров слагаемых сумматоров 9-11 поступает сигнал С . При этом в знаковый разряд регистров, в которые записываются приращения (7), поступающие по первым входам сумматоров, записываются одноразряд-. ные коды с выходов 33-35 генератора

1 случайных чисел.

Сигнал C инициирует начало выполнения огерации суммирования в блоках 9-11, на выходах которых образуются коды координат точки Р, Ilo сигналу С начинается новый шаг траектории: РА - Р, . В регистры блоков 12-14 памяти переписываются из регистров сумматоров 9-11- коды

$$ координат точки Р . На выходе блока

29 образуется напряжение d(Pg ), поступающее на вход аналого-цифровогс преобразователя и т.д.

На каждом шаге напряжение d(P ) сравнивается с помощью компаратора

30 с Я . Прид(Р ) F на выходе

27 устройства появляется логическая единица, сигнализирующая об обрыве траектории. В этот момент коды на выходах 24-26, соответствующие коор. динатам точки обрыва траектории поступают в у=тройство, производящее соответствующие вычислейия, a:-.ðèèåð унн ерсальную ЦВИ. На вход а блока управления постула-.

-.::т логи ческая едичгца, переводящая RS-триггер 4 1: в нулевое сос"" тояние. Возникающий на его выходе логический нуль запирает вход двоич" ного счетч а 39.. Траектория закончена. Моделирование следующей траектории начи --:ется с поступления сигнала на вход 36 и повторяется описанная последовательность операций.

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

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

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

99906

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

12 управляющий вход устройства.

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

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

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

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

tf 383054, кл. 6 06F 15/32, 1970.

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

Н 767785, кл. G 06 G 7/ 40 1980.

Составитель А.Иванус

Редактор Л.Филиппова Техред И.Гергель

Корректор М. лароши

Подписное

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

Заказ 1158/73 Тираж 704

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

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