Генератор цепей маркова

 

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) 3(51) ОПИСАНИЕ ИЗОБРЕТЕН

К ABTOPCHOIVlY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3454378/18-24 (22) 14.06.82 (46) 23,10.83. Бюл. 1 39 (72) 10,А. Альпин, Г.Г. Баранов, В.М. Захаров и Ю.С, Комаров (71) Казанский ордена Ленина и ордена

Трудового Красного Знамени государств енный университет им. В.И. Ульянова"

Ленина (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

Н 330452, кл. G 06 F 7/58, 1970.

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

h 437061, кл. G 06 F 7/58, 1973.

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

М 290281, кл. G 06 F 7/58, 1969 (прототип). (54) (57) 1. ГЕНЕРАТОР ЦЕПЕЙ МАРКОВА, содержаший блок задания статических характеристик,. блок управления, вероятностный преобразователь, о т л и -. ч а ющи и с я тем, что, с целью расширения функциональной возможности генератора эа счет введения г -свяэ" ности в цепь Маркова, он содержит регистр памяти, регистр кода, регистр адреса, блок памяти и коммутатор, вы" ход которого соединен с адресным вхо" ,дом блока памяти, выход которого coe"" динен с информационным, входом регистра памяти, первый и второй выходы ко." торого соединены соответственно с первым входом вероятностного преоб-, . разователя и с первым информационным ... входом коммутатора, а блок управления содержит два кнопочных элемента, ге-. нератор тактовых импульсов, делитель частоты, распределитель импульсов, элемент задержки, элемент НЕ, три элемента И, пять элементов ИЛИ и четыре триггера, выход генератора тактовых импульсов соединен через элемент задержки с.первым входом пер" вого элемента И, а также непосредственно соединен с входом "Сдвиг" распределителя импульсов и с входом делителя частоты, выход которого соединен с первым входом второго элемента И, второй вход которого объедиHeн с первым входом третьего элемента И и подключеH к выходу элемента

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

ИЛИ, шестой выход распределители импульсов — с вторым входом четвертого

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

НЕ, выход регистра кода соединен с

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

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

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

"Считывание" блока памяти, пятым входом блока - управляющий вход первого регистра памяти, шестым входом преобразователя - вход "Сдвиг" регистра сдвига, седьмым входом преобразователя - управляющий вход второго регистра памяти, выход которого является выходом преобразователя, восьмым входом которого является управляющий вход коммутатора, девятым входом преобразователя является вход

"Установка" датчика равномерно распределенных случайных чисел, десятым входом преобразователя — информационный вход блока памяти, одиннадцатым входом преобразователя - .третий информационный вход коммутатора, двенадцатым входом преобразователявход "Запись" блока памяти.

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

1 1049903 2

Изобретение относится к вычисли-. тельной технике и может быть исполь-. зовано для моделирования простых и сложных (.r-связных) цепей Маркова.

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

Известен также генератор и -связных цепей Маркова, содержащий регистр сдвиГа, генератор .случайных символов, генератор тактовых импульсов, вероят.- 15 ностный (1, m) - полюсник и элементы

И, ИЛИ j2) .

Однако этот генератор не позволяет формировать многоразрядные числа марковской посЛедовательности. . 20

Наиболее близким по технической сущности к изобретению является ге- нератор цепей Маркова, содержащий блок ввода, блок управления и управляемый датчик случайных чисел, кото- 25 рый .включает в себя генератор равно-. мерно распределенных чисел, регистр. адреса, регистр эоны, дешифратор зон, коммутатор зон, запоминающее устройство, элементы И, ИЛИ (3), 30

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

Маркова задают в виде таблицы состояний .детерминированного автомата, ад- рес обращения к которой формируют слу чайным образом, Недостаток этого устройства за" ключается в том, что онр не позволяет формировать и -связные цепи Маркова,40

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

