Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v1.0 (1127210), страница 2
Текст из файла (страница 2)
Полином g(x) является делителем полинома xn + 1.Такой полином g(x) называется порождающим полиномом циклического кода. Любой полином,являющийся делителем xn + 1, является порождающим для некоторого циклического кода.Несистематическое кодирование u(x) для циклического кода, заданного своим порождающимполиномом g(x), может быть осуществлено как v(x) = g(x)u(x).
Процесс систематического кодирования может быть реализован какv(x) = xm u(x) + mod(xm u(x), g(x)),где m – степень g(x). Здесь биты входного сообщения u(x) воспроизводятся в крайних правых битахкодового слова v(x).Назовём синдромом принятого полинома w(x) полином s(x) = mod(w(x), g(x)) = mod(v(x) +e(x), g(x)) = mod(e(x), g(x)). Как и раньше для случая линейных кодов синдром является нулевым многочленом тогда и только тогда, когда w(x) является кодовым словом.
Таким образом, дляциклических кодов синдром вычисляется без необходимости конструирования проверочной матрицы H. Общий алгоритм декодирования циклического кода принципиально не отличается от общего алгоритма декодирования линейного кода. В нём рассматривается общее решение системыe(x) = s(x) + g(x)u(x) для всех возможных полиномов u(x) степени k − 1, а искомый полиномошибок определяется как решение с минимальным числом ненулевых слагаемых.Пример 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 , если он является полиномом минимальной степени, для которого α является корнем.
В частности, минимальныйполином для примитивного элемента α называется примитивным полиномом. Можно показать, чтоqкорнями минимального полинома mα (x) являются {α, α2 , α4 , . . . , α2 }. Данный набор элементов изlполя F2 называется классом смежности для элемента α. Смежные классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полиномqYi(x + α2 ) = xq + λq−1 xq−1 + · · · + λ1 x + λ0i=1имеет коэффициенты из F2 и является минимальным полиномом для α, а также для всех элементов поля, входящих вместе с α в один смежный класс. Отсюда выводится метод построенияминимального полинома для заданного элемента поля α:1.
Построить смежный класс, порождённый элементом α;i2. Найти коэффициенты полинома mα (x) путем перемножения многочленов x + α2 для всехi = 1, . . . , q.Пусть 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. Полином x3 + 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 . Эти элементы входят вдва смежных класса (α, α2 , α4 ) и (α3 , α6 , α5 ).
Поэтому g(x) = mα (x)mα3 (x). Найдем минимальныймногочлен mα3 (x) по его корнямmα3 (x) = (x + α3 )(x + α6 )(x + α5 ) = x3 + (α3 + α6 + α5 )x2 + (α9 + α8 + α11 )x + α14 .Все коэффициенты многочлена mα3 (x) принадлежат F2 . Вычислим эти коэффициенты, используясвойства α7 = 1 (т.к. α является примитивным элементом) и α3 = α + 1 (т.к.
α является корнемx3 + x + 1):α3 + α6 + α5 = α + 1 + (α + 1)2 + α2 (α + 1) = α + 1 + α2 + 1 + α3 + α2 = 1,α9 + α8 + α11 = α2 + α + α4 = α2 + α + α(α + 1) = 0,α14 = 1.Таким образом, mα3 (x) = x3 + x2 + 1, g(x) = mα (x)mα3 (x) = (x3 + x + 1)(x3 + x2 + 1) = x6 + x5 +x4 + x3 + x2 + x + 1.Заметим, что многочлен g(x) имеет корни α, α2 , α3 , α4 , α5 , α6 . Следовательно, построен код БЧХ(7, 1, 7), который исправляет не менее, чем t = 3 ошибки. Нетрудно видеть, что данный код содержитвсего два кодовых слова v 1 = [0000000], v 2 = [1111111].Декодирование кода Хэмминга.
Код Хэмминга является частным случаем кода БЧХ дляt = 1. Поэтому нулями кода Хэмминга являются α и α2 , где α – примитивный элемент поля Fl2 .Для декодирования принятого слова w(x) вычислим синдром s1 = w(α). Синдром s2 автоматическиопределяется по s1 как s2 = w(α2 ) = (w(α))2 = s21 . Если s1 = 0, то w(x) уже является кодовымсловом и v̂(x) = w(x). Предположим, что при передаче по каналу была совершена одна ошибка.Тогда w(x) = v(x) + e(x), где полином ошибок e(x) = xj для некоторого j.
Для нахождения позицииошибки вычислим значения полинома ошибок в точке α для всех j = 1, . . . , n. Если e(α) = αj = s1 ,то j – искомая позиция ошибки и v̂(x) = w(x)+xj . Если αj 6= s1 ∀j, то при передаче было совершеноболее одной ошибки, и процедура декодирования выдает отказ.Пример 5. Рассмотрим код Хэмминга из примера 4. Он имеет порождающий полином g(x) =x3 + x + 1, а все вычисления проводятся в поле F32 = F2 [x]/(x3 + x + 1)1 . Пусть входной полиномu(x) = x3 + x2 . Его систематическое кодирование было найдено в примере 3: v(x) = x6 + x5 + x.Пусть при передаче произошла ошибка в позиции 5, т.е. w(x) = x6 + x, а истинный e(x) = x5 . Длядекодирования сначала найдем синдром s1 = w(α) = α6 + α = (α3 )2 + α = (α + 1)2 + α = α2 + α + 1.1 Совпадение в данном случае порождающего полинома и полинома, по которому строится поле, является случайностью.Теперь вычислим αj для всех j = 0, .
. . , 6:α0 = 1,α1 = α,α2 = α2 ,α3 = α + 1,α4 = α(α + 1) = α2 + α,α5 = α2 (α + 1) = α3 + α2 = α2 + α + 1,α6 = (α + 1)2 = α2 + 1.Отсюда находим, что α5 = s1 , т.е. ошибка произошла в позиции 5. Таким образом, v̂(x) = w(x)+x5 =x6 + x5 + 1.Декодирование БЧХ кода. Пусть при передаче по каналу произошло ν ошибок, т.е.
e(x) =xj1 + xj2 + · · · + xjν , где j1 , . . . , jν – позиции ошибок. Рассмотрим полином локаторов ошибокσ(x) =νY(1 + αji x) = 1 + σ1 x + σ2 x2 + · · · + σν xν .i=1Корнями данного полинома являются α−ji . Рассмотрим также синдромный полиномs(x) = 1 + s1 x + s2 x2 + · · · + s2t x2t ,где si = w(αi ), i = 1, .
. . , 2t – значения принятого полинома в нулях БЧХ кода. Можно показать,что полином локаторов ошибок может быть найден путем решения уравненияs(x)σ(x) + x2t+1 a(x) = Λ(x)(2)для некоторого многочлена Λ(x), степень которого не превосходит t. Данное уравнение может бытьрешено с помощью расширенного алгоритма Евклида для пары многочленов x2t+1 и s(x). Количество фактически совершенных ошибок ν определяется степенью найденного σ(x). В результатеобщая схема декодирования БЧХ кода выглядит следующим образом:1. Для принятого слова w(x) найти все синдромы si = w(αi ) ∀i = 1, . . . , 2t;2.
Найти полином локаторов ошибок σ(x) путем решения уравнения (2) с помощью расширенногоалгоритма Евклида;3. Найти все корни σ(x) полным перебором; пусть найденные корни равны αk1 , . . . , αkν ;4. Найти позиции ошибок ji = −ki mod n, где n = 2l − 1 – порядок примитивного элемента α;5. Исправить ошибки v̂(x) = w(x) + xj1 + · · · + xjν ;6. Найти все синдромы v̂(x); если они не равны нулю, то выдать отказ от декодирования.Пример 6. Рассмотрим (15,5,7) БЧХ код, исправляющий три ошибки.
Он имеет порождающийполином g(x) = x10 +x8 +x5 +x4 +x2 +x+1, а все вычисления проводятся в поле F42 = F2 [x]/(x4 +x+1).Пусть входной полином имеет вид u(x) = x4 + x2 + x. При систематическом кодировании емусоответствует кодовый полином v(x) = x14 + x12 + x11 + x8 + x4 + x3 + x2 + x. Пусть полином ошибокравен e(x) = x12 +x6 +1. Следовательно, принятое слово w(x) = x14 +x11 +x8 +x6 +x4 +x3 +x2 +x+1.Для удобства последующих вычислений построим для всех элементов поля F42 таблицу соответствий между степенным представлением и полиномиальным (см. таблицу 1).С использованием таблицы 1 найдём синдромы для принятого слова:s1 = w(α) = α3 + 1 + α3 + α2 + α + α2 + 1 + α3 + α2 + α + 1 + α3 + α2 + α + 1 = α,s2 = w(α2 ) = (w(α))2 = α2 ,s3 = w(α3 ) = α42 + α33 + α24 + α18 + α12 + α9 + α6 + α3 + 1 = α12 + α3 + α9 + α3 + α12 + α9 + α6 + α3 + 1 == α6 + α3 + 1 = α3 + α2 + α3 + 1 = α2 + 1 = α8 ,s4 = w(α4 ) = (w(α2 ))2 = α4 ,s5 = w(α5 ) = α70 + α55 + α40 + α30 + α20 + α15 + α10 + α5 + 1 = α10 + α10 + α10 + 1 + α5 + 1 + α10 + α5 + 1 = 1,s6 = w(α6 ) = (w(α3 ))2 = (α2 + 1)2 = α4 + 1 = α.Таблица 1: Таблица вычислений для поля F42 = F2 [x]/(x4 + x + 1).αα2α3α4α5α6α7α8α9α10α11α12α13α14α15αα2α3α+1α2 + αα3 + α2α3 + α + 1α2 + 1α3 + αα2 + α + 1α3 + α2 + αα3 + α2 + α + 1α3 + α2 + 1α3 + 11Таким образом, синдромный полином s(x) = αx6 + x5 + α4 x4 + α8 x3 + α2 x2 + αx + 1.Теперь решим уравнение x7 a(x) + s(x)σ(x) = Λ(x) расширенным алгоритмом Евклида.Шаг 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
