Генератор псевдослучайных чисел Советский патент 1978 года по МПК G07C15/00 G06F1/02 

Изобретение относигея к области вычисл тельной техники, в частности к генераторам диркретных функций, поэволяюшим получать последовательности псевдослучайных чисел с равномерным законом распределения, и может оыть использовано в качестве генератора чайного сигнала в устройствах статистическог кодирования тина код-вероятность и.аналснг-вероятность. Известен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи. Этот генератор позволяет получать последовательность случайных чисел с периодом следования не более 1 l. Известен также генератор псевдослучайных чисел, который для увеличения длины периода имеет два одновременно тактируемых регистра сдвига с сумматорами по модулю два в цепях Обратной связи и Группу логических схем типа сумматоров по модулю два, на выходах которых формируются псевдослучайные числа. Наличие второго регистра сдвига с обратной связью и группы логических схем позволяет удлинить период следования генерируемой последовательности - разрядных чисел, который равен () (), где разрядности используемых регистров сдвига. Зднако этот генератор при значительно большем периоде следования псевдослучайных чисел не обладает оптимальным значением автокорреляционной функции, необходимой для повышения эффективности статистического кодирования 2.. Наиболее близким техническим решением к данному изобретению является генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи, вход которого подключен к выходу генератора тактовых импульсов Гз. Этот генератор позволяет генерировать последовательности неповторяющихся в цикле псевдослучайных чисел с периодом следования и соответственно с максимально возможной длиной выборки NQ 2 2Рчто явлжпется недостаточным для проведения статистического кодирования и стахостическсйго вычисления С повышенной точностью.

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

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

Кроме того, мультиплексор содержит

блок элементов ИЛИ,блок элементов И и элемент ИЛИ, выход которого является вЫходом мультиплексора, а входы подключены к выходам блока элементов И; первые вхощл которых непосредственнее, а вторые вхо. ды через блок элементов ,ИЛИ подключены ко входам мультиплексора.

На фиг. 1 показана блок-схема генерЕЬ тора; : на фиг. 2 - блока-схем а мультиплексора.

Генератор содержит генератор тактовых импульсов 1, выход которого подключен ко входу регистра 2 сдвига с сумматором по модулю два в цепи обратной связи и через делитель частоты 3 - ко входу распределигеля потенциалов 4. Выходы регистра 2 и распределителя импульсов 4 соединены; со входами мультиплексоров 5, каждый из которых содержит п групп коммутирующих входов по (U -l)i индентичных входов

в каждой группе. Схема соединений выходов распределителя 4 с группами входов каждого мультиплексора 5 образует матрицу размером п ч TI « из элементов 1 - наличие соединения и О - отсутствие соединения. Равенство элемента матрицы соединений единице, T.e., 1, означает налиj -го выхода распрэделичие соединения I -ой группы комму тителя 4 со входом руюших входов соответствующего мультиплексора 5. Матрица соединений обладает следующими свойствами: лишь один элемен каждого столбца равен , сумма матриц соединений всех мультиплексоров 5 является матрицей, все элементы которой равны . 1ервое свойство матриц соединений выходов распределителя 4 с группами коммутирующих входов мультиплексоров 5 ознчает подключение каждого выхода распределителя 4 к одному из коммутирующих входов каждого мультиплексора 5. Следствием второго свойства является то, что порядковый номер группы коммутирующих входов, подключенных к одному выходу рао предёлйтеля 4, последующих мультиплекса ров 5 не повторяет порядкового номергрупп входов предыдущих мультиплексоров 5, подключенных к тому же выходу распределителя 4, и порядок подключения последующих выходов распределителя 4 не повторяет порядка подключения предьщущих .выходов распределителя 4 к группам коммутирующих входов мультиплексоров 5. Для W 3 и Ия 4 матрицы соединений выглядят следующим образом:

П 3Т 4

110000 Г11111 lOOOOOOOOOOOOOOOOOd 001100 ОООООО11111100ОООООООООО ОООО11, ОООООООООООО1111110ООООО О0101СГ оООООООООООООООООО 111111 100001 ,О1О100, OOOOOOllOOOOllOOOOllOOOOl

coo101 1loooooooooooo1looooiloo

010010 . OOllOOOOllOOOOOOOOOOOOOO . 10lOOOJ tOOOO 1 lOOOO 1 lOOOO 1 lOOOOOO,

OOOOOOOO1010001010001010 OO10lOOOOOOOlOOOO1lOOOO1 lOOOOllOOOOlOOOOOOOlOlOO

oioioooioioooioioooooooq

OOOOOOOOOIOIOOOIOIOOOIOI OOOIOIOOOQOOOIOOIOOIOOIO OIOOIOOIOOlOOOOOOOlOlOOO 10lOOO10lOOOlOlOOOOOOOOO

