Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Полиномиальная арифметика | Пример 1 | Пример 4 | Пример 4 (прод.) |


Читайте также:
  1. Аффективные синдромы
  2. В которых часто допускают ошибки
  3. ВОЗМОЖНЫЕ ОШИБКИ В ПОПУЛЯРНОЙ ИНДУКЦИИ
  4. Все мы совершаем ошибки
  5. Вторая фаза. СРАЖЕНИЕ НА ИЗМАТЫВАНИЕ • НЕКОТОРЫЕ ВЫВОДЫ • ПОВТОРЯЮТСЯ УЖЕ ИЗВЕСТНЫЕ ОШИБКИ
  6. ВЫБОРКИ ОШИБКИ

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

xn-k+i = qi(x)g(x) + ri(x)

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

xn-k+i - ri(x) = qi(x)g(x) in C

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

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

x3 = (1)(x3 + x + 1) + (1+ x)
x4 = (x)(x3 + x + 1) + (x + x2)
x5 = (x2 + 1)(x3 + x + 1) + (1 + x + x2)
x6 = (x3 + x + 1)(x3 + x + 1) + (1 + x2).

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

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 I4] где R = 1 1 1

1 0 1 0 0 0 1 1 0 1.

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

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

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

Док-во: Пусть r(x) = a0 + a1 x +... + an-1 xn-1. Заметим, что столбцы i, 0 <= i <= n-k-1, матрицы H соответствуют xi a столбцы j, n-k <= j <= n-1, соответствуют rj-n+k(x), так что

где h(x) = an-k q0(x) +... + an-1 qk-1(x). Таким образом r(x) = h(x)g(x) + s(x). Поскольку deg ri(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) - sn-k-1 g'(x)) <= n - k - 1. Теперь в силу единственности остатка и предыдущей теоремы, мы видим, что синдром xs(x) есть xs(x) - sn-k-1 g(x). Приходим к выводу:

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

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

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

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

1 0 0 1 0 1 1

H = [I3 -Rt] = 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 + x2 + x3 + x5 + x6.

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

r(x) = (x3 + x2 + x + 1)g(x) + x2.

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

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

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

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

Предположим, что C это (n,k)-код с минимальным расстоянием d = 2t + 1, и проверочной матрицей H = [In-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. Вычислим синдром s0(x) of r(x) по алгоритму деления.

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

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

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

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

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

7. Go to (3).

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

r(x) = (x3 + 1)g(x) + (x + x2),

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

e(x) = x7-1(s1, 0) = x6(1000000) = x6.

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

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

r = (1100 1110 1100 010)

считаем,

r(x) = (x + x2 + x4 + x5)g(x) + (1 + x2 + x5 + x7).

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

 

i si(x)

 

0 10100101

1 11011001

2 11100111

3 11111000

4 01111100

5 00111110

6 00011111

7 10000100

Итак, ошибка

e = x15-7(s7, 0) = x8(100001000000000) = (0000 0000 1000 010),

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

 


Дата добавления: 2015-07-16; просмотров: 94 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
IV. Размерность, порождающая и проверочная матрицы| НАЗНАЧЕНИЕ РУКОВОДСТВА

mybiblioteka.su - 2015-2024 год. (0.01 сек.)