Метод и критерий оценивания качества последовательностей случайных чисел
Изучена зависимость равномерности распределения знаков эмпирической автокорреляционной функции относительно количества перекрывающихся символов отрезков, на которые разбивается последовательность случайных чисел. Установлен допустимый «порог» перекрытия, ниже которого наблюдается равномерное распред...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/131417 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод и критерий оценивания качества последовательностей случайных чисел / Э.В. Фауре, А.И. Щерба, В.Н. Рудницкий // Кибернетика и системный анализ. — 2016. — Т. 52, № 2. — С. 116-124. — Бібліогр.: 20 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-131417 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1314172018-03-23T03:02:48Z Метод и критерий оценивания качества последовательностей случайных чисел Фауре, Э.В. Щерба, А.И. Рудницкий, В.Н. Системный анализ Изучена зависимость равномерности распределения знаков эмпирической автокорреляционной функции относительно количества перекрывающихся символов отрезков, на которые разбивается последовательность случайных чисел. Установлен допустимый «порог» перекрытия, ниже которого наблюдается равномерное распределение знаков автокорреляционной функции. Определено понятие барьерной функции. На ее основании разработан критерий оценивания качества генераторов случайных чисел. Представлены методика его применения и ее реализация для нескольких известных генераторов. Вивчено залежність рівномірності розподілу знаків емпіричної автокореляційної функції щодо кількості перекритих символів відрізків, на які розбивається послідовність випадкових чисел. Встановлено допустимий «поріг» перекриття, нижче якого спостерігається рівномірний розподіл знаків автокореляційної функції. Визначено поняття бар’єрної функції. На її основі розроблено критерій оцінювання якості генераторів випадкових чисел. Наведено методику його застосування та її реалізацію для декількох відомих генераторів. The authors analyze the dependence of the uniformity of distribution of signs of empirical autocorrelation function with respect to the number of overlapping symbols of segments into which a sequence of random numbers is divided. A feasible ‘threshold’ of overlap is established, below which the signs of the autocorrelation function are uniformly distributed. The concept of barrier function is defined and used to develop a criterion to estimate the quality of random number generators. The technique of its application and its implementation for several well-known generators are presented. 2016 Article Метод и критерий оценивания качества последовательностей случайных чисел / Э.В. Фауре, А.И. Щерба, В.Н. Рудницкий // Кибернетика и системный анализ. — 2016. — Т. 52, № 2. — С. 116-124. — Бібліогр.: 20 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/131417 519.246.2:004.415.538:004.421.5 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Фауре, Э.В. Щерба, А.И. Рудницкий, В.Н. Метод и критерий оценивания качества последовательностей случайных чисел Кибернетика и системный анализ |
| description |
Изучена зависимость равномерности распределения знаков эмпирической автокорреляционной функции относительно количества перекрывающихся символов отрезков, на которые разбивается последовательность случайных чисел. Установлен допустимый «порог» перекрытия, ниже которого наблюдается равномерное распределение знаков автокорреляционной функции. Определено понятие барьерной функции. На ее основании разработан критерий оценивания качества генераторов случайных чисел. Представлены методика его применения и ее реализация для нескольких известных генераторов. |
| format |
Article |
| author |
Фауре, Э.В. Щерба, А.И. Рудницкий, В.Н. |
| author_facet |
Фауре, Э.В. Щерба, А.И. Рудницкий, В.Н. |
| author_sort |
Фауре, Э.В. |
| title |
Метод и критерий оценивания качества последовательностей случайных чисел |
| title_short |
Метод и критерий оценивания качества последовательностей случайных чисел |
| title_full |
Метод и критерий оценивания качества последовательностей случайных чисел |
| title_fullStr |
Метод и критерий оценивания качества последовательностей случайных чисел |
| title_full_unstemmed |
Метод и критерий оценивания качества последовательностей случайных чисел |
| title_sort |
метод и критерий оценивания качества последовательностей случайных чисел |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2016 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/131417 |
| citation_txt |
Метод и критерий оценивания качества последовательностей случайных чисел / Э.В. Фауре, А.И. Щерба, В.Н. Рудницкий // Кибернетика и системный анализ. — 2016. — Т. 52, № 2. — С. 116-124. — Бібліогр.: 20 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT faureév metodikriterijocenivaniâkačestvaposledovatelʹnostejslučajnyhčisel AT ŝerbaai metodikriterijocenivaniâkačestvaposledovatelʹnostejslučajnyhčisel AT rudnickijvn metodikriterijocenivaniâkačestvaposledovatelʹnostejslučajnyhčisel |
| first_indexed |
2025-07-09T15:24:23Z |
| last_indexed |
2025-07-09T15:24:23Z |
| _version_ |
1837183444366393344 |
| fulltext |
ÓÄÊ 519.246.2:004.415.538:004.421.5
Ý.Â. ÔÀÓÐÅ, À.È. ÙÅÐÁÀ, Â.Í. ÐÓÄÍÈÖÊÈÉ
ÌÅÒÎÄ È ÊÐÈÒÅÐÈÉ ÎÖÅÍÈÂÀÍÈß ÊÀ×ÅÑÒÂÀ
ÏÎÑËÅÄÎÂÀÒÅËÜÍÎÑÒÅÉ ÑËÓ×ÀÉÍÛÕ ×ÈÑÅË
Àííîòàöèÿ. Èçó÷åíà çàâèñèìîñòü ðàâíîìåðíîñòè ðàñïðåäåëåíèÿ çíàêîâ ýìïèðè÷åñêîé àâ-
òîêîððåëÿöèîííîé ôóíêöèè îòíîñèòåëüíî êîëè÷åñòâà ïåðåêðûâàþùèõñÿ ñèìâîëîâ îòðåçêîâ,
íà êîòîðûå ðàçáèâàåòñÿ ïîñëåäîâàòåëüíîñòü ñëó÷àéíûõ ÷èñåë. Óñòàíîâëåí äîïóñòèìûé «ïî-
ðîã» ïåðåêðûòèÿ, íèæå êîòîðîãî íàáëþäàåòñÿ ðàâíîìåðíîå ðàñïðåäåëåíèå çíàêîâ àâòîêîð-
ðåëÿöèîííîé ôóíêöèè. Îïðåäåëåíî ïîíÿòèå áàðüåðíîé ôóíêöèè. Íà åå îñíîâàíèè ðàçðàáî-
òàí êðèòåðèé îöåíèâàíèÿ êà÷åñòâà ãåíåðàòîðîâ ñëó÷àéíûõ ÷èñåë. Ïðåäñòàâëåíû ìåòîäèêà
åãî ïðèìåíåíèÿ è åå ðåàëèçàöèÿ äëÿ íåñêîëüêèõ èçâåñòíûõ ãåíåðàòîðîâ.
Êëþ÷åâûå ñëîâà: ñëó÷àéíûå ÷èñëà, êîððåëÿöèÿ, îöåíêà êà÷åñòâà, ñòàòèñòè÷åñêèé êðèòåðèé.
ÂÂÅÄÅÍÈÅ
Èñïîëüçîâàíèå ïîñëåäîâàòåëüíîñòåé ñëó÷àéíûõ ÷èñåë ÿâëÿåòñÿ íåîòúåìëåìîé
÷àñòüþ ïðîöåññîâ èìèòàöèîííîãî ìîäåëèðîâàíèÿ, ïðîâåäåíèÿ ñòàòèñòè÷åñêèõ
ýêñïåðèìåíòîâ, ïåðåäà÷è è ïðåîáðàçîâàíèÿ èíôîðìàöèè.  ïðàêòè÷åñêèõ ïðè-
ëîæåíèÿõ ÷àñòî ïðèìåíÿþò èñêóññòâåííî ñãåíåðèðîâàííûå ïîñëåäîâàòåëüíîñ-
òè ïñåâäîñëó÷àéíûõ ÷èñåë (ÏÑ×).  ÷àñòíîñòè, äëÿ êðèïòîãðàôè÷åñêîãî ïðå-
îáðàçîâàíèÿ â ïîòî÷íîì ðåæèìå øèôðóþùàÿ ïîñëåäîâàòåëüíîñòü äîëæíà
èìåòü ñâîéñòâî âîñïðîèçâîäèìîñòè, ÷òî îãðàíè÷èâàåò â äàííîì ñëó÷àå èñïîëü-
çîâàíèå ïîñëåäîâàòåëüíîñòåé åñòåñòâåííûõ ñëó÷àéíûõ ÷èñåë. Âìåñòå ñ òåì íå-
îáõîäèìî, ÷òîáû ïðèìåíÿåìàÿ ïîñëåäîâàòåëüíîñòü ÏÑ× áûëà ñòàòèñòè÷åñêè
íåîòëè÷èìîé îò ïîñëåäîâàòåëüíîñòè ñëó÷àéíûõ ÷èñåë, ïîðîæäàåìîé åñòåñ-
òâåííûì èñòî÷íèêîì äèñêðåòíîãî áåëîãî øóìà (ãåíåðàòîðîì ñëó÷àéíûõ ÷èñåë
(ÃÑ×)). Îòìåòèì, ÷òî òîëêîâàíèå òåðìèíà «áåëûé øóì» íåîäíîçíà÷íî [1, 2].
 íàñòîÿùåé ñòàòüå èñïîëüçóåòñÿ îïðåäåëåíèå èç [2], è ïîä äèñêðåòíûì áå-
