Устройство концентрического блуждания

 

О П

ИЗОБРЕТЕНИЯ т;оюз Советских

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

Республик

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

++ &

Зависимое от авт. свидетельства ¹

Заявлено 18Х.1970 (№ 1440204/18-24) с присоединением заявки №

Приоритет

Опубликовано 23Х.1973. Бюллетень ч" 23

Дата опубликования описания 05.1Х.1973.Ч. Кл. G 06f 15 32

Комитет по лелем изобретений н открытий при Совете Министров

УДК 681.3:519.2(088.8) ссср

Авторы изобретения

В. С. Гладкий, А. П. Уриков и Н. В. Урикова

Морской гидрофизический институт AH Украинской ССР

Заявитель

УСТРОЙСТВО КОН ЦЕНТРИ Ч ЕСКОГО БЛУЖДАНИЯ

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

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

Цель изобретения — повысить точность, Эта цель достигается тем, что устройство содержит регистр радиуса, датчик равномерно распределенных случайных чисел, дополнительный регистр, блок выбора направления блузкдания, два дешифратора, регистр выдачи и блок разделения, выход которого соединеll c() входом сумматора, первый вход — с выходом нервои схемы совпадения, второй вход в с выходом второй схемы совпадения, а третий— с выходом третьей схемы совпадения, к первому входу которой подключен выход первой линии задержки, а ко второму — вход четвертой схемы совпадения и выход пятой схемы совпадения, первый вход которой соединен с выходом датчика равномерно распределенных случайных чисел, а второй — с выходом перваго дешифратора, ко входу которого подключен выход регистра радиуса и первый вход второго дешифратора, выход которого соединен с первым входом регистра выдачи, а второй вход — с выходом дополнительного регистра, к первому входу которого подключен вылод четвертой схемы совпадения, а ко вто* рому — первый выход генератора тактовых т мпульсов, второй вход регистра выдачи, вход

1О первой линии задержки, первый вход шестой схе,ты совпадения, первыи вход второй схемы совпадения и первый вход блока выбора на: правления блуждания, выход которого соединен с третьим входом третьей схемы совпадения и первым входом первой схемы совпадения, ко второму входу которой подключен выход регистра выдачи, а к третьему — выход второй линии задержки, вход которой соединен со вторым выходом гc".tåðëòîðà тактовых импульсов, со вторым входом блока выбора направления блуждания, со вторым входом четвертой схемы совпадения, вторые входы второй и шестой схем совпадения соединены соответственно со входами устройства.

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

Устройство концентрического блуждания

30 содержит регистр радиуса 1, датчик равно383054

3 мер-ro распределенных случайных чисел 2, сумматор 8, представляющий собой регистрсумматор переменной структуры, схему соападепия 4, осушествляющую опрос датчика случайиых .исел, схему совпадения 5 па три входа, осуществляющую запесепие приращеa is?i п» одной из координат, дополнительный регистр 6, фиксирующий ход датчика для втор»г. такта блуждания, блок выбора паправ: еция блуждания 7, состояп,ий из трех одноразрядных датчиков случайных чисел, трех триггеров rr c.re>iri »»rrrra reriiisr, в roii par»IUrrrl паправление блуждания за два такта с веро1 ятцостшо —, дсшифраторы 8 и 9, ре rr»Tp выдачи 10, выдающий числа второго такта, схему совпадения 11, блок разделения 1>, схемы совпадения 18, 14 и 15, линии задержки 16, 17 и ге ератор тактовых импульсов 18.

В процессе вероятностного блуждания частица совершает равномерное случаипое блуждание с вероятностью переходов, равной 1/4 по узлам сеточной области до попадаппя в один из граничных узлов, Одним из приемов ускорения сходимости решения для вероятностных моделей является тот факт, что решение уравнения Лапласа в любом внутреннем узле области равно среднему арифметическому его значений па любой окружности с центром в этой точке. Поэтому случайные блу>кдания, которые пачи в некоторой точке, будут пересекать окружность с центром v> этой точке с одицаковои вероятностью в любом направлении. В результате такого блуждания траектория за один скачок оказывается на окружности, лежащей внутри области с центром в данной цачальиои точке. Годится любая окружность, ее следует выбирать по возможности наибольшей, принадлежащей исследуемой области. Если необходимо найти решение ур авп ения Л а ил аса в точке А (фиг. 2), строится окружность с цептром в точке А с максимальным радиусом, при котором эта окружность еще принадлежит области. Окру>кпость разбивается на и одинаковых дуг, и моделируется случайное попадание с вероятностью 1/и па одну из этих дуг. На этой дуге берется точка А,, и с центром в этой точке опять строится максимальная окружность, разыгрывается случайных выход па границу этой окружности и т. д. Повторение таких процессов порождает последовательность, сходящуюся к границе области. Из фиксированной начальной точки процесс производится N раз, среднее арифметическое случайных граничных значений является решением уравнения Лапласа для точки А.

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

