Исправление ошибок произвольной кратности

Пусть имеется k информационных разрядов. Хотим исправлять ошибки кратности S.

Из условия:

находим n и следовательно m = n – k.

Из условия d ≥ (2S + 1) находим количество значащих членов в образующем многочлене g(x) степени m. Из полученных данных m и d по таблице неприводимых многочленов (таблица 6.1) подбираем нужный g(x). Получим помехоустойчивый код с минимальным количеством проверочных символов.

Например:

k = 7; S = 2. Найдем g(x).

1. d = 2S + 1 = 2 · 2 + 1 = 5, то есть в образующем многочлене g(x) должно быть 5 значащих членов.

2.

.

Решаем подбором:

1. При n = 16 имеем m = 16 – 7 = 9.

,

m = 9 > 8.

2. При n = 15 имеем m = 15 – 7 = 8.

,

m = 8 > 7.

3. При n = 14 имеем m = 14 – 7 = 7.

,
.

Решение: g(x) = x⁷ x⁴ x³ x² 1, данный многочлен найден по таблице 6.1 образующих многочленов помехоустойчивых кодов, взят один из четырех возможных. Имеем циклический код (14; 7).

4. При n = 13 имеем m = 13 – 7 = 6.

,
,

n = 13 – не подходит.

Рассмотрим другой, не оптимальный метод формирования g(x) для исправления ошибок кратности S.

1. По заданному «k» определяем «m» и строим код, исправляющий одиночные ошибки. Получим код (n₁; k) с g₁(x).

2. Рассматривая полученный код как безизбыточный, снова строим Ц.К., способный исправлять единичные ошибки. В результате получаем код, исправляющий двойные ошибки по отношению к исходному коду. http://peredacha-informacii.ru/ Повторяя эту операцию S раз, получаем код, исправляющий ошибки кратности до S включительно.

В итоге имеем (n_S; k) с g_Σ(x) = g₁(x) · g₂(x) · g₃(x) · …g_S(x).

Полученный код не является оптимальным, так как число проверочных символов не минимально.

Покажем это на том же примере:

k = 7; S = 2. Найдем g_Σ(x) = g₁(x) · g₂(x).

1. Сначала найдем n₁ и g₁(x) для S = 1.

• d = 2 · S + 1 = 2 · 1 + 1 = 3;
• 2^n₁–k– 1 ≥ n₁; 2^n₁–7– 1 ≥ n₁; n_1min = 11; m₁ = n₁ – k = 4;
• по таблице находим: g₁(x) = x⁴ x 1 или x⁴ x³ 1.

2. Найдем n₂ и g₂(x) для S = 1.

• d = 2 · S + 1 = 2 · 1 + 1 = 3;
• 2^n₂–n₁– 1 ≥ n₂; 2^n₂–11– 1 ≥ n₂; n_2min = 15; m₂ = n₂ – n₁ = 4;
• по таблице находим: g₂(x) = x⁴ x 1 или x⁴ x³ 1.

3. В итоге получаем:

• 
• g_Σ(x) содержит 7 значащих членов, что на два символа больше, чем в ранее рассмотренном методе.

Известны оптимальные коды Боуза-Чоудхури-Хоквингема (сокращенно БЧХ), но они требуют более сложных кодирующих и декодирующих устройств.