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

На рис. 38 представлена блок-схема вероятностного преобразо­ вателя, построенного в соответствии с ФАЛ

что достигается путем подачи на входы случайного числа X следу­ ющей комбинации случайных последовательностей

%1-л1»*^■ /-2' а:/_з. ■ *

Р г А

V

X

Рис. 38. Блок-схема ПКВ: РгА — Z-разряд- ный регистр числа А

Несмотря на то что функция (3.6) содержит явно не минималь­ ное количество контактов, практическое использование схемы на рис. 38 может оказаться более предпочтительным, чем схемы синте­ зированной на основе МДНФ. Это вызвано тем, что в первом слу­ чае каждый разряд ПКВ может быть выполнен в виде стандартного субблока, что упрощает изготовление устройства и облегчает его эксплуатацию.

Аналогичным способом может быть осуществлен синтез комби­ национной части ПКВ, использующего иные функции алгебры логики из класса ФАЛ рассматриваемых в этом параграфе.

С целью упрощения вероятностных расчетов логические функ­ ции (3.1, 3.2, 3.3, 3.4, 3.5) часто приводят к иным дизъюнктивным формам. Мы уже показали (стр. 25), что для нахождения матема­ тического ожидания процесса на выходе некоторой логической схемы вместо использования ДСНФ целесообразнее осуществить переход к ОДНФ исследуемой функции алгебры логики. С этой точки зрения особое значение имеют ФАЛ z3 и z4, описываемые выражениями (3.3) и (3.4).

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

ПКВ. Действительно, воспользовавшись алгоритмом приведения к ОДНФ (стр. 26), представим одну из функций, например z3, в виде

z3 — х ^ а у /х ^ (х у /а х) x2a2\Jxxax {х^ У /ху/а^ х-У /

Vai) (z2Va2) х3а 3У ххах (x2a2\Jх у /а х) {х3а3у х у / а у /

Ух.у/а2) (х у /а 4) (х2У а2) (х3У а3) х4а 4У . ..

Применяя к этому выражению операцию поглощения, запишем

Таким же способом можно получить ОДНФ для функции z4

Использование этих двух формул лежит в основе еще одного, так называемого «множественного» подхода к проектированию ПКВ. Прежде чем изложить сущность этого метода, заметим, что все Z-значные наборы, действующие на входах X (рис. 38), можно

отнести к объединению двух произвольных множеств G и G. Преобразователь генерирует на выходе импульс типа G тогда, когда /-разрядная комбинация принадлежит множеству G, в обратном

случае он генерирует импульсы типа G.

Обозначив число элементов множеств символами N (G) и N (G) , можно перейти к вероятностям

Так как в преобразователе на рис. 38 /-разрядные комбинации, действующие на входах X , понимаются как двоичные числа, то множеству G приписывают те числа X , для которых справедливо

8 2

X <( А г, где А ± — заранее установленное число. При этом вероят­ ность на выходе р (G) может изменяться произвольно в пределах от

ющиеся подмножества Glt G2, . . ., Gt таким образом, чтобы для числа элементов, содержащихся в /-м подмножестве, было справед­ ливо равенство N (67) = 21~% где i = 1, 2, . . ., I.

Вероятность того, что набор из X принадлежит подмножеству 67, равна

р { х е з г} = ^ - = 2-г.

Поскольку по условию множества Gt не пересекаются, то для лю­ бого их объединения справедливо

где at — разрядные коэффициенты двоичного разложения числа А , то множество G нужно выбирать так, чтобы

влена произвольно в зависимости от величины преобразуемого числа А с дискретностью 2~1 в диапазоне (0,1—2~1).

Каждое подмножество 67 можно описать некоторой логической функцией так, что функция принимает значение 1 , если для на­ бора X на входах справедливо X £ Gt и значение 0 — в противном

Подмножеству 6г(- соответствует логическая функция

хес,-

83

и множеству G по уравнению (3.11) соответствует функция

Изложенный метод преобразования, в общем, не приводит к каким-либо новым концепциям структурного построения ПКВ. Так, ФАЛ (3.8) структурно реализуется устройством на рис. 38, если на входы случайного числа X подать такую комбинацию случайных последовательностей

X l , [ X l - l , X l - ll> 1*1-2, */-2]. •••> 1 * ь * i l -

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

В работе [95] предложен способ последовательного преобразо­ вания числа А в вероятность с использованием лишь одной слу­ чайной последовательности импульсов, у которой р (0) = р (1) = = 0,5. Блок-схема такого преобразователя приведена на рис. 39.

В схеме осуществляется:

1) разбиение входной последовательности Бернулли в последо­ вательности Z-разрядных комбинаций двоичных символов;

8 4

2) определение принадлежности каждой такой комбинации

