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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Соцналнстнческнз

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 17. 02. 81 (2! ) 3250588/18-24

Рq М.g<

G 06 F 7/70 с присоединением заявки ¹Государственный комитет

СССР по делам изобретений н открытий (23) Приоритет

Опубликовано 300982. Бюллетень №36

Дата опубликования описания 30.09.82

1ЗЗ) УДК 681. 3 (088. 8) (72) Автор изобретения

В. В. Яковлев

Ленинградский ордена Ленина институт инженеров железнодорожного транспорта им. акад. В. H. Образцова (71) Заявитель (54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО

ДЛЯ ИЗВЛЕЧЕНИЯ КОРНЯ

Изобретение относится к вычисли.тель ной технике и предназначается для выполнения операции извлечения корня п-й степени из числа A (B

r ЯГА, Аб 0-1, n — целое положительное число) в стохастических вычислительных машинах.

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

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

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

Главным недостатком этого устройства также является низкое быстродействие при выполнении операции извлечения корня.

Цель изобретения — повышение быстродействия.

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

9б2937 соединены соответственно с разрядными выходами первого счетчика и второй группой разрядных ныходов второго счетчика, первый и второй генераторы случайных чисел, группы выходов которых соединены с вторыми группами 5 нходов соответственно первого и второго блоков сравнения, генератор тактовых импульсов, триггер, элемент И, первый и нторэй входы которого соединены соответственно с нулевым выходом триггера и выходом . генератора тактовых импульсов, а выход— с входами первого генератора случайных чисел и первого блока сравнения, дополнительно содержит делитель частоты следования импульсов, вход которого подключен к выходу элемента И и соединен с суммирующим входом второго счетчика, а выход — с входами второго генератора случайных чисел и второго блока сраннения, выход второго блока сравнения соединен с вычитающим нходом второго счетчика, выход первого блока сравнения соединен с суммирующим входом первого счетчика, выход старшего разряда . которого соединен с единичным входом триггера, нулевой вход триггера является пусковым входом устройства.

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

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

Первые группы входов первого 2 и второго 9 блоков сравнения соедине- 40 ны соответственно с разрядными выходами первого счетчика 1 и второй группой разрядных выходов второго счетчика 8, вторые группы входов с группами выходов соответственно 45 первого 3 и нторого 10 генераторов случайных чисел, а выходы соединены соответственно с суммирующим входом первого счетчика 1 и вычитающим входом .второго счетчика 8.

Выход старшего разряда первого счетчика 1 соединен с единичным входом триггера 4, нулевой выход которого соединен с первым входом элеме нта И б.

Второй вход элемента И б соединен с выходом генератора 5 тактовых импульсов, а выход - с входами первого блока 2 сравнения, первого генератора 3 случайных чисел, делителя 7 частоты следования импульсов и сум- 60 мирующим входом второго счетчика 8.

Выход делителя 7 частоты следования импульсов соединен с входами второго блока 9 сравнения и второго генератора 10 случайных чисел.

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

Таким образом, импульсы синхронизации с частотой F поступают на входы управления первого генератора 3 случайных чисел и первого блока 2 сравнения, а с частотой F/n (после деления частоты делителем 7 частоты слвдования импульсов) — на входы второго блока 9 сравнения и второго генератора

10 случайных чисел. Следовательно, работа обоих счетчиков протекает параллельно во времени.

Сигнал "1" на выходе блока 2 сравнения формируется, если содержимое счетчика 1 не меньше значения кода на выходе генератора 3 случайных чисел на такте управления (управление с частотой F). В процессе работы содержимое счетчика 1 нарастает, и н некоторый момент времени счетчик 1 переполняется. Импульсом переполнения по единичному входу выключается триггер 4, формируя на своем выходе временной импульс, длительность которого равна где 6 — разрядность счетчика 1 (оба счетчика, блоки сравнения и генераторы случайных чисел имеют одинаковую разрядность).

За это же время Г на выходе второго счетчика 8 формируется результат выполнения операции / А, ПроисИ ходит это следующим образом.

Система, состоящая из второго счетчика 8, блока 9 сравнения и генератора 10 случайных чисел, представляет собой следящий стохастический интегратор. 3а время математическое ожидание содержимого счетчика 8 сост авляе т

- гМ С

Подставляя в это выражение соотношение для ; из (1), получим

- /иСи /А

М.; -й =1 и/У, (2)

Таким образом, искомый результат получается на выходе счетчика 8 в об1эатном коде. Другими словами, число À образовано двоичным кодом на иннерсных выходах счетчика 8.

Время вычислений результата в предлагаемом устройстве определяется соотношением (1). В известном устройстве оно составляет

t - 2.3 .ГАт (3) 962937

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

ВНИИПИ Заказ 7514/69 Тираж 731 Подписное

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная,4

Коэффициент 2,3 определяет 90%-ный уровень достижения результата операции °

Отношение определяет выигрыа в быстродействии предлагаемого устройства по сравнению с прототипом. Например, при n = 2, 10

А = 0,1 — = 100. При этом достигаемое увеличение быстродействия тем выше, чем больше и.

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

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

1. Кирьянов Б. Ф., Песошин В. А.

Стохастические вычислительные машины и устройства. Уч. пособие. Казанский авиационный институт, 1978, рис. 19.

2. Massen R., Kohl А., C>enauig keit und Bandbreite in йег stochastischen Rechentechnik. — "Flectronik", Munchen, Р 8, 1975, В. 7.

3. Яковлев В. В., Федоров Р. Ф.

Стохастические вычислительные машины. Л., "Машиностроение", 1974,,с. 159, рис. 73 (прототип).