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

ас

00 00.

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

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

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

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

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

Наиболее близким по технической сущности к предлагаемому является устройство для вероятностного моделирования, содержащее блок управления, генератор равномерно распределенных чисел, вход которого соединен с первым выходом блока управления, блок сравнения, первый вход которого соединен с выходом генератора равномерно распределенных чисел, а второй вход - с вторым выходом блока управления, регистр адреса, разделенный на две части (ctapшyю и младшую), первый вход которого соединен с первым выходом блока сравнения, а второй вход - с пятым выходом блока управления, блок памяти, вход которого соединен с выходом регистра адреса, регистр числа, первый вход которого соединен с выходом блока памяти, а второй вход - с четвертым выходом блока управления , регистр маски, первый 1ВХОД которого соединен с выходом регистра-числа, второй с вторым выходом блока сравнения, третий вход - с третьим выходом блока управления, первый выход соединен с третьим входом блока сравнения, а второй выход с третьим входом регистра адреса. Устройство по3воляет формировать последовательности случайных чисел с требуемыми законами распределения. В устройстве реализуется метод обратных функций, основанный на сравнении

равномерно распределенных случайных чисел со значениями Р(х,) воспроизводимой функции распределения, отыскании интервала, для которого выполняется условие

F((5i,-.b/

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

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

F(x|). В результате сравнения в младшую часть регистра поступает код. По ЭТОМУ коду из блока памяти выбирается и подается а блок сравнения очередная группа знамений F.:() , после чего

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

Устройство позволяет моделировать 2 различных законов распределений (где - разрядность старшей части регистра адреса). Информация о законах располагается в 2 областях памяти. Выбрр требуемого закона осуществляется соответствующей адресацией с помощью старшей части регистра адреса З. Недостатком устройства является сложность технической peaлизaцi1и иаза наличия блока управления и сложно го составного регистра адреса, ограниченные возможности программного управления из-за жесткого распределения поля памяти и относительно низкая надежность работы из-за сложных цепей управления, что является существенным,.так как сбой и отказы стохастических блоков трудно различимы. Цель изобретения - упрощение устройства и повышение надежности работы. Для достижения поставленной цели в известный генератор случайных чисел, содержащий генератор равномерно распределенных случайных чисел, блок памяти, вводится генератор тактовых импульсов, регистр сдвига и сумматор, первый вход которого соединен с выходом генератора равномерно распределенных случайных чисел, вход которого объединен с тактовым входом регистра сдвига и подключен к выходу генератора тактовых импульсов, выход регистра сдвига соединен со своим входом Установка, является выходом генератора и соединен с входом блока памяти, выход которого соединен с вторым входом сумматора, выход которого соединен с информационным входом регистра сдвига, управляющий вход которого является .входом Пуск генератора. Упрощение устройства достигается за счёт того, что для формирования.адресов чтения памяти и для. формирования случайного числа используется один регистр последовательных прибли жений, в прототипе для этих целей используется три регистра, причем регистр эдреса является сложным (составным). Упрощение устройства X достигается также за счет управления работой устройства сигналами с выхода регистра последовательных приближений, при этом отсутствует .. специальный блок управления. Кроме того, асе блоки устройства, за исключением генератора равномерно рас пределенных чисел, существуют в интегральном исполнении, что определяет простоту технической реализации устройства, его высокую надёжность, компактность. 738.4 На чертеже приведена структурная схема устройства. Генератор содержит генератор 1 тактовых импульсов, генератор 2 рав- , номерно распределенных случайных чисел, сумматор 3 блок k памяти, регистр 5 сдвига. Генератор 1 тактовых импульсов предназначен для генерации регулярной последовательности импульсов синхронизации устройства, для его реализации можно использовать ральную схему . Генератор 2 равномерно распределенных случайных чисел предназначен для формирования потока первичных равномерно распределенных случайных чисел, может быть использован любой из известныхии описанных в литературе. Сумматор 3 может быть выполнен на интегральных схемах К155ИПЗ и др. В качестве регистра 5 последовательных приближений можно использовать регистр последовательных приближений .аналого-цифровых преобразователей .(интегральная-схема К155ИР17)| либо регистр сдвига типа К155ИР1. Блок А памяти служит для хранения кодов, задающих законы распределения формируемых потоков случайных чисел. Для обеспечения возможности формирования произвольных законов распределения необходимо применить оперативное запоминающее устройство. Если датчик случайных чисел ориентирован на формирование потока случайных чисел одногоИЛИ нескольких заданных законов распределения, можно применить постоянное запоминающее устройство. В интегральном исполнении существует большое количество элементов запоминающих устройств различной емкости и быстродействия. Рассмотрим работу устройства при использовании регистра последовательных приближений типа К155ИР17 предназначенного для построения аналогоцифровых преобразователей. При этом вход 6 регистра 5 после довательных приближений - информационный, вход 7 - синхронизации работы, вход 8 разрешения работы, вход 9 задания режима, причем вход 9 соединен с вы- . ходом мла/рего. разряда.; Цикл формирования случайного числа начинается, когда в младшем разряде регист{ а 5 нуль и на вход 8 регистра поступает разрешающий сигнал. По заднему фронту очередного тактового импульса в старший разряд регистра последовательных приближений записывается нуль, во все остальные разряды - единицы. Из блока памяти k считывается код и суммируется со случайным числом. С выхода переноса сумматора 3 на вход 6 регистра 5 поступает значение первого разряда формируемого случайного числа (нуль иди единица). По заднему фрон ту следующего тактового импульса значение первого разряда формирует:мого (случайного) числа принимается в старший разряд регистра 5 нуль ИЗ первого разряда сдвигается во второй, генератор 2 равномерно распределенных случайных чисел формирует новое случайное число. По сформированному на выходе регистра. 5 последовательных приближени новому адресу из блока А памяти считывается новый код, суммируется с но вым случайным числом, по заднему фронту следующего тактового импульса сформированный второй разряд выходно го числа принимается во второй разряд регистра 5, нуль из второго разряда регистра 5 сдвигается в следующий (третий) разряд, генератор 2 равномерно распределенных случайных чисел формирует новое первичное случайное число. Последовательность опи санных тактов идет до сдвига нуля в младший разряд регистра 5. Нуль в младшем разряде регистра 5 указывает, что число сформировано, поступая на вход 9 регистра, разрешает установку начального состояния. Код сфор мированного случайного числа находит ся в регистре последовательных приг ближений. Так как на первый вход 10 сумматора 3 поступают равномерно распределенные числа с интервалом от О до 1-2, где И - разрядность сумматора, генератора 2 равномерно распределенных случайных чисел и блока

Т а б .Л и ц а 1 ч памяти, вероятность единицы на выходе переноса сумматора, вырабатываемой, если сумма чисел больше единицы, равна поступающему на второй вход 11 сумматора 3 коду из блока k памяти.. На первом такте из блока памяти читается код, равный вероятности попадания случайной величины воспроизводимого закона распределения, во вторую половину области существования (вероятность единицы старшего разряда формируем 1х чисел. На втором такте читается код, задающий условную вероятность попадания во вторую четверть, если первый сформированный разряд равен нулю, или в четвертую четверть, если сформированный первый разряд равен единице, т.е. задается условная вероятность единицы во втором разряде. На последующих тактах задают- . ся в зависимости от полученных значений разрядов формируемого числа условные вероятности попадания случайной величины в соответствующие 1/2 части области существования, где-1 - номер такта. Например, если на первых двух тактах получена комбинация 10, на третьем такте из блока памяти читается код условной вероятности попадания случайной величины воспроизводимого закона распределения в интервал от 5/8 до 6/8 области существования. На каждом такте задаются условные вероятности, отсюда и название Метод условных вероятностей. В табл. 1 показано расположение кодов УСЛОВНЫХ вероятностей в блоке 4 памяти для случая, если устройство формирует четырехразрядные случайные числа. В каждой клетке табл.1 слева указывается обозначение кода вероятности, справа - адрес ячейки. Нумерация адресов памяти с нуля. Верхний индекс в обозначении кода вероятности - результат, полученный на предыдущих тактах. Если обозначить P - вероятносгь k-й кодовой комбинации формируемых случайных чисел (, где m разрядность формируемых чисел), усЬ ные вероятности I вычисляются по формуле jliiilii HjHH к/;. . :РК, , k. jr+f/2 где i ; Устройство может формировать слу чаййые числа и по методу обратных функций, для этого необходимо, чтоб генератор 2 равномерно распределен-Таблица 2 ных случайных чисел формировал одно число на весь цикл формирования выходного числа, а не новое на каждом такте. Для этого .выходной регистр генератора 2 равномерно распределенных случайных чисел можно синхронизировать выходом младшего разряда pervfctpa 5, а не.импульсами генератора 1 тактовых импульсов. При этом в блок памяти последовательно записываются значения интегральной функции распределения , начиная с нулевой ячейки. Расположение кодов в блоке памяти для случая формирования четырехразрядных случайных чисел показано в табл. 2..

ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ, срдержащий генератор равномернораспределенных случайных «чисел, блок пачто, с целью .упрощения и повышения надежности, он содержит генератор Тактовых импульсов, регистр, сдвига и сумматор, первый вход которого соединен с выходом генератора равномерно распределенных случайных чисел, вход которого объединен с тактовым входом ре пестра сдвига и подключен к выходу генератора тактовых импульсов, выход регистра сдвига соеданеи со своим входом Установка, является выходом генератора и соединен с входом блока памяти, выход которого соединен с вторым входом сумматора , выход которого соединен с инфор§ мационным входом регистра сдвига, (Л управляющий вход которого является входом Пуск генератора.

В этом случае, -как и в прототипе осуществляется логарифмический перебор кодов вероятностей, если Рц; требуемые вероятности кодовых комбинацик.

Как говорилось выше, в качестве регистра 5 данного генератора слу чайных чисел можно использовать регистр сдвига с возможностью параллельного занесения кода, типа существующего интегрального регистра К155ИР17. При этом вход 6 регистра :5 последовательных приближений является входом последовательной записи регистра сдвига, вход 7 - синхронизации сдвига, вход 8 - синхронизации,параллельной записи, вход 9 - задания режима, соединенный со старшим выходом регистра.

Цикл формирования случайного числа начинается при поступлении на вход 8 импульса запуска, если в старшем разряде регистра S единица. При этбм по входам параллельной записи в старший разряд записывается единица, во всех остальных - нули. На каждом такте формируется аналогично (как описано выше) один разря выходного числа, по Заднему фронту

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

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

Единица с выхода старшего разряда регистра 5 является указателем готовности числа, сформированное

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

55 при методе условных вероятностей для случая формирования четырехраз-. рядных случайных чисел показано в табл. 3.

Расположение кодов в памяти при методе обратных функций для случая Из табл. 1- видно, что при методе условных вероятностей в случае использования регистра последователь ных приближений на базе; регистра сдв га, расположение кодов в памяти сов падает с порядком их расчета, при ме тоде обратных функций расположение кодов в памяти и порядок их расчета совпадают в случае использования регистра последовательных приближений, применяемого в аналого-цифровых преобразователях. Если датчик случайных чисел используется совместно с ЭВМ, которая осуществляет расчет кодов настройки и их загрузку, при совпа-. дении порядка расчета кодов и их раз грузке системе оказывается более эффективной, так как не требуется дополнительной перестановки кодов. Метод обратных функций отличается простотой процедуры расчета кодов настройки генератора случайных чисел и требует меньше исходных равномерно-распределенных случайных чисел, чем метод условных вероятностей, что позволяет применить менее быстродействующий и простой генератор 2 равномерно распределенных случайных чисел. Однако метод условных вероятностей обладает в общем более высокой точностью воспроизведения заданных законов распределения.

формирования четырехразрядных случайных чисел показано в табл. i. При использовании в качестве регистра 5 регистра сдвига, предлагаемое устройство позволяет как и прототип ,. моделировать в режиме разделения времени несколько законов распределе1;|ия, а также цепи Маркова различной связности. При этом по сравнению с прототипом предлагаемое уст- ройство имеет более гибкое программное управление, позволяющее варьирование количеством воспроизводимых законов распределений и разрядностью случайных чисел, связностью цепей Маркова и количеством их состояний при постоянном объеме блока памяти и разрядности регистра последовательных приближений. Задание режима формирования требуемого распределения из группы распределений, информации о которых записаны в блок памяти, задание разрядности форм1 уемых чисел, сходности цепи Маркова и количества состояний осуществляется путем задания соответствующего кода начального состояния регистра последовательных приближений. В табл. 5 показано расположение кодов вероятностей в блоке памяти при использовании метода условных вероятностей, при объеме блока памяти 16 ячеек, для случая моделирования двух законов распределения. Запрос на генерацию чисел первого закона распределения осуществляется при записи в начале каждого ци|у1а генерации в регистр последовательных приближений кода двойки, запрос на генерации чидел второго распределения - кода тройки. По окончании цикла генерации в старшем разряде регистра последовательных приближений находится единица, в следующем разряде - нуль или единица, указывающая номер распределения, в остальных разрядах сформированное случайное число.. В общем ллучае, при моделировании группы распределений, разрядность фо мируемых в данный момент случайных верхний индекс в обозначении кодов вероятностей указывает состояние из которого переходит цепь, нижний состояние,, в которое переходит цепь, В первой строчке табл. 6 коды, определяющие вероятность переходов в одно из старших состояний, в нижней строчке - коды условных вероятностей Так, например,Pj2 вероятность перехода цепи в состояние 2 или 3, если она находится в состоянии 1, Р| вероятность перехода цепи из состояния 1 в состояние 2, если на предыдущем такте определилось, что цепь переходит в состояние 2 или 3. В начале цикла генерации нового состоя.ния в младшие два разряда регистра 5 Заносится номер состояния цепи, в третий разряд единица. За два такта генерируется состояние, единица сдви гается в старший разряд .регистра последовательных приближений Максимальное число состояний Марковского процесс,а и его максимальная связность снеобходимым числом состояний, кoличecтвd моделируемых чисе равна количеству разрядов регистра последовательных приближений в начальном состоянии равных нулю, начиная со старшего разряда до первого разряда устанавливаемого в; еде1ницу, номер распределения задается кодом, следующим за первой единицей. В..табл.5 первый нижний индекс в обозначении кода вероятности указывает на номер распределения. В табл. 6 показано размещение кодов вероятностей переходовпри моде-, лировании односвязной цепи Маркова, описываемой матрицей /вероятностей перехода типа РЛ (j, ,1,2,3) для блока памяти объемом 16 слов. Т а - б ;Л и ц d 6., -l-J. В режиме разделения времени процессов Маркова и законов распределения случайных чисел требуемой разрядности, т.е. функциональные возможности устройства определяются блока памяти устройства. Технико-экономическая эффективность изобретения определяется упрощением устройства, что снижает его стоимость и повышает надежность; обеспечением возможности программного управления, что позволяет оперативно управлять устройством вплоть до его применения для генерации нестационарных потоков чисел. Устройство имеет высокую досто.верность, работы, что KiiasaHOупрощением в первую очередь цепей управления, при сохранении функциональных возможностей, В совокупности с простотой реализации это позволяет широко использовать предлагаемое устройство в микропроцессорных системах контроля и диагностики ци()овых схем в качестве генератора тестовых се13.100873814

рий, в системах управления испыта-и виде одной микросхемы, так как все

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