1. ВВЕДЕНИЕ Преобразователем вероятности (далее ПВ) [1] называется устройство, которое преобразует входную двоичную случайную последовательность независимых величин ,,0" и „1" с вероятностями появления импульсов Р(0) = Р(1) = 1/2 в случайную последовательность того-же типа, вероятности появления импульсов А, В в которой равны Р(А) = р, Р(В) — 1 — р, где р — устанавливаемое значение вероятности. Это — добавочное устройство к генератору случайного процесса [2]. Возможности использования ПВ были в достаточной степени освещены в литературе [1,2], и здесь поэтому этими вопросами заниматься не будем. В этой статье рассмотрены некоторые схемы ПВ, работа которых основана на „множественном" принципе: входную последовательность разбивают на равные отрезки по п импульсам в каждом, образуя последовательность п-значных комбинаций. Вводят два непересекающиеся множества А и В, объединение которых содержит все возможные двоичные и-значные комбинации. ПВ генерирует на своем выходе импульс типа А тогда, когда п-значная комбинация входной последовательности принадлежит множеству А, в обратном случае он генерирует импульс типа В. Если для вероятностей появления импульсов „0" и ,Д" входной последовательности справедливы равенства Р(0) = Р(1) = 1/2,
и импульсы независимы, то вероятности появления всех л-местных комбинаций одинаковы, и равны 1/2". Очевидно, что вероятности появления импульсов А и В на выходе ПВ в этом случае зависят только от числа элементов соответствующих множеств. Обозначим число элементов множества А символом N(А). Тогда искомые вероятности определяются по формулам: (1) !^) = « , ВД-1--М. В реальном ПВ вероятности Р(А) и Р(В) отличаются от вероятностей, рассчитанных по этой формуле, потому что вероятности входных нулей и единиц могут быть зависимы или отличаться от 1/2. Частота следования импульсов выходной последовательности равна 1/я частоты следования импульсов последовательности входной. Конструкция ПВ должна обеспечивать возможность выбора вероятностей Р(А) и Р(В). Это означает, что множество А, а, следовательно, и В должны быть такими, чтобы обеспечивали возможность выбора числа их элементов. В ПВ описанном в [1] л-значные комбинации элементов ,,0" и „1 " на входе рассматриваются как числа, записанные в двоичной системе счисления. Множеству А потом принадлежат те числа N для которых справедливо неравенство N ^ V, где V — некоторое, заранее устанавливаемое число. Выходная вероятность Р(А) может быть выбрана произвольно в пределах от 1/2" до 1 по ступеням 1/2". 2. ОПРЕДЕЛЕНИЕ МНОЖЕСТВА А И РАСЧЕТ ВЕРОЯТНОСТИ Р(А) В этой работе использован другой способ. Из множества всех возможных л-значных комбинаций выбраны попарно непересекающиеся подмножества А1 , А2 , ...,А, таким образом, чтобы для числа элементов, содержащихся в «-том подмножестве, было справедливо равенство Л^А;) = 2"~', где г = = 1, 2, ..., п. Вероятность того, что л-значная комбинация X принадлежит подмножеству А; будет равна: (2) Р {ХбА; } = ^ = 2- ; . Подмножества непересекаются, поэтому для любого их объединения справедливо: (3) Р{ХеиА! }=12-', где / — произвольное подмножество индексов (1, 2, ..., л}. Формула (3) показывает способ выбора множества А для реализации заданной вероятности Р(А). Если (4) Р(А) = ^Ъ{1~1 ,
где Ь1 — коэфициенты равные нулю или единице, то множество А необходимо выбрать так, чтобы (5) А = I) А,, 16/о где 10 — множество тех индексов, для которых выполняется равенство Ь, = 1. Вероятность Р(А) на выходе ПВ может быть, следовательно, выбрана произвольно в пределах от 0 до 1 — 1/2" по ступеням 1/2". Каждое подмножество А; можно описать некоторой логической функцией так, что функция принимает значение 1 во всех тех случаях, когда для гс-значной комбинации X на входе справедливо X е А; , и значение 0 тогда, когда X $ А( . Поставим каждой и-значной комбинации X = ах а2 ... ап в соответствие элементарную конъюнкцию х°'х22 ... х"„", где, как обычно: <ч _ Г *• П Р И а . = 1 , I х1 при а1 = 1 . Подмножеству А,- будет соответствовать логическая функция: (6) /(А>)= у х?*?...** , ХеЛ, и множеству А по уравнению (5) функция: (7) ДА) = УДА,)- Подмножества А, необходимо выбрать так, чтобы функции ДА,-) были, по возможности, простыми. К задаче можно подойти с другой стороны: выбрать простые функции ДА( ) такие, что (а) функция ДА,) содержит 2"~' элементарных конъюнкций при ; = 1, 2, ..., п, (б) произведение ДА,). ДАу) = 0 для . ф } и все /, ] = 1,2,..., п. Выбираем: (8) ДА,.) = х л_; + Л _,. + 2 ...х и . Условие (а), очевидно, выполняется. Кроме того, для I > ] справедливо: К А дКА } ) = xп -^ + 1xп_^ + 2...xп_^+1 ...ХпХа -л.1Х„-./+2...Х„ = О, потому что х„-]+1 хп_]+1 = 0. Выполняется, следовательно, и условие (б). Вероятности в формуле (2) были получены в предположении, что вероятности появлений ,,0" и „1" во входной последовательности равны в точности 1/2. На самом деле реальный генератор случайной последовательности генерирует