Выбор образующего многочлена для исправления одиночных ошибок

Для исправления одиночных ошибок в n разрядной К.К. необходимо определить, какой разряд был искажен. Поэтому каждому вектору ошибки необходимо сопоставить свой остаток. Для исправления одиночной ошибки должно быть выполнено условие:

2nk – 1 = 2m – 1 ≥ Cn1 = n,

то есть 2mn + 1;

Выбор образующего многочлена для исправления одиночных ошибок.

Из последнего равенства определяется число проверочных разрядов – это целое число с округлением log2(n + 1) в большую сторону. В теории кодирования доказано, что если m и n связаны условием n = 2m – 1, то многочлен может быть представлен произведением всех без исключения неприводимых многочленов степени которых являются делителями числа «m» от единицы до «m». Причем всегда имеется хотя бы один многочлен степени «m». Таблицы таких многочленов приведены в литературе по кодированию (см. таблицу 6.1).

Для исправления одиночных ошибок минимальная дистанция между двумя Р.К.К. должна быть:

d ≥ 2S + 1 = 2·1 + 1 = 3.

Таким образом, нам потребуется выбрать g(x), удовлетворяющий двум условиям: и d = 3, где m – максимальная степень образующего многочлена, а d – количество значащих членов в нем.

Например:

Пусть n = 15; S = 1; тогда 2nk – 1 ≥ n, откуда k = 11 и m = n k = 15 – 11 = 4 или

Выбор образующего многочлена для исправления одиночных ошибок.
  1. Делителями числа «m» являются: 1; 2; 4.
  2. Разложим на сомножители: Выбор образующего многочлена для исправления одиночных ошибок.
  3. Нас интересуют неприводимые многочлены степени m = 4. Таких многочленов в разложении – три.
  4. Проверим, дают ли они n = 15 различных остатков, чтобы поставить им в соответствие ошибки в различных разрядах. Пусть . Остатки будем получать путем деления X j на g1(x).
Выбор образующего многочлена для исправления одиночных ошибок
Выбор образующего многочлена для исправления одиночных ошибок

Получили 15 различных остатков, а шестнадцатый остаток такой же, как первый.

Так же 15 различных остатков можно получить при . Однако, при получим лишь 5 различных остатков:

Выбор образующего многочлена для исправления одиночных ошибок

Это получилось потому, что g3(x) входит в разложение не только Выбор образующего многочлена для исправления одиночных ошибок, но и в разложение , так как .

Выбор образующего многочлена для исправления одиночных ошибок

Выбирая в качестве многочлена g(x) многочлен m – ной степени, входящий в разложение , необходимо проверить, что он не входит в разложение , где λ < n. http://peredacha-informacii.ru/ В данном случае не было необходимости проверять число различных остатков, которые дает g3(x). В g3(x) пять значащих членов, а нам для исправления одиночной ошибки нужны g(x), содержащие всего 3 значащих члена, то есть g1(x) или g2(x), так как d = 2S + 1 = 2 · 1 + 1 = 3.

После того как вы ознакомились с содержанием данного раздела, предлагаем вам решить задачу. Если у вас в процессе решения возникнут затруднения, то предлагаем вам воспользоваться помощью.