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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистичесних

Республик

<>962933 (61) Дополнительное к авт. свид-ву— (22) Заявлено 18. 02. 81(21) 3250533/18-24 с присоединением заявки ¹â€” (23) Приоритет—

Опубликовано 3009.82. Бюллетень ¹ 36

Дата опубликования описания 300982 (513 М.Кп з

С 06 F 7/58

Государственный комитет СССР по делам нзобретеннй н открытнй (53) УДК 681. 325 (088. В) (72) Авторы изобретения

В.A.Ìoëîòêoâ, Ю.С.Ицкович, М.H.Àðoíøòàì и Л.И.Тихомирова

" %С9НЗН и Р йА ЕНТИ913 „„„„,,„,„,13 йй1вАМОТЕкА (71) Заявитель (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Изобретение Ьтносится к вычислительной технике, в частности к устройствам для генерации произвольных чисел, и может быть использовано в системах автоматики. например для управления сменой. фиксированного числа значений йерестраиваемого параметра.

В аппаратуре дискретной автоматики и вычислительной технике широко используются генераторы псевдослучайных чисел, построенные на базе регистра сдвига, охваченного цепью обратной связи через сумматор по модулю два, в которых псевдослучайные числа образуются путем формирования псевдослучайной (имеющей детерминированную структуру) последовательностью двоичных символов максимального периода (m-последовательности) и использовании определенных символов этой последовательности в качестве значений разрядов псевдослучайного числа.

Известен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю два и в цепи обратной связи, генератор тактовых импульсов, счетчик по модулю

S и с выходных вентилей. В известном генераторе очередное двоичное число образуется на выходах с разрядов регистра сдвига через каждые тЯ > Й импульсов сдвига. Условие „Я)Р устраняет корреляцию смежных чисел формируемой выборки (1).

Недостатком известного генератора является сокращение длины выбор10 ки в $ раэ по сравнению с периодом

m-последовательности, генерируемой регистром сдвига, а также отсутствие воэможности ограничения величины формируемых чисел на уровне, соответствующем фиксированному числу значений перестраиваемого параметра системы автоматики, которое может бьжь отличным от 2 -1.

Ф

