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

ОПИСАНИЕИЗОБРЕТЕНИЯ -)868734К АВТОРСКОМУ СВ ИТВЛЬСТВУ Союз Советских Социалистических Республик(63) Дополнительное к авт, свид-ву М Клз 6 Об Г 1/02 6 07 С 15/00 22) Заявлено 1009,7присоединением за23) Приоритет 21)2815712/18 вки йо Государстаеняый коикте СССР яо аслам язобретеякй н открытяй(088,8 та опубликов описания 30,09,8 72) Авторы изобретения(71) Заявител 54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к тельной технике и может быт эовано в качестве устройств лучения случайных чисел при задач методом Монте-Карло, для построения генераторов процессов с заданными харак вычислиь исполь а для порешенииа также случайнытеристик я - повышение точа счет приблнжеИзвестен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи 1 .Недостатком такого генератора является наличие периода в формулируе. мой последовательности. 15Известно также устройство, в котором для приближения свойств псевдослучайных чисел к свойствам истинно случайных, полученных физическими способами, период повторения последоО вательности увеличен до величины22 ф 2ко"периодичность в укаэанномустройстве сохраняется.Наиболее близким к предлагаемому 25 является генератор псевдослучайных чисел, содержащий первую и вторую группы двухвходовых сумматоров по модуюпо два, первую и вторую группы элементов И, группу элементов ИЛИ, груп пу триггеров и генератор равновероятной двоичной цифры. Подобный генератор предназначен для генерирования за один такт двух в-разрядных псевдослучайных чисел 3 .Недостаток описанного устройства - отличие вероятности появления нуля нли единицы в. разрядах чисел от 0,5 по обоим каналам. Так, вероятность появления нуля или единицы в любом разряде псевдослучайного числа по обоим каналам определяется иэ выраженийО) г у. ЮИзвестно, что построение таких высокоэффективных устройств, какие приведены в 2, имеет смысл прн небольших значениях величины 1 а. В этом случае выражение= ---- .2 м ф характеризующее отклонение от равновероятности, принимает значение, величина которого в ряде случаев оказывается недопустимой. Даже при а=10,=0,001.Цель изобретениности генератора зчайной последовательности с последовательностью отсчетов равновероятной двоично 9 цифры.Это следует из такого факта, что выражение для формирования значения любого разряда выходного псевдослучайного числа по обоим каналам на основании (3)-(6 ) представляется в виде выраженийд 1 (с) д 5(1 с)9 х (1 с) у 1 фф 1 в ф (9)а (1 с) д (1 с)ах(1 с), 1=Ге, (10)В1 где 51; так, например, для д, Ь 1 Юд= о Ь 1 Ь 79 Ь 6 Юх=д Ех. Здесь в преобразованиях используется свойство сдвига и сложения М-последовательности.Таким образом, вероятность появления нуля или единицы на выходе любого разряда псевдослучайного числа по лю бому каналу определяется следующим образомУчитывая, что а и х независимы,1 выражение (11)принимает вид+ Р(а 5=4) Р(Х=О)=О 6- -Чх (Ю)Анализ выражения (12) показывает,что вероятность появления единицы или 30нуля на выходе генератора отличаетсяот 0,5 на величину1 х2"-1где 1 - отклонение от 0,5 вероятности35появления единицы на выходе генератора равновероятной двоичной цифры.Так как величина 1 с =0,01 - 0,001для известных устройств 11, то значение Р(С 1=1) незначительно отличается от 0,5. Таким образом, вероятностьпоявления нуля или единицы в разрядахпсевдослучайных чисел по обоим каналам в предлагаемомустройстве максимально приближена к 0,5, Для случая 45И 1=10,величина, характеризующая отклонение от 0,5, равна 0,00001-0,000001,Таким образом, природа выходныхпсевдослучайных последовательностеймаксимально приближена к истинно случайным числам. Предлагаемый генератор отличается простотой технической реал 1 ации. Удельные аппаратныезатраты на один разряд псевдослучайного числа составляют один элемент И,-элемента ИЛИ,двухвходового сум 2.матора по модулю два, - трехвходовосго сумматора по модулю два, - триггера игенератора равновероятнойдвоичной цифры. Предлагаемый генератор псевдослучайных чисел позволяет 60получать числа по двум каналам.Применение предлагаемого генератора псевдослучайных чисел позволяет повысить точность и достоверность 5 решения задач методом Монте-Карло. Кроме того, подобные устройства позволяют получать истинно "белый" шум для построения генератора случайных процессов.формула изобретенияГенератор псевдослучайных чисел,содержащий первую группу из в-) двухвходовых сумматоров по модулю два, вторую группу издвухвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цирры,ко входу которого подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй групп соответственно, вторые входы в-) младших элементов И первой группы подключены, соответственно, к выходам вдвухвходовых сумматоров по модулю два первой группы,вторые входымладших элементов Ивторой группы подключены соответственно к выходаммлацших двухвходовых сумматоров по модулю два второй группы, выходы 1-х элементов И первойи второй групп подключены к соответствующим входам 1-го элемента ИЛИ, выход которого подключен ко входу 1-го триггера, к первым входам 1-х двухвходовых сумматоров по ьюдулю два первой и второй групп подключены соответственно единичные выходы 1-х триггеров, вторые входы в) младших двухвходовых сумматоров по модулю два первой группы подключены соответственно к выходам встарших сумматоров по модулю два первой группы, выход генератора тактовых импульсов подключен к синхровходам триггеров, о т л и ч а ю - щ й й с я .тем, что, с целью повышения точности генератора, он содержит первую группу из 1 трехвходовых сумматоров по модулю два и вторую группу иэ в-) трехвходовых сумматоров по модулю два, к первым входам 1-х трехвходовых сумматоров по модулюдва первой и второй групп подключены единичные выходы (в-)+1)-х и (+ +1)-х триггеров, соответственно, вторые входы 1 трехвходовых сумматоров по.модулю два первой группы подключены к выходаммладших триггеров, вторые входы втрехвходовых сумматоров по модулю два второйгруппы подключены к выходам вмладших триггеров, третьи входы 1 трехвходовых сумматоров по модулю два первой группы подключены к нулевому выходу генератора равновероятной двоичной цифры, третьи входы ) трехвходовых сумматоров по модулю двавторой группы подключены к единично-му выходу генератора равновероятнойдвоичной цифры, выходытрехвходовых сумматоров по модулю два первой группы подключены соответственно ко вторьм входамстарших двухвходовых сумматоров по модулю двапервой группы, а выходыстаршихтрехвходовых сумматоров по модулюдва второй группы подключены соответственно ко вторым входаммладшихдвухвходовых сумматоров по модулюдва второй группы, кроме того, выход -го трехвходового сумматора помодулю два первой группы подключенко второму входу щ+)-го элемента И первой группы, выход 1-го трехвходового сумматора по модулю двавторой группы подключен ко второмувходу (+)-го элемеьта И второйгруппы.источники информации,принятые во внимание при экспертизе1. Яковлев В.В., федоров Р.Ф.Вероятностные вычислительные машины. Л., фйашиностроение", 1974,с,344.2. Авторское свидетельство СССРУ 524175, кл. О 06 Р 1/02, 1975.3, Авторское свидетельство СССРпо заявке 9 2505976/18-24,15 кл. С 06 Г 1/02, 1978 (прототип).,1000 1010 1001 Ю 1 Редактор И.Михеева Заказ 8329/70 Тираж 748ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, -35, Раушская наб., д.4/5 Подписное филиал ППП "Патент", г.ужгород, ул.Проектная,4 4 02 8 1 У 0 0001 1001 1101 0100 ОСОО 1100 Составитель А.КарасовТехред Т.Маточка Корректор М.Коста