Предлагаемое устройство концентрического блуждairrrsr позволяет из данной начальной

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

Ila фпг. 3 и 4 показаны»кружпости с радиусами от двух до десяти клеток и пх аппро ; ..мации сеткой с квадратными ячейками (полцой индукцией все и» »?кецпя распрост»aöÿþòñÿ для окру>к остей л:обого радиуса), «r — число сеточных узлов, аппроксимирующих окружность. При осуществлении одного перехода блуждающей частицы из центра круга за два такта, вероятность попадания в любой из аппроксимирующих окружность узлов одииакова и равна 1/и, т. е. траектория блуждапия пересекает окружпость в любом иаправлеции с одинаковой вероятностью.

Пусть наибольшая окружность с центром в данной начальной точке области, для которой ищется решение задачи Дирихле, имеет радиус «=4. Из фиг. 2 видпо, что окружность такого радиуса аппроксимируется двадцатью узлами а=20, поэтому вероятность попадания в любой из этих 20 узлов должна быть одинакова и равна 1/20.

Рассмотрим алгоритм.

1 такт. Датчик равномерно распределяемых случайных чисел вырабатывает случайные числа Я; в интервале 0(P,(«с вероятностью

«- 1 по одному из четырех направлений +-х, ++ó. Таким ооразом, вероятпость появления случайного числа 0(R;(4 по одному из четырех направлений в первом такте равна

1 1 1

P =—

5 4 20

II такт. Во втором такте частица перемещается только по одному из двух направлений +-x, +-у, перпендикулярно выбранному в

1 первом такте, т. е. с вероятностью P = — вы2 бирается направлепие блу>кдапия, а с вероятностью единица вырабатывается число, перебрасывающее траекторию иа окружность.

Вероятность наступления совместного сооытия, заклю ающсгося 13 том, что за два такта блуждающая частица оказывается»a окружпости, равна произведению вероятностей обоих тактов:

1 1 1 1

1,2—

5 4 2 40

Полученная вероятность не окончательна, так как в любую из 20 точек на окружности мо>к. о поп" ñòü гвумя путями: например в точку А (фиг. 2, 3) — выработав в первом такте единицу по направлению +х, а во втором — число четыре по направлению +у, или же выработав четверку по пути +у в первом такте и число один по направлению + х во втором.

На фиг. 2, 3 показаны все варианты попада:Ièÿ па любой узел окружности, в которых

383054

1О первое число всегда вырабатывается лат иком случайных чисел, а второе — неслучайное.

Следовательно, чтобы получить истинную вероятность попадания в один из 20 узлов о«ружности, нужно вероятность блуждания за два такта увеличить вдвое:

Р=Р, Р,2=

Окружности большего радиуса аппроксимируются сложнее. Например при r=- — 9, Окр3 жность (фиг. 3) аппроксимируется п=48 узлами. В первом такте с вероятностью 1 =1/12 вырабатываются случайные числа в интервале от нуля Ло одиннадцати по оЛIIoìó из четырех направлений, а втором — по одному из двух направлений образуются i!åc7ó÷2IIHbic числя, т21 ие, что траектория блу жл211ия по 12дает на одну из 48 точек, лежащих на окружности. Например, если первое случайное число 1, то второе неслучайное — 9 11;iii если первое 9, то второе 1 и т. д. Вероятность попалания на окружность одинакова и равна лля г=9.

Р=...1 2=

1 1 1 1

4 12 2 48

Работа предлагаемого устройства заключается в следующем. Первым тактовым импу Iьсом с генератора 18 коор IHH;IT2 гачальной точки (центр окружности) в параллель" î коде заносится в сум 12ТОр 8, а величина:;2диуса записывается в регистр 1.

Блок 7 в ioiip2eT о!»0 из четырех iiaHpaBлсний блу кгг.ания (-+-х, w+-у), а дешифратор 8 коммутирует соответствующее радиусу количество разрядов датчика. Так, если г = — 4, Латчик будет вырабатывать случайные числа B интервале от 0 ло 4, если r=5, датчик вырабатывает числа от 0 Ло 5 и т. д., кai показано в таблицах па фиг. 3 и 4.

Код случайного числа с датчика 2 через схему совпадения 5 подается в сумматор 8 лля изменения алреса по од!!ому из вьгбранi:I ix блоком 7 направлению.

Во BTOpoi(I такте код латчика пост3 паст !срез регистр б в дешифратор 9, на другие входы которого заг!есена величина радиуса с регистра 1.

На выходе лешифратора 9 возбужлается олна из ппш, которая выбирает опрелелc líb*.:( код числа в регистре 10.

Во втором такте блок 7 выбирает ПBïðàBление бл i ждапия с Всроятностьго 1!2 по О.!ной координате. Так, если в псрвом такте блуждание произошло по коорлщга те (или +-у), то во Втором неслучайный кол с

15 го

25 о

pc!;!c pc 19,с". ; схему сОВпале,li»I 11 пОст3пит В с и H2T0p 8 как прир2ще!!ие по коорлиИатЕ !-У (И7i! -г ).

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

Таким образом, устройство позволяет осуи;ествигн равновероят:!остнос блу клание 32 .Ва Т21 Та, Предмет изобретения

Устройство конце (трического блужлания, СОЛЕРЖBÙCC ГЕНЕР2ТОР Т IКТOВЬIX ИМПУ,7bCOB, лшши залержки, сумматор и логические схемы согпа:!е:пи, ит.гичагоце(сл тем, что, с целью повышения точности устройства. оно солержит ре."истр радиуса, датчик равномерно распре:.еленных. случа lilbix чисел, лополиительный рсI IICTp, блок выоора направления блужла:шя, лва лсшифратора, регистр выла«и и блок разлелсния, выход которого сослииен со вхолом сумматора, первый вхо7,— с выхолом первои схемы совпадения, второй

Bxoä — с выхолом второй схемы совпадения, а третий — с выхолом третьей схемы coBII21cния, к первому входу которой подключен гыхол первой линии залсржки, а ко второму—

ЛХОЛ HeTIIC .1ТОЙ СХЕМ(ЬI COBII27CHHH И BbIXO;1, ПЯтой схемы совпаЛения, первый вхоЛ которой соели:c;i с выхолом датчика равномерно распре le7eii»»ix. случайных чисел, а второй — с выхолом первого лешифратора, ко ьходу которого полключен вход регистра радиуса и пеовый вхол второго лешифратора, Выход которого сое;шнсг! с первым вхолом регистра выЛач;1, а Бто:30й вхоЛ вЂ” с выходом Лополнитсльного регистра, к первому вхолу которого полкл;очси выхол четвертой схемы совпалеиия, 2 ко гторому — первый выход генератора тактовых импульсов, второй вхол регистра выла П3, вхол первой линии залержки, первый вхол шестой схсх!ы coвпалег!Пя, первый Вход

Второй схемь! Совпаления и псрвьш вхо I блои а Б Ы О О Р 2 П !1 и . (1 B:Л С Н И Ч 0,7 1 Ж Л с! П И Я, B bi X O (1 О торого соели,с:l с TpcTbIDI гхолом третьей схемы совгалс:!»«и первым Бхолом первой схемы соьпалсн;и, ко второму вхолу которой полклю;еи в !хол регистра Былачи, а к третьсм3 — Бы. Ол Второl! лиlгии залержки, Бхол которой соелиг;сн со вторым выхолом генератора THêòîâûx импульс,В, со Вторым Вхо lîì б 70!;2 Вь!0092 напр213лс!IПЯ бл i жЛания, со

Бтооы.,I BxG«ом четвертой схемы coBпадеиия, Вторые Бхольl BTopoli l! шестой схем совпалсния сос;ги !сиы соответственно со Бхолами устройства.

383054

r =g ° 77 "7g и-г

12 Р 717

Z-1 4 3Z7Z а

5-г .

1

Фиг 3 — ь — -ь

0 11

=70, = 50, и- 0, Р

- 0-9, 1-9.72-9.73-9 .

9-7 110;2 l 11.,-S

4 8 0-7. 0-0

7-5 E.b

1-10. Z-70. 5-70, (- 7,Г-,,9 5 l6-0 ) -7

1,1,- 1 Т,ф Фиг 4

Составитель С. Громова

Текред Е. Борисова

Корректор А. Дзесова

Редактор С. Авдеева

Заказ 2379i6 Изд. ¹ 615 Тираж 647 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, 5Ê-35, Рауьпская наб., д. 4, 5

Типография, пр. Сапунова, 2

В г -.3 i п=Ю;

0 3

1-5 /Г Г, 31 12 2

p =-.— -1 =—

7 71 1

7 4 Я 16 —,5 и0-5 (7-5

6 Z-0

--- В

711

5i 47Z

)s, (4 6. 5-5.

7 1 g7

Р-470 г 40