Вероятностное вычислительное устройство Советский патент 1978 года по МПК G06F7/70 G06F17/18 G06F7/38 

36319 го счетчика, установочный вход которого явпяется числовым входом устройства, а выход старшего разряда второго счетчика подключен к нулевому входу триггера, единичный вход которого подключен f ко входу пуска устройства, а единичный выход триггера соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к выходам соответственно первого к второго преоб- разователей код-вероятность- третий вход второго элемента И соединен с выходом второго блока сравнения, а выход первого блока сравнения через инвертор подключен к третьему входу первого эле- мента И. Схема вероятностного вычислительного устройства представлена на чертеже. Устройство содержит счетчики 1,2, блоки сравнения 3, 4, элементы И 5,6, преобразователи код-вероятность 7,8, датчик случайных чисел 9, триггер 10, инвертор 11. Преобразователи 7 и 8 вырабатывают на своих выходах случайные последовательности с вероятностями символов 1 соответственно Pg, причем R (Е и 2 - разрядности преобразователей). Разрядности избирают исходя из условия F 1 il. Работа устройства начинается с занесения кода двоичного числа А в счетчик 2. После этого подается пусковой сигнал на установочный вход 12 триггера 10. В результате этого открьтаются оба элемента И, и начинается накопление содержимого счетчиков. Сигналы на выходах блоков сравнения формируются, если содержимое соответстйуюшего счетчика не меньше значения кода на выходах датчика 9 на каждом такте работы устройства. В процессе работы содержимое счетчика 2 нарастает, и в некоторый момент времени счетчик переполняется. Импульсы переполнения по нулевому входу вкгаочают триггер, в результате чего прекращается, поступление единичных символов на входы счетчиков. При этом содержимое счетчика 1 фиксирует оценку искомой величины А- , причем Покажем это. Для математического ожидания содержимых счетчиков в i-том такте можно записать следующие рекуррентные соотношения. .1 V их/. Х , .хо. ,,,(---i)P,P,.,) (А М Сг-р-М Сг2)-....,,.,()). где , С - разрядность счетчиков. Обозначив . и ,-АЛ2 и тывая, что М 0, а М МЛ,запишем 0. ( РЛ M,,-vnO-ff), .рД,И.... N|l-0-|iVji Так кик при больших N величина , 0-S) , кончательно Д. N(-t ч) d) МА АЛ. NA(), М2,- МАО §ЛмАе В момент переполнения счетч 1ка 2 его содержимое равно N, поэтому N-NAei Pii , (2) Г2 лПодставляя (2) в (1), имеем M,, N(l-).NfA|),(3) т. е. искомый результат образуется в счетчике 1 в обратном коде. Заметим, что время выполнения операций Afp в предлагаемом устройстве занимает Т |у-6п.т тактов работы устройства. В то же время в прототипе результат устанавливается не менее чем за три постоянных времени, т. е. Следовательно, относительное ускорение работы предлагаемого устройства составляеTot rp-i fm г-Разрядность преобразователя всегда можно выбрать такой, чтобы выполнялось соотношение f 0,5, поэтому oL дыеп jU (4) Например, если А 0,1, , Т соответствии с (4) ускорение работы у„ройе составляет более чем 65

563

С ростом fM быстродействие возрастает еще больше.

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

Формула изобретения Вероятностное вычислительное устройство, содержащее преобразователь код-вероятность, датчик случайных чисел, выход которого подключен к первому входу блока сравнения, второй вход которого соединен с разрядными выходами счетчика, числовой выход которого 5тпяется выходом устройства, отличающееся тем, что, с целью упрощения схемы и повышения ее быстродействия, в нее введены элементы И, триггер, инвертор, второй преобразователь код-вероятность, второй счетчик и второй блок сравнения, первый выход которого подключен к выходу датчика случай86

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

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

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

1.Гейне Б. Р. Стохастическая вычислительная машина, журн. Электроника, 1967, № 14.

2.Яковлев В. В,, Федоров Р. Ф. Стохастические вычислительные машины,. Машиностроение, 1974, с. 159, рис. 73, а.