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

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

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

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

.

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

Алгоритм.

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

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

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

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

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

6. Если deg (s_{j - 1} (x) < n - k — 1, тогда s_j (x) = x s_{j - 1} (x); в противном случае — s_j (x) = x s_{j - 1} (x) — g (x);

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

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

y = c +E,

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

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

s = Hy^T = H (c + E) ^T = H (E) ^T.

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

H (E*) ^T = s.

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

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

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

Алгоритм I.

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

Установка i: = 0

Если wt (s_i (x)) t, тогда полагаем E (x) = xⁱ (s_i, 0) и корректируем ошибку, вычисляя y (x) — E (x);

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

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

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

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

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

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

y (x) = (x³+1) g (x) + (x+x²), s (x) = (x+x²).

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

s₁ (x) = xs (x) mod g (x) = 1.

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

E (x) = x⁷⁻¹ (s₁,0) = x⁶ (100 0000) = x⁶.

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

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

Предположим, что принимается вектор y= (1100 1110 1100 010). Вычислим синдром y (x) = (x +x²+x⁴+x⁵) g (x) + (1+x²+x⁵+x⁷). Далее, вычисляем синдромы s_i (x) для циклических сдвигов xⁱy (x) до тех пор, пока вес синдрома не станет не более двух wt (s_i (x)) 2.

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

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

E = x¹⁵⁻⁷ (s₇,0) = x⁸ (10 000 100 0) = (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 2b.

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

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

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

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

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

Алгоритм II.

Вычисляется синдром s (x) для y (x).

Устанавливается i: =0.

Контролируется (n-k) первых позиций синдрома. Если конфигурация синдрома s_i (x) идентифицирует пачку ошибок (нециклическую) длиной t или менее, то вектор ошибок E (x) = x^n-i (s_i, 0).

Устанавливается i: = i+1.

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

Вычисляется синдром s_i (x) по аналогии с алгоритмом I.

Переход к шагу 3.

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

y = (1110 1110 1100 000).

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

y (x) = (x²+x³) g (x) + (1+x+x⁴+x⁵), s (x) = (1+x+x⁴+x⁵).

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

Вектор ошибок вычисляется как E (x) = x^n-i (s₉, 0) = x⁶ (101 000 0) = (0 101 000 000) mod (x¹⁵-1).

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

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

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

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