Генератор псевдослучайных чисел Советский патент 1979 года по МПК G07C15/00 G06F1/02 

(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

I

Изобретение относится к области вычислительной техники и может быть испрльзовано при построении специализированных вычислительных машин.

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

Однако этот генератор обладает малой длиной псевдослучайной последовательности.

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

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

Целью изобретения является повышение точности генератора.

Для достижения поставленной цели генератор содержит первый и второй блоки памяти, первь1е,вторь1еитретьи входы которых, соединены, с первым, вторым и третьим выходами блока управления соответственно, четвертые входы блоков памяти - с выходами первого и второго элементов эквивалентности соответственно, первые и вторые выходы - с первыми и вторымн входами первого и второго элементов эквивалентности соответственно, группы выходов блока

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

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

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

Генератор содержит первый блок памяти 1, состоящий из накопителя 2 с произвольной адресацией, буферного регистра 3, счетчика 4 и дещифратора 5; блок управления 6; второй блок памяти 7; блок 8 сумматоров по mod 2 и два элемепт-а 9 и 10 эквивалентности. Блок 7 состоит из накопителя 11 с произвольной адресацией, буферного регистра 12, счетчика 13 и дешифратора 14.

Накопитель 2 содержит m ячеекдля хранелия m п-разрядных чисел, а накопите чь 11 - t ячеек для хранения Е п-разрядных чисел, причем m и - взаимно простые. Выходные разрядные шины накопителя 2 подключены ко входам регистра 3, а выходные разрядные шины накопителя 11 - ко входам регистра 12. Выходы регистров 3 и 12 попарно подключены ко входам соответствующих сумматоров по mod 2 блока 8. Выход регистра 3 подключен также ко

входным разрядным щинам накопителя П. Выходы сумматоров по mod 2 блока 8 подключены ко входным разрядным шинам накопителя 2 и к выходам 15 генератора, m адресных щин накопителя 2 подключены к выходам дешифратора 5, ко входам которого подключены выходы счетчика 4 с модулем пересчета т, а t адресных шин накопителя 11 подключены к выходам дешифратора 14, ко входам которого подключены выходы счетчика 13 с модулем пересчета 1. Счетные входы счетчиков 4 и 13, а также шины СЗ («Считывание-Запись) накопителей 2 и 11 подключены к выходной щине

РЙ («Рабочие импульсы) блока управления 6, выходная шина которого Уст «О подключена к щинам сброса счетчиков 4, 13 и регистров 3, 12. Кроме того, выходная шина СИ («Сдвигающие импульсы) блока управления 6 подключена к шине сдвига регистров 3 и 12. Выходы п-го и k-oro разрядов (п и k взаимно простые числа) регистра 3 подключены ко входам элемента эквивалентности 9, выход которого подключен к последовательному входу первого разряда этого же регистра. Выходы п-го и (n-k)-oro разрядов регистра 12 подключе-, ны ко входам элемента эквивалентности 10, йыход которого подключен к последбвательному входу первого разряда этого же реГИСТра. :.-::. . ;:.../ ,.-.,...... .,..;.,.. :

Устройство имеет два основных режима: начальный режим формирования псевдослучайной информации и рабочий режим - режим формирования и выдачи п-разрядных псевдослучайных чисел.

Режимы работы задаются соответствующими сигналами с выходов блока управления 6 ,(см. фиг. 2).

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

В начальном режиме блок управления б в первом такте вырабатывает сигнал Уст«О (фиг. 2 а), который устанавливает в нулевое состояние счетчики адресов 4 и 13 и регистры 3 и 12, начиная со второго

такта блок 6 вырабатывает рабочие импульсы РИ (фиг. 26), поступа(рщие на счетные входы счетчиков 4 и 13, на шины СЗ («Считывание-3апись«) накопителей 2 и 11, на входь синхронизации триггеров регистров 3 и 12. Для управления работой регистров 3 и 12 блок 6вырабатывает потенциальный сигналсдвига ПС (фиг. 2 в). При наличии сигнала ПС и поступлении импульсов РИ регистры 3 и 12 работают в режиме сдвига записанной информации в сторону старших разрядов. Кроме того, сигнал ПС запрещает запись в регистры 3 и 12 информации, присутствующей на выходных разрядных шинах при считывании из накопителей 2 и 11. С другой стороны сигнал ПС разрешает запись сигналов, посту .нающих на последовательные входы первых разрядных регистров 3 и 12 с выходов элементов эквивалентности 9 и 10. Таким образом, в начальном режиме регистр 3 и элемент 9, а также регистр 12 и элемент 10

5 представляют собой два генератора псевдослучайных последовательностей, которые формируют одинаковые последовательности, но с противоположными порядками следования двоичных символов в последовательностях. В известном генераторе на основе АЛПМ нулевое состояние регистра является запрещенным (выйти из него без внешнего сигнала АЛПМ не может). В рассматриваемом устройстве для генераторов псевдослучайных последовательностей На регистS pax 3, 12 и элементах 9, 10 нулевые состояния регистров являются рабочими, что достигается включением в цепи обратных связей элементов эквивалентности вместо сумматоров по mod 2.

Работа генератора в начальном режиме происходит следующим образом.

С одной стороны, импульсы РИ и потенциал ПС, поступая на регистры 3 и 12, . приводят к тому, что последние совместно 5 с элементами формируют псевдослучайные последовательности. С другой стороны, рабочие импульсы РИ, поступая на счетные входы счетчиков 4 и 13, в каждом такте увеличивают на единицу номера адресов, по которым происходит обращение к накопителям 2 и 11. Кроме того, положительные импульсы сигнала РИ, поступающие на шины СЗ («Считывание-Запись), в первой половине каждого такта воспринимаются накопителями 2 и 11, как сигнал «Считывание числа по выбранному адресу. Пауза .сигнала РИ на шинах СЗ во второй половине каждого такта воспринимается накопителями 2 и 11, как сигнал «Запись числа по выбранному адресу. Таким образом, в каждом из накопителей в одном такте вначале считывается число, хранящееся в выбранной ячейке памяти, а затем по этому же адресу записывается число, поступающее на входные разрядные шины соответствующего накопителя. Как уже. отмечалось, сигналы, возникающие на входных разрядных шинах накопителей 2 и И, не записываются на регистры 3 и 12, поскольку параллельные входы последних блокируются сигналом ПС.

В каждом такте во второй половине такта псевдослучайное число, присутствующее в регистре 3, записывается в вы&ранную ячейку накопителя 11. Это же число поразрядно складывается на блоке сумматоров 8 с псевдослучайным числом, присутствующим в этом такте в регистре 12. С выходов блока 8 результат поразрядного сложения записывается в выбранную ячейку накопителя 2. По истечении m тактов (в предложении, что m t) во всех ячейках накопителей 2 и 11 будут записаны некоторые псевдослучайные числа. Следует отметить, что в ячейках накопителя 11 будут все разные числа. В k первых ячейках (если k -) накопителя 2 при m п после m тактов будут записаны нули, а в остальных - псевдослучайные числа, отличные от чисел, записанных в накопителе П. Во избежание наличия большого числа «нулей значение номера разряда k регистра 3, с выхода которого заводится обратная связь на элементы 9, необходимо выбирать достаточно малым, порядка 2-4. При этом псевдослучайные последовательности, формируемые регистрами 3,. 12 и элементами 9, 10 могут получиться не максимальными. Однако в этом нет никакой необходимости, поскольку емкость наксгпителей 2 и 11 (число ячеек памяти) намного меньше числа символов в последовательности максимальной длины, т. е. m « 2 1; « . Можно выбрать k и достаточно большим k (если этого требует условие генерации последователькости длины I). Во избежание записи большого количества нулевых чисел в накопителе 2 потенциальный сигнал ПС необходимо формировать длительностью в 2 тактов. Время, существования сигнала ПС можно выбрать необязательно кратным m тактам. В общем случае можно указать, что

длительность сигнала ПС должна удовлетворять неравенству , где Три- период следования рабочих импульсов.

По окончании начального режима (окончание сигнала ПС) регистры 3 и 12 переключаются в режимы статического хранения информации с записью и выдачей чисел параллельными кодами. В отсутствие потенциала ПС сигналы с выходов элементов эквивалентности 9 и 10 не воспринимаются первыми разрядами регистров 3 и 12.

После окончания ПС блок управления выдает второй сигнал Уст«0, осуществляющий сброс счетчиков 4, 13 и регистров 3 и 12 (фиг. 26). Со следующего такта начинается рабочий режим формирования п-разрядных псевдослучайных чисел.

В рабочем режи.ме генератор работает следующим образом. В первом такте импульс РИ, поступающий на счетные входы счетчиков 4 и 13, устанавливает последние в состояние 1. Дешифраторы адресов 5 и 14 возбуждают адресные шиньг ячеек соответствующих накопителей 2 и 11. При этом единичный уровень РИ в первой половине такта, поступая на пгииы СЗ накопителей 2 и 11, осуществляет считывание чисел, хранящихся в первых ячейках накопителей 2 и 11. Сигналы, соответствующие разрядам считанных чисел, появляются на выходных разрядных шинах накопителей 2 н 1. Под воздействием этих сигналов и сиг;1ала РИ на щинах синхронизации считанные-из накопителей 2 и 11 числа запис.ьшаются соответственно на регистры 3 и 12. С выходов регистра 3 считанное из первой ячейки накопителя 2 число поступает на выходные разрядные шины накопителя 11 и на одни входы блока 8. На вторые входы блока 8 поступают разряды числа, считанного из первой ячейки накопителя 11 и хранящегося на регистре 12. В итоге на выходах блока 8 (блок сумматоров по mod 2) появляется число, представляющее поразрядную сумму входных чисел. Эта поразрядная сумма является первым псевдослучайным числом, которое поступает на выходы генератора 15 и на выходные разрядные шины накопителя 2.

Во второй половине первого такта нулевой уровень сигнала РЙ, поступая на шины СЗ накопителей 2 и 11, осуществляет запись чисел, присутствующих на входных разрядных щинах в первые ячейки накопителей 2 и 11, т. е. в первую ячейку накопителя 2 записывается первая поразрядная сумма, а в первую ячейку накопителя 11 записьГвается число, хранящееся на регистре 3.

Во втором такте сигнал РИ устанавливает счетчики 4, 13 в состояние 2. Дешифраторы 5 и Г4 возбуждают адресные шины вторых ячеек накопителей 2 и 11. В результате в первой половине второго такта произойдет считывание чисел со вторых ячеек накопителей 2 и 11 на регистры 3 и 12. Кроме того, сумматорами по mOd 2 блока 8 осуществляется поразрядное сложение чисел, записанных на регистрах 3 и 12. В итоге образуется второе псевдослучайное число, поступающее на выходы 15 и на входные разрядные шины накопителя 2. Во второй половине такта это число записывается во вторую ячейку накопителя 2. Во вторую ячейку накопителя 11 записывается число, хранящееся на регистре 3. В дальнейшем с поступлением каждого импульса РИ последовательно изменяются состояния счетчиков 4 и 13 и, следовательно, осуществляется последовательное обращение к ячейкам накопителей 2 и 11. При этом в первой полосе такта осуществляется считывание чисел из выбранных ячеек накопителей 2 к И с записью на регистры 3 и 12 и поразрядное сложение этих чисел в блоке 8, а во второй половине - запись поразрядной суммы в выбранную ячейку накопителя 2 и числа, хранящегося на регистре 3, в выбранную ячейку накопителя 11. ---В силу .того, что счетчик 13 имеет модуль пересчета t, в (-ом такте он окажется в нулевом состоянии, в результате дешифратор 14 выберет последнюю С-ую ячейку накопителя 11. В остальном генератор будет работать также, как и в предыдущих случаях. В (Е-Ь 1)-ом такте счетчик 4 устанавливается в (.+ 1)-ое состояние и осуществляет(я обращение к (Е+ 1)-ой ячейке накопителя 2. Счетчик 13 устанавливается в первое состояние и, следовательно, обращение осуществляется к первой ячейке наконителя 11. В результате поразрядного сложения чисел из этих ячеек на выходе блока 8, образуется (С+ 1)-ое псевдослучайное число. ,,которое выдается на выход 15 и записыва ,р . ,, „ о „ ется в (-f 1)-ую ячейку накопителя 2. Число, выбраЕжое из (t+ 1)-ой ячейки этого блока , записывается также в первую ячейку накопителя 11. Поскольку счетчик 4 имеет модуль пересчета щ, то в гп-ом такте он окажется в нулевом состоянии. Дешифратор 5 выберет последнюю гп-ую ячейку накопителя 2. В остальном генератор будет работать также, как и в предыдущих случаях. В (т + 1)-ом такте счетчик устанавливается в первое состояние и обращение осуществляется к первой ячейке накопителя 2. Счетчик 13 установится в состояние R - -целочисленный остаток от деления (ш + 1) на С. В результате поразрядного сложения выбранных псевдослучайных чисел образуется (гп + 1) ое псевдослучайное число, которое выдается на выход 15 и записывается в первую ячейку накопителя 2. Кроме того, выбранное в первой половине этого такта псевдослучайное число из первой ячейки накопителя 2 записывается в ячейку накопителя 11. Дальнейщий процесс формирования псевдослучайных чисел очевиден. В общей сложности генератор сформирует и выдаст на выход 15 ( 1) псевдослучайных неповторяющихся чисел. После (2™ --1) тактов в ячейках накопителей 2 и II окажется зафиксированной та информация, которая была записана в них в начальном режиме, а счетчики 4 II 13 установятся в нулевые состояния. С ()-го такта начнется второп период работы генерятора, в точении которо го генератор будет выдавать те же 1севдослучайные числа и в той же последовательности, что и в первом периоде. Формула изобретения 1. Генератор псевдослучайных чисел, содержащий блок управления, первый и второй элементы эквивалентности, блок сумматоров по модулю два, выходы которого явля-. ются выходами генератора, отличающийся тем, что, с целью повышения точности генератора, он содержит первый и второй блоки памяти, первые, вторые и третьи входы которых соединены с первым, вторым и третьим выходами блока управления соответственно, четвертые входы блоков памяти - с выхода.ми первого и второго элементов эквива лентности соответственно, первые и вторые выходы - с первыми и вторыми входами первого и второго элементов эквивалентности соответственно, группы выходов блока Памяти соединены со входами блока сумматоров по модулю два соответственно, выходы которого подключены к группе входов первого блока памяти соответственно, груп . р./ па вы.чодов которого подключена к группе « входов второго блока памяти соответственно. 2. Генератор псевдослучайных чисел по п. 1, отличающийся тем, что каждый блок памяти содержит счетчик, дещифратор, накопитель и буферный регистр, разрядные выходы которого являются группой выходов блока, i-ый и j-ый выходы - nepBbfM и вторым выходами блока, первый вход объединен с первыми входами накопителя и счетчика и является первым входом блока, второй вход объединен со вторым входом счетчика и является вторым входом блока, третий и четвертый входы являются третьим и четвертым входами блока, а разрядные входы соединены с разрядными выходами накопителя соответственно, разрядные входы которого являются группой входов блока, а второй вход соединен через дешифратор с выходом счетчика.

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

L .ТТГ- - L

Фиг. / Уст„0 ) « ППП-- р л.г

ПП п п п