Генератор случайных чисел

 

ИЗОБРЕТЕНИЕ ОТНОСИТСЯ К ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ И МОЖЕТ БЫТЬ ИСПОЛЬЗОВАНО ДЛЯ ВЫДЕЛЕНИЯ ИЗ МНОЖЕСТВА ВЕКТОРОВ ПОДМНОЖЕСТВА ОМЕГА-ЭФФЕКТИВНЫХ ВЕКТОРОВ. ЦЕЛЬ ИЗОБРЕТЕНИЯ - РАСШИРЕНИЕ ФУНКЦИОНАЛЬНЫХ ВОЗМОЖНОСТЕЙ ЗА СЧЕТ ФОРМИРОВАНИЯ СЛУЧАЙНЫХ ЧИСЕЛ, ЯВЛЯЮЩИХСЯ ПОДМНОЖЕСТВОМ ОМЕГА-ЭФФЕКТИВНЫХ ВЕКТОРОВ. ГЕНЕРАТОР СОДЕРЖИТ ГЕНЕРАТОР ТАКТОВЫХ ИМПУЛЬСОВ, ГЕНЕРАТОР ПАЧЕК ИМПУЛЬСОВ, СЧЕТЧИКИ, ГРУППЫ СХЕМ СРАВНЕНИЯ 4.1 - 4.К, ГРУППЫ ЭЛЕМЕНТОВ И 5.1 - 5.К, БЛОКИ ЭЛЕМЕНТОВ ИЛИ, блоки сравнения, счетчики, дешифратор, регистры памяти, группу регистров 14.1 - 14.к, группы регистров памяти 15.1 - 15.к, регистры 22 сравнения, элементы задержки, группу элементов задержки, умножитель частоты, триггер, элементы И, R.S - триггеры, Поставленная цель достигается за счет введения новых блоков и функциональных связей. 1 ил.

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

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

РЕСПУБЛИК (19) (11) А1 (59 4 G 06 Р 7/58

1Я. ц3., к

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

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

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

ПРИ ГКНТ СССР

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ! (21) 4395128/24-24 (22) 21,03,88 (46) 30,11,89, Бюл, ¹ 44 (72) Е,С,Егоров, С.Н,Воробьев, и Э.В,Борисов (53) 681.3(088,8) (56) Авторское свидетельство СССР № 1170454 кл. С 06 Р 7/58, 1984.

Авторское свидетельство СССР

¹ 1453401, 1987. (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано для выделения из множества векторов подмножества омега-эффективных векторов, Цель изобретения — расширение функциональных возможностей

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

Цель изобретения — расширение функциональных возможностей за счет формирования случайных чисел, являющихся подмножеством омега-эффективных векторов, На чертеже представлена электрическая структурная схема устройства, Генератор случайных чисел содержит генератор 1 тактовых импульсов, генератор 2 пачек импульсов, счетчик 3, группы 4,1-4,К схем. сравнения, группы

5 ° 1-5.К. элементов И, блок,б элементов ИЛИ, блок 7 сравнения, счетчик 8, 2 за счет формирования случайных чиссл являющихся подмножеством омега-эффективных векторов, Генератор содержит генератор тактовых импульсов, генератор пачек импульсов, счетчики, группы схем сравнения, группы элементов И блоки элементов ИЛИ, блоки сравнения, счетчики, дешифратор, регистры памяти, группы регистров,, группы регистров памяти, группу схем сравнения, регистры, регистры памяти, элементы задержки, группу элементов задержки, умножктель частоты, триггеры группы 29, 30.элементов И, блок 31 элементов ИЛИ, группы 32-33 элементов

И элементы И RS-триггеры 37 ° Постав- д ь у

Я ленная цель достигается за счет введения новых блоков и функциональных овя- Щ зей. 1 ил, С: блок 9 сравнения, счетчик I Q, дешифратор 11, регистр 12 памяти, группы

13,1-13.К элементов И, группы 14,114.К регистров,,группы 15,1-15.К.регистров памяти, группы 16 ° 1-16.К схем сравнения, группы 17,1-17,К элементов И, блок 18 элементов ИЛИ, ре гистр 19, регистр 20 памяти, счетчик

21, блок 22 сравнения, элемент 23 задержки, группу 24 элементов задержки, элемент 25 задержки, группу регистров 26,1-26,К памяти, умножитель 27 частоты, триггер 28, группы элементов

И 29-30у блок элементов ИЛИ 31, группы элементов И 32-.33, схему 34 сравнения, элемент И 35, регистр 36, RSтриггер 37, элемент 38 задержки, элемент И 39 и RS-триггер 40.

1525701 (s)

Пусть Хе= (х (х,х ), 1=1,111— множество всех имеющихся 2-мерных векторов с компонентами х, х и имеется информация Qo том, что первая компонента важнее второй, Тогда вектор х.Е Х 1 называется омега-эффективным по информации Р если не существует вектора х F Х 1 такого, что: (i ) 30

Число 1 импульсов с выхода счетчика 21 через группу элементов 24 задержки поступает на схемы сравнения группы 16,1-16,К, на которые соответственно поступают номера 1 векторов х ) хранящиеся в регистрах 26„1—

26.К. Та схема сравнения группы 16.1I 6„К, где выполнилось равенство 1=j

ràåò разрешение соответствующей груп.)е элементов И 17,1 — 17,К на запись (х x Ax x )7(x, ()1 (i) ()

1 х. х(» х) (1) где х= (х, х ) — вектор, полученный Э путем перестановки компонент вектора х, если х< с х

Таким образом, второе условие пос ле связки Ч в (1) формируется лишь в том случае, если х х .

Генератор для выделения подмножест- . . ва омега-эффективных двумерных векто, ров работает с использованием правила (1) следующим образом.

Перед началом работы устройства

:,счетчики 3, 8, 10 и 21„а также ре; гистры 14 ° 1-14,К, 19 и 36 обнулены, В регистры 26, 15,1-15,К, занесены

,номеР 3 и кооРдинаты х,, х у ()) (1) векторов множества Х ) = )x(1) (.)) (>)

