Определить, есть ли ошибка в принятом кодовом слове, и если да — в каком разряде она произошла

Предмет: Информатика / Теория информации
Раздел: Кодирование информации — Линейные коды, Полиномиальное деление, Коды БЧХ, CRC (циклический избыточный код)

Условие задачи:

Дан код БЧХ или циклический код с параметрами (7;4):
Кодовое слово: 1111001
Порождающий многочлен: P(x) = x^3 + x + 1

Нужно определить, есть ли ошибка в принятом кодовом слове, и если да — в каком разряде она произошла.

Шаг 1: Анализ кода

Код (7;4) — это линейный блоковый код длины 7 с 4 информационными битами. Значит, в кодовом слове 4 информационных бита и 3 проверочных (избыточных) бита.
Порождающий многочлен P(x) = x^3 + x + 1 используется для формирования и проверки кода.

Шаг 2: Представим принятое слово как многочлен

Принятое слово: 1111001
Это соответствует многочлену:

R(x) = x^6 + x^5 + x^4 + x^3 + 1

(т.е. коэффициенты при степенях x: 1 1 1 1 0 0 1 → x⁶ + x⁵ + x⁴ + x³ + x⁰)

Шаг 3: Проверка на делимость

Чтобы проверить, есть ли ошибка, нужно выполнить деление R(x) на P(x).
Если делится нацело (остаток 0), то ошибок нет.
Если есть остаток — значит, ошибка есть.

Шаг 4: Полиномиальное деление

Делим R(x) = x^6 + x^5 + x^4 + x^3 + 1 на P(x) = x^3 + x + 1 по модулю 2 (все операции по модулю 2: сложение — это XOR).

Выполним деление в столбик:

1. Первая часть деления: x^6 ÷ x^3 = x^3
   Умножаем x^3 на P(x):
   x^3(x^3 + x + 1) = x^6 + x^4 + x^3
   Вычитаем (т.е. XOR) из R(x):

   (x^6 + x^5 + x^4 + x^3 + 1) ⊕ (x^6 + x^4 + x^3) = x^5 + 1

2. Осталось: x^5 + 1
   x^5 ÷ x^3 = x^2
   Умножаем: x^2(x^3 + x + 1) = x^5 + x^3 + x^2
   Вычитаем:

   (x^5 + 1) ⊕ (x^5 + x^3 + x^2) = x^3 + x^2 + 1

3. Осталось: x^3 + x^2 + 1
   x^3 ÷ x^3 = 1
   Умножаем: 1 * (x^3 + x + 1) = x^3 + x + 1
   Вычитаем:

   (x^3 + x^2 + 1) ⊕ (x^3 + x + 1) = x^2 + x

Шаг 5: Остаток

Остаток от деления: x^2 + x ≠ 0
Значит, в принятом кодовом слове есть ошибка.

Шаг 6: Определение позиции ошибки

Для циклических кодов при одиночной ошибке можно найти позицию ошибки, сравнив остаток с синдромами.

Синдром — это остаток от деления принятого слова на порождающий многочлен.
Если ошибка одиночная, то она соответствует одному из векторов с одной единицей (например, 0000001, 0000010, ..., 1000000), что соответствует многочленам x^0, x^1, ..., x^6.

Найдем, при каком x^i остаток от деления x^i на P(x) равен x^2 + x

Проверим:

• x^0 = 1 → остаток: 1
• x^1 = x → остаток: x
• x^2 → остаток: x^2
• x^3 → делится на P(x), остаток: 0
• x^4 → x^4 ÷ x^3 = x,
  x(x^3 + x + 1) = x^4 + x^2 + x,
  x^4 ⊕ (x^4 + x^2 + x) = x^2 + x ✅

Значит, ошибка в разряде, соответствующем x^4 — это пятый бит (нумерация справа налево, начиная с 0).

Ответ:

• Ошибка есть
• Позиция ошибки: 5-й разряд (считаем справа налево, начиная с 0; или 3-й бит слева в записи 1111001)

Проверка:

Изначальное слово: 1111001
Поменяем 5-й бит (слева направо: 1 1 1 1 0 0 1), т.е. третий бит слева (значение 1) → на 0:
Получим: 1101001

Проверим, делится ли 1101001 на P(x) — остаток будет 0 ✅

Окончательный ответ:

Ошибка есть, в 5-м разряде (считая справа налево от младшего бита, или 3-й бит слева).