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

Date: 2015-10-07; view: 438.

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

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

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

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

Відповідні рекурентні та перевірочні співвідношення також називаються покриваючими або похідними.

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

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

Який початковий стан та яке рекурентне співвідношення відповідає сумі цих рекурент?

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

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