Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 101
Скачиваний: 0
Выберем конкретный материал куба, например, германий. Элементарный кубик кристаллической решетки германия имеет длину одной грани 5,6 •10 8см и содержит 8 атомов. Следовательно, р ^ 2 , 8 - 10“8 см, и при температуре Т° = 10 К из формулы (2.59) находим п ^ 25 атомов. Так как тепловая энергия кТ° является только средней величиной и могут существовать фононы с большей энергией, выберем п 102. Это, в свою очередь, дает время Дг = = 10~16 с. Учитывая, что кубический сантиметр германия содер жит 4,52 -1022 атомов, найдем количество vVB бит информации, которые можно различить в объеме 20 литров (куб с гранями размером 27 см) N B ^ 1021.
На практике, естественно, невозможно достичь такой плот ности упаковки хотя бы по причине необходимых затрат простран ства на межсоединения.
В заключение скажем, что все рассмотренные перспективные по быстродействию логические схемы являются детерминирован ными по своей природе. Мы требуем от них лишь надежного фикси рования двух состояний 0 и 1. В перспективе можно ожидать по явления действительно стохастических элементов, основанных, например, на высокоскоростных взаимодействиях потоков эле ментарных частиц, фотонов и фононов, у которых случайное поведение является естественным правилом.
Г л а в а III
СТОХАСТИЧЕСКИЕ ФУНКЦИОНАЛЬНЫЕ ПРЕОБРАЗОВАТЕЛИ
Всоответствии со структурой на рис. 33 в СтВМ осуществля ются преобразования трех видов.
1. Код — вероятность на ПКВ, используемое для ввода пере менных в машину. Естественным у этих преобразователей является стремление обеспечить высокую линейность передаточной харак теристики.
Вобщем случае можно себе представить также и нелинейную (функциональную) зависимость между выходным и входным пара метрами ПКВ. Такие преобразователи будем называть функцио нальными (ФПКВ). Причем, поскольку информация на входе ФПКВ представлена в регулярной форме, а выходная информа ция — в виде параметров стохастического процесса, то ФПКВ можно условно разделить на две части: детерминированную и ве роятностную. Такое разделение, безусловно, имеет смысл только
синформационной точки зрения, так как устройства обеих частей
содержат совершенно одинаковые электронные элементы.
Таким образом, появляется возможность осуществления соб ственно функционального преобразования либо в детерминиро ванной, либо в вероятностной части ФПКВ.
2. Вероятность — вероятность на логическом преобразователе ЛП. Отличительной особенностью преобразователей ПВВ является представление информации на входе и выходе устройства в одной и той же форме последовательности Бернулли. Поэтому синтез ПВВ осуществляется в основном на основе методов и идей тео рии вероятностных автоматов.
По аналогии с преобразователями ПКВ будем различать ЛПВВ (линейные преобразователи вероятность — вероятность) и ФПВВ (функциональные преобразователи вероятность — вероятность).
3. Вероятность — код, используемое при выводе информации из СтВМ. Преобразователи вероятность — код (ПВК), основу которых составляют интеграторы, могут также успешно приме няться в качестве операционных блоков при решении дифферен циальных, алгебраических и трансцендентных уравнений.
Вэтой главе будут подробно обсуждаться вопросы, связанные
сорганизацией и проектированием первых двух типов преобразо
вателей.
7Г
12. Преобразование входных переменных
Вп. 3 был рассмотрен основной и наиболее очевидный метод
получения случайной последовательности двоичных символов с вероятностью появления единиц пропорциональной преобразу емому числу А , заключающийся в сравнении истинного числа с последовательностью случайных равномерно распределенных двоичных чисел.
Блок-схема такого вероятностного преобразователя приведена на рис. 37.
Случайное двоичное число X {х1: х 2, . . ., x t}, вырабатываемое генератором случайных чисел (ГСЧ), в каждом такте сравнивается
|
с кодом детерминированного числа |
||||||
|
А |
{ |
а г, а 2, |
. . ., |
аД, |
хранимым |
|
|
в |
регистре |
РгА. |
|
А , на вы |
||
|
|
В случае, если X |
|||||
|
ходе схемы |
сравнения появляется |
|||||
|
символ 1 , в противном случае — 0. |
||||||
|
Так как каждая |
двоичная комби |
|||||
|
нация на входе X схемы сравне |
||||||
|
ния равновероятна, а полное их |
||||||
Рис. 37. Вероятностный преоб |
число равно 21, то единицы на вы |
||||||
разователь: СС — схема сравне |
ходе |
схемы |
будут |
появляться |
|||
ния |
в среднем А |
раз из 21, т. е. вероят |
|||||
|
ность их появления р (z) = А2 1. |
||||||
При абсолютной случайности |
появления |
чисел в |
ГСЧ исход |
||||
сравнения в каждом такте не зависит от исходов в предыдущих, т. е. преобразователем действительно реализуется схема испыта ний Бернулли.
Другой интерпретацией метода преобразования код — вероят ность является синтез вероятностного преобразователя на основе р -схем [57]. р -схема представляет собой стохастический элемент, на выходе которого сигнал, сопоставляемый значению 1 , в каждый момент времени появляется с вероятностью р. Соединяя выходы набора р-схем с входами комбинационной логической схемы, можно синтезировать я-схему, где О ^ я ^ 1 . В [57] доказывается, что если я записывается в виде несокращаемой дроби А2~1 (А — целое число), то соответствующая я-схема может быть построена из I р -схем (р = 0,5).
Можно показать, что вероятностный преобразователь с вероят ностью появления 1 на выходе пропорциональной ^-разрядному
двоичному числу А {«!, а2, . . ., |
аД может быть |
построен из |
I 0,5-схем и логической комбинационной схемы (рис. 37), реализу |
||
ющей функцию z2 |
|
|
z2= ххахУ х2а2 (x^Jа^ У х3а3 {x^Ja^) {x2\Ja2)\ J.. . |
||
. . .\Jxlal Orj_V«i) |
••• (z/-i\/a/-i)- |
(3-1) |
7 8
Пример. Пусть А = О, а ха 2а 3а 4аь = 0,01011 = 11/32. Тогда
z2= x.2xL\Jxix1xs\]х-ах4хг = х1 [х2\/х3 (х4\/х5)].
Переходя к вероятностям и учитывая, что для статистически независимых переменных x-t и x-s справедливо
|
P{XiX>)=p(x>)p{x>), |
|
|
Р (XiVXj) = 1 — [1 —р (Xi)] [1 —p(Xj)], |
|
получим р |
(х4 V хъ) = 3/4, Р (х3х 4 V Х 3ХЪ) |
= 3/8, Р (х2 V Х 3Х 4 V |
V х 3х5) = |
п / 1в и окончательно |
|
|
P(z2) = t X t7T = 1 1 |
’ |
|
32 |
|
Табл. 7 иллюстрирует два рассмотренных способа преобразования
код — вероятность |
при |
А = |
0,101. |
|
|
||
|
|
|
|
|
|
Т а б л и ц а 7 |
|
|
Таблица истинности для логических схем линейных ПКВ |
||||||
X i |
X 2 |
Хз |
Z\ |
z2 = Х, V Х 2Х) z 3 — x t |
V x 2x 2 z 4 = r.xi V x 2x 3 |
||
Х < А |
|||||||
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
|||||||
0 |
0 |
1 |
0 |
1 |
1 |
||
1 |
|||||||
0 |
1 |
0 |
0 |
1 |
0 |
||
1 |
|||||||
0 |
1 |
1 |
1 |
1 |
0 |
||
1 |
|||||||
1 |
0 |
0 |
1 |
0 |
1 |
||
|
|||||||
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
|
Нетрудно видеть, что логическая функция г г, которую реализует схема сравнения на рис. 37, может быть записана в виде
Н = х4а4\/х2а2 (x-y\/aj\/xsaz {х4у а 4) {x2\Ja2)\J.. .
■■-Vx^t |
(3.2) |
Очевидно, что функция z2эквивалентна zlt если на входы схемы СС
подать х 4, х г, х 3.
Таким образом, можно сделать вывод, что по существу оба этих метода преобразования идентичны, а схемы, реализующие их, относятся к классу преобразователей распределений — равномер ного распределения Z-мерных двоичных векторов в распределение случайной величины, принимающей значения 1 и 0 с вероятно стями р (z) и 1 — р (z).
79
Обобщая полученные результаты, заметим то важное обстоя тельство, что для построения ПКВ в принципе можно использо вать целое семейство ФАЛ вида (3.2), отличающихся различным порядком расстановки инверсий у каждой из переменных Xj. Например, кроме уже известных функций zt и z2 для реализации преобразователей код — вероятность могли бы подойти функции:
z3= х1а 1\ух2а 2 (хх\/ax)\Jх3а3 {ххУ ах) (ж2V «2) V |
••• |
|
. . . \Jxfli {ххУ ах) . . . |
(3.3) |
|
zl = x1al\Jx2a2 (^ V a ^ V ^ s^ iV a i) Or2Va2)V •. . |
||
••• |
(*iV«i) ••• f a - i W i ) , |
(3.4) |
z5= xxa-^\Jx2a2(«iV^i)V^3a3СнХ/аО (ж2V«2)V •••,
z6= xxaxy x 2a2(a^Vax)\Jx3a3 {х^Уах) (£2V«2)V
\Jxiai (x,\/ai) (x2\fa2) (x3\/a.t)\/ . . . |
(3.5) |
и T. Д.
Однако, не все эти функции допускают линейное преобразова ние подобно zx или z2. Для построения ПКВ с линейной передаточ ной характеристикой могут быть использованы лишь те ФАЛ, в которых исключается возможность одновременного присутствия
двучленов Xj V а,- и х,- У «/ при всех / £ (1, Z). Например, функ ции алгебры логики (3.3), (3.4) и (3.5) удовлетворяют этому усло вию в отличие от функции z5, содержащей одновременно xx \J а х
И I i V а х.
При переходе к вероятностям все функции вида (3.1, 3.2, 3.3, 3.4, 3.5) дают одинаковый результат на выходе (при одном и том же значении А, если выполняется условие р (хД = р (х2) — . . . — = Р (хд = 0,5 и, кроме того, если все эти случайные последова тельности независимы попарно и в совокупности. При выборе конкретной ФАЛ для построения линейного ПКВ необходимо руководствоваться критериями минимума затрат оборудования на реализацию, точности и быстродействия устройства.
Заметим, что формула (3.5) может быть представлена в форме рекуррентного соотношения
z6 = xxa1\/{x1\Jal) \x2a2\J{x2\/a2) [х3а3У {х3у а3) х4я4\/ .•■]},
что позволяет свести процедуру синтеза устройства к последова тельному раскрыванию скобок и, таким образом, обеспечивает эффективное использование логических элементов.
Отметим, что ранее рассмотренные функции z4 и z2 относятся к такому же классу ФАЛ.
80