12749

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

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

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

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

Русский

2013-05-03

168 KB

93 чел.

Лабораторная работа 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.


 

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

47617. ГРУЗОВЫЕ ПЕРЕВОЗКИ 1.82 MB
  Результаты расчетов производственной программы по эксплуатации необходимо свести в таблицу. Результаты расчетов необходимо свести в таблицу. Цель работы: найти кратчайшие расстояния между пунктами транспортной сети и заполнить ими соответствующую таблицу; найти кратчайшие пути проезда между пунктами и отразить их на соответствующем рисунке.
47618. Измерение сопротивлений изоляции и защитного заземления. Методические указания 898 KB
  Измерение сопротивлений изоляции и защитного заземления: методические указания к лабораторной работе составители Лустгартен Т. В методических указаниях содержатся краткие теоретические сведения об измерении сопротивления изоляции и защитного заземления методика измерения сопротивления. преподаватель Рассмотрено и рекомендовано к изданию редакционноиздательским советом КГТУ Костромской государственный технологический университет 2009 Введение Для безопасной и безаварийной работы электроустановок промышленных предприятий...
47619. Исследование параметров вибрации. Методические указания 951.5 KB
  Букалов ИССЛЕДОВАНИЕ ПАРАМЕТРОВ ВИБРАЦИИ Методические указания к выполнению лабораторной работы Кострома 2008 УДК 677 Сусоева И. Исследование параметров вибрации И. Лабораторная работа Исследование параметров вибрации соответствует учебным планам по дисциплине Безопасность жизнедеятельности для студентов вузов всех специальностей и факультетов. Требования безопасности во время работы Включать источник вибрации только после полного уяснения порядка работы с прибором и только на время замеров.
47620. UML Основы. Краткое руководство 20.23 MB
  В книге описаны все главные типы диаграмм UML, рассказано, для чего они предназначены и какие нотации применяются при их создании и чтении. Это диаграммы классов, последовательности, объектов, пакетов, развертывания, прецедентов, состояний, деятельности, составных структур, компонентов, обзора взаимодействия, коммуникационные и временные
47621. МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЖЕННЯ ОПЕРАЦІЙ. НАВЧАЛЬНИЙ ПОСІБНИК 831 KB
  Ускладнення процесів управління сучасним підприємством та необхідність оперативного реагування на зміни зовнішніх факторів, що впливають на діяльність підприємства, вимагають застосування математичних методів, зокрема методів дослідження операцій, динамічного програмування, сіткового планування і управління, для обґрунтування економічної ефективності управлінських рішень, що приймаються
47622. Проектирование и создание базы данных в MS Access 684 KB
  Проектирование и создание базы данных в MS ccess. Учебное пособие предназначено для изучения раздела информатики по теме Системы управления базами данных студентами экономических специальностей. Настоящее пособие является первым этапом в изучении этого материала здесь изложены основные понятия и терминология этой области этапы проектирования и разработки баз данных реляционного типа создание структуры и заполнение баз данными.
47623. Методичні вказівки. Теорія автоматичного керування 283 KB
  Включают работы по исследованию объектов управления методами активного эксперимента а также исследованию влияния различных параметров автоматических систем управления на их качественные показатели. ЛАБОРАТОРНАЯ РАБОТА 1 ЭКСПЕРИМЕНТАЛЬНОЕ ОПРЕДЕЛЕНИЕ СТАТИЧЕСКОЙ ХАРАКТЕРИСТИКИ И КРИВОЙ РАЗГОНА ОБЪЕКТА УПРАВЛЕНИЯ 1. ЦЕЛЬ И ЗАДАЧИ РАБОТЫ Студенты должны изучить методику экспериментального определения и обработки статических характеристик и кривых разгона объектов управления. На основании результатов эксперимента определить параметры...