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

Союз СоветскихСощиалистическихРеспублик ОП ИСАНИНА ИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДВТВЛЬСТВУ 693408 4В1(51) ."51. Кл, - 5.5 О ( В 00 6 06 Е 1 О 2 с присое нием зая ооударстеенный комете СССР оо делам иэооретенкй н открытийбликовано та опублик ия описания 03.11.79 2) Авторы изобретен Е. 5"1 ельни Таганрогский радиотехнический институт им. 15.(54) ГЕНЕРАТОР ПСЕБДОСЛУС 1 АЙН 11 Х с 1 С.,Изобретение от литсльной техники вано при пастрое вычислитслы 1 ых м Известен гснср сел, соде рж а 1 ци й тором по модулю зи 11. Однако эт длиной псевдсится к области выч 1 и может быть использони и специализпрованны,ашин. атор псевдослучайных чи регистр сдвига с сумма два в цепи обратной свя Наиболее близ ности к 51 забрет псевдослучайных управления, первь вивалентности, бл два, выходы кото генератора 21. ской сушгенератор Гний блок менты эко модулю выходами ким по техниче нию является чисел, содержа 1 й и второй эле ок сумматоров Г рого являются Однако извести наличием линейно емой последовате счете снижает его Целью изобре ние точности генеарактерен формиру- конечном е атор х ыи г зави ьнос точи ения атор имостичтоть.являет повыше от генератор обладает малои ослучайной последовательнос 1 я даст 1 жсни 5 постав, снОп цс 51;нсратор солерж,г р 11,1 11 Вгор, и Ол 1; нах 151 тп, попвьс, Вт)рьстрс 51 я 1 х,1 л к 1.РЬ 1 Х СОСДИНСНЫ С НС 1 Ь;М, В 1;. 5 П;1;С,М Выходах н 0510 к 11 ,и 1 1 лснн 51 . 00 Гвс , 5 НО, Ч ТН РТ 1,НХ ;, ЛО 1.0 В :;, МВВ 1 х(1 Д 1 хи псНичл, и ВтороХ 1 э,",0110. (Я 5 к.Вива;1 снтнос и с 00 Встствспно,;1.О 11 с . В 1- рыс Выхолы - с 1 с 1 В 1)1 м 1111 ч 15 ыс х(ь 1 . - М 11 ПСР НОГО П В 1 ОРОГО ЭГ 1 ССНТ 01 КВ 111 ".:С ности соотвстствснО, г) ппы Выхол 1),1.; памяти сосли пень с 0 Входа кн 05 Ок;1 см 51;1.ТОРОВ Г 10 М ОЛ 1 Л О Л 1СООТВСТСТВСННО, ВЫ Х 1).лы которого ш 1 лключсны к группе Вх 1 лн ГСРВОГО Олока памяГн соотвс Гствснно, Грм 11- па ВыхОЛОВ которОГО подк,1 К)сна и Гру П 1. ВхОдОВ Вт 01)ОГО ОЛОка памяти соотвс 1 ствснно, кроме того, каждый блок памяти солержит счетчик, дешифратор, накопитель и буферный регистр, разрядные выходы которого являются группой выходов блока, 1-ый и 1-ый выходы - первым и вторым выхода ми блока, первый вход объелини с первы.ми входами накопителя и счетчика и яв,1 яется первым входом блока, Второй Вхол Объединен со вторым входом счетчика н 51 вля 693408ется вторым Входом олока, третий и четвертый входы являются третьим и четвер-ым входами блока, а разрядные входы соединены с разрядными выходами накопителя соответственно, разрядные входы которого яве 15)ются группой Вдо бОка, 2 Второй вход соединен через дешифратор с вь:ходом счет ика.На (риг. 1 приведена блок-схема генератора; не) фиГ, 2диаграмма, п 051 сня)огд 251 работу генератора.Генератор содержит первый блок памяти 1, состоящий из накопителя 2 с произвольной адресацией, буферного регистра 3, счетчика 4 и дешифратора 5; блок управления 6; Второй блок памяти 7; блок 8 сумматорв по п)о( 2 и два элемента 9 и 10 экВиве.Рн 1(осг(. Г) (01( . СсОнт из Як теля 11 с (роизвслИ Дресаписи, бс( н ре.(истра 2, счегчикя 13 и деешНр(т ра 4 12 к 1; ГРГ 1 2 г (д(р)кн 1 Гп яческ Гля х 2 НС 11(Я ( П-РаГ)51 ДНХ ЧИСРЛ, 2 Н 1 ЕГ 1 НТССЬ 11 - Р ячеек для хранения Ю и-разряднь(х чисел, нрн .Рм п и е". Взаимно простые. В.хдные;)азрядные Нины накопит(ля 2 подк,110 че 11 Ы к Вхдам регистра 3, 2 ВьКОд ные разрядные шины накопителя 11 - к входам регистра 12. Выходы регистров 3 и 2 попарно подклочены ко входам сответ(с гну(н,х сумматоров по )пос 1 2 олэкя 8. Выход регистра 3 пдклк)чен также ко ВХОДНЫМИ РЯЗ 1)5 ДНЬ М ШИ НЯМ ЕГЯКОГ 1 ИТЕЛЯ1, ВГ,(ходы сумматоров по Гпо(1 2 блока 8 ИО,(- клк)чень к В.(однь(м разрядным шинам н;(- капителя 2 и к Выходам 15 Генератора. Гп ЯЕ- ресных шин накопителя 2 по.;ключены к Выходе 1 м деифг)атОГ)я 5, ко Входях 1 котр- го подкл(очсны Гыходы счетчика 4 с мсду- ЛЕМ ПРРЕСЧРт ГП, 2 е, аДРЕСНЫХ 1 НИН НЯКОРпнтеля 1 подк;почены к выходам дешиссратра 14, ко Входам которого подключе 1;ы Выходы счетчика 13 с модулем перес чета 1. Счетные входы счетчиков 4 и 13, 2 так)ке иНны СЗ (Счиывание-Запись)телей 2 и 1 подключены к выходной шине РИ (Рабочие импульсы) блока управления 6, Выходная шина которого Уст 0 подключена к шинам сброса счетчиков 4, 3 и регистров 3. 12. Кроме того, выходная шина СИ (СдвигаюГцие импульсы) блэка угравления 6 подключена к шине сдвига регистров 3 и 12. Вь(ходь( и-го и (-Ого Г.Ез рядов (и и 1( взаимно простые числа) регистра 3 подксночены ко входам элемента эквивалентности 9, выход которого подключен к последовательному входу первого разряда этого же регистра. Выходы и-го и (и-ого разрядов регистра 12 нодклк(че ны ко входам элемента эквивалентности 10, выход которого подключен к последовательному входу первого разряда этого же регистра,У стройстВО имеет дВ 2 ОснОВ 51 ых режима: начальный режим формирования псевдослучайной информации и рабочий режим - режим формирования и выдачи и-разрядных псевдослучайных чисел.Режимы работы задаются соответствчоНими сигналами с выходов блока управлеия 6 (см. фиг. 2).Раоота устройства осугцествлястся следуогцим образом.В начальном режиме блок управле ния6 В первом такте вырабатывает сигнал Уст 0 (фиг. 2 а), который устанавливает В нулевое состояние счетчики адресов 4 и 3 и регистры 3 и 12, начиная с ВОрго такса блок 6 вырабнтынает рабочие;мнульРИ (фи 2 б), (ю "ту(2(.ц:.2 ( к.т 1 ые ВхОды счРТНОВ 4 и 3, (5 н(1 н СЗ Читывание- )21(ись) ньк(.г.Р,(е(иГ,1 Входы синхрОИ 11 зец( 1 реров ,Рг.РтГюв 3 1 12. Д(1 я )Гр 21.Иня н; бгой г)Р 1(СтоВ 3 и 12 бгОк 6 Вь:э 1 бать:5 СГ Г:ОГРциель:Гй (."Н.(нал (.ДВи 2 1 С (,ф:.г. 2 В. рн 52- .(1)чии сигнала ПС и (:стунлении нмпуль- "Б РИ реГистры 3 и (2 200 Гаюг В режи- ИР С ТВИЯ 32 ПИСЯНН й НОРМ 2111 В " 0- роной старш 5)х ра(зр 51 д(В. 1 рОГЧР то: О, сигнал ПС запре(цвет заГись В регистры 3 и 2 ннформаНи, прсу;ствук)щей на зьсод 1 цх разрядных ши 1 нх при считывании из . Яконителей 2 и 1. С другой стороны сиг- (2; ПС разрс:пает 22 Г)ись с 11 ЯДОВ, Осту 1 аюших па,оследва гсльные Входы первых разрядных регистров 3 и 12 с Выходов эле:(1 ентов экВР)Валентнсти;( и(. Гак)Х 1 образом, н начальном режиме регистр 3 и элеменг 9, а также реп сгр 12 и элемент 1 О зБ редставляют собой два генератора псевдослучайных последователь остей, которые формируют одинаковые последовательности, ;(о с противоположными порядками с.)едо)ания дВОичных симВОЛОВ а последоватечьностях. В Известно г.нераторе на основе 4 ОАЛПМ нулевое состояние рсч истра является запрещении) (выйти нз Него без внеш.него сигнала АЛГ 1 М не может). В Оас( х)ЯТГ)инаемом устройстве для генераторов псевдослучайных последовательностей на;.:епстрах 3, 12 и элементах 9, 10 нулевь:-: ( ос"Ояния регистров являются рабоцим . Что достигается включением в ценибрат)ь х .Вязей элементов эквивалентное)и вмет.) ум:;аторов по гпо( 2.,гРабота генератора н начальном реякимеяроисходит следующим образом.С одной стороны, импульсы РИ и потенциал ПС, поступая ня ре;истры 31 РИВОДЯТ К ТОМУ, ЧТО .1 ОСЛЕДНИР СОВМЕС("Оэлементами формируют гсевдослучайпоследовательности, С другой стороны, рабочие импульсы РИ, поступая на; Ртыс:,ходы счетчиков 4 и 13, в каждом та те узе 693408личивают на единицу номера адресов, по которым происходит обращение к накопителям 2 и 11. Кроме того, положительные импульсы сигнала РИ, поступающие на шины СЗ (Считывание-Запись), в первой половине каждого такта воспринимаются накопителями 2 и 11, как сигнал Считывание числа по выбранному адресу. Пауза .сигнала РИ на шинах СЗ во второй половине каждого такта воспринимается накопителями 2 и 11, как сигнал Запись числа по выбранному адресу. Таким образом, в каждом из накопителей в одном такте вначале считывается число, хранящееся в выбранной ячейке памяти, а затем по этому же адресу записывается число, поступающее на входные разрядные шины соответствующего накопителя. Как уже отмечалось, сигналы, возникающие на входных разрядных шинах накопителей 2 и 11, не записывяотя на регистры 3 и 12, поскольку параллельные Входы последних блокируются сигналом ПС. В каждом такте во второй половине такта псевдослучайное число, присутствующее в регистре 3, записывается в выбранную ячейку накопителя 11. Это же число поразрядно складывается на блоке сумматоров 8 с псевдослучайным числом, присутствующим в этом такте в регистре 12. С вьходов блока 8 результат поразрядного сложения записывается в выбранную ячейку накопителя 2. По истечении гп тактов (в предложении, что гп 1) во всех ячейках накопителей 2 и 11 будут записаны некоторые псевдослучайные числа. Следует отметить, что в ячейках накопителя 11 будут все разные числа. В 1 первых ячейках (если к ( ф - ) накопителя 2 г 5 ри гп (и после пт тактов Оудут записаны нули, а в остальных -- псевдослучайные числа, отличные от чисел, записанных в накопителе 11. Во избежание наличия большого числа нулей значение номера разряда 1 регистра 3, с выхода которого заводится обратная связь на элементы 9, необходимо выбирать достаточно малым, порядка 2 - 4. При этом псевдослучайные последовательности, формируемые регистрами 3,. 12 и элементами 9, 10 могут ,.лучиться не максимальными. Однако в этом нет никакой необходимости, поскольку е:;: .ость накс 5 пителей 2 и 11 (число ячеек памяти) намного меньше числа символов в последовательности максимальной длины, т. е. гп ( ( 2 - 1; ь ( ( 2 щ". Можно выбрать 1 и достаточно большим 1 ((если этого , ребует условие генерации последовательос и длины 2 - 1), Во избежание записи больцого количества нулевых чисел в накоггителе 2 потенциальный сигнал ПС необходимо формировать длительностью в 2 тактов. Время существования сигнала ПС можно выбрать необязательно кратным гп тактам. В общем случае можно указать, что 10 20 25 36 6длительность сигнала Г 1 С должна удовлетворять неравенству 1 спТри, где Тпи - . период следования рабочих импульсов.По окончании начального режима (ОИ 5:чание сигнала ПС) регистры 3 и 12 перключаются в режимы статического хранения информации с записью и Выдачей чисел параллельными кода ми. В Ото у гствипотенциала ПС сигналы с выходов элемтов эквивалентности 9 и 10 не воспринимаются первыми разрядами регистров,3 и2После окончания ПС блок управлениявыдает второй сигнал Уст 0, осуществляющий сброс счетчиков 4, 3 и регистров 3и 12 (фиг. 26). Со следующего такта начинается рабочий режим формирования и-разрядных псевдо.хайн ы х .В ряоо гемжи;г;1 яследх юЦи. Образом В ОО:пульс РИ, посту: якнцсчетчиков 4 и 13. с,.В ссст 05 ни. 1 .",э,14 Всзохждяют я 15 сн ц . ,ВЕТСТВЮЩИХ НЯКО;ИТС.".С "единичный уровень Р 1 ; Срвс.ТЯКЯ, ПОСТХЯ 5 Ь,:.: С.:Я:2 и1, осу 5 цссг,5, ,.55 ЩИХСЯ В ХЧ)ВЫХ 5:":,и1. Сигн 5 ы,СЧИТЯННЫХ ИСЕЛ,;О 5разрядных шинах Вкс.;.и:".с .воздействием этих с: ;С,и:, сина шинах сииОнизя 5)и ",1 я:.;.копителей 2 и 11 чсля,:.я.1: ю-.:я ссветственно на регистры 3 и 12. С:хо В "; -гистра 3 считанное из ;срв,:, я., ":к:пителя 2 число постяет ия .;,хо. рядные шины нанон:гс,:яды блока 8. НЯ нтсрыс нходь: Г. ; 8 ступают рязря;ы числя. считя;:Ого и ВОЙ ячейки някснте,яна регистре 12. В итоге на Выхо.мх О О (блок сумматоров по гное 2) поя;-.:, ;. я ч,:., ло, представляющее псразр 51 д, у 5 О сум.5 входных чисел. Эта поразрядная сумма .5- ляется первым псевдослучайным и:Ом.О торсе поступает на выхо ы генерстспа 5 и на выходные разрядные шины някоНт- ля 2. Во второй половине первого такта нулевой уровень сигнала РИ, поступая на шины СЗ накопителей 2 и 11, Осуществляет запись чисел, присутствующих ня Вхо,ных разрядных шинах в первые ячейки накопителей 2 и 11, т. е. в первую ячейку накопителя 2 записывается первая поразрядная сумма, а в первую ячейку накопителя 11 записывается число, ранящееся ня регистре 3.Во втором такте сигнал РИ устанавлиВает счетчики 4, 13 в состояние 2. ДецНфраторы 5 и 14 возбуждают адресные шины вто грых ячеек накопителей 2 и 11, В результате в:ср 3(й половице второго такта произойдет считывание цисел со вторых ячеек накоцитслс Й 2 и 11 ца регистры 3 и 12. Кроме того, сумматорами по т 0( 2 Олока 8 Осуществляется поразрядное сложение чисел, записаных ца регистрах 3 и 12. В и 0-с образуется второе Псевдослучайное число, цо ступающее на выходы 15 и на входные р;юрядцыс шины накопителя 2. Во второй псГс)- вике такта зто число записывается Бо вторук) 5 чсйкх накопителя 2. ВО Вторук) ячейку цакоцитсля 11 записывается число, .сра нящееся на регистре 3.В ГееГьцс 1 пс 51 с цс)РГчплс)313(е)м к 3 ждОГО ИЦ)ЛЬС а . ) ЦОС, .,ОБ 11(."1 ЬНО ИЗЧСЦЯКТС 5 ,с 0 ци, с).Оз 1 . 1 и, с,сдБ) л- цо, Г)с, и .с ГГ 1 51 стся ПО(т(;О ват(., ь нос Об) 1.щсние к яц;ика, Накципсгс 2 и 11. При -,ТОЧ 3.С )Б; И цо, гСС 1;К Ч ОС Чцес Г 3.1 ГС 51 С ЧИТЫ БЕ 1;ССС. ИЗ БЬОРИ ЦЦЫХ 5111: Накопи Гстси " .1 с:)анис ю ца регистры 3 лв и2: цор(зря;Пос с.10 жсцис эих цис.010 К( Г, а ВО БТОРОИ ПОГ 10 ВЦНС ЗЕЦИС 1 нора 3;)д 301 СЧГ1 13 Б 1 бНцуЮ я)СЙКХ ца ОПИТС,1и ИС 11, ХР 1 Ц 5 ЦК 51 1(а РСИСТ рс 3, 3 Бы ра ни 1 О 5(.Йк и 1 коцися 1 .г) с 1 Г ) т 0 1 О,0 с ч Р т ч и к 1 3 и м с( т )(;х, 1 ь цересцс)а О, в 8-см санте он скажете Б нмлевом состояни, Б результате дсцифрагор 14 выоср.т цос,с;кк) Е-к) 5 )Йк) накоцителя 1. В Остальноч генератор Оудст раОтаь Гекжс, как и В п 1)сдьГпик с.учаях.15 (Р -) -0, Бкге сс 1 чик ц хстс 1 али;3- ется Б (е -1) -Ос состояние и Ол ис е Б,ястс сбр(31 СНРГР и (С - 1).ойцикс накопит(.л 51 2. (,.тис 13 устине В,иВ 1(.тсЯ Б цср- ОС СОТОНИС) 31, СГ 1 РДОБ 11 с ЬНО, ООрсц(ПИС О 1 С Т 3,151.)Т.Я К ПСрвОЙ 51 ЧСИКС ц 1 КОГ РГС С 51 г . В рссзчгьт 1 Гс норар 51;ц)10 с,ожсц 51 с(х 3 .)тх 5 ск 1(1 Выхо 3,(. 0,101 Г( - РЧС ГС 51 (, г 1 ) -0( ЦСБДОСЛЧЧгйно( цС,г), которос 3 ьется на выход 15 и записыва- (в сгс 1 Б (е) -чк ЯчсЙкч цакоцтсл 5 2. Чсло, Быораццое цз (ь+ 1)-Ой Ячейки зтсго блока, записывас(ся также Б первую ячсйсу цакОцитсля 11.Поскольку с етц к 4 имеет чсду,ь прссчета т), тО В ш-с тактР 01 с)каж.с 51 Б 13 у.левом состоянР. Лсцисьратор 5 1:ьбрс последнюю гп-ую ячейку а копиел2. В остальном генератор бу;ет р 3)от;:ть также, как и в предыдущих сгуцаях. В (и - 1) -ом в 1 актР счстчик мсте 1 це)ВГиваетс 51 В нерво(. (10 сгояние и обращение осуществляется к цер- ВОЙ ячсЙке накОците)ч 51 2. Счетнк 13 устаНОВится Б сОст 051 цие) 1 х-Е -ПРлоч 1 с;1 сццьЙ остаток от деления (п + 1) на ь. В рсзуль 55тате поразрядного сложения выбранных псевдослуцайных чисел образуется (гг + 1)- ое псевдослучайное число, которое выдается ца Выход 15 и записывсРтсЯ Б цс ,)3), к ЯРйку накопителя 2. Крохс , Б,брнис в пРрВОЙ ПО,10 вцпс зто 0 ак а пссвд;)сгччЙ. нос чис. из первой Ячейки накопите,Я 2 з 3 пись 3 а(151 Б 1)Е 1 .О ячс 1 к БКОпи;,+етсля 1..Г, Ч;ИЦЬ)Г 1 И.С,13),,С".С :;ГС ЬНОС 1 И. иг3 1:С;) 5(,: . ри) .) .ФОГ),/.Ги цзООГ)( ) нцл1. 1 с 1 р 1 ГОч( "11,О,) 1)иИ . 1;С),. СО Де РЖ 1 И И 0,ОК Ч Ц ),1 ЛС 1 И ), 10 0 Ь И И 31 0- Р 01 З(СЦЬ) КБц)а,:Т П)СТИ, 0,10 К С) М Ы . тОРО 3 цо 10,ч,к) Два 13 хо;1 к(п ОРО)5 БГ 15- 10 ТСЯ 3 Х 0,1(3 )1 И ГС Ц .с ГОР, ОГ,ГГ)О) Ч Тех, Ч , С 1 СГЬ 0 ЦОЫЦ.Ц:Я ТочОСТ (ЦС. Р;тОРИ, СЦ СС)ДСРжцт ПСР 3,й г СРОИ 0,ОКИ ПСМ 51 ТИ, ЦС 1 ВЫ., ВТОРЫ И)г.Т 3): ХД 1 КОГОРЫХ С(С Ц Н(.ЦЬ С ЦСРВ 1 М, Б)1 ОР.)1 И Т)С ТЬ.1 ихс)дахи блока уцравлс ция соси Бстствсц, четвертьс входы блоков памяти с зыков ДВМИ ЦСРВСГО И ВтОРОГС ЗЛс ЧЕН Св ЗКВИ 31- .с цгцос-.1 соотвс.тстс;с, );срвьс и Бтс;рыс Е)ЫХОДЫ С ПЕ)РБЬ 51И ТИПЫ)1 И Б.10 3 Г)1 , 1 Р БОГО И )ТОРОГО З СОБКИИЛ(Ц НОС ГИ СООБТС 3 СЧ 1 С, 1 РЧ 1 Ц 31 Ы Х)Г),10:3 )ЛС)Ка гЧ 5СО,Ш гг(.11) СС 1) Х г);11,1 И ,1(ка С )1 М а - :С)0 цо ХДЧГ(,113 Х)Г БС хт Б, гцо.)Ь 1 ОРОГО 1:ОДКГЦОЦСНЬ 3): 3 Р) 1:3( )ХО 0сг);100 б, Ока и м 5 и ссБс с)си, Гр)выходов котсрог: цодклюцс н; крупие БХ ОД 0 1Тор Г) ОГ 10 К а ц 3 5151 ТИ СОО. 3(СТБС: 1 г).2. 1 Пг)Г ПС(вдО,Х цаИНЫХ ЧРГСЛ П 1, О),ГГГГ)(ГГГ ТС);, )1 КаК;1 ЫИ б.ОР ца 1 Т С)дерЖ 1 Г (."1 ) Си"фо" ")кои и( 1, и б) фср,11 , И тр ;а )51,1; ;)ЫХО Ы К)Гог)010 51 3,15110, 51 "Р( П;Ой БЫ)0 дов блока, 1-ьй ц )-ь:(1 Бьсодц - к гвы И ВтОрЫМ ВЫХОдаМИ б,)О:Са, Пг.рвый ВХОбЪ- сдинсн с первыми Бхсдами накопи (ля и ССТ 3 ИКа и яв)Ляегс 5 ЕБЫЧ БХ)д( б 115 второй вход обьсд;це; со вторым вхо, счетчик 3 и ЯвлЯстс 5: Вторы м Вхо,еОГ)( блок., ГретиЙче)твсрГ 1) и )ход и Вл 51 О с. Я тГ)с г,и 51 И ЧЕтверты)г ВХО,га;И ОГ 30 КБ, а ра)ЗЯц. Входы соединены с разря,чВьходам 1 накОГ 1 ителя соотВет(3 гвснцй, разрядныР вх)693408 ды которого являются группой входов блока, а второй вход соединен через дешифратор с выходом счетчика.Источники информации,принятые во внимание при экспертизе 10. Яковлев В. В. и др. Стохастическимвычислительные машиныЛ., Мащиностро.ение, 1974, с. 114.2. Авторское свидетельство СССР476340, кл. й 06 Г 1/02, 1973.693408 Составитель А, Ка Техред О. Луговая Тираж 669 кач СССР тий б., д. 4/5 Проектная,ого комитет ий и откр Раушская н жгород, ул. едактор С. Лнжоаказ 6306(21 ЦНИИПИпо дел 113035, Моск лиал ПРП П ос удаам ива, Жатент стаениобретен- 35,овКорректоПодписи