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

Г 1И (.-Ф" ФН+ О ПИЗОБРЕТЕНИЯ Союз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Зависимое от авт. свидетельстваЗаявлено 18 Х,1970 ( 1440204/18-24)с присоединением заявкиПриоритетОпубликовано 23 Х,1973. Бюллетень23Дата опубликования описания 05.1 Х.1973 Кл. Ст 061 1532 Комитет по делам изобретений н открытий при Совете МинистровУДК 681.3:519.2(088.8) ссср Авторыизобретения В. С. Гладкий, А. П. Уриков и Н. В. Урикова Морской гидрофизический институт АН Украинской ССРЗаявитель УСТРОЙСТВО КОН ЦЕНТРИ Ч ЕСКОГО БЛУЖДАНИЯ Устройство относится к области вычисли. тельной техники и может быть использовано в универсальных и специализированных вычислительных устройствах при решении дифференциальных уравнений в частных производных методом статистических испытаний.Известное устройство для решения дифференциальных уравнений в частных производных методом статистических испытаний, содержащее генератор тактовых импульсов, линии задержки, сумматор и логические схемы совпадения, це обладает достаточной точностью.Цель изобретения - повысить точность, Эта цель достигается тем, что устройство содержит регистр радиуса, датчик равномерно распределенных случайных чисел, дополнительный регистр, блок выбора направления блуждетция, два дешифратора, регистр выдачи и блок разделения, выход которого соедццец со Входом сумматора, первый вход - с выходом .тервоц схемы совпадения, второй вход - с выходом второй схемы совпадения, а третий - с выходом третьей схемы совпадения, к первому входу которой подключен выход первой линии задержки, а ко второму - вход четвертой схемы совпадения и выход пятой схемы совпадения, первый вход которой соединен с выходом датчика равномерно распределенных случайных чисел, а второй - с выходом перваго дешифратора, ко входу которого под.ключен выход регистра радиуса и первый вход второго дешифратора, выход которого соеди нен с первым входом регистра выдачи, а вто.рой вход - с выходом дополнительного ре.гцстра, к первому входу которого подключен В 11 лод четвертой схемы совпадения, а ко вто рому - первый выход генератора тактовых 1 мпульсов, второй вход регистра выдачи, вход 10 1;ервой лцццц задержки, первый вход шестойгхс.1 ы сОВпадецця, перВы 11 Вход гтторой схемы совпадения ц первый Вход блока Выбора на" правления блуждания, выход которого соедц.цец с третьим Входом третьей схемы совпаде.цця и первым Входом первой схемы совпаде.цця, ко второму входу которой подключен выход регистра выдачи, а к третьему - выход второй линии задержки, Вход которой соеди.нен со вторым Выходом гс.1 ератора тактовых импульсов, со вторым Входом блока выбора направления блуждания, со вторым входом четвертой схемы совпадения, вторые входы второй и шестой схем совпадения соединены соответственно со входамц устройства.На фцг, 1 представлена олок-схема предлагаемого устройства; ца фцг. 2, 3 и 4 показаны окружности и цх аппроксимации сеткой с квадратичными ячейками.Устройство концентрического блуждания 30 содержит регистр радиуса 1, датчик равно55 60 65 3мерно распределенных случайных чисел 2, сумматор г, представляющий собой регистр- сумматор переменной структуры, схему совпадения 4, осушествляющую опрос датчика случайцых чисел, схему совпадения 5 нг три входа, осуществляющую занесение приращегги пс, одной из координат, дополнительный регистр б, фиксирующий ход датчика для второго такта блркдания, блок выбора направ: ения блуждания 7, состояп,нй нз трех одноразрядных датчиков случайных чисел, трех триггеров и схем соваденгя, Вьгбнргггогци направление блуждания за два такта с веро 1ятностыо - , дсшифраторы 8 и 9, репстр выдачи 10, выдающий числа второго такта, схему совпадения 11, блок разделения 12, схемы совпадения 1 г, И и 15, линии задержки 6, 17 и ге ератор тактовых импульсов 1 Ь.В процессе вероятностного блуждания частица совершает равномерное случайное блуждание с вероятностью переходов, равной 1/4 по узлам сеточной области до нопадашя в один из граничных узлов, Одним из приемов ускорения сходимости решения для вероятностных моделей является тот факт, что решение уравнения Лапласа в любом внутреннем узле области равно среднему ариф.,етическому его значений на любой окружности с центро в этой тогке. Поэтому слугаЙные блу;и- дания, которые начинаются в некоторой точке, будут пересекать округкность с центром и этой точке с одинаковои вероятностью в любом направлении, В результате такого блуждания траектория за один скачок оказывается на окружности, лежащей внутри области с центром в данной начальнои точке, Годится любая окружность, ее следует выбирать по возможности наибольшей, принадлежащей исследуемой области. Если необходимо найти решение уравнения Лапласа в точке А (фиг, 2), строится окружность с центром в точке А с максимальным радиусом, при котором эта окружность еще гринадлежит области. Окрукность разбивается на гг одинаковых дуг, и моделируется случайгцое попадание с вероятностью 1/п на одну из этих дуг. На этой дуге берется точка А и с центром в этой точке опять строится максимальная окружность, разыгрывается случайных выход на границу этой окружности и т, д. Повторение таких процессов порождает последовательность, сходящуюся к границе области. Из фиксированнон начальной точки процесс производится Л раз, среднее арифметическое случайных граничных значений является решением уравнения Лапласа для точки А.Такой способ блуждания требует гораздо меньшего числа шагов, чем моделироьапие блум(данил по всем узлам сеточной области, следовательно, имеет лучшую сходимость, и его реализация занимает ца порядок меньше машинного времени.Предлагаемое устройство концентрического блуждания позволяет из данной начальной 5 10 15 20 25 30 35 40 45 50 точки, являющейся центром наибольшей окружности, расположеног внутри исследуемой области, за два такта (один переход) попадать в любую точку окружности с одинаковой вероятностью.На фпг. 3 и 4 показаны окружности с радиусами от двух до дести лето и пх аппро; .мации сеткой с кадратными ячейками(полной индукцией все поожсння распростпа яются для окружостей любого радиуса),п - число сеточных узлов, аппроксимирующихокружность. При осуществлении одного перехода блуждающей частицы из центра кругаза два такта, вероятность попадания в любойиз аппроксимирующих окружность узлов одинакова и равна 1/гг, т. е. траектория блуждапия пересекает окруж.ость в гюсом направлениси с одинаковой вероятностью.Пусть наибольшая окружность с центром вдацной начальной точке области, для которойищется решение задачи Дирихле, имеет радиус =4. Из фиг. 2 видно, что окружность такого радиуса аппрокси мируется двадцатьюузлами и=20, поэтому вероятность попадания в любой из этих 20 узлов должна бытьодинакова и равна 1/20,Рассмотрим алгоритм,1 такт. Датчик равномерно распределяемыхслучайных чисел вырабатывает случайныечисла Яг в интервале 0(1 с,(г с вероятностью1- 1по одному из четырех направлений +.х,+у. Таким ооразом, вероятность появленияслучайного числа 0(Я;(4 по одному из че.тырех направлений в первом такте равна1 1 1Р = -15 4 2011 такт. Во втором такте частица перемещается только по одцому из двух направлений +-х, +у, перпендикулярно выбранному в1первом такте, т. е. с вероятностью Р = - вьбирается направление блуждггния, а с вероят.пастью единица вырабатывается число, перебрасываюнгее траекторию на окружность.Вероятность наступления совместного со.оытия, заклочаюгцсося в том, что за два такта блуж;гающая частица оказывается на окружности, равна произведению вероятностейобоих тактов:1 1 1 1Р 2: -- 1:5 4 2 40Полученная вероятность не окончательна, так как в любуо цз 20 точек на окружности мож, о попасть двумя путями: например в точку А (фиг, 2, 3) - выработав в первом такте с,синицу по направленио +х, а во втором - число четыре по направлению +у, или же выработав четверку по пути +г 1 в первом такте и число один по направлению + х во втором,На фиг, 2, 3 показаны все варианты попада:ия на любой узел окружности, в которыхпервое число всегда вырабатывается лат шком случайных чисел, а второе - неслучайное. Следовательно, чтобы получить истинную вероятность попадания в один из 20 узлов ок. рркности, нужно вероятность блуждания за два такта увеличить вдвое:Р=Р, Р,2=20Окружности большего радиуса аппроксцмцруются сложнее. Например при г=-9, окржность (фиг, 3) аппроксимируется п=48 узлами, В первом такте с вероятностью Р=1/12 вырабатываются случайные числа в интервале от нуля ла олицнадцати по одному из четырех направлений, а втором - по одному из двух направлений образуются неслуча 1 Пыс ЧИСЛЕ, Т 2 КИЕ, ЧТО ТраЕКТООИя блсн(даНИя Попадает на одну из 48 тачек, лежащих на окружности. Например, если первое случайное число 1, то второе неслучайное - 9 илп если первое 9, то второе 1 и т. д. Вероятность попадания на окружность одинакова и равна лля г = 9.Р= . . 12=1 1 1 14 12 2 48Работа предлагаемого устройства заключается в следующем. Первым тактовым цмпул,- сам с Генер 2 тар 2 18 кооа;ипата П 2 чаль.ОЙ точки (центр окружности) в параллель. ом коде заносится в сумматор 5, а велич 2 радиуса записывается в регистр 1.Блок 7 выбирает олцо из четырех цаправ;сний блрканця (+-х, .+-у), а дешифратор д коммутирует соответствующее радиусу количество разрядов датчика, Так, если= - 4, датчик будет вырабатывать случайные числа Б интервале от О до 4, если г=5, датчик вырабатывает числа от О до 5 и т. д как показано в таблицах ца фиг. 3 и 4.Код случайного числа с датчика 2 через схему совпадения 5 подается в сумматор ц лгя изменения алоеса па од 1 ому цз вьбра 1;ых блоком 7 цаправлецию.ВО Вт 000 м такте код датчика паступаст срез регистр б в дешифратор 9, ца другие Входы которого за 1 есена величина радиуса с регистра 1.На выходе дешифратора 9 возбуждается одна из цпш, которая выбирает опреде;сный код числа в регистре 10.Во втором такте блок 7 выбирает цапрап ление лукдация с вероятностью 1/2 ГО ал - ной координате. Так, если в псрвом такта блуждание произошло по координате:Т.т (или +у), то во Втором неслучайный кал с5 10 рсГцстр 2 1,1 1 с",сз схе:у сОВпалеция 11 пасту- ПИТ В СуМц 12 ТОБ с К 21( Прцр 2 ЩЕНИЕ ПО Коард 1- нате +у (цлц х).Слеловате;ь:10, к канц ВтороГО такта блу- ЖЛ 2 ЮЩ 2 Я Ч 2 СТЦЦЗ ОК 2 ЗЫВВЕТСЯ Ца ГРЯНЦЦЕ окружности ралцуса г, зафиксированного на регистре 1.Таким образам, устроцство позволяет осу- Ц;ЕСТВЦТЬ Р 2 ВНОБЕРОЯТ 10 СТНОС ОЛЖЛ 2 НЦЕ 32 лза т 2 кта. 15 20 25 30 35 40 45 50 55 Предмет изобретения. стройство коццентрцческОГО алужланця, СОЛЕРЖСЩСЕ ГЕНЕР 2 ТОР ТЛКТОВЫХ ИМПУЛЬСОВ, лцццц залержкц, сумматор ц логические схемы согпале:я, ит,гичаОцесся тем, что, с целью повышения точности устройства. оно содержит регистр радиуса, датчик равомеро распрееленцьх слуцайных чисел,;опал- тельны 1 регистр, бл 01( ВыаОра направления блужла:шя, лва лсшцфратора, регистр вылацц ц алак разделения, выход которого соединен со входом сумматора, первый вход - с выхолом перво схемы совпадения, второй вход - с выходом второй схемы совпадения, а третий - с выходом третьей схемы совпадения, к первому входу которой подключен выход первой линии задержки, а ко второму - БХОЛ ЧЕТБСРТОй СХЕМЪ 1 СОБПЯЛЕЦЦЯ И ВЫХОЛ ПЯ- тоц схемы совпадения, первый вход которой соедисц с выходом датчика равномерно распределенных случайны:( ццссл, а второй - с выходам первого лешифратора, ко ьходу которого подключен вход регистра радиуса и пеовьй вход второго лешифратора, выход которого сое;шсн с первым входом регистра В Ы Л а1, 2 Б Т О р О й В О Л - С Б Ы:с; О Л О Х 1 Л О П О Л Н ц " тельного регистра, к первому входу которого полкл;очсн Выкал четвертои схемы совпадения, 2 ка Второму - первый выход генератора тактовых цмпульсов, второй вход регистра ВыдасЦ, ВХОЛ ПЕРВОЙ ЛИНИИ ЗБЛЕРЖКЦ, ПСРВЫй вход шестой схемы совпале 1 ця, первый Вход вторзй схемь савпаленця ц псрвьш вхо; бло- КсЗ БЫООР 2 1 с,;ВБЛСНЦЯ ОЛУЖЛс 1 Ц 51, ВЬ 1,0; 1(0- торога саеде:1 с трстьцм Входом третьей схемы совгалс:шч и первым Входом первой схемы соьпалец;ш, ко второму входу которой полключец Вгкал регистра Былачц, а к третьему - Выход ВтОР 01 ли 1 цц задежни, Бход каталай саед 1:сн со вторым выходом генерато тактовых импульсов, со Вторым Бхо:ам блана Выбора направленя блуждания, со втааым вхалам цствертой схемы совпадеця, вторые вхаль 1 Бтароц и шестой схем совпадения сосл:1 сы соответственно со Вхоламц устройства.Подписноете Министров СССР Изд. ЪЪ 615 Тираж 647о делам изобретений и открытий при С Москва, Ж, Рауьпская наб., д. 4,5 Заказ 237916ЦНИИПИ Комитет ипография, пр, Сапунова, 2