Генератор псевдослучайных чисел

Саз Соаакмма Социалме чесжма раси убвти(22) Заявлено 0.03 76 (21) 233228 И 7 С 15/00 6 Р 1/02 присоединением за Гфсударстваеай аавтет Феввтв Иектрее СОР в делам ааеарвтвеа а Отзцзмтмй(43) Опублииовано 15.04.78 Зюллетень М 14 (53 (45) Дата опубликования описания 23.03,78 ДК 681.32М. Г. Пояс и А. Ж. Виксна ститут электроники и вычислительной техникиАН Латвийской ССР(71) Заявитель ЕЛ ЕНЕРАТОР ПСЕВДОСЛУЧАЙН Изобретение относится к области вычислительной техники, в частности к генераторам дискретных функций, позволяющим получать последовательности псевдослучайных чисел с равномерным законом распределения, и может оыть использовано в качестве генератора случайного сигнала в устройствах статистического . кодирования тила код-вероятность" и .аналог-вероятность".сИзвестрн генератор псевдослучайных чи- тО сел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи. Этот генератор позвсляет получать последовательность случайных чисел с периодом следования не более 2 . - 1 1. т 5 звест ных чисел, периода и мых регис дулю два вических два, на вдослуч логлюпсерег ра сд н также генератор псевдослучайкоторый для увеличения длинымеет два одновременно тактируера сдвига с сумматорами по моцепях обратной связи и группу схем типа сумматоров по модувыходах которых формируются йные числа. Наличие второго вига с обратной связью и группы логических схем позволяет удлинить период следования генерируемой последовательности - разрядных чисел, который равен(2 -1) т(2 ф), где .П сттт- разрядностииспользуемых регистров сдвига. ;Однакоэтот генератор при значительно большемпериоде следования псевдослучайных чиселне обладает оптимальным значением автокорреляционной функции, необходимой для повышения эффективности статистического кодирования 2.Наиболее близким техническим решениемк данному изобретению является генераторпсевдослучайных чисел, содержаший регистрсдвига с сумматором по модулю два в цели обратной связи, вход которого подключенк выходу генератора тактовых импульсов 3.. Этот генератор позволяет генерировать последовательности неповторяюшихся в цикле 20 псевдослучайных чисел с периодом следования и соответственно с максимально возможной длинои выборки К = 2 , что является недостаточным для проведения статистического кодирования и стахостического 25 вычисления с павышеяной точностью,ров 5 не повторяет порядкового номер,.групп входов предыдуших мультиплексоров 5, подключенных к тому же выходу распределителя 4, и порядок подключения после дующих выходов распределителя 4 не повторяет порядка подключения предыдущих выходов распределителя 4 к группам коммутирующих входов мультиплексоров 5, Для ФФ =3 и И =4 матрицы соединений выгля дят следующим образом; 1: 11000 0110 0001 00101 10000 01010 00010 01001 10100 Цель изобретения является расширение функциональных возможностей генератора засчет увеличения периода генерируемых чисел.Для достижения поставленной цели генератор содержит делитель частоты, распределитель потенциалов и группу мультиплексоров, первая группа входов которых соедииена с выходами регистра сдвига с сумматором по модулю два в пепи обратной связи, а вторая группа входов - с выходамираспределителя потенциалов, вход которогочерез делитель частоты подключен к выходу генератора импульсов,Кроме того, мультиплексор содержитблок элементов ИЛИ,блок элементов И иэлемент ИЛИ, выход которого является выходом мультиплексора, а входы подключенык выходам блока элементов И;- первые входы которых непосредственно, а вторые входы через блок элементов ,ИЛИ подключены ко входам мультиплексора,На фиг. 1 показана блок-схема генера".тора; на фиг. 2 - блока-схема мультиплексора. 25Генератор содержит генератор тактовыхимпульсов 1, выход которого подключен ко.входу регистра 2 сдвига с сумматором помодулю два в цепи обратной связи и черезделитель частоты 3 - ко входу распредели- З 0теля потенциалов 4. Выходы регистра 2 ираспределителя импульсов 4 соединены.совходами мультиплексоров 5, каждый изкоторых содержит а групп коммутирующих. входов по (1 -1) 1 индентичных входов . ув каждой группе. Схема соединений выходов распределителя 4 с группами входовкаждого мультиплексора 5 образует матрицу размером акт из элементов "1" - наличие соединения и 0 - отсутствие соединения. Равенство элемента матрицы соединений единице, т.е, С; 1, означает нали.чие соединения-го выхода распрделителя 4 со входом (, -ой группы коммутирующих входов соответствующего мультиплексора 5. Матрица соединений обладаетследующими свойствами: лишь один элеменькаждого столбца равен 1", сумма матрицсоединений всех мультиплексоров 5 является матрицей, все элементы которой равны 50"1". Яервое свойство матриц соединенийвыходов распределителя 4 с группами коммутирующих входов мультиплексоров 5 означает подключение каждого выхода распределителя 4 к одному из коммутирующих Мвходов каждого мультиплексора 5, Следствием второго свойства является то, чтопорядковый номер группы коммутирующихвходов, подключенных к одному выходу раопределйтеля 4, последующих мультиплексди п 4 111111000000000000000000 000000111111000000000000 000000000000111111000000 000000000000000000111111 ОООООО 1 1 0000 1 10000 1 1 0000 110000000000001100001100 001100001100000000000000 000011000011000011000000 : 000000001010001010001010 001010000000100001100001 100001100001000000010100 010100010100010100000000 000000000101000101000101 000101000900010010010010010010010010000000101000101000101000101000000000 При отсутствии необходимости получения максимальной периодичности возможно использование распределителя 4 на меньшее число выходов, при этом уменьшается число идентичных входов в группе, однако свойст- ва матриц соединений остаются теми же. Соответствующие информационнве входы мультиплексоров 5 соединены друг с другом и с соответствующим выходом регистра 2 сдвига (генератора исходной последовательности равномерно распределенных а - разрщных псевдослучайных чисел). Выходы мультиплексоров 5 подключены к выходам устройства.Мультиплексор 5 состоит иэ .Р (Ф) входовых элементов ИЛИ 6, входы каждого из которых образуют группу коммутирующих входов, двухвходовых элементов И 7, первые входы которых являются информационными входами мультиплексора 5, и одного т - входового элемента ИЛИ 8. Выходы (а -1)1-входовых элементов ИЛИ 6 подключены ко вторым входам элементов И 7. Выходы элементов И 7 соединены со входа; ми, 1 п -входового элемента ИЛИ 8, выход которого является выходом мультиплексора 5.602975 Вообще говоря, максимально возможный период следования, и соответственно длина выборки, Ф - разрядных псевдослучайных чисел, неповторяющихся в пределах цикла, равны 2 ф, Предлагаемое устройство обесФЬ 1печивает период таких последовательностей 2 1 , а прототип - 2 2 тс, Ниже покаМвзаноувеличение длины выборки. 3 8 64 16 245 32 1206 64 7207 128 50408 256 403209 512 362880101024 3628800Сравнив айпаратурные затраты и длину модулю два в цепи обратной связи, вход ковыборки йредлагаемого генератора и прото- торого подключен к выходу генератора тактипа, условно, приравнивая сложность дели-, товых импульсов, о т л и ч а ю ш и й с я теля частоты и распределителя потенциалов тем, что, с целью расширения функцнональк сложности счетчика, а мультиплексора - 15 ных возможностей генератора за счет увели-.блоку сумматоров ло модулю два, можно чения периода генерируемых чисел, он содеротметить что при возрастании оборудования жит делитель частоты, распределитель потенна (Ф) мультиплексоров длина выборки циалов и группу мультиплексоров, перваяр 5увеличивается в -раз.Я 7группа входов которых соединена с выходаИспользование предлагаемого генератора ми регистра сдвига с сумматором по моду- псевдослучайных чисел в устройствах статно- лю два в цепи обратной свцзи, а вторая тического кодирования позволяет значительно группа входов-с выходами распределителя повысить точность статистического кодирова- потенциалов, вход которого через делитель йия, следствием чего является повышение частоты подключен к выходу генератора точности стохастического вычисления. импульсов. фоРмула изобретения 2. Генератор-йо п.1, о т л н ч а ю -ш и й с я тем,чтомультиплексор содержит 1. ГенеРатоР псевдослУчайных чисел, со- блок элементов ИДИ, блок элементов И и держащий регистр сдвига с сумматором ло ф элементов ИЛИ, выход которого являетсяГвнератор работает следующим образом,Тактовые импульсы, поступая на тактовый вход регистра 3 вызывают появление неповторяюшихся в периоде чисел из интервала0,2 ф - 1 на информационных входах мультиплексоров 5. При этом на одном из выходов распределителя 4 присутствует потенциал, поступающий на один из коммутирующих входов каждого мулвтиплексора .5. Разрешающий потенциал через элемент ИЛИ 6 поступает на второй вход одного из элементов И 7 каждого мультиплексора 5, обеспечивая тем самым прохождение на выход мультиплексора 5 информации с выхода одного из разрядов регистра 2 сдвига с сумматора по модулю два в цепи обратной связиПри подключении выходов распределителя 4 ко входам мультиплексоров 5, согласно вышеизложенному правилу, на выход каждого из мультиплексоров 5 поступает информация с выхода одного из разрядов регистра 2 беэ дублирования, что изменяет вес разрядных выходов регистра 2, выходная информация которого представлена в позиционной 25 системе счисления. Благодаря наличию делителя частоты 3 с коэффициентом пересчета 2 в цепи тактирования распределителя 4 разрешающий потенциал на одном его выходе удерживается в течение генерации одного цикла псевдослучайных чисел, Перед началом очередного цикла распределитель 4 переключается и разрешающий потенциал появляез ся на следующем его выходе, Таким образом осуществляется изменение веса двоичных цифр, совокупность которых в окцельные мо- менты времени представляет собой число исходной последовательности, что позволяет изменять порядок следования чисел в цикле выходной последовательности относительно исходной. Очевидно, число возможных измеФ.нений веса двоичных цифрбез дублирования ограничивается числом перестановок иээлементов, т,е, , что находит выражение в порядке подключения выходов распределителя 4 к коммутируюшнм входам мультиплексоров 5.ф7 Тиражосударственного кпо делам взоб13035, Москваэ 730 Подписное митета Совета Министров С етений н открытийЖ, Раушскаи наб., д, 4/5 э 1858 ЫНИИПИ филиал ППП Патент, г. Ужгород, ул. Проектная, 4 7выходом мультиплексора, а выходы подключены к выходам блока элемента И, первые входы которых непосредственно, а вторые входы через блок элементов ИЛИ подицочены ко входам мультиплексора, 5 Источники информации, принятые во внимание прн экспертизе: 81Патент США М 3700869, кл. 235- 152, 1974.2. Яковлев В. В., федоров Р, ф. Стохаатические вычислительные машины, Л., фМа- шиностроение", 1974.3. Заявка М 2124371/24, 1975, по которой принято решение о выдаче авторокого свидетельства.