ëûì øóìîì ïîíèìàåòñÿ ñòàöèîíàðíûé äèñêðåòíûé ñëó÷àéíûé ïðîöåññ, âû-
áîðêè êîòîðîãî íåêîððåëèðîâàíû.
Äëÿ àíàëèçà ïîñëåäîâàòåëüíîñòåé ÏÑ× ïðèìåíÿåòñÿ øèðîêèé ñïåêòð òåñòîâ
è êðèòåðèåâ [3–6], ìíîãèå èç êîòîðûõ ðåàëèçîâàíû â ñïåöèàëèçèðîâàííûõ ïðè-
êëàäíûõ ïàêåòàõ òåñòîâ (DIEHARD [7], NIST [8], TestU01 [9] è äð.). Çàìåòèì, ÷òî
âñå ðàçðàáîòàííûå êðèòåðèè îïðåäåëÿþò òîëüêî íåêîòîðûå óñëîâèÿ, íåîáõîäèìûå
äëÿ îáåñïå÷åíèÿ íåîòëè÷èìîñòè ïîñëåäîâàòåëüíîñòåé ÏÑ× îò ïîñëåäîâàòåëüíîñ-
òåé ñëó÷àéíûõ ÷èñåë, è â íàñòîÿùåå âðåìÿ èçâåñòíû àëãîðèòìû, êîòîðûå ïðîõîäÿò
ïðèâåäåííûå ïàêåòû òåñòîâ [9–12]. Êðîìå òîãî, ñòàòèñòè÷åñêèå êðèòåðèè è òåñòû
äëÿ ïîñëåäîâàòåëüíîñòåé ÏÑ× ìîæíî òàêæå ïðèìåíÿòü äëÿ àíàëèçà ÃÑ× â öåëÿõ
âûÿâëåíèÿ íåîïòèìàëüíûõ ïðîöåäóð ïðåîáðàçîâàíèÿ ôèçè÷åñêèõ ïðîöåññîâ â ïî-
ñëåäîâàòåëüíîñòè ñëó÷àéíûõ ÷èñåë. Òàêèì îáðàçîì, àêòóàëüíà ïðîáëåìà ñîçäàíèÿ
íîâûõ êðèòåðèåâ, ñ ïîìîùüþ êîòîðûõ ìîæíî âûÿâëÿòü ñâîéñòâà, õàðàêòåðíûå
òîëüêî äëÿ åñòåñòâåííîãî äèñêðåòíîãî áåëîãî øóìà.
Íàèáîëåå ðàñïðîñòðàíåííûì äëÿ àíàëèçà ïîñëåäîâàòåëüíîñòè ñëó÷àéíûõ
÷èñåë (àíàëîãà äèñêðåòíîãî áåëîãî øóìà) ÿâëÿåòñÿ àâòîêîððåëÿöèîííûé òåñò.
Äëÿ åãî ðåàëèçàöèè ïðåäëîæåíû ðàçëè÷íûå ïîäõîäû [3, 4, 13, 14]. Âìåñòå ñ òåì
îñíîâíàÿ è îáùàÿ äëÿ âñåõ ïîäõîäîâ çàäà÷à àâòîêîððåëÿöèîííîãî àíàëèçà —
îïðåäåëåíèå ñîîòâåòñòâèÿ îöåíêè àâòîêîððåëÿöèîííîé ôóíêöèè (ÀÊÔ) èçó÷àå-
ìîé ïîñëåäîâàòåëüíîñòè äåëüòà-ôóíêöèè Äèðàêà [15], ÷òî, êàê ïðàâèëî, ïðîâî-
äèòñÿ ñ ïîìîùüþ t-êðèòåðèÿ Ñòüþäåíòà [16].
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2
© Ý.Â. Ôàóðå, À.È. Ùåðáà, Â.Í. Ðóäíèöêèé, 2016
 ðàáîòå [17] âûïîëíåí ñðàâíèòåëüíûé àíàëèç îöåíîê ÀÊÔ ïîñëåäîâàòåëü-
