Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v2.0 (1127212), страница 3
Текст из файла (страница 3)
Эти элементы входят в два смежных класса (α, α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(линейная сложность по 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). Пусть входной полином u(x) = x3 + x2 . Егосистематическое кодирование было найдено в примере 3: v(x) = x6 + x5 + x. Пусть при передаче произошла8 Простейшим способом обойти указанное ограничение на длину кода является рассмотрение т.н.
укороченных кодов БЧХ. Пустьn, k – необходимые параметры кода, n1 – некоторое число такое, что n1 ≥ n, n1 = 2l − 1, k1 = n1 − n + k. Тогда можно рассмотреть(n1 , k1 )-код БЧХ, в котором на вход подавать блоки длины k, дополненные нулями до длины k1 .ошибка в позиции 5, т.е. w(x) = x6 + x, а истинный e(x) = x5 . Для декодирования сначала найдем синдромs1 = w(α) = α6 + α = (α3 )2 + α = (α + 1)2 + α = α2 + α + 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ν – позиции ошибок. Запишем свойство si = w(αi ) = e(αi ), i = 1, . . . , 2t в виде системы:s1 = αj1 + αj2 + · · · + αjν ,s2 = (αj1 )2 + (αj2 )2 + · · · + (αjν )2 ,(3)................................s2t = (αj1 )2t + · · · + (αjν )2t .Любое решение данной системы j1 , . .
. , jν для некоторого ν ≤ t будет искомым (такое решение всегда существуети единственно, т.к. БЧХ код по построению способен исправлять до t ошибок).Введём обозначение βi = αji , i = 1, . . . , 2t. Тогда систему (3) можно записать какs1 = β1 + β2 + · · · + βν ,s2 = β12 + β22 + · · · + βν2 ,(4).........................s2t = β12t + β22t + · · · + βν2t .Рассмотрим полином локаторов ошибокσ(x) =νY(1 + βi x) = 1 + σ1 x + σ2 x2 + · · · + σν xν .i=1Корнями данного полинома являются βi−1 = α−ji .
Связь между коэффициентами полинома σk и элементами βiможно определить по теореме Виета:σ 1 = β1 + β2 + · · · + β ν ,σ2 = β1 β2 + β2 β3 + β1 β3 + · · · + βν−1 βν ,Xσ3 =βi1 βi2 βi3 ,(5)i1 <i2 <i3.........................σ ν = β 1 β 2 . . . βν .Система (4) определяет значения симметрического многочлена суммы k-ых степеней βi для всех k = 1, . . . , 2t.Система (5) определяет значения элементарного симметрического многочлена. Соотношения между этими двумя типами симметрических многочленов задаются тождествами Ньютона-Жирара, которые с учётом двоичнойарифметики могут быть записаны какs1 + σ1 = 0,s2 + σ1 s1 + 2σ2 = 0,s3 + σ1 s2 + σ2 s1 + 3σ3 = 0,................................sν + σ1 sν−1 + · · · + σν−1 s1 + νσν = 0,sν+1 + σ1 sν + · · · + σν−1 s2 + σν s1 = 0,sν+2 + σ1 sν+1 + · · · + σν−1 s3 + σν s2 = 0,.............................................s2t + σ1 s2t−1 + · · · + σν−1 s2t−ν+1 + σν s2t−νКлючевое уравнение= 0.В литературе по кодам последние 2t − ν + 1 уравнений данной системы получили название ключевого уравнения.
Ключевое уравнение является СЛАУ относительно σ1 , . . . , σν . Решение ключевого уравнения позволяетнайти полином локаторов ошибок σ(x). Далее все его корни могут быть найдены полным перебором (линейнаясложность по n), по которым в свою очередь могут быть найдены позиции ошибок ji .Основная трудность в решении ключевого уравнения состоит в том, что значение ν неизвестно.
ДекодерPGZ (Peterson-Gorenstein-Zierler) предполагает последовательное решение ключевого уравнения для всех ν =t, t − 1, . . . до тех пор, пока матрица очередной СЛАУ не окажется невырожденной (при переходе от t к t − 1кладём σt = 0).Рассмотрим альтернативный декодер на базе расширенного алгоритма Евклида9 . Для этого введём синдромный полином видаs(x) = 1 + s1 x + s2 x2 + · · · + s2t x2t ,где si = w(αi ), i = 1, .
. . , 2t – значения принятого полинома в нулях БЧХ кода. Домножим синдромный полиномна σ(x):λ(x) = s(x)σ(x) = 1 + λ1 x + λ2 x2 + · · · + λ2t+ν x2t+ν ,Pjгде коэффициенты многочлена определяются как λj =i=0 si σj−i . С учётом σ0 = 1 ключевое уравнениеэквивалентно условию λν+1 = λν+2 = · · · = λ2t = 0, т.е.λ(x) = 1 + λ1 x + λ2 x2 + · · · + λν xν + λ2t+1 x2t+1 + · · · + λ2t+ν x2t+ν .Далее рассмотрим остаток от деления λ(x) на x2t+1 . Очевидно, чтоmod (λ(x), x2t+1 ) = 1 + λ1 x + · · · + λν xν .Таким образом, произвольный многочлен σ(x), удовлетворяющий уравнениюs(x)σ(x) + x2t+1 a(x) = λ(x)(6)для некоторого многочлена λ(x), степень которого не превосходит t, будет искомым полиномом локаторов ошибок.
Данное уравнение может быть решено с помощью расширенного алгоритма Евклида для пары многочленовx2t+1 и s(x). Количество фактически совершенных ошибок ν определяется степенью найденного σ(x) (степеньλ(x) при этом может оказаться меньше ν).В итоге общая схема декодирования БЧХ кода выглядит следующим образом:1. Для принятого слова w(x) найти все синдромы si = w(αi ) ∀i = 1, . .
. , 2t;2. Найти полином локаторов ошибок σ(x) либо путем решения уравнения (6) с помощью расширенного алгоритма Евклида, либо последовательно решая ключевое уравнение для всех ν = t, t − 1, . . . до тех пор,пока матрица системы не окажется невырожденной;3. Найти все корни σ(x) полным перебором; пусть найденные корни равны αk1 , . . . , αkν ;4. Найти позиции ошибок ji = −ki mod n;5. Исправить ошибки v̂(x) = w(x) + xj1 + · · · + xjν ;6. Найти все синдромы v̂(x); если они не равны нулю, то выдать отказ от декодирования.9 Однако, наиболее эффективным декодером БЧХ кода с точки зрения вычислений на компьютере является декодер БерлекемпаМэсси.Пример 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: Таблица вычислений для поля 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С использованием таблицы 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 = α.Таким образом, синдромный полином 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}
