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

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

2^{n – k} – 1 = 2^m – 1 ≥ C_n¹ = n,

то есть 2^m ≥ n + 1;

.

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

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

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

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

Например:

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

.

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

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

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

Это получилось потому, что g₃(x) входит в разложение не только , но и в разложение , так как .

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

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