Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v2.0 (1127212), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Сложность построения такой таблицы равна Õ(2n )6 , т.к. для каждого из 2m синдромов необходимоперебирать 2k решений очередной СЛАУ. В результате процедура декодирования произвольного линейного кодатребует экспоненциальных затрат как по памяти, так и по сложности алгоритма декодирования.Пример 2. Рассмотрим линейный код из примера 1. Пусть исходный вектор u = [0 1 1]T . Систематическоекодирование для него было получено раньше: v = [1 1 0 0 1 0]T . Пусть при передаче происходит ошибка вовтором бите, т.е. принятый вектор w = [1 0 0 0 1 0]T . Для декодирования w найдём его синдром 1 0  11 1 1 0 0 0 0 = 0 .s = Hw = 1 0 0 1 1 0 001 0 1 0 1 1 10Далее необходимо найти все решения системы He = s. Частное решение этой системы легко найти с учётомтого, что в столбцах 2, 4, 6 проверочной матрицы H стоит единичная подматрица.

Пусть ê1 = ê3 = ê5 = 0. Тогдаê2 = s1 , ê4 = s2 , ê6 = s3 , т.е. ê = [0 1 0 0 0 0]T . Решение однородной системы уже было найдено раньше на этапевычисления кодового расстояния d:0 1 0 1 0 1 0 10 1 0 1 1 0 1 00 0 0 0 1 1 1 1.G[u1 , u2 , . . . , u8 ] = 0 1 1 0 1 0 0 10 0 1 1 1 1 0 00 1 1 0 0 1 1 0Таким образом, все 8 решений системы He = s могут быть записаны как0 1 0 1 0 1 0 11 0 1 0 0 1 0 10 0 0 0 1 1 1 10 1 1 0 1 0 0 1 .0 0 1 1 1 1 0 00 1 1 0 0 1 1 0Выбирая среди них решение с наименьшим весом, находим e = [0 1 0 0 0 0]T , т.е. v̂ = w + e = [1 1 0 0 1 0]T .Циклические кодыРанее в курсе были рассмотрены т.н.

циклические подпространства Fnp , рассматриваемого как линейное пространство размерности n с элементами векторов из Fp . Напомним, что подпространство I называется циклическим, если вместе с любым вектором v = {v0 , v1 , . . . , vn−1 } ∈ I оно содержит и его циклический сдвиг6 СимволомÕ(x) обозначена сложность с точностью до логарифмических факторов, т.е. O(x logγ x).{v1 , . . . , vn−1 , v0 }. При дополнительном требовании линейности циклического подпространства I можно показать, что I является главным идеалом в фактор-кольце Fp [x]/(xn − 1), порождённым некоторым делителем g(x)многочлена xn − 1.

Переведём этот алгебраический результат на язык кодов с учётом p = 2.Назовём линейный блоковый (n, k)-код циклическим, если в нём любой циклический сдвиг кодового словаявляется кодовым словом. Поставим в соответствие произвольному вектору v = {v0 , v1 , . . . , vn−2 , vn−1 } ∈ {0, 1}nполином вида v(x) = v0 + v1 x + · · · + vn−2 xn−2 + vn−1 xn−1 . Тогда рассмотренное выше свойство главного идеала для циклического кода можно переформулировать следующим образом: для (n, k)-линейного циклическогоблокового кода найдется полином g(x) степени m = n − k такой, что1.

Все кодовые слова v(x) могут быть представлены как g(x)q(x), где q(x) – некоторый полином степени невыше, чем k − 1;2. Полином g(x) является делителем полинома xn + 1.Такой полином g(x) называется порождающим полиномом циклического кода. Любой полином, являющийсяделителем xn + 1, является порождающим для некоторого циклического кода длины n.Кодирование.

