Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf

На рис. 26 кривая т = 1 представляет зависимость nD (zt) —

— р 2 (1 — р 2) в функции р — математического ожидания входной переменной квадратора, а кривая т = 2 — зависимость диспер­ сии, вычисленной по формуле (2.38). Первая функция достигает

максимума D x = 0,25 при р = 1/0,5; значение максимума второй «функции D 2 = 0,46 и определено при р = 0,728. Отношение

Рис. 26. Зависимость дисперсии частоты появле­ ния единиц в выходной последовательности дли­ ной п от р при возведении переменной в т-ю степень

дисперсий D JD X= 1,84. Следовательно, относительное увеличе­ ние длины случайной двоичной последовательности Бернулли равно 1,84, то есть п' = 1,84ге, что, очевидно, приведет к необхо­ димости повышения разрядности выходного накопителя СтВМ.

На рис. 27 представлена схема с двумя стохастическими умно­ жителями, позволяющая вычислить третью степень от входной переменной. Вероятность появления импульса на выходе схемы равна р 3, а дисперсия p s (1 — р 3). Вероятность совместного на­ ступления Событий Zi = 1 и zUx = 1

Р — Р fa ) Р (х{ |xt) р fa .j) Р (ж£_г |х{_х) р (xt_2) р (х,+1) = р4,

•54

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

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

5 а

Отношение n'Jn получим из таблицы, умножив соответствующее Dm на величину D j1 = 4, т. е.

В качестве элементов задержки входящей последовательности можно использовать триггеры и тогда практическая схема для воз­ ведения переменной в т-ю степень будет состоять из т — 1-разряд­ ного регистра сдвига и такого же количества двухвходовых конъюнкторов, включенных цепочкой, как показано на рис. 28. Число вентилей И, используемых в схеме, в общем является избыточ­ ным и, следовательно, может быть сокращено. Хорошей иллюстра­ цией этому служит схема на рис. 27.

Рг

Рис. 28. Схема с одним регистром сдвига Рг для возведения переменной в произвольную степень т

Выпишем значения выходной функции схемы в последовательдше моменты времени с условием т х = т 2 = 1:

zi = XiXi.jXi.yXi.^

Z;+l x i+ ix ix ix i-y,

zn— XnXn^yXn_yXn_2-

Исключая тавтологии и переходя к вероятностям, при условии идеальности входящей последовательности получим

Р (zd = Р (xt) р (хи1) р (х£_?)

возведения переменной в третью степень и в том случае, если вто­ рой элемент задержки подключается к выходу первого конъюнкчора (эта связь показана на рисунке штрихами).

Если тА= 1, а т2 = 2, то

Z; = х (Xi ^\Х£.о'Г/-к-

Z;+1 — Xi+yX£Xi „уХ/_2,

Zn ---х пх п-\х п-2х п-Ь

и

Таким образом, схема на рис. 27 содержит на один вентиль меньше,, чем схема на рис. 28, когда они обе работают в режиме возведения переменной в четвертую степень.

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

Запишем выражения этих интересующих нас операций:

фактически определяют алгоритмы вычисления функций системы (2.41). Следовательно, первое уравнение системы (2.42) может быть реализовано на некотором количестве N 0 г-входовых венти­

дами не имеют памяти, первая задача (умножение т различных переменных) решается за один шаг вычислений.

При этом количество r-входовых элементов И, требуемое для

где символ [а] обозначает число а взятое по избытку до ближай­ шего целого.

Доказательство можно провести индукцией по г. При г = 2 каждый элемент выполняет одну операцию умножения. Поэтому общее число элементов определяется числом операций, необходи­ мых для умножения т переменных, т. е. N 0 = т — 1. При г = 3 каждый элемент выполняет две операции умножения, т. е. потре­ буется вдвое меньшее число элементов, и т. д. Ясно, что при г > 2 для некоторых т не все N 0r входов логической схемы окажутся занятыми. Для определения количества избыточных входов L 0 .

5 7 ;

откуда вытекает, что при перемножении нечетного числа перемен­ ных на трехвходовых элементах используются все входы; если т — четное, то не используется один вход.

Следовательно, при перемножении т переменных на четырех­ входовых элементах все входы будут использованы, если сумма цифр, изображающих т, минус единица кратна трем. Например,

иных г.

На рис. 29 показаны зависимости N 0 от т при использовании двухвходовых и трехвходовых стохастических умножителей в ре­ жиме перемножения т переменных.

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

5 8

Представим т в системе счисления с основанием г

m = bs+1rs + bsrs~1-{- . . . + & ! •

Тогда минимальное число r-входовых стохастических умно­ жителей, с помощью которых можно вычислить р т{х), равно

Действительно, из разложения т по степеням г вытекает, что-

применяя формулу (2.43), получим

что и дает искомый результат (2.44).

На рис. 29 представлены зависимости iV0 от т, вычисленные* по формуле (2.44) для случаев использования двухвходовых и трехвходовых умножителей. Отметим, что для некоторых т (4, 8, 16 и т. д.) затраты оборудования одинаковы.

Определим разницу в оборудовании при вычислениях по фор­ мулам (2.43) и (2.44)

s+1

т —^ bi— s (r—1)

Разложив т по степеням г, получим

5 3