=(х, х х ), 1=1,KI, в РегистР

12 занесено число К вЂ” количество векторов множества Хп, а в регистр 20— число К-1, 35

Генератор 1 тактовых импульсов вырабатывает последовательность импульсов с периодом Т1, Выход генератора 1 соединен со счетным входом счетчика 21 с выхода которого число 40

1 импульсов поступает на блок 22 сравнения, где сравнивается с числом К, поступающим с регистра 12, При равенстве чисел на выходе блока 22 сравнения появляется сигнал, который через 45 элемент 23 задержки поступает на вход останова генератора l прекращающий его работу, координат х()) x () . в регистр! 9В через блок 18 элементов ИЛИ, Одновременно с э тим импульс с г енератора I тактовых импульсов устанавливает триггер 40 в единичное состояние, триггер 37 — в нулевое состояние и поступает на вход умножителя 27 частоты, который умножает частоту в два раза, Импульс с выхода умножителя частоты обнуляет счетчики 3 и 8, дает разрешение через элемент задержки 25 на запись в регистр

19 координат х,, х ) а также за(11 пускает генератор 2 пачек импульсов, Причем число импульсов в пачке равно К, а период следования Т выбран из условия Т е К " Т, Выход генератора 2 пачек импульсов соединен со счетным входом счетчика 3, с выхода которого число m импульсов поступает на входы схем сравнения, второй группы 4,1-4,К„ Кроме того, на каждую из этих схем сравнения поступает номер j вектора х(1, хранящийся в.соответствующем регистре 26.126,К, а на инверсные входы схем срав. нения — сигнал с выхода соответст" вующей схемы сравнения первой груп" пы 16,1-16,К, Таким образом, если оказывается выполненным условие

m=j A 1ф j в некоторой схеме сравнения второй группы 4,1-4.К, то дается разрешение соответствующей группе элементов И, 5.1-5,К на подачу координат у, х(), у =х(), в блок 7 сравнения через блок 6 элементов ИЛИ, Первый импульс относительно входного с умножителя частоты 27 устанавливает триггер 28 в единичное состояние, давая разрешение на подачу координат х)=х, и х. =х (1) () из регистра 19 через группы элементов

И 29, 30 и блок 31 элементов ИЛИ в блок 7 сравнения и запрещая прохождение координат (х, х ) из регистра 36 через группы элементов И 32. и 33, Запись координат (х, х ) в регистр 36 из регистра 19 производится при наличии импульса с генератора 1, проходящего через элемент

38 задержки, и сигнала с выхода схемы 34 сравнения, который появляется в том случае, если выполняется ус1 ловие х „ x для координат, хранящихся в регистре 19, Разрешающий запись координат (х„, х ) в регистр

36 сигнал с выхода элемента И 35 переводит триггер 37 из нулевого в

0l

Фо р мул а

5 15257 единичное состояние. Разрешение на прохождение координат (х,, х>) в блок

7 сравнения из регистра 36 через группы элементов И 32 и 33 и блок 31 элементов ИЛИ дается лишь в том случае, если на входах групп элементов