При отсутствии необходимости получе, ния максимальной периодичности возможно использование распре 1елителя 4 на меньшее 1испо выходов, при этом уменьщается чиспо идентичных входов в группе, однако свойства матриц соединений остаются теми же. Соответствующие информационные входы мультиплексоров 5 соединены друг с другом и с соответствующим выходом регистра 2 сдвига (генератора исходной последовательгности равномерно распределенных П - разр1 5ных псевдослучайных чисел). Выходы мультиплексоров 5 подключены к вь1ходам устройства.

Мультиплексор 5 состоит из р (ti-l) входовых элементов ИЛИ 6, входы каждого из которых образуют группу коммутирующих входов, двухвходовых элементов И 7, первые входы которых являются информационными входами мультиплексора 5, и одного п -входового элемента ИЛИ 8. Выходы (in-1) 1-входовых элементов ИЛИ 6 подключены ко вторым входам элементов И 7. Выходы элементов И 7 соединены со входами ; П -входового элемента ИЛИ 8, и.1ход которого являетсй выходом мультиплексора 5. Генератор работает следующим образом. Тактовые импульсы, поступая на тактовы вхоа регистра вызывают появление непов торяющихся в периоде чисел из интервала Г 0,2 - 11 на информационных входах мупьтиплэксоров 5. При этом на одном из выходов распределителя 4 присутствует потенциал, поступающий на один из коммутирующих входов каждого мулвтиплексора 5. Разрешающий потенциал через элемент ИЛИ 6 поступает на второй вход одного из элементов И 7 каждого мультиплексора 5, обеспечивая тем Ъамым прохождение на выход мультиплексора 5 информации с выхода одного из разрядов регистра 2 сдвига с сумматора по модулю два в цепи обратной При подключении выходов распределителя 4 ко входам мультиплексоров 5, согласно вЫщеизложенному правилу, на выход каждого из мультиплексоров 5 поступает информа ция с выхода одного из разрядов регистра 2 без дублирования, что изменяет вес разрядных выходов регистра 2, выходная инфор мация которого представлена в позиционной системе счисления. Благодаря наличию делитепя частоты 3 с коэффициентом пересчета

в цепи тактирования распределителя 4

2

16

32

64

128

256

512 1024 .Сравнив аппаратурные затраты и длину М51борки предлагаемого генератора и прототипа, условно .приравнивая сложность делителя частоты и распределителя потенциалов к сложности счетчика, а мультиплексора блоку сумматоров но модулю два, можно отметить что при возрастании оборудования на (-rt-l) мультиплексоров длина выборки увеличивается в Использованиепредлагаемого генератора о псевдослучайных чисел в устройствах статнотнческого кодирования позволяет значительно повысить точность статистического кодировайия,следствием чего является повьпиение точности стохастического вычисления.55 Формула изобретения 1. Генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по

з1аноувеличение длины выборки.

Т.

6

24

120

720

5О4О

40320

36288О

36288ОО 45 разрещающий потенциал на одном его выходе удерживается в течение генерации одного цикла псевдослучайиых чисел. Перед началом очередного цикла распределитель 4 переключается и разрешающий потенциал появляе ся на следующем его выходе. Таким образом осуществляется изменение веса двоичных цифр, совокупность которых в отдельные моменты времени представляет собой число исходной последовательности, что позволяет изменять порядок следования чисел в цикле выходной последовательности относительно исходной. Очевидно, число возможных изменений веса двоичных цифр Г |без дублирования ограничивается числом перестановок из Т1 элементов, т.е,/ что находит выражение в порядке подключения выходов распределит ля 4 к коммутирующим входам К1ультиплексоров 5.. Вообще говоря, максимально возможный период следования, и соответственно длина выборки , IT - разрядных псевдослучайных чисел, неповторяющихся в пределах цикла, равны 2 /. Предлагаемое устройство обеспечивает период таких последовательностей 2 1 , а прототип - 2п Ниже покамодулю два в цепи обратной связи, вход которого подключен к выходу генератора тактовых импульсов, о тлич ающий с я тем, что, с целью расширения функциональных возможностей Генератора за счет увеличения пери од а генерируемых чисел, он содержит делитель частоты, распределитель потенциалов и группу мультиплексоров, первая группа входов которых соединена с выхода регистра сдвига с сумматором по модулю два в цепи обратной свчзи, а втораягруппа входов-с выходами распределителя потенциалов, вход которого через делитель частоты подключен к выходу генератора 2. Генератор Во пЛ, о т л и ч а ю щ и и с я тем, что мультиплексор содержит блок элементов ИЛИ, блок элементов И и элементов ИЛИ, выход которого является

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

Источники информации, принятые во внимание при экспертизе:

8

1.Патент США № 3700869, кл. 235152,,1974.

2.Яковлев В. В., Федоров Р. Ф. Стохас тнческие вычислительные машины. Л., Машинос троение , 1974.

3.Заявка № 2124371/24, 1975, по «оторой принято решение о выдаче авторокого свидетельства.