Другой известный генератор (2) псевдослучайных чисел, содержащий два одновременно тактйруемых регистра сдвига с сумматорами по модулю два в цепях обратной связи и группу сумматоров по модулю два на выходах сдвига с обратной связью и группы логических схем позволяет увеличить период следования генерируемой последовательности п-разрядных чисел, который равен (2"- 1) ° (2п -t), где

n(m — разрядности используемых регистров сдвига, 962931

О днако этот генератор не обеспечивает во можности ограничения формируемых чисел на уровне, определяемом фиксированным числом значений перестраиваемого параметра системы автоматики, и имеет сложное схемное 5 решение.

Наиболее близким к предлагаемому является генератор псевдослучайных чисел, содержащий основной и. дополнительный регистры сдвига, счетчик, сумматор по модулю два, коммутатор, делитель и генератор импульсов. Выход с основнсго регистра через до-полнительный регистр соединен с входом счетчика. Выходы разрядов осноВлого регистра в соответствии с коэфициентами генераторного полинома оединены с входами сумматора по модулю два, выход которого через коммутатор соединен с информационным входом основного регистра сдвига. Управ20 ляющий вход коммутатора через делитель с переменным коэффициентом деления соединен с вторым выходом генератора импульсов и тактовыми входами регистров сдвига. Выходы разрядов до-25 полнительного регистра соединены с, входами коммутатора. Первый выход генератора соединен с установочными входами делителя и счетчика.

На тактовый вход основного регис- 30 тра сдвига поступает пачка из n k импульсов, где k — разрядность. основного регистра сдвига. Первые m (m < n) тактов основной регистр .с сумматором по модулю два работает как генератор 35 бинарной псевдослучайной последовательности. Затем с выхода делителя выдается сигнал на коммутатор, который переключает выходы сумматора по модулю два и дополнительного регис- 40 тра таким образом, что оба регистра сдвига оставшиеся (n-m) тактов работают в режиме кольцевого регистра сдвига.

В результате на вход счетчика по- 45 ступает и символов и по окончании цикла работы генератора в счетчике формируется псевдослучайное число, равное числу единиц среди символов прошедшего отрезка последовательности.

Описанный цикл работы генератора повторяется для формирования каждого новоге числа . Псевдослучайные числа формируются из пересекающихся отрезков, чем достигается возможность изменения степени корреляции.

В частном случае m -= -n генерируются некоррелированные числа (3).

Недостатком известного генератора является сокращение емкости формиру- 60 емого (за период) числового массива некоррелированных чисел в М раз по сравнению с периодом последовательности, генерируемой регистром сдви. га. С другой стороны, в устройстве

65 возможны ситуации формирования подряд двух и более одинаковых- чисел, что нежелательно при использовании его для выработки перестраиваемого параметра систем автоматики, так как приводит к увеличению времени, в течение которого параметр не изменяется и, следовательно, к увеличению среднего времени корреляции параметра. Кроме того, известный

ГПСЧ достаточно сложен.

Цель изобретения — расширение объема формируемого числового массива и исключение повторения смежных чисел при одновременном упрощении генератора.

Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержащий счетчик, коммутатор, сумматор по модулю два, первый и второй выходы которого соединены соответственно с выходами регистра сдвига, информационный вход которого соединен с выходом сумматора по модулю два, генератор тактовых импульсов, первый выход которого соединен с управляющим входом регистра памяти, выход которого является выходом генератора, введены D-триггер,.два элемента И, элемент задержки и блок сравнения, второй и третий выходы генератора тактовых импульсов соединены с первыми входами соответственно первого и второго элементов И, выходы которых соединены соответственно с тактовым входом регистра сдвига и счетным входом счетчика, выход которого соединен с первым входом коммутатора и первым входом блока с авнения, второй вход которого соединен с выходом регистра памяти, а выход блока сравнения соединен с вторым входом коммутатора, третий вход которого является первым входом генератора, а выход коммутатора соединен с информационным входом регистра пат мяти, управляющий вход которого объединен с установочным входом D-триггера и подключен к входу элемента задержки, выход которого соединен с входом "Сброс" счетчика, выход

D-триггера соединен с вторыми входами первого и второго элементов

И, выход сумматора по модулю два соединен с третьим входом второго элемента И и синхровходом D-триггера, D-вход которого является вторым входом генератора.

Сущность изобретения заключается в формировании двоичного псевдослучайного числа подсчетом количества символов в единичной серии (ряд следующих друг за другом единиц)

m-последовательности, генерируемой и-разрядным регистром сдвига с сумматором по модулю два,и цепи обратной связи и замене сформированного таким образом числа числом, равным

962931

10 и-1 в случае равенства его предыдущему числу, что достигается введением в устройство D-. òðèããåðà, двух эле,ментов совпадения, элемента задержки, шины числа и-1 и блока сравнения соединенных соответствующими связями °

На фиг.1 дана структурная схема генератора псевдослучайных чисел; на фиг.2 - временные диаграммы, иллюстрирующие частный случай работы устройства.

Генератор содержит генератор 1 тактовых импульсов, регистр 2 сдвига, .сумматор 3 по модулю два, шину

4.питания, D-триггер 5, элементы

И 6 и 7, счетчик, 8, блок 9 сравнения, коммутатор 10, регистр 11 памяти, элемент 12 задержки, шину 13 ввода числа п-1.

Первый выход генератора 1 тактовых импульсов соединен с тактовым входом регистра 2 сдвига через элемент H.

Выходы разрядов регистра 2 сдвига в соответствии с коэффициентами генератора полинома соединены с входами сумматора 3 по модулю два. Второй выход генератора 1 тактовых импульсов связан со счетным входом счетчика 8 через элемент И 7. Выход счетчика 8 объединен с первым входом блока

9 сравнения, выполненного в виде схемы сравнения кодов, и подключен к первому входу коммутатора 10, выход которого подключен к информационному входу регистра 11 памяти, выход которого, являющийся выходом генератора, подключен к второму входу блока

9 сравнения, выход которого соединен с вторым входом коммутатора 10, третий вход которого подключен к шине

13 числа и-1. Выход сумматора 3 по модулю два объединен с информационным входом и-разрядного регистра 2 сдвига и подключен к третьему входу элемента 7 совпадения и синхронному входу D-триггера 5, выход которого подключен к вторым входам элементов

6 и 7. Вход установки единицы D-триггера 5 объединен с входом записи регистра 11 памяти и подключен к третьему выходу генератора 1 тактовых импульсов, соединенному через элемент 12 задержки с входом сброса счетчика 8. D-вход D-триггера 5 соединен с общей шиной 4 питания.

На фиг.2 обозначены сигналы 14, 15,16 на втором, первом и третьем выходах генератора 1 соответственно, сигнал 17 на выходе триггера 5, сигнал 18 на выходе сумматора 3, сигнал 19 на тактовом входе регистра 2, сигнал 20 на счетном входе счетчика 8.

Устройство работает следующим образом.

Рассмотрим случай, когда регистр

2 сдвига содержит 4 разряда (n = 4).

Допустим, в исходном состоянии в регистре 2, счетчике 8 н регистре 11 записаны произвольные начальные условия, а триггер 5 выдает сигнал, запрещающий прохождение тактовых импульсов через элементы 6 и 7.

Генератор 1 тактовых импульсбв предназначен для формирования цикловых импульсов, выдаваемых по третьему saaxo y c периодом T<(cM.16 фиг.2), и двух сдвинутых но фазе импульсных последовательностей, выдаваемыХ по первому и второму выходам, причем импульсы, выдаваемые по второму выходу (см.14 фиг.2), опережают по фазе импульсы, выдаваемые по-его первому выходу (см.15 фиг.2) . В момент . поступления циклового импульса с генератора 1 на вход записи регистра 11 в последний заносится код с выхода коммутатора 10, значение которого определяется выходным сигналом блока 9 сравнения, поступающим на управляющий вход коммутатора 10, т.е. соотношением кодов, записанных в виде начальных условий в счетчике 8 и регистре 11.

Одновременно производится установка триггера 5 в единичное состояние (см. 17 фиг.2), при котором последний выйдет сигнал, разрешающий прохождение тактовых импульсов через элементы И 6 и 7 (см. 19,20 фиг.2).

Задержанным цикловым импульсом (задержка необходима для содержимо35. го в регистр 11), снимаемым с элемента 12 задержки, осуществляется сброс счетчика 8.

С приходом тактового импульса содержимое регистра 2 сдвигается на

40 один разряд вправо, а в освободившу/ юся ячейку записывается сигнал с выхода сумматора 3. При этом на выходе сумматора 3 формируется псевдослучайная последовательность двоичных символов.

Для получения в регистре 2 псевдослучайной последовательности, имеющей максимально возможный (для данного n) период L = 2"- 1, необходи50 мо, чтобы генераторный полином, определяющий структуру связей от выходов регистра 2 к входам сумматора

3, был примитивным.

, В частности,при n = 4 на сумма55 тор 3 подаются выходы первого и четвертого разрядов регистра 2.

При этом каждый из формируемых символов псевдослучайной последовательности удовлетворяет линейному

-соотношению а „ = а „(+) а -4, где порядковый номер символа, а знак(+)означает сложение по модулю два сигйалов с выходов первого и четвертого разрядов регистра 2.

Если исходное состояние регистра

65 2(1,0,0,0), то на выходе сумматора

96?9 31

35 с

45 :55

3 формируется. последовательность с периодом 1. = 2 — 1 = 15...,11101

110010001,...

Для удобства счета можно пронумеровать кажпый разряд двоичной последовательности соответствующим числом импульсов, поступающих на тактовый вход регистра 2 в каждом цикле работы генератора псевдослучайных чисел, соответствующем формированию одного числа, (см.19 фиг.2).

11101, 01, 10010001,...

12345, 12, 1234,...

Когда в формируемом отрезке m-последовательности проходит серия единиц (на выходе сумматора 3 сохраняется высокий потенциал, см. 18 фиг.2, сигнал с второго выхода генератора

1 поступает через элемент 7 совпадения на счетный вход счетчика 8 (см.20 на фиг.2).

Из-за наличия временной задержки импульсных последовательностей на первом и втором выходах генератора 1 (необходимой для исключения работы счетчика 8 в момент прохождения переходного процесса в сумматоре 3) первый импульс в каждом цикле ра6оты устройства поступает на вход счетчика 8 до начала сдвига в регистре 2 (т.е. раньше момента входа регистра 2 ). При этом в случае, если при поступлении первого в данном цикле работы устройства импульса на тактовый вход регистра 2 на выходе сумматора 3 устанавливается низкий потен циал, то в счетчике 8 оказывается сформированным число, равное единице (см.фиг.2 А д — — 1) .

Как только в составе m-последова- тельности появляестя нуль, элемент7 совпадения закрывается низким потенциалом с выхода сумматора 3, в результате чего прекращается поступление импульсов на счетчик 8. В момент перехода в формируемой

m-последовательности от нуля к едини це положительным перепадом, поступаю щим с выхода сумматора 3 на синхровход D-триггера 5, на выходе последнего устанавливается низкий потенциал (см.18 фиг.2), при этом прекращается поступление имппульсов на тактовый вход регистра 2, который фиксируется в состоянии, соответству ющем высокому потенциалу на выходе сумматора 3, а также на вход счетчика 8.

В счетчике 8 оказывается сформиро ванным псевдослучайное число, соответствующее количеству единичных символов в генерируемом за цикл работы устройства отрезке m-последова-. тельности (cM.фиг.2 A„ = 4, A = 1, A3 = 2), Дпя исключения повторения смежных чисел в блоке 9 производится сравнение кода, записанного в счетчике 8, с кодом в регистре 11. В случае их равенства коммутатор 10 переключается выходным сигналом блока 9 таким образом, что на информационный вход регистра 11 поступает код с шины 13 числа и-1 (серии с числом единиц, равным п-1, в составе m-псгсхероаательности отсутствуют). В противном случае на выход коммутатора 10 поступает код, зафиксированный в счетчике 8.

В начале следующего цикла работы генератора в момент поступления циклового импульса с третьего выхода генератора 1 осуществляется запись числа, подготовленного в предыдущем цикле работы генератора, в регистр

11 и установка триггера 5 в единичное состояние. Затем осуществляется сброс счетчика 8 и происходит формирование: очередного псевдослучайного числа.

Описанный цикл работы генератора повторяется при формировании каждого нового цикла.

Так как общее число единичных серий в периоде m-последовательности, генерируемой п-разрядным регистром

2и 4 и-1 сдвига, составляет - - = 2, а в каждом цикле работы генератора про- (, изводится подсчет числа символов одной единичной серии, то предлагап-9. емое устройство за период 2 рмиоует ряд псевдослучайных чиел, ограниченных по величине на уровне и, так как максимальный размер единичной серии (число следующих друг за другом единиц) равен и

При этом в формируемой последовательности исключается повторение смежных чисел.

Среднее количество тактов работы регистра сдвига, затрачиваемое на формирование одного числа, составляет при достаточно большой разрядности регистра сдвига (2"л11 ° В то время, как в известном устройстве для формирования числа требуется и тактов работы регистра сдвига.

Таким образом, предлагаемый гене.ратор позволяет получить последовательность ограниченных по величине независимых псевдослучайных чисел с неповторяющимися смежными числами, в которой объем формируемого за период работы генератора числового массива в раз больше, чем у извеси тного генератора псевдослучайных чисел.

Кроме того, предлагаемое устройство по сравнению с известным является более простым, так как отсутствует необходимость формирования пачек импульсов, обладает существенно

962931

10 лУчшими массогабаритными характеристиками и является более надежным.

Предлагаемое устройство также позволяет сократить стоимость и трудоемкость изготовления и регулировки, так как содержит меньшее по сравнению с известным устройством количес

-тво электрорадиоэлементов широкогоприменения.

Эффективность использования предлагаемого устройства возрастает при увеличении разрядности регистра сдвига, соответствующей максимальному значению формируемых псевдослучайных чисел.

Формула изобретения

Генератор псевдослучайных чисел, содержащий счетчик, коммутатор, сумматор по модулю два, первый и второй входы которого соединены соответственно с выходами регистра сдвига, информационный вход которого соединен с выходом сумматора по модулю два, генератор тактовых импульсов, первый выход которого соединен с управляющим входом регистра памяти, выход которого является выходом генератора, отличающийся тем, что, с целью повышения точности, он содержит П-трриггер, два элемента И, элемент задержки и блок сравнения, второй и третий выходы генератора тактовых импульсов соединены с первыми входами соответственно первого и второго элементов И, выходы которых соединены соответственно с тактовыи входом регистра сдвига и счетным входом счетчика, выход которого соединен с первым входом коммутатора и первым входом блока сравнения, второй вход которого соединен с выходом регистра памяти, а выход блока сюав10 нения соединен с вторым входом коммутатора, третий вход которого является первым входом генератора, а выход коммутатора соединен с.информационным входом регистра памяти, 15 управляющий вход которого объединен с установочным входом D-триггера и подключен к входу элемента задержки, выход которого сбедйнен с входОм

"Сброс" счетчика, выход 9-триггера

2О соединен с вторыми входами первого и второго элементов И, выход сумматора по модулю два соединен с третьим входом второго элемента И и с синхровходом D-триггера, D-вход которого является вторым входом генератора.

Источники информации, принятые во внимание при экспертизе

1. Яковлев В.В., Федоров Р.Ф.

Стохастические вычислительные машины. Л., машиностроение", 19 74 с.247-253.

2. Там же, с.263-270.

3; Авторское свидетельство СССР

Р 656086, кл.G 06 F 1/02, 1977 (прототип).

9б2931 (Риг.2

Составитель A ° Kapacos

Редактор Ю.Середа Техред С.МИгунова Корректор A.Гриценко

Заказ 7513/68 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретения и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал IIIIII "Патент", г.ужгород, ул.Проектная,4