Автономный вероятностный автомат Советский патент 1980 года по МПК G06F15/173 G06F7/58 G06F17/00 G06F17/18 

Изобретение относится к вычислительной технике и может быть использовано для моделирования сложных систем: подверженных влиянию случайных воздействий, для построения специализированных вычислительных устройств. Известно устройство для формирования однородной позиционной цепи Маркова, основными узлами которого являются шиф ратор команд управления, набор элементов И, последовательно соединенные гене ратор регулярных импульсов и счетчик, регистр сдвига, ключи, блок запоминающих логических элементов, а также первичгеый источник случайных сигналов li Недостатки этого устройства - сложность его настройки на заданную матрицу переходных вероятностей, аппаратурная избыточность, а также то, что состояния устройства являются нетактируемыми. Наиболее близким техническим решени ем ,к изобретению является автономный вероятностный автомат, состоящий из по следовательно соединенных генератора случайных импульсов, элемента Запрет, регистра сдвига, запоминающих логических элементов, генератора тактовых импульсов, матрицы логических элементов, каждый столбец которой состоит из И Я-входовых элементов ИЛИ и Л 2-входовь1Х элементов И, первый вкод каждого из которых соединен с выходом одного из И входов элементов ИЛИ, а второй вход- . с одним из выходов регистра сдвига. К роме Torot устройство содержит блок элементов ИЛИ, входы каждого из которых соединены с выходами элементов И соот ветствуюшего столбца матрицы логических элементов, а их выходы соединены с первыми входами соответствующих элементов И, вторые входы которых соединены с выходом генератора тактовых импульсов. Выход каждого элемента И соединен с соответствующим входом запоминающего логического элемента, выход каждого из которых соединен посредством контактов со входами элементов ИЛИ матрицы логических элементов 2. При увеличении числа состояний эт.ого автомата необходимо увеличивать соответственно число разрядов регистра сдвига. А это неизбежно приводит к увеличению периода опроса тактовыми импульсами, т.е, к снижению быстродействия. Кроме того, увеличение числа состояний автомата ведет к квадратичному увеличению объема оборудования матрицы логических элементов. Таким образом, недостатками известного устройства являются снижение быстродействия и значительное увеличение объема оборудования при увеличении числа состояний автомата. Цель изобретения - повышение быстродействия и сокращение количества оборудования автомата с большим числом состояний. Эта цель достигается тем, что в вероятностный автомат , .содержащий генератор тактовых импульсов, первый генератор слу чайных импульсов, выход которого соединен с первым входом первого элемента Запрет, второй вход которого соединен с выходом генератора тактовых импульсов блок элементов И, матрицу логических эле ментов, блок элементов ИЛИ, блок запоми нающих логических элементов, каждая ячейка которого состоит из триггера и элемента ИЛИ, регистр сдвига, выходы которого соединены соответственно с первой группой входов матрицы логических элементов, вторая группа входов которой соединена соответственно с выходами триг геров блока запоминающих логических элементов, первые входы триггеров соединены соответственно с выходами блока элементов И, второй вход триггера каждой ячейки соединен с выходом элемента ИЛИ своей ячейки, входы элементов ИЛИ каждой ячейки блока запоминающих логических элементов соединены соответственно с выходами всех триггеров, кроме триггера своей ячейки, при этом группа первых входов блока элементоБ И объединена и подключена к выходу генератора тактовых импульсов,вторая группа входов блока элементов И соединена соответственно с выходами блока элементов ИЛИ, входы которого подключены к Соответствующим выходам матрицы логических элементов, введены дополнительный регистр сдвига, буферный регистр, дополнительный блок элементов И, второй генератор случайных импульсов и

второй элемент Запрет, первый вход которого Соединен с выходом второго генератора случайных импульсов, а второй