И 32 и 33 появляется одновременно единичный сигнал с выхода триггера

37, единичный сигнал с инверсного выхода триггера 28 (появляющийся при переключении триггера 28 в нулевое состояние вторым относительно входного к умножителю 27 частоты импульсом}, 15

Таким образом, координаты х, х л ° поступают в блок 7 сравнения линь после выполнения К-.l сравнений вектора {х,, х ) с векторами,(у =х 20 (s) (11 }

° 1 э у =х }, В блоке 7 сравнения осуществляется проверка невыполнения

° / условия у x„hy х (или уъ. х Я у м

2 х ). Результат сравнения поступает на счетный вход счетчика 8, По окон- 25 чании прохождения первой относительно импульса с генератора 1 пачки (К)импульсов с выхода генератора.2 пачек импульсов в счетчике 8 (до момента его обнуления) находится число 30 и-количество невыполнений, условия у„: х, Л у х, Если количество не-. выполнений указанного условия оказывается равным числу К-l, записанному в регистре 20, то на выходе блока

9 сравнения появляется сигнал, который перебрасывает триггер 40 в нулевое состояние, Если триггер 40 находится в единичном состоянии (единичное состояние устанавливается им- 40 пульсом генератора I тактовых импульсов), то дается разрешение на прохождение сигнала с выхода блока 9 сравнения через элемент И 39 на входы .группы элементов И 13 ° 1-13.К и счет- 45 ный вход счетчика 1.0. Число с выхода счетчика 111 поступает на вход дешифратора 11, который дает разрешение. на запись координат вектора (х,, х 1, хранящегося в регистре 19, в соответ- 50 ствующий регистр 14,1-14.К, Таким образом, по окончании рабо-. ты„устройства в выходном регистре

14.1-14,К находятся векторы, состав55 ляющие омега-эффективное подмножество, причем число этих векторов равно числу, содержащемуся в счетчике 10. изобретения

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

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

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

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

t соединены с первыми группами информационных входов соответствующих схем равнвния второй группы, вторые групы информационных входов схем сравнения второй группы соединены с втоыми группами информационных входов дноименных схем сравнения„первой руппы и подключены к информационм выходам одноименных регистров амяти первой группы, выходы "Равно" хем сравнения второй группы соеди-. ены с входами синхронизации схем равнения первой группы и подключены первым входам элементов И третьей руппы, выходы элементов И третьй группы соединены с соответствуюими входами второго блока элеменов ИЛИ,,выход которого соединен информационным входом первого ре. истра, первый и второй информацион-.. е выходы регистров памяти второй руппы соединены с вторым и третьим ходами элементов И третьей и втоой групп, разрядные выходы четверого счетчика соединены с первой руппой информационных входов треть;его блока сравнения, вторая группа информационных входов которого сое,цинена с соответствующими информа ционными разрядными выходами вто:рого регистра памяти, о-т л и ч а юшийся тем, что, с целью расширения функциональных воэможностей.за счет формирования случайных чисел, являющихся подмножеством омега-эффективных векторов, в него введены третий блок элементов ИЛИ, умножитель частоты, триггер, два RS-триггера, третий элемент задержки, схема сравнения, четыре группы элементов

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

RS-триггера и R-входом второго RSтриггера, выход которого соединен с вторыми входами элементов И шестой и седьмой групп, выход "Равно" третьего блока сравнения соединен с

R- âõîäîì первого RS-триггера, выход

2о которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом "Равно" третьего блока сравнения, выход первого элемента И соединен со счет25 ным входом первого счетчика и подключен к вторым входам элементов И первой группы, выход генератора тактовых импульсов через третий элемент задержки соединен с первым входом второго элемента И, выход которогосоединен с входом разрешения записи второго регистра и S-входом второrî RS-триггера, первый информационный выход первого регистра соединен с первым информационным входом второго регистра, с вторыми входами элементов И четвертой группы и подключен к первому информационному вхо.ду схемы сравнения второй информаl ционный вход которой соединен с вторым информационным выходом первого регистра, с вторыми входами элементов И пятой группы и подключен к второму информационному входу второго I регистра, первый и второй информационные выходы которого соединены соответственно с третьими входами элементов И шестой и седьмой групп, выход "Меньше" схемы сравнения соединен с вторым входом второго элемента И, 1 525701

Составитель И,Столяров

Редактор Л,Пчолинская Техред А. Кравчук Корректор О. Ципле

Заказ 7228/45 Тираж б68 Подписное

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

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

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