Устройство для моделирования случайных блужданий Советский патент 1983 года по МПК G06F17/18 

(5) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЛУЧАЙНЫХ БЛУЖДАНИЙ

1

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

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

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

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

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

10 краевых задач, которое характеризуется наличием генератора белого шума с тремя некоррелированными каналами,блока моделирования изотропного вектора, блока вычисления корр15динат и блока задания конфигурации области, связанных с цифровым вычислителем.

Блок задания конфигурации области устройства содержит несколько сумми20рующе-вычитающих усилителей, объединенных по соответствующим входам, и связанную с их выходами схему выделения минимума, выход которой связан с входом блока вымисленЙя ;.оордмнат. Блс:к вычисления координат содер три умножителя и три идентичные замкнутые, цепи, включающие в себя сумм.тторы, -клюми и модули аналого ОЙ памяти, связанные с входами блока задания конфигурации области. Блок моделирования изотропного вектора, входы которого соединены с выходами генератора белого шума, содержит три параллельные цепочк последовательно включенных интегр торрв и умножителей, выходы которых подключены к входам сумкомпараторов и мптора, а таюке RS-триггер. Входы этого блока со блока вычислен чинены с входами оординат О 2. Однако известное устройство имеет яизкую точность результатов, обуслов ленную значительным отклонением реализуемой им случайной траектории от идеальной, что вызвано высокой приборной погрешностью выполнения операций умножения, интегрирования и хранения в блоке моделирования изоrrjoriHoro вектора, а также блока вы-, числения координат, низкое быстродействие, аызванное ограниченностью полосы пропускания интеграторов блока иоделирования изотропного вектора и частоты срабатывания аналоговь х ключей блока вычисления координат. Кроме того, оно обладает нестабильностью времени выдачи результатов на каждом шаге случайной траек тории, обусловленную реализующимся способом выбора случайного направле ния, которая приводит к усложнению управления работой устройства. Целью изобретения является повыи.1ение быстродействия и точности. Поставленная цель достигается тем, что в устройстве,содержащем генератор случайных чисел, первый, второй и третий блоки умножения, выходы которых связаны с первыми вхо дами соответственно первого, второго и третьего сумматоров, три элемента И, ВЫХОДЫ которых подключены к первым входам соответственно первого второго и третьего блоков памяти, а выходы первого и третьего блоков памяти соединены с вторыми входами соответствующих сумматор-чв, блок зад ния конфигурации области,первый выход которого подключен к первому вх S 34 ду блока управления, а перый выход блока управления соединен с первым входом к.пюча, аналого-цифровой преобразователь ,, введены четвертый, пятый ишестой блоки памяти5три цифро-аналоговых преобразователя, четвертый блок умножения, причем входы четвертого, пятого и шестого блоков памяти и первый вход третьего блока умножения соединены с соответствующими выходами генератора случайных чисел, а выходы четвертого, пятого и шестого блоков памяти подключены соответствен-ино к первым входам первого, второго и четвертого блоков умножения, выход четвертого блока умножения подключен к вторым входам первого и второго блоков умножения, выходы первого,второго и третьего блokoв памяти через цифро-аналоговые преобразователи подкл 0чены соответствующим входам блоКЗ задания конфигурации области, вто-. рой выход которого соединен с первым входом аналого-цифрового преобразователя, а выход аналого-цифрового преобразователя подключен к вторым третьего и четвертого блоков умножения, второй, третий, четвертый, пятый, шестой и седьмой выходы блока управления соединены соответственно с вторым входом амалого-цифрового преобразователя, с первым входом генератора случайных чисел, с третьим входом четвертого блока , с третьими входами первого, второго третьего блоков умножения, с четвертыми входами трех сумматоров, с пятыми входами трех сумматоров, вторым входом блока управления является управляющий вход устройства. Кроме того, блок управления содержит RS-триггер, генератор тактовых импульсов, двоичный счетчик, дешифратор,:элемент И, причем выход 1триггера подключен к первому входу элемента И, а второй вход соединен с выходом генератора тактовых импульсов, выход элемента И подключен через двоичный счетчик к входу дешифратора, первым и вторым входами блока управления являюtcn первый и второй управляющие входы RS-триггера, первым, вторым, третьим, четвертым, пятым, шестым и седьмым выходами блока управления являются соответственно первый, второй, третий, четвертый, пятый, шестой и седьмой выходы дешифратора. На фиг,1 приведено блок-схема устройства для моделирования слу4aiiHbix блужданий; на .фиг. 2 - схема блока управления. Устройство для моделирования случайных блужданий содержит генератор 1 случайных чисел, блоки 2- памяти, блоки умножения, три сумматора , блоки 12-1t памяти, три цифроаналоговых преобразователя 15-17, блок 18 задания конфигурации области аналого-цифровой преобразователь 13, блок 20 управления, инфррмационные входы 21-23, выходы 2(-2б, сигнальный выход 27. Блок 18 задания конфигурации области содержитШ суммиру юще-вычитающих усилителей 28, а такж схему 29 выделения минимальной сое тавляющей из нескольких входных пере менных и компаратор 30,выходы которы являются соответственно первым и вто рым выходами блока 18. Генератор 1 случайных чисел имеет первыйи второ р-разрядные выходы 31 и 32 и третий, четвертый, пятый одноразрядные 33, 3 и 35. Управляющим входом блока 20 является вход Зб. Блок 20 управления содержит элемент И 37. генератор 38 тактовых импульсов, двоичный счетчик 39, дешифратор 0, RS-триггер 1. Работа устройства состоит в построении случайных траекторий в про цессе решения краевых задач методом Монте- Карло. Случайные траектории должны начинаться в той точке области, в которой ищется решение задачи. П эичем сама оценка решения зависит от координат точек выхода этих траекторий на границу области. Время получения результата существенно зависит от скорости моделирования траекторий. Координаты точек моделируемых траекторий вычисляются по формуле P. Л где 1ш: 1 - последовательность единичных изотропных (равновероятных векторов; dCp)- минимальное расстояние от точки Р до границы области Траектории обрываются в -окрест ности границы и координаты точки обрыва используются для вычисления оценки решения задач ;. 9 3« Для вычисления координат точек оследовательности (1 используем оотношения + a(.P,i,), -,--,( .ta(p,)COS4, в которых значения углов f и являются случайными величинами, причем угол 4 , равномерно распределенный в интервале XО 21С7, определяется по формуле , , где dL равномерно распределенная в интервале (0,1) случайная . . величина. Закон распределения величины Ve (0,fC) определяется соотношением со5Ц) 1-2р, где р - равномерно распределенная в интервале (0,1) случайная величина. вычисления знамений si nip, используот табличный способ. Интервал (0,1) разбивают на частей и составляют таблицы значений функций 51п(1к€/2), cos (116/2) а точках- f (2k-l)/2M; ,... , М, которые записывают в блоки постоянной памяти. Для полученияслучайных .величин , cos If берут р-разрядное случайное число и, использовав его в качестве адресов выборки для обоих блоков постоянной памяти, считают значения из Соответствующих ячеек. Испольчуют для записи таблиц sin(C/2), cos(1ifF/2) блоки 2 и 3 постоянной памяти, адреса считывания из которых определяются кодом разрядов выхода 31 блока 1. Величина cos Ц) ,равномерно распределенная в интервале (-1,1) статистически эквивалентна величине t gVp-P где jb - равномерно распределенная в интервале ,(О , 1) случайная ве. личина; sigyip)- знак, принимающий с одинаковой вероятностью значе+7 Для определения sin применяют отношение .einS -V -cos H-Vl-p , которое реализуют табличным способо аналогично описанному, т.е. строят таблицу зависимости значений р в точках ty (2k-1)/2M, согласно С), которую записывают в постоянну память, используя блок памяти. Ад считывания определяется кодом на вы ходе 32 генератора 1 случайных чисе Координатные приращения из (2) м но записать в виде Д Xi Slg-H а( И1И Ч I С05Ч I; л. 6 СС.,) sin Ц) f siHM ,iQfvi;z.«3CPi-i , . где , .что дает возможность производить оп рации умножения без учета знаков сомножителей. Знаки приращений Istgoy signi j sign можно присвоить .после того, как вычислены абсолютные значения приращений, учитывая при этом, что вероятности положител ных и отрицательных значений равны Рц. . Перед началом нахождения решения трехмерной краевой задачи с помощью предлагаемого устройства для моделирования случайных блужданий в заданной точке Рр (х, j z) выпуклой области, образованной совокупностью )hi плоских граней, уравнения которых имеют вид )C33. JH,2,.«,W, (5) необходимо произвести задание конфи гурлции области. Для этого уравнение (S) записывается в нормализован ной форме ,, (6) А i. . йА Ci b-tlJL c---- i- Ej ) Ej j Е j--. , Каждой из плоских граней, образующи границу, отводится по одному суммирующе-вычитающёму усилителю 28, общее число которых m равно числу гра 38 ней (например для трехсторонней приз|мы W) S ) Задание конфигурации области производится установкой значений коэффициентов передачи, равных , bj, с, d по входам х, у, z, q. соответствующих суммирующе-вычитающих усилителей 28. Устройство для моделирования случайных блужданий работает следующим О Раздм. По сигналу управления, поступаю У (о от ЦВМ, либо с пульта one на вход Зб, RS-триггер 1,1 переводится в единичное состояние и открывается дрступ тактовых импульсов на вход счетчика 39 По сигналу С., возникающему в момент времени t на выходе дешифратора 40 , в регистры 12-1 памяти записыва отся коды начальных координат XQ , Yj. , z, подаваемые на входы устройства 21-23. Коды начальных координат, записанные в регистры блоков 12-11 памяти, преобразуются с помощью цифро-аналоговых преобразователей 15-17 в напряжения, которые поступают на входы х у, z блока 18 задания конфигурации области. .На выходе каждого из суммирующевычитающих усилителей 28 образуются напряжения, равные -- которые представляют расстояния от начальной точки, траектории РО %, УО.,- о Д° граней, образующих область. Установкой соответствующих знаков коэффициентов а, , ч., ij-j передачи суммирующевычитающих усилителей 28 всегда сделать так, чтобы все они были поло хительными, пока траектория (1) находитсявнутри области. Напряжения cQ с выходов суммирующе-вычитающих усилителей 28 поступают на входы схемы 29 выделения минимальной составляющей из нескольких входных переменных, на выхрде которой напряжение соответствует минимальному расстоянию от точци Q Ixo, YD, 2о)ДО граней d(Po). Напряжение с выхода схемы 29 выделения минимума прикладывается к входу аналого-цифрового преобразователя 19 и к первому входу компаратора 30, на второй вход которого подается напряжение б. , равное ширине приграничной 99 лолосы, в которой траектории обрываются. В момент времени 1л на трактирую щий вход С аналого-цифрового преобразователя 19 поступает управляющий импульс С с блока 20 управления, ко торый инициирует его работу. В момент времени t на тактирующи входы триггеров генератора 1 случайных чисел поступает управляющий им;пульс С. По нему на выходах 31-35 генератора вырабатываются соответственно два Р-разрядных случайных и три одноразрядных случайных числа, Р-разрядные случайные числа йоступая на адресные входы блоков 2-k памяти, вызывают появлен не информационных выходах этих блоко кодов значений . sin т/, .sin Ч которые поступают на первые входы блоков 5,6,и 8 умножения. На первый вход блока 7 умножения поступает код образующийся на выходе 32 генератора 1 случайных чисел. В момент врём(5ни t, на тактирующи входы регистров первого и второго сомножителей блока 8 умножения посту пает сигнал . Код произведения d(FJj) sin4 поступает на вторые входы блоков 5 и 6 умножения. В момент времениtc на тактирующие входы регистров сомножителей блоков умножения поступает сигнал СсiВ результате на выходах этих блоков образуются коды произведений e(Po)5iv.H(cos4), 6 (РО )SIM ц )), d(Po)coS4. (7) В момент времени t, на тактирующие входы регистров слагаемых сумматоров 9-11 поступает сигнал С. При этом в знаковый разряд регистров, в которые записываются приращения 7) поступающие по первым входам сумматоров, записываются одноразрядные коды с выходов генератора 1 случайных чисел. Сигнал С.у инициирует начало выполнения операции суммирования в блоках 9-11, на выходах которых образуются коды координат точки Р По сигналу С начинается новый шаг траектории: Р В регистры блоков 12-й памяти переписываются из регистров сумматоров 9-11 коды координат точки Р . На выходе блока 29 образуется напряжение d{P), поступающее на вход аналого-цифрового преобразователя и т.д. На каждом шаге напряжение d(P|) сравнивается с помощью компаратора 30 с е . ПрисЗСР б- на выходе 27 устройства появляется логическая единица, сигнализирующая об обрыве траектории. В этот момент коды на выходах , соответствующие коор динатам точки обрыва траектории , поступают в устройство, ,производящее соответствующие вычислейия, например универсальную ЦВМ. На вход а блока управления поступает логическая единица, переводя- , RS-триггер М в нулевое соетЬяние. 8оз ::4кгющий на его выходе логический нуль запирает аход двоич ноге счетчу .3 39. Траектория закончена. Моделирование следующей траектории начинается с поступления си|- нала на вход 26 и повторяется описанная последовательность операций. Введение новых блоков и свззей между ними позволило повысить точность и быстродействие устройства. Формула изобретения 1. Устройство для моделирования случайных блужданий, содержащее г.енератор случайных чисел, первый, второй и третий блоки умножения, выходы которых связаны-с первыми входами соответственно первого, второго и третьего сумматоров, три элемента И, выходы которых подключены к первым входам соответственно первого, второго и третьего блоков памяти, а выходы первого и третьего блоков памяти соединены с вторыми входами соответствующих сумматоров, блок задания конфигурации области, первый выход которого подключен к первому входу блока управления, а первый выход блока управления соединен с первым входом ключа, аналого-цифровой преобразователь, отличающ е е с я тем, что,с целью повышения быстродействия и точности, в него введены четвертый, пятый и шестой блоки памяти, три цифро-аналоговых преобразователя, четвертый блок умножения, причем входы четвертого, пятого и шестого блоков памяти и первый вход третьего блока умножения соединенй с соответствующими выходами генератора случайных чисел, а выходы четвертого, пятого и шестого блоков памяти подключены соответственно 11 iK первым входам первого, второго и четвертого блоков умножения, выход четвертого блока умножения подключен к вторым входам первого и второго блоков умножения, выходы первого, второго и третье1вэ блоков памяти через цифро-аналоговые преоб разователи подключены к соответству щим входам блока задания конфигурации области, второй выход которого соединен с первым входом аналого-ци рового преобразователя, а выход ана лого-цифрового преобразователя подкЛючен к вторым входам третьего и четвертого блоков умножения, второй третий, четвертый, пятый, шестой и седьмой выходы блока управления соединены соответственно с вторым входом аналого-цифрового преобразователя, с первым входом генератора-случайных чисел, с третьим вхо дом четвертого блока умножения, с третьими входами первого, второго и третьего блоков умножения, с четвер тыми входами трех сумматоров, с пятыми входами трех сумматоров, вторы входом блока управления является 3 12 управляющий вход устройства. 2. Устройство по п.1, о т ли чающееся тем, что блок управления содержит RS-триггер, генератор тактовых импульсов, двоичный счетчик, дешифратор, элемент И, причем выход триггера подключен к первому входу элемента И, а второй вход соединен с выходом генератора тактовых импульсов, выход элемента И подключен через двоичный счетчик к входу дешифратора, первым и вторым входами блока управления являются первый и второй управляющие входы RS-триггера, первым, вторым, третьим, четвертым, пятым, шестым и седьмым выходами блока управления являются соответственно первый, второй, третий, четвертый, пятый, шестой и седь ой выходы дешифратора. Источники информации, ринятые во внимание при экспертизе м ,J;ncf свидетельство СССР , №38305, кл. G06F 15/32, 1970. 2. Авторское свидетельс-J o СССР N 767785, кл. G Об G 7/1,0 1980.

Ч

а

Cj f,

t---t

iT-frl J

israJ

Фиг. 2