Устройство для моделирования квадратичного блуждания Советский патент 1986 года по МПК G06F7/58 

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

Цель изобретения - повьшение быстродействия устройства„

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

Устройство (фиг. 1) содержит вход запуска устройства, первый вход 2 ввода исходньпс данных устройства, второй вход 3 ввода исходных данных устройства, второй блок 4 элементов И, дешифратор 5, датчик 6 равномерно распределенных случайных чисел, первый и второй элементы 7 задержки,,равновероятностный эле- меНт 8, первый и третий блоки 9 элементов И, блок 10-сравнения, блок 11 элементов НЕ, коммутатор 12, сумматор 13.

Вероятностный элемент 8 (фиго 2) содержит первый и второй регистры 14 и 14- сдвига, первый и второй сумма- . торы 15 по модулю два, дешифратор 16 Коммутатор 12 (фиг, 3).содержит блоки 17 и 18 элементов И, элементы ИЛИ 19 и 20. Сумматор 13 (фиг. 4) содержит регистры 21, комбинационные сумматоры 22 и блоки 23 элементов ИЛИ. Дешифратор 5 коммутирует определенное количество разрядов датчика 6, соответствующее количеству разрядов двоичного кода числа К.

Датчик 6 равномерно распределенных случайных чисел вырабатывает равномерно распределенные случайные числа в прямом и инверсном двоичном коде в интервале (0,1). Равновероятностный элемент 8 осуществляет рав- , новероятный розыгрьпп одного и четырех возможных исходов (секторов квадрата). Коммутатор 12 вырабатывает приращения по координатам х и у в соответствии с таблицей кодирования (фиг. 7). Сумматор 13 осуществляет формирование координат очеред-

S

0

5

0

0

5

50

55

ного узла траектории случайного 1 блуждания.

Устройство осуществляет построение трае:ктории случайного блуждания следукицим образом.

С центром в стартовом узле А (фиг. 5) строится максимальный квадрат, принадлежащий исследуемой сеточной области, стороны квадрата располагают параллельно осям координат и аппроксимируют лежащими на них узлами области (фиг. 6), где К равно половине числа узлов области, лежащих на одной стороне квадрата, кроме одного углового. Моделируется случайный переход с вероятностью

из узла А в один из узлов п оК °

периметра квадрата (например, узел А, фиг. 5). Далее с центром в узле А строится максимальный- квадрат, разыгрывается случайный переход в один из узлов периметра этого квадрата и т.д. Повторение таких случайных переходов порождает марковскую цепь, которая с вероятностью, равной единице, заканчивается на границе сеточной области. Для получения оценки решения уравнения Лапласа в узле АО вычисляется среднее арифметическое случайных граничных значений от требуемого числа траек- торий квадратичного блуждания.

Устройство квадратичного блуткда- ния,работает следующим образом.

Управляющий сигнал по входу 1 открьгеает блок 4 элементов И, запускает датчик 6 равномерно распределенных случайных чисел и равнове- роятностный элемент 8 и через Элементы задержки поступает соответственно на блок 10 сравнения сумматор 13. Значение К по входу 2 устройства поступает на коммутатор 12 и через блок 4 элементов И - на де- шифратор 5. По этому же входу значение К поступает на блок 10 сравнения и через блок 11 элементов НЕ - на коммутатор 12, По входу 3 устройства координаты стартового узла заносятся в сумматор 13. Дешифратор 5 коммутирует соответствующее значению К количество разрядов датчика 6. Прямой и инверсный код случайного числа с датчика 6 через блоки элементов И подаются на коммутатор 12,, Сравненное значение прямого кода случайного числа и кода

25

числа К с блока 10 сравнения поступает на коммутатор 12, В зависимости от кода, выбранного равновероятностным элементом 8 сектора квадрата, коммутатор 12 в соответствии с таблицей кодирования (фиг. 7) заносит приращения по координатам х и у в сумматор 13, В последнем осуществляется формирование координат очередного узла траектории случайного блуждания.

Равновероятностный элемент 8 (фиг, 2) работает следующим образом, . Регистр 14 с сумматором 15 по модулю два в цепи обратной связи представляет собой генератор одноразрядных псевдослучайных равномерно распределенных чисел. По казкдому управляющему сигналу, поступающему с входа 1 устройства на вход первого разряда регистров, с выхода .первого разряда регистров снимаются одноразрядные равномерно распределенные псевдослучайные числа, которые поступают на входы двоичного дешифратора 16 Двоичный дешифра- тор 16 формирует единичный сигнал на одном из своих четырех выходов в зависимости от кода двухразрядного случайного числа на его входе.

Коммутатор 12 (фиг, З) работает следующим образом,

ЕСЛИ, например, элемент 8 формирует единичный сигнал на первом выходе, то этот сигнал открывает блоки 17, 17 и 18 элементов И, Значение числа К через первый блок 8 двухвходовых элементов И и пятый блок 195 двухвходовых элементов ИЛИ поступа§т на первый блок трех- входовых элементов ИЛИ. Единичный сигнал, соответствующий случаю, когда- К больше случайного числа, поступает с выхода блока 10 сравнения на пятьй блок 17 трехвходовЫх элементов И. Единичный сигнал, соответствующий случаю, когда К меньше или равно случайному числу, поступает с выхода блока 10 сравнения на восьмой блок 17 трехвходовых элементов И. Прямой (обратный) код случайного числа с датчика 6 через пятый (восьмой) блок 17j(17g) трехвходовых элементов И и третий (четвертый) блок 19 (19) двухвходовых 55 элементов ИЛИ поступает на второй блок 20 трехвходовых элементов ИЛИ, На выходе коммутатора 12 образуются

30

35

40

45

50

S

0

5

0

приращения по координатам х и у в соответствии с таблицей кодирования (фиг, 7)о Коммутатор 12 работает аналогичным образом, если равновероятностный элемент 8 формирует единичный сигнал на втором, третьем или четвертом выходе.

Сумматор 13 (фиг, 4) работает следующим образом.

Координаты стартового узла А, по входу 3 устройства через блоки 23- и 23 элементов ИЛИ поступают на регистры 21 и 21 . Приращения по координатам X и у с коммутатора 12 поступают на регистры 21 и 2Г , По управляющему сигналу с элемента 7 задержки операнды суммирования с регистров 21 поступают на входы комбинационных сумматоров 22, череэ бло ки 23 элементов ИЛИ - на регистры 2Ь и 21.

Использование предлагаемого устройства в составе универсальной или специализированной ЭВМ для решения сеточных однородных эллиптических уравнений (например, уравнения Лапласа) в прямоугольных областях позволяет сократить время решения задачи по сравнению с известным устройством в (2к+1) раз.

5

5

0

5

0

Формула изобретения

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

отличающееся

тем, что,

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

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

LJ

Изобретение отйосится к специализированным средствам вычислительной техники и может быть использовано при решении сеточных уравнений методом статистических испытаний. Цель изобретения - повышение быстродействия. Устройство содержит вход I запуска, первый 2 и второй 3 входы ввода исходных данных, блоки элементов И 4, 9, дешифратор 5, датчик 6 равномерно распределенных случайных чисел, элементы 7 задержки, равновероятностный элемент 8, блок 10 сравнения, блок II элементов НЕ, коммутатор 12, сумматор 13. 7 ил.

Составитель В, Фукалов

Редактор Н. Яцола Техред И.Попович Корректор А, Зимокосов

Заказ 5123/47 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно- полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Фы. 1