Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 27
Текст из файла (страница 27)
р < а, то последовательность ё признается неслучайной; в противном случае (при р ^ а) последовательность считается случайной.Отметим, что большие значения статистики s соответствуют слишкомчастой смене единичных и нулевых значений в исследуемой последовательности, а малые — слишком редкой.П.1.4. T E S T FOR T H E L O N G E S T R U N O F O N E S IN A B L O C KОбъектом исследования являются единичные серии наибольшей длины в подпоследовательностях длины М последовательности ё.
В процессетеста определяется, согласуется ли количество блоков, содержащих максимальные серии определенной длины, с ожидаемым для случайных последовательностей значением.Отметим, что отклонения в распределении единичных серий влекутза собой отклонения в распределении нулевых серий, поэтому достаточноосуществить только один из двух тестов.Параметры.1) ё — исследуемая последовательность, ё = е\, в2, • •.,£п',2) п — длина исследуемой последовательности;3) М — длина блока (фиксированное значение 8, 128 или 10 000 в зависимости от п, см. табл. 12).Процедура тестирования.1) исходная последовательность ё разбивается на подпоследовательностидлины М;2) все подпоследовательности разделяются на классы щ в зависимостиот максимальной длины А; серии из единиц; соответствие классов щи длин серий для некоторых значений длины подпоследовательностейМ приведено в табл.
12);3) рассчитывается значение статистики_ * ( Н - ТУтг,)2г=0где \щ\ — число подпоследовательностей, отнесенных к классу иг, азна--178чения К, N и 7Ti могут быть получены из табл. 12;4) вычисляется достигаемый уровень значимостиp = igamc(T,£).Таблица 12.Параметры теста для некоторых значений длиныподпоследовательностей ММ =8щV\у%"3k^l,7Г0 =к = 2, тг1 =к = 3, 7г2 =к ^ 4, 7г3 =0,21480,36720,23050,1875щVbМ = 128М = 10000к < 4, 7г0 = 0,1174А; = 5, 7Г1 = 0,2430fc = 6, 7г2 - 0,2493/с = 7, тгз = 0,1752/с = 8, тг4 = 0,1027/с ^ 9, 7г5 = 0,1124/с < 10, 7г0 = 0,0882к = 11, 7Г1 = 0,2092А: = 12, 7г2 = 0,2483/с = 13, 7г3 = 0,1933/с = 14, тг4 = 0,1208к = 15, тг5 = 0,0675к ^ 16, тг6 = 0,0727^ 6 272549^ 750 000675ЩпКN^ 128316Рекомендации по выбору параметров.Длина последовательности п должна быть не менее 128 бит (n ^ 128).Значение длины подпоследовательностей М определяется величиной п всоответствии с табл.
12.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е. р < а, то последовательность ё признается неслучайной; в противном случае (при р ^ а) последовательность считается случайной.Большие значения статистики s соответствуют наличию в последовательности кластеров из единиц.-179П.1.5.
BINARY MATRIX RANK T E S TОбъектом исследования является ранг двоичных матриц, образованных непересекающимися подпоследовательностями последовательности е.Тест направлен на выявление линейной зависимости между подпоследовательностями фиксированной длины. Отметим, что он также входит в н а б о рDIEHARD [51].Параметры.1) ё — исследуемая последовательность, ё = ei, £2, • • •, £п',2) п —длина исследуемой последовательности;3) М — количество строк в каждой матрице (фиксированное значениеМ = 32);4) Q — количество столбцов в каждой матрице (фиксированное значениеg = 32).Процедура тестирования.Описание процедуры тестирования приведено для значений М — Q=32. В случае использования других значений должны быть рассчитаныновые константы в выражении (П.1) вычисления статистики теста.1) исходная последовательность ё разбивается наN =п\_MQ\непересекающихся подпоследовательностей длины М каждая; н е и с пользованные члены в конце последовательности отбрасываются;2) члены подпоследовательностей используются для заполнения д в о и ч ных матриц размера М х Q (заполнение осуществляется по с т р о к а м ) ,после чего для каждой матрицы вычисляется ее двоичный ранг/^ (г —7номер матрицы, 1 ^ г ^ Л ");3) рассчитывается значение статистики2{FM - 0,2888Л00,2888iV(FM-i - 0,57767V)20,57767V{N-FM-FM_X - 0,1336iV)20,13367V' ^1 )-180где FM — число матриц максимального ранга (Ri = М) и FM-I ~~ число матриц с рангом, на единицу меньше максимального (Ri — М — 1);4) вычисляется достигаемый уровень значимостиp=exp(ir)-Рекомендации по выбору параметров.Длина последовательности ё должна быть достаточной для построения не менее 38 матриц (п ^ 38MQ), что при фиксированных значенияхМ = Q = 32 дает п ^ 38 912).Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е.
р < а, то последовательность ё признается неслучайной; в противном случае (при р ^ а) последовательность считается случайной.П.1.6. D I S C R E T E F O U R I E R TRANSFORM ( S P E C T R A L ) T E S TОбъектом исследования является спектр последовательности, полученный при помощи дискретного преобразования Фурье. В частности,определяется отклонение числа спектральных компонентов, амплитуда которых превышает 95% барьер, от ожидаемого результата 5%. Целью тестаявляется выявление периодичности (т.е. повторяющихся шаблонов).Параметры.1) ё — исследуемая последовательность, ё = £\, £2, • • •, £п\2) тт.
—длина исследуемой последовательности.Процедура тестирования.1) по исходной последовательности ё = £i, £2, • • •, £п строится последовательность X = Xi, Х2,...,Хп, гдеXi = 2ei — l,1 ^ г ^ п,т.е. осуществляется замена Он-»— 1 и 1 и + 1 ;2) вычисляется дискретное преобразование Фурье от последовательности X:S = DFT(X),-181-результатом которого является последовательность комплексных чисел, отражающих частотные характеристики исходной последовательности;3) строится последовательность абсолютных значений амплитудM = \S'\,где S' — подпоследовательность S, образованная ее первыми п/2 членами;4) рассчитывается величина 95% уровнядля случайных последовательностей амплитуды 95% частотных компонентов не должны превосходить Т;5) определяется ожидаемое число членов М, значение которых не превосходит Т:пN0 = 0,95-;6) подсчитывается величина TVi — наблюдаемое число членов М, не превосходящих Т;7) вычисляется значение статистики•v/n-0,95-0,05/4'8) определяется достигаемый уровень значимостиfр = ericr\s\\у/2 J'Рекомендации по выбору параметров.Рекомендуется использовать последовательности ё длиной не менее1000 бит ( п ^ 1000).Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е.
р < а, то последовательность ё признается неслучайной; в против--182ном случае (при р ^ а) последовательность считается случайной.Малые значения статистики s свидетельствуют о том, что слишкоммного частотных компонентов имеет амплитуду, превосходящую 95% порог Г.П.1.7. NON-OVERLAPPING T E M P L A T E MATCHING T E S TОбъектом исследования является • количество повторений определенной фиксированной подпоследовательности (шаблона) в исходной последовательности.
Целью теста является выявление генераторов псевдослучайных чисел, порождающих последовательности со слишком часто встречающимися апериодическими шаблонами."Для поиска шаблона длины га используется скользящее га-битное окно. Если шаблон не обнаружен, окно перемещается на одну позицию; впротивном случае осуществляется сдвиг окна нага позиций.Параметры.1) ё — исследуемая последовательность, ё = £i, £2, • • •, £п\2) п — длина исследуемой последовательности;3) га — длина искомого шаблона;4) N — количество подпоследовательностей, на которые разбивается исходная последовательность ё (фиксированное значение N = 8);5) М — длина каждой из подпоследовательностей, на которые разбивается исходная последовательность (фиксированное значение М = [^J).Процедура тестирования.1) исходная последовательность ё разбивается на N непересекающихсяподпоследовательностей длины М каждая; неиспользованные членыв конце последовательности отбрасываются;2) для каждой подпоследовательности определяется число Wj вхожденийв нее искомого шаблона (J — порядковый номер подпоследовательности, 1 ^ j ^ JV); для поиска шаблона используется m-битное окно:если шаблон не содержится в окне, оно сдвигается на одну позицию,иначе оно сдвигается на га позиций и значение Wj увеличивается наединицу;23) рассчитываются математическое ожидание ц и дисперсия ачисла-183вхождений шаблона в случайную последовательность длины М:V =М-т+1«..
(2о-=М,12т-1\-=;4) вычисляется значение статистикиNТТЛ5) определяется достигаемый уровень значимостиV = igamc (£, 0 .Приведенная выше процедура повторяется для каждого шаблона указанной длины (в реализации тестов NIST шаблоны задаются в текстовыхфайлах). Таким образом, в результате теста получается наборр-значений —по одному для каждого шаблона (при т = 9 возможно получение до 148значений, при т — 10 —до 284).Рекомендации по выбору параметров.Реализация тестов NIST рассчитана на поиск шаблонов длиной от 2до 10 бит. Рекомендуемыми значениями для т являются 8 и 9.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
