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

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

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

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

Генератор случайных чисел содержит генератор 1 тактовых импульсов, генератор 2 пачек импульсов, счетчик 3, группы 4.1-4.К схем.сравнения, группы 5.1-5.К элементов И, блок.6 элементов ИЛИ, блок 7 сравнения, счетчик 8,

блок 9 сравнения, счетчик 1Q, дешифратор 11, регистр 12 памяти, группы 13.1-13.К элементов И, группы 14.1- 14.К регистров,.группы 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.

эле Пусть (x | ,x:, ),.K - координат X множество всех имеющихся 2-мернЫх век- «рпр- Rnnw

через блок

торов с компонентами и имеется информация QO том, что первая компонента важнее второй. Тогда вектор X Е Xj называется омега-эффективным по информации 52 , если не существует

;вектора х

(J)

€ Xi такого, что:

(х , X, Л X

(J)

X2:)V(.

X. Д X

(П

xj,

(1)

1 ( 1

где х(х,,х) - вектор, полученный путем перестановки компонент вектора х, если X ;, «с х.

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

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

Перед началом работы устройства счетчики 3, 8, 10 и 21, а также ре- ги стры 14,1-14.К, 19 и 36 обнулены, В регистры 26, 15.1-1 5.К, Занес.екы

номер 3 и координаты х векторов множества Xj

О)

.(П

(х

IJ)

X

(J)

), .K ,

12 занесено число К

в регистр количество век

торов множества X, а в регистр 20 - число К-1,

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

поступающим с регистра 12, При равен- из регистра 19 через группы элементов стве-чисел на выходе блока 22 сравне- И 29, 30 и блок 31 элементов ИЛИ в ния появляется сигнал, который через 45 блок 7 сравнения и запрещая прохождение координат (,, х) из регистра 36 через группы элементов И 32.

элемент 23 задержки поступает на вход останова генератора 1, прекращаюп ий его работу.

и 33, Запись координат (х,, х) в регистр 36 из регистра 19 произвоЧисло 1 импульсов с выхода счетчика 21 через группу элементов 24 задержки поступает на схемы сравнения группы 16,1-16,К, на которые соответственно поступают номера j векторов , хранящиеся в регистрах 26,1- 26,К, Та схема сравнения группы 16,1- 16.К, где выполнилось равенство l j laeT разрешение соответствующей груп- le элементов И 17,1-17,К на запись

координат X «рпр- Rnnw

(i)

,(.

: в регистр 1 9

5

0

.

5

через блок 18 элементов ИЛИ,

Одновременно с этим импульс с гег нератора 1 тактовых импульсов устанавливает триггер 40 в единичное со- . стояние, триггер 37 - в нулевое состояние и поступает на вход умножителя 27 частоты, который умножает

0 частоту в два раза. Импульс с выхода умножителя частоты обнуляет счетчики 3 и 8, дает разрешение через элемент задержки 2,5 на з апись в регистр 19 координат х , , а также запускает генератор 2 пачек импульсов. Причем число импульсов в пачке равно К, а период следования Т выбран из условия Т. К Т Выход генератора 2 пачек импульсов соединен со счетным входом счетчика 3, с выхода которого число m импульсов поступает на входы схем сравнения,второй группы 4,1-4,К,Кроме того, на каждую из этих схем сравнения поступает номер j вектора х , хранящийся в.соответствующем регистре 26,1- 26,К, а на инверсные входы схем сравнения - сигнал с выхода соответст- вующей схемы сравнения первой груп

30 пы 16,1-16,К, Таким образом, если оказывается выполненным условие Л в некоторой схеме сравнения второй группы 4,1-4,К, то дается разрешение соответствующей

35 группе элементов И, 5,1-5,К на подачу координат у, , y, блок 7 сравнения через блок 6 элементов ИЛИ, Первый импульс относительно входного с умножителя часто40 ™ 27 устанавливает триггер 28 в

единичное состояние, давая paзpeшeн e на подачу координат х,х и

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

и 33, Запись координат (х,, х) в регистр 36 из регистра 19 производится при наличии импульса с генератора 1, проходящего через элемент 38 задержки, и сигнала с выхода схе - мы 34 сравнения, который появляется в том случае, если вьтолняется условие X : X 2 для координат, хранящихся в регистре 19, Разрешающий запись координат (х, х,) в регистр 36 сигнал с выхода элемента И 35 переводит триггер 37 из нулевого в

единичное состояние. Разрешение на. прохождение координат (х,, х) в бло 7 сравнения из регистра 36 через группы элементов И 32 и 33 и блок 3 элементов ИЛИ дается лишь в том случае, если на входах групп- элементов И 32 и 33 появляется одновременно единичный сигнал с выхода триггера 37, единичный сигнал с инверсного выхода триггера 28 (появляющийся при переключении триггера 28 в ну- лев1ое состояние вторым относительно входного к умножителю 27 частоты импульсом), .

Таким образом, координаты х, х поступают в блок 7 сравнения лишь после выполнения К-1 сравнений вэк- тора ,(х,, Хд) с векторами,(у, х ,

filX -1- -tч

)

В блоке 7 сравнения

ществляется проверка невьтолнения условия у,ь, X, Л х (или у..: х, 4 х).. Результат сравнения поступает на счетный вход счетчика 8. По окон- чании прохождения первой относитель- но импульса с генератора 1 пачки (К)импульсов С выхода генератора-2 пачек импульсов в счетчике 8 (до момента его обнуления) находится число п-количество невьшолнений.условия У,:Х, л ., Если количество не-- выполнений указанного условия оказывается равным числу К-1, записанному в регистре 20, то на выходе блока 9 сравнения появляется сигнал, который перебрасывает триггер 40 в нулевое состояние. Если триггер 40 находится в единичном состоянии (единичное состояние устанавливается импульсом генератора 1 тактовых импуль- coBj, то дается разрешение на прохождение сигнала с выхода блока 9 сравнения через элемент И 39 на входы .группы элементов И 13.1-13,К и счетный вход счетчика 10, Число с выхода счетчика Ш поступает на вход дешифратора 11, который дает разрешение на запись координат вектора (х,, х,,) хранящегося в регистре 19, в с оответ- ствующий регистр 14,1-14,К,

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

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

. ю 15

20

25 ЗО 0

35

0

5

5

Генератор случайных чисел, содержащий генератор тактовых импульсов, генератор пачек импульсов, четыре счетчика, две группы схем сравнения, :три группы элементов И, два блока . элементов ИЛИ, три блока сравнения, дешифратор, два регистра памяти, две Ггруппы регистров памяти, перрый регистр, два элемента задержки, группу, элементов задержки, группу регистров, причем вход запуска генератора тактовых импульсов является входом пуска генератора, выход генератора тактовых импульсов через первь1й элемент задержки соединен с входом разрешения записи первого регистра, первый и второй информационные выходы которого соединены соответственно с первыми и вторыми информационными входами регистров группы, входы разрешения записи регистров группы соединены с выходами одноименных элементов И первой группы, первые входы элементов И первой группы соединены с соответствующими выходами дешифратора, вход которого соединен с. выходом первого счетчика, выход генератора тактовых импульсов соединен со счетным входом второго счетчика, разрядные выходы которого .подключены к первой группе информационных разрядных входов первого блока сравнения вторая группа информационных разрядных входов которого соединена с соответствующими информационными разрядными выходами первого регистра памяти, выход Равно первого блока сравнения через второй элемент задержки соединен с входом останова генератора тактовых импульсов, выход генератора пачек импульсов соединен.со счетным входом третьего счетчика, разг рядные выходы которого соединены с первыми группами информационных входов схем сравнения первой группы, выходы Равно которых соединены с первыми входами одноименных элементов И второй группы,.выходы элементов И второй группы подключены к соответствующим входам первого блока элементов ИЛИ, выходы которого соединены с первой группой информационных входов - второго блока сравнения, выход Меньше которого соединен со счетньш входом четвертого счетчика, разрядные выходы второго счетчика через соотВ:етствующие элементы задержки группы с|оединены с первыми группами информа uJHOHHMx входов соответствующих схем сравннния второй группы, вторые груп пы информационных входов схем срав- tieHHH второй группы соединены с вто- jibiMH группами информационных входов одноименных схем сравнения„первой группы и подключены к информацион- itbiM выходам одноименных регистров 1гамяти первой группы, выходы Равно схем сравнения второй группы соединены с входами синхронизации схем (равнения первой группы и подключены к первым входам элементов И третьей руппы, выходы элементов И треть- |;й грзгппы соединены с соответствую- цими входами второго блока элементов ИЛИ,,выход которого соединен с информационным входом первого ре- систра, первый и второй информацион ibie выходы регистров памяти второй : руппы соединены с вторым и третьим зходами элементов И третьей и вто- рой групп, разрядные выходы четвертого счетчика соединены с первой группой информационных входов третьего блока сравнения, вторая группа |информационных входов которого сое- |динена с соответствующими информа- рионньми разрядными выходами вто- iporo регистре памяти, о-т л и ч а ю- и и с я тем, что, с целью расши- ;рения функциональных возможностей . за :счет формирования случайных чисел, являющихся подмножеством омега-эф- фективных векторов, в него введены третий блок элементов ИЛИ, умножитель частоты, триггер, два RS-триг- гера, третий элемент задержки, схема сравнения, четыре группы элементов И, два элемента И, второй регистр, причем выход генератора тактовых импульсов через умножитель частоты соединен с входом запуска генератора пачек импульсов, выход умножителя частоты соединен с входами обнуления третьего и четвертого счетчиков и счетным входом триггера, , прямой выход которого соединен с

о Q 5 Q

5

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

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