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

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

Метод является частным случаем перестановочного декодирования. Предположим, что требуется исправить все векторы ошибок e = (e0, …, ev - 1) вес которых не превосходит t при некотором фиксированном t lb [ (d - 1) /2]. Для выполнения декодирования надо найти такое множество подстановок, чтобы код был инвариантен относительно этого множества и чтобы для каждого вектора e, вес которого не превосходит t, нашлась бы подстановка, передвигающая все ошибки из информационных позиций в проверочные.

Метод перестановочного декодирования состоит в следующем. Определим оператор подстановок pj По полученному вектору y вычисляются векторы сдвигов pj {y} и их синдромы s (j), до тех пор, пока не будет найден индекс j, для которого вес wt (s (j)) lb t. При этом все ошибки будут сосредоточены в первых r = n - k позициях вектора pj {y} и задаются равенством [s (j)] T = (e0, …, er - 1). Следовательно, принимаемый вектор декодируется как слово

.

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

Алгоритм.

1. Вычисляется синдром s (x) для принимаемого сигнала y (x), используя алгоритм деления на порождающий полином.

. Установка j: = 0

. Если wt (sj (x)) lb t, тогда полагаем e (x) = x j (sj, 0) и корректируем ошибку, вычисляя y (x) - e (x);

. Устанавливаем j: = j + 1;

. Если j = n, тогда алгоритм останавливается и ошибка считается не выловленной;

. Если deg (sj - 1 (x) < n - k - 1, тогда sj (x) = x sj - 1 (x); в противном случае - sj (x) = x sj - 1 (x) - g (x);

. Перейти к шагу 3.

Декодирование циклического кода путем вылавливания ошибок. Рассмотрим случай декодирования С кода с параметрами (n,k), d=2t+1 и проверочной матрицей H= [In-kA]. Передается кодовое слово с, а принимается вектор

y = c +E,

где E-вектор ошибки.

Синдром вектора y вычисляется как

s = HyT = H (c + E) T = H (E) T.

Образуем вектор E*= (sT, 0), где 0 нулевой вектор, состоящий из k нулей. Нетрудно показать, что выполняется следующее соотношение

H (E*) T = s.

Вектора E и E* имеют один и тот же синдром и соответствуют одному и тому же подмножеству кода C. Предположим, что вес синдрома wt (s) lb t. Тогда wt (E*) lb t и следовательно E = E* так как соответствующее подмножество кода C может содержать только один вектор заданного веса. Следовательно, вектор ошибки можно записать через E = (sT,0). Теперь предположим, что структура вектор ошибки веса не менее t может иметь в своем составе циклический сдвиг пачки из k нулей. На определенном i - ом циклическом сдвиге в структуре вектора ошибки отличные от нуля символы будут располагаться на первых (n-k) позициях. Для этого значения i вес соответствующего синдрома wt (si (x)) lb t, где si (x) - синдром mod (xn-1). Если синдром si (x) вычислять как остаток от деления xiy (x) на порождающий полином g (x), тогда wt (si (x)) lb t для значений i соответствующих соотношению xiE (x) = (si, 0).

Таким образом, вектору ошибки E (x) соответствует циклический сдвиг E (x) = xi (si, 0).

Такое свойство синдрома позволяет построить следующий алгоритм декодирования.

Алгоритм I.

1. Вычисляется синдром s (x) для принимаемого сигнала y (x), используя алгоритм деления на порождающий полином.
2. Установка i: = 0
3. Если wt (si (x)) lb t, тогда полагаем E (x) = xi (si, 0) и корректируем ошибку, вычисляя y (x) - E (x);
4. Устанавливаем i: = i+1;
5. Если i = n, тогда алгоритм останавливается и ошибка считается не выловленной;
6. Если deg (si-1 (x) < n-k-1, тогда si (x) = x si-1 (x); в противном случае - si (x) = x si-1 (x) - g (x);
7. Перейти к шагу 3.

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

Предположим, что передается кодовое слово c (x) = 1+x+x5 = (1+x+x2) g (x), а принимается вектор y (x) = 1+x+x5+x6. Разделим вектор y (x) на порождающий полином g (x)

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

Такт как вес синдрома больше 1, то вычисляем синдром циклического сдвига s1 (x) для xy (x). Поскольку степень синдрома s (x) равна 2 = n-k-1, то

s1 (x) = xs (x) mod g (x) = 1.

Вес синдрома равен единице и соответствует корректирующей способности кода. Следовательно, вектор ошибки равен

E (x) = x7-1 (s1,0) = x6 (100 0000) = x6.

Пример. Пусть g (x) = 1+x4+x6+x7+x8 генерирует бинарный циклический код (15,7,5), позволяющий исправлять две ошибки.

Любая ошибка веса два содержащая в своей структуре пачку из 7 нулей может быть выловлена.

Предположим, что принимается вектор y= (1100 1110 1100 010). Вычислим синдром y (x) = (x +x2+x4+x5) g (x) + (1+x2+x5+x7). Далее, вычисляем синдромы si (x) для циклических сдвигов xiy (x) до тех пор, пока вес синдрома не станет не более двух wt (si (x)) lb2.

Вычисления сведем в таблицу

iSi (x) 010100101111011001211100111311111000401111100500111111600011111710000100

Ошибка представляется как

E = x15-7 (s7,0) = x8 (10000100 0000000) = (0000 0000 1000 010),

Декодируем кодовое слово как

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

Пакеты ошибок

Характерной особенностью циклических кодов является способность к распознаванию пакетов ошибок. Под пакетом ошибок понимается группирование ошибок в одной ограниченной области кодового слова. Пакет ошибок в полиномиальном виде можно представить как

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

.

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

Граница Рейджера. Для любого линейного (n, k) - кода, исправляющего пачки ошибок длиной b и меньше, должно выполняться следующее соотношение: n - k ^3 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) ^3 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) ^3 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