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

 

Изобретение относится к вычислительной технике. Цель изобретения - повышение точности задания вероятности появления единичных символов в формируемой последовательности . Генератор содержит регистр сдвига 1, генератор тактовых импульсов 2, счетчик 3, элементы И 4 и 5. формирователь импульса 6, блок ключей 7, делитель частоты 8, сумматор по модулю два 11, кольцевые регистры 12, мультиплексор 10 1 ил , 1 табл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я) 5 G 06 F 7/58

ГОСУДАРСТВЕ ННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

))Ю

)ф

1С

О

ЬЭ й

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4813090/24 (22) 10.04.90 (46) 15.05.92. Бюл. М 18 (71) Гродненский государственный университет (72) В.Н. Сюрин, Н.А. Колодинская и

И.С, Федкевич (53) 681.3(088.8) (56) Авторское свидетельство СССР

N 917316, кл. Н 03 К 3/84, 1979, „„Ы) „„1734092 А1 (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике. Цель изобретения — повышение точности задания вероятности появления единичных символов в формируемой последовательности, Генератор содержит регистр сдвига 1, генератор тактовых импульсов 2, счетчик 3, злементы И 4 и 5, формирователь импульса 6, блок ключей 7, делитель частоты

8, сумматор по модулю два 11, кольцевые регистры 12, мультиплексор 10, 1 ил„1 табл.

1734092

10

3О

50

Изобретение относится к вычислительной технике и связи и может быть использовэ:-;с для тестирования цифровыхэлектронных блоков, вероятностно-статистических испытаний систем для статистического моделироBàния и для формирования псевдослучайных сигналов, Цель изо" ðåòåíèÿ — повышение точности задания вероятности появления единичных символов в формируемой последовательностии.

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

Генератор содержит регистр сдвига с обратной связью 1, генератор 2 тактовых импульсов, счетчик 3, элементы И 4 и 5, формирователь 6 импульса . блок 7 ключей, делитель 8 частоты, N каналов 9 формирования, каждый канал 9 формирования содержит мультиплексор 10, сумматор 11 по модулю два, два кольцевых регистра 12 и входы 13 установки вероятностей.

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

01110 I 00

00111010, длина которых, выраженная числом элементов, определяется в общем случае как

2, где m — число ячеек регистра 1 сдвига с обратной связью, В данном случае m = 3 и длина периода выходных последовательностей регистра 1 составит восемь двоичных элементов, Первая из последовательностей, вероятность появления единичных символов в которой равна 1/2. подается непосредственно на первый информационный вход мультиплексора 10. Вторая и третья последовательности с выходов регистра 1 сдвига подаются на соответствующие входы элемента И 5, где производится логическое умножение этих последовательностей, На выходе элемента И 5 появится последовательность вида 00110000 с вероятностью появления единичных символов, равной 1/4, Эта последовательнс сть подается на второй информационный вход мультиплексора 10, а также на второй ход элемента И 4, на первый вход которой подается последовательность с первого разрядного выхода регистра 1 сдвига. В результате логического умножения элементов этих последовательностей на выходе элемента И 4 получим результирующую последовательность

1 1 101000 00«ОООО

00100000, вероятность появления единичных символов в которой равна 1/8. Эта последовательность подается на третий информационный вход мультиплексора 10. Таким образом, на информационных входах мультиплексора

10 имеется совокупность базисных последовательностей с вероятностями появления единичных символов P = (0,5) . i =- 1, 2. 3.

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

Эти импульсы поступают также на вход делителя 8, коэффициент деления которого выбирается равным 2 (коэффициент деления равен 8), Через каждые восемь тактов на выходе делителя 8 появляется единичный сигнал, который изменяет на единицу состояние счетчика 3, емкость которого также равна 2m. От заднего фронта этого же сигнала запускается формирователь 6 импульса, постоянная времени которого выбирается примерно равной 1.5,. где tTi — период следования тактовых импульсов.

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

1 сдвига с обратной связью устанавливается лог ."1". Состояние управляющих входов So и S1 регистра 1 сдвига с обратной связью принимает значение 11, т.е. регистр переключается в положение параллельной записи информации по входам D>. 02 и Оз. Это приводит к тому, что при поступлении следующего тактового импульса на вход С регистра 1 сдвига с обратной связью через открытый блок 7 ключей новое состояние счетчика 3 переписывается в ячейки регистра 1 сдвига с обратной связью. 1ак что на каждом периоде базисных последовательностей меняется начальное состояние регистра 1 сдвига, что приводит к изменению расположения единичных символов в базисных последовательностях от периода к периоду, но вероятность появления единичных символов в них остается неизменной, После перезаписи формирователь 6 импул ьсов возвращается в исходное состояние. на входах So и S1 регистра 1 сдвига с обратной связью устанавливается комбинация 01. т.е. он переключается в режим сдвига и все последующие на периоде базисных последовательностей тактовые импульсы будут производить сдвиг информации в регистре

1734092

1 сдвига с обратной связью. Из сформированныхтаким образом базисных последовательностей с фиксированной вероятностью появления единичных символов может быть создана результирующая последовательность с произвольным, наперед заданным значением вероятности появления единичных символов, Это осуществляется с помощью независимых каналов 9 формирования, в которых производится временное мультиплек.сирование базисных последовательностей посредством мультиплексора 10 по программе, предварительно запи, анной по входам 13 в кольцевые регистры 12, Пусть каждый кольцевой регистр 12 имеет по четыре двоичных разряда, старшие разряды этих регистров связаны с соответствующими управляющими входами мультиплексора 10 и система адресации приведена в табл:дце.

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

Верхний регистр — 0 v 1 1

Нижний регистр, „1 0 0 1

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

В течение первых восьми тактов на управляющие входы мультиплексора 10 поступает код 1, на этом интервале к выходу мультиплексора 10 подключается трегий информационный вход и через сумматор 11 по модулю два, на втором входе которого присутствует нулевой сигнал. на выход канала 9 выдается базисная последовательность с вероятностью появления единичного символа, равной 1/8, По истечении восьми тактов сигналом с выхода счетчика 3 производится циклический сдвиг содержимого регистров

12 и на управляющие входы мультиплексора

10 будет подаваться следующий код (1) . что соответствует подключению к выходу мульплексора 10 первого информационного входа и выдаче на выход канала 9 формирования базисной последовательности с Р. = 1/2. Далее в соответствии с адресными кодами выдаются базисные последовательности с P = О и с Р; = 1/4, Тогда результирующая вероятность на четырех периодах различных базисных последовател ьн остей будет равна 7/32, т. е, она может быть задана с точностью до 1/32, В общем случае результирующая вероятность определяется по формуле: (р)

=1 р J i=1, m, % и где и — число разрядов в регистрах 12, Таким образом, можно задать вероятности от О до 0,5, Значения результирующей вероятности большей 0,5 задаются путем подачи единичного сигнала по входу 13 сумматора 11 по модулю два. При совокупности ранее рассмотренных кодов в данном случае на выход канала 9 формирования будет поступать инвертированная с помощью сумматора 11 по модулю два результирующая последовательность. Суммарная веро15 ятность появления единичных символов в ней до инвертирования равнялась 7/32. тогда после инвертирования эта вероятность будет равна дополнению до единицы, т,е. P = (1 - 7/32) = 25/32.

,$c

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

45 вероятности Р . При достаточном числе вре2 менных позиций и, на которых размещаются базисные последовательности. можно получить практически любой закон распределения единичных символов в результирующей последовательности. Для рассмотренного выше примера (n = 4) результирующая последовательность с вероятностью P = 4/32 можно получить, располагая базисные последовательности с соответствующими вероятностями Р; на четырех позициях как 1/2. О. О.

О и как 1/8, 1/8, 1/8, 1/8. B первом случае единичные символы группируются. во втором распределены по всему периоду результирующей последовательности, 1734092

1 начение !

1/2

1/4

1/8

Составитель B.Îðëîâ

Техред М,Моргентал

Корректор M,Màêñèìèøèíeö

Редактор А.Долинич

Заказ 1670 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

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

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

10 соединен с первым входом первого элемента И и с одноименными информационными входами мультиплексоров каналов формирования второй разрядный выход регистра сдвига с обратной связью соединен с первым

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