С учётом того, что для циклического кода любой кодовый полином v(x) делится на порождающий полином g(x), процедура кодирования может быть организована как v(x) = g(x)u(x), где u(x) – входящийполином степени не выше k − 1. Такое кодирование будет несистематическим. Оно соответствует рассмотрениюпорождающей матрицы кода G = [g 0 |g 1 | . .

. |g k−1 ], где базисные вектора g i определяются полиномами g(x)xi ,i = 0, . . . , k − 1.Для организации систематического кодирования полинома u(x) рассмотрим полином xm u(x), где m – числопроверочных бит кода и степень g(x). Поделим xm u(x) на g(x) с остатком:xm u(x) = g(x)q(x) + r(x),где deg r(x) < m. Тогдаxm u(x) + r(x) = g(x)q(x) ∈ C.Заметим, что deg xm u(x) ≥ m.

Таким образом, в векторном представлении полином xm u(x) + r(x) имеет вкрайних правых позициях элементы u(x). В результате процесс систематического кодирования u(x) может бытьреализован какv(x) = xm u(x) + mod(xm u(x), g(x)).Такая схема кодирования соответствует выбору порождающей матрицы кода с базисными векторами g i , определяемыми полиномами xm+i + mod(xm+i , g(x)).По аналогии с понятием проверочной матрицы для циклического кода можно ввести понятие проверочногополинома. Полином h(x) степени k называется проверочным, если выполнено свойствоg(x)h(x) = xn + 1.Соответственно, проверочный полином может быть найден по порождающему g(x) простым делением многочлена xn + 1 на g(x). Пусть v(x) – произвольный кодовый полином, т.е. он представим в виде v(x) = g(x)q(x).Тогдаv(x)h(x) = q(x) g(x)h(x) = 0.| {z }0Пусть проверочный полином имеет вид h(x) =какh0 h1 h2 .

. . 0h0 h1 . . .H=. . . . . . . . . . . .0 ... ...0Pkhi xi . Тогда нетрудно построить проверочную матрицу кодаhk0 ...00hk−1 hk0...0 ∈ {0, 1}m×n ....... ....... . .h0h1 . . . hk−1 hki=0Такой выбор проверочной матрицы соответствует рассмотрению базисных векторов hj , определяемых полиномами h(x)xj , j = 0, . . . , m − 1.Декодирование.

Назовём синдромом принятого полинома w(x) полином s(x) = mod(w(x), g(x)) =mod(v(x) + e(x), g(x)) = mod(e(x), g(x))7 . Как и раньше для случая линейных кодов синдром является нулевым многочленом тогда и только тогда, когда w(x) является кодовым словом. Общий алгоритм декодирования7 Очевидно,что синдром можно определить и с помощью проверочного полинома как s(x) = mod(w(x)h(x), xn + 1).циклического кода принципиально не отличается от общего алгоритма декодирования линейного кода.

В нёмрассматривается общее решение системы e(x) = s(x) + g(x)u(x) для всех возможных полиномов u(x) степениk − 1, а искомый полином ошибок определяется как решение с минимальным числом ненулевых слагаемых.Таким образом, для задания циклического кода достаточно определить порождающий или проверочныйполином. По сравнению с линейными кодами в циклических кодах операции умножения матриц на вектора ирешение СЛАУ заменяются на более простые операции умножения полиномов и деление полиномов с остатком.Однако, общий алгоритм декодирования по-прежнему имеет экспоненциальную сложность по k.Пример 3.

Пусть длина циклического кода n = 7. Для построения циклического кода необходимо сначаланайти разложение полинома x7 + 1 на неприводимые множители. Так как 7 = 23 − 1, то все ненулевые элементыполя F32 являются корнями x7 +1. Известно, что каждый многочлен над F2 содержит в расширении поля F32 вме23сте с любым своим корнем β также смежные корни вида β 2 , β 2 , β 2 , . . . . Пусть α – произвольный примитивныйэлемент поля F32 .

Тогда с учетом α7 = 1 легко найти разбиение всех элементов поля на смежные классы:(α, α2 , α4 ); (α3 , α6 , α5 ); α7 .Таким образом, многочлен x7 + 1 имеет один неприводимый делитель степени 1, а также два неприводимыхделителя степени 3. В результате получаем разложениеx7 + 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).В качестве g(x) может выступать произвольный делитель x7 + 1.

