12749

Исследование свойств линейного рекуррентного регистра (ЛРР)

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 8 Исследование свойств линейного рекуррентного регистра ЛРР Цель работы Изучить способы задания ЛРР и свойства генерируемых им последовательностей. Используемое программное обеспечение Для работы используется программа LRR.EXE З...

Русский

2013-05-03

168 KB

98 чел.

Лабораторная работа 8

Исследование свойств линейного рекуррентного регистра (ЛРР)
Цель работы
Изучить способы задания ЛРР и свойства генерируемых им последовательностей.
Используемое программное обеспечение
Для работы используется программа LRR.EXE
Задание
1. Найти периоды выходных последовательностей ЛРР, заданных различными полиномами обратных связей и при различных начальных заполнениях.
2. Исследовать основные статистические свойства выходных последовательностей ЛРР на примитивном полиноме:
                               -«окна»,
                               -баланса нулей и единиц,
                               -серий,
                               -корреляционной функции.
3. Сделать выводы о соответствии результатов по п.1-2 теоретическим знаниям, полученным на лекциях.
Порядок выполнения работы
Для начала работы перейти в каталог, содержащий рабочие программы lab1.
Запустить программу LRR.EXE.
1. Задать длину ЛРР равной 4, полином обратных связей x4 + x3 + x + 1 и начальное заполнение 1110. Сгенерировать выходную последовательность ЛРР и найти зрительно ее период.
2. Выполнить п.1, изменив начальное заполнение на 1001.
3. Задать длину ЛРР равной 4, полином обратных связей x4 + x + 1. Сгенерировать выходные последовательности ЛРР при тех же двух начальных заполнениях, что и в п.1-2, и найти их периоды. Объяснить результаты, полученные в п.1-3.
4. Просмотрев таблицу примитивных полиномов, содержащуюся в файле poly.dat,открыв ее через блокнот и выбрать  произвольно примитивный полином степени не более 17. Задать произвольное начальное заполнение и сгенерировать выходную последовательность ЛРР.
5. Сравнить  последовательность ЛРР по п.4 с чисто случайной последовательностью, полученной, как “hot bits” из Интернет (чисто случайная последовательность заложена в программу). Сделать выводы о совпадении или несовпадении их свойств.
6. Рассчитать период, частость нулей и единиц, частость серий и вид автокорреляционной функции (АКФ) для последовательности, полученной в п.4. Сравнить полученные результаты с теоретическими знаниями, полученными на лекциях.
Отчет
1. Титульный лист.
2. Анализ свойств по п.1-3.
3. Примитивный полином по п.4, полученный период выходной последовательности ЛРР для этого полинома, автокорреляционная функция и ее значения на периоде.
4. Сравнение последовательности на выходе ЛРР и чисто случайной последовательности по п.5.
5. Частости нулей и единиц, частости серий и значения АКФ, рассчитанные в п.6.
Описание программы
Для выполнения лабораторной работы используется специально разработанная программа, содержащаяся в файле LLR.exe. Вид главного окна программы представлен на рис. 1.
Рис.1. Главное окно программы
В начале работы необходимо ввести исходные данные: длину используемого регистра, коэффициенты полинома обратных связей и начальное заполнение ячеек регистра, длину генерируемой последовательности. Данные вводятся в пустые поля с соответствующими названиями в левой части окна. Если все данные введены верно, то будет активна кнопка Генерировать (рис. 2).
Рис.2. Заполнение исходных данных
Для получения данных необходимо нажать кнопку Генерировать. После этого в нижней части окна в верхнем поле будет показана полученная на основе указанного полинома обратных связей и его начального заполнения двоичная последовательность, свойства которой исследуются в настоящей лабораторной работе. В нижнем поле будет представлена чисто случайная двоичная последовательность, представленная для сравнения с линейной рекуррентной последовательностью. После этого станут доступны ещё две кнопки: Статистика и График (на рис.3 обведены красным и зеленым соответственно).
Рис. 3. Сгенерированная двоичная последовательность
Для расчета статистических данных полученной двоичной последовательности (период, число серий и пр.) необходимо нажать кнопку Статистика. Рассчитанные величины будут показаны в нижней части окна программы. Для достаточно длинных последовательностей это может занять некоторое время.
Рис.4. Статистика двоичной последовательности
Кнопка График предназначена для просмотра графика корреляционной функции.
Рис.5.  График корреляционной функции примитивного полинома
Рис.6. График корреляционной функции не примитивного полинома
Статистические свойства выходных последовательностей ЛРР
  1.  Период.
