Контрольная работа №5 (Пример)

Дано:

n = 15

𝐹 = (𝑥⁴ + 𝑥³ + 1) · (𝑥⁴ + 𝑥³ + 𝑥² + 𝑥 + 1)

𝐸̃ = 506438

Найти:

𝑒8−? И10−?

Решение

1. Раскроем скобки полинома:

𝐹 = (𝑥⁴ + 𝑥³ + 1) · (𝑥⁴ + 𝑥³ + 𝑥² + 𝑥 + 1) = 𝑥⁸ + 𝑥⁷ + 𝑥⁶ + 𝑥⁵ + 𝑥⁴ +

𝑥⁷ + 𝑥⁶ + 𝑥⁵ + 𝑥⁴ + 𝑥³ + 𝑥⁴ + 𝑥³ + 𝑥² + 𝑥 + 1 = 𝑥⁸ + 𝑥⁴ + 𝑥² + 𝑥 + 1 ⫘

100010111₂

2. Используя таблицу разложения полинома 𝑥^𝑛 + 1 (см. лекции) выпишем корни нашего полинома F:

𝑥⁴ + 𝑥³ + 1 – корни 𝛼8, 𝛼12, 𝛼14, 𝛼15

𝑥⁴ + 𝑥³ + 𝑥² + 𝑥 + 1– корни 𝛼4, 𝛼7, 𝛼10, 𝛼13

Среди полученных корней найдѐм число m, которое определяется, как

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

𝛼4, 𝛼7, 𝛼8, 𝛼10𝛼12, 𝛼13, 𝛼14, 𝛼15 => m = 4

3. Определим максимальное количество ошибок, которое может исправить полином F

𝑚

𝑚 = 𝑑𝑚𝑖𝑛 − 1 ≥ 2𝑡 + 1 − 1 = 2𝑡 → 𝑡 ≤ 2 = 2

Т.е. полином F позволяет исправить ошибки в 2-х разрядах

закодированного сообщения.

4. Попробуем обнаружить и исправить ошибки

𝐸̃ = 506438 = 101000110100011 2

Ищем остаток от деления 𝐸̃ на F

(cм фото)

5. Значит вектор ошибки, смещѐнный на 5 разрядов влево равен

2

5 = 000000000010001

𝑒→

Сдвинем его на 5 разрядов вправо и получим исходный вектор

ошибки

𝑒 = 1000100000000002 = 420008

6. Исправим ошибку

𝐸 = 𝐸̃ xor 𝑒 = 10101101000112

7. Выделим информационную часть кода.

Количество проверочных разрядов равно степени образующего полинома, значит r = 8.

Отбрасываем 8 разрядов справа: 𝐸инф = 101012

и переворачиваем: И = 101012 = 2110

Ответ:

𝑒 = 420008

И = 2110