12749

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

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

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

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

Русский

2013-05-03

168 KB

100 чел.

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


 

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

51511. Исследование дисперсии стеклянной призмы 39.5 KB
  Цель работы Наблюдение линейчатых спектров испускания определение показателей преломления оптического стекла для различных длин волн и построения кривой дисперсии этого стекла определение дисперсионных характеристик призмы. ά_min = N – No ; где показатель преломления вычисляется по формуле : n = 2sin30 1 2 ά_min; соответственно для каждой длины волны .
51512. Изучение явления дифракции света с помощью лазера 47.5 KB
  Переходим к измерениям Измерения начинаем с минимально открытой щели как рекомендуется при которой хорошо наблюдается дифракционные минимумы и соответственно максимумы. L фиксированное расстояние от щели до экрана а – ширина щели Хk – ширина максимально наблюдаемой на экране дифракционной картины k – число максимумов и минимумов одинаковое Ширина дифракционной полосы : ∆Х = Хk k ; ∆Хi = λL i = Zi ...
51515. Содержание операционной логистической деятельности 48.81 KB
  Элементами системы логистики являются: производственные запасы оборотных средств, проблемы закупки сырья, материалов, работа транспорта как внешнего, так и транспорта внутри предприятия, структура и особенности организации складского хозяйства и другие процессы
51516. ОПЕРАЦИОННАЯ ЛОГИСТИЧЕСКАЯ ДЕЯТЕЛЬНОСТЬ 40 KB
  С развитием бизнеса перечисленные виды деятельности стали называться логистическими, а подразделения промышленных, торговых или сервисных компаний, которые их выполняли, получили название служб (отделов, дирекций, департаментов) логистики.
51517. Мысль семейная в романе Л. Н. Толстого «Война и мир» 71.92 KB
  В романе «Война и мир» автор показывает пятнадцатилетний пласт жизни многих людей в период великих потрясений и перемен в России. Наряду с изображением грандиозных исторических событий, с философскими размышлениями автора значительное внимание в романе уделяется семье как основе основ.