Поставленная цель достигается тем, 45 что в генератор цепей Маркова, содержащий блок задания статистических характеристик, блок управления, вероятностный преобразователь, введены ре-. гистр памяти регистр адреса регистр 50 кода, блок памяти и коммутатор, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом регистра памяти первый и второй выходы ко1

55 торо го соединены соот ветст вен но с первым входом вероятностного преобразователя и с первым информационным входом коммутатора, а блок управления содержит два кнопочных элемента, генератор тактовых импульсов, делитель частоты, распределитель импульсов, элемент задержки, элемент НЕ, три элемента И, пять элементов ИЛИ и четь ре триггера, выход генератора тактовых импульсов соединен через элемент задержки с. первым входом первого элемента И, а также, непосредственно соединен с входом "Сдвиг" распределителя импульсов и с входом делителя частоты, выход которого соединен с первым входом второго элемента И, второй вход которого объединен с первым входом третьего элемента И и подключен к выходу элемента НЕ,, первый выход распределителя импульсов соединен с вто" рым входом вероятностного преобразователя,. с управляющим входом регистра памяти и с единичным входом первого триггера, выход котороп» соединен с вторым входом первого элемента И,. выход которого соединен с третьим входом вероятностного преобразователя, второй выход распределителя импульсов соединен с вторым входом третьего элемента И, с первым входом первого элемента ИЛИ и с единиче ным входом второго триггера, выход которого соединен с четвертым входом вероятностного преобразователя, третий выход распределителя импульсов соединен с первым входом второго элемента ИЛИ, выход которого соединен с пятым входом вероятностного преобразователя, четвертый выход распределителя импульсов соединен с первыми Входами третьего и четвертого:элементов

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

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

04ЭЭО3 ным входом третьего триггера,. выход которого соединен с входом "Считывание" блока памяти, вход "Запись" которого подключен к первому выходу блока задания статистических харак . теристик, выход первого кнопочного элемента подключен к входу "Установка" распределителя импульсов и к вторым входам первого, третьего и пятого

10 элементов И1!И, выход первого элемента

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

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

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

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

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

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

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

НЕ соединен с первым входом второго элемента И, выход которого является вторым выходом укаэанного блока, выход кнопочного элемента соединен с вторыми входами первого и второго элементов И, На фиг. приведена блок-схема генератора; на фиг. 2 — схема блока управления; на фиг. 3 — схема вероятностного преобразователя; на фиг. 4 схема блока задания статистических характеристик; на фиг. 5 — диаграмма работы блока управления; на фиг, 6граф, поясняющий работу вероятностного преобразователя; на фиг. 7-!3таблицы, поясняющие принцип действия генератора.

Генератор содержит регистр 1 па-. мяти, блок 2 памяти, коммутатор 3, блок 4 управления, вероятностный преобразователь 5, блок 6 задания статистических характеристик и связи

7-22 между блоками.

Блок управления содержит. генератор 23 тактовых импульсов, распределитбль 24 импульсов, делитель 25 частоты, элемент И 26, элемент 27 затриггер 30, элемент ИЛИ 31, триггер

32, элементы ИЛИ 33-35, триггер 3б,, элемент НЕ 37, элемент И 38, триг- гер 39.

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

Принцип действия устройства заключается в следующим, Пусть задана» -связная цепь Маркова, имеющая состояний х,...,хр, " и в этой цепи для всякой последова-, тельности состояний длины r (цепочки

S; длины r) определены условные r . вероятности Р; (x>/S„), где i = 1,Р";

j = l Е

В принятых обозначениях задание -связной цепи Маркова означает, что

30 задана табл. 1, в которой в левом столбце пере числены все цепочки 5;, в правом - соответствующие им плотности распределения условных вероят" ностей (фиг. 7). Для случая » =1 цепь Маркова является простой, однородной цепью.

Количество распределений лишь в самом общем случае будет равно числу, цепочек Sj, которое равно f . Bo мно- 40 гих практически важных случаях для некоторых цепочек распределения могут совпадать, поэтому число m различных распределений удовлетворяет соотношению rn 0" . В табл. 1 различные 45 распределения помечены индексами ! у у у ° ° ° р у»» °

