М- и (М-1)-последовательности на основе произведения многочленов. Результаты по синтезу модели: структурная схема, методика построения по алгоритму Хемминга и по корреляционному моменту, аффинному преобразованию для заданного множества векторов.
Целью работы является то, что по заданному многочлену построить его структурную схему, найти максимальную последовательность, по данной последовательности найти соответствующие АКФ по корреляционному моменту, по алгоритму Хэмминга и по аффинному преобразованию. Определение: Последовательностью над полем GF(2) будем называть любую функцию заданную на множестве N и принимающую значения в поле GF(2). Определение: Последовательность над полем GF(2), получаемая по соотношению X (t 1)= и имеющая максимальный период , называется максимальной линейной рекуррентной последовательностью - M-последовательностью. Замечание: ппоследовательности имеют статистическую равномерность на периоде L= ., т.е. число единиц и нулей определяется величинами и 1.2 М-последовательности на основе произведения многочленов Из этого утверждения следует, что если выбраны неприводимые полиномы , которым соответствуют ЛРП с взаимно простыми периодами , определяемыми порядками этих многочленов, тогда характеристическому полиному соответствует ЛРП с периодом , Пример: Пусть заданы неприводимые примитивные полиномы , а также характеристическим полиномом видаВ своей работе, я построил с помощью непримитивного многочлена структурную схему ЛРС и (М-1) последовательность, по которой нашли коэффициент корреляции и построили график, нашли АКФ по корреляционному моменту.
Введение
Целью работы является то, что по заданному многочлену построить его структурную схему, найти максимальную последовательность, по данной последовательности найти соответствующие АКФ по корреляционному моменту, по алгоритму Хэмминга и по аффинному преобразованию. Произведение двух полиномов будет равняться:
Где -примитивный.
Построим: ЛРС по полиному f(x)
Максимальную последовательность
АКФ по алгоритму Хэмминга
АКФ по корреляционному моменту
Последовательности по аффинному преобразованию для заданного множества векторов, и соответствующие АКФ
1. Теоретические элементы
1.1 ГПСП на ЛРС многочлен аффинный вектор хемминг
Определение: Последовательностью над полем GF(2) будем называть любую функцию заданную на множестве N и принимающую значения в поле GF(2).
Рассмотрим класс последовательности , получаемых на основе схемы линейного регистра сдвига с обратной связью (ЛРС), изображенной на рис. 1. Схема содержит n-разрядный регистр сдвига (запоминающие ячейки регистра обозначены символами ), сумматоры, обозначенные символом ?, по модулю 2 в цепи обратной связи и цепи(отводы) с коэффициентами передачи . Если , это эквивалентно отсутствию (наличию при ) связи между выходом i-го разряда регистра и входом i-го сумматора ?. Символ принимает значения 0 или 1. Схему, изображенную на рис. 1., обозначим символом ЛРС1.
Определение: Периодом последовательности называется наименьшее число , для которого существует натуральное число К>0, такое, что для всех справедливо равенство
Максимальный период последовательности .В самом деле, при начальное состояние регистра X(0) порождает последовательность , состоящую из одних нулей (запрещенное состояние), а число различных заполнений длины n равно .
Однако в зависимости от структуры обратной связи и от начального состояния регистра период последовательности может быть иным (в частности, даже единичным (L=1))
Определение: Последовательность над полем GF(2), получаемая по соотношению X (t 1)= и имеющая максимальный период , называется максимальной линейной рекуррентной последовательностью - M-последовательностью.
Период ЛРП определяется характеристическим многочленом над полем GF(2) матрицы :
Которым является определитель матрицы ( , где E-единичная матрица размера n. Коэффициенты многочлена f(x) определяют первую строку матрицы Если характеристический многочлен над полем GF(2) является неприводимым и примитивным, то период ЛРП равен .
Замечание: ппоследовательности имеют статистическую равномерность на периоде L= ., т.е. число единиц и нулей определяется величинами и 1.2 М-последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение многочленов, при .
Определение: Многочлены называются взаимно простыми, если их наибольший общий делитель - многочлен h(x) - есть константа.
Пусть - взаимно простые многочлены над полем GF(2), тогда ord (f*g) равно н.о.к. - наименьшему общему кратному порядков [9]
Из этого утверждения следует, что если выбраны неприводимые полиномы , которым соответствуют ЛРП с взаимно простыми периодами , определяемыми порядками этих многочленов, тогда характеристическому полиному соответствует ЛРП с периодом , Пример: Пусть заданы неприводимые примитивные полиномы , а также характеристическим полиномом вида
Соответствующая схема ГПСП представлена на рис. 2., она порождает ЛРП с периодом L=3*7=21 при . Например, ЛРП, снимаемая с пятого разряда регистра, имеет вид 100001111101010011000, если . При . И . ЛРП имеет периоды соответственно L=7 и L=3.
Замечание: Максимальный период, равный произведению взаимно простых периодов, можно получить и другим способом - почленным сложением по модулю двух двоичных ЛРП, определяемых неприводимыми многочленами.
1.3 (М-1) - последовательности на основе произведения многочленов
Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП. Изображенной на рис. 1, при .
1. Пусть характеристический многочлен для схемы ГПСП представлен в виде произведения примитивного многочлена и линейного многочлена , тогда максимальный период многочлена степени n равен (четное число). Последовательности такого типа (с периодом ) принято называть (М-1) - последовательностями. Минимальный период последовательности. Порождаемой ГПСП с рассмотренным характеристическим многочленом, равен 2.
2. В (М-1) - последовательности отсутствуют два(запрещенных) - разрядных двоичных набора, состоящие из чередующихся символов 0 и 1.
3. Число единичных символов в (М-1) - последовательности совпадает с числом нулевых символов в периоде .
Пример: Пусть задан многочлен , где многочлен примитивный.
Последовательность , снимаемая, например, с выхода при , имеет вид , ее период равен = 14. Если в качестве начального состояния взять, например, двоичный набор , то в этом случае период получаемой последовательности равен 2.
1.4 Корреляционный момент и коэффициент корреляции
Корреляционный момент.
1. - мат. ожидание.
2. -дисперсия
3. Корреляционные моменты
Коэффициент корреляции
Коэффициент корреляции по Хэммингу
2. Результаты по синтезу модели
2.1 Структурная схема ЛРС
Задан многочлен , где многочлен примитивный.
2.2 Построение (М-1) последовательности
№ № №
1 1 0 0 1 1 1 22 0 0 0 1 0 1 43 1 1 0 0 1 1
2 0 1 0 0 1 1 23 0 0 0 0 1 0 44 1 1 1 0 0 1
3 0 0 1 0 0 1 24 0 0 0 0 0 1 45 1 1 1 1 0 0
4 1 0 0 1 0 0 25 0 0 0 0 0 0 46 0 1 1 1 1 0
5 0 1 0 0 1 0 26 1 0 0 0 0 0 47 0 0 1 1 1 1
6 1 0 1 0 0 1 27 0 1 0 0 0 0 48 0 0 0 1 1 1
7 0 1 0 1 0 0 28 0 0 1 0 0 0 49 1 0 0 0 1 1
8 0 0 1 0 1 0 29 0 0 0 1 0 0 50 0 1 0 0 0 1
9 1 0 0 1 0 1 30 1 0 0 0 1 0 51 1 0 1 0 0 0
10 1 1 0 0 1 0 31 1 1 0 0 0 1 52 1 1 0 1 0 0
11 0 1 1 0 0 1 32 0 1 1 0 0 0 53 1 1 1 0 1 0
12 0 0 1 1 0 0 33 1 0 1 1 0 0 54 1 1 1 1 0 1
13 0 0 0 1 1 0 34 1 1 0 1 1 0 55 1 1 1 1 1 0
14 0 0 0 0 1 1 35 0 1 1 0 1 1 56 1 1 1 1 1 1
15 1 0 0 0 0 1 36 1 0 1 1 0 1 57 0 1 1 1 1 1
16 1 1 0 0 0 0 37 0 1 0 1 1 0 58 1 0 1 1 1 1
17 1 1 1 0 0 0 38 1 0 1 0 1 1 59 1 1 0 1 1 1
18 0 1 1 1 0 0 39 1 1 0 1 0 1 60 1 1 1 0 1 1
19 1 0 1 1 1 0 40 0 1 1 0 1 0 61 0 1 1 1 0 1
20 0 1 0 1 1 1 41 0 0 1 1 0 1 62 0 0 1 1 1 0
21 0 0 1 0 1 1 42 1 0 0 1 1 0
Последовательность , снимаемая с выхода , при , имеет вид , ее максимальный период равен .
2.3 Построение АКФ по алгоритму Хэмминга
1) Коэффициент корреляции
2) Построение графика.
Совпадений-
Не совпало-
2.4 Построение АКФ по корреляционному моменту
2.5 Построение последовательности по аффинному преобразованию для заданного множества векторов, и соответствующие АКФ
Итак, возьмем . Просуммируем все 62 шага. Получим следующую таблицу.
№ № №
1 0 0 0 1 1 0 22 1 0 0 1 0 0 43 0 1 0 0 1 0
2 1 1 0 0 1 0 23 1 0 0 0 1 1 44 0 1 1 0 0 0
3 1 0 1 0 0 0 24 1 0 0 0 0 0 45 0 1 1 1 0 1
4 0 0 0 1 0 1 25 1 0 0 0 0 1 46 1 1 1 1 1 1
5 1 1 0 0 1 1 26 0 0 0 0 0 1 47 1 0 1 1 1 0
6 0 0 1 0 0 0 27 1 1 0 0 0 1 48 1 0 0 1 1 0
7 1 1 0 1 0 1 28 1 0 1 0 0 1 49 0 0 0 0 1 0
8 1 0 1 0 1 1 29 1 0 0 1 0 1 50 1 1 0 0 0 0
9 0 0 0 1 0 0 30 0 0 0 0 1 1 51 0 0 1 0 0 1
10 0 1 0 0 1 1 31 0 1 0 0 0 0 52 0 1 0 1 0 1
11 1 1 1 0 0 0 32 1 1 1 0 0 1 53 0 1 1 0 1 1
12 1 0 1 1 0 1 33 0 0 1 1 0 1 54 0 1 1 1 0 0
13 1 0 0 1 1 1 34 0 1 0 1 1 1 55 0 1 1 1 1 1
14 1 0 0 0 1 0 35 1 1 1 0 1 0 56 0 1 1 1 1 0
15 0 0 0 0 0 0 36 0 0 1 1 0 0 57 1 1 1 1 1 0
16 0 1 0 0 0 1 37 1 1 0 1 1 1 58 0 0 1 1 1 0
17 0 1 1 0 0 1 38 0 0 1 0 1 0 59 0 1 0 1 1 0
18 1 1 1 1 0 1 39 0 1 0 1 0 0 60 0 1 1 0 1 0
19 0 0 1 1 1 1 40 1 1 1 0 1 1 61 1 1 1 1 0 0
20 1 1 0 1 1 0 41 1 0 1 1 0 0 62 1 0 1 1 1 1
21 1 0 1 0 1 0 42 0 0 0 1 1 1
Совпадений - {0.5}
Несовпадений - {61.5}
АКФ=(61.5-0.5)/62 1
Вывод
В своей работе, я построил с помощью непримитивного многочлена структурную схему ЛРС и (М-1) последовательность, по которой нашли коэффициент корреляции и построили график, нашли АКФ по корреляционному моменту. Далее мы нашли АКФ по алгоритму Хэмминга и вновь построили график. В обоих примерах АКФ был равен -1. В последнем задании, с помощью Аффинного преобразования я нашел АКФ и построил соответствующие графики.
Список литературы
многочлен аффинный вектор хемминг
1) А.Н. Бухарев, В.М. Захаров, Ш.Р. Нурутдинов, В.А. Песошин, С.В. Шалагин. «Вычислительные и автоматные схемы над полем GF(2)» Казань 2006
2) Тезисы Лекций по Компьютерному моделированию
3) В.А. Песошин, В.М. Кузнецов «Генераторы Псевдослучайных и случайных последовательностей на регистрах сдвига» Казань. КГТУ. 2007 г.
Размещено на
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
