Преобразователь код-вероятность Советский патент 1974 года по МПК G06F1/02 

1

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

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

Известные преобразователи недостаточно точны.

Целью изобретения является повышение точности работы преобразователя.

Для достижения этой цели преобразователь содержит /п-разрядный двоичный счетчик, вход которого соединен со входом генератора псевдослучайных чисел, и т сумматоров по модулю «2, выходы которых подключены ко вторым входам блока сравнения соответственно, первые входы - к разрядным выходам двоичного счетчика, а вторые входы - к первым т разрядам генератора псевдослучайных сигналов.

Схема предлагаемого преобразователя представлена на фиг. 1, где обозначены:

1 - регистр -преобразуемого числа; 2 - /-разрядный блок сравнения; 3 - сумматоры

по модулю 4 - т-разрядный двоичный счетчик; 5 - генератор псевдослучайных чисел на регистре сдвига; 6 - шина тактовых импульсов; 7 - выход блока сравнения.

Малыми латинскими буквами на фиг. 1 указан порядок нумерации разрядов и шин.

На фиг. 2 приведены диаграммы, поясняющие работу преобразователя.

Выходы разрядов регистра 1 соединены с / входами блока сравнения 2. Другие т входов блока сравнения через сумматоры 3 по модулю «2 подключены к выходам т-разрядного двоичного счетчика 4 и генератора 5 псевдослучайных чисел, остальные (/-т) входов блока сравнения непосредственно соединены с выходами младших разрядов генератора 5. Порядок соединения каждого из т сумматоров 3 с элементами схемы 2, 4 и 5 одинаков, причем первый вход /-го сумматора (, 2, ..,ш.) соединен с соответствующим разрядом двоичного счетчика 4, второй его вход - с выходом /-ГО разряда генератора 5 псевдослучайных чисел, а выход - с соответствующим разрядом блока сравнения 2. Работа генератора 5 псевдослучайных чисел и двоичного счетчика 4 синхронизируется последовательностью тактовых импульсов, поступающих по шине 6. При этом для двоичного счетчика 4 импульсы этой последовательности одновременно являются импульсами счета.

Работа преобразователя код-вероятность заключается в следующем.

На каждом такте в зависимости от соотношения между преобразуемым числом А, хранящимся в регистре 1, и псевдослучайным числом X, поступающим на входы блока сравнения 2, на выходе 7 формируется символ «О или «1, «О - если и «1 - если X,А. Значение X на входе схемы сравнения, в свою очередь, определяется значением псевдослучайного числа X на выходе генератора 5 и содержимым двоичного счетчика 4. При этом, если в /-М разряде счетчика ноль, то на соответствующий вход схемы сравнения подается прямое значение переменной с выхода /-ГО разряда генератора псевдослучайных чисел -Xj, и инверсное значение этой переменной Xj при единичном состоянии /-го разряда счетчика.

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

Пусть между разрядами псевдослучайных чисел X к У существует линейная зависимость вида

®х., у ()

(или л:10л:2@г/1 0). Поскольку при наличии такой зависимости появление на выходах генератора 5 псевдослучайных чисел комбинаций Xi-Xz-yi-yz и Х1-Х2-у1-у2-Уг, исключается, то ошибка произведения, очевидно, будет равна

8-- -У-Г-У-- -

- V 2 у V 2 у32

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

Xi@JCz У, тождественным i @ ЛГа r/i 1.

Теперь указанные комбинации будут появляться с вероятностью, соответственно равной

/ - 1 и () следовательно, ошибка произведения будет положительной и равной ,± + ± ±

16 32 32

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

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

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

Покажем, что в результате инвертирования двух переменных Xi и Х2, осуществляемого с помощью двухразрядного счетчика и двух сумматоров по модулю «2, достигается полная 0 компенсация ошибки произведения.

Учитывая, что погрешность результата будет равна теперь среднему арифметическому погрешностей е на каждом из четырех участков временной диаграммы (фиг. 2), соответствующих возможным состояниям разрядов счетчика t/ь г/г, а также, что знак погрешностей si, 82, 83 изменяется на противоположный только при инвертировании нечетного числа переменных, входящих в линейные соотношения, получим 1

Y (Е. + 2. + . + s)

(si + s, + s,) + (e,-e, -e,) +

+ (- 1 + Ss - е,) + (- S, - е,+ в,) Е О,

ошибка действительно

Т. е. результируюшая равна нулю.

Необходимое количество инвертируемых переменных или разрядность счетчика т зависит от характера линейных соотношений, связывающих разряды псевдослучайных чисел X, рода операций, выполняемых над последовательностями случайных символов, их точности и может изменяться в пределах отот 3-4 до I (/ 10-12). В большинстве практических случаев заданная точность выполнения операций (+) достигается при инвертировании т-- переменных Xj в старших разрядах генератора псевдослучайных чисел (,2,.., т).

Предмет изобретения

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