íîñòåé ÏÑ× êîìáèíàöèîííîãî ãåíåðàòîðà [18] è ãåíåðàòîðà MT19937 [10] ñ îöåí-
êàìè ÀÊÔ ñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé ÷èñåë àòìîñôåðíîãî øóìà [19] è êâàí-
òîâîãî ÃÑ× [20]. Äëÿ ôîðìèðîâàíèÿ îöåíîê ÀÊÔ èñïîëüçîâàí ïîäõîä, èçëîæåí-
íûé â [13, 14]. Ïîëó÷åííûå ðåçóëüòàòû ñâèäåòåëüñòâóþò îá îäíîðîäíîñòè îöåíîê
ÀÊÔ äëÿ âñåõ ðàññìîòðåííûõ ïîñëåäîâàòåëüíîñòåé. Äàííàÿ ñòàòüÿ ÿâëÿåòñÿ ïðî-
äîëæåíèåì íà÷àòîãî â [17] èññëåäîâàíèÿ çíàêîâ áîêîâûõ ëåïåñòêîâ ýìïèðè÷åñêîé
ÀÊÔ — òî÷åê íà êîððåëîãðàììå, ñîîòâåòñòâóþùèõ êîýôôèöèåíòàì êîððåëÿöèè
íåíóëåâîãî ïîðÿäêà.
Öåëü äàííîé ðàáîòû — âûÿâëåíèå êîððåëÿöèîííûõ ñâîéñòâ, ïðèñóùèõ ïî-
ñëåäîâàòåëüíîñòÿì, ïîðîæäåííûì åñòåñòâåííûìè èñòî÷íèêàìè äèñêðåòíîãî áå-
ëîãî øóìà, è íå ïðèñóùèõ èñêóññòâåííî ñãåíåðèðîâàííûì ïîñëåäîâàòåëüíîñòÿì
ÏÑ×, à òàêæå ðàçðàáîòêà ìåòîäà è êðèòåðèÿ îöåíèâàíèÿ êà÷åñòâà ïîñëåäîâàòåëü-
íîñòåé ðàâíîìåðíî ðàñïðåäåëåííûõ ñëó÷àéíûõ è ïñåâäîñëó÷àéíûõ ÷èñåë, ïîçâî-
ëÿþùèõ âûÿâëÿòü â íèõ íå îáíàðóæåííûå äî íàñòîÿùåãî âðåìåíè ñòàòèñòè÷åñ-
êèå íåðåãóëÿðíîñòè.
Äàëüíåéøèé àíàëèç ïðîâåäåì äëÿ ïîñëåäîâàòåëüíîñòåé ÷èñåë, ñèíòåçèðî-
âàííûõ åñòåñòâåííûì èñòî÷íèêîì ñëó÷àéíûõ ÷èñåë [19], ãåíåðèðóþùèì ñëó÷àé-
íîñòü ñ ïîìîùüþ àòìîñôåðíîãî øóìà è âûáðàííûì â êà÷åñòâå ýòàëîííîãî,
êâàíòîâûì ÃÑ× [20], îñíîâàííûì íà èçìåðåíèè âðåìåíè ðåãèñòðàöèè ôîòîíîâ,
à òàêæå ãåíåðàòîðîì «Âèõðü Ìåðñåííà» MT19937 [10].
ÂÛ×ÈÑËÅÍÈÅ ÎÖÅÍÎÊ ÍÎÐÌÈÐÎÂÀÍÍÛÕ ÊÎÝÔÔÈÖÈÅÍÒΠÊÎÐÐÅËßÖÈÈ
Êîððåëÿöèîííûé àíàëèç èññëåäóåìûõ ïîñëåäîâàòåëüíîñòåé ïðîâåäåì íà îñíî-
âå âû÷èñëåíèÿ îöåíîê êîýôôèöèåíòîâ êîððåëÿöèè ìåæäó ïîñëåäîâàòåëüíûìè
îòðåçêàìè (ïîäïîñëåäîâàòåëüíîñòÿìè) ôèêñèðîâàííîé äëèíû. Äëÿ ýòîãî ïîñëå-
äîâàòåëüíîñòü ÷èñåë (âûáîðêó) { }x n( ) äëèíû Lseq , 0 1� � �n Lseq , ðàçîáüåì íà
ñëåäóþùèå îäèí çà äðóãèì îòðåçêè äëèíû Lsegm : {x k( ), x k( ),�1 �
� , ( )x k Lsegm� �1 }, êîòîðûå ìîãóò ïåðåêðûâàòüñÿ èëè îòñòîÿòü îäèí îò äðóãîãî
íà íåêîòîðîå êîëè÷åñòâî ñèìâîëîâ. Ðàññòîÿíèå ìåæäó ñîñåäíèìè îòðåçêàìè
{ }x k x k x k Lsegm( ), ( ), , ( )� � �1 1� è { }x l x l x l Lsegm( ), ( ), , ( )� � �1 1� ïðè k l�
îïðåäåëÿåòñÿ âåëè÷èíîé � � � �l k Lsegm . Îòðèöàòåëüíîå çíà÷åíèå � õàðàêòåðè-
çóåò ïåðåêðûòèå (íàëîæåíèå, çàöåïëåíèå) îòðåçêîâ íà âåëè÷èíó àáñîëþòíîãî
çíà÷åíèÿ �. Òàêèì îáðàçîì, � � �1 Lsegm è ìîæåò ïðèíèìàòü ëþáûå öåëûå çíà-
÷åíèÿ èç ýòîé îáëàñòè.
Ïðîíóìåðóåì îòðåçêè â ñîîòâåòñòâèè ñ íîìåðàìè èõ ïåðâûõ ýëåìåíòîâ. Íà-
ïðèìåð, îòðåçîê { }x k x k x k Lsegm( ), ( ), , ( )� � �1 1� èìååò íîìåð k .
Îïèñàííàÿ ñõåìà ðàçáèåíèÿ âûáîðêè íà îòðåçêè ïðåäñòàâëåíà íà ðèñ. 1, ãäå
îáëàñòè ïåðåêðûòèÿ ñîñåäíèõ îòðåçêîâ îáîçíà÷åíû ÷åðíûì öâåòîì, à îáëàñòè
ìåæäó ñîñåäíèìè îòðåçêàìè — ñåðûì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2 117
� � �2
� � �1
� � �
� � 1
� � 2
0
0
0
0
0
. . .
. . .
. . .
. . .
. . .
Lsegm � 2
Lsegm �1
Lsegm
Lsegm �1
Lsegm � 2
2(Lsegm � 2)
2(Lsegm �1)
2Lsegm
2(Lsegm �1)
2(Lsegm � 2)
Ðèñ. 1. Ñõåìà ðàçáèåíèÿ âûáîðêè íà îòðåçêè ñ ïåðåêðûòèåì è ðàñòÿãèâàíèåì
Îöåíêà íîðìèðîâàííîãî êîýôôèöèåíòà êîððåëÿöèè ri ( )� âû÷èñëÿåòñÿ äëÿ
îòðåçêîâ ñ íîìåðàìè i Lsegm �( )� è ( ) ( )i Lsegm� �1 � ñëåäóþùèì îáðàçîì:
r
L
x i L l x i L
i
segm
segm segm
( )
( ( ( ) ) (( ) ( )
�
� �
�
� � � � �
1
1
� �
l
D X i L D X i L
l
L
segm segm
segm
))
( ( ( ))) ( (( ) (
�
�
� � �
0
1
1� �)))
, (1)
ãäå x j l x j l M X j
�
( ) ( ) ( ( ))� � � � — ðåàëèçàöèÿ öåíòðèðîâàííîé ñëó÷àéíîé âåëè-
÷èíû (ñ.â.), íàõîäÿùàÿñÿ íà ïîçèöèè ( )j l� , 0 1� � �l Lsegm ; x j l( )� — ( )j l� -é
ýëåìåíò âûáîðêè, 0 1� � � �( )j l Lseq ; M X j( ( )) è D X j( ( )) — ñîîòâåòñòâåííî
ìàòåìàòè÷åñêîå îæèäàíèå è äèñïåðñèÿ ñ.â. X j( ) , ðåàëèçàöèÿìè êîòîðîé ÿâëÿ-
þòñÿ ýëåìåíòû j-ãî îòðåçêà { }x j x j x j Lsegm( ), ( ), , ( )� � �1 1� .
Òàêèì îáðàçîì, äëÿ ëþáîé âûáîðêè äëèíû Lseq ìîæíî âû÷èñëèòü
i entier L Lseq segmmax ( ) (( ) / ( ))� � �� � � �1 (2)
îöåíîê íîðìèðîâàííûõ êîýôôèöèåíòîâ êîððåëÿöèè ri ( )� â ñîîòâåòñòâèè ñ (1)
(ôóíêöèÿ entier a( ) îïðåäåëÿåò öåëóþ ÷àñòü (àíòüå) ÷èñëà a ), à i i� �[ , ( ) ]max0 1� .
 äàííîé ðàáîòå îãðàíè÷èìñÿ ðàññìîòðåíèåì ðàâíîìåðíî ðàñïðåäåëåííûõ ïî-