Если выполняется условие»»» (8, задание v — связной цепи Маркова можно . минимизировать, сведя его к автомат- 50 ной таблице, описывающей функции. пере. хода и выхода устройства. Такая таблица представляет собой минимальную по объему перерабатываемой информации и эквивалентную табл. l форму 55 задания 1 -связной цепи.

Для минимизации формы задания

Y -связной цепи на основе табл. 1 со

5 1049903 6 держки, влемент. И 28, элемент ИЛИ 29, : ставляют уабл. 2 (фиг. 8), в которой столбцы помечены цепочками q, пред" ставляющими всевозможные последовательности состояний длины k, где

1 k< r- 1 строки помечены цепочками

S;; элемейтами таблицы являются сийволы распределений, (индексы или условные номера), соответствующие цепочкам, которые можно получить приписысдвига, регистр 44 памяти, блок 45 10 ванием справа к цепочке 5> цепочки q памяти, коммутатор 46, регистр 47 и последующим отбрасыванием от цепамяти. почки S; слева числа состояний-, равБлок задания статистических харак" ного длине цепочки q; расположение теристик содержит элементы И. 48 элементов в первом столбце совпадает и 49, элемент HE 50. 15 с табл. 1.

Кроме того, генератор содержит ре". Цепочки Ь», которым соответствуют гистр 51 адреса, регистр 52 кода, пе" одинаковые строки в табл. 2, объедиреключатель 53, кнопочные элементы няют. в непересекающиеся группы G

54-56 с °

2 ° G „„...Gä, - классы эквивалентности.

Число и классов эквивалентности равно числу различных строк в табл. 2 и может принимать значение в пределах пап k Г в зависимости от вида функции Ю, задаваемой табл. 1. т

В табл. 2 в каждой группе G строки одинаковы. Взяв из каждой группы строк по одной строке получают табл. 3 (фиг. 9), состоящую из и различных строк, помеченных символами соответствующих классов эквивалентности.

На основе таблицы 3 строят автоматную табл. 4 (фиг. 10), в которой столбцы помечены состояниями цепи

;.x>,j=l,/; строки помечены символами классов эквивалентности G,,1=1,п; на пересечении строки G, 1=Г,п и столбца х», »=1,6 находится символ такого класса, в котором находятся все цепочки S образованные из цепочек класса G< путем приписывания справа состояния х» и отбрась»вания слева первого состояния, а также символ у плотности распределения условных вероятностей, соответствующий этим цепочкам.

lТабл. 4 представляет собой укрупненную форму задания r -связной цепи Маркова и отображает работу логического автомата, минимального по объему памяти, необходимой для задания закона его функционирования, и эквивалентного автомату, реализуемому в соответствии с табл. l. Табл.4 описывает работу логического автомата с помощью следующих функций перехода и выхода.

1049903

Функция перехода о (6,х )6, где t - дискретное время, каждой паре входных сигналов G и х ставит в соот еетст вие новый сигнал, определяющий класс эквивалентности на следующем юаге работы устройства. функция выхода 3I (G,х )=у каждой паре сигналов G и х ставит в соответствие управляющий сигнал у, задающий функцию распределения, с помощью 10 которой будет получено состояние цепи на следующем шаге работы устройства.

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

Для иллюстрации построения табл,4 рассмотрим пример.

Пусть г -связная цепь имеет глубину связности = 6 и два состояния: 25 х = О, х2 = 1, а функция 1 пусть такова: всем цепочкам S длины r из совокупности .k 2, содержащим се)Э рию иэ пяти единиц, соответствует распределение (Р, Р ), а всем прочим цепочкам из этой совокупности

1 соответствует распределение (Р,Р2), т.е. табл. 1 для рассматриваемого примера имеет вид табл. 5 (фиг.. 11), где в верхней графе число цепочек равно трем, в нижней - 2 - 3.

