• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Запис станів двійкового регістру через супроводжуючу матрицю

Розглянемо матрицю , для якої елементи останнього стовпця з номерами дорівнюють одиниці, а решта – нулі.

, , .

Матриця називається супроводжуючою матрицею послідовності.

Матриця оборотна і

,

тобто

.

Звідки

і , .

Зокрема, якщо

,

то

,

де рекуренти додаються поелементно.

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

Точки знімання мають номери 0 і 2, тому в останньому стовпці елементи і , а решта – нулі.

Виразимо послідовність початкових станів 11000 10001 00011 00110 … через супроводжуючу матрицю:

;

;

;

……………………………………………………….

Стан регістру після -го такту роботи дорівнює

.

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

.

Це дозволяє розглядати рекуренту з векторним початковим станом.

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

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

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

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

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

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

,

або

,

де – довільне ціле число, оскільки матриця оборотна. Таким чином, ми легко можемо обчислити вектори . Назвемо стовпці матриці характеристичними векторами.

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

Приклад. Розглянемо одночасно послідовності станів регістра з рекурентним співвідношенням для початкових станів.

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

Перший крок (перехід від початкового стану до стану з номером ) дає

тобто .

Другий крок (перехід від стану до стану ) дає

тобто і так далі.

Тепер треба сумістити стани, щоб отримати рекурентних послідовностей, які підписані одна під одною

Маємо 5 початкових станів (рядки матриці ), далі 5 станів після кроку 1 (рядки матриці ) і 5 станів після кроку 2 (рядки матриці ).

Суміщаємо стани з перших рядків: 1000010, з других рядків: 0100001 і так далі. Але це теж саме, що суміщати сусідні матриці, бо останні 4 стовпчики попередньої матриці і перші 4 стовпчики наступної матриці співпадають, тобто маємо:

.

Розгорнемо матрицю до кінця періоду. У цієї матриці стовпці з номерами 0-4 утворюють матрицю , стовпці з номерами 1-5 утворюють матрицю , стовпці з номерами 2-6 утворюють матрицю і т.д. Таким чином, матриці, що перетинаються по 4-х стовпцях мають вид , і їхні останні стовпці розташовані поруч. Але за правилами множення матриць з рівності випливає, що останній стовпець матриці дорівнює добутку матриці на останній стовпець матриці , тобто , , і так далі.

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

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

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

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

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

1. II. За зміною ступенів окиснення елементів, які входять до складу реагуючих речовин
2. Акустичний контроль приміщень через засоби телефонного зв'язку
3. Аналіз ризику через моделювання.
4. Аналіз службового призначення деталей та конструктивних елементів обладнання харчових виробництві, визначення технічних вимог і норм точності при їх виготовленні
5. Аналітичний вираз сил і моментів.
6. Баланс (початковий)
7. Бізнес через Internet
8. Біоелектричні явища в тканинах: будова мембран клітини, транспорт речовин через мембрану, потенціал дії та його розповсюдження.
9. Будова атомів хімічних елементів.
10. Будова нагрівальних елементів
11. В чому полягає явище тунелювання через потенціальний бар’єр, наведіть приклади.
12. В. Розрахунки через Інтернет

Переглядів: 1092