Метод вылавливания ошибок
Доклад - Компьютеры, программирование
Другие доклады по предмету Компьютеры, программирование
Метод вылавливания ошибок
Метод является частным случаем перестановочного декодирования. Предположим, что требуется исправить все векторы ошибок e = (e0, …, ev - 1) вес которых не превосходит t при некотором фиксированном t [ (d - 1) /2]. Для выполнения декодирования надо найти такое множество подстановок, чтобы код был инвариантен относительно этого множества и чтобы для каждого вектора e, вес которого не превосходит t, нашлась бы подстановка, передвигающая все ошибки из информационных позиций в проверочные.
Метод перестановочного декодирования состоит в следующем. Определим оператор подстановок pj По полученному вектору y вычисляются векторы сдвигов pj {y} и их синдромы s (j), до тех пор, пока не будет найден индекс j, для которого вес wt (s (j)) t. При этом все ошибки будут сосредоточены в первых r = n - k позициях вектора pj {y} и задаются равенством [s (j)] T = (e0, …, er - 1). Следовательно, принимаемый вектор декодируется как слово
.
Метод вылавливания ошибок использует циклические постановки Dj. Метод позволяет исправлять все векторы ошибок, содержащие круговую серию нулей длины не менее k.
Алгоритм.
1. Вычисляется синдром s (x) для принимаемого сигнала y (x), используя алгоритм деления на порождающий полином.
. Установка j: = 0
. Если wt (sj (x)) t, тогда полагаем e (x) = x j (sj, 0) и корректируем ошибку, вычисляя y (x) - e (x);
. Устанавливаем j: = j + 1;
. Если j = n, тогда алгоритм останавливается и ошибка считается не выловленной;
. Если deg (sj - 1 (x) < n - k - 1, тогда sj (x) = x sj - 1 (x); в противном случае - sj (x) = x sj - 1 (x) - g (x);
. Перейти к шагу 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.
Вычисления сведем в таблицу
iSi (x) 010100101111011001211100111311111000401111100500111111600011111710000100
Ошибка представляется как
E = x15-7 (s7,0) = x8 (10000100 0000000) = (0000 0000 1000 010),
Декодируем кодовое слово как
c = y - E = (1100 1110 0100 000).
Пакеты ошибок
Характерной особенностью циклических кодов является способность к распознаванию пакетов ошибок. Под пакетом ошибок понимается группирование ошибок в одной ограни