Для данного примера при составлении табл. 2 можно заметить, что цепочки S разбиваются на эквивалентные классы только при приписывании к ним 4О справа следующих цепочек: q)= (1, q а11>, q = C111>, 1 = (11110, Эти четыре цепочки разбивают все

2 цепочек на семь эквивалентных клас сов (табл. 6, фиг. 12).

В табл. 6 семь различных строк, которые помечены символами G соответствующих классов, В первой колонке показан вид цепочек, составляющих классы, причем через х обозначены та50 кие состояния, которые могут принимать как значения х1, так и значения х . Столбцы помечены только четырьмя цепочками q, так как остальные цепочки g не увеличивают числа различных строк.

Автоматная табл. 4, построенная на основе данных табл. 6, имеет вид табл. 7 (фиг. 13).

Устройство работает следующим образом, -связную цепь Маркова задают в ви" де таблицы функций перехода и выхода детерминированного автомата (табл. 4), классам эквивалентности G и распределения у присваивают условные номера и записывают комбинации G и у в блок 2 памяти по адресам G и x в соответствии с автоматной таблицей.

Комбинации G и у поступают в блок 2 памяти по шине 18 с блока 6. Комбинации G, x, определяющие адрес комбинаций G, у, поступают по шине 19 с блока 6 через коммутатор 3 на адресный вход блока 2 памяти.

Информацию . о распределении у записывают в виде функций распределе ний в блок 45 памяти вероятностного преобразователя 5. При этом функцию распределения задают числами z такими что где P — вероятность того, что цепь принимает состояние х1

- разность чисел х, описывающих состояние цейи, в двоичной системе счисления; т1-, -1 т1 2 -1, то=-1, к»

zp =2-1

Числа z1 поступают с блока 6 по шине 18 на информационный вход блока

45 памяти, а адрес чисел z>, который задают в виде комбинаций младшей час- ти, адреса-а и старшей части, в

4 качестве которой служит номер распределения у, поступает по шине 19 через коммутатор 46 на адресный вход блока 45 памяти.. формирование младшей части адреса а зависит от прин1 ципа действия вероятностного преобразователя 5 и от структуры блока 45 памяти, Для рассматриваемого примера соответствие между числами z> и а устанавливает граф, изображенный йа фиг. 6. Этот граф отображет процедуру сравнения случайного числа 1, формируемого датчиком 40, с числами zj

Числа z<, вписаны в вершины графа.

Двоичные коды, записанные слева от вершин графа, представляют собой младшую часть адреса а ., соответствующего числа л1 и формйруются регист ром 43 сдвига по результатам сравне-, ний. Код 001 является начальным адресом. Его записывают в регистр 43 сдвига перед началом каждого цикла сравнения, состоящего из трех тактов.

9 1049

Полученный в регистре.43 сдвига йос,ле трех тактов сравнения код служит текущим состоянием. цепи, т,е. в качестве числа х ., j = 1,2,...,г..

Процесс записи информации осу" 5 ществляется следующим образом.

С блока 6 ввода по шине 15 подают сигнал установки исходного состояния, который устанавливает в нулевое состояние распределитель 24 и через эле- О менты ИЛИ 29, 31 и 35 поступает на

R вeх оoд ы тTр и г lгеeр оoв e 3300, 32 и 36. Ilo шине 16 с помощью кнопки 56 в блок. 4 управления подают сигнал установки режима работы коммутаторов 3 и 46. 15

Этот сигнал поступает на 5 вход триг".. гера 39 и на вход датчика 40 для установкии его в начальное состояние.

Коммутаторы 3 и 46 под действием единичного сигнала, поступающего с - Ю выхода триггера 39 по шине 13, .переходят в режим приема информации с бло" ка 6. Затем с помощью переключателя

43, который адресует синхроимпульсы записи, выбирают блок 45 памятй и 25 набирают на регистре 52 одно из чи" сел z1 а на регистре 5I - соответ" ствующий этому числу адрес, Нажатием на кнопку 54 формируют синхроим" пульс,.который записывает в блок 45 щ

Э по шине 17 поступает в блок 2 памяти 40 и осуществляет запись информации.

После окончания записи всех комбина- ций G, у задают начальный адрес блока 2 памяти в виде комбинации G и х.

Начальную комбинацию G и х гюдают из блока 6 ввода по шине 19. Затем с поьющью кнопки 56 переводят генератор, в рабочий Режим. При этом в блок 4 управления по шине 16 поступает нулевой уровень. Единичный уровень на выходе элемента НЕ 37 отпирает элемент

И 26 и очередной импульс с делителя

25 частоты поступает на вход распре" делителя 24 импульсов, для которого этот импульс служит пусковым сигналом.:

Одновременно этот импульс устанавливает в единичное состояние триггер 36 и блок 2 памяти переходит в режим считывания. Так как до момента появ903 10 ления импульса на втором выходе распределителя 24 триггер 39 остается в единичном состоянии, коммутаторы 3 и 46 попрежнему находятся в режиме приема информации с блока 6. ввода, поэтому первое считывание из блока 2 памяти осуществляется гю адресу,,который гюступвет с блока 6 ввода. При этом в регистр 1 поступает комбинация С и у, записанная по начальному адресу.

Регистр 1 так же, как и ячеики блока 2 памяти, условно разделен на две части, одна из которых предназначена для записи номера класса эквивалентности G, а другая - для записи номера распределений у. Число G с выхода регистра 1 поступает через коммутатор 3 в адресную часть блока 2 памяти, а число у по шине 21 - в вероятностный преобразователь 5; который формирует величину х с распределением, соответствующим номеру у. Значение х поступает на выход генератора и через коммутатор 3 на адресный вход блока 2 памяти. На этом цикл формирования первого значения цепи заканчивается. !

Эффективность предлагаемого устройства определяется тем, что при его исгюльзовании достигается существенное сокращение обьема памяти. Пре" образование формы задания Р -связной цепи, основанное на принципе выделения классов эквивалентности, позволяет исгюльзовать в блоке 2 памяти п8 ячеек, где и -. число классов эквивалентности, - число состояний цепи, в то время как в известном устройст0с. ве требуется ячеек. Для рассмотренного выше примера автоматная таблица имеет вид табл. 8 и требует использования ng = 7 ° 2 14 ячеек, в то время как 8" = 2 = 64. Необходимо отметить, что для того же примера ,значение пС не существенно растет и при больней глубине связности, наприпамяти заданное значение z> . После Формирование следующего текущего записи всех чисел z» выбирают с по- значения х- происходит аналогичным мощью переключателя 53 блок 2 памяти, образом. Отличие состоит в формирона регистре 52 набирают комбинацию G, вании адресной комбинации G и х. Вмесу, взятую из автоматной таблицы, а то начального адреса, подаваемого из

35 на регистре 51 - соответствующий ад- блока 6 ввода, используются значения рес (комбинацию G и х взятую из той G и х, полученные в первом цикле раже таблицы). С помощью кнопки 54 фор-. боты устройства. мируют синхроимпульс записи который

11 10499 мер, при r 10, и B 9 ° 2 Ф 18, Этот прииВ Р показывает что минимизация табл. I может быть значительной, так

03 12 как п0 18 (< 8"= 1024, Эффективность предлагаемого устройства особенно велика при больших и r, 1049903 а499оз

Фиа Ф

1049903

10,3b

12 ху

Фи8.6

1049903

7Флица 1

7айица Г

Тадлща Р

1049903

1049903

Фиа 15

Заказ 0427/46

Тираж 706 Подписное

ВНИИПИ Государственного. комитета СССР по делам изобретений и открытий.313035, Москва, 6-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, Составитель А. Карасов

Редактор Т. Киселева Техред М,Тепер Корректор А. Повх