Вероятностное вычислительное устройство

Иллюстрации

Показать все

Реферат

 

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

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

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

631928 (6I) Дополнительное к авт. свил-ву (22) Заявлено 21.02.77 (21) 2454564/18-24 (51) M. Кл.

G 06 V 15/36 с присоединением заявки № (23) Приоритет (43) Опубликовано05.11.78.Бюллетень №41 (45) Дата опубликования описания 10.11.78

Государственный комитет

Совета Министров СССР по делам изооретений

И OTKPblTHN (53) УДК681 3 (088. 8) Г. B. Добрис, B. П. Касзаков, В. Г. Корчагин и В. В. Яковпев. (72) Авторы изобретения

Государственнэе союзное прэектнэ-конструкторское технэлэгическое бюро пэ прэектирэванию счетных машин и Опытный завод (71) Заявители (54) ВЕРОЯТНОСТНОЕ ВЫЧИСЛИТЕЛЬНОЕ

УСТРОЙСТВО

Изобретение относится к вычиспитепьной технике и может быть использовано дпя вьгчиспения значений А — п(AGOG вт >0 тир-произвольно целые чиспа) и дпя воспроизведения аппроксимируюших функций типа многочпенов, составпенньтх из пинейной комбинации цепых и дробных степеней аргументов, в стохастических вычислите пьных машинах.

Известно вероятностное вычиспитепьное устройство (11выпопняюшее математи- 10 ческую операцию А — (AE 01), однако и только дпя целых чисел —, Наиболее близко к предлагаемому вероятностное вычиспитепьное устройство (2),содержашее преобразователь код- 15 вероятность», датчик случайных чисеп, выход которого подключен к первому входу блока сравнения, второй вход которого соединен с разрядными выходами счетчика, числовой выход которого является 20 выходом устройства.

Это устройство реапизует зависимость

А ф так что выход линейного преобразователя "код-вероятность { ЛПКВ), выпоте25

2 няюшего преобразование P=A (P-вероятность появления символа 1 на выходе

ЛПКВ), соединяется с блоком возведения переменной в целую тп - ную степень.

Затем переменная Р подается на сум И мирующий вход реверсивного счетчика, в цепь обратной связи которого вкпючен блок возведения переменной в целую тт - ную степень. Если выход поспеднего блока подать на вычитающий вход реверсивного счетчика (PC) математическое ожидание РС равно искомой вепиВт3 чине А и.

Гпавный недостаток прототипа — сложность и низкое быстродействие.

Hemü изобретения — упрощение устройства и повышение его быстродействия.

Достигается это бпагодаря тому что в вероятностное вычиспитепьное устройс1 во введены элементы И, триггер, инвертор, второй преобразоватепь код-вероят ность, второй счетчик, второй бпок сравнения, первый вход которого подключен к выходу датчика случайных чисеп, второй вход — к разрядным выходам второ631928 го счетчика, установочный вход которого является числовым входом устройства, а выход старшего разряда второго счетчика подключен к нулевому входу триггера, единичный вход которого пощспючен ф ко входу пуска устройства, а единичный выход триггера соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к выходам соответственно первого и второго преоб- <О раэоватепей код-вероятность - третий

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

Схема вероятностного вычислительного устройства представлена на чертеже.

Устройство содержит счетчики 1,2, блоки сравнения 3, 4,. элементы И 5,6, ® преобразователи код-вероятность 7,8, датчик случайных чисел 9, триггер 10, инвертор 11.

Преобразователи 7 и 8 вырабатывают И на своих выходах случайные поспедоватепьности с вероятностями символов

"1" соответственно Р„и Ря, причем Р=

И 21 1 УЦ

=р-(С и Я - разрядности преобразователей). Разрядности избирают исходя из условия Р Р 61.

Работа устройства начинается с занесения кода двоичного числа А в счетчик

2. После этого подается пусковой сигнал на установочный вход 12 триггера 10.

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

Импульсы переполнения по нупевому входу включают триггер, в результате чего прекращается. поступпение единичных символов на входы счетчиков. При этом содержимое счетчика 1 фиксирует оценку искомой вепичины А ф, причем М<С>„)»Аф

Покажем это. Ипя математического ожидания содержимых счетчиков в -том такте можно записать сцедующие рекуррентные соотношения:

M(Cr > M(Cr>{. + )p,*Ð,tM(cr > (4 — — ii, 4 Р

М М(Сг,)„»М<Сг,) „+

М(сг,) г

+ — P =M(Cr >

Я 2 2 - М

9 где N =- 2, - разрядность счетчиков.

Обозначив Q4 Cr). М; и М<Сyg),=Ì „.и учитывая, что M =О, а М = МЛ,запишем

М 0 о

hh Р м" p . (- - )

1 s М

Р4 Р Я Р t-i

= р >i+(- — )+()+ - + <1

N Н

=Р>{ {-({- >{ J;

Так как при бопьших Й величина ({ — )=å ", 1 то окончательно ф .=м(q-е и 1) (1)

11

М »МД далее

М24 йд(1+ )

М { >{А({э — „>= {{5А{{»Р» и maes@ иЛи

i» — en — (2)

М рг

Подставляя (2) в (1), имеем

Р м,„=N 1-e " ", „А

Р т. е. искомый результат образуется в счетчике 1 в обратном коде.

Заметим, что время выполнения опеРП раций А и в предлагаемом устройстве занимает Т= y-En - тактов работы уст2 ройства. В то же время в прототипе результат устанавливается не менее чем за три постоянных времени, т. е. Т > †„щ

М

Следовательно, относительное ускорение работы предлагаемого устройства т составляет К * — > Разрядность

4 оп преобразователя всегд можно выбрать такой, чтобы выпопнялось соотношение

Р э 0,5, поэтому c{ Э уу@<„{ 4>

Например, если A =™0,1, щ»2, то в соответствии с (4) ускорение работы устройства составляет более чем 65 раз.

В момент переполнения счетчика 2 его содержимое равно К, поэтому

63 1928

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

Редактэр Б. Федэтэв Техред H. Бабурка Кэрректэр Е. Личинская

Заказ 6345/49 Тираж 784 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

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

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

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

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

Вероятностное вычислительное устройство, содержащее преобразовате ль

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

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

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

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

У внимание при экспертизе:

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

2. Яковлев B В., Федоров P. Ф. Стохастические вычислительные машины,.

Машиностроение, 1974, с. 159, рис. 73, а.