элементов, каждая ячейка которого состоит из элемента 13, -13 j ИЛИ и триггера -14. вход - с вторым входом первого элемента Запрет и с управляющим входом буферного регистра, разрядные входы которого соединены соответственно с разрядными выходами дополнительного регистра сдвига, вход которого соединен с выходом первого элемента Запрет , при этом разрядные выходы буферного регистра соединены соответственно с группой информадионньк входов допо/щительного блока элементов И, группа управляющих входов которого объединена и подключена к выходу второго элемента Запрет, Сущность изобретения состоит в следуюш:ем. N -разрядный регистр сдвига, в котором обеспечивается равновероятность возбуждения его выходных шин, делителя на П независимых последовательных регист- ров с меньшим числом разрядов в каждом и равном N (П Соответственно этому делится на И частей (подматриц) и матрица логических элементов так, что каждая из ее частей соединена только с одним из П разделенных регистров сдвига. Так как скорость опроса регистра сдвига находится в линейной зависимости от числа его разрядов, то скорость опроса каждого разделенного регистра и соответ ствуюшей части выходов вероятностного автомата увеличивается в h раз. Каждый из Г1 разделенных регистров сдвига выбирается с равной веро 1Тностью с помощью блока элементов И, регистра, дополнительных И -разрядного регистра сдвига (т.е, в дополнительном регистре сдвига должно быть столько разрядов, сколько разделенных регистров), элемента Запрет и генератора случайных импульсов. Это обеспечивает,как и вслучае неразделенного регистра сдвига, равновероятность возбуждения всех выходов в каждом из разделенных регистров. На фиг, 1 приведена схема устройства; на фиг, 2 - пример организации обратных связей. Устройство состоит из генераторов 1 и 2 случайных импульсов, элементов 3 и 4 Запрет, дополнительного регистра 5 сдвига, генератора 6 тактовых импульсов (ТТИ), буферного регистра 7, блоков 8 и 9 элементов И, (основного разделенного) регистра 10 сдвига, матрицы 11 логических элементов, блока 12 элементов ИЛИ, блока 13 запоминающих логических 57 Генератор 1 случайньгх импульсов рез элемент 3 Запрет соединен со входом дополнительного регистра 5 сдвига, выходами соединенного с соответствующими информационными входами буферного регистра 7, каждый выход которого соединен с первым входом соответствующего элемента И блока 8, Выход i -го элемента И блока 8 соединен со входом 1-го (разделенного) регистра 10 сдвига, а выходы кш сдого i -го регистра Ю соединены со входами i -ой матрицы 11 выходы каждой из. которых соединены со входами соответствующих э юментов ИЛИ блока 12, Выходы блока 12 соединены с первыми входами элементов И блока 9, вторые входы которых запараллелены со вторыми входами элементов 3 и 4 Запрет и входом Перепись буферного регистра 7 и соединены с выходом генератора 6, Выход каждого элемента И блока 9 соединен с единичным входом соответствующего триггера блока 13, Второй вход каждого триггера соединен с выходом соответствующего элемента ИЛИ этого же блока. Выход первого триггера 14 соединен с первым входом матрнпы 11 и с первыми входами всех элементов ИЛИ ( кроме своего элемента 13-{ ИЛИ, Выход К-го триггера 14 Ч соединен с К-м входом матрицы 11 и с К-ми входами элементов ИЛИ (13 -13Vi, 13Х-И-13и), т.е. кроме своего элемента 131 ИЛИ. Выходы остальных триггеров соединены в такой же последовательности с соответствующими входами матрицы 11 и элементами ИЛИ блока 13, Внутренняя структура всех элементов матрицы 11 и их связи с соответствующими узлами устройства идентичны и для Т1-ой матрицы (приведены на фиг. 2JL Первый выход m -го разделенного регистра Ю сдвига соединен с первыми exo дами элементов И первой строки Hi-ои матрицы llnji второй выход - с первыми входами элементов И второй строки матр цы 11 и т,д. Второй вход каждого элемента И в матрице 11 соединен с выходом соответствующего элемента ИЛИ. Вы ходы всех элементов И каждого столбца матрицы объединены соответствующим элементов ИЛИ блока 12 (на фиг. 2. приведена часть элементов ИЛИ блока 12 Первые входы всех элементов id ЛИ в матрице 11 у через контакты соединены 016 с выходом1 т-А) N (.) триггера. вторые входы элементов ИЛИ через контакты соединены с выходом (т--l)N(ni-2.)lго триггера, Аналогично организована связь всех остальных входов элементов ИЛИ в матрице И с соответствующими триггерами. Устройство в некоторый произвольный момент времени работает следующим обрадом. Случайные импульсы с выхода генерагора 1 через элемент Запрет 3 посту„ают на вход дополнительного {циклического) регистра 5 сдвига, а с выхода генератора 2 через элемент Запрет 4 и один из открытых элементов И блока 8 на вход соответствующего (циклического разделенного) регистра 1О сдвига. Во всех регистрах сдвига в одном из разрядов записана единица, а в остальных разрядах - нули. Интенсивность случайных импульсов обоих генераторов 1 и 2 выбирается такой, чтобы осуществлялось многократное переполнение регистров между моментами опроса их состояний тактовыми импульсами. Это обеспечивает равновероятность возбуждения выходных шин всех регистров. Тактовые импульсы переписывают единицу с возбужденного выхода регистра 5 сдвига в буферный регистр 7, возбуясдая соответствующий его выход и открывая тот элемент И блока 8, который подключен к возбужденному выходу буферного регистра 7, Зтнм самым осуществляется равновероятный выбор одного из разделенных регистров Ю, т.е. подключение его к выходу генератора 2, Кроме этого, тактовые импульсы опрашивают выходные шины всех матриц 11, выдавая на выход аъ , томата единицу с возбужденной шины,; Обеспечение заданных матриц переход ных вероятностей возбуждення выходов автомата осуществляется соответствующей организацией обратных связей с выходов триггеров {14, -14j) на входы элементов ИЛИ матрицы 11, На фиг, 2 приведен пример орган изаций обратных связей, обеспечивающих фермированне подматрицы переходных вероятностей ввда О1/ЗП 2/3 П 2/ЗпО 1/31Л 1/3 1/ЗП 1/ЗП Коэффициент l/nучитывает, что на фиг. 2 приведена hi -ая матрица 11 nice своими связями. После окончания тактового импульса открываются элементы 3 и 4 Запрет и случайные импульсы вновь начинают поступать на один из разделенных регист ров 1О и на регистр 5, обеспечивая в соответствии с выше описанным возбуждение выходов автомата с заданными вероятностями. Предлагаемое устройство по сравнению с известным обладает в И раз большим быстродействием ( И - число последователь ных независимых регистров, на которые разделен регистр 10 сдвига). Однако при заданном числе состояний автомата N величина числа И имеет оптимальное значение, при котором можно получить максимальное быстродействие. Оптимальное значение величиньГ h будет при равенстве числа разрядов и регистре 5 и в каждом из разделенных регистров 10. А так как разрядов ЛЛр.д в регистре 5 долж но быть столько же,, сколько разделенных независимых регистров 1О, то Pr.S- Onrгде после вычислений число П опт необходи. МО округлить до ближайшего большего .явдчен Таким образом, выигрыш по быстродей ствию получается тем больший, чем большее число состояний N имеет автомат. Несмотря на то, что в предлагаемый автомат введены дополнительные элементы, оно наряду с повышением быстродействия, в целом оказывается и менее громоздким по сравнению с известным. Это достигается за счет разбиения автомата на части. Если в известном автомате маГ рица логических элементов содержит по N элементов И, ИЛИ и переключателей (контактов), то в предлагаемом устройстве их соответственно будет N /h7T.e. в П раз меньше. Действительно, поскольку матрица 11 делится на И равных частей (подматриц и каждая подматрицаяшшется квадратной. - то в каждой подматрице будет no(N/n) элементов И, ИЛИ и переключателей. Во всех же И подматрицах обшее число указанных элементов составляет величину f / 2. v ) n N /П тч опт Таким образом, предлагаемое устройство требует в несколько раз (в зависимости от N ) меньших затрат оборудования на его реализацию, чем известное. Формула изобрет ения Автономный вероятностный автомат, содержащий генератор тактовых импульсов, первый генератор случайных импульсов. выход которого соединен с первым входом первого элемента Запрет, второй вход которого coeamieH с выходом генератора тактовых импульсов, блок элементов И, матрицу логических элементов, блок элементов ИЛИ, блок запомш1ающих логических элементов, каждая ячейка которого состоит из триггера и элемента ИЛИ, регистр сдвига выходы которого соединены соответственно с первой группой входов матрицы логических элементов, вторая группа входов которой соединена соответстве}1но с выходами триггеров блока заломинающих логических элементов, первые входы триггеров соединены соответственно с выходами блока элементов И, второй вход триггера каждой ячейки соединен с выходом элемента ИЛИ своей ячейки, входы элементов ИЛИ каждой ячейки блока запоминающих логических элементов соединены соответственно с выходами всех триггеров, кроме триггера своей ячейки, при этом группа первых входов блока элементов И объединена и подключена к генератора тактовых импульсов, втоР группа входов блока элементов И соеаинена соответственно с выходами блока элементов ИЛИ, входы которого подключены к соответствующим выходам матрицы логических элементов, о т л и ч а ю ш и и с я тем, что, с целью повышения быстродействия и упрощения автомата, в него введены дополнительный регистр сдвига, буферный регистр, дополнительный блок элементов И, второй генератор случайных импульсов и второй элемент Запрет, первый вход которого соединен с выходом второго генератора случайных импульсов, а второй вход - со вторым входом первого элемента Запрет и с управляющим входом буферного регистра, разрядные входы которого соединены соответственно с разрядными выходами дополнительного регистра сдвига, вход которого соединен с выходом первого элемента Запрет, при этом разрядные выходы буферного регистра соединены соответственно с группой информационных входов допол- нительногоблокаэлементов И, группауправляющих входов которого объединена и подключена к выходу второго элемента Запрет. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 4819О1, кл. G 06 F 15/20, 1971. 2.Авторское свидетельство СССР по заявке № 2455327/18-24, кл. G Об F 15/20, 22,02.77 (прототип).

ЬыхОдЫ

Фaг.i

отгтн

от ре2Ц.с7лраю7п

j