Генератор случайного процесса

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

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

Республик

< ч 840896 (61) Дополнительное к авт. сеид-ву— (22) Заявлено 31.05.78 (21) 2621005/18-24 (51)М. Кл.

G 06 F 7/58 с присоединением заявки Нов

Государственный комитет

СССР по делам изобретений, и открытий (23) Приоритет—

Опубликовано 23.0681, Бюллетень Йо 23

Дата опубликования описания 2 106,81 (53) УДК 681. 325 (088 с8) (72) Автор изобретения

Л.М. Метрик (71) Заявитель (54 г ГенеРАтОР случАЙнОГО пРОцессА

Изобретение относится к вычислит тельной технике, в частности к устройствам для моделирования случайных процессов, и может быть использовано при построении управляющих устройств, которые интерпретируются как вероятностные автоматы компенсирующего типа, Известен генератор случайного процесса, содержащий блок управления, ассоциативное запоминающее устройство, регистр числа, регистр маски, элементы И, элементы ИЛИ, счетчики, дешифратор адреса, дополнительные элементы H. В этом устройстве осуществляет- 15 ся ассоциативный поиск по поисковому образу запроса, представляющему собой конъюнкцию ассоциативных признаков, каждый из которых закодирован комбинационным кодом, без пермутации 20 ассоциативных признаков в поисковом образе запроса (1).

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

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

В блоке ассоциативной памяти, разделенной на зоны, в первую зону записываются значения элементов первой строки матрицы переходных вероятнос" тей йA it во вторую зону — значения элементов второй строки матрицы и т.д. Таким образом, информация в блоке ассоциативной памяти упорядочена, т.е. номер зоны совпадает с номером состояния цепи Маркова. Фиксирование результата сравнения производится в той зоне, номер которой в теку- щемтакте записан в выходном регистре (2) .

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

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

840896

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

1 памяти, второй выход которого соединен со входом блока управления, а входы блока памяти подключены к выходам первой группы элементов ИЛИ, входы которых подключены к выходам второй группы элементов ИЛИ, введена группа функциональных преобразователей, выходы которых соединены со входами второй группы элементов ИЛИ, первая группа входов функциональных 15 преобразователей соединена с выходами блока управления, а вторая группа входов функциональных преобразователей соединена с выходами блока ассоциативной памяти соответственно. 20

Кроме того, каждый функциональный преобразователь содержит первый, второй и третий Элементы ИЛИ, элемент И и триггер, выход которого соединен с первым выходом элемента И, второй вход которого соединен с выходом второго элемента ИЛИ, входы первого .и второго элементов ИЛИ являются первой группой входов функционального преобразователя, выходами которого являются выход первого элемента ИЛИ и выход элемента И, единичный вход триггера соединен с выходом третьего элемента ИЛИ, вход третьего элемента ИЛИ и нулевой вход триггера являются второй группой входов функцио- З5 нального преобразователя.

На чертеже приведена блок-схема предлагаемого генератора.

Генератор содержит генератор 1 равномерно распределенных случайных 40 чиеел, блок 2 ассоциативной памяти,-: первую группу элементов ИЛИ 3, вторую группу элементов ИЛИ 4, блок 5 памяти, блок б управления, блоки 7 нормировки, функциональные преобразо- 45 ватели 8 и 9, элементы ИЛИ 10-15, элементы И 16 и 17, триггеры 18 и 19.

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

6 управления, выходы элементов ИЛИ 3 соединены через элементы ИЛИ 4 со входами блока 5 памяти, выходы блока

2 соединены со входами блоков 7 нор- . мировки, каждый из которых состоит иэ функциональных преобразователей

8 и 9. Названные блоки могут быть выполнены в нескольких вариантах. В конкретном выполнении предлагаемого 60 генератора преобразователь 8 содержит элементы ИЛИ 10-12, элемент И 16 и триггер 18, а преобразователь 9 содержит элементы ИЛИ 13-15, элемент

И 17 и триггер 19, причем в преобразо-65

4 ! вателе 8 входы элементов ИЛИ 10 и 11 соединены с выходами блока 2, выход элемента ИЛИ 10 соединен со входом соответствующего элемента ИЛИ 3, выход элемента 11 соединен с первым входом элемента И 16, ко второму входу которого подсоединен выход триггера 18, а выход элемента И 16 — co входом соответствующего элемента ИЛИ

13, первый вход триггера 18 соединен с соответствующим первым выходом бло.ка б,,а второй вход триггера 18 через элемент ИЛИ 12 — co вторым и соответствующим третьим выходом блока б, а в преобразователе 9 входы элементов ИЛИ 13 и 14 соединены с соответствующими выходами блока 2, выход элемента ИЛИ 13 соединен со входом

Соответствующего элемента ИЛИ 3, а выход элемента ИЛИ 14 — с первым входом элемента И 17, ко второму входу которого подсоединен выход триггера.

19, а.выход элемента И 17 - со входом соответствующего элемента ИЛИ 3.

Первый вход триггера 19 через элемент ИЛИ 15 соединен со вторым и соответствующим третьим выходом блока 6 управления, при этом второй вход триггера 19 соединен с соответствующим первым выходом блока 6 управления.

Рассмотрим особенности работы предлагаемого устройства, интерпретируемого как. автономный вероятностный автомат компенсирующего типа с поэлементным изменением матрицы переходных вероятностей /(АОН

Рrr Р1к Р1и

"1

1 УПри этом, выполняется условие нормировки

p° . = 1 (= 1, и) ., 1к

Отметим, что в дальнейшем предполагается, что все значения Р „ представляют собой дроби со знаменателем вида 2д (g — целое число) или могут быть айЪроксимированы с удовлетворительной точностью дробями такого вида.

Пусть автомат в некоторый момент времени t находится в i-м состоянии, выдан соответствующий этому состоянию выходной сигнал и получил сигнал "Нештраф". Тогда в матрице AO значение элемента P-„ увеличивается на не старую величину АР, а все остальные элементы i-ой строки матрицы Ао уменьшаются на величину

tl-1 новая матрица переходных вероятностей обозначается как А

Если же в следующем такте работы автомат получает сигнал "Штраф", то в матрице A элемент Р„- уменьшает11 ся на величину Р, а все остальные

840896 элементы i-й строки A увеличивают-

1 ся на величину— ьР и 1

Отметим, что значение дР должно быть выбрано таким образом, чтобы

b,Р величина =, — представляла собой 5

0-1 дробь со знаменателем вида 2 }, .

При сделанных предположениях ин формация в матрице блока АП 2 представляется следующим образом.

Разрядность матрицы блока АП 2 определяется из соотношения

6 = (о9 (>пах (9, ..., g ., 91п) > где (9;1. . g, g;„) — показате-,}5 ли стейени, в знаменателях дробей Р-„, при этом верхняя граница числа строк в матрице блока АП 2 равна 2 хп, причем в каждой из 2 строк размещается один из 2 кодов. Выделим в каждой из и групп, число которых соответствует размерности матрицы переходных вероятностей ((A 0((, подгруппы таким образом, чтобы число строк в ка дой подгруппе равнялось Р1к 2

6 (P„ < — значение элементов матрицы 25 (A i(). Тогда для перестройки струк0 туры в каждой подгруппе необходимо выделить базовую и переменную части, которые в подгруппах, реализующих

Р„-,, т.е. соответствующих переходов 3р вида а, обеспечивают установку

Р1 ° — — P„-. + ЬP или P<„. = Р1(ЛР

Д И а в подгруппах, реализующих Р;, (ikk), обеспечивают компенсирующие установки, т.е. 35

Р- = Р. и. (к или

ЬР

О- =9 v. }УПеред началом работы устройства со второго входа блока б управления выдается сигнал начальной установки во все блоки 7 нормировки. По .этому сигналу триггеры 18 и 19 во всех блоках,7 нормировки устанавливаются в 45 такое положение, что сигналы, посту.пающие на второй вход элементов И 16 преобразователя 8 и на второй вход элементов И 17 преобразователя 9, фиксируют объединение строк блока 2 5р ассоциативной памяти во всех подгруп. пах, состоящих из базовых частей, определяемых элементами ИЛИ 10 в преобразователе 8 и элементами ИЛИ 13 в преобразователе 9, которое соответст- 5 вует распределению вероятностей переходов автомата, задаваемого матрицей переходных вероятностей ((А0((Режим 1. B этом режиме генератор работает как автономный вероятностный автомат в соответствии с заданной 1р матрицей переходных вероятностей (A(( представленной в блоке 2.

Случайное число, поступающее на первые входы блока 2 из генератора

1 равномерно распределенных случай- 65 ных чисел, в сочетании с кодом состояния, поступающим из блока 5 памяти на вторые входы блока 2, определяет код опроса блока 2. В результате ас-, о социативного поиска возбуждается один из выходов блока 2 и через один из элементов ИЛИ 10, 11, 13 и 14 соответствующего блока.- 7 нормировки и соответствующий элемент ИЛИ первой группы элементов ИЛИ 3 и соответствующий элемент ИЛИ второй группы элементов ИЛИ 4 выбирается ячейка блока 5 памяти, определяющая код состояния, в которое переходит этот автомат. Этот код в сочетании с новым значением случайно" î числа, поступает на входы блока 2 и определяет следующий переход автомата.

Таким образом, цикл работы автомата повторяется.

Режим 2. В процессе работы автомата, если после перехода из i-го состояния по сигналу, поступившему из генератора 1, блок 6 выдает сигнал "Нештраф", соответствующий i-й группе, т.е. i-ìó состоянию автомата, триггер 18 i-го блока нормировки устанавливается таким образом, что к базовой части .подгруппы, фиксирующей значение вероятности перехода P..

11 подключаются строки блока 2, составляющие переменную часть подгруппы, объединенную элементом ИЛИ 11, что увеличивает значение вероятности перехода а. на величину b.Ð. Одновреi менно с этим, вследствие подачи сигнала Нештраф" с .того же выхода блока 6 на вход триггера 19 преобразователей 9, входящий в i-й блок 7 нормировки, фиксируется исключение переменной части подгрупп, объединенных элементами ИЛИ 14, задающих вероятности переходов из i-го состояния во все остальные, т.е. значения всех P. (k = 1, и; }с Ф }) уменьша1К ются на величину . Если при

>>-1 дальнейшей работе при переходе автомата из i ro состояния блок 6 управления выдает сигнал "Штраф", то по этому сигналу, поступающему на входы i-ro блока 7 нормировки выполняется обратная настройка автомата, т.е. ,триггер 18 по сигналу, поступающему через элемент ИЛИ 12 устанавливается таким образом., что сигналы, посту пающие с выхода элемента ИЛИ 11, объединяющего переменную часть подгруппы,. не поступают на вход соответствующего элемента ИЛИ 3 и таким образом, восстанавливается значение Р.

Одновременно с этим, вследствие подачи сигнала "Штраф" с того же выхода флока б на вход триггера 19 через элемент ИЛИ 15 преобразователей 9, входящий в i-й блок 7 нормировки, фиксируется подключение переменной части подгруппы, объединяемых элементом ИЛИ 14, задающих вероятности пе840896 реходов иэ i-го состояния ва все остальные т.IB значения Всех Р (k T,n> k H () восстанавливаются.

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

Отметим, что в конкретных случаях число строк в матрице блока 2 оказывается меньше приведенной верхней оценки за счет того, что некоторые значения Р (= 10,1 . В этом случае соответствующие подгруппы вырождают ся в одну строку (Р„-„ = 1) или вообще исключаются (Р;„ = О), Кроме того, |если ассоциативные запоминающие элементы, образующие матрицу блока 2, реализуют троичный структурный алфавит, то число строк в подгруппах может быть минимизировано за счет склеивания различных кодов и исполь- 20 зования кубического представления, что достигается установкой соответствующих ассоциативных запоминающих элементов в некоторых строках блока

2 в безразличное состояние (самомас- 25 кирование) .

Кроме того, следует также отметить, что при рассмотрении работы устройства предполагается, что перестройка структуры осуществляется на один шаг, т.е. перестройка структуры для любого i-ro состояния может начинаться только с увеличения Р „. на дР.

На следующем этапе перестройки структуры для этого состояния возможно только уменьшение нового значения вероятности Р>. на (Р. Соотношение 9 где n — размерность матрицы переходных вероятностей, справедливо в общем случае, но ь каждом конкретном случае с учетом того, что часть

P. = О, оно должно определяться как — где m «c< n — число значения йр

Р1 (- О ..

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

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

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

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке Р 2037964/18-24, 1974.

2. Авторское свидетельство СССР

Р 451085, кл. G 06 F 1/02, 1973 (прототип).

840896

Составитель А. Карасов

Техред А.Бабинец Корректор В. Бутяга

Редактор. В. Лазаренко

Заказ 47б7/72 Тираж 745

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб. д. 4/5

Подписное

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4