УСТРОЙСТВО КОНЦЕНТРИЧЕСКОГО БЛУЖДАНИЯ Советский патент 1973 года по МПК G06F17/13 

1

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

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

Цель изобретения - повысить точность. Эта цель достигается тем, что устройство содерЖЕГ регистр радиуса, датчик равномерно распределенных случайных чисел, дополнительный регистр, блок выбора направления блуждания, два дешифратора, регистр выдачи и блок разделения, выход которого соединен ео входом сумматора, первый вход - с выходом первой схемы совпадения, второй вход-с выходом второй схемы совпадения, а третий - с выходам третьей схемы совпадения, к нервому входу которой подключен выход первой линии задержки, а ко второму - вход четвертой схемы совпадения и выход пятой схемы совпадения, первый вход которой соединен с выходом датчика равномерно распределенных случайных чисел, а второй - с выходом первого дешифратора, ко входу которого подключен выход регистра радиуса и первый вход второго дешифратора, выход которого соединен с первым входом регистра выдачи, а второй вход -с выходом дополнительного ре гистра, к первому входу которого подключен ,ыход четвертой схемы совпадения, а ко вто рому - первый выход генератора тактовых 1Мпульсов, второй вход регистра выдачи, вход первой линии задержки, нервый вход шестой схемы совпадения, первый вход второй схемы совпадения н первый вход блока выбора нэправления блуждания, выход которого соединен с третьим входом третьей схемы совпадения и нервым входом первой схемы совпадения, ко второму входу которой подключен выход регистра выдачи, а к третьему - выход второй линии задержки, вход которой соединен со вторым выходом генератора тактовых импульсов, со вторым входом блока выбора нанравления блуи дания, со вторым входом четвертой схемы совпадения, вторые входы второй и шестой схем совладения соединены соответственно со входами устройства.

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

Устройство концентрического блуждания содержит регистр радиуса /, датчик равномерно распределенных случайных чисел 2, сумматор 3, представляющий собой регистрсумматор переменной структуры, схемгу совпадения 4, осуществляющую опрос датчика случайных чисел, схему совпадения 5 на три входа, осуществляющую занесение приращенмя по одной из координат, дополнительный регистр 6, фиксирующий ход датчика для второго такта блуждания, блок выбора нанравления блуждания 7, состоящий из трех одноразрядных датчиков -случайных чисел, трех триггеров и схем совпадения, выбирающий направление блуждания за два такта с вероятностью -, дешифраторы 8 и 9, регистр вы8дачи 10, выдаюпдий числа второго такта, схему совпадения 11, блок разделения 12, схемы совпадения 13, 14 н 15, линии задержки 16, 17 и генератор тактовых импульсов 18. В процессе вероятностного блуждаиия частица совершает равномерное случайное блуждание с вероятностью переходов, равной 1/4 по узлам сеточной области до попадания в один из граничных узлов. Одним из приемов ускорения сходимости решения для вероятностных моделей является тот факт, что решение уравнения Лапласа в любом внутреппем узле области равно среднему арифметическому его значений на любой окружности с центром в этой точке. Поэтому случайные блуждания, которые начинаются в некоторой точке, будут пересекать окружность с центром в этой точке с одинаковой вероятностью в любом1 направлении. В результате такого блуждания траектория за один скачок оказывается на окружности, лежаще внутри области с центром в данной начальной точке. Годится любая окружность, ее следует выбирать по возможности наибольшей, принадлежащей исследуемой области. Если необходимо найти решение уравнения Лапласа в точке.4 (фиг. 2), строится окружность с центром в точке А с максимальным радиусом, при котором эта окружность епде принадлежит области. Окружность разбивается на п одииаковы.х дуг, и моделируется случайное по.падаиие с вероятностью /п на одну из этих дуг. На этой дуге берется точка Л,, и с центром в этой точке Опять строится максимальиая окружность, разыгрывается случайных выход на границу этой окружности и т. д. Повторение таких процессов порождает последовательность, сходящуюся к границе области. Из фиксироваииой начальной точки процесс производится N раз, среднее арифметическое случай.цых граничных значений является решением уравнения Лапласа для точки А. Такой способ блуждания требует гораздо меньшего числа шагов, чем моделирование блуждания по всем узлам сеточной области, следовательно, имеет лучшую сходи.мость, и его реализация занимает на цорядок меньше машинного времени. Предлагаемое устройство концентрического блуждания позволяет из данной начальной точки, являющейся центром наибольшей окружности, расположенной внутри исследуемой области, за два такта (одии переход) попадать в любую точку окружности с одииаковой вероятностью. Па фиг. 3 и 4 показаны окружности с радиусами от двух до десяти клеток и их аппроксимации сеткой с квадратными ячейками (нолной индукцией все ноложепия раснростоа 1яются для окружностей любого радиуса), п - число сеточных узлов, аппроксимирующих окружность. При осуществлении одного перехода блуждающей частицы из центра круга за два такта, вероятность попадания в любой из аппроксимирующих окружность узлов одинакова и равна 1//г, т. е. траектория блуждания пересекает окружность в любом направлении с одипаковой вероятностью. Пусть наибольшая окружность с центром в данной начальной точке области, для которой ищется решение задачи Дирихле, имеет радиус . Из фиг. 2 видно, что окружность такого радиуса аппроксимируется двадцатью узлами я 20, поэтому вероятность попадания в любой из этих 20 узлов должна быть одинакова и равна 1/20. Рассмотрим алгоритм. 1 такт. Датчик равнол5ерно распределяемых случайных чисел вырабатывает случайные числа Ri в интервале с вероятностью по одному из четырех направлении ±х. ±г/. Таким образом, вероятность появления случайного числа по одному -из четырех направлений в первом такте равна i. - L л 5 4 20 П такт. Во втором такте частица перемещается только по одному из двух направлений ±х, +У, перпеидикулярно выбранному в первом такте, т. е. с вероятностью Р - выбирается направление блуждания, а с вероятностью единица вырабатывается число, перебрасывающее траекторию на окружность. Вероятность иаступлсния совместного события, заключающегося в том, что за два тарста блуждающая частица оказывается па окружности, равна произведению вероятностей обоих тактов: j,j L А,. . 2 40 Получеиная вероятность не окопчательна, так как в любую из 20 точек на окружности можно попасть двумя путями: например в точку Л (фиг. 2, 3) - выработав в первом такте единицу по направлению , а во втоpOMi-число четыре но направлению , или же выработав четверку по пути в первом такте и число один ло пацравлению х БО втором. Па фиг. 2, 3 показаны все варианты попаДания на любой узел окружности, в которых

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

