Geum.ru

Метод вылавливания ошибок

Доклад - Компьютеры, программирование

Другие доклады по предмету Компьютеры, программирование

ченной области кодового слова. Пакет ошибок в полиномиальном виде можно представить как

 

 

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

 

.

 

Пакет ошибок начинается и заканчивается отличным от нуля символом. Если длина пакета не превосходит величины r = n - k, то степень полинома ошибок меньше r. В этом случае e (x) не делится на g (x) без остатка и синдром принятого слова всегда отличен от нулевого. Пакет ошибок длиной равной или меньшей r всегда распознается. Распознается также любой циклический сдвиг многочлена b (x) степени, меньшей r. Для циклического (n, k) - кода доля не обнаруживаемых пакетов ошибок длины l > r + 1 равна 2 - r.

Граница Рейджера. Для любого линейного (n, k) - кода, исправляющего пачки ошибок длиной b и меньше, должно выполняться следующее соотношение: n - k 2b.

Теорема Файра. Пусть C - циклический код длиной n0 c порождающим многочленом g0 (x), исправляющий пачки ошибок длиной b и менее, и пусть g1 (x) - неприводимый взаимно простой с g0 (x) многочлен с периодом n1, степень которого не меньше b. Тогда циклический код длиной n = (n0 n1/НОД (n0, n1)) с порождающим многочленом g (x) = g0 (x) g1 (x) исправляет пачки ошибок длиной b и менее.

Из теоремы следует, что если g1 (x) - неприводимый многочлен с периодом n1, степень которого не меньше b, взаимно простой с полиномом (x2b - 1), тогда циклический код длиной (2b - 1) n1/ НОД (2b - 1, n1) с порождающим многочленом (x2b-1 - 1) g1 (x) исправляет пачки ошибок длиной b и менее. Такой код называется кодом Файра, он имеет более чем 3b - 1 проверочных символов, что на b - 1 больше нижней границы Рейджера, равной 2b.

Декодирование пачки ошибок методом вылавливания. Параметры корректирующего кода (n, k), исправляющего пачки ошибок длиной t, должны удовлетворять условию (n - k) 2t. Предполагается, что структура вектора пачки ошибок длиной t имеет отрезок из (n - t) нулевых элементов. Если вектор e представляет собой пачку ошибок длиной t и ошибки располагаются на первых (n - k) позициях вектора, тогда синдром H (eT) = s характеризует структуру пачки ошибок длины не более t. Если ошибки располагаются не первых (n - k) позициях вектора, то для вычисления оценки ошибки используется свойство циклического сдвига синдрома, как и в рассмотренном выше случае, только контролируется не вес используется его свойство (см. алгоритм I). Контролируется (n - k) первых позиций синдрома. Если конфигурация синдрома sj (x) идентифицирует пачку ошибок длиной t или менее, то вектор ошибок e (x) = xn - j (si,0).

вылавливание ошибка циклический код

Декодирование пачки ошибок методом вылавливания. Параметры корректирующего кода (n,k), исправляющего пачки ошибок длиной t, должны удовлетворять условию (n-k) 2t. Предполагается, что структура вектора пачки ошибок длиной t имеет отрезок из (n-t) нулевых элементов. Если вектор E представляет собой пачку ошибок длиной t и ошибки располагаются на первых (n-k) позициях вектора, тогда синдром H (ET) = s характеризует структуру (нециклической) пачки ошибок длины не более t. Если ошибки располагаются не первых (n-k) позициях вектора, то для вычисления синдрома используется его свойство (см. алгоритм I).

Алгоритм II.

  1. Вычисляется синдром s (x) для y (x).
  2. Устанавливается i: =0.
  3. Контролируется (n-k) первых позиций синдрома. Если конфигурация синдрома si (x) идентифицирует пачку ошибок (нециклическую) длиной t или менее, то вектор ошибок E (x) = xn-i (si,0).
  4. Устанавливается i: = i+1.
  5. Если i = n, то алгоритм останавливается и считается, что ошибка не вылавливается.
  6. Вычисляется синдром si (x) по аналогии с алгоритмом I.
  7. Переход к шагу 3.

Пример. Пусть g (x) = 1+x+x2+x3+x6 генерирует бинарный циклический код (15,9), позволяющий исправлять пачку ошибок длиной t = 3. Принимаемый вектор

 

y = (1110 1110 1100 000).

 

Вычислим синдром

 

y (x) = (x2+x3) g (x) + (1+x+x4+x5), s (x) = (1+x+x4+x5).

 

Конфигурация первых символов (n-k) =15 - 9 =6 синдрома не соответствует пачки ошибки длиной 3. Вычисляем значения синдрома для других циклических сдвигов принимаемого сигнала:

 

isi (x) 0110011110010121011103010111411011151001116101111710101181010019101000 - пачка ошибок t = 3

Вектор ошибок вычисляется как E (x) = xn-i (s9,0) = x6 (101000 000000000) = (000000 101000000) mod (x15-1).

Переданное кодовое слово восстанавливается как

 

c (x) = y (x) - E (x) = (1110 1100 0100 000).

 

Заметим, что в рассматриваемом примере синдром s8 (x) имеет вес равный 3, но конфигурация структуры не соответствует пачки ошибок длиной 3.

В таблице приводятся сведения о корректирующей способности пачки ошибок некоторых циклических кодов

 

g (x) (n,k) Длина исправляемой пачки ошибок t1+x2+x3+x4 (7,3) 21+x2+x4+x5 (15,10) 21+x4+x5+x6 (31,25) 1+x3+x4+x5+x6 (15,9) 31+x+x2+x3+x6 (15,9) 3