Разработка и исследование многомерных генераторов равномерно распределенных псевдослучайных векторов, основанных на представлении данных в алгебраических полях

• Автор: Калугин, Александр Николаевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Самара
• Количество страниц: 159 с. : ил.

ВВЕДЕНИЕ

ГЛАВА 1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ.

1.1 Линейные рекуррентные последовательности над конечными полями.

1.2 Тригонометрические суммы и суммы характеров с показательными функциями

1.3 Приведенные базисы решеток.

1.4 Канонические системы счисления.

1.5 Множества с малым отклонением, сети.

ГЛАВА 2. МЕТОДЫ СИНТЕЗА МНОГОМЕРНЫХ ГЕНЕРАТОРОВ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ

2.1 Обобщение одномерных схем синтеза генераторов

на многомерный случай

2.2 Методы генерации последовательности цифровых векторов

2.3 Методы синтеза точек многомерной решетки, ассоциированных с
цифровыми векторами
2.4. Фундаментальные области генераторов, использующих системы счисления в алгебраических полях.
2.5 Унификация фундаментальных областей
2.5.1 Понятие унификации, связь с геометрией фундаментальной области
2.5.2 Выделение гиперкуба, из покрытия многомерной решетки фундаментальными областями.
2.5.3 Эффективные алгоритмы реализации унификации
2.5.4 Специальный частный случай, не допускающий уиификации ГЛАВА 3. АНАЛИТИЧЕСКОЕ ИССЛЕДОВАНИЕ СВОЙСТВ ОБОБЩЕННОГО ГЕНЕРАТОРА ТАУСВОРТА
3.1 КССотклонсние.
3.1.1 Понятие КССотклонения.
3.1.2 Понятие канонических 0,т,ксетей
3.2 Определение максимального периода генерируемой последовательности
3.3. Исследование распределения многомерных точек на полном периоде генератора иРЯКСИЗ Случай
3.4. Распределение многомерных точек на неполном периоде генератора
ЦКСт Случай 1.
3.5 Исследование распределения генерируемой последовательности многомерных точек Случай
ГЛАВА 4. ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКИХ СВОЙСТВ КООРДИНАТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ МНОГОМЕРНОГО ОБОБЩЕННОГО ГЕНЕРАТОРА ТАУСВОРТА. ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ ГЕНЕРАТОРА
4.1 Исследование периода координатных последовательностей
4.2 Исследование равномерности распределения и статистической независимости элементов координатных последовательностей в терминах частотного критерия.
4.3 Исследование статистической независимости элементов координатных последовательностей с использованием критерия серий
4.4 Специальный случай синтез генератора, реализуемого в
негабинарной системе счисления.
4.5 Оптимизация генератора ЛЯСК
ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ
СТАТИСТИЧЕСКИХ СВОЙСТВ И ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ГЕНЕРАТОРА 1ЛГСНС.
5.1 Физические тесты генератора
5.1.1 Высотный корреляционный тест
5.1.2 Тест, использующий множественное случайное блуждание.
5.2 Вычисление значений многомерных определенных интегралов по методу Монте Карло.
5.3 Статистические тесты батареи ТеБШО
5.4 Сравнительное исследование вычислительной сложности генератора
1ЛВД1С.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Всегда можно построить определенную меру критерий, относительно которого используемая генерируемая последовательность будет несостоятельна 7. Как следствие, несмотря на то, что генераторы псевдослучайных последовательностей могут использовать произвольные детерминированные алгоритмы, для любого генератора можно утверждать, что он не может быть с одинаковой эффективностью применен для всех практических задач. В результате попытки конструктивного разрешения ЭТОЙ проблемы, были выработаны эвристические рекомендации к оценке качества псевдослучайных последовательностей , 6. Следует отмстить, что приведенные ниже высказывания не должны рассматриваться как корректные, а уж, тем более, математически строгие определения понятия случайной последовательности. Алгоритм генерации псевдослучайной последовательности должен быть исследован теоретически с использованием различных аналитических например, теоретиковероятностных критериев качества. Гипотеза о соответствии свойств псевдослучайной последовательности требуемым, должна быть исследована численно с применением как можно более обширного набора тестов. Гели возможно, генератор, планируемый для использования в для решения определенной вычислительной задачи, должен быть использован для решения аналогичной задачи, правильное решение которой заранее известно может быть вычислено аналитически2. Решение о уровне качества псевдослучайной последовательности обычно по сравнению с другими ГСЧ принимается на основании результатов, полученных с использованием всех трех описанных подходов. Критерии качества, используемые как для теоретического исследования псевдослучайных последовательностей, так и лежащие в основе статистических численных тестов, различны. Дополнительными требованиями, предъявляемыми к генераторам, используемым в алгоритмах моделирования но методу Монте Карло, являются системотехнические критерии эффективности программной реализации алгоритма генерирования на ЭВМ. Структурные критерии. К дайной группе относятся требования к длине периода псевдослучайной последовательности, требования к геометрической структуре множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др. Заметим, что данный способ анализа очень редко реализуем на практике, так как если аналогичная задача может быть решена аналитически, достаточно высоки шансы, что аналитическое решение может быть получено и для реальной задачи . Статистические теоретиковероятностные критерии. К данной группе относятся критерии согласия эмпирического закона распределения множества на выходе ГСЧ теоретическому наперед заданному закону распределения в одномерном пространстве а также согласия распределения множества многомерных векторов, составленных из последовательных значений на выходе генератора, и др. Критерии теории сложности. К данной группе критериев относятся теоретикоинформационные критерии, интерпретирующие случайноегь последовательности, как непредсказуемость последующих отчетов . Системотехнические критерии. К данным критериям относятся показатели эффективности реализации генератора на ЭВМ длина программной реализации алгоритма генерации, время выполнения, требуемый объем памяти, кроссилатформенная переносимость . Рассмотрим, какие критерии различных групп используются при оценке качества псевдослучайных последовательностей для статистического моделирования3. Наибольшее практическое значение имеют генераторы псевдослучайных последовательностей равномерно распределенных в некотором регулярном множестве. Для одномерных генераторов таким регулярным множеством является см. Длина периода. Пусть генератором псевдослучайных чисел порождается последовательность , 7 0. V п0, п0 , является важным параметром, характеризующим качество генератора. Для решения практических задач с использованием генераторов различных классов, рекомендуется использовать не более чем ут последовательных отсчетов на выходе последовательности. Иные критерии предъявляются, например, к псевдослучайным последовательностям, используемым в криптографии. Для последних большое значение имеюттсоретикосложностные критерии.