Выберем в качестве g(x) многочлен x3 + x + 1.В результате получаем циклический (7, 4)-код.Пусть входной полином u(x) равен x3 + x2 . Его несистематическое кодирование находим какv(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2 .В бинарном представлении это соответствуетu = [0011], v = [0010111].Для осуществления систематического кодирования необходимо найти остаток от деления многочлена x3 u(x)на g(x).

В результате находимv(x) = x3 u(x) + mod(x3 u(x), g(x)) = x6 + x5 + mod(x6 + x5 , x3 + x + 1) = x6 + x5 + x.В бинарном представлении этот соответствуетu = [0011], v = [0100011].Таким образом, действительно биты входного сообщения u воспроизводятся в крайних правых битах кодовогослова v.Коды БЧХПолином mα (x) ∈ F2 [x] называется минимальным полиномом для элемента α ∈ Fl2 , если он является полиномомминимальной степени, для которого α является корнем.

В частности, минимальный полином для примитивногоэлемента α называется примитивным полиномом. Можно показать, что корнями минимального полинома mα (x)qявляются {α, α2 , α4 , . . . , α2 }. Данный набор элементов из поля Fl2 называется классом смежности для элементаα. Смежные классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можнопоказать, что полиномqYi(x + α2 ) = xq + λq−1 xq−1 + · · · + λ1 x + λ0i=1имеет коэффициенты из F2 и является минимальным полиномом для α, а также для всех элементов поля,входящих вместе с α в один смежный класс. Отсюда выводится метод построения минимального полинома длязаданного элемента поля α:1. Построить смежный класс, порождённый элементом α;i2.

Найти коэффициенты полинома mα (x) путем перемножения многочленов x + α2 для всех i = 1, . . . , q.В примере 3 для циклического кода был рассмотрен случай, когда длина кода n представима в виде 2l − 1. Вэтом случае корнями многочлена xn + 1 являются все ненулевые элементы поля Fl2 , а порождающими многочленами циклического кода могут быть только минимальные многочлены для некоторой совокупности элементовFl2 . Коды БЧХ являются подмножеством циклических кодов, которые существенно используют указанную связьмежду порождающим полиномом и элементами из Fl2 .

Прямым следствием такого подхода является то, что длины кодов БЧХ перестают быть произвольными8 .Итак, пусть n = 2l − 1, d = 2t + 1 ≤ n. Тогда кодом БЧХ называется (n, k, d)-линейный циклический код, вкотором порождающий многочлен g(x) определяется как минимальный многочлен для элементов α, α2 , . . . , αd−1из поля Fl2 , где α – произвольный примитивный элемент поля Fl2 , т.е.g(x) = НОК(mα (x), mα2 (x), . . . , mαd−1 (x)).Набор элементов α, α2 , . .

. , αd−1 называется нулями БЧХ-кода. Можно показать, что минимальное кодовое расстояние кода БЧХ не меньше, чем величина d. В результате БЧХ-коды по построению способны исправлять неменее t ошибок, где t = [(d − 1)/2].С учетом того, что все кодовые слова циклического кода делятся на g(x), а g(x) является минимальнымполиномом для выбранных нулей кода, тоv(x) ∈ C ⇔ v(αi ) = 0 ∀i = 1, . . . , 2t.Назовём синдромами принятого сообщения w(x) значения w(x) в нулях кода: si = w(αi ), i = 1, . . . , 2t. Всесиндромы равны нулю тогда и только тогда, когда w(x) является кодовым словом.Пример 4.

Рассмотрим БЧХ-коды для случая поля F32 = F2 [x]/(x3 + x + 1). Здесь l = 3, n = 7. Полином3x + x + 1 является примитивным полиномом над F2 . Обозначим через α ∈ F32 его произвольный корень.Построим код БЧХ, исправляющий не менее, чем t = 1 ошибку. Его порождающий полином g(x) строится какминимальный многочлен для элементов α, α2 . Эти элементы входят в один смежный класс (α, α2 , α4 ). Поэтомуg(x) = mα (x) = mα2 (x) = x3 + x + 1. В результате получаем (7, 4, 3)-код, являющийся кодом Хэмминга.Построим код БЧХ, исправляющий не менее, чем t = 2 ошибок. Его порождающий полином g(x) строитсякак минимальный многочлен для элементов α, α2 , α3 , α4 .

Характеристики

Список файлов учебной работы