Содержание к диссертации
Введение
ГЛАВА 1. Предварительные сведения 32
1.1 Линейные рекуррентные последовательности над конечными полями 32
1.2 Тригонометрические суммы и суммы характеров с показательными функциями 35
1.3 Приведенные базисы решеток 39
1.4 Канонические системы счисления 41
1.5 Множества с малым отклонением, -сети 43
ГЛАВА 2. Методы синтеза многомерных генераторов равномерного распределения 48
2.1 Обобщение одномерных схем синтеза генераторов на многомерный случай 48
2.2 Методы генерации последовательности цифровых векторов 49
2.3 Методы синтеза точек многомерной решетки, ассоциированных с цифровыми векторами 50
2.4. Фундаментальные области генераторов, использующих системы счисления в алгебраических полях 51
2.5 Унификация фундаментальных областей 55
2.5.1 Понятие унификации, связь с геометрией фундаментальной области 55
2.5.2 Выделение гиперкуба, из покрытия многомерной решетки фундаментальными областями 56
2.5.3 Эффективные алгоритмы реализации унификации 64
2.5.4 Специальный частный случай, не допускающий унификации69
ГЛАВА 3. Аналитическое исследование свойств обобщенного генератора таусворта 73
3.1 КСС-отклонение 75
3.1.1 Понятие КСС-отклонения 75
3.1.2 Понятие канонических (Ч,т,к.)-сетей 81
3.2 Определение максимального периода генерируемой последовательности 89
3.3. Исследование распределения многомерных точек на полном периоде генератора LFSR-CNS (Случай 1) 90
3.4. Распределение многомерных точек на неполном периоде генератора LFSR-CNS (Случай 1) 93
3.5 Исследование распределения генерируемой последовательности многомерных точек (Случай 2) 97
ГЛАВА 4. Исследование статистических свойств координатных последовательностей многомерного обобщенного генератора таусворта. параметрическая оптимизация генератора 103
4.1 Исследование периода координатных последовательностей 103
4.2 Исследование равномерности распределения и статистической независимости элементов координатных последовательностей в терминах частотного критерия 106
4.3 Исследование статистической независимости элементов координатных последовательностей с использованием критерия серий 107
4.4 Специальный случай: синтез генератора, реализуемого в негабинарной системе счисления 108
4.5 Оптимизация генератора LFSR-CNS 117
ГЛАВА 5. Экспериментальное исследование статистических свойств и вычислительной сложности генератора LFSR-CNS 131
5.1 «Физические тесты» генератора 132
5.1.1 Высотный корреляционный тест 133
5.1.2 Тест, использующий множественное случайное блуждание. 137
5.2 Вычисление значений многомерных определенных интегралов по
методу Монте Карло 140
5.3 Статистические тесты батареи TestUOl 142
5.4 Сравнительное исследование вычислительной сложности генератора LFSR-CNS 146
Заключение 151
Список использованных источников
- Приведенные базисы решеток
- Методы синтеза точек многомерной решетки, ассоциированных с цифровыми векторами
- Определение максимального периода генерируемой последовательности
- Исследование равномерности распределения и статистической независимости элементов координатных последовательностей в терминах частотного критерия
Введение к работе
Целью диссертационной работы является разработка новых методов синтеза и исследование свойств многомерных генераторов, порождаемых рекуррентными процессами и базирующихся на концепции позиционных систем счисления в многомерных дискретных решетках.
Актуальность темы. Методы статистического моделирования, методы Монте Карло получили большое распространение и применяются в различных областях: от моделирования сложных физических явлений (распространения излучения в земной атмосфере, субъядерных процессов физики высоких энергий, неламинарного течение жидкости и разреженного газа, химической кинетики и процессов горения [1]) до теоретического анализа эффективности различных финансовых инструментов, решения задач эконометрики и предсказания значений индекса Доу-Джонса [3]. Разработаны вычислительные методы Монте Карло для решения стохастических дифференциальных уравнений , задач с граничными условиями для уравнений в частных производных [2], интегральных уравнений, вычисления значений многомерных интегралов и интегралов по контуру [4].
К методам Монте Карло можно отнести численные методы статистического моделирования, основанные на получении большого числа реализаций случайного процесса с вероятностными характеристиками, совпадающими с гипотетическими характеристиками решаемой задачи. Несмотря на применение метода (в наивной форме) в течение нескольких столетий, историю метода Монте Карло принято отсчитывать с публикаций Уламом и Метрополисом в 1944 году работы [6]. За последующие десятилетия своего существования метод был развит до состояния мощного математического аппарата, используемого для решения сложных вычислительных задач [4].
В отличие от классических методов исследования реальных физических или математических систем, центральное место среди которых занимает численное решение обыкновенных дифференциальных уравнений или уравнений в частных производных, описывающих поведение физической или математической системы, метод Монте Карло моделирует эволюции физической или математической системы непосредственно, при условии что исследуемая величина может быть рассмотрена как случайная величина в некотором вероятностном пространстве.
Метод Монте Карло состоит из следующих этапов:
Этап 1. Определение области (множества) входных значений (параметров) и вероятностных характеристик входных параметров.
Этап 2. Формирование (многократное) случайной выборки входных значений из заданной области, и вычисление выходного значения (решения задачи, соответствующего сформированной выборке).
Заметим, что эффективность моделирования (0.2) по методу Монте Карло определяется не только адекватностью стохастической модели физической или математической системы (этап 1), но и, в значительной степени, свойствами используемой случайной выборки (этап 2) [9]. Развитие методов Монте Карло дало толчок теории, методологии и вычислительным методам формирования случайных выборок. Применение случайных последовательностей для реализации алгоритмов на базе метода Монте Карло является классическим. В настоящее время случайные последовательности и выборки находят новые области применения: используются в вычислительной статистике, при реализации вероятностных алгоритмов, тестировании сверхбольших интегральных схем, в задачах криптографии, в компьютерных играх [9]. В обобщенном виде, задача формирования случайной выборки может быть сформулирована следующим образом:
Пусть задана случайная величина X с функцией распределения F{x) = Р(д: X). Требуется сформировать множество чисел {хп} свойства
которого имитируют (в терминах определенных критериев качества) свойства множества независимых реализаций случайной величины X.
Существует множество различных подходов [7] к формированию случайной выборки: от использования таблиц случайных величин и физических датчиков случайных чисел до выполняемых на компьютере детерминированных алгоритмов генерации псевдослучайных последовательностей.
На начальных этапах развития генерации случайных выборок те, кому были необходимы случайные числа (векторы), вынуждены были [7] бросать игральные кости, либо раскладывать карты. В 1927 г (L.H.C. Tippett) была опубликована таблица, содержащая более 40000 чисел «взятых наудачу» из отчетов о переписи. В 1939 году были опубликованы таблицы, содержащие 100000 случайных чисел (M.G. Kendall), в 1955 году содержащие уже миллион чисел (RAND Corporation). Для генерации этих таблиц применялись устройства, называемые механическими (физическими) датчиками случайных чисел.
Действительно, свойства последовательностей, генерируемых физическими датчиками случайных чисел очень близки свойствам «истинно» случайных последовательностей. Физические датчики случайных чисел могут быть основаны как на микроскопических (тепловой шум, фотоэлектрический эффект, квантовые эффекты) так и на макроскопических физических процессах/эффектах (вращение колеса рулетки, бросание игральных костей, и т д).
Тем не менее, физические датчики обладают следующими недостатками, значимыми для статистического моделирования:
1) физические датчики относительно медленны;
2) нередко распределение последовательности на выходе физического датчика значительно отличается от требуемого;
3) так как датчики представляют собой физические устройства, они могут утрачивать со временем свои свойства; 4) с использованием физических датчиков невозможно повторить численный эксперимент, не сохранив всю произведенную генератором последовательность в памяти вычислительной машины, что во многих практических задачах является невозможным в силу огромного числа используемых случайных чисел. Попытки синтезировать метод, лишенный перечисленных недостатков, породили методологию генерации псевдослучайных последовательностей [7], то есть детерминированных (обычно рекурсивных) алгоритмов (функций), производящих на выходе последовательность чисел или точек {д-я}, имитирующую последовательность реализаций случайной величины X.
История генераторов псевдослучайных чисел (ГСЧ) берет свое начало в 1946 году, когда Дж. Фон Нейман предложил метод средин квадратов [7].
В общем виде последовательность {хп} на выходе генератора псевдослучайных чисел (точек) может быть представлена в виде:
где Ч —детерминированная функция, аргументами которой служат предыдущие порожденные псевдослучайные значения, значение функции интерпретируется как следующий элемент последовательности. При этом считается, что начальные элементы последовательности {л;,}, необходимые для корректного однозначного вычисления значения функции F известны.
Критика генераторов псевдослучайных чисел очевидна: генерируемые последовательности по построению не являются случайными; каждое генерируемый элемент полностью определяется предыдущими элементами и параметрами генератора. Однако, в случае если априорная информация о методе генерирования последовательности чисел, или участка этой последовательности, неизвестна, но задана последовательность (или конечное множество) {хп} чисел или векторов многомерного пространства, можно ли, используя лишь элементы этой последовательности, определить, является она (или ее участок, т.е. конечное множество) случайной или нет?
Правомерность и способы проверки гипотезы случайности заданного множества или последовательности, выбор «меры случайности», «критериев качества» являются предметом длительной дискуссии математиков и философов [7], [9].
Приведем лишь нескольких высказываний о мере случайности заданной последовательности чисел1.
«Определение» 0.1. (Лехмер Д. Г., цитируется по [7]). «Случайная последовательность является смутным понятием, олицетворяющим идею последовательности, в которой каждый член является непредсказуемым для непосвященных и значения которой проходят определенное количество проверок, традиционных у статистиков и отчасти зависящих от пользователей, которым предложена последовательность».
«Определение» 0.2. (Франклин Д. Н., цитируется по [7]) «Последовательность случайна, если она обладает любыми свойствами, присущими всем бесчисленным последовательностям независимых выборок ... случайных величин».
Несмотря на неполноту и неточность данных высказываний, суть их очевидна: истинно случайная последовательность должна удовлетворять всем возможным критериям качества. Дальнейший анализ этого требования и попытки его формализации привели [10] к неутешительным выводам - такого объекта как истинно случайная последовательность не существует. Какова бы ни была последовательность { „} и способ ее генерации, всегда можно построить критерий
относительного которого данная последовательность не будет достаточно случайной. Всегда можно построить определенную меру (критерий), относительно которого используемая генерируемая последовательность будет «несостоятельна» [7]. Как следствие, несмотря на то, что генераторы псевдослучайных последовательностей могут использовать произвольные детерминированные алгоритмы, для любого генератора можно утверждать, что он не может быть с одинаковой эффективностью применен для всех практических задач.
В результате попытки конструктивного разрешения этой проблемы, были выработаны (эвристические) рекомендации к «оценке качества» псевдослучайных последовательностей [84], [106], [107].
1 Следует отметить, что приведенные ниже высказывания не должны рассматриваться как корректные, а уж, тем более, математически строгие определения понятия «случайной последовательности».
1. Алгоритм генерации псевдослучайной последовательности должен быть исследован теоретически с использованием различных аналитических (например, теоретико-вероятностных) критериев качества.
2. Гипотеза о соответствии свойств псевдослучайной последовательности требуемым, должна быть исследована численно с применением как можно более обширного набора тестов.
3. Если возможно, генератор, планируемый для использования в для решения определенной вычислительной задачи, должен быть использован для решения аналогичной задачи, правильное решение которой заранее известно (может быть вычислено аналитически)2.
Решение о «уровне качества» псевдослучайной последовательности (обычно по сравнению с другими ГСЧ) принимается на основании результатов, полученных с использованием всех трех описанных подходов.
Критерии качества, используемые как для теоретического исследования псевдослучайных последовательностей, так и лежащие в основе статистических (численных) тестов, различны. Дополнительными требованиями, предъявляемыми к генераторам, используемым в алгоритмах моделирования по методу Монте Карло, являются системо-технические критерии эффективности программной реализации алгоритма генерирования на ЭВМ.
Применяемые в настоящее время критерии могут быть классифицированы [9] по следующим признакам:
1. Структурные критерии. К данной группе относятся требования к длине периода псевдослучайной последовательности, требования к геометрической структуре множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др. Заметим, что данный способ анализа очень редко реализуем на практике, так как если аналогичная задача может быть решена аналитически, достаточно высоки шансы, что аналитическое решение может быть получено и для реальной задачи [41]. 2. Статистические (теоретико-вероятностные) критерии. К данной группе относятся критерии согласия «эмпирического» закона распределения множества на выходе ГСЧ теоретическому (наперед заданному) закону распределения в одномерном пространстве а также согласия распределения множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др.
3. Критерии теории слооїсности. К данной группе критериев относятся теоретико-информационные критерии, интерпретирующие случайность последовательности, как «непредсказуемость» последующих отчетов [87].
4. Системо-технические критерии. К данным критериям относятся показатели эффективности реализации генератора на ЭВМ: длина программной реализации алгоритма генерации, время выполнения, требуемый объем памяти, кросс-платформенная переносимость [85].
Иные критерии предъявляются, например, к псевдослучайным последовательностям, используемым в криптографии. Для последних большое значение имеют теоретико-сложностные критерии. эвристическими [65], [66], [67], [68], [69], [70]. Определенные аналитические оценки характеристик распределения множества чисел/точек на выходе генераторов различных семейств, возможно получить только для ее участков, длина которых превосходит VF.
2. Соответствие распределения элементов последовательности на выходе генератора теоретическому.
Для генерируемой псевдослучайной последовательности должны быть получены аналитические гарантии соответствия (согласия) «эмпирического» распределения генерируемых отсчетов теоретическому. Па практике, таким теоретическим распределением часто является равномерное распределение в регулярной структуре.
В качестве критериев согласия используются критерий %г (критерий Пирсона), двусторонняя статистика Колмогорова-Смирнова, различные меры отклонения (экстремальное отклонения, «звездное» отклонение), статистика Андерсона-Дарлинга, Крамера-фон-Мизеса и другие.
Формальные определения критериев, используемых в работе, представлены в первой главе.
3, Исследование статистической независимости элементов псевдослучайной последовательности.
Анализ статистической независимости элементов псевдослучайной последовательности является важнейшим методом теоретического анализа. Разработаны критерии качества генераторов, которые позволяют делать надежные предсказания о поведении генерированных отсчетов в реальных вычислениях (тем не менее, реальность все же может отличаться от прогноза [84]).
Наиболее распространенным методом исследования независимости элементов псевдослучайной последвоательности является исследование распределения многомерных векторов, составленных из последовательных отсчетов псевдослучайных последовательностей (так называемый критерий серий).
Таким образом, исследование равномерности распределения последовательности (0.3) может быть интерпретировано как исследование статистической независимости элементов псевдослучайной последовательности
Совершенно ясно, что конечность величины d не позволяет исследовать независимость всех возможных наборов случайных элементов псевдослучайной последовательности. В частности, нет никаких гарантий, что последовательность будет лишена корреляций между удаленными отсчетами, которые могут сказаться в задачах, использующих параллельные алгоритмы основанные на разбиении одномерной последовательности на блоки. [72], [73], [74], [75], [76], [77].
Исследование равномрности полно-периодических последовательностей {xjf}}, л = 0,1,...,Г-1 в отношении некоторых критериев качества в пространствах различной размерности d позволяют делать предположения о поведении участка одномерной последовательности в реальных задачах. Эвристические результаты в пользу такого вывода приведены, например в работах [78], [81], [66]. Теоретических результатов в данной области на данной момент не получено.
Для некоторых ГСЧ, например линейных конгруэнтных генераторов, [10], множество векторов - элементов последовательности {.v "} - в пространствах различной размерности d порождают т.н. «решетчатую структуру» [71]. Т.е. существует такая дискретная решетка Л с К , чго векторы последовательности {x{„d)} являются узлами этой решетки (формальное определение решетки в Rk дано в разделе 1.3). Очевидно, что наличие подобной решетчатой структурой является недостатком метода генерирования, однако, в случае если в рамках определенной схемы генератора, решетчатая структура неизбежна, возможно сравнение качества различных генераторов с использованием дополнительных критериев, учитывающих структуру решетки Л (например, с использованием т.н. спектрального критерия, [7], [88]).
В общем случае, к исследованию равномерности распределения элементов на участках многомерных последовательностей {x,(,J)}, применяются критерии согласия аналогичные критериям, применяемым в одномерном случае, например двусторонняя статистика Колмогорова-Смирнова или критерий %2 Пирсона. [82], [77], [65]. Двусторонняя статистика Колмогорова-Смирнова известна под названием звездного отклонения [83], [9], [77] (см. раздел 1.5).
Следует также отметить, что при выполнении гипотезы о статистической независимости элементов последовательности, {х„} равномерность распределения элементов последовательностей {х, } является лишь одним из следствий, хотя и достаточно сильным. Если возможно определить статистику Y, распределение которой известно, когда элементы последовательности {х,,} являются реализациями статистически независимых равномерно распределенных случайных величин, соответствие эмпирического распределения статистики Y теоретическому может быть использовано для проверки гипотезы о равномерности и статистической независимости элементов последовательности {xj. Данный принцип положен в основу методов синтеза всех статистических тестов псевдослучайных последовательностей.
5. Вычислительная эффективность
Принимая во внимание огромные количества случайных чисел/точек, используемых в современных численных экспериментах по методу Монте-Карло, эффективность генерации псевдослучайной последовательности выходит на первый план. Именно для генераторов ГСЧ, используемых при статистическом моделировании, вычислительная эффективность имеет большое значение. Для ГСЧ, применяемых в других задача, например в криптографии, данное требование является менее значимым.
Рассмотрим важнейшие классы генераторов псевдослучайных точек, разработанные на настоящий момент.
Приведенные базисы решеток
Определение 1.6. Пусть {щ,ау,...,ак_х} — множество линейно независимых векторов пространства Шк. Линейная оболочка с целыми коэффициентами Л векторов {а0,а{,...,ак_у} называется решеткой (lattice) в Шк с базисом & = {а0,а1,...,ак_1}. Л = ІІІ# = 4«О+5І+-" + 4-А-ІЬ С1-21) где eZ, / = 0,I,...,Jt-l. Определение 1.7. Определителем решетки называется величина A) = (det(a„ay)j=o J" (1.22)
Базис решетки можно выбрать разными способами; однако, поскольку один базис решетки Л выражается через другой с помощью целочисленной матрицы с определителем ±1 [35], величина d(A) является инвариантом решетки.
Пусть я = {а0,а1,...,ак_1} - базис решетки Л, линейно-независимые векторы в М . Пусть далее векторы а0,а\,...,а\_х определяются соотношениями ;-1 а0 =о0, а]-а, - М9 , = 1-Д-1, (1.23) где =(Й(,Й;)/(Й;,5;),У=О,...,/-1, (І.24 тогда векторы я , 5 ,...,« _, - попарно ортогональны (см. процесс ортогонализации Грама-Шмидта).
Фиксируем решетку Л в К и рассмотрим множество GA, состоящее из всех базисов этой решетки. Рассмотрим на GA следующее отношение упорядоченности. Для {30,й,,...,Я4_,},{„,„...,,_,} еСЛ, {йо.д,,..., .,} {бД,..., .,}, (1.25) если существует номер J, такой что при всех i j справедливо равенство я,=&,, но \а\ \bj .
Определение 1,8. Минимальный элемент GA по отношению - называется приведенным по Минковскому базисом решетки. Очевидно, что базис решетки, приведенный по Минковскому, содержит кратчайший вектор 5 решетки, \а\ b , V6 є Л. Пусть на решетке Л обычным образом определена векторная норма УхеЛ, = 5 Д, л-р4 хЛ (1.26) ;=0 V =0 J
Поскольку норма (1.26) на решетке принимает дискретное множество значений, то приведенный по Минковскому базис решетки существует. Однако он может быть не единственен. Например, в решетке Ък любая перестановка единичных векторов ё0,е,,...,ёА_, образует приведенный по Минковскому базис.
Построение базиса, приведенного по Минковскому, и, даже, вычисление «кратчайшего» вектора при к 2 является NP-сложной задачей [38], [39]. Отчасти по этой причине, для приложений часто используют базисы, приведенные по Ленстре-Ленстре-Ловасу (LLL -приведенные базисы), которые, в общем случае, могут не содержать кратчайшего вектора.
Определение 1.9. Базис {50,5,,...,«,_,} решетки Лей называется LLL приведенным, если для векторов at0,a r...,al_l (1.23) и коэффициентов ду (1.24), полученных с помощью процесса ортогонализации Грама-Шмидта, выполнены следующие неравенства Ay i,0 y / -l, (1.27) \а, +//„-.«,-.1 Г -1 (L28) Сформулируем две леммы, устанавливающие наиболее важные свойства LLL -приведенных базисов. Лемма 1.5. Пусть {й0,«,,...,«,,_,} - LLL-приведенный базис решетки Леї . Тогда: 1-і2 -іі «і2 1. \а I 2 5 1 привсех/,у, 0 j і к-[; Аг—І 2. Л) ПІ«,И«ОД; #=о 3. \a0\ 2{k-l,/4d(A),n, где d(A) - определитель решетки (см. определение 1.7). Доказательство приведено в [37], теорема 7.7. Лемма 1.6. [37] Пусть {а0,й,,...,аА_,} - LLL-приведенный базис решетки Лей . Тогда для любого вектора є Л \ б справедливо неравенство И.Г 2 - 2. Доказательство приведено в [37], теорема 7.8.
Следует отметить, что Принципиальным отличием LLL -приведенного базиса решетки от базиса решетки, приведенного по Минковскому, является то, что в отличии от последнего для LLL -приведенного базиса существуют эффективные алгоритмы вычисления (со сложностью полиномиальной относительно к). Подробное описание алгоритма построения LLL -приведенного базиса приведено в [37].
Пусть Л - решетка в W , reN, М: Л -» Л — линейное отображение, такое что det(M) О и D — конечное подмножество Л содержащее 0 : с Л, card{D) со, О є D и образующее полную систему вычетов (mod М). Определение 1.10. Тройка (A.M,D) называется системой счисления, если любой элемент хеА может быть единственным образом представлен в виде: =х:=омч о-29) Где d,eD, /eN. Оператор М при этом называется основанием системы счисления, D — множеством цифр. Далее будем рассматривать решетку Л = Ъ и каноническое множество цифр D, заданное соотношением 5 = {aee = (l,0,0,...,0)eZ ,a = 0,l,...,detM-l} . (1.30) Определение 1.11 Если множество цифр D определено соотношением (1.30), система счисления (Л, М, D) называется канонической системой счисления. В случае если \ = ZK, элементы решетки Л могут быть отождествлены с «-мерными векторами (с целочисленными координатами), и отображение М может быть отождествлено с матрицей М отображения в каноническом базисе решетки Ъ".
Методы синтеза точек многомерной решетки, ассоциированных с цифровыми векторами
Отметим, что для использования многомерной псевдослучайной последовательности точек в задачах моделирования по методу Монте Карло, необходимо чтобы элементы последовательности были равномерно распределены в многомерном единичном гиперкубе (для большинства задач) [1], [4]. /А=([0;1))\ (2.21) Определение 2.5. Назовем унификацией фундаментальной области F взаимнооднозначное отображение фундаментальной области F КСС-генератора в единичный гиперкуб (2.21) Р: F - Ik. Замечание. Рассматривается СС-генератор, использующий к -мерную систему счисления (Z ,M,D), FаЪк. Построению унификации фундаментальной области F основанной на геометрическом «выделению» гиперкуба из покрытия Tes(F), посвящен следующий раздел. Рассмотрим покрытие решетки ZA фундаментальными областями КСС-генератора Tes(F)= (J Fa. Из данного покрытия можно выделить куб вида C(q,k,t) = ([0;q ))knZk, (2.22) где к — размерность канонической системы счисления. Определение 2.6. Назовем векторы х, такие что X, =У , = J ,i = 0,l,...,k-l, j = 0,l,...,k-l, (2.23) образующими векторами куба C(q,kj). Замечание 2.2. Прямым вычислением несложно показать, что если М -основание А:-мерной g-нарной канонической системы счисления, то векторы х, могут быть представлены в виде Z,=q M e,i = Q,l,...,k-l. (2.24) Далее, будем считать, что s = to,t =N (2.25) где s —размерность цифрового вектора (2.4).
Нетрудно заметить, что при выполнении условия (2.25) количество точек куба (2.22) равно количеству точек фундаментальной области F соответствующего А"СС-генератора псевдослучайных точек: Card С( /, ,/) = Card F. (2-26)
Определим отображение :F- C{q,kJ), задающее выделение куба (2.22) из покрытия Tes(F) соотношением: [«, при ueC(q,k,t), Р(и) = , ч , ч (2.2/) \и = и + со, йієВД :(ії C(q,k,t))A(r eC(q,k,t)) при uC(q,k,t).
Для точек її фундаментальной области F, принадлежащих кубу C(q,k,t), отображение Р — тождественно. Для тех точек и фундаментальной области F, которые не принадлежат кубу C{q,kj), в качестве образа выбирается точка u + eeC(q,k,t) — соответствующая точка другого элемента F + co покрытия Tes(F).
Замечание 2.3. Так как количество точек в кубе C{q,k,t) и в фундаментальной области F равно, car&C(q,k,t) = zard{F), то по принципу Дирихле, для того, чтобы отображение (2.27) было определено корректно, и являлось взаимно однозначным, достаточно чтобы следующее соотношение было удовлетворено. Q(F)n([0;f/))A={0}. (2.28) Если условие (2.28) не выполняется, то существует ненулевой элемент Й 0, fi)eQ, 3 EC(q,k,t), такой что z7, eC{q.k,t), її2 eC(q,k,t),u2 =z7, +а . И, по принципу Дирихле, найдется элемент щ є F такой, что для любого со є О., u3+6) C(q,kj)
Выполнение или невыполнение условия (2.28) является свойством соответствующего покрытия (2.13) Tes(F). Докажем выполнение условия (2.28) для покрытий пространства фундаментальными областями Л СС-генераторов, использующих канонические системы счисления, порожденные многочленами, описанными в условии леммы Лемма 1.7 (р- простое). У, = д-А + с,х + р, если и только если -1 с, 9 - 2, q 2, q = р\ /2 = хк + рхк"х +рхк 2 +...+ рх + р , 2 рєН, q = р : /4 = хк + рх"-1 + pV-2 +... + рк-]х + pk, 2 /;eN, q = pk. Для этого, докажем предварительно две вспомогательные леммы
Определение максимального периода генерируемой последовательности
Если характеристический многочлен (1.2) линейного рекуррентного соотношения (1.1) A(z) = zm+a lzm-]+... + a0 является примитивным, то рекуррентная последовательность (1.1) у(.п) + от_, у{п -1) +... + а0у(п - ш) = 0; является /«-последовательностью (последовательностью полного периода T = qm-\).
Так как наибольший практический интерес представляют псевдослучайные последовательности максимального периода, определим условия, которым должны удовлетворять параметры генератора LFSR-CNS, чтобы последовательность на выходе генератора была последовательностью максимального периода.
Лемма 3.4. Если шаг L генератора LFSR-CNS удовлетворяет соотношению НОД(1,д" -\) = \, (3.35) то последовательность на выходе LFSR-CNS является последовательностью полного периода, равного Т = qm -\.
Доказательство. Так как унификация является взаимно однозначным соответствием, и все элементы решетки Z имеют уникальный КСС код, период последовательности на выходе генератора LFSR-CNS равен периоду последовательности {?{п)} цифровых векторов (2.1).
Далее, по определению, для генератора LFSR-CNS, элементы последовательности цифровых векторов удовлетворяют соотношению (2.4) f (и) = (y(nL),y(nL + l\...,y{nL + А- -))). (3.36) Пусть T-qm \ —период последовательности {у(п)}, величина d определена соотношением d = HOM(?;L). Тогда последовательность (3.36) удовлетворяет соотношению: Y(n + {Tld]) = Y(n), « = 0,1,..., то есть последовательность {п) является периодической с периодом Т{, причем Г, является делителем (делит) период Т последовательности у(п). Из соотношения (3.36) и условия ?(п + Т,) = (п), и = 0,1,... следует равенство y(Ln+ /-l + LTt) = y(Ln+ /-IJ, /7 = 0,1,-, OS / 5. (3.37) Заметим, что справедливость соотношения (3.37) при 0 / s , в случае s L влечет его справедливость при s j L. Таким образом, выполняется равенство у(.п + Щ) у{п), /1 = 0,1,.... Период Т делит Щ, и ТId делит Tt, поэтому выполняется соотношение Tx=Tld. Далее, так как по условию леммы d = 1, имеем ТХ=Т. Лемма доказана.
Таким образом, для обеспечения максимального периода последовательности на выходе LFSR-CNS, при синтезе генератора необходимо обеспечить выполнение соотношения (3.35). 3.3. Исследование распределения многомерных точек на полном периоде генератора LFSR-CNS (Случай 1) В данном разделе исследуются свойства множества Р = {Х0,Х ,Х,_,}, T = q"--\, (3.38) в предположении выполнения условия k ,mlL. Центральным результатом раздела является Теорема 3.2 устанавливающая верхние и нижние оценки величины звездного отклонения (1.42) для множества (3.38). Предпошлем доказательству теоремы 3.2 доказательство нескольких вспомогательных утверждений: укк . т к Лемма 3.5. Пусть k mlL и hs — ZK елі - произвольный вектор. Пусть Я далее Z(h) - количество индексов п, О п Т - с/" -1, такое что ХП=И, тогда справедливы равенства - ІУ Леслі/ А б; Z(A) = Г У""-1, если Л=0.
Доказательство. Пусть множество Р(и). я = 0,1,...,Г-1 определено соотношением: Ф(и) = (?(и),Г(п + 1),...,У(я + -І))єЖ(;" , « = 0,1,...,Г-1
Пусть, далее 7 є F xl, и Z(/7) — количество индексов п, 0 п Т -1, такое что (n) = fj . Так как HOK{L,T) = 1, и k mlL,io выполнены условия теоремы 9.2 в [9] , и справедливы следующие соотношения. 2И)_( - _ (3.39)
Так как каждому цифровому вектору Y(ri) взаимно однозначно (в силу взаимной однозначности представления элементов решетки Ъ" в канонической системе счисления (Z \M,D)) сопоставлен элемент последовательности {х„\, то существует биекция :F;"i- -i-Zrin/ri, = Ф(«)). (3.40) В силу взаимной однозначности отображения q , если h = p(rj), то справедливо соотношение Z(A) = Z(fj). Таким образом, из (3.39) и (3.40) следует утверждение леммы. Следствие 3.1. Если Аг = 1, m = L = s, на выходе генератора LFSR-CNS максимального периода единожды производятся все точки куба —-Ък лГ, за Ч исключением точки б . В случае если m L, s L среди точек множества Р = {Х0,Х1,...,Х7_[} все точки многомерного куба —Z" n/a встретятся q" ks раз, нулевая точка 93 встретиться q " b -1 раз. Такая структура множества Р позволяет получить оценки звездного отклонения D Kk){P).
Исследование равномерности распределения и статистической независимости элементов координатных последовательностей в терминах частотного критерия
Для заданного множества Р на выходе генератора LFSR-CNS реалистичным представляется только теоретическое исследование в терминах отклонения D\P), ассоциированного с системой счисления, используемой в генераторе.
Размерность к системы счисления (и генератора) напрямую зависит от специфики решаемой задачи, и с точки зрения вычислительной эффективности рекомендуется выбирать равной количеству процессоров многопроцессорной системы (см. далее раздел 5.2). В силу специфики архитектуры современной вычислительной техники, очевидным является использование бинарных систем счисления q = 2.
Тем не менее, предпочтение той или иной КСС, возможно отдать с использованием иных критериев, например, вычислительной эффективности. Справедлива следующая лемма.
Лемма 4.9. Справедливы утверждения (а) Для вычисления координаты многомерной точки на выходе генератора LFSR-CNS по заданному цифровому вектору в среднем требуется (s) умножений и (л -1) сложение целых чисел. (б) Для генератора с КСС, порожденной многочленом / = хк +2, вычисление координаты многомерной точки на выходе генератора LFSR-CNS по заданному цифровому вектору требует (s /к) умножений и {siк-1) сложений целых чисел. Доказательство. В силу соотношения (4.1). элемент координатной последовательности (координата многомерной точки на выходе генератора LFSR-CNS) удовлетворяет равенству г70)(«) = Яы-(Г(л))7 (modя ), где () есть скалярное произведение двух S = K( мерных векторов Ни) и Y(п). Таким образом, для вычисления отсчета последовательности йи\п) по заданному цифровому вектору {п) требуется не более s умножений и (i -l) сложения. Так как вектор Y{ri) в общем случае не содержит значительного количества нулевых элементов, данные оценки не улучшаемы.
В силу соотношения (4.12), если вектор Н{,} ассоциирован с канонической системой счисления, порожденной мноючленом f = xk+2, вектор Яы содержит лишь t = slK ненулевых элементов. Таким образом, требуется лишь / нетривиальных умножений и (/-1) сложение. Лемма доказана.
Таким образом, при использовании одного и того же метода вычисления цифрового вектора Y(ri), с точки зрения вычислительной сложности, более эффективным представляется использование генераторов с КСС, порожденной многочленом /(.г) = к" + 2.
Далее, рассмотрим зависимость свойств генерируемой последовательности от параметров рекуррентного соотношения. Порядок используемой рекуррентной последовательности т определяет период генератора Т 2 "-\ Так как для практических задач выбор периода генератора зависит от длины участка псевдослучайной последовательности, который будет использован для вычислений, можно считать, что величина m (так же как и размерность генератора к ) определяется условиями практической задачи [1], [68] — [70].
Рассмотрим зависимость свойств генератора от шага генератора L и длины числового вектора І. Желательным является выполнение соотношения s L, в противном случае векторы Y{n) будут «накладываться», что может негативно отразиться на свойствах последовательности (3.3). В качестве иллюстрации подобных негативных эффектов, рассмотрим случай L - 1, І L . Справедлива следующая лемма.
Рассмотрим задачу выбора оптимальных коэффициентов используемой линейной рекуррентной последовательности. Согласно Теореме 3.8, критерием качества последовательности LFSR-CNS является величина (3.44) rik\A(z),s) = m\n(s,p(Cl)), зависящая от коэффициентов характеристического многочлена A(z) рекуррентной последовательности (1.1).
Заметим, что в силу конструкции обобщенных {t,m,k) -сетей, значения критерия ra\A,s) совпадают с аналогичной величиной, используемой при исследовании традиционных {t,m,k) -сетей. Поэтому, результаты исследования величины r(k)(A,s) могут быть использованы для исследования свойств многомерных обобщенных генераторов. В силу теоремы 9.7 в [9], для любого простого р и любых m,k,L, k m/L, существует примитивный многочлен A(z) над F порядка deg( ) = т такой, что ґ (A,s) min ( ф(рт-\) Iog2 (sA--l)(s + l) (4.32)
Доказательство теоремы 9.7 в [9]. не является конструктивным, но дает возможность поиска примитивного многочлена А, обеспечивающего выполнение соотношения (4.32). В качестве дополнительных критериев качества, которые могут быть использованы при выборе многочлена А, являются вычислительная эффективность и равномерность вероятностного распределения на начальном участке последовательности. В случае если характеристический многочлен A(z) последовательности (1.1) является трехчленом A(z) = z +zr + l, (4.33) существует сверх быстрый алгоритм вычисления элементов последовательности {у{п)}, [91]. Таким образом, многочлены вида (4.33) являются предпочтительными в терминах вычислительной сложности, однако, как показано далее в этом разделе, результаты исследования свойств начального участка рекуррентной последовательности с характеристическим многочленом в виде трехчлена свидетельствуют о значительных отклонениях распределения производимой последовательности от равномерного.
Рассмотрим влияние начального состояния S(0) генератора LFSR-CNS на вероятностные свойства начального участка псевдослучайной последовательности длины М. Следует отметить, что для случая M Jf, определенные гарантии равномерности распределения обеспечиваются Теоремой 3.5. На более коротких участках возможно лишь численное исследование.
