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

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

Из условия:

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

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

Из условия 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) = x7 x4 x3 x2 1, данный многочлен найден по таблице 6.1 образующих многочленов помехоустойчивых кодов, взят один из четырех возможных. Имеем циклический код (14; 7).

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

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

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

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

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

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

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

В итоге имеем (nS; k) с gΣ(x) = g1(x) · g2(x) · g3(x) · …gS(x).

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

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

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

1. Сначала найдем n1 и g1(x) для S = 1.

  • d = 2 · S + 1 = 2 · 1 + 1 = 3;
  • 2n1k– 1 ≥ n1; 2n17– 1 ≥ n1; n1min = 11; m1 = n1k = 4;
  • по таблице находим: g1(x) = x4 x 1 или x4 x3 1.

2. Найдем n2 и g2(x) для S = 1.

  • d = 2 · S + 1 = 2 · 1 + 1 = 3;
  • 2n2n1– 1 ≥ n2; 2n211– 1 ≥ n2; n2min = 15; m2 = n2n1 = 4;
  • по таблице находим: g2(x) = x4 x 1 или x4 x3 1.

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

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

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