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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 734092 А 1 9) 1)5 О 06 Р САНИЕ ИЗОБРЕТЕНИЯ СВИДЕТЕЛЬСТВ ТОРС)ЮфС ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР(71) Гродненский государственный университет(56) Авторское свидетельство СССРВ 917316, кл. Н 03 К 3/84, 1979,(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНОЙ ПОСЛЕДОфАТЕЛЪНОСТИ ЧИСЕЛ(57) Изобретение относится к вычислительной технике. Цель изобретения - повышение точности задания вероятности появления единичных символов в формируемой последовательности, Генератор содержит регистр сдвига 1, генератор тактовых импульсов 2, счетчик 3, злементы И 4 и 5, формирователь импульса б, блок ключей 7, делитель частоты 8, сумматор по модулю два 11, кольцевые регистры 12, мультиплексор 10, 1 ил 1 табл.Изооретение относится к вычислительной технике и связи и может быть использовано для тестирования цифровыхэлектронных блоков, вероятностно-статистических испытаний систем для статистического моделирования и для формирования псевдослучайных сигналов.Цель изобретения - повышение точности задания вероятности появления единичных символов в формируемой последовательности.На чертеже приведена структурная электрическая схема генератора.Генератор содержит регистр сдвига с обратной связью 1, генератор 2 тактовых импульсов, счетчик 3, элементы И 4 и 5, формирователь 6 импульса, блок 7 ключей, делитель 8 частоты, И каналов 9 формирования, каждый канал 9 формирования содержит мультиплексор 10, сумматор 11 по модулю два, два кольцевых регистра 12 и входы 13 установки вероятностей,Генератор работает следующим образом,В регистре сдвига 1 с обратной связью формируется нелинейная псевдослучайная последовательность. Используется трех- разрядный регистр 1 сдвига с обратной связью, формирующий на трех своих выходах циклически сдвинутые на один такт нелинейные последовательности вида111010000111010000111010,длина которых, выраженная числом элементов, определяется в общем случае как 2, где гп - число ячеек регистра 1 сдвига с обратной связью, В данном случае е = 3 и длина периода выходных последовательностей регистра 1 составит восемь двоичных элементов, Первая из последовательностей, вероятность появления единичных символов в которой равна 1/2, подается непосредственно на первый информационный вход мультиплексора 10. Вторая и третья последовательности с выходов регистра 1 сдвига подаются на соответствующие входы элемента И 5, где производится логическое умножение этих последовательностей, На выходе элемента И 5 появится последовательность вида 00110000 с вероятностью появления единичных символов, равной 1/4, Эта последовательнс сть подается на второй информационный вход мультиплексора 10, а также на второй зход элемента И 4, на первый вход которой подается последовательность с первого разрядного выхода регистра 1 сдвига, В результате логического умножения элементов этих последователь 10 ностей на выходе элемента И 4 получимрезультирующую последовательность111010000011 ОООО00100000,вероятность появления единичных символов в которой равна 1/8, Эта последовательность подается на третий информационный вход мультиплексора 10, Таким образом, на информационных входах мультиплексора10 имеется совокупность базисных последовательностей с вероятностями появленияединичных символов Р 1 = (0,5).=- 1, 2. 3, Нелинейная псевдослучайная последовательность вырабатывается в регистре 1 сдвига под воздействием тактовых импульсов, поступающих на его тактовый вход С с выхода генератора 2 тактовых импульсов, Эти импульсы поступают также на вход делителя 8, коэффициент деления которого выбирается равным 2 (коэффициент деления равен 8), Через каждые восемь тактов на выходе делителя 8 появляется единичный сигнал, который изменяет на единицу состояние счетчика 3, емкость которого также равна 2, От заднего фронта этого же сигнала запускается формирователь 6 импульса, постоянная времени которого выбирается примерно равной 1.5 ьи. где стив период следования тактовых импульсов. Сигналом с выхода формирователя 6 импульса открывается по управляющему входу блок 7 ключей и на входе записи Я регистра 1 сдвига с обратной связью устанавливается лог."1". Состояние управляющих входов Яо и Я 1 регистра 1 сдвига с обратной связью принимает значение 11, т.е, регистр переключается в положение параллельной записи информации по входам 01. 02 и 0 з. Это приводит к тому, что при поступлении следующего тактового импульса на вход С регистра 1 сдвига с обратной связью через открытый блок 7 ключей новое состояние счетчика 3 переписывается в ячейки регист 20 25 30 35 40 ра 1 сдвига с обратной связью. 1 ак что на каждом периоде базисных последовательностей меняется начальное состояние регистра 1 сдвига, что приводит к изменению расположения единичных символов в ба 45 50 зисных последовательностях от периода к периоду, но вероятность появления единичных символов в них остается неизменной, После перезаписи формирователь 6 импульсов возвращается в исходное состояние. на 55 входах Яо и 51 регистра 1 сдвига с обратнойсвязью устанавливается комбинация 01. т,е, он переключается в режим сдвига и все последующие на периоде базисных последовательностей тактовые импульсы будут производить сдвиг информации в регистре1 сдвига с обратной связью. Из сформированныхтаким образом базисных последовательностей с фиксированной вероятностью появления единичных символов может быть создана результирующая последовательность с произвольным, наперед заданным значением вероятности появления единичных символов, Это осуществляется с помощью независимых каналов 9 формирования, в которых производится временное мультиплек.сирование базисных последовательностей посредством мультиплексора 10 по программе, предварительно запи, анной по входам 13 в кольцевые регистры 12, Пусть каждый кольцевой регистр 12 имеет по четыре двоичных разряда, старшие разряды этих регистров связаны с соответствующими управляющими входами мультиплексора 10 и система адресации приведена в таблице.При этом на четвертый информационный вход мультиплексора 10 подается постоянный нулевой сигнал, Предположим, что в кольцевых регистрах 12 была записана последовательность адресных кодовВерхний регистр -0 о 1 1 Нижний регистр,. 1 0 О 1 Эти коды циклически сдвигаются под действием сигнала, поступающего с выхода делителя 8, т.е, через каждые восемь тактов. В течение первых восьми тактов на управляющие входы мультиплексора 10 поступает код 1, на этом интервале к выходумультиплексора 10 подключается трегий информационный вход и через сумматор 11 по модулю два, на втором входе которого присутствует нулевой сигнал, на выход канала 9 выдается базисная последовательность с вероятностью появления единичного символа, равной 1/8, По истечении восьми тактов сигналом с выхода счетчика 3 производится циклический сдвиг содержимого регистров 12 и на управляющие входы мультиплексора 10 будет лодаеатксл следующий код 1 . что соответствует подключению к выходу мульплексора 10 первого информационного входа и выдаче на выход канала 9 формирования базисной последовательности с Р = 1/2. Далее в соответствии с адресными кодами выдаются базисные последовательности с Р = 0 и с Р; = 1/4, Тогда результирующая вероятность на четырех периодах различных базисных последовател ьн остей будет равна 7/32, т. е, она может быть задана с точностью до 1/32, В общем случае результирующая вероятность определяется по формуле:=1 р1=1,гп, % и где и - число разрядов в регистрах 12,Таким образом, можно задать вероятности от 0 до 0,5, Значения результирующей вероятности большей 0,5 задаются путем подачи единичного сигнала по входу 13 сумматора 11 по модулю два. При совокупности ранее рассмотренных кодов в данном случае на выход канала 9 формирования будет поступать инвертированная с помощью сумматора 11 по модулю два результирующая последовательность. Суммарная веро ятность появления единичных символов в ней до инвертирования равнялась 7/32. тогда после инвертирования эта вероятность будет равна дополнению до единицы, т,е. Р = (1 - 7/32) = 25/32,Путем смены начального состояния регистра сдвига, вырабатывающего базисные псевдослучайные последовательности, осуществляется дополнительное перемешивания структуры результирующего сигнала. т,е. он более приближается к случайному,Точность задания результирующей вероятности может неограниченно увеличиваться либо с помощью увеличения числа ячеек регистра сдвига п 1 (при этом увеличивается число базисных последовательностей и число входов мул ьтиплексора), либо с помощью увеличения числа и (при фиксированной п 1). определяющего количество размещенных базисных последовательностей на периоде результирующей последовательности. В этом случае необходимо увеличить разрядность кольцевых регистров 12,Для генератора возможно аналитиче ски выразить результирующую вероятностьчерез вероятности базисных последовательностей, являющихся отрицательными степенями двойки, в соответствии с приведенным выражением для результирующей 45 вероятности Р. При достаточном числе временных позиций и, на которых размещаются базисные последовательности. можно получить практически любой закон распределения единичных символов в результирующей последовательности. Для рассмотренного выше примера (и = 4) результирующая последовательность с вероятностью Р = 4/32 можно получить, располагая базисные последовательности с соответствующими вероятностями Р; на четырех позициях как 1/2. О. О.0 и как 1/8, 1/8, 1/8, 1/8. В первом случае единичные символы группируются, во втором распределены по всему периоду результирующей последовательности,670 Тираж Подписное ИПИ Государственного комитета по изобретениям и открытиям при ГКНТ 113035, Москва, Ж, Раушская наб,4/5 ак оизводственно-издательский комбинат "Патент", г. ужгород, ул,Гагарина, 101 Формула изобретения Генератор псевдослучайной последовательности чисел, содержащий регистр сдвига с обратной связью, генератор тактовых импульсов, счетчик, два элемента И, формирователь импульса, о т л и ч а ю щ и й с я тем, что, с целью повышения точности, в него введены блок ключей, делитель частоты и й каналов формирования, причем каждый канал формирования содержит мультиплексор, сумматор по модулю два и два кольцевых регистра, выходы старших разрядов первого и второго кольцевых регистров в каждом канале формирования соединены соответственно с первым и вторым управляющими входами мультиплексора этого канала формирования, тактовые входы первого и второго кольцевых регистров каждого канала формирования объединены и подключены к выходу делителя частоты, в каждом канале формирования выход мультиплексора соединен с первым входом сумматора по модулю два, выходы сумматоров по модулю два каждого канала формирования являются выходами генератора, вторые входы сумматоров по модулю два каждого канала формирования являются входами задания вероятности генератора,выход генератора тактовых импульсов соединен с тактовым входом регистра сдвига собратной связью и подключен к входу делителя частоты, выход которого соединен с так 5 товым входом счетчика, выход которогосоединен с информационным входом блокаключей, выход которого соединен с информационным входом регистра сдвига с обратнойсвязью, первый разрядный выход которого10 соединен с первым входом первого элемента И и с одноименными информационнымивходами мультиплексоров каналов формирования второй разрядный выход регистрасдвига с обратной связью соединен с первым15 входом второго элемента И, выход которогосоединен с вторыми информационнымивходами мультиплексоров всех каналовформирования и подключен к второму входупервого элемента И, выход которого соеди-,20 нен с третьими информационными входамимультиплексоров каналов формирования,выход делителя частоты через формирователь импульса соединен с управляющимвходом блока ключей и с входом записи ре 25 гистра сдвига с обратной связью, третийразрядный выход которого соединен с вторым входом второго элемента И,