Генератор псевдослучайных чисел Советский патент 1982 года по МПК G06F7/58 

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

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

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

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

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

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

15 перестраиваемого параметра системл автоматики, которое может бьцгь отличным от 2 -1.

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

25 логических схем позволяет увеличить период следования генерируемой последовательности п-разрядных чисел, который равен () () , где - разрядности используемых реги30стров сдвига.

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

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

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

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

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

В частном случае m п генерируются некоррелированные числа З.

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

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

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

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

Сущность изобретения заключается в формировании двоичного псевдослучайного числа подсчетом количества символов в единичной серии (ряд следующих друг за другом единиц) т-последоватедьности, генерируемой п-раэрядным регистром сдвига с сумматором по модулю два,и цепи обратной связи и зг1мене сформированного таким образом числа числом, равным n-1 в случае равенства его предыдущ му числу, что достигается введением в устройство Dr-триггера, двух эле. ментов совпадения, элемента задержки, шины числа п-1 и блока сравнения соединенных соответствующими связями . На фиг,1 дана структурная схема генератора псевдослучайных чисел; на фиг.2 - временные диаграммы, иллюстрирующие частный случай работы устройства. Генератор содержит генератор 1 тактовых импульсов, регистр 2 сдвига, .сумматор 3 по модулю два, шину 4, питания, D-триггер 5, элементы И б и 7, счетчик,8, блок 9 сравнения коммутатор 10, регистр 11 памяти, элемент 12 задержки, шину 13 ввода числа п-1. Первый выход генератора 1 тактовы импульсов соединен с тактовым входом регистра 2 сдвига через элемент И. Выходы разрядов регистра 2 сдвига в соответствии с коэффициентами генератора полинома соединены с входами сумматора 3 по модулю два. Второй выход генератора 1 тактовых импульсов связан со счетным входом счетчика 8 через элемент И 7. Выход счетчи ка. 8 объединен с первым входом блока 9 сравнения, выполненного в виде схемы сравнения кодов, и подключен к первому входу коммутатора 10, выход которого под1 лючен к информационному входу реотистра 11 памяти, выход которого, являющийся выходом генератора, подключен к второму входу блока 9 сравнения, выход которого соединен с вторым входом коммутатора 10, третий вход которого подключен к шине 13 числа п-1. Выход сумматора 3 по модулю два объединен с информационным входом п-разрядного регистра 2 сдвига и подключен к третьему входу элемента 7 совпадения и синхронному входу D-триггера 5, выход которого подключен к вторым входам элементов б и 7. Вход установки единицы D-триг гера 5 объединен с входом записи регистра 11 памяти и подключен к третьему выходу генератора 1 тактовы импульсов, соединенному через 12 задержки с входом сброса счетчика 8. D-вход D-триггера 5 соединен с общей шиной 4 питания. На фиг.2 обозначены сигналы 14, 15,16 на втором, первом и третьем выходах генератора 1 соответственно сигнал 17 на выходе триггера 5, сиг нал 18 на выходе сумматора 3, сигнал 19 на тактовом входе регистра 2 сиЛёш 20 на счетном входе счетчика 8. Устройство работает следующим об разом. PaccMotpHM случай, когда регистр 2 сдвига содержит 4 разряда (п 4) Допустим, в исходном состоянии в регистре 2, счетчике 8 и регистре 11 записаны произвольные начальные условия, а триггер 5 выдает сигнал, запрещающий прохождение тактовых импульсов через элементы 6 и 7. Генератор 1 тактовых импульсов предназначен для форьлирования цикловых импульсов, выдаваемых по.третьему выходу с периодом Тц(см.1б фиг.2) и двух сдвинутых по фазе импульсных последовательностей, выдаваемых по первому и второму выходам, причем импульсы,выдаваемые по второму выходу С см. 14 фиг. 2), опережсшзт по фазе импульсы, выдаваемые по-его первому выходу (см.15 фиг.2). В момент поступления циклового импульса с генератора 1 на вход записи регистра 11 в последний заносится, код с выхода коммутатора 10, значение которого определяется выходным сигнсшом блока 9 сравнения, поступающим на управляющий вход коммутатора 10, т.е. соотношением кодов, записанных в виде начальных условий в счетчике 8 и регистре 11. Одновременно производится установка триггера 5 в(единичное состояние fcM. 17 фиг.2), при котором последний выйдет сигнал,разрешающий прохождение тактовых импульсов через элементы И 6 и 7 см. 19,20 фиг.2). Задержанным, цикловым импульсом (залермска необходима для содёрткимого в регистр 11), снимаемым с элемента 12 задержки, осуществляется сброс счетчика 8. С приходом тактового импульса содержимое регистра 2 сдвигается на один разряд вправо, а в освободившуюся ячейкузаписывается сигнал с выхода сумматора 3. При этом На выходе сумматора 3 формируется псевдослучайная последовательность двоичных символов. Для получения в регистре 2 псевдослучайной последовательности, имеющей максимально возможный (для даннрго п) период L 1, необходимо, чтобы генераторный полином, определяющий структуру связей от выходов регистра 2 к входам сумматора 3, был примитивным. iB частности,при п 4 на cyjMMaтор, 3 подаются выходы первого и четвертого разрядов регистра 2. При этом каждаай из формируемых символов псевдослучайной последовательности удовлетворяет линейному соотношению а , ® k - порядковый номер символа, а знак (+)означает сложение по.МОДУЛЮ два сигналов с выходов первого и четвертого разрядов регистра 2. Если исходное состояние регистра , 2(1,0,0,0), то на выходе сумматора 3 формируется последовательность с периодом L 15...,11101 110010001,... Для удобства счета можно пронумеровать каждый разряд двоичной последовательности соответствующим чи слом импульсов, поступающих на тактовый вход регистра 2 в каждом цикле работы генератора псевдослучайных чисел, соответствующем формированию одного числа , (см.19 фиг.2) 11101, 01, 10010001,... 12345, 12, 1234,.,. Когда в формируемом отрезке т-после дователькости проходит серия единиц С на выходе сумматора 3 сохраняется высокий потенциал, см. 18 фиг.2, сигнал с второго выхода генератора 1 поступает через элемент 7 совпаде ния на счетный вход счетчика 8 (см.20 на фиг.2).. Из-за наличия временной задержки импульсных последовательностей на. первом и втором выходах генератора (необходимой для исключения работы счетчика 8 в момент прохождения переходного процесса в сумматоре 3) первый импульс в каждом цикле работы устройства поступает на вход счетчика 8 до начала сдвига в регис тре 2 (т.е. раньше момента входа регистра 2 ), При этом в случае, есл при поступлении первого в данном ци ле работы устройства импульса на та товый вход регистра 2 на выходе сум матора 3 устанавливается низкий пот циал, то в счетчике 8 оказывается сформированным число, равное единиц (см.фиг.2 А 1 1) . Как только в составе т-последова тельности появляестя нуль, элемент7 совпадения закрывается низким потенциалом с выхода сумматора 3, в результате чего прекращается поступ ление импульсов на счетчик 8. В момент перехода в формируемой т-последовательности от нуля к един це положительным перепадом, поступа щим с выхода сумматора 3 на синхровход D-триггера 5, на выходе послед него устанавливается низкий потенци ал (см.18 фиг.2), при этом прекращается поступление имппульсов на тактовый вход регистра 2, который фиксируется в состоянии, соответств ющем высокому потенциалу на выходе сумматора 3, а также на вход счетчика 8. В счетчике 8 оказывается сформир ванным псевдослучайное число, соответствуклцее количеству единичных символов в генерируемом за цикл работы устройства отрезке т-последова тельности (см.фиг.2 А, 4, A«j 1 АЗ 2). Для исключения повторения смежных чисел в блоке 9 производится сравнение кода, записанного в счет1ике 8, с кодом в регистре 11. В случае их равенства коммутатор 10 переключается выходным сигналом блока 9 таким образом, что на информационный вход регистра 11 поступает код с шины 13 числа п-1 (серии с числом единиц, равным п-1, в составе т-по следовательности отсутствуют). В противном случае на выход коммутатора 10 поступает код, зафиксированный в счетчике 8. В начале следующего цикла работы генератора в момент поступления циклового импульса с третьего выхода генератора 1 осуществляется запись числа, подготовленного в предыдущем цикле работы генератора, в регистр 11 и установка триггера 5 в единичное состояние. Затем осуществляется сброс счетчика 8 и происходит формирование очередного псевдослучайного числа. Описанный цикл работы генератора повторяется при формировании каждого нового цикла. Так как общее число единичных серий в периоде т-последовательности, генерируемой п-разрядным регистром 2 сдвига, составляет каждом цикле работы генератора производится подсчет числа символов одной единичной, серии, то предлагаемое устройство за период рмирует ояп псевдослучайных чисел, ограниченных по величине на уровне п , так как максимальный размер единичной серии (число следующих друг за другом единиц) равен п . При ЭТОМ в формируемой последовательности исключается повторение смежных чисел. Среднее количество тактов работы регистра сдвига, затрачиваемое на формирование одного числа, составляет при достаточно большой разрядности регистра сдвига ( В то время, как в известном устройстве для формирования числа требуется п тактов работы регистра сдвига. Таким образом, предлагаемый генератор позволяет получить последовательность ограниченных по величине , независимых псевдослучайных чисел с неповторяющимися смежными числами, в которой объем формируемого за период работы генератора числового массива в -т раз больше, чем у известного генератора псевдослучайных чисел. Кроме того, предлагаемое устройство по сравнению с известнь М является более простым, так как отсутствует необходимость формирования пачек импульсов, обладает существенно 1

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

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

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

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

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

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

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

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

5

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

1.Яковлев В.В., Федоров Р.Ф. Стохастические вычислительные машины. Л., Мсшшностроение, 1974,

0, с.247-253.

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

3; Авторское свидетельство СССР 656086, кл.С 06 F 1/02, 1977 (прототип).