кмножествам G или G;

3)выдача импульса на выходе G, если комбинация принадле­

жит множеству G, и импульса на выходе G в обратном случае. Для реализации этой программы схема содержит распредели­ тель импульсов Р И (рис. 39), который переключает выходы реги­ стра А синхронно с поступающей случайной последовательностью и, таким образом, осуществляет разбиение входного процесса на

принадлежности к множеству G. Если во всех следующих разрядах будут только символы 1 , то состояние ПС не изменится, и после прихода /-го импульса на вход х г на выходе ПКВ появится им­ пульс G (например, 0). После этого схема ПС устанавливается спе­ циальным импульсом гашения в исходное состояние.

Если, наоборот, в некотором из последующих разрядов с но­ мером j <С i появится импульс 0 и соответствующий конъюнктор будет закрыт, то ПС переключится в исходное положение, соответ­

8 5

Полученное уравнение реализуется схемой двухвходового триг­ гера [56]. Соответствующая функциональная схема П С приведена на рис. 40, а.

Покажем теперь, что блок-схема на рис. 39 обладает той же степенью универсальности, что и параллельный преобразователь на рис. 38. Продемонстрируем, например, возможность реализа­

Рис. 40. Функциональные схемы блока П С после­ довательных ПКВ: а — работающего на множе­ ственном принципе, б — работающего по принципу

сравнения кодов

Применяя операцию поглощения, получим

zx — ххахУххах {ху/а^ х2а2Ухха х (ххУ ах) х2х2 (х2\/

У а2) х3а3Уххах (xxy a x)x 2d2 (х2\/а2) х3а3 (х3У а 3) х4а4У . . .

Замечая, что

X j d j ( X j - y a j ) = X j d j y x j a j ,

окончательно найдем искомую форму

zx= ххахУ х2а2 (ххахУ ххах)У х3а3 (x ^ y jx хах) (х2а2У

Ух2а2)У . . . У хха{ (ххахУххах) . . . (x ^ a ^ jV ^ -A -i). (3.13)

Отличия формул (3.13) и (3.8) приводят к изменению функцио­ нальной схемы блока ПС, как это показано на рис. 40, б.

Функция z[ + 1 (см. табл. 8) определяется следующим выраже­ нием:

z i + 1 — X xxX 2XZ ^ y X xxX 2f Z f t

Таким образом, затраты оборудования на реализацию обоих функций zx и z3последовательным ПКВ, как и в случае параллель­

86

ного исполнения устройств преобразования, практически одина­ ковы. Однако, параллельные ПКВ работают в I раз быстрее.

Точность преобразования. Выходная вероятность всех рассмот­

ренных схем ПКВ изменяется по линейному закону в функции А если:

Р = у (1 + е), ? = у (1 — е).

Для любого элементарного произведения х^х^к . . x fl вероят­ ность обращения в единицу равна (см. стр. 83)

р а , равной еа = р а — 2~г,для чего воспользуемся биномиальным

Отбрасывая в разложениях члены со степенью выше третьей, получим

87