Преобразователь код-вероятность

 

О П И С А Н И Е (!) 45iQ l53

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Сею Советских

Социалистических

Ресиублик (61) Зависимое от авт, свидетельства (22) Заявлено 14.09.73 (21) 1958960/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15.11.74. Бюллетень № 42

Дата опубликования описания 27.05.75 (5! ) М. Кл, G 06f 1/02

Государственный комитет

Свветв Министров СССР (53) УДК 681.3(088 8) йо Аелим изобретений и открытий (72) Авторы изобретения

ФМ3 З тИРД3

Г. В. Добр ис и В. В, Яковлев (71) Заявитель Ленинградский ордена Ленина институт инженеров железнодорожного транспорта им. В, Н. Образцова (54) ПРЕОБРАЗОВАТЕЛЬ КОД вЂ” ВЕРОЯТНОСТЬ

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

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

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

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

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

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

1 — регистр преобразуемого числа; 2

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

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

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

Выходы разрядов регистра 1 соединены с 1

1О входами блока сравнения 2. Другие ш входов блока сравнения через сумматоры 3 по модулю «2» подключены к выходам т-разрядного двоичного счетчика 4 и генератора 5 псевдослучайных чисел, остальные (1 — т) входов

15 блока сравнения непосредственно соединены с выходами младших разрядов генератора 5.

Порядок соединения каждого из т сумматоров 3 с элементами схемы 2, 4 и 5 одинаков, причем первый вход j-го сумматора (j= 1, 2, 20, m) соединен с соответствующим разрядом двоичного счетчика 4, второй его вход — с выходом j-го разряда генератора 5 псевдослучайных чисел, а выход — с соответствующим разрядом блока сравнения 2. Работа генера25 тора 5 псевдослучайных чисел и двоичного счетчика 4 синхронизируется последовательностью тактовых импульсов, поступающих по шине 6. При этом для двоичного счетчика 4 импульсы этой последовательности одновре30 менно являются импульсами счета.

450153

З0

45

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

На каждом такте в зависимости от соотношения между преобразуемым числом А, хранящимся в регистре 1, и псевдослучайным числом Х, поступающим на входы блока сравнения 2, на выходе 7 формируется символ «О» или «1», «О» — если Х )A и «1» — если

Х (А. Значение Х на входе схемы сравнения, в свою очередь, определяется значением псевдослучайного числа Х на выходе генератора 5 и содержимым двоичного счетчика 4. При этом, если в j-м разряде счетчика ноль, то на соответствующий вход схемы сравнения подается прямое значение переменной с выхода

1 -го разряда генератора псевдослучайных чисел — Х;, и инверсное значение этой переменной Х; при единичном состоянии j-го разряда счетчика.

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

Пусть между разрядами псевдослучайных чисел Х и Y существует линейная зависимость вида х -P x g (*) (или х, ® х, Q+ g, =0). Поскольку при наличии такой зависимости появление на выходах генератора 5 псевдослучайных чисел комбинаций х хр g> у и х> х yi ур уз исключается, то ошибка произведения, очевидно, будет равна

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

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

1 1 3

6: — + —:—

16 32 32

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

15

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

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

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

1 а: — (а, +а, + sg, +sq) =

= — l(<+-. + =.)+(—" — ) +

+ (—, + . — .) + (—, —,,+,)) = О, т. е. результирующая ошибка действительно равна нулю.

Необходимое количество инвертируемых переменных или разрядность счетчика m зависит от характера линейных соотношений, связывающих разряды псевдослучайных чисел Х, рода операций, выполняемых над последовательностями случайных символов, их точности и может изменяться впределах отт=З вЂ” 4 до 1 (1=10 — 12). В большинстве практических случаев заданная точность выполнения операций 6(Bgpp=2 + 1 достигается при инверти1 ровании т= — переменных х; в старших раз2 рядах генератора псевдослучайных чисел (j=1, 2,, m).

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

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

450153

Фиг 1

Фиг с

Составитель А. Карасов

Техред Н. Куклина

Корректор Е, Мохова

Редактор Б. Нанкина

Типография, пр. Сапунова, 2

Заказ 1202/2 Изд. № 1132 Тираж 624 Подписное

UHHHIIH Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5