V. Синдромы и охота на ошибки

Прежде всего рассмотрим альтернативный вид [R, I_k] порождающей матрицы циклического кода (систематический). Пусть g(x) ПМ кода. Разделим x^n-k+i на g(x) для 0 <= i <= k-1. Это дает

x^n-k+i = q_i(x)g(x) + r_i(x)

где deg(r_i(x)) < deg (g(x)) = n-k или r_i(x) = 0. Then

x^n-k+i - r_i(x) = q_i(x)g(x) in C

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

Пример: Рассмотрим бинарный (7,4)-циклический код, порожденный g(x) = 1 + x + x³. Алгоритм деления дает:

x³ = (1)(x³ + x + 1) + (1+ x)
x⁴ = (x)(x³ + x + 1) + (x + x²)
x⁵ = (x² + 1)(x³ + x + 1) + (1 + x + x²)
x⁶ = (x³ + x + 1)(x³ + x + 1) + (1 + x²).

Порождающая матрица

1 1 0 1 0 0 0 1 1 0

0 1 1 0 1 0 0 0 1 1

G = 1 1 1 0 0 1 0 = [R I₄] где R = 1 1 1

1 0 1 0 0 0 1 1 0 1.

Заметим, что строки R как раз остатки от деления.

Соответствующая проверочная матрица это H = [I_n-k -R^t]. Разделение матрицы подобным образом предоставляет возможность удобной полиномиальной интерпретации синдрома вектора.

Tеорема: Пусть r(x) и s(x) есть соответствующие полиномиальные представления для вектора r и его синдрома s = H r ^t. Тогда s(x) -- остаток от деления r(x) на g(x).

Док-во: Пусть r(x) = a₀ + a₁ x +... + a_n-1 x^n-1. Заметим, что столбцы i, 0 <= i <= n-k-1, матрицы H соответствуют xⁱ a столбцы j, n-k <= j <= n-1, соответствуют r_j-n+k(x), так что

где h(x) = a_n-k q₀(x) +... + a_n-1 q_k-1(x). Таким образом r(x) = h(x)g(x) + s(x). Поскольку deg r_i(x) <= n-k-1, то deg s(x) <= n-k-1. В силу единственности промежуточного частного и остатка при делении многочленов, мы можем заключить, что s(x) это остаток при делении r(x) на g(x).

Таким образом синдром вектора можно получить делением многочленов. Более того, синдром вектора и его циклического сдвига тесно связаны. Предположим, что

r(x) = q(x)g(x) + s(x),

где deg(s(x)) самое большее n-k-1. По вышеприведенной теореме s(x) синдром r(x). Теперь

xr(x) = xq(x)g(x) + xs(x).

Если степень xs(x) не более n-k-1, то снова это синдром xr(x). В противном случае, синдром xr(x) остаток от деления xs(x) на g(x). В этом случае, положим

Пусть ПМ

Тогда

где deg (xs'(x) - s_n-k-1 g'(x)) <= n - k - 1. Теперь в силу единственности остатка и предыдущей теоремы, мы видим, что синдром xs(x) есть xs(x) - s_n-k-1 g(x). Приходим к выводу:

Tеорема: Пусть C циклический (n,k)-код над F с ПМ g(x), и пусть r(x) имеет синдромный многочлен s(x) = s₀ + s₁ x +... + s_m x^m. Тогда синдромный многочлен xr(x) есть

1. xs(x) если deg s(x) < n-k-1, и

2. xs(x) - s_n-k-1 g(x), если deg s(x) = n-k-1.

Пример: Рассмотрим код предыдущего примера с ПМ g(x) = 1 + x + x³. Используя записанную там порождающую матрицу, мы можем получить проверочную матрицу,

1 0 0 1 0 1 1

H = [I₃ -R^t] = 0 1 0 1 1 1 0.

0 0 1 0 1 1 1

Получили вектор r = (1011011). Синдром r равен H r ^t = (001)^t = s. Многочлен

r(x) = 1 + x² + x³ + x⁵ + x⁶.

