Генератор псевдослучайных чисел
Иллюстрации
Реферат
С©тоа Соаатсмма
Социалметмчесюа
Раси убити (И} 602075 с т-,с ( аы (б1) дополнительное к авт свид-ву—
{22) Заявлено 09.03.76 (21) 233228 (51} И, Кл;
6 07 С 15/00
1/02 с ирисоединеинем заявки Pb
Гфеударатаеееиа аавтет
CNaTa Иаактрее ССУ ае делам ааеаретееа
If атармтаВ (23) Приоритет (43) Опубли ковано15-04. 78 Зюллетень,йе 14 (45} Дата опубликования описания 23.03.78 (Я} УДК 681.325 (088.8 } (72) Автори изобретения
° М. Г. Пояс и А. Ж. Виксна
Институт электроники и вычислительной техники
AH Латвийской ССР (71) Заявитель (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ
Изобретение относится к области вычислительной техники, в частности к генераторам дискретных функций, позволяющим получать последовательности псевдослучайных чисел с равномерным законом распределения, и может оыть использовано в качестве генератора случайного сигнала в устройствах статистического . кодирования тица код-вероятность" и. аналог-вероятность".
Известрн генератор псевдослучайных чи- тв сел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи. Этот генератор позвсляет получать последовательность случайных чисел с периодом следования не более 2 .— 1 (1). 15.
Известен также генератор псевдослучайных чисел, который для увеличения длины периода имеет два одновременно тактируемых регистра сдвига с сумматорами по мо-20 дулю два в цепях обратной связи и группу логических схем типа сумматоров по модулю два, на выходах которых формируются псевдослучайные. числа. Наличие второго регистра сдвига с обратной связью и груп-25
2 пы логических схем позволяет удлинить период следования генерируемой последовательности — разрядных чисел, который равен (2 -1 } <(2 -1 }, где . П с ттт- разрядности используемых регистров сдвига. )Однако этот генератор при значительно большем периоде следования псевдослучайных чисел не обладает оптимальным значением автокорреляционной функции, необходимой для повышения эффективности статистического кодирования (2) .
Наиболее близким техническим решением к данному изобретению является генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два в цели обратной связи, вход которого подключен к выходу генератора тактовых импульсов (3).
Этот генератор позволяет генерировать последовательности неповторяюшнхся в цикле псевдослучайных чисел с периодом следования и соответственно с максимально возможной длинои выборки К = 2, что является недостаточным для проведения статистического кодирования и стахостического вычисления .с повышенной точностью, 602975
Цель изобретения является расширение функциональных возможностей генератора за счет увеличения периода генерируемых чисел.
Для достижения поставленной цели гене ратор содержит делитель частоты, распр . делитель потенциалов и группу мультиплексоров, первая группа входов которых соеди. иена с выходами регистра сдвига с сумматором по модулю два в цепи обратной связи, а вторая группа входов - с выходами распределителя потенциалов, вход которого через делитель частоты подключен к выходу генератора импульсов, Кроме того, мультиплексор содержит блок элементов ИЛИ,блок элементов И и элемент HllH выход которого является выходом мультиплексора, а входы подключены к выходам блока элементов И; первые входы которых непосредственно, а вторые вхо ды через блок элементов,ИЛИ подключены ко входам мультиплексора.
На фиг. 1 показана блок-схема генера". тора;.на фиг. 2 - блока-схема мультиплексора. 25
Генератор содержит генератор тактовых импульсов 1, выход которого подключен ко. входу регистра 2 сдвига с сумматором по модулю два в цепи обратной связи и через делитель частоты 3 - ко входу распредели- gp теля потенциалов 4. Выходы регистра 2 и распределителя импульсов 4 соединены: со входами мультиплексоров 5, каждый из которых содержит т групп коммутирующих . входов по (-1) t индентичных входов . 55 в каждой группе. Схема соединений выходов распределителя 4 с группами входов каждого мультиплексора 5 образует матрицу размером к т из элементов ") " — наличие соединения и О - отсутствие сое- 4р динения. Равенство элемента матрицы соединений единице, т.е. 5." 1, означает нали1 чие соединения ) -го выхода распоеделителя 4 со входом t. -ой группы коммутирующих входов соответствующего мульти- 45 плексора 5. Матрица соединений обладает следующими свойствами: лишь один элемент каждого столбца равен 1", сумма матриц соединений всех мультиплексоров 5 является матрицей, все элементы которой равны 50
"1 . Первое свойство матриц соединений выходов распределителя 4 с группами ком» мутирующих входов мультиплексоров 5 означает подключение каждого выхода распределителя 4 к одному из коммутирующих 55 входов каждого мультиплексора 5. Следствием второго свойства является то, что порядковый номер группы коммутирующих входов, подключенных к одному выходу рао пределйтеля 4, последующих мультиплекс - 60 ров 5 не повторяет порядкового номер.. групп входов предыдуших мультиплексоров
5, подключенных к тому же выходу распределителя 4, и порядок подключения последующих выходов распределителя 4 не повторяет порядка подключения предыдущих выходов распределителя 4 к группам коммутирующих входов мультиплексоров 5. Для
lA 3 и Ии =4 матрицы соединений выглядят следующим образом:
Ъ =4
000000000000000000111111
0001
00101
ÎOO10
0100 1
10100
ОООО001 1 ОООО 1 10000 1 10000
: 0000000O101ООО1О1ООО1O10
OO1О1ООООООО1ОООО11ОООО1
0101000101000101000ООООО
000000000 10 1000 10 100010 1
000 10 1000QOOO 100 100 100 1 О
L О 100 100 100 10000000 10 1000
10 1000 101000 10 1ООООООООО
При отсутствии необходимости получения максимальной периодичности возможно использование распределителя 4 на меньшее число выходов, при этом уменьшается число. идентичных входов в группе, однако свойст ва матриц соединений остаются теми же.
Соответствующие информационнв е входы мультиплексоров 5 соединены друг с другом и с соответствующим выходом регистра 2 сдвига (генератора исходной последовательности равномерно распределенных а- разрщных псевдослучайных чисел). Выходы мультиплексоров 5 подключены к выходам устройства.
Мультиплексор 5 состоит иэ p (Ф-1)! входовых элементов ИЛИ 6, входы каждого из которых образуют группу коммутирующих входов, двухвходовых элементов И 7, первые входы которых являются информационными входами мультиплексора 5, и одного т — входового элемента ИЛИ 8. Выходы (м -1)1-входовых элементов ИЛИ 6 подключены ко вторым входам элементов И 7.
Выходы элементов И 7 соединены со входа;
МН; 1п -входового элемента ИЛИ 8, выход которого является выходом мультиплексора
602975
Вообще говоря, максимально возможный период следования, и соответственно длина выборки, Ф вЂ” разрядных псевдослучайных чисел, неповторяюшихся в пределах цикла, равны 2 i. Предлагаемое устройство обесИ 1 печивает период таких последовательностей
2 l, а прототип — 2 2тс. Ниже покаМ% и зано увеличение длины выборки.
3 8 6
4 16 24
5 32 120
6 64 720
7 128 5040
8 256 40320
9 512 362880
10 1024 3628800 ,(:,равняв айпаратурные затраты и длину модулю два в цепи обратной связи, вход Ко выбоРки.,йредлагаемого reHeParoPa и прото- торого подключен к выходу генератора тактипа, Условно.приравниваи сложность дели- товых импульсов, о т л и ч а ю ш и и с я телЯ ч стоты и РаспределителЯ потенциалов тем, что, с целью расширения функцнональк сложности счетчика, а мУльтиплексоРа - 1; ных возможностей генератора за счет увели-. блоку сумматоров цо модулю два, можно чения периода генерируемых чисел, он содеротметить что при возрастании оборудования жит делитель частоты, распределитель потенна (ФФ-1) мультиплексоров длина выборки циалов и группу мультиплексоров, первая
° рФ увеличивается в — раз.
Я % группа входов которых соединена с выходаИспользование предлагаемого генератора ми Регистра сдвига с сумматором по модупсевдослучайных чисел в устройствах статно- лю два в цепи обратной свцзи, а вторая тического кодирования позволяет значительно груцпа входов-с выходами распределителя повысить точность статистического кодирова потенциалов, вход которого через делитель йия, следствием чего является повышение частоты подключен к выходу генератора точности стохастического вычисления. импульсов.
Формула изобретения 2. Генератор-ho п.1, о т л н ч а ю— ш и и с я тем, что мультиплексор содержит
1. Генератор псевдослУчайных чисел, со- блок элементов ИЛИ, блок элементов И и дер аший РегистР сд а с сУмматором ло 60 элементов ИЛИ. выход которого яыяется
Гвнератор работает следующим образом.
Тактовые импульсы, поступая на тактовый вход регистра 3 .вызывают появление неповторяюшихся в периоде чисел из интервала (0,21 - 1) на информационных входах мультиплексоров 5. При этом на одном из выходов распределителя 4 присутствует потенциал, поступающий на один из коммутирующих входов каждого мулвтиплексора .
5. Разрешающий потенциал через элемент
ИЛИ 6 поступает на второй вход одного из элементов И 7 каждого мультиплексора 5, обеспечивая тем самым прохождение на выход мультиплексора 5 информации с выхода одного из разрядов регистра 2 сдвига с сумматора по модулю два в цепи обратной связи
При подключении выходов распределителя
4 ко входам мультиплексоров 5, согласно вышеизложенному правилу, на выход каждого из мультиплексоров 5 поступает информа ция с выхода одного из разрядов регистра
2 беэ дублирования, что изменяет вес разрядных выходов регистра 2, выходная информация которого представлена в позиционной 25 системе счисления. Благодаря наличию делителя частоты 3 с коэффициентом пересчета
2 в цепи тактирования распределителя 4 разрешающий потенциал на одном его выходе удерживается в течение генерации одного цикла псевдослучайных чисел. Перед началом очередного цикла распределитель 4 переключается и разрешающий потенциал появляез ся на следующем его выходе. Таким образом осуществляется изменение веса двоичных цифр, совокупность которых в окцельные моменты времени представляет собой число исходной последовательности, что позволяет изменять порядок следования чисел в цикле выходной последовательности относительно исходной. Очевидно, число возможных измеФ. нений веса двоичных цифр i без дублирования ограничивается числом перестановок иэ элементов, т.е, W, что находит выражение в порядке подключения выходов распределителя 4 к коммутирующим входам мультиплексоров 5. г
602 975
Составитель А. Карасов
Редактор M. Трофимова Техред М. Борисова Корректор Н. Ковалева
Заказ 1858/47 Тираж 730 Подписное
IlHHHflH Государственного комитета Совета Министров СССР по делам изобретениЯ н открытий
113035, Москва, Ж-35, Раушскан наб., д. 4/5 филиал ППП Патент, г. Ужгород, ул. Проектная, 4
7 выходом мультиплексора, а выходы подключены к выходам блока элемента И, первые входы которых непосредственно, а вторые входы через блок элементов ИЛИ подключены ко входам мультиплексора. 5
Источники информации, принятые во внимание при экспертизе:
1 ° Патент США М 3700869, кл. 235152, 1974.
2. Яковлев В. В., Федоров P. Ф. Стохаатические вычислительные машины, Л., Ма.- шиностроение", 1974.
3. Заявка 14 22112244337711//2244, 1975,. по которой принято решение о выдаче авторокого свидетельства.