12749

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

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

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

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

Русский

2013-05-03

168 KB

94 чел.

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


 

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

35547. ПРОЕКТИРОВАНИЕ ФАСОННОГО ДИСКОВОГО РЕЗЦА С ПРИМЕНЕНИЕМ ЭВМ 835.5 KB
  Приведены методика проектирования дискового фасонного резца на базе системы автоматизированного проектирования металла режущего инструмента САПР РИ и характеристики фасонных резцов их конструктивные особенности технические условия на проектирование резцов программа коррекционного расчета профиля дискового фасонного резца на ЭВМ СМ4. По конструктивной форме фасонные резцы подразделяются на стержневые призматические и дисковые Наибольшее распространение получили дисковые резцы так как они более технологичны в изготовлении и...
35548. Проектирование фасонных резцов 111 KB
  Целью работы является ознакомление с различными формами и видами фасонных резцов, правилами установки, правилами назначения передних и задних углов, алгоритмом проектирования профиля фасонного резца
35549. Двухступенчатый цилиндрический редуктор 553.5 KB
  Определение силовых и кинематических параметров редуктора. Конструирование зубчатого редуктора. Конструирование и расчет элементов корпуса редуктора. Редуктор двухступенчатый несоосный Кинематическая схема редуктора: вращающий момент на тихоходном валу редуктора; угловая скорость выходного вала редуктора; ч.
35550. Редуктор двухступенчатый соосный двухпоточный с внутренним зацеплением тихоходной ступени 1.7 MB
  Кинематический расчет и выбор электродвигателя Исходные данные: потребный момент на валу исполнительного механизма ИМ Тим=30Нм; угловая скорость вала ИМ ωим=58с1; Определяем мощность на валу ИМ Nим= Тимх ωим=30х58=174Вт. Определяем общий КПД привода по схеме привода ηобщ=ηкп ηшп ηм ηп1. =097209820994=0868 Определяем потребную мощность электродвигателя [1 с. Определяем номинальную частоту вращения электродвигателя по формуле 5 [1c.
35551. Кибернетика. Курс лекций 887.5 KB
  Уже давно ученые обнаружили сходство некоторых процессов управления в системах различной материальной природы и попытались использовать эти аналоги в исследованиях и практических приложениях. Она показала плодотворность использования аналогии процессов управления для их познания и совершенствования. Именно на этой почве формируются конкретные приложения кибернетики в экономике предметом изучения которой являются процессы управления и связанные с ними процессы передачи и обработки информации в экономических системах. Это обуславливается...
35552. АНАЛИЗ МЕДИАРЫНКОВ 524 KB
  Существуют ли другие продукты которые будут покупать потребители что ограничит потенциал нового продукта услуги Сила поставщиков или Рыночная власть поставщиков Достаточно ли продукции на рынке Существует ли какойнибудь компонент добавленной стоимости позволяющий конкурировать с другими поставщиками Противостояние существующих производителей или Угроза от существующих конкурентов Сколько компаний борются за рынок Какова в целом позиция конкурентов Какие методы конкуренции используются Угроза новых участников рынка или...
35553. Система управления летательного аппарата (СУЛА) 2.06 MB
  В основе процесса управления лежит информация о задачах управления заданной цели и текущем состоянии системы. В соответствие с эти процесс управления включает следующие основные этапы: получение необходимой информации о задачах управления; получение информации о текущем состоянии объекта управления ЛА; анализ полученной информации и выработку решения управляющего воздействия; реализацию принятого решения. Из этих же элементов состоит процесс управления ЛА.
35554. Эстетика 2.1 MB
  Такой подход позволяющий уйти от умозрительных схем избежать схоластичности эстетических суждений сопровождает рассмотрение содержания основных эстетических категорий искусства художественного сознания художественного образа художественного стиля художественной композиции художественного содержания и формы художественного творчества и других в процессе их исторического становления. Синтез исторического и теоретического примененный к эстетическому знанию оказывается по убеждению автора наиболее продуктивным в учебном и...
35555. БИОМЕДИЦИНСКАЯ ЭТИКА 1.36 MB
  Медицинские вмешательства в репродукцию человека. Это не значит что они удалены от повседневной жизни рядового человека и представляют интерес только для специалистов. Ознакомиться с основными этическими документами: Конвенция о правах человека и биомедицине Клятва Гиппократа Клятва российского врача. Тексты: Конвенция о правах человека и биомедицине Клятва Гиппократа Клятва российского врача.