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

Алгоритм Берлекемпа-Мессі

Знаходження покриваючого співвідношення для лінійної рекуренти методом Гаусса

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

.

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

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

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

Приклад. Для послідовності =1100011011101 з мінімальним многочленом побудувати покриваючий многочлен методом Гаусса.

Розв'язання. Оскільки довжинарекурентної послідовності дорівнює , , а , то двійкова матриця має розмірність . Складемо матрицю з елементів послідовності з наступними номерами:

тобто

Знайдемо ненульовий розв’язок системи рівнянь . Застосуємо метод Гаусса:

Невідомі – базисні, невідомі – вільні. Виразимо базисні невідомі через вільні:

Надамо вільним невідомим довільних значень, наприклад, . Будемо мати .

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

.

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

.

Зауваження. Для знаходження мінімального многочлена цим методом необхідно перебирати довжину шуканого регістру та після відновлення многочленів перевіряти, чи відповідне рекурентне співвідношення виконується для всього відрізку послідовності. Для швидкого знаходження мінімального многочлена для відрізку довільної рекуренти існує спеціальний алгоритм (Берлекемпа-Мессі).

Алгоритм Берлекемпа-Мессі призначений для знаходження конфігурації регістра зсуву з лінійним зворотним зв’язком мінімальної довжини, який генерує задану скінчену послідовність, що складається з елементів поля . Розглянемо випадок поля .

Конфігурація регістра – це довжина регістра та перелік коефіцієнтів лінійної форми , яка реалізує функцію зворотного зв’язку.

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

Для покладаємо:

, , .

– коефіцієнт при степені в многочлені ,

Для

,

– коефіцієнт при степені в многочлені .

Шуканий мінімальний многочлен визначається рівністю

.

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

.

Приклад. Знайти конфігурацію РЗЛЗЗ мінімальної довжини, який генерує скінченну послідовність над полем : 1100011011.

Розв’язання. Запишемо покриваючий многочлен для згенерованої частини послідовності:

.

Для покладаємо:

, , ,

,

– коефіцієнт при степені в многочлені .

,

, оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

,

, оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

,

,

оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

,

,

оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

,

, оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

,

, оскільки .

, оскільки .

.

– коефіцієнт при степені в многочлені .

,

, оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

,

,

оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

,

, оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені

,

, оскільки .

, оскільки .

,

– коефіцієнт при степені в многочлені .

Протокол роботи алгоритму зручно оформлювати у вигляді таблиці:

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

.

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

1. Rete-алгоритм
2. Алгоритм
3. Алгоритм
4. Алгоритм 1.
5. Алгоритм RLE
6. Алгоритм безпосередньої заміни
7. Алгоритм відшукання оптимального плану.
8. Алгоритм Дейкстри.
9. Алгоритм Деккера.
10. Алгоритм Деккера.
11. Алгоритм діагностики при травмах живота.

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