Периодом называется наименьшее целое число  такое, что для элементов последовательности выполняется соотношение ,
Период линейной рекуррентной последовательности , где  – порядок примитивного полинома. Период рекуррентной последовательности  на примитивном полиноме находится как .
  1.  Серия.
Серией длины  называется последовательность из  одинаковых символов, окруженных другими символами. На периоде ЛРР максимальной длины, число серий равно длины 1 равно 1/2 от общего количества серий, 1/4 всех серий длины 2, 1/8 всех серий длины 3 и так далее.
  1.  Окно.
Если «окно» шириной n перемещать вдоль выходной последовательности ЛРР на примитивном полиноме, то каждый из  ненулевых наборов будет виден в окне только один раз.
  1.  Баланс.
Число нулей на периоде линейной рекуррентной последовательности в точности равно
,
а число единиц равно
.
Отсюда: частость появления нулей и единиц вычисляется так
,      
  1.  Автокорреляционная функция (АКФ).
АКФ называется
,
- линейная рекуррентная последовательность,
- линейная рекуррентная последовательность, сдвинутая на  тактов.
Для линейной рекуррентной последовательности максимального периода
,
.
Отчет по лабораторной работе
«Исследование свойств линейного рекуррентного регистра (ЛРР)»
(пример оформления)
Выполнил студент: Петров В.В.
Преподаватель: Яковлев В.А.
Пункт 1
Длина регистра: 4
Полином обратных связей: h(x) = x4 + x3 + x + 1 (коэффициенты полинома 11011)
Начальное заполнение: 1110
Двоичная последовательность: 1110001110001110001110001110001110001110001110001110001110001110001110001110001110001110001110001110
Период двоичной последовательности: 6
Пункт 2
Длина регистра: 4
Полином обратных связей: h(x) = x4 + x3 + x + 1 (коэффициенты полинома 11011)
Начальное заполнение: 1001
Двоичная последовательность:
1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001
Период двоичной последовательности: 3
Пункт 3
Длина регистра: 4
Примитивный полином обратных связей: h(x) = x4 + x + 1 (коэффициенты полинома 10011)
Начальное заполнение: 1110
Двоичная последовательность:
1110101100100011110101100100011110101100100011110101100100011110101100100011110101100100011110101100
Период двоичной последовательности: 15
Длина регистра: 4
Примитивный полином обратных связей: h(x) = x4 + x + 1 (коэффициенты полинома 10011)
Начальное заполнение: 1001
Двоичная последовательность:
1001000111101011001000111101011001000111101011001000111101011001000111101011001000111101011001000111
Период двоичной последовательности: 15
Пункт 4
Длина регистра: 15
Примитивный полином обратных связей: h(x) = x15 + x11 + x7 + x6 + x2 + x + 1 (коэффициенты полинома 1000100011000111)
Начальное заполнение: 100100011010011
Двоичная последовательность:
1001000110100110011011100101110100010111001110000111101100110001100111000001011001100100111110000110
Период двоичной последовательности: 32767
Пункт 5
Период двоичной последовательности: 32767
Частость появления нулей и единиц: 0,500015259
Частость серий:
8193 серии длины 1
4096 серий длины 2
2048 серии длины 3
1024 серии длины 4
512 серий длины 5
Автокорреляционная функция: константа R(k) = -3,05185094 * 10-5, для k0.
Контрольные вопросы
1. Что такое ЛРР и чем он задается?
2. Что такое примитивный полином?
3. Каким может быть период ЛРР?
4. Зависит ли период от начального заполнения?
5. Задайте полином обратных связей, который при любом начальном заполнении дает период равный длине ЛРР.
6. Как выбрать полином обратных связей, чтобы обеспечить максимально возможный период выходной последовательности? Чему равен этот период?
7. Каково соотношение нулей и единиц на максимальном периоде, какова частость серий и вид АКФ?
8. Можно ли непосредственно использовать ЛРР в качестве датчика гаммы потокового шифра?
Литература
1. В.И.Коржик “Конспект лекций по курсу “Основы криптографии”’.
2. В.И.Коржик, Д.В.Кушнир, ”Теоретические основы информационной безопасности телекоммуникационных систем”, СПбГУТ, 2000.


 

