Вероятностное устройство для возведения в квадрат

Вероятностное устройство для возведения в квадрат

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Социапистических

Республик

«>857991 (63) Дополнительное к авт. свид-ву р )м. кл. (22) Заявлено 24. 12. 79 (21) 2857414/18-24 с присоединением заявки H (23) Приоритет

Опубликовано 23.08.81. Бюллетень М 31

Дата опубликования описания 23. 08. 81

G 06 F 7/70

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

СССР оо деяаи изобретений и открытий (53) УДК 681. 3 (088. 8) (72) Авторы изобретения

Г. В. Добрис, P. Ф. Федоров и В. В.

Ленинградский ордена Ленина институт железнодорожного транспорта им. а

В.И. Образцова (71) Заявитель (54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ

В КВАДРАТ

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

Йзвестны устройства для возведения в квадрат, содержащие генератор случайных чисел, линейный преобразователь код-вероятность, элемент задержки, элемент И и счетчик результатов 1) н P2) .

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

Наиболее близким техническим реше- 15 нием к предлагаемому изобретению является устройство, содержащее генератор псевдослучайных чисел, два линейных преобразователя код-вероятность, элемент задержки, элемент И 20 и счетчик результата, причем вход счетчика результата подключен к выходу элемента И, первый вход которого подключен к выходу первого линейного преобразователя код-вероятность,а второй вход — через элемент задержки к выходу второго преобразователя кодвероятность. При этом выходы генератора псевдослучайных чисел подключены к соответствующим ра,зрядным входам Зо первого линейного преобразователя ,код-вероятность. Устройство реализует операцию умножения двоичных чисел

A и В, коды которых занесены в регистры преобразователей код-вероятность.

Операцию возведения в квадрат указанное устройство выполняет при занесении в регистры обоих преобразователей одного и того же числа A $3j .

Недостатком такого устройства является его сложность (наличие двух преобразователей код-вероятность при одной входной переменной). Устранение же второго преобразователя кодвероятность и подключение входа элемента задержки к выходу первого преобразователя приводит к понижению точности в 2-4 раза. . Цель изобретения — упрощение устройства и повышение точности работы.

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

857991

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

i-ый вход которого (i = 1,2,...n) соединен с j-ым выходом генератора псевдослучайных чисел, причем п-2(i-1)(п-п>),п, >если i< 2 и и+1 и- (2 (и-1)+1) (n-»>)п>одп,если i ) 2 у

n+1 где п,m(n ) m) — степени характеристического полинома Х" + X + 1 генератора псевдослучайных чисел.

На чертеже представлена блок-схема устройства.

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

Устройство работает следующим образом.

Перед началом операции в регистр преобразователя код-вероятность 2 заносится подлежащее возведению в квадрат исходное число А, счетчик

5 результатов устанавливается в нуль, а в регистр генератора 1 псевдослучайных чисел заносится произвольное исходное число Хс (за исключением нуля). При работе устройства последовательность псевдослучайных чисел Х, К = 1,2, й, вырабатываемых генератором 1, сравнивается в преобразователе код-вероятность 2 с исходным числом A. В результате на выходе преобразователя код-вероятность 2 образуется последовательность нулей и единиц (0> ) с вероятностью появления единицы P(U =1)=

=А, Последовательность (Ок) непосредственно и через элемент 3 задержки с задержкой на один такт подается на входы элемента И 4, реализующего операцию умножения вероятностей. Результат операции S=A + E, фиксируется счетчиком 5 результата по окончании цикла генерации псевдо25

4О

55 с.>учайных чисел N = 2" — 1. Момент окончания цикла устанавливается по появлению в регистре генератора 1 псевдослучайных чисел исходного числа Х,>.

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

Х „ на входах преобразователя кодвероятность 2 таких пар Х„, Х> 1>для которых ошибка произведенйя6 x g " " минимальна.

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

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

Вероятностное устройство для возведения в квадрат, содержащее генератор псевдослучайных чисел, иразрядный преобразователь код-вероятность, .элемент И, первый вход которого соединен с выходом преобразователя код-вероятность, элемент задержки, выход которого соединен с вторым входом элемента И, и счетчик результата, вход которого соединен с выходом элемента И, о т л ич а ю щ е е сятем,,что, с целью упрощения устройства и повышения точности работы, вход элемента задержки соединен с выходом преобразователя код-вероятность, каждый i-ый вход которого (i = 1,2,...n) соединен с j-ым выходом генератора псевдослучайных чисел, причем j и+1 и-2(i -1) (п-m)>n Ä,если i c и

j = " t2 (n i )+13 (n m)n>own> если п+1

° Где и, m (n 7 m) степени xa— рактеристического полинома Х +Х™+1 ге нера тора псе вдослуча йных чисел.

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

1. Яковлев В.В., Федоров P.Ô.

Стохастические вычислительные машины. M., "Машиностроение", 1974, рис. 25 и 37.

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

9 305482, кл. G F 7/36, 1972.

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

N 571810, кл. G 06 F 7/39, 1977 (прототип).

857991

Составитель О.. Майоров

Редактор П. Ортутай Техред 3. Кастелевич Корректор,М. Коста

Заказ 7245/79 Тираж 745 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, Ул. Проектная,4