Вираз елементів рекуренти через початковий стан

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

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

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

Нехай - рядки одиничної матриці порядка . Розглянемо кожний рядок як початковий стан відповідної рекуренти .

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

Координати наступного вектора можна отримати як останні біти станів , або одною матричною операцією: - цеостанній стовбчик з матриці .

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

У добутку матриць останній стовбчик матриці дорівнює добутку матриці на останній стовбчик матриці . Це означає, що сусідні стовбчики матриці пов'язані співвідношенням , або , де - довільне ціле число, оскільки матриця оборотна.

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

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

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