Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 30
Текст из файла (страница 30)
Разработанный программный комплекс функционирует совместно с программным комплексом статистического тестирования Assess,разработанном Национальным институтом стандартов и технологии США.Центральным элементом программного комплекса является база данных статистического тестирования. База данных имеет иерархическуюструктуру (см. рис. П.2), фактически соответствующую структуре объектов в памяти ЭВМ при выполнении программ.-199-База данныхПрофильтестирования 1ПараметрыпрофиляПрофильтестирования 2Генератор 1Генератор 2Профильтестирования тПараметрыгенератораРезультатытестированияГенератор пРис.
П.2. Структура базы данных программного комплекса статистического тестированияПрофиль тестирования является объектом, определяющим характеристики статистического тестирования, такие как длину битовой последовательности, количество последовательностей для каждого генератора, наборвыполняемых тестов и их параметры.Профили содержат в себе перечень генераторов, каждый из которыхопределяется набором его параметров. Кроме того, каждому генераторув профиле сопоставляются результаты статистического тестирования, осуществленного в соответствии с этим профилем.В состав программного комплекса входят 11 программ, сгруппированных по функциональному признаку:1) программы обслуживания базы данных:1.1) CreateDatabase — создание базы данных;2) программы обслуживания профилей тестирования:2.1) CreateProfile — создание профиля тестирования;2.2) DeleteProfile — удаление профиля тестирования;2.3) ListProfiles — вывод списка профилей тестирования;-2002.4) ShowProfile — вывод информации о профиле тестирования;3) программы обслуживания генераторов псевдослучайных последовательностей:3.1) AddGenerators — добавление новых генераторов к профилю тестирования;3.2) ListGenerators — вывод списка генераторов;3.3) ShowGenerator — вывод информации о конкретном генераторе;3.4) MigrateGenerators — копирование генераторов между профилями;4) программы осуществления статистического тестирования:4.1) Stat Test — осуществление тестирования статистических свойстввыходных последовательностей генераторов в соответствии с выбранным профилем;5) программы автоматизации построения аппаратной реализации:5.1) Implement — автоматическое построение блока Generate аппаратной реализации по заданным параметрам генератора.П.З.ФОРМИРОВАНИЕ ПАРАМЕТРОВДОСЛУЧАЙНЫХГЕНЕРАТОРОВПСЕВПОСЛЕДОВАТЕЛЬНОСТЕЙ НА ОСНОВЕКЛЕТОЧНЫХ АВТОМАТОВП.3.1.
А Л Г О Р И Т М Ф О Р М И Р О В А Н И Я Л О К А Л Ь Н О Й Ф У Н К Ц И И С В Я З И ЗАДАННОГО ВЕСАЛокальная функция связи / является булевой функцией от п аргументов, где п — мощность окрестности клеточного автомата. Как и любаядругая булева функция от п аргументов, она может быть представлена ввиде двоичного набораL/bj/b • • • >/2"]длины 2П, где fc — значение функции / на г-ом наборе аргументов. Следуявведенным в главе 2 обозначениям, через w обозначим вес функции /,т.
е. число наборов аргументов, на которых функция принимает единичныезначения.Для формирования булевой функции веса w от п аргументов используется следующий алгоритм:-2011) всем компонентам набора (/о, Д , . . . , /2™) присваиваются нулевые значения:Д = 0,0 < г < 2П;2) счетчик с устанавливается в ноль: с = 0;3) случайнои равновероятновыбираетсязначение индекса г6я{ОД,. . .
, 2 - 1 } ;4) если fi = 1, осуществляется переход к шагу 3;5) компоненту fi набора значений функции присваивается значение 1:/г = 1;6) счетчик с увеличивается на единицу: с = с + 1;7) если с < w, осуществляется переход к шагу 3; в противном случаеработа алгоритма завершена.П.3.2. А Л Г О Р И Т М Ф О Р М И Р О В А Н И Я Н А Ч А Л Ь Н Ы Х З Н А Ч Е Н И Й Я Ч Е Е К ПАМЯТИ К Л Е Т О Ч Н О Г О АВТОМАТА И Р Е Г И С Т Р А СДВИГА С Л И Н Е Й НЫМИ О Б Р А Т Н Ы М И С В Я З Я М ИМножество ячеек памяти рассматривается как одномерный двоичныймассив (набор)[гп0,т1,...,тп],где п — общее количество ячеек памяти.Для формирования начальных значений ячеек используется следующий алгоритм:1) счетчику г присваивается нулевое значение: г = 0;2) случайно и равновероятно выбирается значение о: Е {0,1};3) ячейке памяти ггц присваивается значение х: mi = х\4) счетчик г увеличивается на единицу: г — i + 1;5) если г < п, осуществляется переход к шагу 2; в противном случаеработа алгоритма завершена.Результатомработыалгоритмаявляетсядвоичныйнабор[mo,77ii,...
,77гп], компоненты которого имеют равновероятное распределение на множестве {0,1}.-202-П.3.3. А Л Г О Р И Т МКЛЕТОЧНЫХФОРМИРОВАНИЯОКРЕСТНОСТИ НЕОДНОРОДНЫХАВТОМАТОВОкрестность ячейки т г - неоднородного клеточного автомата можетбыть представлена в виде набора^lijrn) = [mkl,mk.2,...,mkl],0 ^ kj < n, 1 ^ j < ltгде n — размер неоднородного клеточного автомата (т. е.
число ячеек памяти), mkj — ячейка памяти автомата с индексом kj, а / — мощность окрестности.Для формирования окрестности используется следующий алгоритм:1) счетчику г присваивается нулевое значение: г = 0;2) счетчику j присваивается значение 1: j = 1;3) случайно и раврювероятно выбирается значение х Е { 0 , 1 , . .
. , п — 1};4) индексу kj в наборе Ч^(тг-) присваивается значение х: kj — х, т.е. вкачестве j-oro элемента окрестности rrii устанавливается ячейка тх;5) значение счетчика j увеличивается на единицу: j — j + 1;6) если j ^ I, осуществляется переход к шагу 3;7) значение счетчика г увеличивается на единицу: г — г + 1;8) если г < п, осуществляется переход к шагу 2; в противном случаеработа алгоритма завершена.П.4.СПОСОБЫ ЗАДАНИЯТОЧНЫХНЕКОТОРЫХ ПАРАМЕТРОВКЛЕАВТОМАТОВДанное приложение устанавливает соглашения по указанию параметров генераторов на основе клеточных автоматов и необходимо для исключения неоднозначности в их трактовке.-203П.4.1.
С П О С О Б З А Д А Н И Я З Н А Ч Е Н И Й Я Ч Е Е К К Л А С С И Ч Е С К И Х Д В У М Е Р НЫХ К Л Е Т О Ч Н Ы ХАВТОМАТОВНачальные значения ячеек классических двумерных клеточных автоматов задаются в виде двоичного набора. Ячейки нумеруются следующимобразом:7^(0,0)m(l,0)" *•Що,1)Щ1,1)•••_m(o,io) Щ1,ю)m(36,0)Щзе,1)• • • Щзб,ю)_П.4.2. С П О С О Б З А Д А Н И Я З Н А Ч Е Н И Й Я Ч Е Е К Н Е О Д Н О Р О Д Н Ы Х К Л Е Т О Ч Н Ы Х АВТОМАТОВНачальные значения ячеек неоднородных клеточных автоматов такжезадаются в виде двоичного набора. Ячейки нумеруются следующим образом:т0miтпзбт37ГП38га7зmi85m38ГП221ГП222 ГП38П.4.3.
С П О С О БЗАДАНИЯ• • •ГП256ОКРЕСТНОСТИЯЧЕЙКИНЕОДНОРОДНОГОКЛЕТОЧНОГО АВТОМАТАОкрестность ячейки неоднородного клеточного автомата с окрестностью мощности 4 задается при помощи следующей записи:х ^[XQ,XUX2,XZ],где # —индекс ячейки, для которой задается окрестность, a XQ, Х\, Х2, Ихз —значения индексов ячеек, входящих в окрестность в качестве первого,второго, третьего и четвертого элементов.-204П.4.4. С П О С О Б З А Д А Н И Я Л О К А Л Ь Н О Й Ф У Н К Ц И И С В Я З И КЛАССИЧЕСКИХКЛЕТОЧНЫХ АВТОМАТОВЛокальная функция связи f(xo,x\,..., £ 7 ) классических двумерныхклеточных автоматов с квазиполной окрестностью радиуса 1 задается ввиде двоичного набора ее значений:/оh• • • /31/з2/зз• • • /вз/224/225* * '/255Величина /о соответствует значению функции / на наборе (0,0,..., 0),/i — на наборе (1, 0 , . .
. , 0), / 2 — на наборе ( 0 , 1 , . . . , 0) и т. д. до / 25 5 — нанаборе ( 1 , 1 , . . . , 1).Отображение значений ячеек из окрестности некоторой ячейки т назначения аргументов локальной функции связи для квазиполной окрестности с учетом геометрической интерпретации решетки осуществляется следующим образом:х5Х\х^х2тXQXQх3х7П.4.5. С П О С О Б З А Д А Н И Я Л О К А Л Ь Н О Й Ф У Н К Ц И И С В Я З И Н Е О Д Н О Р О Д НЫХ КЛЕТОЧНЫХ АВТОМАТОВЛокальная функция связи /(жо,ЖьЖ2?яз) неоднородных клеточныхавтоматов с окрестностью мощности 4 задается в виде двоичного набораее значений:[/о,/ь- • • ,Лб] •Величина /о соответствует значению функции / на наборе (0,0,0,0),/i — на наборе (1,0,0,0), / 2 — на наборе (0,1, 0, 0) и т. д. до /is — на наборе(1,1,1,1).Аргументы XQ, XI, хч и ж4 соответствуют значениям ячеек, входящих вокрестность в качестве первого, второго, третьего и четвертого элементов.-205П.5.ПАРАМЕТРЫГЕНЕРАТОРОВПРИ ОСУЩЕСТВЛЕНИИСТАТИСТИЧЕСКОГО Т Е С Т И Р О В А Н И ЯВ данном приложении приводятся параметры генераторов псевдослучайных последовательностей на основе клеточных автоматов, использованные при осуществлении статистического тестирования выходных последовательностей.
При описании параметров генераторов мы придерживаемсясоглашений, установленных в приложении П.4.П.5.1. П А Р А М Е Т Р Ы Б А З О В Ы Х Г Е Н Е Р А Т О Р О В Н А О С Н О В Е К Л А С С И Ч Е СКИХП.5.1.1.ДВУМЕРНЫХ КЛЕТОЧНЫХ АВТОМАТОВПАРАМЕТРЫКЛЕТОЧНОГОАВТОМАТАДля клеточного автомата С используются следующие параметры:- множество значений ячеек памяти—Z2;- размерность и размер решетки —двумерная, 37 х 11 ячеек;- окрестность — квазиполная радиуса 1;- локальная функция связи — равновесная от 8 аргументов, выбираетсяслучайным образом для каждого клеточного автомата в соответствиис приложением П.3.1.В качестве начального заполнения ячеек памяти решетки клеточногоавтомата используется следующее фиксированное значение:0001000 11101 110001 10110 110111 000101001011110 10111 100101 00010 110101 111101000001100 00001 100100 00011 110111 010110001100101 01101 011000 10000 100110 000010100101010 01101 000110 11011 000110 110100100101010 01110 001010 10001 010001 110111100100000 11000 001011 11110 110100 001001101011110 01010 001100 01111 011011 001100111111101 10110 001001 00010 101111 111100101100010 11011 000011 10110 111110 110010010101100 10011 000100 10100 101000 00111111-206П.5.1.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
