Генератор псевдослучайных чисел — SU 962931 (original) (raw)
ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистичеснихРеспублик 962933(22) Заявлено 18. 02. 81(21) 3250533/18-24с присоединением заявки Нов(51М. Кп. з С 06 Р 7/58 Государственный комитет СССР по делам нзобретеннй н открытнй(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение Ьтносится к вычислительной технике, в частности к устройствам длягенерации произвольных чисел, и может быть использовано в системах автоматики, например для управления сменой. фиксированного числа значений йерестраиваемого параметра.В аппаратуре дискретной автоматики и вычислительной технике широко используются генераторы псевдослучайных чисел, построенные на базе регистра сдвига, охваченного цепью обратной связи через сумматор по модулю два, в которых псевдослучайные числа образуются путем формирования псевдослучайной (имеющей детерминированную структуру) последовательностью двоичных символов максимального периода (щ-последовательности) и использовании определенных символов этой последовательности в качестве значений разрядов псевдослучайного числа.Известен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два и в цепи обратной связи, генератор тактовых импульсов, счетчик по модулю Б и с выходных вентилей. В известном генераторе очередное двоичное числообразуется на выходах с разрядоврегистра сдвига через каждые тЯЙимпульсов сдвига. Условие 53 Р устраняет корреляцию смежных чисел формируемой выборки (1).Недостатком известного генератора является сокращение длины выборки в Я раэ по сравнению с периодомщ-последовательности, генерируемойрегистром сдвига, а также отсутствиевоэможности ограничения величины формируемых чисел на уровне, соответствующем фиксированному числу значенийперестраиваемого параметра системыавтоматики, которое может бьюь отличным от 2 -1.Другой известный генератор 2псевдослучайных чисел, содержащийдва одновременно тактйруемых регистра сдвига с сумматорами по модулюдва в цепях обратной связи и группусумматоров по модулю два на выходахсдвига с обратной связью и группылогических схем позволяет увеличитьпериод следования генерируемой последовательности п-разрядных чисел,который равен (2"- 1)(2 п) , гдепщ - разрядности используемых реги- ЗО стров сдвига.О дггако этот генератор не обеспечивает во гможности ограничения формируемых чисел на уровне, определяемом Фиксированным числом значенийперестраиваемого параметра системыавтоматики, и имеет сложное схемное 5решение.Наиболее близким к предлагаемомуявляется генератор псевдослучайньгхчисел, содержащий основной и дополнительный регистры сдвига, счетчик, 10сумматор по модулю два, коммутатор,делитель и генератор импульсов. Выход с основного регистра через до полнительный регистр соединен с входом счетчика. Выходы разрядов осняВ:гого регистра в соответствии с коэфициентами генераторного полиномаоединены с входами сумматора по модулю два, выход которого через коммутатор соединен с информационным входом основного регистра сдвига. Управ 20ляющий вход коммутатора через делитель с переменным коэффициентом деления соединен с вторым выходом генератора импульсов и тактовыми входамирегистров сдвига. Выходы разрядов до полнительного регистра соединены с,входами коммутатора. Первый выход генератора соединен с установочнымивходами делителя и счетчика.На тактовый вход основного регистра сдвига поступает пачка из пЮ импульсов, где- разрядность. основногорегистра сдвига. Первые пг (пги)тактов основной регистр .с сумматоромпо модулю два работает как генератор 35бинарной псевдослучайной последовательности, Эатем с выхода делителявыдается сигнал на коммутатор, который переключает выходы сумматора помодулю два и дополнительного регистра таким образом, что оба регистрасдвига оставгггиеся (и-пг) тактов работают в режиме кольцевого регистрасдвига,В результате на вход счетчика поступает и символов и по окончаниицикла работы генератора в счетчикеформируется псевдослучайное число,равное числу единиц среди символовпрошедшего отрезка последовательности.Описанный цикл работы генератораповторяется для формирования каждогоновоге числа. Псевдослучайные числаформируются из пересекающихся отрезков, чем достигается возможность изменения степени корреляции.В частном случае ггг = и генерируются некоррелированные числа 13.Недостатком известного генератораявляется сокращение емкости формируемого (за период) числового массиванекоррелированных чисел в М раз посравнению с периодом последовательности, генерируемой регистром сдви. га. С другой стороны, в устройстве65 возможны ситуации формирования подряд двух и более одинаковых чисел,что нежелательно при использованииего для выработки перестраиваемогопараметра систем автоматики, так какприводит к увеличению времени, втечение которого параметр не изменяется и, следоватЕльно, к увеличению среднего времени корреляциипараметра. Кроме того, известныйГПСЧ достаточно сложен.Цель изобретения - расширениеобъема формируемого числового массива и исключение повторения смежных чисел при одновременном упрощении генератора.Поставленная цель достигаетсятем, что в генератор псевдослучайныхчисел, содержащий счетчик, коммутатор,сумматор по модулю два, первый и второй выходы которого соединены соответственно с выходами регистра сдвига, информационный вход которого соединен с выходом сумматора по модулюдва, генератор тактовых импульсов,первый выход которого соединен с управляющим входом регистра памяти, выход которого является выходом генератора, введены Р-триггер,.два элемента И, элемент задержки и блок сравнения, второй и третий выходы генератора тактовых импульсов соединены спервыми входами соответственно первого и второго элементов И, выходыкоторых соединены соответственно стактовым входом регистра сдвига исчетным входом счетчика, выход которого соединен с первым входом коммутатора и первым входом блока сгавнения, второй вход которого соединенс выходом регггстра памяти, а выходблока сравнения соединен с вторымвходом коммутатора, третий вход которого является первым входом генератора, а выход коммутатора соединенс информационным входом регистра патмяти, управляющий вход которого объединен с установочным входом Р-триггера и подключен к входу элементазадержки, выход которого соединенс входом "Сброс" счетчика, выход0-триггера соединен с вторыми входами первого и второго элементовИ, выход сумматора по модулю двасоединен с третьим входом второгоэлемента И и синхровходом Р-триггера, 0-вход которого является вторымвходом генератора,Сущность изобретения заключаетсяв формировании двоичного псевдослучайного числа подсчетом количествасимволов в единичной серии (рядследующих друг за другом единиц)ггг-последовательности, генерируемойи-разрядным регистром сдвига с сумматором по модулю два,и цепи обратной связи и замене сформированноготаким образом числа числом, равным10 ив случае равенства его предыдущему числу, что достигается введением в устройство 0-. триггера, двух эле.ментов совпадения, элемента задержки, шины числа ии блока сравнения соединенных соответствующими связямиНа фиг.1 дана структурная схема генератора псевдослучайных чисел; на фиг.2 - временные диаграммы, иллюстрирующие частный случай работы устройства.фГенератор содержит генератор 1 тактовых импульсов, регистр 2 сдвигасумматор 3 по модулю два, шину 4.питания, 0-триггер 5, элементы И б и 7, счетчик, 8, блок 9 сравнения, коммутатор 10, регистр 11 памяти, элемент 12 задержки, шину 13 вводачисла п.Первый выход генератора 1 тактовых импульсов соединен с тактовым входом регистра 2 сдвига через элемент И. Выходы разрядов регистра 2 сдвига в соответствии с коэффициентами генератора полинома соединены с входами сумматора 3 по модулю два. Второй выход генератора 1 тактовых импульсов связан со счетным входом счетчика 8 через элемент И 7. Выход счетчика 8 объединен с первым входом блока 9 сравнения, выполненного в виде схемы сравнения кодов, и подключен к первому входу коммутатора 10, выход которого подключен к информационному входу регистра 11 памяти, выход которого, являющийся выходом генератора, подключен к второму входу блока 9 сравнения, выход которого соединен с вторым входом коммутатора 10, третий вход которого подключен к шине 13 числа п. Выход сумматора 3 по модулю два объединен с информационным входом и-разрядного регистра 2 сдвига и подключен к третьему входу элемента 7 совпадения и синхронному входу 0-триггера 5, выход которого подключен к вторым входам элементов б и 7. Вход установки единицы 0-триггера 5 объединен с входом записи регистра 11 памяти и подключен к третьему выходу генератора 1 тактовых импульсов, соединенному через элеМент 12 задержки с входом сброса счетчика 8, 0-вход 0-триггера 5 соединен с общей шиной 4 питания.На Фиг.2 обозначены сигналы 14, 15,16 на втором, первом и третьем выходах генератора 1 соответственно, сигнал 17 на выходе триггера 5, сигнал 18 на выходе сумматора 3, сигнал 19 на тактовом входе регистра 2,сигЪал 20 на счетном входе счетчика 8. Устройство работает следующнм образом. Рассмотрим случай, когда регистр2 сдвига содержит 4 разряда (и = 4). Допустим, в исходном состоянии в регистре 2, счетчике 8 н регистре 11 записаны произвольные начальные условия, а триггер 5 выдает сигнал, запрещающий прохождение тактовых импульсов через элементы б и 7.Генератор 1 тактовых импульсбв предназначен для формирования цикловых импульсов, выдаваемых по третьему Выходу с периодом тц(см.16 ФИГ.2,и двух сдвинутых по Фазе импульсных последовательностей, выдаваемыХ попервому и второму выходам, причемимпульсы,выдаваемые по второму выходу (см.14 фиг,2), опережают по Фазе импульсы, выдаваемые по-его первому выходу (см.15 Фиг.2). В момент. поступления циклового импульса с генератора 1 на вход записи регистра11 в последний заносится код с выхода коммутатора 10, значение которого определяется выходным сигналомблока 9 сравнения, поступающим науправляющий вход коммутатора 10,т.е. соотношением кодов, записанных в виде начальных условий в счетчике 8 и регистре 11.Одновременно производится установка триггера 5 вединичное состояние см. 17 фиг.2), при которомпоследний выйдет сигнал, разрешающийпрохождение тактовых импульсов через элементы И 6 и 7 (см. 19,20фиг.2).Задержанным цикловым импульсом(задержка необходима для содержимо. го в регистр 11), снимаемым с элемента 12 задержки, осуществляетсясброс счетчика 8.С приходом тактового импульса содержимое регистра 2 сдвигается на 40 один разряд вправо, а в освободившу/юся ячейку записывается сигнал свыхода сумматора 3. При этом на выходе сумматора 3 формируется псевдослучайная последовательность двоичных символов.Для получения в регистре 2 псевдослучайной последовательности, имеющей максимально возможный (для данного и) период . = 2"- 1, необходимо, чтобы генераторный полином,определяющий структуру связей от выходов регистра 2 к входам сумматора3, был примитивным., В частности,при и = 4 на сумматор 3 подаются выходы первого и четвертого разрядов регистра 2.При этом каждый из формируемыхсимволов псевдослучайной последовательности удовлетворяет линейному-соотношению а= а (+) а -4, гдепорядковый номер символа, азнак (+)означает сложение по.моду 1 подва сигйалов с выходов первого ичетвертого разрядов регистра 2.Если исходное состояние регистра65 2(1,0,0,0), то на выходе сумматора3 формируется последовательность с периодом 1. = 2 - 1 = 15,11101110010001,Для удобства счета можно пронумеровать кажпый разряд двоичной последовательности соответствующим числом импульсов, поступающих на тактовый вход регистра 2 в каждом цикле работы генератора псевдослучайных чисел, соответствующем формированию одного числа , (см.19 фиг.2).11101, 01, 10010001,12345, 12, 1234,Когда в формируемом отрезке щ-последовательности проходит серия единиц( на выходе сумматора 3 сохраняетсявысокий потенциал, см, 18 фиг.2,сигнал с второго выхода генератора1 поступает через элемент 7 совпадения на счетный вход счетчика 8(см.20 на фиг,2),Из-за наличия временной задержкиимпульсных последовательностей напервом и втором выходах генератора 1(необходимой для исключения работысчетчика 8 в момент прохождения переходного процесса в сумматоре 3)первый импульс в каждом цикле работы устройства поступает на входсчетчика 8 до начала сдвига в регистре 2 ( т.е. раньше момента входарегистра 2 ). При этом в случае, еслипри поступлении первого в данном цикле работы устройства импульса на тактовый вход регистра 2 на выходе сумматора 3 устанавливается низкий потрициал, то в счетчике 8 оказываетсясформированным число, равное единице(см.фиг,2 А д -- 1),Как только в составе ш-последова"тельности появляестя нуль, элемент 7 совпадения закрывается низким потенциалом с выхода сумматора 3, врезультате чего прекращается поступление импульсов на счетчик 8.В момент перехода в формируемой в-последовательности от нуля к едини це положительным перепадом, поступаю щим с выхода сумматора 3 на синхровход Р-триггера 5, на выходе последнего устанавливается низкий потенциал (см,18 фиг.2), при этом прекращается поступление имппульсов на тактовый вход регистра 2, который фиксируется в состоянии, соответству ющем высокому потенциалу на выходе сумматора 3, а также на вход счетчика 8.В счетчике 8 оказывается сформиро ванным псевдослучайное число, соответствующее количеству единичных символов в генерируемом за цикл работы устройства отрезке щ-последова-. тельности (см.фиг.2 А = 4, А 1 = 1, А щ 2).:55 Дпя исключения повторения смежныхчисел в блоке 9 производится сравнение кода, записанного в счетчике 8,с кодом в регистре 11. В случае ихравенства коммутатор 10 переключается выходным сигналом блока 9 такимобразом, что на информационный входрегистра 11 поступает код с шины 13числа и(серии с числом единиц,равным п, в составе щ-последовательности отсутствуют). В противномслучае на выход коммутатора 10 поступает код, зафиксированный в счетчике 8.В начале следующего цикла работы генератора в момент поступленияциклового импульса с третьего выходагенератора 1 осуществляется записьчисла, подготовленного в предыдущемцикле работы генератора, в регистр11 и установка триггера 5 в единичноесостояние. Затем осуществляется сброссчетчика 8 и происходит формирование:очередного псевдослучайного числа,Описанный цикл работы генератораповторяется при формировании каждогонового цикла.Так как общее число единичных серий в периоде щ-последовательности,генерируемой п-разрядным регистром2и сдвига, составляет = 2 , а вкаждом цикле работы генератора про- (,изводится подсчет числа символов одной единичной серии, то предлагаи емое устройство за период 2формирует ряд псевдослучайных чисел, ограниченных по величине науровне и , так как максимальный размер единичной серии (число следующих друг за другом единиц) равен иПри этом в формируемой последовательности исключается повторение смежных чисел,Среднее количество тактов работырегистра сдвига, затрачиваемое наформирование одного числа, составляет при достаточно большой разрядности регистра сдвига (2"л 11 В товремя, как в известном устройстведля формирования числа требуетсяи тактов работы регистра сдвига.Таким образом, предлагаемый гене,ратор позволяет получить последовательность ограниченных по величиненезависимых псевдослучайных чисел снеповторяющимися смежными числами,в которой объем формируемого за период работы генератора числовогомассива в 4 раз больше, чем у извеситного генератора псевдослучайных чисел.Кроме того, предлагаемое устройство по сравнению с известным является более простым, так как отсутствует необходимость формирования пачек импульсов, обладает существеннолучшими массогабаритными характеристиками и является более надежным.Предлагаемое устройство также позволяет сократить стоимость и трудоемкость изготовления и регулировки, так как содержит меньшее по сравнению с известным устройством количес тво электрорадиоэлементов широкого- применения,Эффективность использования предлагаемого устройства возрастает при увеличении разрядности регистра сдвига, соответствующей максимальному значению формируемых псевдослучайных чисел.формула изобретенияГенератор псевдослучайных чисел, содержащий счетчик, коммутатор, сумматор по модулю два, первый и второй входы которого соединены соответственно с выходами регистра сдвига, информационный вход которого соединен с выходом сумматора по модулю два, генератор тактовых импульсов, первый выход которого соединен с управляющим входом регистрафпамяти, выход которого является выходом генератора, о т л и ч а ю щ и й с я тем, что, с целью повышения точности, он содержит П-трриггер, два элемента И, элемент задержки и блок сравнения, второй и третий выходы генератора тактовых импульсов соединены с первыми входами соответственно первого ивторого элементов И, выходы которыхсоединены соответственно с тактовыивходом регистра сдвига и счетным вхо 5 дсм счетчика, выход которого соединен с первым входом коммутатора ипервым входом блока сравнения, второй вход которого соединен с выходомрегистра памяти, а выход блока срав 1 О нения соединен с вторым входом коммутатора, третий вход которого является первым входом генератора, авыход коммутатора соединен с,информационным входом регистра памяти,15 управляющий вход которого объединенс установочным входом 0-триггера иподключен к входу элемента задержки,выход которого сбедйнен с входом"Сброс" счетчика, выход П-триггерасоединен с вторыми входами первого ивторого элементов И, выход сумматорапо модулю два соединен с третьим входом второго элемента И и с синхровходом Р-триггера, П-вход которого является вторым входом генератора.Источники информации,принятые во внимание при экспертизе1. Яковлев В.В., Федоров Р.ф,Стохастические вычислительные машины, Л., "Машиностроением, 1974,с.247-253.2, Там же, с.263-270,3; Авторское свидетельство СССРР 656086, кл.6 06 Е 1/02, 19779 б 2931 Составитель Л.Карасовактор Ю.Середа Техред С,МИгунова Корре Гриценк аказ 7513/68 Тираж 731 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж-З 5, Рауш