Лекции по прикладной алгебре. v2.0 (1127112), страница 16
Текст из файла (страница 16)
. . g k−1 ] данного кодабазисные векторы g i соответствуют полиномам xi g(x),i = 0, k − 1.Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: систематическое кодирование...Систематическое кодирование.Образуем полином xm u(x) (степени n − 1) и поделим его на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.и систематическое кодирование может быть задано какu(x) 7→ v(x) = xm u(x) + r(x), где r(x) ≡g(x) xm u(x).Ясно, что полином v(x) имеет в крайних правых позициях (пристарших степенях x) k коэффициентов полинома u(x).В порождающей матрице Gn×k = [ g 0 . . .
g k−1 ] данного кодабазисные векторы g i соответствуют полиномам xm+i + ri (x),где ri (x) ≡g(x) xm+i , i = 0, k − 1.210 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклический код: пример кодированияПусть требуется построить циклический код длины n = 7.1. Находим разложение полинома x7 + 1 на неприводимыемножители.Так как 7 = 23 − 1, то корнями x7 + 1 являются все ненулевыеэлементы поля F = F32 . Известно, что каждый многочлен надF2 содержит в расширении этого поля вместес любым своим2корнем β также смежные корни вида β 2 , β 2 , . .
.. Пусть α —произвольный примитивный элемент поля F . Тогда с учетомα7 = 1 находим разбиение элементов поля на смежные классы:(α, α2 , α4 ); (α3 , α6 , α5 ); α7 = 1.Таким образом, многочлен x7 + 1 имеет один неприводимыйделитель степени 1, а также два неприводимых делителястепени 3. В результате получаем разложениеx7 + 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).211 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклический код: пример кодирования...2.
Выбираем порождающий полином g(x): в этом качествеможет выступать произвольный делитель x7 + 1.Выберем g(x) = x3 + x + 1, тогда и m = n − k = 3 и будетпостроен циклический (7, 4)-код (k = 4).212 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклический код: пример кодирования...2. Выбираем порождающий полином g(x): в этом качествеможет выступать произвольный делитель x7 + 1.Выберем g(x) = x3 + x + 1, тогда и m = n − k = 3 и будетпостроен циклический (7, 4)-код (k = 4).3.
Проведём кодирование полинома u(x) = x3 + x2 .212 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклический код: пример кодирования...2. Выбираем порождающий полином g(x): в этом качествеможет выступать произвольный делитель x7 + 1.Выберем g(x) = x3 + x + 1, тогда и m = n − k = 3 и будетпостроен циклический (7, 4)-код (k = 4).3. Проведём кодирование полинома u(x) = x3 + x2 .3.1. Несистематическое кодирование:v(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2или в векторном представлении u = [0011], v = [0010111].212 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклический код: пример кодирования...2.
Выбираем порождающий полином g(x): в этом качествеможет выступать произвольный делитель x7 + 1.Выберем g(x) = x3 + x + 1, тогда и m = n − k = 3 и будетпостроен циклический (7, 4)-код (k = 4).3. Проведём кодирование полинома u(x) = x3 + x2 .3.1. Несистематическое кодирование:v(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2или в векторном представлении u = [0011], v = [0010111].3.2.
Систематическое кодирование. Находим остаток r(x) отделения многочлена x3 u(x) на g(x):x3 (x3 + x2 ) = x6 + x5 = (x3 + x2 + x)(x3 + x2 + 1) + x,поэтому v(x) = u(x) + r(x) = x6 + x5 + xили в векторном представлении u = [0011], v = [0100011].Мы видим, что биты входного сообщения u воспроизводятся вкрайних правых битах кодового слова v.212 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: декодированиеОпределениеНазовём синдромом принятого полинома w(x), являющимсязакодированным линейным циклическим (n, k)-кодом спорождающим полиномом g(x) некоторого сообщения и,возможно, содержащего ошибки (инвертированные биты),полином s(x) ≡g(x) w(x).Свойства синдрома w(x):0 6 deg s(x) < m = n − k;s(x) ≡g(x) v(x) + e(x) ≡g(x) e(x) ≡xn +1 w(x)h(x);s(x) ≡ 0 ⇔ w(x) — кодовое слово;213 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: декодирование...
и свойстваДекодирование циклического кода проходит по той же схеме, чтои декодирование линейного кода:12ищется решение системы e(x) = s(x) + g(x)u(x) для всехвозможных полиномов u(x) степени k − 1;полином ошибок определяется как решение с минимальнымчислом ненулевых слагаемых.214 / 432Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: декодирование... и свойстваДекодирование циклического кода проходит по той же схеме, чтои декодирование линейного кода:12ищется решение системы e(x) = s(x) + g(x)u(x) для всехвозможных полиномов u(x) степени k − 1;полином ошибок определяется как решение с минимальнымчислом ненулевых слагаемых.Свойства циклических кодовДля задания циклического кода достаточно указатьпорождающий или проверочный полином.Операции умножения матриц на векторы и решение СЛАУпри декодировании линейных кодов при декодированиициклических кодов заменяются на более простые впрактической реализации операции умножения и деленияполиномов с остатком.Алгоритм декодирования циклических кодов по-прежнемуимеет экспоненциальную сложность по k.214 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды215 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств216 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать217 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХКоды БЧХ — коды длины n = 2k − 1Рассматриваемый далее способ построения «хорошего» кода,исправляющего «много» ошибок предложили Радж ЧандраБоуз и Двайджендра Камар Рей-Чоудхури в 1959 г.
инезависимо Алексис Хоквингем в 1960 г.Они называются кодами Боуза-Чоудхури-Хоквингема илиБЧХ-кодами (BCH, Bose-Chaudhuri-Hocquenghem) — это классциклических кодов, исправляющих кратные (2 и более) ошибки.Теоретически коды БЧХ могут исправлять произвольноеколичество ошибок, но при этом существенно увеличиваетсядлина кодового слова (что приводит к уменьшению скоростипередачи данных и усложнению приёмно-передающейаппаратуры).Коды Хэмминга — частный случай БЧХ-кодов.218 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХУточнение описанной выше схемы при n = 2m − 1 —— конкретизирующей выбор идеала:219 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХУточнение описанной выше схемы при n = 2m − 1 —— конкретизирующей выбор идеала:123Строим поле Fn2 ∼= F2 [x]/(f ), f — неприводимыймногочлен степени n = 2m − 1.Выберем в циклической группе Fn∗2 порождающий(примитивный) элемент α ∈ Fn∗ирассмотрим его степени222rα, α , .
. . , α ,где r — число ошибок, которые нужно уметь исправлять.В разложении многочлена xn − 1 выберем такиенеприводимые многочлены, чтобы каждая из указанныхстепеней была корнем одного из них (это непростосделать, и даже не всегда возможно). Тогда:ϕ есть результат перемножения этих многочленов;коды — коэффициенты многочленов из идеала (ϕ);эти коды исправляют r ошибок (будет доказано далее).219 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ220 / 432Построение кода БЧХ, исправляющего 3 ошибкиПример (m = 4, многочлен для разложения: x15 − 1)Пусть нужен код, исправляющий r = 3 ошибки.
Значит, нужнонайти многочлены, корнями которых являются первые 2r = 6степеней порождающего элемента α.123если многочлен имеет кореньαα3α5то он имеет корниα2 , α4 , α86α , α12 , α9 (= α24 )α10По трём наборам корней построим три многочлена, два — 4-йстепени и один — 2-й. Перемножив их, получим многочлен 10-йстепени.Идеал по модулю этого многочлена будет 5-мернымпространством.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХСколько элементов содержит идеал (ϕ)?ϕ = произведение некоторых специально выбранныхнеприводимых многочленов-делителей xn − 1.Каждый делитель имеет, как минимум, 2 корня изсовокупности { α, .
. . , α2r }, т.е. их требуется не более rштук.Если делитель имеет корнями s элементовs{ αt , α2t , . . . , α2 t }, то 2s 6 n = 2m − 1, т.е. степенькаждого делителя не более m = log2 (n + 1).deg ϕ 6 rm = r log2 (n + 1).Идеал, порожденный ϕ, имеет размерность n − deg ϕ.2n|(ϕ)| 6 2n−r log2 (n+1) = (n+1)r.Ясно, что эта оценка далека от точности.221 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХСколько элементов содержит идеал (ϕ)?ϕ = произведение некоторых специально выбранныхнеприводимых многочленов-делителей xn − 1.Каждый делитель имеет, как минимум, 2 корня изсовокупности { α, . .
. , α2r }, т.е. их требуется не более rштук.Если делитель имеет корнями s элементовs{ αt , α2t , . . . , α2 t }, то 2s 6 n = 2m − 1, т.е. степенькаждого делителя не более m = log2 (n + 1).deg ϕ 6 rm = r log2 (n + 1).Идеал, порожденный ϕ, имеет размерность n − deg ϕ.2n|(ϕ)| 6 2n−r log2 (n+1) = (n+1)r.Ясно, что эта оценка далека от точности.221 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХОценка кодового расстоянияПокажем, что расстояние между точками кода не меньше, чем2r + 1 (что нам и требуется!).222 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХОценка кодового расстоянияПокажем, что расстояние между точками кода не меньше, чем2r + 1 (что нам и требуется!).Все многочлены, входящие в код — в идеал (ϕ) — кратны ϕ⇒ каждый кодовый многочлен имеет корни α, α2 , .
. . , α2r(как и ϕ). Кодовое расстояние = min γe, γe — элемент кода.Значит, надо доказать следующееУтверждениеЕсли многочлен ψ ∈ (ϕ) имеет корни αs , s = 1, . . . , 2r, то у ψне менее 2r + 1 ненулевого коэффициента.222 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ223 / 432Оценка кодового расстояния...ДоказательствоРассмотрим многочленψ(x) = a0 + a1 x + . . . + an−1 xn−1 ,удовлетворяющий указанному условию.Коэффициенты ψ(x)линейных уравнений:1αα22 1 α(α2 )2 ... ......1 α2r (α2r )2составляют решение следующей системы...αn−1a0 a1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
