Генератор случайного процесса Советский патент 1981 года по МПК G06F7/58 

Изобретение относится к вычислительной технике, в частности к устро ствам для моделирования случайных процессов, и может быть использовано при построении управляющих устройств которые интерпретируются как вероятностные автоматы компенсирующего типа, . Известен генератор случайного про цесса, содержащий блок управления, ассоциативное запоминающее устройств регистр числа, регистр маски, элелюн ты И, элементы ИЛИ, счетчики, дешифратор адреса, дополнительные элементы И. В этом устройстве осуществляет ся ассоциативный поиск по поисковому образу запроса, представляющему собой конъюнкцию ассоциативнЕзис признаков, каждый из которых закодирован комбинационным кодом, без пермутации ассоциативных признаков в поисковом образе запроса Tl. Недостатком известного устройства определяемым его структурными особенностями, является невозможность моделирования однородных конечных цепей Маркова, Наиболее близким по технической сущности к предлагаемому является згенератор случайного процесса, содер жащий генератор равномерно распределенных случайных чисел, блок ассоциативной памяти, схемы сборки, блок схем совпадения, блок индикаторов, шифратор, выходной регистр и дешифратор, В блоке ассоциативной памяти, разделенной на зоны, в первую зону записываются значения элементов первой стрюки матрицы переходных вероятное тей //AJ и , во вторую зону - значения элеглентов второй строки матрицы и т.д. Таким образом, информация в блоке ассоциативной памяти упорядочена, т,е. номер зоны совпадает с номером состояния цепи Маркова. Фиксирование результата сравнения производитЬя в той зоне, номер которой в текущем такте записан в выходнсш регистре -,2 . Однако известное устройство имеет ограниченные функциональные возможности при моделировании случайных процессов, поскольку не позволяет реализовать вероятностный автомат комneHCHpWaoero типа. Цель изобретения - расширение функциональных возможностей генератора за счет реализации вероятностных автоматов компенсирукяцего типа. Поставленная цель достигается тем что генератор случайного процесса, с держащий генератор равномерно распре деленных случайных чисел, выходы которого соединены с группой входов блока ассоциативной памяти, вход кот рого соединен с первым выходом блока |памяти, второй выход которого соединен со входом блока управления, а входы блока памяти подключены к выхо дам первой группы элементов ИЛИ, входи которых подключены к выходам второй группы элементов ИЛИ, в-ведена группа функциональных преобразователей, выходы которых соединены со вхо дами второй группы элементов ИЛИ, первая группа входов функциональных преобразователей соединена с выходами блока управления, а вторая группа входов функциональных преобразова телей соединена с выходаили блока ассоциативной памяти соответственно. Кроме того, каждый функциональный преобразователь содержит первый, вто рой и третий Элементы ИЛИ, элемент И и триггер, выход которого соедин-ен с первым выходом элемента И, второй вход которого соединен с выходом вто рого элемента ИЛИ, входы первого .и второго элементов ИЛИ являются первой группой входов функционального преобразователя, выходами которого являются выход первого элемента ИЛИ и выход элемента И, единичный вход триггера соединен с выходом третьего элемента ИЛИ, вход третьего элемента ИЛИ и нулевой вход триггера являются второй группой входов ф.ункцио нального преобразователя. На чертеже приведена блок-схема предлагаемого генератора. Генератор содержит генератор 1 равномерно аспределенных случайных чиоел, блок 2 ассоциативной памяти, первую группу элементов ИЛИ 3, вторую группу элементов ИЛИ 4, блок 5 памяти, блок б управления, блоки 7 нормировки, функциональные преобразо ватели 8 и 9, элементы ИЛИ 10-15, элементы И 16 и 17, триггеры 18 и 19 Выходы генератора 1 равномерно ра пределенных случайных чисел соединены с первыми входами блока 2, выходы блока 5 памяти соединены, со вторыми входами блока 2 и со входами блока б управления, выходы элементов ИЛИ 3 соединены через элементы ИЛИ 4 со входами блока 5 памяти, выходы блока 2 соединены со входами блоков 7 нормировки, каждый из которых состоит из функциональных преобразователей 8 и 9. Названные блоки могут быть выполнены в нескольких вариантах. В конкретном выполнении предлагаемого генератора преобразователь 8 содержи элементы ИЛИ 10-12, элемент И 16 и триггер 18, а преобразователь 9 содержит элементы ИЛИ 13-15, элемент И 17 и триггер 19, причем в преобраз вателе 8 входы элементов ИЛИ 10 и 11 соединены с выходами блока 2, выход элемента ИЛИ 10 соединен со входом соответствующего элемента ИЛИ 3, выход элемента 11 соединен с первым входом элемента И 16, ко второму входу которого подсоединен выход триггера 18, а выход элемента И 16 - со входом соответствующего элемента ИЛИ 13, первый вход триггера 18 соединен с соответствующим первым выходом бло.ка 6, , а второй вход триггера 18 через элемент ИЛИ 12 - со вторым и соответствующим третьим выходом блока б, а в преобразователе 9 входы элементов ИЛИ 13 и 14 соединены с соответствующими выходами блока 2, выход элемента ИЛИ 13 соединен со входом Соответствующего элемента ИЛИ 3, а выход элемента ИЛИ 14 - с первым входом элемента И 17, ко второму входу которого подсоединен выход триггера. 19, а. элемента И 17 - со входом соответствующего элемента ИЛИ 3. Первый вход триггера 19 через элемент ИЛИ 15 соединен со вторым и соответствующим третьим выходом блока 6 управления, при этом второй вход триггера 19 соединен с соответствующим первым выходом блока 6 управления. Рассмотрим особенности работы предпагаемого устройства, интерпретируемого как. автономный вероятностный автомат компенсирующего типа с поэлементным изменением матрицы переходных вероятностей // рР pVp ll ;ч;i n. 1-1 nvi. При этом .выполняется условие нормировкиСР;. 1 (J Г) )i:-1 31 Отметим, что в дальнейшем предполагается, что все значения Pi представляют собой дроби со знаменателем :вида 2 (д - целое число) или могут быть апЬроксимированы с удовлетворительной точностью дробями такого вида. Пусть автомат в некоторый момент ремени t находится в i-м состоянии. ыдан соответствующий этому состояию выходной сигнал и получил сигал Нештраф. Тогда в матрице A(j начение элемента Р.. увеличивается а не1 оторую величину др, а все осальные элементы 1-ой строки матриы Ад уменьшаются на величину -АР.; овая матрица переходных вероятносей обозначается как А . Если же в следующемтакте работы втомат получает сигнал Штраф, то Матрице А. элемент P.j. уменьшаетя на величину дР, а все осталь-ные элементы i-и строки А увеличиваются на величину Отметим, что значение ЛР должно быть выбрано таким образом, чтобы ЛР величина - представляла собой дробь со знаменателем вида 2 Я При сделанных предположениях информация в матрице блока АП 2 представляется следующим образом. Разрядность матрицы блока АП 2 о ределяется из соотношения при этом верхняя граница числа стро в матрице блока АП 2 равна 2® хп , причем в каждой из 2 строк размещается один из 2 кодов. Выделим в каждой из п групп, число которых соответствует размерности матрицы переходных вероятностей , подг пы таким образом, чтобы число строк в каждой подгруппе равнялось Р - 2 ° (PIK - значение элементов матрицы //Agil). Тогда для перестройки струк туры в каждой подгруппе необходимо вьщелить базовую и переменную части которые в подгруппах, реализующих т.е. соответствующих переходов обеспечивают установку вида а., , Г V + л - ДР , ,- viitk а в подгруппах, реализующих Р обеспечивают компенсирующие установ ки, т.е. р.р. ЧК. 1К П--1 о-., Р-„.- П--1 Перед началом работы устройства со второго входа блока б управления выдается сигнал начальной установки во все блоки 7 нормировки. По .этому сигналу триггеры 18 и 19 во всех бл ках .7 нормировки устанавливаются в такое положение, что сигналы, посту .пающие на второй вход элементов И 1 преобразователя 8 и на второй вход элементов И 17 преобразователя 9, фиксируют объединение строк блока 2 ассоциативной памяти во всех подгру пах, состоящих из базовых частей, определяемых элементами ИЛИ 10 в пр образователе 8 и элементами ИЛИ 13 преобразователе 9, которое соответс вует распределению вероятностей пер ходов автомата, задаваемого матрице переходных вероятностей J/AQ/( . Режим 1. В этом режиме генератор работает как автономный вероятностн автомат в соответствии с заданной матрицей переходных вероятностей .// А представленной в блоке 2. Случайное число, поступающее на первые входы блока 2 из генератора 1 равномерно распределенных случайных чисел, в сочетании с кодом состояния, поступающим из блока 5 памяти на вторые блока 2, определйет код опроса блока 2. В результате ас-, социативного поиска возбуждается один из выходов блока 2 и чер$з один из элементов ИЛИ 10, 11, 13 и 14 соответствующего блока-7 нормировки и соответствукхций элемент ИЛИ первой группы элементов ИЛИ 3 и соответствующий элемент ИЛИ второй группы элементов ИЛИ 4 выбирается ячейка блока 5 памяти, определяющая код состояния, в которое переходит этот автомат. Этот КОД} в сочетании с новым значением случайного числа, поступает на входы блока 2 и определяет следующий переход автомата. Таким образом, цикл работы абтомата повторяется. Режим 2. в процессе работы автомата, если после перехода из i-го состояния-по сигналу, поступившему из генератора 1, блок б выдает сигнал Нештраф, соответствующий t-й группе, т.е. i-му состоянию автомата, триггер 18 i-го блока нормировки устанавливается таким образом, что к базовой части подгруппы, фиксирующе:р значение вероятности перехода Р.. , подключаются строки блока 2, состав ляющие переменную часть подгруппы, объединенную элементом ИЛИ 11, что увеличивает значение вероятности перехода а- на величину лР. Одновременно с этим, вследствие подачи сигнала Нештраф с ,того же выхода бло- ка б на вход триггера 19 преобразователей 9, входящий в t-й блок 7 нормировки, фиксируется исключение переменной части подгрупп, объединенных элементами ИЛИ 14, задаюгчих вероятности переходов из i-го состояния во все остальные , т.е. значения (k lT n; k # i ) уменьшавсех p. ЛР Если при ются на величину дальнейшей рабоТ(е при переходе автомата из i-то состояния блок 6 управления выдает сигнал Штраф, то по этому сигналу, поступающему на входы i-го блока 7 нормировки выполняется обратная настройка автомата, т.е. |Триггер 18 по сигналу, поступающему через элемент ИЛИ 12 устанавливается таким образом,, что сигналы, поступающие с выхода элемента ИЛИ 11, объединяющего переменную часть подгруппы,, не поступают на вход соответствующего элемента ИЛИ 3 и таким образом, восстанавливается значение Р . Одновременно с этим, вследствие подачи сигнала Штраф с того же выхода §лока 6 на вход триггера 19 через элемент ИЛИ 15 преобразователей 9, входящий в i-й блок 7 нормировки, фиксируется подключение переменной части подгруппы, объединяемых элементом ИЛИ 14, задающих вероятности переходов из 1-го состояния во все остальные, т.е. значения всех .«„. I . 7 I t Т fS (к и 1 ,nj к f и восстанавливаются. Таким образом, второй режим, в ко торый авт|)мат переходит в случае вьвдачи сигналов из блока 6, представ ляет собой режим перестройки структуры автомата. Отметим, что в конкретных случаях число строк в матрице блока 2 оказывается меньше приведенной верхней оценки за счет того, что некоторые значения Pjj..6. -fo,}- . В этом случае соответствующие подгруппы вырождаются в одну строку (f 1) или вообде исключаются (Р, 0), Кроме того если ассоциативные запоминающие элементы, образующие матрицу блока 2, реализуют троичный структурный алфа вит, то число строк в подгруппах может быть минимизировано за счет склеивания различных кодов и использования кубического представления, что достигается установкой соответст вующих ассоциативных запоминающих элементов в некоторых строках блока 2 в безразличное состояние (самомаскирование j . Кроме того, следует также отметит что при рассмотрении работы устройст ва предполагается, что перестройка структуры осуществляется на один шаг, т.е. перестройка структуры для любого i-го состояния может начинать ся только с увеличения Р. на ЛР. На следующем этапе перестройки струк туры для этого состояния возможно только уменьшение нового значения вероятности Р. на Л Р. Соотношение j 1 где n - размерность матрицы переходных вероятностей, справедливо в общем.случае, но в каждом конкретном случае с учетом того, что часть О, оно должно определяться как йр где m 4п - число значения Наибольший эффект от применения предлагаемого устройства достигается в системах моделирования случайных процессов , что обеспечивается следующими факторами: а) выбор состояния перехода для принятого способа представления матриц переходных вероятностей в блоке ассоциативной памяти реализуется, в отличие от известных устройств для моделирования случайных процессов, простым .ассоциативным поиском. б) возможностью отображения в блоке ассоциативной памяти различных матриц переходных вероятностей, динамически изменяемых в процессе работы устройства. Формула изобретения 1.Генератор случайного процесса, содержащий генератор равномерно распределенных случайных чисел, выходы которого соединены с группой входов блока ассоциативной памяти, вход которого соединен с первым выходом блока памяти, второй выход которого соединен со входом блока управления, а входы блока памяти подключены к выходам первой группы элементов ИЛИ, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет реализации вероятностного автомата, компенсирующего типа, он содержит группу функциональных преобразователей, выходы которых соединены со входами второй группы элементов ИЛИ, первая группа входов функциональных преобразователей соединена с выходами блока управления, а вторая группа входов функциональньлх преобразователей соединена с выходами блока ассоциативной, памяти соответственно. 2.Генератор по п. 1, отличающийся тем, что каждый функциональный преобразователь содержит первый, второй и третий элементы ИЛИ, элемент И и триггер, выход которого соединен с первым выходом элемента И, второй вход которого соединен с выходом второго элемента ИЛИ, входы первого и второго элемен.тов ИЛИ являются первой группой входов функционального преобразователя, выходами которого являются выход первого элемента ИЛИ и выход элемента И, единичный вход триггера соединен с выходом третьего элемента ИЛИ, вход третьего элемента ИЛИ и нулевой вход триггера являются второй группой входов функционального преобразователя, в Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР по заявке № 2037964/18-24, 1974. i 2. Авторское свидетельство СССР № 451085, кл. G Об F 1/02, 1973 (прототип).