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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ВТИЛЬСТВУ Союз Советских Социалистических Республик(23) Приоритет -осударственный комите СССР по делам изобретений/ 7 ГрЖтД 1/о 71) Заяви ГЕНЕРАТОР СЛУЧАЙНОГО ПРОЦЕС 5 Изобретение относится к вычислиетельной технике, в частности к устройствам для моделирования случайныхпроцессов, и может быть использованопри построении управляющих устройств,которые интерпретируются как вероятностные автоматы компенсирующего типа,Известен генератор случайного процесса, содержащий блок управления,1ассоциативное запоминающее устройство,регистр числа, регистр маски, элементы И, элементы ИЛИ, счетчики, дешифратор адреса, дополнительные элементы И, В этом устройстве осуществляется ассоциативный поиск по поисковомуобразу запроса, представляющему собой конъюнкцию ассоциативных признаков, каждый из которых закодированкомбинационным кодом, без пермутации 20ассоциативных признаков в поискбвомобразе запроса 13.Недостатком известного устройства,определяемым его структурными особенностями, является невозможность 2моделирования однородных конечныхцепей Маркрва.Наиболее близким по техническойсущности к предлагаемому является)енератор случайного процесса, содер жащий генератор равномерно распределенных случайных чисел, блок ассоциативной памяти, схемы сборки, блоксхем совпадения, блок индикаторов,шифратор, выходной регистр и дешифратор.В блоке ассоциативной памяти, разделенной на зоны, в первую зону записываются значения элементов первойстроки матрицы переходных вероятнос"тей ПА х , во вторую зону - значения элементов второй строки матрицыи т.д. Таким образом, информация вблоке ассоциативной памяти упорядочена, т.е. номер зоны совпадает с номером состояния цепи Маркова. Фиксирование результата сравнения производится в той зоне, номер которой в теку-щем такте записан в выходном регистре 12),Одйако известное устройство имеетограниченные функциональные возможности при моделировании случайных процессов, поскольку не позволяет реализовать вероятностный автомат компенсирующего типа.цель изобретения " расширениефункциональных возможностей генератора за счет реализации вероятностныхавтоматов компенсирующего типа.840896 Поставленная цель достигается темчто генератор случайного процесса, содержащий генератор равномерно распределенных случайных чисел, выходыкоторого соединены с группой входовблока ассоциативной памяти, вход которого соединен с первым выходом блока1памяти, второй выход которого соединен со входом блока управления, авходы блока памяти подключены к выходам первой группы элементов ИЛИ,входы которых подключены к выходамвторой группы элементов ИЛИ, введенагруппа Функциональных преобразователей, выходы которых соединены со входами второй группы элементов ИЛИ,первая группа входов функциональных 15преобразователей соединена с выходами блока управления, а вторая группа входов функциональных преобразователей соединена с выходами блока ассоциативной памяти соответственно. 20Кроме того, каждый функциональныйпреобразователь содержит первый, второй и третий Элементы ИЛИ, элемент Ии триггер, выход которого соединенс первым выходом элемента И, второйвход которого соединен с выходом второго элемента ИЛИ, входы первого .ивторого элементов ИЛИ являются первой группой входов функциональногопреобразователя, выходами которогоявляются выход первого элемента ИЛИи выход элемента И, единичный входтриггера соединен с выходом третьегоэлемента ИЛИ, вход третьего элемента ИЛИ и нулевой вход триггера являются второй группой входов функцио- З 5нального преобразователя.На чертеже приведена блок-схемапредлагаемого генератора.Генератор содержит генератор 1равномерно распределенных случайных 40чиоел, блок 2 ассоциативной памяти,.первую группу элементов ИЛИ 3, вторую группу элементов ИЛИ 4, блок 5памяти, блок б управления, блоки 7нормировки, функциональные преобразователи 8 и 9, элементы ИЛИ 10-15,элементы И 16 и 17, триггеры 18 и 19.Выходы генератора 1 равномерно распределенных случайных чисел соединены с первыми входами блока 2, выходы 50блока 5 памяти соединены.со вторымивходами блока 2 и со входами блока6 управления, выходы элементов ИЛИ 3соединены через элементы ИЛИ 4 совходами блока 5 памяти, выходы блока2 соединены со входами блоков 7 нор- .мировки, каждый из которых состоитиэ Функциональных преобразователей8 и 9. Названные блоки могут бытьвыполнены в нескольких вариантах. Вконкретном выполнении предлагаемого 60генератора преобразователь 8 содержитэлементы ИЛИ 10-12, элемент И 16 итриггер 18, а преобразователь 9 содержит элементы ИЛИ 13-15, элементИ 17 и триггер 19, причем в преобразо4вателе 8 входы элементов ИЛИ 10 и 11соединены с выходами блока 2, выходэлемента ИЛИ 10 соединен со входомсоответствующего элемента ИЛИ 3, выход элемента 11 соединен с первымвходом элемента И 16, ко второму входу которого подсоединен выход триггера 18, а выход элемента И 16 - совходом соответствующего элемента ИЛИ13, первый вход триггера 18 соединенс соответствующим первым выходом бло.ка ба второй вход триггера 18 через элемент ИЛИ 12 - со вторым и соответствующим третьим выходом блокаб, а в преобразователе 9 входы элементов ИЛИ 13 и 14 соединены с соответствующими выходами блока 2, выходэлемента ИЛИ 13 соединен со входомСоответствующего элемента ИЛИ 3, авыход элемента ИЛИ 14 - с первым входом элемента И 17, ко второму входукоторого подсоединен выход триггера.19, а.выход элемента И 17 - со входом соответствующего элемента ИЛИ 3,Первый вход триггера 19 через элемент ИЛИ 15 соединен со вторым исоответствующим третьим выходом блока 6 управления, при этом второйвход триггера 19 соединен с соответствующим первым выходом блока 6 управления,Рассмотрим особенности работы предлагаемого устройства, интерпретируемого как автономный вероятностный автомат компенсирующего типа с поэлементным изменением матрицы переходных вероятностей /( АОНРиР 1 к Р 1 и, ЗкОтметим, что в дальнейшем предполагается, что все значения Рпредставляют собой дроби со знаменателем вида 2 (д - целое число) или могут быть айЪроксимированы с удовлетворительной точностью дробями такого вида. Пусть автомат в некоторый момент временинаходится в 1-м состоянии, выдан соответствующий этому состоянию выходной сигнал и получил сигнал "Нештраф". Тогда в матрице А значение элемента Рувеличивается на нестарую величину АР, а все остальные элементы 1-ой строки матрицы Ао уменьшаются на величинуьновая матрица переходных вероятностей обозначается как АЕсли же в следующем такте работы автомат получает сигнал "Штраф", то в матрице А. элемент Р уменьшаетися на величину Р, а все остальныеэлемеНты (-й строки А увеличивают-ся на величину -ьРиОтметим, что значение АР должно быть выбрано таким образом, чтобыЪРвеличина =, - представляла собой 50-1дробь со знаменателем вида 2.При сделанных предположениях ин формация в матрице блока АП 2 представляется следующим образом.Разрядность матрицы блока АП 2 определяется из соотношения6 = (о 9 (пах (9, , 9;,91 д )где (я( . . 9 , , 9. ) - Показатели стейени, в знаменателях дробей Р ,при этом верхняя граница числа строкв матрице блока АП 2 равна 2 хп,причем в каждой из 26 строк размещается один из 26 кодов. Выделим вкаждой из и групп, число которыхсоответствует размерности матрицыпереходных вероятностей А(подгруппы таким образом, чтобы число строкв каждой подгруппе равнялось Р 1 к 26(Рк - значение элементов матрицы 25(А ), Тогда для перестройки струкОтуры в каждой подгруппе необходимовыделить базовую и переменную части,которые в подгруппах, реализующихР т,е. соответствующих переходов 30вида а , обеспечивают установкуР 1 -- Р. + Ь Р или РМ 1. = Р 1( Л РД Иа в подгруппах, реализующих Р;, ФМ),обеспечивают компенсирующие установки, т.е. 35Р =9е, килиЬРг =9К (К -1Перед началом работы устройствасо второго входа блока б управлениявыдается сигнал начальной установкиво все блоки 7 нормировки. По .этомусигналу триггеры 18 и 19 во всех блоках,7 нормировки устанавливаются в 45такое положение, что сигналы, посту,пающие на второй вход элементов И 16преобразователя 8 и на второй входэлементов И 17 преобразователя 9,фиксируют объединение строк блока 2 5 Оассоциативной памяти во всех подгруппах, состоящих из базовых частей,определяемых элементами ИЛИ 10 в преобразователе 8 и элементами ИЛИ 13 впреобразователе 9, которое соответствует распределению вероятностейпереходов автомата, задаваемого матрицейпереходных вероятностей Ао(1Режим 1. В этом режиме генераторработает как автономный вероятностныйавтомат в соответствии с заданной 0матрицей переходных вероятностейАпредставленной в блоке 2,Случайное число, поступающее напервые входы блока 2 из генератора1 равномерно распределенных случай ных чисел, в сочетании с кодом состояния, поступающим из блока 5 памяти на вторые входы блока 2, определяет код опроса блока 2. В результате ас-,ф социативного поиска возбуждается один из выходов блока 2 и через один из элементов ИЛИ 10, 11, 13 и 14 соответствующего блока. 7 нормировки и соответствующий элемент ИЛИ первой группы элементов ИЛИ 3 и соответствующий элемент ИЛИ второй группы элементов ИЛИ 4 выбирается ячейка блока 5 памяти, определяющая код состояния, в которое переходит этот автомат. Этот код в сочетании с новым значением случайного числа, поступает на входы блока 2 и определяет следующий переход автомата.Таким образом, цикл работы автомата повторяется.Режим 2. В процессе работы автомата, если после перехода из (-го состояния по сигналу, поступившему из генератора 1, блок б выдает сигнал "Нештраф" соответствующий (-й группе, т.е. (-му состоянию автомата, триггер 18 (-го блока нормировкиустанавливается таким образом, что к базовой части .подгруппы, фиксирующеф значение вероятности перехода Р., подключаются строки блока 2, составляющие переменную часть подгруппы, объединенную элементом ИЛИ 11, что увеличивает значение вероятности перехода а на величину ьР. Одноврет(менно с этим, вследствие подачи сигналаНештраф" с ,того же выхода блока 6 на вход триггера 19 преобразователей 9, входящий в (-й блок 7 нормировки, фиксируется исключениепеременной части подгрупп, объединенных элементами ИЛИ 14, задающих вероятности переходов из (-го состояния во все остальные, т,е. значения всех Р, (М = (, п; (с Фуменьшаются на величину , Если приП дальнейшей работе при переходе автомата из ( го состояния блок б управления выдает сигнал "Штраф", то по этому сигналу, поступающему на входы (-го блока 7 нормировки выполняется обратная настройка автомата, т.е. ,триггер 18 по сигналу, поступающему через элемент ИЛИ 12 устанавливается таким образом что сигналы, поступающие с выхода элемента ИЛИ 11, объединяющего переменную часть подгруппы не поступают на вход соответствующего элемента ИЛИ 3 и таким образом, восстанавливается значение Р Одновременно с этим, вследствие подачи сигнала "Штраф с того же выхода лоха б на вход триггера 19 через элемент ИЛИ 15 преобразователей 9, входящий в (-й блок 7 нормировки, фиксируется подключение переменной части подгруппы, объединяемых элементом ИЛИ 14, задающих вероятности пе 840896(М д Г,п М1) восстанавливаются.Таким образом, второй режим, в который автрмат переходит в случаевыдачи сигналов из блока 6, представляет собой режим перестройки структуры автомата.Отметим, что в конкретных случаяхчисло строк в матрице блока 2 оказывается меньше приведенной верхнейоценки за счет того, что некоторыезначения Р Й 0,1 . В этом случаесоответствующие подгруппы вырождаются в одну строку (Р = 1) или вообще исключаются (Р; = О), Кроме того,если ассоциативные запоминающие элементы, образующие матрицу блока 2,реализуют троичный структурный алфавит, то число строк в подгруппахможет быть минимизировано за счетсклеивания различных кодов и использования кубического представления,что достигается установкой соответствующих ассоциативных запоминающихэлементов в некоторых строках блока2 в безразличное состояние (самомаскирование) .Кроме того, следует также отметить,что при рассмотрении работы устройства предполагается, что перестройкаструктуры осуществляется на одиншаг, т,е, перестройка структуры длялюбого -го состояния может начинаться только с увеличения Р . на дР.На следующем этапе перестройки структуры для этого состояния возможнотолько уменьшение нового значениявероятности Р. на Ь Р. СоотношениеА 9где и - размерность матрицыпереходных вероятностей, справедливов общем случае, но в каждом конкретном случае с учетом того, что часть сР = 0, оно должно определяться как- где аи - число значения69Р 1 - О.Наибольший эффект от применения 45предлагаемого устройства достигается в системах моделирования случайных процессов, что обеспечиваетсяследующими факторами:а) выбор состояния перехода для 50принятого способа представления матриц переходных вероятностей в блокеассоциативной памяти реализуется, вотличие от известных устройств длямодеюфрования случайных процессов, 55простым ассоциативным поиском,б) возможностью отображения в блоке ассоциативной памяти различных матриц переходных вероятностей, динамически изменяемых в процессе работы устройства.формула изобретения1. Генератор случайного процесса, содержащий генератор равномерно распределенных случайных чисел, выходы которого соединены с группой входов блока ассоциативной памяти, вход которого соединен с первым выходом блока памяти, второй выход которого соединен со входом блока управления, а входы блока памяти подключены к выходам первой группы элементов ИЛИ, отличающийся тем, что, с целью расширения Функциональных возможностей генератора за счет реализации вероятностного автомата, компенсирующего типа, он содержит группу функциональных преобразователей, выходы которых соединены со входами второй группы элементов ИЛИ, первая группа входов функциональных преобразователей соединена с выходами блока управления, а вторая группа входов функциональных преобразователей соединена с выходами блока ассоциативной, памяти соответственно.2, Генератор по и. 1, о т л ич а ю щ и й с я тем, что каждый Функциональный преобразователь содержит первый, второй и третий элементы ИЛИ, элемент И и триггер, выход которого соединен с первым выходом элемента И, второй вход которого соединен с выходом второго элемента ИЛИ, входы первого и второго элементов ИЛИ являются первой группой входов Функционального преобразователя, выходами которого являются выход первого элемента ИЛИ и выход элемента И, единичный вход триггера соединен с выходом третьего элемента ИЛИ, вход третьего элемента ИЛИ и нулевой вход триггера являются второй группой входов Функционального преобразователя.Источники информациипринятые во внимание при экспертизе1. Авторское свидетельство СССРпо заявке Р 2037964/18-24, 1974.2. Авторское свидетельство СССРР 451085, кл. О 06 Е 1/02, 1973