3. Низкоскоростные корреляционные коды: методы и схемы кодирования.

4. Низкоскоростные коды: методы и схемы корреляционного декодирования.

5.Коды бчх: схемы кодирования и алгоритмы декодирования.

Декодирование БЧХ-кода

6.Коды Рида-Соломона: схемы кодирования и алгоритмы декодирования.

Коды Рида - Соломона являются важным подмножеством кодов Боуза-Чоудхури-Хоквингема (БЧХ), у которых мультипликативный порядок алфавита символов кодового слова делится на длину кода. Особенности:

- коды РС являются максимальными, т.е. при заданной длине n и размерности k имеют наибольшее кодовое расстояние d= (n - k +1);

- любой набор из k позиций кодового слова является информационным, т.е. позволяет восстановить все кодовое слово;

- число кодовых слов веса ω равно

где - число сочетаний из n по ω, q - основание кода;

- коды могут быть эффективно декодированы во временной и частотной областях.

Код РС над полем Галуа GF(q) можно определить как код, состоящий из всех слов с=(с₀, с₁,…, с_n-1) длины n, для которых выполняются (d-1) уравнений:

(1)

где r₀ и d – произвольные целые числа (не больше n); ϒ₀, ϒ ₁, …, ϒ _n-1 – различные ненулевые элементы конечного поля, которые называют локатором i-й позиции кодового слова. Число различных элементов ϒ _i определяет максимальную длину кода РС, которая не превышает (q –1). Если длина кода равна (n < q–1), то код называется укороченным, если длина кода равна n = q (или q + 1), то код является расширенным на один (или два) символа.

Циклический РС-код длиной n, равной любому делителю (q – 1), задается выражением (1) и последовательностью локаторов положений вида ϒi = aⁱ, где a - элемент порядка n в поле GF(q), a = .

Проверочная матрица циклического РС-кода имеет вид

Определение синдрома. Предположим, что на вход декодера поступает последовательность символов (y0, y1,…, y_n-1), где yi = ci + ei, {ei} – элементы вектора ошибок, ei GF(q). Синдромом кода называется вектор s =(s0, s1, …, s_d-2), элементы которого определяются из выражения

Если все элементы синдрома равны нулю, то принятое слово считается кодовым. В противном случае принятое слово y содержит ошибки. Синдром зависит только от ошибок в принятом слове.

Алгебраический алгоритм декодирования кода РС.

Исходные данные: принятое слово y =(y0, y1, …, y_n-1); параметры кода – n, k, d, m = d – 1, r0, локаторы кода - ϒ0, ϒ1,….

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

2. Решение ключевого уравнения s(x): σ(x) = ω(x) mod m^x. Если степень deg(σ(x)) ≥m/2, то отказ и переход к 5.

3. Определение множества локаторов ошибок Z: z Z, если σ( z^-1) = 0. Если же не все корни являются локаторами позиций, то отказ и переход к 5.

4. Вычисление значений ошибок и исправление искаженных позиций , если

5. Восстановление информационных символов или выдача признака отказа от декодирования.

Кодирование и декодирование кода РС в частотной области. Кодирование в частотной области РС-кодами над полем GF(q =2^m) состоит в следующем (рис. 3). Информационное сообщение a из k=(n – m = q – 1) символов представляется в виде старших коэффициентов спектра F_G Фурье-Галуа (ФГ), а остальные m символов этого спектра полагаются равными нулю. Кодовое слово c в несистематическом виде получается с помощью обратного n-точечного преобразования ФГ спектра F_G.

Рис.3. а) кодирование, б) декодирование

Алгоритм декодирования в спектральной области

Основные этапы спектрального декодирования:

1) дискретное преобразование Фурье-Галуа (ДПФГ);

2) нахождение полинома локаторов;

3) рекуррентное продолжение синдрома;

4) коррекция и извлечение сообщения.

На первом этапе принятое слово y=с+e подвергается n-точечному ДПФГ. Полученный вектор Y=(Y0, Y1, …, Yn-1) соответствует спектру для суммы кодового слова и ошибки (с + e)Wn= C + E, где Wn– матрица ДПФГ. Так как m составляющих вектора V являются нулевыми, то соответствующие им m компонент вектора s =(s0=Xk, s1=Xk+1, …, s_m-1= Xn-1) характеризуют конфигурацию ошибок e. Другими словами, эти m компонент аналогичны синдрому во временной области, причем, если все они равны нулю, то считается, что в принятом слове нет ошибок. Второй этап проще по сравнению с временным декодированием, так как отпадает необходимость в полном решении ключевого уравнения, а достаточно найти лишь полином локаторов s(x). Третий этап сводится к вычислению спектра E={Ei} ошибок. Для этого осуществляется рекуррентное продолжение синдрома по формуле

где yi- коэффициент при xi полинома локаторов ошибок s(x), j = 0, 1,…, (n - l), l - степень полинома s(x). При этом m старших коэффициентов спектра E совпадают с соответствующими компонентами синдрома, характеризующими ошибку e: E(n – 1)= sm-1, E(n – 2)= sm-2,…, E(k = n -m)= s0.

Коррекция на четвертом этапе состоит в сложении векторов Y и E, а также выделении сообщения из полученной после отбрасывания нулевого вектора 0 длины m из суммы.