Размещено на http://www.allbest.ru/

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

Метод является частным случаем перестановочного декодирования. Предположим, что требуется исправить все векторы ошибок 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^7-1 (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^15-7 (s₇,0) = x⁸ (10000100 0000000) = (0000 0000 1000 010),

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