ñëåäîâàòåëüíîñòåé ñî çíà÷åíèÿìè íà îòðåçêå [ , ]0 1M � , ãäå M — ìîùíîñòü àëôàâè-
òà. Òîãäà � � � �j L Lseq segm[ , ]0 1 : M X j M( ( )) ( ) /� �1 2 , D X j M( ( )) ( ) /� �2 1 12 .
Ïóñòü äëÿ âñåõ èñïîëüçóåìûõ èñòî÷íèêîâ M � 256 , Lseq � 256256,
Lsegm � 256 . Òàêîé âûáîð ïðè � � 0 ïîçâîëÿåò âû÷èñëÿòü imax ( )0 1000� îöåíîê
ri ( )0 ïî (1). Çàìåòèì, ÷òî ïðè îáîçíà÷åííûõ ïàðàìåòðàõ � �j [ , ]0 256001 :
M X j( ( )) .�127 5 , D X j( ( )) .� 5461 25 .
ÀÍÀËÈÇ k -ÃÐÀÌÌ ÇÍÀÊÎÂ ÎÖÅÍÎÊ ÍÎÐÌÈÐÎÂÀÍÍÛÕ
ÊÎÝÔÔÈÖÈÅÍÒÎÂ ÊÎÐÐÅËßÖÈÈ
Äëÿ àíàëèçà ïîñëåäîâàòåëüíîñòè çíàêîâ { }zi ( )� îöåíîê íîðìèðîâàííûõ êîýôôèöè-
åíòîâ êîððåëÿöèè ri ( )� âûïîëíèì ïðåîáðàçîâàíèå z ri i( ) ( ( ( )) . )� �� �sign sign 0 5 ,
êîòîðîå ïîçâîëèò ïîëó÷èòü ìíîæåñòâî çíà÷åíèé { }zi ( )� , ñîñòîÿùåå èç äâóõ
ýëåìåíòîâ: �1 è �1 .
Ïîñêîëüêó çíàìåíàòåëü â (1) ïîëîæèòåëüíûé, âìåñòî îöåíêè êîýôôèöèåíòà
êîððåëÿöèè ri ( )� ìîæíî èñïîëüçîâàòü îöåíêó êîýôôèöèåíòà êîâàðèàöèè cov i ( )�
èëè C Li segm i( ) ( )� �� cov :
C x i L l x i L li segm segm
l
( ) [ ( ( ) ) (( ) ( ) )]� � �� � � � � �
�
� �
1
0
Lsegm�
1
. (3)
Òîãäà ïîñëåäîâàòåëüíîñòü çíàêîâ
{ } sign sign { } sign sign { }z C ri i i( ) ( ( ) . ) ( ( ) .� � �� � � �0 5 0 5). (4)
Òàêèì îáðàçîì, ïðè àíàëèçå êàæäîé ïîñëåäîâàòåëüíîñòè ïîëó÷èì ìíîæåñòâî çíà-
÷åíèé { }zi ( )� , ãäå i i� �[ , ( ) ]max0 1� , imax ( )� âû÷èñëÿåòñÿ ïî (2), à � � �1 Lsegm .
Äëÿ êàæäîé ïîñëåäîâàòåëüíîñòè { }zi ( )� ñ ôèêñèðîâàííûì � ïðîâåðèì ãèïîòå-
çó î ðàâíîìåðíîñòè ðàñïðåäåëåíèÿ k-ãðàìì çíàêîâ äëÿ k � 1 ñ ïîìîùüþ ñòàòèñòè-
÷åñêîãî êðèòåðèÿ �2 [13]. Çàìåòèì, ÷òî â ñîîòâåòñòâèè ñ ðåêîìåíäàöèÿìè Êíó-
òà [4] äàííûé àíàëèç òðåáóåò ðàçáèåíèÿ ïîñëåäîâàòåëüíîñòè { }zi ( )� íà íåïåðåêðû-
âàþùèåñÿ îòðåçêè èç k çíàêîâ (k-ãðàììû) âèäà { }z z zkj kj kj k( ), ( ), , ( )� � �� � �1 1� .
 ðåçóëüòàòå ïðîâåðêè ðàâíîìåðíîñòè ðàñïðåäåëåíèÿ k-ãðàìì çíàêîâ ïîëó÷èì
ìíîæåñòâî çíà÷åíèé ñòàòèñòèêè { }� �2 ( , )k , k K�[ , ]1 .
118 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2
Ïîäîáíûé àíàëèç âûïîëíÿåòñÿ äëÿ áîëüøîãî êîëè÷åñòâà N âûáîðîê ãåíåðà-
òîðà ñëó÷àéíûõ èëè ïñåâäîñëó÷àéíûõ ÷èñåë.  ðåçóëüòàòå ôîðìèðóåòñÿ íàáîð
çíà÷åíèé { }� �n k2 ( , ) , ãäå n N�[ , ]1 .
Äëÿ êàæäîé ïàðû ( , )k � âû÷èñëèì îòíîñèòåëüíóþ ÷àñòîòó ïîïàäàíèÿ ñòàòèñ-
òèêè � �n k2 ( , ) â êðèòè÷åñêóþ îáëàñòü ( ; )
,
�
�1
2
�
m
ïðè çàäàííîì óðîâíå çíà÷èìîñ-
òè � è m k� �2 1:
W k N k NB( , , ) ( , , ) /� � � �� , (5)
ãäå N kB ( , , )� � — ÷èñëî ïîÿâëåíèé ñîáûòèÿ B kn m
� �
�
{ }� � �
�
2
1
2( , )
,
â N èñ-
ïûòàíèÿõ ( [ , ])n N� 1 .
Âåëè÷èíà N kB ( , , )� � , à çíà÷èò è W k( , , )� � , ÿâëÿåòñÿ ñëó÷àéíîé. Îïðåäåëèì
èíòåðâàë ( ( , ), ( , ))min maxW W� � � � , ñèììåòðè÷íûé îòíîñèòåëüíî ìàòåìàòè÷åñêî-
ãî îæèäàíèÿ ñ.â. W k( , , )� � , â êîòîðûé îíà ïîïàäàåò ñ âåðîÿòíîñòüþ
P W W k W{ }min max( , ) ( , , ) ( , )� � � � � � �� � � .
Äëÿ ðåøåíèÿ äàííîé çàäà÷è óñòàíîâèì çàêîí ðàñïðåäåëåíèÿ îòíîñèòåëüíîé
÷àñòîòû ïîïàäàíèÿ ñòàòèñòèêè � �n k2 ( , ) â êðèòè÷åñêóþ îáëàñòü ( ; )
,
�
�1
2
�
m
. Äëÿ
ýòîãî âû÷èñëèì çíà÷åíèÿ W k( , , )� � ïðè ðàñòÿãèâàíèè îòðåçêîâ ( )0 255� �� äëÿ
N �1000 ïîñëåäîâàòåëüíîñòåé àòìîñôåðíûõ øóìîâ. Ïîñêîëüêó íåïåðåñåêàþùè-
åñÿ îòðåçêè ñòàöèîíàðíîãî áåëîãî øóìà íåêîððåëèðîâàíû ìåæäó ñîáîé, ðàñïðå-
äåëåíèå W k( , , )� � èíâàðèàíòíî ïî îòíîøåíèþ ê âåëè÷èíå � � 0. Ãðàôèêè ïîëèãî-
íîâ ÷àñòîò çíà÷åíèé W k( , , )� � , âû÷èñëåííûõ äëÿ � �[ , ]0 255 , â çàâèñèìîñòè îò
íåêîòîðûõ ïàðàìåòðîâ k è � ïðåäñòàâëåíû íà ðèñ. 2, ãäå øòðèõîâîé ëèíèåé âû-
ïîëíåíû ãðàôèêè ïðè íîðìàëüíîì çàêîíå ðàñïðåäåëåíèÿ ñ ìàòåìàòè÷åñêèì
îæèäàíèåì � è äèñïåðñèåé � �( ) /1� N .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2 119
Ðèñ. 2. Ãðàôèêè ïîëèãîíîâ ÷àñòîò ïîïàäàíèÿ ñòàòèñòèêè � �2 ( , )k â êðèòè÷åñêóþ îáëàñòü äëÿ k � 1
è � � 0 01. (à); k � 1 è � � 0 05. (á); k � 2 è � � 0 025. (â); k � 2 è � � 0 1. (ã)
à
×àñòîòà
á
W k( , , )� �
×àñòîòà
ãâ
W k( , , )� �
Ñîîòâåòñòâèå ýìïèðè÷åñêèõ ðàñïðåäåëåíèé çíà÷åíèé W k( , , )� � äëÿ àòìîñ-
ôåðíîãî øóìà òåîðåòè÷åñêîìó ïðåäåëüíîìó (íîðìàëüíîìó) ïîäòâåðæäàåòñÿ ðå-
çóëüòàòàìè ïðîâåðêè ïî êðèòåðèþ �2 Ïèðñîíà [13], î ÷åì ñâèäåòåëüñòâóþò äîñ-
òèãíóòûå óðîâíè çíà÷èìîñòè ( p-value), ïðèâåäåííûå â òàáë. 1.
Ïðîâåðêà ñîîòâåòñòâèÿ ýìïèðè÷åñêîãî ðàñïðåäåëåíèÿ çíà÷åíèé ôóíêöèè
W k( , , )� � (ïðè � � 0 è ôèêñèðîâàííûõ � è k ) íîðìàëüíîìó çàêîíó ñ ìàòåìàòè-
÷åñêèì îæèäàíèåì � è äèñïåðñèåé � � �2 1� �( ) / N ÿâëÿåòñÿ îäíèì èç ýòàïîâ
ðàçðàáàòûâàåìîãî ìåòîäà òåñòèðîâàíèÿ. Íåïðîõîæäåíèå äàííîãî ýòàïà ïðèâîäèò
ê íåïðîõîæäåíèþ âñåãî òåñòà. Îòìåòèì, ÷òî êâàíòîâûé ÃÑ× [20] è «Âèõðü Ìåð-
ñåííà» MT19937 [10] óñïåøíî ïðåîäîëåâàþò äàííûé ýòàï.
 ñèëó òîãî, ÷òî äëÿ áåëîãî øóìà ñ.â. W k( , , )� � ÿâëÿåòñÿ íîðìàëüíî