Р Р, -.

20

Окружности большего радиуса аппроксимируются сложнее. Например при г 9, окружность (фиг. 3) аппроксимируется п 48 узлами. В первом такте с вероятностью вырабатываются случайные числа в интервале от нуля до одиннадцати по одному из четырех направлений, а втором - но одному из двух направлений образуются неслучайные числа, такие, что траектория блуждания попадает на одну из 48 точек, лежащнх на окружности. Например, если первое случайное число 1, то второе неслучайное - 9 нли если первое 9, то второе i и т. д. Вероятность попадания иа окружность одинакова и равна для г 9.

1-248

12

Работа предлагае:.юго устройства заключается в следующем. Нервьш тактовым импульсом с генератора 18 координата иачалыюй точки (нентр окружности) в параллельном коде заносится в сумматор 3, а величнна радиуса записывается в регистр /.

Блок 7 выбирает одно нз четырех направлений блуждания (±х, ±у}, а дешифратор 8 коммутирует соответствующее радиусу количество разрядов датчика. Так, если г -4, датчик будет вырабатывать случайные числа в интервале от О до 4, если , датчик вырабатывает числа от О до 5 и т. д., как ноказаио в таблицах на фиг. 3 и 4.

Код случайного числа с датчика 2 через схему совпадения 5 подается в сумматор 3 для изменения адреса по одному нз вьюраншпх блоком 7 иаправлепию.

Во втором такте код датчика поступает через регистр 6 в дешифратор 9, на другие входы которого занесена величина радиуса с регистра 1.

На выходе дещифратора 9 возбуждается одна из HJnn, которая выбирает определенны код числа в регистре 10.

Во втором такте блок 7 выбирает ianpaRлеиие блуждания с вероятностью 1/2 по олной координате. Так, если в первом такте блуждание произошло по координате ±-v (или ±у, то во втором неслучай:1ый код с

регистра 10 через схему совпадения 11 поступит в сум:матор 3 как прираи ение по координате ±у ( ±.v).

Следовательно, к концу второго такта блуждающая частица оказывается на границе окружности радиуса г, зафиксированного на регистре 1.

Таким образом, устройство позволяет осун ествить равновероятностное блуждание за два такта.

Предмет изобретения

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

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

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

первый вход второго дешифратора, выход которого соединен с первым входом регистра выдачи, а второй вход - с выходом дополнительного регистра, к первому входу которого подключен выход четвертой схемы совпадения, а ко второму - первый выход генератора тактовых 1 мпульсов, второй вход регистра выдач, вход первой линии задержки, первый вход шесто схемы совпадеипя, первьи; вход второй совиаденпя и первый вход блока B ii6opa направленпя блужда1 пя, которого соед 1;1еи с третьим входом третьей совпаде; я и первым входом nepBoii схемы совпадения, ко второму входу KOTOpoii подключен выход рег 1стра выдачи, а к третьему - выход BTOpoii задержк, вход которой соеди ;ен со вторым выходом генератора тактовых импульсов, со вторым входом блока вьгбора 1аправле 1 я блун дания, со вторыл входом четверто совпадення,

вторые входы второй i шесто схем совпадения соедн 1е Ы соответствепно со входами устпойства. -2 р....1 iz-г f , n tS; 0-5 11-5 п-г. tJ-I /2-2 J.11.7-1 -4 4 г 4, /7 2/Г S 0да- :/ Ч:-7IZ-J П- M . ,. 1 P-j- - -7-2- 5. , г--5,л--М, 0-5 I ,Ж, 5|e/2-5 ./4-J , I b.,-2h- . f.. г--Б,п--32} 2-7 -11-7.13 8.2 l7-1l9.-, ik6-l5-5. I 6 f l5-5 4-/-z i/O 2 r-.8,.-, 0-8, 1-8.12-8 13-7 . 8-Т19,-2Ч10.г,/4-7 . Ь-5 / 7-/ 16-5 P--1 1 44