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

Тип работы:
Доклад
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

Метод является частным случаем перестановочного декодирования. Предположим, что требуется исправить все векторы ошибок e = (e0, …, ev — 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 = (e0, …, er — 1). Следовательно, принимаемый вектор декодируется как слово

.

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

Алгоритм.

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

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

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

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

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

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

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

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

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

Алгоритм I.

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

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

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

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

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

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

Перейти к шагу 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)) 2.

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

i

Si (x)

0

10 100 101

1

11 011 001

2

11 100 111

3

11 111 000

4

1 111 100

5

111 111

6

11 111

7

10 000 100

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

E = x15−7 (s7,0) = x8 (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 — циклический код длиной 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) 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) 2t. Предполагается, что структура вектора пачки ошибок длиной t имеет отрезок из (n-t) нулевых элементов. Если вектор E представляет собой пачку ошибок длиной t и ошибки располагаются на первых (n-k) позициях вектора, тогда синдром H (ET) = s характеризует структуру (нециклической) пачки ошибок длины не более t. Если ошибки располагаются не первых (n-k) позициях вектора, то для вычисления синдрома используется его свойство (см. алгоритм I).

Алгоритм II.

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

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

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

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

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

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

Переход к шагу 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. Вычисляем значения синдрома для других циклических сдвигов принимаемого сигнала:

i

si (x)

0

110 011

1

100 101

2

101 110

3

10 111

4

110 111

5

100 111

6

101 111

7

101 011

8

101 001

9

101 000 — пачка ошибок t = 3

Вектор ошибок вычисляется как E (x) = xn-i (s9, 0) = x6 (101 000 0) = (0 101 000 000) mod (x15-1).

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

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

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

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

g (x)

(n, k)

Длина исправляемой пачки ошибок t

1+x2+x3+x4

(7,3)

2

1+x2+x4+x5

(15,10)

2

1+x4+x5+x6

(31,25)

1+x3+x4+x5+x6

(15,9)

3

1+x+x2+x3+x6

(15,9)

3

ПоказатьСвернуть
Заполнить форму текущей работой