Если разделить r(x) на g(x), то получим

r(x) = (x³ + x² + x + 1)g(x) + x².

Остаток, как и следовало ожидать, равен s.

А теперь найдем остаток циклического сдвига r. Положим w = (1101101), что соответствует многочлену xr(x). H w ^t = (110)^t. В полиномиальной интерпретации этот синдром получается так. Поскольку deg s(x) = 2 = n-k-1, синдром xr(x) есть

xs(x) - 1g(x) = x³ - (x³ + x + 1) = 1 + x.

Предыдущее расмотрение дает нам интересный метод декодирования некоторых видов ошибок в циклических кодах. Эту технику иногда называют охотой(капканы) на ошибки (error trapping).

Предположим, что C это (n,k)-код с минимальным расстоянием d = 2t + 1, и проверочной матрицей H = [I_n-k A]. Пусть c кодовое слово и e вектор ошибки веса не более t. Если получено r = c + e, то синдром r равен

s = H r ^t = H (c + e)^t = H e ^t.

Пусть e* = (s ^t, 0), где 0 это k-вектор из 0'ей. Тогда H e* ^t = s, т.е. e* и e имеют один и тот же синдром, значит в одном смежном классе C. Теперь пусть wt(s) <= t. Тогда wt(e*)<= t и значит e = e*, поскольку смежный класс содержит не более одного вектора веса меньше или равного t.

Следовательно, в этом случае ошибка известна и равна e = (s ^t,0).

Алгоритм декодирования

1. Вычислим синдром s₀(x) of r(x) по алгоритму деления.

2. Положим i = 0.

3. Если wt(s_i(x)) <= t, тогда установим e(x) = x^n-i(s_i, 0), и декодируем to r(x) - e(x).

4. Положим i = i + 1.

5. Если i = n then stop; ошибка не исправляется.

6. Если deg s_i-1(x) < n-k-1, тогда set s_i(x) = xs_i-1(x); иначе s_i(x) = xs_i-1(x) - g(x).

7. Go to (3).

Пример: g(x) = 1 + x² + x³ генерирует бинарный (7,4)-циклический код с минимальным расстоянием 3 (и следовательно 1-ошибку исправляет). Рассмотрим кодовое слово 1 + x + x⁵ = (1 + x + x²) g(x), пусть после передачи многочлен r(x) = 1 + x + x⁵ + x⁶ был получен. Декодируем его. Разделим r(x) на g(x) для нахождения синдрома,

r(x) = (x³ + 1)g(x) + (x + x²),

так s(x) = x + x².Так как вес s(x) > 1 (= t), вычислим синдром s₁(x) xr(x). Так как of s(x) = 2 = n - k - 1, умножаем s(x) на x и делим на g(x), что дает s₁(x) = 1. Поскольку вес 1, мы получили маску ошибки

e(x) = x^7-1(s₁, 0) = x⁶(1000000) = x⁶.

Так как n = 7 все ошибки веса 1 имеют циклический сдвиг на шесть 0's и 6 > k = 4, исправляются все единичные ошибки..

Пример: g(x) = 1 + x⁴ + x⁶ + x⁷ + x⁸ порождает бинарный (15,7)-циклический код. Если минимальное расстояние 5(так), то t = 2. Некоторые (по меньшей мере) веса 2 маски ошибок могут содержать сдвиги не менее 7 0й и могут бытьотловлены. Если мы получили

r = (1100 1110 1100 010)

считаем,

r(x) = (x + x² + x⁴ + x⁵)g(x) + (1 + x² + x⁵ + x⁷).

Вычисляем синдромы s_i(x) для xⁱ r(x) пока wt(s_i(x)) <= 2.

i s_i(x)

0 10100101

1 11011001

2 11100111

3 11111000

4 01111100

5 00111110

6 00011111

7 10000100

Итак, ошибка

e = x^15-7(s₇, 0) = x⁸(100001000000000) = (0000 0000 1000 010),

и мы исправляем r(x) на r - e = (1100 1110 0100 000).

Дата добавления: 2015-07-16