А также другие работы, которые могут Вас заинтересовать

893. Экономическое обоснование оптимальной схемы доставки машин и оборудования из Петрозаводска в Ростов-на-Дону 744 KB
  Анализ задания и обоснование расчетных вариантов схемы доставки груза. Анализ возможных маршрутов доставки в прямых и смешанных транспортных сообщениях и выбор расчетных вариантов схемы доставки груза. Определение себестоимости эксплуатационного содержания судов. Определение путевой составляющей издержек перевозки грузов водным транспортом.
894. Строительство железных дорог, путь и путевое хозяйство 170 KB
  Требования безопасности при разборке и сборке звеньев путевой решетки. Особенности технологии ремонта бесстыкового пути и ремонта звеньевого пути с укладкой плетей бесстыкового пути. Производственный состав ПМС.
895. Службові листи як особливий вид довідково–інформаційних документів 166 KB
  Службові листи в системі документообігу організації. Складання та оформлення службових листів. Особливості складання службових листів. Реквізити листа та їх оформлення.
896. Программное средство анализа врожденных характеристик человека 243.5 KB
  Краткая техническая характеристика выбранного ПК и внешних устройств. Проектирование отдельных компонент программы и классов без учета языка реализации. Проверка программы в статическом режиме, и динамическая проверка, включающая контроль адекватности реакции системы на заявки пользователя и поведения системы при возникновении недопустимых ситуаций.
897. Четырехэтажный 32-квартирный жилой дом 134 KB
  Географический пункт строительства: г.Тюмень. Четырехэтажный жилой дом имеет 12 квартир 1-комнатные, 2-комнатные и 3-комнатные. На каждом этаже размещено по 3 квартиры. Здание рассчитано на проживание в нем 12 семей. Плиты перекрытия из сборных железобетонных плит.
898. Черный пиар 157.5 KB
  О происхождении российского черного пиара. Сферы применения черного пиара. Эффективность рr и коммуникативных мероприятий: проблема измерения и оценки. Оценка эффективности РR-кампаний с помощью ЕАV. Проблемные точки оценки эффективности PR.
899. Программное обеспечения информационных технологий 171 KB
  Обоснование необходимости разработки программного продукта. Уточнение структуры входных и выходных данных. Определение формы представления входных и выходных данных. Обоснование приемов программирования. Работа с ГОСТами и нормативными документами при разработке алгоритмов и оформлении технической документации.
900. Ведущие фондовые индексы 160.5 KB
  Индексы фондового рынка США. Аукцион по размещению нового выпуска без погашения старого. Погашение ГКО на аукционе по размещению бумаг, не входящих в индекс. Методы расчета индексов. Ценовой, взвешенный по рыночной капитализации композитный фондовый индекс.
901. Обзор баз данных библиотеки ПКС 171.5 KB
  Место прохождения практики Библиотека ПКС. Библиотека занимается выдачей/приемов книг и учебников для студентов, а также ведет учет выдачи/приема. Изучение различных баз данных, на примере одного из видов баз данных - MS Access.