ðàñïðåäåëåííîé, äëÿ îïðåäåëåíèÿ âåðîÿòíîñòè åå ïîïàäàíèÿ â èíòåðâàë
( ( , ), ( , ))min maxW W� � � � èñïîëüçóåòñÿ âûðàæåíèå
� �(( ( , ) ) / ) (( ( , ) ) / )max minP P� � � � � � � �� � � ,
ãäå �( )x — ôóíêöèÿ Ëàïëàñà. Òîãäà íèæíèé Wmin ( , )� � è âåðõíèé Wmax ( , )� �
ïðåäåëû èíòåðâàëà èìåþò âèä:
W t N W tmin ( ) / max ( )/( , ) ( ) / , ( , )� � � � � � � � �� �� � � � �� �1 2 1 21 ( ) / ,1� � N (6)
ãäå t( )/1 2� � — êâàíòèëü ñòàíäàðòíîãî íîðìàëüíîãî ðàñïðåäåëåíèÿ ñ óðîâíåì
( ) /1 2� � .
ÂÛ×ÈÑËÅÍÈÅ ÁÀÐÜÅÐÍÎÉ ÔÓÍÊÖÈÈ
Ðàññìîòðèì ñòàòèñòè÷åñêèå îñîáåííîñòè ïðè � �[ , ]1 1� �Lsegm .
Îïðåäåëåíèå 1. Áàðüåðíîé ôóíêöèåé � � �min ( , , )k áóäåì íàçûâàòü ñëó÷àé-
íóþ ôóíêöèþ ïàðàìåòðà � , ðàâíóþ ìèíèìàëüíîìó çíà÷åíèþ � �, �� 0 , ïðè êîòî-
ðîì îòíîñèòåëüíàÿ ÷àñòîòà W k( , , )� � ïîïàäàíèÿ ñòàòèñòèêè � �n k2 ( , ) â êðèòè÷åñ-
êóþ îáëàñòü ( ; )
,
�
�1
2
�
m
ïðåâûøàåò âåðõíþþ ãðàíèöó Wmax ( , )� � :
� � � � � � � �min max( , , ) min ( : ( , , ) ( , ))k W k W� � � �0 . (7)
Ñòàòèñòè÷åñêèé ñìûñë áàðüåðíîé ôóíêöèè � � �min ( , , )k ñîñòîèò â òîì, ÷òî
ïðè ôèêñèðîâàííûõ çíà÷åíèÿõ ( , , )k � � îíà âûÿâëÿåò «ïîðîã» � �min , âûøå êîòî-
ðîãî (� �� � min ) íàáëþäàåòñÿ ðàâíîìåðíîå ðàñïðåäåëåíèå k-ãðàìì çíàêîâ ýìïè-
ðè÷åñêîé êîððåëÿöèîííîé ôóíêöèè (1) èññëåäóåìîé ïîñëåäîâàòåëüíîñòè
ñëó÷àéíûõ ÷èñåë.
Äëÿ íîðìàëüíî ðàñïðåäåëåííîé ñ.â. W k( , , )� � ñïðàâåäëèâû ñëåäóþùèå
óòâåðæäåíèÿ:
— ïðè � �' ''� � 0 5. : � �
� �1
2
1
2
� �
�
' '', ,m m
, ïîýòîìó W k W k( , , ) ( , , )� � � �' ' '� ;
— ïðè � �' ''� � 0 5. : � � � �' ' ' ' ''( ) ( )1 1� � � , ñëåäîâàòåëüíî, Wmax ( , )� �' �
� Wmax ( , )� �' ' , à W W W Wmax min max min( , ) ( , ) ( , ) ( , )� � � � � � � �' ' ' ' ' '� � � .
120 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2
Ò à á ë è ö à 1 . Ðåçóëüòàòû ïðîâåðêè ãèïîòåçû î íîðìàëüíîñòè ðàñïðåäåëåíèÿ
îòíîñèòåëüíîé ÷àñòîòû ïîïàäàíèÿ ñòàòèñòèêè � �n k2 ( , ) â êðèòè÷åñêóþ îáëàñòü
Óðîâåíü çíà÷èìîñòè � � � 0.01 � � 0.025 � � 0.05 � � 0.1
Äëèíà k -ãðàììû k � 1 k � 2 k � 1 k � 2 k � 1 k � 2 k � 1 k � 2
p-value 0.445 0.495 0.676 0.798 0.287 0.808 0.391 0.451
Èíûìè ñëîâàìè, ïðè óâåëè÷åíèè óðîâíÿ çíà÷èìîñòè � êðèòè÷åñêàÿ îáëàñòü
( ; )
,
�
�1
2
�
m
ðàñøèðÿåòñÿ. Ñëåäîâàòåëüíî, îòíîñèòåëüíàÿ ÷àñòîòà ïîïàäàíèÿ ñòà-
òèñòèêè � �n k2 ( , ) â êðèòè÷åñêóþ îáëàñòü íå óìåíüøàåòñÿ (ïðè N �
íåðàâå-
íñòâî ïðèîáðåòàåò âèä ñòðîãîãî). Ïðè óâåëè÷åíèè óðîâíÿ çíà÷èìîñòè ðàñøèðÿ-
åòñÿ òàêæå èíòåðâàë ( ( , ), ( , ))min maxW W� � � � .
Çàìå÷àíèå 1. Îáå ÷àñòè íåðàâåíñòâà W k W( , , ) ( , )max� � � �� èç (7) ìîíîòîí-
íî âîçðàñòàþùèå ïî � . Â òî æå âðåìÿ � � �min ( , , )k ìîæåò áûòü íå ìîíîòîííîé
ïî � .
ÊÐÈÒÅÐÈÉ ÁÀÐÜÅÐÍÎÉ ÔÓÍÊÖÈÈ È ÅÃÎ ÏÐÈÌÅÍÅÍÈÅ
Ðåàëèçàöèÿ áàðüåðíîé ôóíêöèè. Èññëåäóåì ïîâåäåíèå áàðüåðíîé ôóíêöèè
� � �min ( , , )k â çàâèñèìîñòè îò óðîâíÿ çíà÷èìîñòè � . Äëÿ ýòîãî ïðè ôèêñèðî-
âàííîì � , k K�[ , ]1 è N �1000 âû÷èñëèì ïîñëåäîâàòåëüíîñòü çíà÷åíèé
� � �min ( , , )k äëÿ � � ��[ , ]1 2 ñ øàãîì � � � � �� �( ) /2 1 N , ãäå ( )N � �1 — êîëè-
÷åñòâî çíà÷åíèé � .
Ïóñòü � �[ . , . ]0 01 0 1 , N � � { }20 30 45 90, , , , � � 0 95. , à K � 2. Ãðàôèêè çàâèñè-
ìîñòåé çíà÷åíèé ôóíêöèè � � �min ( , , )k îò � �[ . , . ]0 01 0 1 äëÿ N � � { }20 45, è k �1
ïðåäñòàâëåíû íà ðèñ. 3, ãäå âèäíû ñóùåñòâåííûå îòëè÷èÿ äëÿ ðàçëè÷íûõ èñòî÷-
íèêîâ. Ïðèìåì òî÷êè íà ãðàôèêàõ ðåàëèçàöèÿìè íåêîòîðûõ ñ.â. è âû÷èñëèì äëÿ
íèõ âûáîðî÷íûå äèñïåðñèè. Ïîëó÷åííûå ðåçóëüòàòû (òàáë. 2) ïîêàçûâàþò, ÷òî
äèñïåðñèÿ D k( ( , , ))min� � � ìèíèìàëüíà äëÿ àòìîñôåðíîãî øóìà è çíà÷èòåëüíî
ìåíüøàÿ, ÷åì ó äðóãèõ èñòî÷íèêîâ.
Êðèòåðèé áàðüåðíîé ôóíêöèè. Äëÿ ðàçðàáîòêè êðèòåðèÿ, õàðàêòåðèçóþ-
ùåãî ïîñòîÿíñòâî áàðüåðíîé ôóíêöèè, èñïîëüçóåì ñòàòèñòè÷åñêóþ ìåòîäîëîãèþ
èíòåðïðåòàöèè çàâèñèìîñòåé � � �min ( , , )k . Ïðèìåíÿåìûé ìåòîä îñíîâàí íà èäå-
îëîãèè êðèòåðèÿ �2 Ïèðñîíà è ñîñòîèò â òîì, ÷òî äëÿ êîëè÷åñòâåííîé îöåíêè
íàáëþäàåìûõ ñòàòèñòè÷åñêèõ íåðåãóëÿðíîñòåé ïîëó÷åííûå ïîñëåäîâàòåëüíîñòè
çíà÷åíèé áàðüåðíîé ôóíêöèè � � �min ( , , )k ïðè � � ��[ , ]1 2 ñ øàãîì � � è ôèêñè-
ðîâàííûìè � è k ðàññìàòðèâàþòñÿ êàê ÷àñòîòû ïðè ðåàëèçàöèè ñòàòèñòè÷åñêîãî
ýêñïåðèìåíòà ñ N � �1 âîçìîæíûìè èñõîäàìè.  ýòîì ñëó÷àå ãðàôèêè (ñì. ðèñ. 3)
ÿâëÿþòñÿ ïîëèãîíàìè ÷àñòîò äèñêðåòíûõ ñ.â.
Ïîñêîëüêó â êà÷åñòâå èñòî÷íèêà ýòàëîííîãî áåëîãî øóìà âûáðàí èñòî÷íèê
àòìîñôåðíîãî øóìà [19], à òàêæå â ñîîòâåòñòâèè ñ âèäîì ñîîòâåòñòâóþùèõ åìó
íà ðèñ. 3 ïîëèãîíîâ ÷àñòîò, òåîðåòè÷åñêèì çàêîíîì ðàñïðåäåëåíèÿ ÿâëÿåòñÿ
ðàâíîìåðíûé çàêîí.
Òàêèì îáðàçîì, êðèòåðèé áàðüåðíîé ôóíêöèè ïðåäóñìàòðèâàåò ñëåäóþùóþ
ïðîâåðêó. Ýìïèðè÷åñêîå ðàñïðåäåëåíèå ñ îòíîñèòåëüíûìè ÷àñòîòàìè � ��k , ( ) �
�
�
� � � � � �
� �
�
min min( , , ) / ( , , )k k
1
2
ñðàâíèâàåòñÿ ñ òåîðåòè÷åñêèì ïðåäåëüíûì (ðàâ-
íîìåðíûì) ïî êðèòåðèþ �2 Ïèðñîíà ïðè çàäàííîì óðîâíå çíà÷èìîñòè �. Èññëå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2 121
Òàáëèöà 2. Âûáîðî÷íûå äèñïåðñèè D k( ( , , ))min� � � â çàâèñèìîñòè îò N a è k
Èñòî÷íèê
N a � 20 N a � 30 N a � 45 N a � 90
k � 1 k � 2 k � 1 k � 2 k � 1 k � 2 k � 1 k � 2
Àòìîñôåðíûé øóì 0.43 2.03 2.77 2.48 1.69 1.99 1.48 2.03
Êâàíòîâûé ÃÑ× 27.53 3.73 25.10 5.91 23.35 5.91 25.63 5.86
Ãåíåðàòîð ÌÒ19937 36.16 9.23 26.12 9.21 30.42 9.42 30.06 9.13
äóåìûé èñòî÷íèê óäîâëåòâîðÿåò êðèòåðèþ áàðüåðíîé ôóíêöèè, åñëè äëÿ âñåõ
k K�[ , ]1 ïîëó÷åííûå ñòàòèñòèêè �2 íå ïîïàäàþò â êðèòè÷åñêóþ îáëàñòü.
Ïðèìåíåíèå êðèòåðèÿ áàðüåðíîé ôóíêöèè. Äëÿ èññëåäóåìûõ èñòî÷íèêîâ
ïðîâåðèì ñîîòâåòñòâèå ïîëó÷åííûõ ýìïèðè÷åñêèõ ðàñïðåäåëåíèé ñ îòíîñèòåëüíû-
ìè ÷àñòîòàìè � ��k , ( ) ðàâíîìåðíîìó çàêîíó ïî êðèòåðèþ �2 Ïèðñîíà. Äîñòèãíóòûå
óðîâíè çíà÷èìîñòè äëÿ H Nk0 1 1: ( ) / ( ),{ }� �� �� � ïðèâåäåíû â òàáë. 3.
Ïîëó÷åííûå ðåçóëüòàòû ñâèäåòåëüñòâóþò î òîì, ÷òî ðàâíîìåðíîìó çàêîíó
ñîîòâåòñòâóåò ðàñïðåäåëåíèå ñ àáñîëþòíûìè ÷àñòîòàìè � � �min ( , , )k òîëüêî äëÿ
ïîñëåäîâàòåëüíîñòåé àòìîñôåðíîãî øóìà. Êâàíòîâûé ÃÑ× è ãåíåðàòîð MT19937
íå óäîâëåòâîðÿþò ðàçðàáîòàííîìó êðèòåðèþ. Íåïðîõîæäåíèå òåñòà êâàíòîâûì
ÃÑ× ìîæåò ÿâëÿòüñÿ ñëåäñòâèåì èñïîëüçîâàíèÿ íåîïòèìàëüíîãî ïðåîáðàçîâàíèÿ
êâàíòîâûõ ÿâëåíèé â ïîñëåäîâàòåëüíîñòü ñëó÷àéíûõ ÷èñåë.
122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2
Ðèñ. 3. Ãðàôèêè çàâèñèìîñòåé � � �min ( , , )k îò � �[ . , . ]0 01 01 ïðè k � 1 äëÿ: àòìîñôåðíîãî øóìà
ïðè N � � 20 (à) è N � � 45 (á); êâàíòîâîãî ÃÑ× ïðè N � � 20 (â) è N � � 45 (â); ãåíåðàòîðà
MT19937 ïðè N � � 20 (ä) è N � � 45 (å)
à á
ãâ
ä å
�
� � �min ( , , )k � � �min ( , , )k
�
�
Çàìåòèì, ÷òî âûáîð çíà÷åíèÿ N � íå îêàçûâàåò ñóùåñòâåííîãî âëèÿíèÿ íà ðå-
çóëüòàòû ýêñïåðèìåíòà. Ïîýòîìó N � ìîæíî âûáèðàòü êàê ìèíèìàëüíîå çíà÷åíèå,
ïðè êîòîðîì ïðàâîìåðíî èñïîëüçîâàíèå êðèòåðèÿ �2 äëÿ ïðîâåðêè ðàâíîìåðíîñòè
äèñêðåòíîãî ðàñïðåäåëåíèÿ: � � �
�
min ( , , )k
�100 èëè N N N� � �� � �min ( ):( )1
� �� � �min ( , , )k 100, ãäå � � � � � �min min( , , ) ( , , ) / ( )k k N
a
a�
�
�
�
�
�
�
�
�
�
1 — âûáîðî÷-
íîå ñðåäíåå.
ÌÅÒÎÄÈÊÀ ÏÐÈÌÅÍÅÍÈß ÊÐÈÒÅÐÈß
Ìåòîäèêà ïðèìåíåíèÿ ðàçðàáîòàííîãî êðèòåðèÿ âêëþ÷àåò ñëåäóþùèå ýòàïû:
— àíàëèçèðóþòñÿ N ïîñëåäîâàòåëüíîñòåé ãåíåðàòîðà (N � 1000);
— êàæäàÿ ïîñëåäîâàòåëüíîñòü äëèíû Lseq (Lseq � 256256) ðàçáèâàåòñÿ íà îò-
ðåçêè äëèíû Lsegm (L Msegm � � 256), ðàññòîÿíèå ìåæäó ñîñåäíèìè îòðåçêàìè
� � �1 Lsegm , êîëè÷åñòâî îòðåçêîâ ðàâíî imax ( )� �1, imax ( )� âû÷èñëÿåòñÿ ïî (2);
— äëÿ êàæäîé ïîñëåäîâàòåëüíîñòè âû÷èñëÿåòñÿ ìíîæåñòâî îöåíîê { }ri ( )� (1)
èëè { }Ci ( )� (3), i i� �[ , ( ) ]max0 1� ;
— ìíîæåñòâî { }ri ( )� ïðåîáðàçóåòñÿ â ìíîæåñòâî { }zi ( )� (4);
— ñ ïîìîùüþ êðèòåðèÿ �2 äëÿ ïîñëåäîâàòåëüíîñòåé { }zi ( )� ïðè ôèêñèðî-
âàííîì � ïðîâåðÿåòñÿ ãèïîòåçà î ðàâíîìåðíîñòè ðàñïðåäåëåíèÿ k-ãðàìì äëÿ
k K�[ , ]1 (K � 2), â ðåçóëüòàòå ÷åãî ôîðìèðóåòñÿ ìíîæåñòâî çíà÷åíèé ñòàòèñòèêè
{ }� �2 ( , )k äëÿ îäíîé ïîñëåäîâàòåëüíîñòè è { }� �n k2 ( , ) ( [ , ])n N� 1 — äëÿ N ïîñëå-
äîâàòåëüíîñòåé;
— äëÿ êàæäîé ïàðû ( , )k � âû÷èñëÿåòñÿ ôóíêöèÿ W k( , , )� � (5) ïðè
� � ��[ , ]1 2 ñ øàãîì �� � � �� �( ) /2 1 N , �1 0 01� . , � 2 0 1� . , N � � 20;
— ñ ïîìîùüþ êðèòåðèÿ �2 ïðîâåðÿåòñÿ ñîîòâåòñòâèå ýìïèðè÷åñêîãî ðàñ-
ïðåäåëåíèÿ çíà÷åíèé ôóíêöèè W k( , , )� � äëÿ � � 0 (ïðè ôèêñèðîâàííûõ � è k)
íîðìàëüíîìó çàêîíó ñ ìàòåìàòè÷åñêèì îæèäàíèåì � è äèñïåðñèåé
� � �2 1� �( ) / N (íåïðîõîæäåíèå äàííîãî ýòàïà ïðèâîäèò ê íåïðîõîæäåíèþ âñå-
ãî òåñòà);
— äëÿ êàæäîãî � îïðåäåëÿåòñÿ èíòåðâàë ( ( , ), ( , ))min maxW W� � � � (6);
— âû÷èñëÿþòñÿ çíà÷åíèÿ áàðüåðíîé ôóíêöèè � � �min ( , , )k (7);
— äëÿ âû÷èñëåííûõ çíà÷åíèé � � �min ( , , )k ïðèìåíÿåòñÿ êðèòåðèé áàðüåð-
íîé ôóíêöèè;
— òåñò ïðîéäåí, åñëè äëÿ âñåõ k K�[ , ]1 ïîëó÷åííûå ñòàòèñòèêè êðèòåðèÿ
áàðüåðíîé ôóíêöèè íå ïîïàäàþò â êðèòè÷åñêóþ îáëàñòü ïðè çàäàííîì óðîâíå
çíà÷èìîñòè � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2 123
Ò à á ë è ö à 3. Ðåçóëüòàòû ïðîâåðêè ãèïîòåçû î ðàâíîìåðíîñòè ýìïèðè÷åñêîãî
ðàñïðåäåëåíèÿ ñ ÷àñòîòàìè � � �min ( , , )k ïðè a �[ . , . ]0 01 0 1 è � � 0 95. â çàâèñè-
ìîñòè îò N a è k
Èñòî÷íèê
Äîñòèãíóòûé óðîâåíü çíà÷èìîñòè (p-value)
N a � 20 N a � 30 N a � 45 N a � 90
k � 1 k � 2 k � 1 k � 2 k � 1 k � 2 k � 1 k � 2
Àòìîñôåðíûé øóì 1.0000 0.9977 0.9999 0.9989 1.0000 1.0000 1.0000 1.0000
Êâàíòîâûé ÃÑ× 0.0000 0.7538 0.0000 0.4915 0.0000 0.4446 0.0000 0.4744
Ãåíåðàòîð ÌÒ19937 0.0004 0.0109 0.0164 0.0037 0.0000 0.0005 0.0000 0.0000
ÇÀÊËÞ×ÅÍÈÅ
 ðåçóëüòàòå ïðîâåäåííîãî èññëåäîâàíèÿ ðàçðàáîòàíû íîâûå ìåòîä è êðèòå-
