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

Изобретав;;te относится к вычислительной TexHi-ifce, предназначенной дтш оцаикн качества потока paDHObsapiO р предй. случайных чисел и может быть использовано для повьгшекыя достоверности работы аппаратурыS исполь 3 угоща и пос.па,;,г и а тел; нос ти с.пу ч аи иьп чнсал, фор шруаглгх аппаратным спосо 6ом Известно устройство для анализа вероятностных характернст1 к датчика случайных Ч15сел5 содержашее гшдикаторр первый вход которого подкя пчеи к выходу блока сравнепия, а второй вход к выходу блока угфа злениЯз йёрвая грзттга вкоггоп блока ср-аинолп-ая соедпнеиа с BuxoAatin коммутатора соответственно, первая группа входов котороз о ясляется входами ycipioucTsa nepsbiti и второй регистры па;чятк,, вхо ды которых сседынелк с выходом блока упратзлйииХ; а выходы - с зторьми груииани дходоь :соммуга ор 1 г: блока еразнеиия соответствеино CiJo Недостатком данного устройст зг йвляатся надсстаточно высокое быстро действие аралтаристик генератора случат-ньзх чгчса и vtc .-. делать оперативную оценку тоспособнпсти, вызоаи - ое кесоходль Ю стыо иакоплв;;: ;я большого -iVборки для получения состоятелъгшй оценки о Ск11жению 6ыстродгкс; ;: ия способ :тзует также применетгчю комг ута-тора, что предус 1агрииас; ггоследозательный aлгopчт , Нквестио акже ycTponctso д.;;; ста тистического анализа датчика случанньш чисел, содержащее геяератор такг вык импульсоп. датчик случа;;|гых чксел, разрядиьгй регистр сд.ч-гга, элемент И, блок трехпо;;иционных переклю чателей, сиетчгпс числа испытан) переключатель п триггер Г 23, Иедостатког-; этого устройства такж является низкое быстродейстЕчте. Кроме- Toroj аппаратурные затраты :на, реализация устройства зиачгггелыю аревьзЕают затраты на реализадмю само го датчика случайных чисел,; чркчем устройство одемлзагь качес.гБо только одного ,цвоич-:шго разряда пото ка . Наиболее близкий по технической сущности к данному изобретенио является устройство для анализа вероят}госгяьгх характеристик датчика случай ных; Ч}1сел5 со,::,ер;каЕ(ее блок управлени ,ij.;iT4i-fK случа;1ны : чисел, первый регистр памгчи. ког-мутатор, блок сравк;:11ня, второй 1зегнстр памяти, индика тсф, схему сравнения и блок злемен ов И, CxLi;-: cpaisiif-лия предс%-авляет с.обоп од:-и:р;-;зрядг1у10 схему сравнения, 1;грный КАСД г-;от;/рс;й соедннеи со старШ1-1М разрядом .датчика cJcyMaunbix чйс-я.г,, нторок вхо.д - с выходом блока управ.гшыкя, BbDHHi, блока соединен с иервьм регистром намяти. Первые входы каж,пого элемента Н соединены с выходами коммутатора, вторые входы - с блоком уирСЕлення, а выходы - со втоpijiM регистром намяти. Выход нидикатора является пfcIxoдc устройства. Работу ycipo.;iCTra можно нредстаБить как лрэи,есс фс рми1 }О15ан 1Я coGiiiтнй, 1олучагкг,1х на ньгходе блока срав-Hc:n-iH: cocTDHiiu-iK ii С ;о;ги ;е} И11 , )Г-,Х сгучагль;-; чн;ел н глзря-дке их следо.занья с датчика случайных чисел Б двуплечиьс сноплзнчые rpyiintr cefi - , ьи; на дчл гакта 1 аботь; ст;шгстчг ГЗ. Сдг-ако ::;;.В1:;Сгнс С устройсчч-io имеет п, 1-1едост;г:ч г1м нрт-г мспольтои зпии его а кСНт:;оо1;у paaoiocnocooaocii-f генеavopr с-ГУ 4;i;4)ibix чгк:ел Наг.ример, зггдержки обнаружения -ьле/;но(: тфеменем ка ч;ки Т; итгдикатпре для оя-ельгйой О1 енки„ 1 ягляегся и го. что ( ог:у1игст1.1:яется только для 1-1Огс |5азрил,л , ;i,e4biO и;(: орртгния Яплястся новы- iHR Зыс1 pcдeйcтJэия устройства и : yHOOWCKiiS , /хля достг1жеииу: посгавленной пелн )ойстгс цля коггтроля reirepaTopa учай;1Ь Х -.мсгл, содержаи;се элеме-гт .. олок уг(аплсы- :я, вне,дечтл депифTpj-:rrepoB, два счетчиок ФормцрОЕанкя iHiTeDiiaя блок управления содерJAIIPRТ к элемент И; выcoa jHHBH с входом ск блок,;; сЬорТИрования юггеряала ;мени. с |у7,се1зь.ми входами трнггеi группы я с 11улевь м нходом триг а. единичный выход которого явля-Я выходом Неислравность устроила,, нькод генератора тактовых им:ьсов соединен со счетным входоь iBoro счетчика, с нервы -{и вход,аь;н мен|Ч; ЧЛ11РЕТ и элемента И и с входом контролируемого генератора случайных чисел, пьгходы разрядов которого соединены с входами соответствуюпщх разрядов дешифратора, выходы которого соединены с единичными входами соответствующих триггеров группы, выходы которых соединены с входами элемента И соответственно, выход которого соединен со счетным входом второго счетчика, с входом Сброс(0 блока формирования итервала времени и с вторыми входами элемента И и элемента выход которого соединен с синхронизируюшлм входом деши фратора, выход блока-формирования ин тервала времени соединен с единичным входом триггера, ныход переноса первого счетчика соединен с входом Сброс второго счетчика, информационные выходы первого и второго сче чиков являются соответственно первым и вторым информацис нными Нулходями устройства. На фиг. 1 представлена сгрук-iypная схема устройства; на фит. 2 схема блока уггравления. Устройство содержит генератор тактовых импульсоп, генератор чайных чисел, дешиф)атор 3, группу триггеров ;, элемент И 5, блок 6 управления, счетчик 7, блок 8 формирования интервала лремени, триггер 9 счетчик 10. Блок у 1равле ия со;;ержит элемент И 11 и элемент ЗАПРЕТ 12. В предлагаемом устройстзе используется метод оценки качестгкэ некоторой рав}{омерно распределенной случай ной числовой пос.тгсдовательности, основанный на формировании полного набора событий и оценки отклонения от времени, в которого это событие должно произойти с заданной вероятностью. Устройство работает следу)ощ1-1м образом. Началу работы устройства предшест вует устаповка его в исходное состоя ние, Т;е. сброс блока трихтеров 4 н триггера 9 п О и запуск формирователя 8 временного интервала, что осу ществляется импульсом с второго выхо да блока 6 управления, а сброс считчиков 7 и 10 происходит циклически в процессе работы. Количество триггеро блока триггеров 4 равно количеству выходов депгифратора 3 и равно множеству состояний выхода генератора 2 случайных чисел. Процесс формировани Ш 934 полногс наОора событий состоит в запомил .11)ли факта появления случайных чисел, представленных дешифрато ром в у; -rrnpHOM коде в порядке их следовй:Л:я С. выхода генератора 2 случайных чисел на блоке триггеров 4. Прор1сход11т это следующим образом. Первый тактовый импульс поступает на первый вход блока управления, на вход счетчика 7 и на вход генератора 2 случайных чисел. Генератор 2 случайных чисел вырабатывает по этому импульсу некоторое случайное число Uj , которое поступает на информационные выходы дешифратора 3. При налични на его втором входе нулевого уровня, поступающего с первого пыхода блока 6 управления, происходит дешифрац{ Я данного случайного числа и на одном из выходов дешифратора в течение длительности тактового сигнала сохраняется низкий логический урогзень, который поступает па cooTiievcTHyioiiiero ему триггера из блока триггеров 4 и устанавливает его I 1. Осталыиде триггеры из блока Tpi:rrei: OLJ 4 свое состояние не изменяют, )мхолм всех триггеров заведен; I па входе ;)лементов И 5. Данная схема сох)апяет нулевой уровень lia выходе ;:ри условии, что хотя пы одни ч-риггер. из блока триггеров 4 паходдпсл Б нулевом состоянии. C4t:T4iuc. 7 суммгппет количество тактовых I; iпyJIьcoь поступаощих на его вход с геиерлторл 1 такговых импульсов, т.е. ч1-1сло сгенерирова1П ьк случайных чисел. Поя:чГ1ение полыогО набора событий соотно.тствуст установ се всех Tpurrepoii 4 в состояние лопгч-еской e.iHHiiuM., при этом на г ыходе элемента И 5 точс появляется уровень jior;i4i2c,KoO единиць, 3 MOMtnrr перехода и ч нуля Б единицу фиксируется счетчиком 10, далее сигнал с выхода схемы И поступает на HTOpovi вход блока 6 управления, я также на второй вход формирователя 8 йременлого интервала, сбрасывая его и исходное состояние. После чего на ироьгя суцествоваиия В1ДСОКОГО логического уровня ка выходе элемента И 5 запрещена работа ;еигифратора 3, а на второй вых(1д блока 6 управления разрешается npoxoHvieHne тактового импульса от генератора 1 тактов1)Тх импульсов, которьш устанавливает в исходное состояние б:юк триггеров 4 и триггер 9, а формирователь 8 временного интервала запускает на новый цикл формирования временного интервала. Требуемая длина временного интерзала определяется как Т r.t, :где t период следования тактоаьгх импульсов с генератора тактО Bbtx импульсов; г - длина последовательности слу чайных чисел вида . формируемых генератором 2 случайных чисел, необходимая для накопления полного набора событий с вероятностью Р, Если полный iia6opV событий появится за время меньпгее Т, то фор -1ирователь 8 временного интерва ла уста навливается в исходное состояние по первому входу и ожидает сигнал запуска па новый цикл формирования ::ременного интервала. Если за время Т полный набор событий не сформирОЕ1г то формирователь 8 временного интерпала устанавливает триггер 8 в единичное состояние- что означает либо отклонение от нормального работы генератора случггйньг. , либо с вероятностью (1-Р) ложное ср-аса тьпзание. Выход триггера 9 должеч кс пользоваться для :инип,-1ирования работ схемы более полного контроля, напри Meps в случае работы генератора слуайных чисел в составе ЭВМ к вькоду ршициации агитаратного прерывания для остановки текущей программы, а более точная проверка осуществляется допол нительньми средствами npi-i работе в с.оставе ЭВМ программным тестом. Достоиксгво предлагаемого устройс.тва состоит в том, что при возн.икно Бенин существенных отклонений в рабо те генератора случайных чисел (отказе ) в процессе решения задачи г- скпкчается возмола-юсть потребления больпих массивом чисел от неисправного генератора и распространение. оп1ибки iia уже полученные результаты. Это особенно ваткно при контроле генераторов случайньх чисел, работающих Е составе систем испытаний в масштабе реального времени, где задержка с обнарул;ением отказа грозит вьпсодом и нерасчетный режим и необрати {ьв4и ГЕЗменеииями в объекте испытаний,, Для более полной оценки качества работы генератора случайных чисел имеется дополнительная нформа1гия: п - число полн,п наборов событий на вьглоде счетчика 10; L - общая длина последовательности с-чучайных чисел, необходимых для формирования п полнь Х наборов,, на первом Bbrxc;ie сч;;тчика 7. Полуменнь)е эмпирические значения и L сравкиваются с теоретическими начениями зтгк характеристик LrTin i-сгэ , k - d-Hd rvВ I I Й li Л де d - - число возможнь;х с ; бытий. которые мог-ут появиться в данио1 ЧИСЛОНОЙ пос;:едовательиости; H. . .5 Г S ОH F-1-3 - J , J ,... - стакдар-тиое отклонение длины -гисловой последователы ости ч -;сел н;ща U; ; -мьгиимальная длина последовате.чьности чисел вида U-; -средняя длина последовательности чисел вида U. , длина числовой последовательости с.лучаймых чисел, полученная в езультате анализа генератора случайь;х чисел, при условии, что мло по:учено п полных наборов, ,ne;i«fT Р тих пределах, то вероятность Р праильной работы генератора случайных исел где г число Стирл1П га 2-гч рода. Таким образок, предлагаемое устойстве позволяет упростить пропедуу контроля качества работы генератоа равномерно распределенных случайbDt чисел по сравнению с известными ешениями.. Пои этом повьш1аетс5; скоость { сокращается время ) обнаружения тказа и oДi oвpeмeннo уменьшаются ппаратурные затраты. Повь;шение бь cтpoдeйcтв я предлагамого устройства достигается за счет рименения нового прирщипа контроля, беспечивающего получе1.:пе ои,енки качества работы генератора случайных чисел за время существенно меньшее, чем это делается в цзвестных устройс вах за время меньшее необходимого для состоятельного анализа. Для достижения поставленной цели в устройство контроля введены дешифратор, блок триггеров, формирователь временного интервала, триггер контроля. Оценка качества работы генератора происходит путем контроля за накоплением полного набора состояний за время Т, определяемое вероятностью Р появления последовательност Uj , содержащей полный набор . При непоявлении такого события за интервал времени И, отрабатываемы формирователем временных интервалов срабатывает триггер контроля, что вы зьшает необходимость проведения боле тщательной проверки характеристик генератора, т.е. накопления выборки большего объема. Для накопления состоятельной статистики полньгх наборов. служит первый и второй счетчики. Производитель ность (быстродействие I предлагаемого устройства как средства контроля по вышена и за счет того, что анализ потоков случайных чисел не поразрядный, а параллельный - все разряды числа и. Упрощение аппаратурной реализации достигнуто за счет контроля при эквивалентном количестве оборудования не одного двоичного, а всех разрядов числа и.. В противном случае для контроля п разрядов числа U припшось бы использовать п устройств контроля, что потребовало бы пропорционального увеличения аппаратурных затрат, Технико-экономическая эффективность предлагаемого устройства обусловлена сокращением затрат машинного времени и на тестовые проверки генератора. Если в качестве базового образца использовать программный тест контроля, то экономический эффект будет определяться экономией машинного времени. Однако тестовый контроль - периодический. Эффект от организации 1;епрерывного контроля работы генератора случайных чисел зависит от важности и характера решаемой задачи, поэтому оценить его трудно.

Bxodi

8лод2

В А/л од 2

УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ГЕНЕРАТОРА СЛУЧАЙНЫХ ЧИСЕЛ, содерж--Чцее элемент II, блок управления, отличающееся тем, что, с целью новышения быстродействия и унрощения ycTpoiicTua, оно содержит дешифратор, группу триггеров, два счетчика, генератор тактовых импульсов, триггер и блок формирования интервала времени, а блок управления содержит элемент ЗАПРЕТ и элемент Н, выход которого соединен с входом Пуск блока фор-шрования интервала времени, с нулевыми входами триггеров группы и с нулевым входом триггера, единичный пыход которого является выходом Неисправность устройства, выход генератора тактовых импульсов соединен со счетным входом первого счетчика, с первыми входами элемента ЗАПРЕТ и элемента И и с входом контролируемого генератора случайных чисел, выходы разрядов которого соединены с входами соответствующих разрядов дешифратора, выходы которого соединены с единичными входами соответствующих триггеров группы, выходы KOTOpbfx соединены с входами элемента И.соответственно , выход которого соединен со счетным входом С 5S второго счетчика, с входом Сброс (Л блока формирования интервала времени, с вторыми входами элемента И и элемента ЗАПРЕТ , выход которого соединен с синхронизирующим входом дешифратора, вькод блока фop иpoвaния интервала времени соеди}1ен с единичным входом триггера, выход переноса первого счетчика coeди eн с входом 00 Сброс второго счетчика, информаци онные выходы первого и второго счетсо со чиков являются соответственно первым и вторым информацион}1ымн ньг одами со устройства.

0tis. 2

Выл од 1

-