Автономный вероятностный автомат

 

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

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

Республик (! !)7347О) (6l ) Дополнительное к авт. свид-ву (22)Заивлено02.01.78 (21)2566723/18-24 (51)М. 1(ë.

G 06 F 15/20 с присоединением заявки .%—

Государственный комитет (23) Приоритет по делам изобретений и открытий

Опубликовано 15.05.80. Бюллетень,% 18

Дата опубликования описания 16.05.80 (53 ) УД К 681.8 (088.8) В. М. Глушань и Б. Я. Буянов (72) Авторы изобретения (7I) Заявитель

Таганрогский радиотехнический институт им. В, Д. Калмыкова (54) АВТОНОМНЫЙ ВЕРОЯТНОСТНЫЙ АВТОМАТ

Изобретение относится к вычислительной технике и может быть использовано для моделирования сложных систем: подверженных влиянию случайных воздействий, для построения спепиализированных вычислительных устройств, 5

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

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

Наиболее близким техническим решением к изобретению является автономный вероятностный автомат, состоящий из последовательно соединенных генератора случайных импульсов, алемента Запрет, регистра сдвига, запоминающих логических элементов, генератора тактовых импульсов, матрицы логических алементов, каждый столбец которой состоит из !! H-azogoвых элементов ИЛИ и YI 2-входовых элементов И, первый вход каждого из которых соединен с выходом одного из т1входов элементов ИЛИ, а второй вход- ° с одним из выходов регистра сдвига.Кроме того, устройство содержит блок алементов ИЛИ, входы каждого из которых соединены с выходами алементов И соо1 ветствуютего столбца матрицы логических элементов, а их выходы соединены с первыми входами соответствующих элементов

И; вторые входы которых соединены с выходом генератора тактовых импульсов.

Выход каждого элемента И соединен с соответствующим входом запоминающего логического элемента, выход каждого из которых соединен посредством контактов со входами элементов ИЛИ матрицы логических элементов (2).

При увеличении числа состояний этого автомата необходимо увеличивать соответ« ственно число разрядов регистра сдвига.

А это неизбежно приводит к увеличению периода опросе тактовыми импульсами

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

Цель изобретения - повышение быстро- 15 действия и сокращение количества оборудования автомата с большим числом состояний.

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

"Запрет, второй вход которого соединен с выходом генератора тактовых импульсов, 15 блок элементов И, матрицу логических элементов, блок элементов ИЛИ, блок запоминающих логических элементов, каждая ячейка которого состоит из триггера и элемента ИЛИ, регистр сдвиге, выходы 30 которого соединены соответственно с первой группой входов матрицы логических элементов, вторая группа входов которой соединена соответственно с выходами триг- геров блока запоминающих логических эле- 35 ментов, первые входы триггеров соединены соответственно с выходами блока элементов И, второй вход триггера каждой ячейки соединен с выходом элемента ИЛИ своей ячейки, входы эле- 40 ментов ИЛИ каждой ячейки блока запоминающих логических элементов соединены соответственно с выходами всех триггеров, кроме триггера своей ячейки, при этом группа первых входов блока элемен- 45 тов И объединена и подключена к выходу генератора тактовых импульсов, вторая группа входов блока элементов И соединена соответственно с выходами блока элементов ИЛИ, входы которого подклю- 50 чены к соответствующим выходам матрицы логических элементов, введены дополнительный регистр сдвига, буферный регистр, дополнительный блок элементов И, второй генератор случайных импульсов и 55 второй элемент «Запрет, первый вход которого соединен с выходом второго гене« ратора случайных импульсов, в второй

01 4 вход — с вторым входом первого элементе

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

Сущность изобретения состоит в следуюшем.

Й -рвэрядный регистр сдвига, в котором обеспечивается равновероятность возбуждения его выходных шин, делителя на Й независимых последовательных регистров с меньшим числом разрядов в каждом и равном Й!Ю Соответственно этому делится на и частей (подматриц) и матрица логических элементов тек, что каждая иэ ее частей соединена только с одним из разделенных регистров сдвига.

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

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

На фиг, 1 приведена схеме устройства; на фиг. 2 — пример организации обратных связей.

Устройство состоит из генераторов I и 2 случайных импульсов, элементов 3 и

4 Запрет, дополнительного регистра 5 сдвига, генератора 6 тактовых импульсов (ГТИ), буферного регистра 7, блоков 8 и 9 элементов И, (основног разделенного) регистра 10 сдвига, матрицы 11 логических элементов, блока 12 элементов

ИЛИ, блоке 13 запоминающих логических элементов, каждая ячейка которого состоит из элемента 13 -13 ИЛИ и триггере

1 1.4

5 734

Генератор 1 случайных импульсов через элемент 3 Запрет соединен со входом дополнительного регистра 5 сдвига, выходами соединенного с ".оответствуюшими информационными входами буферного регистра 7, каждый выход которого соединен с первым входом соответствующего элемента И блока 8. Выход 1-го элемента И блока 8 соединен со входом

1 -го (разделенного) регистра 10 сдвига, 10 а выходы каждого 1 -го регистра 10 соединены со входами 1-ой матрицы 11, выходы каждой из. которых соединены со входами соответствующих элементов ИЛИ блока 12. Выходы блока 12 соединены с первыми входами элементов И блока 9, вторые входы которых запараллелены со вторыми входами элементов 3 и 4 "3aпрет" и входом "Перепись" буферного регистра 7 и соединены с выходом генератора 6.

Выход каждого элемента И блока 9 соединен с единичным входом соответствующего триггера блока 13. Второй вход каждого триггера соединен с выходом соответствующего элемента ИЛИ этого же блока.

Выход первого триггера 14 соединен с первым входом матрицы 114 и с первыми входами всех элементов ИЛИ (13 -13п) 30 кроме своего элемента 13.{ ИЛИ. Выход К-го триггера 14 % соединен с К-м входом матрицы 114 и с К-ми входами элементов ИЛИ (134-13 К-1, 13 +4-136), т.е. кроме "своего" элемента 13к ИЛИ.

Выходы остальных триггеров соединены в такой же последовательности с соответствующими входами матрицы 11 и элементами ИЛИ блока 13.

Внутренняя структура всех элементов матрицы 11 и их связи с соответствуюшими узлами устройства идентичны и для

И1-ой матрицы(приведены на фиг. 2), Первый выход 1п -ro разделенного ре45 гистра 10 сдвига соединен с первыми входами элементов И первой строки И -ой матрицы 11п, второй выход - с первыми входами элементов И второй строки матрицы 11 п и т.д. Второй вход каждого элемента И в матрице 11 „соединен с выходом соответствующего элемента ИЛИ. Выходы всех элементов И каждого столбца матрицы 1 1 объединены соответствующим элементов ИЛИ блока 12 (на фиг. 2, приведена часть элементов ИЛИ блока 12)Первые входы всех элементов ИЛИ в матрице 11 щ через контакты соединены

701 6 с выходом (-11 р (1+ 1 3 -го три -гера, вторые входы элементов ИЛИ через контакты соединены с выходом ". (m-1) И(n+25ro триггера, Аналогично организована связь всех остальных входов элементов

ИЛИ в матрице 11„;„с соответствующими триггерами.

Устройство в некоторый произвольный момент времени работает следующим образом.

Случайные импульсы с выхода генератора 1 через элемент "Запрет 3 поступают на вход дополнительного (циклического) регистра 5 сдвига, а с выхода генератора 2 через элемент Запрет 4 и один из открытых элементов И блока 8на вход соответствующего (циклического разделенного) регистра 10 сдвига. Во всех регистрах сдвига в одном из разрядов записана единица, а в остальных разрядах - нули. Интенсивность случайных импульсов обоих генераторов 1 и 2 выбирается такой, чтобы осушествлялось многократное переполнение регистров между моментами опроса Нх состояний тактовыми импульсами. Это обеспечивает равновероятность возбуждения выходных шин всех регистров.

Тактовые импульсы переписывают единицу с возбужденного выхода регистра 5 сдвига в буферный регистр 7, возбуждая соответствующий его выход и открывая тот элемент И блока 8, который подключен к возбужденному выходу буферного регистра 7. Этим самым осуществляется равновероятный выбор одного из разделенных реги тров 10, т.е. подключение его к выходу генератора 2. Кроме этого, тактовые импульсы опрашивают выходные шины всех матриц 11, выдавая на выход автомата единицу с возбужденной шины.;

Обеспечение заданных матриц переходных вероятностей возбуждения выходов автомата осуществляется соответствующей организацией обратных связей с выходов триггеров (14 -14 ) на входы элементов

ИЛИ матрицы 11.

На фиг. 2 приведен пример организации обратных связей, обеспечивающих формирование подматрицы переходных вероятностей вида

0 1/3 tl 2/3 A

Р= 2/3 0 1/зи

1/3o 1/3 t1 1/3 И

Коэффициент 1/й учитывает, что на фиг. 2 пр иведена - tn -а я метр иц а 1 1 м сс своими связями.

/34701

После окончания тактового импульса

Открываются элементы 3 и 4 Запрет и случайные импульсы вновь начинают поступать на один из разделенных регистров 10 и на регистр 5, обеспечивая в соответствии с выше описанным возбуждение выходов автомата с заданными вероятностями

Предлагаемое устройство по сравнению с известным обладает в и раз большим о быстродействием (й — число последовательных независимых регистров, на которые разделен регистр 10 сдвига). Однако при заданном числе состояний автомата М величина числа И имеет оптимальное 15 значение, при котором можно получить максимальное быстродействие. Оптимальное значение величинь1 и будет при ра»» венстве числа разрядов и регистре 5 и в каждом иэ разделенных регистров 10. А 20 так как разрядов Мр,g в регистре 5 должf" но быть столько же,, сколько разделенных независимых регистров 10, то

МР б-- П Я

Г. On т.

25 где после вычислений число l1 Опт необходи. мо округлить до ближайшего большего эначения.

Таким образом, выигрыш по быстродействию получается тем больший, чем большее число состояний Й имеет автомат.

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

35 достигается эа счет разбиения автомата на части. Если в известном автомате матрица логических элементов содержит по

И элементов И, ИЛИ и переключателей (контактов), то в предлагаемом устройа стве их соответственно будет N й, т.е. в П раэ меньше.

Действительно, поскольку матрица 11 делится на 11 равных частей (подматриц) и каждая подматрица HBBseTc> квадратной,45 то в каждой подматрице будет по (Nfn)

2 элементов И, ИЛИ и переключателей. Во всех же И подматрицах общее число указанных элементов составляет величИну (N/n) п - N /n = N /n (о,„,-й ) so

Таким образом, предлагаемое устройство требует в несколько раз (в зависимости от N ) меньших затрат оборудования на его реализацию, чем известное.

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

Автономный вероятностный автомат, содержащий генератор тактовых импульсов, первый генератор случайных импульсов, ВЫХОД КОТОРОГО СОЕДИНЕН С ПЕРВЫМ ВХОДОМ первого элемента "Запрет", второй вход которого соединен с выходом генератора тактовых импульсов, блок элементов И, матрицу логических элементов, блок элементов ИЛИ, блок запоминающих логических элементов, каждая ячейка которого состоит из триггера и элемента ИЛИ, регистр сдвига, выходы которого соединены соответственно с первой группой входов матрицы логических элементов, вторая группа входов которой соединена соответственно с выходами триггеров блока запоминающих логических элементов, первые входы триггеров соединены соответственно с выходами блока элементов И, второй вход триггера каждой ячейки соединен с выходом элемента ИЛИ своей ячейки, входы элементов ИЛИ каждой ячейки блока запоминающих логических элементов соединены соответственно с выходами всех триггеров, кроме триггера своей ячейки, при этом группа первых входов блока элементов И объединена и подключена к выходу генератора тактовых импульсов, вторая группа входов блока элементов И соединена соответственно с выходами блока элементов ИЛИ, входы которого подключены к соответствующим выходам матрицы логических элементов, о т л и ч а ю— шийся тем, что, с целью повышения быстродействия и упрощения автомата, в него введены дополнительный регистр сдвига, буферный регистр, дополнительный блок элементов И, второй генератор случайных импульсов и второй элемент Запрет, первый вход которого соединен с выходом второго генератора случайных импульсов, а второй вход — со вторым входом первого элемента "Запрет и с управляющим входом буферного регистра, разрядные входы которого соединены соответственно с разрядными выходами дополнительного регистра сдвига, вход которого соединен с выходом первого элемента "Запрет, при этом разрядные выходы буферного регистра соединены соответственно с группой информационных входов дополнительного блока элементов И, группа управляющих входов которого объединена и подключена к выходу второго элемента "Запрет".

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

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

% 48 190 1в кл. G 06 F 15/201 197 1.

2. Авторское свидетельство СССР по заявке % 2455327/18-24, кл. G 06 F 15/20. 22,02.77 (прототип).

734701

Составитель Э. Сечина

Редактор С. Лыжова Техред О. Андрейко Корректор М, Пожо

Заказ 2224/12 Тираж 751 Подписное

HHHHTIH Государственного комитета СССР по делам изобретений. и открытий

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

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