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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 59 СУДАРСТВЕНН О ИЗОБРЕТЕНИ ПРИ ГКНТ СССР КОМИТЕТ ОТКРМТИЯМ ИСАНИЕ ИЗОБРЕТЕН ТЕЛЬСТВРАТОР СЛУЧАЙНЫХ ЧИСЕЛ б ительной я из множествава омега-эффективизобретения - расвыделенидмножеств, Цель ова оров ых векторирение Фу б рес генератор ратор 2 и группы 4,т 51 28/24-2403,8811,89, Бюл, В 44,Егоров, С.НвВоробьев,рисов3(088,8)орское свидетельств4, кл, С 06 Р 7/58,ское свидетельство1, 1987,тение относится к вычисехнике и может быть испол кциональных возможностей Изобретение относится к специализиованным устройствам вычислительнойехники и может быть использовано дляыделения из множества векторов подножества омега-эффективных векторов,Цель изобретения - расширение функиональных возможностей за счет форирования случайных чисел, являющихя подмножеством омега-эффективныхекторов,На чертеже представлена электриеская структурная схема устройства,Генератор случайных чисел содержит1 тактовых импульсов, генеачек импульсов, счетчик 3,1-4,К схем, сравнения, группы51-5,К. элементов И, блок,б элеменов ИЛИ, блок 7 сравнения, счетчик Ь,за счет формирования случайных чиссл являющихся подмножеством омега-эффективных векторов, Генератор содержит генератор тактовых импульсов, генератор пачек импульсов, счетчики, группы схем сравнения, группы элементов И блоки элементов ИЛИ, блоки сравнения, счетчики, дешифратор, регистры памяти, группы регистров группы регистров памяти, группу схем сравнения, регистры, регистры памяти, элементы задержки, группу элементов задержки, умножитель частоты, триггеры группы 29, 30,элементов И, блок 31 элементов ИЛИ, группы 32-33 элементов И элементы И ЕЯ-триггеры 37Постав- д ь уЯ ленная цель достигается за счет введения новых блоков и функциональных овя- Щ зей, 1 ил,С: лок 9 сравнения, счетчик 10, дешифратор 11, регистр 12 памяти, группы 13,1-13,К элементов И, группы 14,1- 14,К регистровгруппы 15,1-15,К, гистров памяти, группы 161-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, КЯ- триггер 37, элемент 38 задержки, элемент И 39 и КБ-триггер 40.(Пусть Хещ х "(х ",х т ) р 1=1,Кв множество всех имеющихся 2-мерных векторов с компонентами х,х и имеется информация йо том, что первая компонента важнее второй, Тогда вектор х.б Х называется омега-эффективным по информации Я, если не существует вектора х 6 Х( такого, что:(1) 30 Число 1 импульсов с выхода счетчика 21 через группу элементов 24 задержки поступает на схемы сравнения группы 16,1-16,К, на которые соответственно поступают номера 1 векторов х ) хранящиеся в регистрах 26,1- 55 26,К, Та схема сравнения группы 16,1- 6 К, где выполнилось равенство 1= (ает разрешение соответствующей груп)е элементов И 17,1-17,К на запись1 ( 11х, Л хх ), (1)где х=(х ,х ) - вектор, полученныйпутем перестановкикомпонент вектора х,если х 1.с хТаким образом, второе условие после связки Ч в (1) формируется лишьв том случае, если х 1 х,Генератор для выделения подмножест- .ва омега-эффективных двумерных векто,ров работает с использованием правила (1) следующим образом.Перед началом работы устройства=(х, х ь ), 1=1,К), в регистр12 занесено число К - количество векторов множества Хп), а в регистр 20 -число К, 35Генератор 1 тактовых импульсоввырабатывает последовательность импульсов с периодом Т 1, Выход генератора 1 соединен со счетным входомсчетчика 21, с выхода которого число 401 импульсов поступает на блок 22 сравнения, где сравнивается с числом К,поступающим с регистра 12, При равенстве чисел на выходе блока 22 сравнения появляется сигнал, который через 45элемент 23 задержки поступает на входостанова генератора 1, прекращающийего работу,координат хх ( в регистр9- )через блок 18 элементов ИЛИ,Одновременно с этим импульс с генератора 1 тактовых импульсов устанавливает триггер 40 в единичное состояние, триггер 37 - в нулевое состояние и поступает на вход умножителя 27 частоты, который умножаетчастоту в два раза, Импульс с выходаумножителя частоты обнуляет счетчики 3 и 8, дает разрешение через элемент задержки 25 на запись в регистр19 координат х, , х) , а также запускает генератор 2 пачек импульсов,Причем число импульсов в пачке равно К, а период следования Т выбраниз условия ТК " Т , Выход генератора 2 пачек импульсов соединен сосчетным входом счетчика 3, с выходакоторого число ш импульсов поступает на входы схем сравнения, второйгруппы 4,1-4,К Кроме того, на каждую из этих схем сравнения поступает номер 1 вектора х(, хранящийся в.соответствующем регистре 26,126,К, а на инверсные входы схем сравнения - сигнал с выхода соответст"вующей схемы сравнения первой груп"пы 16,1-16,К, Таким образом, еслиоказывается выполненным условиеш=1 Л 1 фв некоторой схеме сравнения второй группы 4,1-4,К, то дается разрешение соответствующейгруппе элементов И, 5,1-5,К на подачу координат у х р у хр вблок 7 сравнения через блок 6 элементов ИЛИ, Первый импульс относительно входного с умножителя частоты 27 устанавливает триггер 28 вединичное состояние, давая разрешениена подачу координат х)=х, и х. =хиз регистра 19 через группы элементовИ 29, 30 и блок 31 элементов ИЛИ вблок 7 сравнения и запрещая прохождение координат (х, х) из регистра 36 через группы элементов И 32.и 33, Запись координат (х , х ) врегистр Зб из регистра 19 производится при наличии импульса с генератора 1, проходящего через элемент38 задержки, и сигнала с выхода схе .мы 34 сравнения, который появляетсяв том случае, если выполняется условие х 1 хдля координат, хранящихся в регистре 19, Разрешающийзапись координат (х, х ) в регистр36 сигнал с выхода элемента И 35 переводит триггер 37 из нулевого в5 15257 единичное состояние, Разрешение на прохождение координат (х х в блок 7 сравнения из регистра 36 через группы элементов И 32 и 33 и блок 31 элементов ИЛИ дается лишь в том случае, если на входах групп элементов И 32 и 33 появляется одновременно единичный сигнал с выхода триггера 37, единичный сигнал с инверсного выхода триггера 28 (появляющийся при переключении триггера 28 в нулевое состояние вторым относительно входного к умножителю 27 частоты импульсом), 15Таким образом, координаты х , хлепоступают в блок 7 сравнения линьпосле выполнения К-.1 сравнений вектора (х х) с векторами,(у =х 200)(11)1 Эу =х ) , В блоке 7 сравнения осуществляется проверка невыполненияФусловия ухЬух (или уъ х 4 у мРма е. т 1 .2х ). Результат сравнения поступаетна счетный вход счетчика 8, По окончании прохождения первой относительно импульса с генератора 1 пачки(К)импульсов с выхода генератора.2пачек импульсов в счетчике 8 (до момента его обнуления) находится числои-количество невыполнений, условияу. х, Л у х, Если количество невыполнений указанного условия оказывается равным числу К, записанному в регистре 20, то на выходе блока359 сравнения появляется сигнал, который перебрасывает триггер 40 в нулевое состояние, Если триггер 40 находится в единичном состоянии (единичное состояние устанавливается им рпульсом генератора 1 тактовых импульсов), то дается разрешение на прохождение сигнала с выхода блока 9 сравнения через элемент И 39 на входы.группы элементов И 131-13.К и счетный вход счетчика 1.О. Число с выхода счетчика 1 О поступает на вход дешифратора 11, который дает разрешение,на запись координат вектора (х х),хранящегося в регистре 19, в соответствующий регистр 14,1-14,К,Таким образом, по окончании рабо-. тыустройства в выходном регистре 14,1-14,К находятся векторы, состав 55 ляющие омега-эффективное подмножество, причем число этих векторов равно числу, содержащемуся в счетчике 10.01 Фо р мул а изобретения Генератор случайных чисел, содержащий генератор тактовых импульсов, генератор пачек импульсов, четыре счетчика, две группы схем сравнения ,три группы элементов И, два блока элементов ИЛИ, три блока сравнения, дешифратор, два регистра памяти, две ,группы регистров памяти, первый регистр, два элемента задержки, группу. элементов задержки, группу регистров, причем вход запуска генератора тактовых импульсов является входом пуска генератора, выход генератора тактовых импульсов через первый элемент задержки соединен с входом разрешения записи первого регистра, первый и второй информационные выходы которого соединены соответственно с первыми и вторыми информационными входами регистров группы, входы разрешения записи регистров группы соеди" иены с выходами одноименных элементов И первой группы, первые входы элементов И первой группы соединены с соответствующими выходами дешифратора, вход которого соединен с выходом первого счетчика, выход генератора тактовых импульсов соединен со счетным входом второго счетчика, разрядные выходы которого подключены к первой группе информационных разрядных входов первого блока сравнения вторая группа информационных разрядных входов которого соединена с соответствующими информационными разрядными выходами первого регистра памяти, выход "Равно" первого блока сравнения через второй элемент задержки соединен с входом останова генератора тактовых импульсов, выход генератора пачек импульсов соединен.со счет. ным входом третьего счетчика, разрядные выходы которого соединены .с первыми группами информационных входов схем сравнения первой группы, выходы "Равно" которых соединены с пер" выми входами одноименных элементов И второй группы, выходы элементов И второй группы подключены к соответструюшим входам первого блока элементов ИЛИ, выходы которого соединены с первой группой информационных входов второго блока сравнения, выход "Меньше" которого соединен со счетным входом четвертого счетчика, разрядные выходы второго счетчика через соот 1525701ветствующие элементы задержки группы соединены с первыми группами информаЧионных входов соответствующих схем равнвния второй группы, вторые групы информационных входов схем сравнения второй группы соединены с вто" ыми группами информационных входов дноименных схем сравненияпервой группы и подключены к информационщ выходам одноименных регистров амяти первой группы, выходы "Равно" хем сравнения второй группы соеди-. ены с входами синхронизации схем равнения первой группы и подключеныпервым входам элементов И третьей руппы, выходы элементов И третьй группы соединены с соответствуюими входами второго блока элеменов ИЛИвыход которого соединенинформационным входом первого ре. истра, первый и второй информацион-е выходы регистров памяти второй руппы соединены с вторым и третьим ходами элементов И третьей и втоой групп, разрядные выходы четверого счетчика соединены с первой руппой информационных входов треть;его блока сравнения, вторая группа информационных входов которого сое" ,цинена с соответствующими информационными разрядными выходами второго регистра памяти, о т л и ч а ющ и й с я тем, что, с целью расширения Функциональных воэможностей.за счет формирования случайных чисел, являющихся подмножеством омега-эфФективных векторов, в него введены третий блок элементов ИЛИ, умножитель частоты, триггер, два КБ-триггера, третий элемент задержки, схема сравнения, четыре группы элементов И, два элемента И второй регистр, причем выход генератора тактовых импульсов через умножитель частоты соединен с входом запуска генератора пачек импульсов, выход умножителя частоты соединен с входами обнуления третьего и четвертого счетчиков и счетным входом триггера, прямой выход которого соединен с первыми входами элементов И четвертой и пятой групп, инверсный выходтриггера соединен с первыми входамиэлементов И шестой и седьмой. групп,выходы элементов И четвертой, пятой,шестой и седьмой групп соединены ссоответствуйицими входами третьегоблока элементов ИЛИ, выходы которого подключены к второй группе информационных входов второго блока сравнения,выход генератора тактовых импульсов соединен с Б-входом первогоКЯ-триггера и К-входом второго КБтриггера, выход которого соединен свторыми входами элементов И шестойи седьмой групп, выход "Равно" третьего блока сравнения соединен сК- входом первого КБ-триггера, выход 20 которого соединен с первым входомпервого элемента И, второй вход которого соединен с выходом "Равно"третьего блока сравнения, выходпервого элемента И соединен со счет ным входом первого счетчика и подключен к вторым входам элементов И первой группы, выход генератора тактовых импульсов через третий элементзадержки соединен с первым входомвторого элемента И, выход которого .соединен с входом разрешения записи второго регистра и Б-входом второго КЯ-триггера, первый информационный выход первого регистра соединенс первым информационным входом второго регистра, с вторыми входамиэлементов И четвертой группы и подключен к первому информационному вхо.ду схемы сравнения второй информационный вход которой соединен с вторым информационным выходом первогорегистра, с вторыми входами элементов И пятой группы и подключен к второму информационному входу второгорегистра, первый и второй информационные выходы которого соединены соответственно с третьими входами элементов И шестой и седьмой групп, выход "Меньше" схемы сравнения соеди"нен с вторым входом второго элемента И,1525701 Составитель И,Столяродактор Л,Пчолинская Техред А.Кравчукрректор О,Ципл издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 01 оизводствен Заказ 7228/45 Тираж бб 8 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5