Існування тричленних похідних співвідношень

Анулюючі та мінімальні многочлени послідовностей

над полем

Означення. Анулюючим многочленом послідовності , називається такий многочлен над полем , що , де – нульова послідовність.

Означення. Мінімальним многочленом послідовності , називається нормований анулюючий многочлен найменшого степеня.

Мінімальним многочленом рекурентної послідовності над полем є многочлен

який є мінімальним многочленом матриці , оскільки вона для цього многочлену є супроводжуючою. За побудовою, для кожного такту роботи РЗЛЗЗ він задає співвідношення

або

, де .

Початковий стан рекуренти складається з елементів.

Приклад. Мінімальним многочленом рекурентної послідовності з рекурентним співвідношенням буде многочлен

або

Покажемо, що для нашої рекуренти існують інші рекурентні співвідношення.

Розглянемо многочлен виду і побудуємо для нього супроводжуючу матрицю, порядок якої дорівнює . Тоді коефіцієнти многочлена задають для деякої рекуренти співвідношення виду

або

Коефіцієнти можна легко отримати за правилами добутку многочленів , за якими набір коефіцієнтів многочлена зсувається на величину степеня кожного одночлену , що входить до , а потім ці зсуви виду підсумовуються. Таким чином, вектор коефіцієнтів дорівнює сумі деяких таких зсувів.

Многочлени виду називаються похідними, або покриваючими многочленами рекурентної послідовності з мінімальним многочленом .

Застосуємо до нашої рекуренти рекурентне співвідношення з коефіцієнтами . Рекурента задовольняє співвідношенню для довільного зсуву, а це значить, що вона буде задовольняти рекурентне співвідношення з коефіцієнтами .

Нехай тепер задані дві рекурентні послідовності з відомими рекурентними співвідношеннями (мінімальними многочленами , ) і початковими станами і , розмірності яких задовольняють умову .

Рекурентне співвідношення для суми цих рекурент задають коефіцієнти многочлена , тому що цей многочлен є покриваючим для кожної з рекурент. Тому довжина (розмірність) початкового стану дорівнює .

Якщо ми продовжимо і , за відповідними рекурентними законами до бітів, то отримаємо послідовності і , з яких отримаємо .

Як нам відомо, для того, щоб послідовність векторів , , мала максимальний період , слід вибирати мінімальний многочлен примітивним многочленом степеня над полем . Тому будемо вважати многочлен примітивним.

У цьому випадку послідовність , при пробігає всі ненульові двійкові вектори, тобто довільний вектор дорівнює вектору при деякому .

Виберемо в матриці , рядками якої є рекуренти два ненульових нерівних вектори , і обчислимо вектор . За попереднім, існує ціле , таке, що .

При цьому

, ,

звідки

і .

Таким чином, для нашої рекуренти виконується тричленне співвідношення

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Вираз елементів рекуренти через початковий стан	\|	Алгоритм Берлекемпа-Мессі

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.