ðèé îöåíèâàíèÿ êà÷åñòâà ïîñëåäîâàòåëüíîñòåé ðàâíîìåðíî ðàñïðåäåëåííûõ
ñëó÷àéíûõ è ïñåâäîñëó÷àéíûõ ÷èñåë, ïîçâîëÿþùèå âûÿâëÿòü â íèõ íå îáíàðó-
æåííûå äî íàñòîÿùåãî âðåìåíè ñòàòèñòè÷åñêèå íåðåãóëÿðíîñòè. Îïðåäåëåíî,
÷òî òîëüêî âûáðàííûé â êà÷åñòâå ýòàëîíà àòìîñôåðíûé øóì [19] ñîîòâåòñòâó-
åò ðàçðàáîòàííîìó êðèòåðèþ, à êâàíòîâûé ÃÑ× [20] è ãåíåðàòîð MT19937 [10]
íå óäîâëåòâîðÿþò ïðåäúÿâëÿåìûì òðåáîâàíèÿì.
Ïîëó÷åííûå ðåçóëüòàòû èìåþò áîëüøîå òåîðåòè÷åñêîå è ïðàêòè÷åñêîå çíà-
÷åíèå ïðè îöåíèâàíèè êà÷åñòâà ïîñëåäîâàòåëüíîñòåé ñëó÷àéíûõ ÷èñåë è èõ
ìîæíî èñïîëüçîâàòü â ñïåöèàëèçèðîâàííûõ ïðèêëàäíûõ ïàêåòàõ òåñòèðîâàíèÿ
òåõíè÷åñêèõ ñðåäñòâ ôîðìèðîâàíèÿ ïîñëåäîâàòåëüíîñòåé ñëó÷àéíûõ è ïñåâäîñëó-
÷àéíûõ ÷èñåë.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B r o w n R . G . Introduction to random signal analysis and Kalman filtering. — New York: John
Wiley and Sons, 1983. — 347 p.
2. P a p o u l i s A . Probability, random variables, and stochastic processes. — 3rd ed. — New York:
McGraw-Hill, 1991. — 666 p.
3. È â à í î â Ì . À . , × ó ã ó í ê î â È .  . Òåîðèÿ, ïðèìåíåíèå è îöåíêà êà÷åñòâà ãåíåðàòîðîâ
ïñåâäîñëó÷àéíûõ ïîñëåäîâàòåëüíîñòåé. — Ì.: ÊÓÄÈÖ-ÎÁÐÀÇ, 2003. — 240 ñ.
4. K n u t h D . E . The art of computer programming: In 7 vol. Vol. 2: Seminumerical algorithms. —
3rd ed. — Reading (Massachusetts): Addison Wesley Longman Publishing Co., 1998. — 762 p.
5. Ï î ò î ÷ í û å øèôðû. Ðåçóëüòàòû çàðóáåæíîé îòêðûòîé êðèïòîëîãèè. — http://www.ssl.stu.
neva.ru/psw/crypto/potok/str_ciph.htm.
6. R o b s h a w M . J . B . Stream ciphers. Technical Report TR-701, V. 2.0. — RSA Lab., 1995. — 42 p.
7. M a r s a g l i a G . DIEHARD battery of tests of randomness. — http://www.stat.fsu.edu/pub/diehard.
8. R u k h i n A . e t a l . A statistical test suite for random and pseudorandom number generators for
cryptographic applications. Spec. Pub. 800-22 rev. 1a. — Gaithersburg, MD, NIST, 2010. — 131 p.
9. L ’ e c u y e r P . , S i m a r d R . TestU01: A C library for empirical testing of random number
generators // ACM TOMS. — 2007. — 33, N 4. — Article 22. — 40 p.
10. M a t s u m o t o M . , N i s h i m u r a T . Mersenne twister: A 623-dimensionally equidistributed
uniform pseudorandom number generator // ACM TOMACS. — 1998. — 8. — P. 3–30.
11 S o t o J . Statistical testing of random number generators // Proceedings of the 22nd National
Information Systems Security Conference. — Gaithersburg, MD: NIST, 1999. — 10. — 12 p.
12. C o l l i n s J . C . Testing, selection, and implementation of random number generators. Rep.
ARL-TR-4498. — Aberdeen Proving Ground, MD: U.S. Army Research Laboratory, 2008. — 76 p.
13. Ñ ì è ð í î â Í . Â . , Ä ó í è í - Á à ð ê î â ñ ê è é È . Â . Êóðñ òåîðèè âåðîÿòíîñòåé è ìàòåìàòè-
÷åñêîé ñòàòèñòèêè äëÿ òåõíè÷åñêèõ ïðèëîæåíèé. — Ì.: Íàóêà, 1969. — 512 ñ.
14. K e n d a l l M . G . The advanced theory of statistics. — V. II. — London: C. Griffin&Co, 1946. —
521 p.
15. D i r a c P . A . M . The principles of quantum mechanics. — 4th ed. — London: OUP, 1958. — 314 p.
16. Á î ë ü ø å â Ë . Í . , Ñ ì è ð í î â Í .  . Òàáëèöû ìàòåìàòè÷åñêîé ñòàòèñòèêè. — 3-å èçä. —
Ì.: Íàóêà, 1983. — 416 ñ.
17. Ô à ó ð å Ý . Â . , Ù å ð á à À . È . , Ë à â ä à í ñ ê è é À . À . Àíàëèç êîððåëÿöèîííûõ ñâîéñòâ
ïîñëåäîâàòåëüíîñòåé (ïñåâäî) ñëó÷àéíûõ ÷èñåë // Íàóêà ³ òåõí³êà Ïîâ³òðÿíèõ Ñèë Çáðîéíèõ
Ñèë Óêðà¿íè. — 2015. — ¹ 1 (18) — Ñ. 142–150.
18. Ë à â ä à í ñ ê è é À . À . , Ô à ó ð å Ý . Â . Êîìáèíàöèîííûé ìåòîä ôîðìèðîâàíèÿ ïîñëåäîâà-
òåëüíîñòè ïñåâäîñëó÷àéíûõ ÷èñåë // Ñèñòåìíèé àíàë³ç òà ³íôîðìàö³éí³ òåõíîëî㳿: Ìàòåð³àëè
16-¿ ̳æíàðîäíî¿ íàóêîâî-òåõí³÷íî¿ êîíôåðåíö³¿ SAIT-2014, Êè¿â, 26–30 òðàâíÿ 2014 ð. ÍÍÊ
«²ÏÑÀ» ÍÒÓÓ «Êϲ». — Ê.: ÍÍÊ «²ÏÑÀ» ÍÒÓÓ «Êϲ», 2014. — Ñ. 403–404.
19. H a a h r M . True random number service. — http://random.org/.
20. Q R N G Service. — http://qrng.physik.hu-berlin.de/.
Ïîñòóïèëà 22.09.2015
124 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 2
|