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

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

элемента ИЛИ, выход которого соединен с нулевым входом второго триггера, вы-1 ход второго элемента И соединен с, входом Пуск, распределителя импульсов и с единичным входом третьего триггера, выход которого соединен с входом Считывание блока памяти, вход Запись которого подключен к первому выходу блока задания статистических характеристик, выход первого кнопочного элемента подключен к входу Установка распределителя импульсов и к вторым входам первого, третьего и пятого элементов ИЛИ, выход, первого элемента ИЛИ соединен с нулевым входом третьего триггера, выход третьего элемента И - с нулевом входом четвертого триггера, выход которого соединен с восьмым входом вероят ностного преобразователя и с управляющим входом коммутатора, выход второго кнопочного элемента соединен с девятым входом вероятностного преобразователя, с единичным входом четвертого триггера и с входом элемента НЕ, выход регистра кода соединен с

информационным входом блока памяти и с десятым входом вероятностного преобразователя, одиннадцатый вход которого объединен с вторым информационным входом коммутатора и подключен к выходу регистра адреса, второй выход блока задания статистичес- ,

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

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

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

3. Генератор по п. 1, отличающийся тем, что блок задания статистических характеристик содержит кнопочный элемент, два элемента И, элемент НЕ и переключатель, выход которого соединен с входом элемента НЕ и с первым входом первого элемента И, выход которого является первым выходом указанного блока, выход элемента НЕ соединен с первым входом второго элемента И, выход которого является вторым выходом указанного блока, выход кнопочного элемента соединен с вторыми входами первого и второго элементов И.. Изобретение относится к вычислительной технике и может быть исполь-. зовано для моделирования простых и сложных (г-связных) цепей Маркова. Изве.стен генератор, содержащий уп равлпемый датчик случайных двоичных цифр, блок управления, счетчик, блок памяти, регистр, элементы И .Ij. . Недостаток этого генератора заключается в том, что он не позволяет формировать г -связные цепи Маркова. Известен также генераторп-связных цепей Маркова, содержащий регистр сдвига, генера.тор .случайных символов генератор тактовых импульсрв, вероятностный (1, т) - полюсник и элементы И, ИЛИ 2. Однако этот генератор не позволяет формировать многоразрядные числа марковской последовательности. Наиболее близким по технической сущности к. изобретению является генератор цепей Маркова,.содержащий блок ввода, блок управления и управляемый датчик случайных чисел, который .включает в себя генератор равномерно распределенных чисел, регистр адреса, регистр зоны, дешифратор з.ои коммутатор зон, запо.минающее устройство,, элементы И, ИЛИ . Это устройство позволяет формировать многоразрядные случайные числа, причем стохастическую матрицу цепи Маркова задают в виде таблицы состоя НИИ детерминированного автомата, адрее обращения к которой формируют слу чайным образом. Недостаток этого устройства заключается в том, что онр не позволяет формировать Р-связные цепи Маркова Целью изобретения является расширение функциональных возможностей генератора за счет введения -связности в цепь Маркова. Поставленная цель достигается тем что в генератор цепей Маркова,содержа щий блок задания статистических характеристик, блок управления, вероятностный преобразователь, введены ре-. гистр памяти, регистр адреса, регистр кода, блок памяти и коммутатор, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом регистра памяти, первый и второй выходы которого соединены соответственно с первым входом вероятностного преобразователя и с первым информационным входом коммутатора, а блок управления содержит два кнопочных элемента, генератор тактовых импульсов, делитель частоты, распределитель импульсов, элемент задержки, элемент НЕ, три элемента И, пять элементов ИЛИ и четь ре триггера, выход генератора тактовых импульсов соединен через элемент задержки с-первым входом первого эле-, мента И, а также.непосредственно соединен с входом Сдвиг распределителя импульсов и с входом делителя частоты, выход которого соединен с первым вхо- . дом второго элемента И, второй вход которого объединен с первым входом третьего элемента И и подключен к выходу элемента НЕ,,первый выход распределителя импульсов соединен с вторым входом ее роя т нос т; но го преобразователя,, с управляющим входом регистра памяти и с единичным входом первого триггера, выход которого соединен с вторым входом первого элемента И, выход которого соединен с третьим входом вероятностного преобразователя, второй выход распределителя импульсов соединен с вторым входом третьего элемента И, с первым входом первого элемента ИЛИ и с единичным входом вто1эого триггера, выход которого соединен с четвертым входом вероятностного преобразователя, третий выход распределителя импульсов соединен с первым входом второго элемента ИЛИ, выход которого соединен с пятым входом вероятностного преобразователя, четвертый выход распределителя импульсов соединен с первыми входами третьего и четвертого-элементов ИЛИ, выходы которых соединены соответственно с нулевым входом первого т иггера и с шестым входом вероятностного преобразователя, пятый выход распределителя импульсов соединен с вторым входом второго элемента ИЛИ, шестой выход распределителя импульсов соединен с вторым входом четвертого элемента ИЛИ, седьмой выход распределителя импульсов - с третьим входом второго элемента ИЛИ, восьмой выход распределителя импульсов - с третьим входом четвертого элемента ИЛИ, девятый выход распределителя импульсов - с седьмым входом вероятностного преобразователя и с первым входом пятого элемента ИЛИ, выход которого соединен с нулевым входом второго триггера, выход второго элемента И соединен с входом Пуск распределителя импульсов и с единиц ным входом третьего-триггера, выход которого соединен с входом Считывание блока памяти, вход Запись которого подключен к первому выходу блока задания статистических характеристик, выход первого кнопочного элемента подключен к входу Установка распределителя импульсов и к вторым входам первого, третьего и пятого элементов ИЛИ, выход первого элемента ИЛИ соединен с нулевым входом третьего триггера; вых.од третьего элемента И - с нулевым входом четвертого триггера, выход которого соединен с восьмым входом вероятностного преобразователя и с управляющим входом ком мутатора, выход второго кнопочного элемента соединен с девятым входом вероятностного преобразователя, с еди ничным входом четвертого -триггера и с входом элемента НЕ, выход регистра кода соединен с информационным входом блока памяти и.с десятым входом вероятностного преобразователя, одиннадцатый вход которого объединен с вторым информационным входом коммутатор и подключен к выходу регистра адреса второй выход блока задания статистических характеристик соединен с двенадцатым входом вероятностного преобразователя, выход которого является выходом генератора и соединен с трет им информационным входом коммутатора Кроме того, вероятностный преобразователь содержит датчик равномерно распределенных случайные чисел, схему сравнения, элемент ИЛИ, регистр сдвига, два регистра памяти, блок памяти и коммутатор, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом первого регистра памяти, первый и второй выходы которого соединены соответственно с первыми входами элемента ИЛИ и схемы сравнения, выход которой соединен с вторым входом элемента ИЛИ, выход которого соединен с информационным входом регистра сдвига, выход которого соединен с входом второго регистра памяти и с первым информационным входом коммутатора, второй информационный вход которого является первым входом преобразователя, вторым входом которого является управляющий вход регистра сдвига, третьим входом преобразователя является вход Опрос датчика равномерно распределенных случайных чисел, выход которого соединен с вторым входом схемы сравнения, четвертым входом блока является вход Считывание блока памяти, пятым входом блока является управляющий вход первого регистра памяти, шестым входом преобразователя является вход Сдаиг регистра сдвига, седьмым входом преобразователя является управляющий вход второго регистра памяти, выход которого является выходом преобразователя, восьмым входом которого является управляющий вход коммутатора, девятым входом преобразователя является вход Установка датчика равномерно распределенных случайных чисел, десятым входом преобразователя информационный вход блока памяти, одиннадцатым входом преобразователя является третий информационный вход коммутатора, двенадцатым входом преобразователя является вход Запись блока памяти. Кроме того, блок задания статистических характеристик содержит кнопочный элемент, два элемента И, элемент НЕ и переключатель, выход которого соединен с входом элемента НЕ и с первым входом первого элемента И, выход которого является первым выходом указанного блока, выход элемента НЕ соединен с первым входом второго элемента И, выход которого является вторым выходом указанного блока, выход кнопочного элемента соединен с вторыми входами первого и второго элементов И. На фиг. 1 приведена блок-схема генератора; на фиг. 2 - схема блока управления; на фиг. 3 - схема вероятностного преобразователя; на фиг. + схема блока задания статистических характеристик; на фиг. 5 - диаграмма работы блока управления; на фиг. 6 граф, поясняющий работу вероятностного преобразователя; на фиг. таблицы, поясняющие принцип действия генератора. Генератор содержит регистр 1 па-, мяти, блок 2 памяти, коммутатор 3, блок k управления, вероятностный преобразователь 5 блок 6 задания статистических характеристик и связи 7-22 между блоками. Блок управления содержит генератор 23 тактовых импульсов, распределитель импульсов, делитель 25 частоты, элемент И 26, элемент 27 задержки, элемент И 28, элемент ИЛИ 29 триггер 30, элемент ИЛИ 31, триггер .32, элементы ИЛИ 33-35, триггер Зб, элемент НЕ 37, элемент И 38, триг- гер 39. Вероятностный преобразователь содержит датчик tO равномерно распределенных случайных чисел, схему k сравнения, элемент ИЛИ «i, регистр А сдвига, регистр Mk памяти, блок памяти, коммутатор б, регистр 47 памяти. Блок задания статистических харак теристик содержит элементы И. 48 и 49, элемент НЕ 50. Кроме того, генератор содержит ре гистр 51 адреса, регистр 52 кода, пе реключатель 53, кнопочные элементы 54-56. Принцип действия устройства заключается в следующим. Пусть заданаг -связная цепь Маркова, имеющая В состояний х.,;,,,хр, и в этой цепи для всякой ;последова-, тельности состояний длины г (цепочки Sj длины г) определены условные г вероятности Р:: (x;/S), где i 1 ,j j ГГ. / . в принятых обозначениях задание -связной цепи Маркова означает, что задана табл, 1, в которой в левом столбце перечислены все цепочки S, , в п|эавом - соответствующие им плотности распределения условных вероятностей (фиг, 7). Для случая ( 1 .цепь Маркова является простой, однородной цепью. Количество распределений лишь в самом общем случае будет равно числу цепочек Sj , которое равно Е . Во мно гих практически важных случаях для некоторых цепочек распределения могу совпадать, поэтому число m различных распределений удовлетворяет соотношению rniE, В табл, 1 различные распределения помечены индексами у ,У2 - Уп1 Если выполняется условие т К , задание р-связной цепи Маркова можно минимизировать, сведя его к автомат.ной таблице, описывающей функции пер хода и выхода устройства. Такая таблица представляет собой минимальную по объему перерабатываемой информации и эквивалентную табл, 1 фор.му задания -связной цепи. Для минимизации формы задания Г-связной цепи на основе табл, 1 составляют абл, 2 (фиг, 8), в которой столбцы помечены цепочками q, представляющими всевозможные последовательности сортояний длины k, где li- k г-1строки помечены цепочками элементами таблицы являются символы распределений, (индексы или условные номера), соответствующие цепочкам, которые можно получить приписыванием справа к цепочке Sj цепочки q и последующим отбрасыванием от цепочки S; слева числа состоянийу равного длине цепочки q; расположение элементов в первом столбце совпадает с табл, 1,; Цепочки S{ , которым соответствуют одинаковые строки в табл, 2, объединяют в непересекающиеся группы С, GjT,... ,G, - классы эквивалентности, Число п классов эквивалентности равно числу различных строк в табл, 2 и может принимать значение -в пределах в зависимости от вида функции f, задаваемой габп. 1, В табл, 2 в каждой группе G строки одинаковы. Взяв из каждой группы строк по Одной строке получают табл, 3 (фиг, 9), состоящую из п различных строк, помеченных символами соответствующих классов эквивалентности, На основе таблицы 3 строят автоматную табл. 4 (фиг, 10), в которой столбцы помечены состояниями цепи f .j 1 строки помечены символами классов эквивалентности G,,п; на пересечении строки G, 1 Г,п и столбца )j, j T,e находится символ такого класса, в котором находятся все цепочки S, образованные из цепочек кл1асса Gj путем приписывания справа состояния xj и отбрасывания слева первого состояния, а также символ у плотности распределения условных вероятностей, соответствующий этим цепочкам, Табл, 4 представляет собой укрупненную форму задания г-связной цепи Маркова и отображает работу логического автомата, минимального по объему памяти, необходимой для задания закона его функционирования, и эквивалентного автомату, реализуемому в соответствии с табл. 1,Табл,4 описывает работу логического автомата с помощью следующих функций перехода и выхода. 710 Функция перехода 6 1Ц х )G4 44 где t - дискретное время, каждой паре входных сигналов Сих ставит в соответствие новый сигнал, определяющий класс эквивалентности на следующем шаге работы устройства. Функция выхода у (G. ,х)У| каждой паре сигналов G и х ставит в соот ветствие управляющий сигнал у, задающий функцию распределения, с помощью которой будет получено состояние цепи на следуюи ем шаге работы устройства. Таким образом, принцип действия предлагаемого устройства заключается в том, чтоf -связную цепь Маркова задают в виде таблицы функций перехода и выхода детерминированного автомата в адрес обращения к этой таблице формируют .случайным образом, используя для это го текущее состояние цепи. Для иллюстрации построения табл, рассмотрим пример. Пусть t -связная цепь имеет глубину связности р 6 и два состояния: х О, Х2 1 а функция i пусть такова: всем цепочкам S длины г из совокупности .В 2 , содержащим серию из пяти единиц, соответствует распределение (P , Р), а всем прочим цепочкам из этой совокупности соответствует распределение (Р,), т.е. табл. 1 для рассматриваемого примера имеет вид табл. 5 (фиг. 11), где в верхней графе число цепочек равно трем, в нижней - 2 - 3. Для данного примера при составлении табл. 2 можно заметить, что цепочки S разбиваются на эквивалентные классы только при приписывании к ним справа следующих цепочек: q i1, Я2 С11 , 4 :П1 , П4 1111 . . Эти четыре цепочки разбивают все 2 цепочек на семь эквивалентных клас сов (табл. 6, фиг. 12). В табл. 6 семь различных с.трок, которые помечены символами G соответствующих классов. В первой колонке показан вид цепочек, составляющих классы, причем через х обозначены такие состояния, которые могут принимать как значения х, так и значения Хл. Столбцы помечены только четырьмя цепочками q, так как остальные цепочки g не увеличивают числа различных строк. Автоматная табл. 4, построенная на основе данных табл. 6, имеет вид табл. 7 (фиг. 13). 3 Устройство работает следующим образом. R -связную цепь Маркова задают в ви де таблицы функций перехода и выхода, етерминированного автомата (табл.), классам эквивалентности G и распределения у присваивают условные номера и записывают комбинации G и у в блок 2 памяти по адресам G и х в соответствии с автоматной таблицей. Комбинации G и у поступают в блок 2 памяти по шине 18 с блока 6. Комбинации G, X, определяющие адрес комбинаций G, у, поступают по шине 19 с блока 6 через коммутатор 3 на адресный вход блока 2 памяти. Информацию о распределении у записывают в виде функций распределений в блок памяти вероятностного преобразователя 5. При этом функцию распределения задают числами z тар. 12 6 2 PJ 2Ti J где P - вероятность того, что цепь принимает состояние xj k - разность чисел Xj, описывающих состояние цепи, в двоичной системе счисления; zi. Zj, -U ZJ 2.-1, , -rtlL 1 Числа z поступают с блока 6 по шине 18 на информационный вход блока 45 памяти, а адрес чисел zj, который задают в виде комбинаций младшей части,адреса-a j и старшей части, в качестве которой служит номер распределения у, поступает по шине 19 через коммутатор 6 на адресный вход блока S памяти. Формирование младшей части адреса ajjj зависит от принципа действия вероятностного преобразователя и от структуры блока iS памяти. Для рассматриваемого примера соответствие между числами zj и aj-устанавливает граф, изображенный йа фиг. 6. Этот граф отображет процедуру сравнения случайного числа 1, формируемого датчиком tO, с числами z , Числа z;, вписаны в вершины графа. Двоичные коды, записанные слева от вершин графа, представляют собой младшую часть адреса , соответст-, вующего числа z| и формируются регистром сдвига по результатам сравие- -НИИ. Код 001 является начальным адресом. Его записывают в регистр Ц сдвига перед началом каждого цикла сравнения, состоящего из трех тактов. Полученнуй в регистре.3 сдвига ribc, ле трех тактов сравнения код служит текущим состоянием, цепи, т.е. в качестве числа }с: , j Ij2, ..,,6. . Процесс записи информации осуществляется следующим образом. С блока 6 ввода по шине 15 подают сигнал установки исходного состояния который устанавливает в нулевое состояние распределитель Zf и через эл менты ИЛИ 29, 31 и 35 поступает на R входы триггеров 30, 32 и 36 По шине 1б с помощью кнопки 56 в блок управления подают сигнал установки режима работы коммутаторов 3 и 6, Этот сигнал поступает на S вход триг гера 39 и на вход датчика «О для установки его в начальное состояние. Коммутаторы 3 и i6 под действием единичного сигнала, поступающего с выхода триггера 39 по шине 13, перех дят в режим приема информации с блока 6„ Затем с помощью переключателя З, который адресует синхроимпульсы записи, выбирают блок S памяти и набирают на регистре 52 одно из чисел 2J , а на регистре 51 - сЬответствующий этому числу адресJ Нажатием на кнопку 5 формируют синхроимпульс,, который записывает в блок 45 памяти заданное значение zj. После записи всех чисел Zj выбирают с помощью переключателя 53 блок 2 памяти на регистре 52 набирают комбинацию G у, взятую из автоматной таблицы, а на регистре 5 - соответствуюи1ий адрес (комбинацию G и х.взятую из той же таблицы). С помощью кнопки 5 фор мируют синхроимпульс записи, который по шине 1 7 поступает в блок 2 памяти и осуществляет запись информации. После окончания записи всех комбинаций G, у задают начальный адрес блока 2 памяти в виде комбинации G и х. Начальную комбинацию G и х подают из блока 6 ввода по шине 19. Затем с по мощью кнопки 5б переводят генератор, в рабочий режим. При этом в блок 4 управления по шине 16 поступает нуле вой уровень. Единичный уровень на вы ходе элемента НЕ 37 отпирает элемент И 26 и очередной импульс с делителя 25 частоты поступает на вход распределистеля 24 импульсов, для которого этот импульс служит пусковым сигналом. Одновременно этот импульс устанавливает в единичное состояние триггер 3 и блок 2 памяти переходит в режим считывания. Так как до момента появ1310 ления импульса на втором выходе распределителя 2k триггер 39 остается в единичном состоянии, коммутаторы 3 и 6 попрежнему находятся в режиме приема информации с блока 6. ввода, поэтому первое считывание из блока 2 памяти осуществляется по адресу, .который поступает с блока 6 ввода. При этом в регистр 1 поступает комбинация G и у, записанная по -начальному адресу. Регистр 1 так же, как и ячейки блока 2 памяти, условно разделен на две части, одна из которых предназначена для записи номера класса эквивалентности G, а другая - для записи номера распределений у. Чис.ло G с выхода регистра 1 поступает через коммутатор 3 в адресную часть блока 2 памяти, а число у по шине 21 - в вероятностный преобразователь 5; который формирует величину х с распределением, соответствующим номеру у. Значение X поступает на выход генератора и через коммутатор 3 на адресный вход блока 2 памяти. На этом цикл формирования первого значения цепи заканчивается. Формирование следующего текущего значения х происходит аналогичным образом. Отличие состоит в формировании адресной комбинации Сих. Вмес- то начального адреса, подаваемого из б.лока 6 ввода, используются значения G их, полученные в первом цикле работы устройства. Эффективность предлагаемого устройства определяется тем, что при его использовании достигается существенное сокращение объема памяти. Преобразование формы задания Р-связной цепи, основанное на принципе выделения классов эквивалентности, позволяет использовать в блоке 2 памяти пВ ячеек, где п - число классов эквиваентности, f - число состояний цепи. в то время известном устройстве требуется ячеек. Для рассмотренного выше примера автоматная таблица имеет вид табл, 8 и требует использования 14 ячеек, в то время как С 2 64. Необходимо тметить, что для того же примера значение п не существенно растет и ри большей глубине связности, напри1110/499032

иер, при г - 10, п9 9« 2 )| 18. Этот как п 102. Эффективность

пример показывает, что минимизация табл. 1 может быть значительной, так

предлагаемого устройства особенно велика при больших 6 и г.

Фиг.1

0

6

i I i i A

19 2

Фиг.3

||7

zo

U9

tfB

-; 7

I

5Ц

53

Фие.

25

fft,36

11

Фиг.

Ф(г.9

Таблща 1

TadAU ffl

Фиг. 8

Таблица 3

TodAi4t4ff «4

Фиг.Ю

Таблице 5

Уг

Фиг. 11

Таблица 6

Фиг. 11

Фиг. /J

Таблица 7