AA3-2(ECC) (1127140), страница 5
Текст из файла (страница 5)
. . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) ∈ C.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыОпределение и основные свойства56 / 132Циклические коды: определениеОпределениеКод C называется циклическим (эквидистантным,сдвиговым), если он инвариантен относительно циклическихсдвигов, т.е. для любого 0 6 s 6 n − 1 справедливо(α0 , . . . , αn−1 ) ∈ C ⇒ (αs , αs+1 , .
. . , αn−1 , α0 , . . . , αs−1 ) ∈ C.Ранее рассматривалось и было показано:В кольце Fp [x]/(xn − 1), рассматриваемом как линейноевекторноепространствоno над полем Fp , имеется базис1, x, . . . , xn−1 .Циклический сдвиг координат в этом базисе равносиленумножению на x.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыОпределение и основные свойства56 / 132Циклические коды: определениеОпределениеКод C называется циклическим (эквидистантным,сдвиговым), если он инвариантен относительно циклическихсдвигов, т.е. для любого 0 6 s 6 n − 1 справедливо(α0 , . .
. , αn−1 ) ∈ C ⇒ (αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) ∈ C.Ранее рассматривалось и было показано:В кольце Fp [x]/(xn − 1), рассматриваемом как линейноевекторноепространствоno над полем Fp , имеется базис1, x, . . . , xn−1 .Циклический сдвиг координат в этом базисе равносиленумножению на x.Теорема: Линейное подпространство I ⊆ Fp [x]/(xn − 1)является циклическим iff I Fp [x]/(xn − 1).ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыОпределение и основные свойстваЦиклические коды: идея построенияПоэтому построить двоичный циклический код можно так:12выбираем некоторый делитель g(x) многочлена xn + 1.Многочлен g(x) называют порождающим илиобразующим.в кольцеF2 [x]/(xn + 1) образуем идеал (g(x)).57 / 132ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЦиклические кодыОпределение и основные свойстваЦиклические коды: идея построенияПоэтому построить двоичный циклический код можно так:12выбираем некоторый делитель g(x) многочлена xn + 1.Многочлен g(x) называют порождающим илиобразующим.в кольцеF2 [x]/(xn + 1) образуем идеал (g(x)).Оказывается, при удачном выборе g(x) коэффициентымногочленов из данного идеала будут давать хороший код(с малой избыточностью m/n при большом d ).Однако:есть только несколько конструкций циклических кодовс хорошими параметрами;в общем случае определение кодового расстоянияциклического кода чрезвычайно сложно.57 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыОпределение и основные свойства58 / 132Линейные циклические кодыИз всех линейных (n, k)-кодов будем далее рассматривать те,которые являются одновременно и циклическими.Установим соответствие вектора v координатногопространства {0, 1}n и полинома v(x) ∈ F2 [x]:v = [ v0 , v1 , .
. . , vn−1 ]T ↔ v(x) = v0 + v1 x + . . . + vn−1 xn−1 .Тогда свойство главного идеала переформулируется:для каждого (n, k)-циклического кода найдется порождающийполином g(x) такой, что1 g(x) xn + 1;2любое кодовое слово v(x) представляется в видеv(x) = g(x)q(x), где q(x) — некоторый полином.Любой делящий xn + 1 полином является порождающим длянекоторого циклического кода длины n.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодированиеРазделы12Блоковое кодирование.
Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать59 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование60 / 132Циклические коды: кодированиеПусть задан порождающий полином g(x) степени m(это число проверочных битов у будущего кода C).Рассмотримвозможныеметодыпостроениялинейныхциклических (n, k)-кодов (n = m + k), кодирующих сообщение–полином u(x) степени k − 1:u(x) 7→ v(x).Результат — кодовое слово–полином v(x) ∈ C степени n − 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование60 / 132Циклические коды: кодированиеПусть задан порождающий полином g(x) степени m(это число проверочных битов у будущего кода C).Рассмотримвозможныеметодыпостроениялинейныхциклических (n, k)-кодов (n = m + k), кодирующих сообщение–полином u(x) степени k − 1:u(x) 7→ v(x).Результат — кодовое слово–полином v(x) ∈ C степени n − 1.Несистематическое кодирование:v(x) = g(x)u(x).В порождающей матрице Gn×k = [ g 0 .
. . g k−1 ] данного кодабазисные векторы g i соответствуют полиномамxi g(x), i = 0, k − 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодированиеЦиклические коды: систематическое кодирование...Систематическое кодированиеОбразуем полином xm u(x) (степени m + k − 1 = 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и систематическое кодирование может быть задано какv(x) = xm u(x) + r(x), где r(x) ≡g(x) xm u(x).Полином v(x) имеет в k крайних правых позициях (т.е. пристарших степенях 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.61 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодированиеЦиклический код: пример кодированияПусть требуется построить циклический код длиныn = 7.Это означает, что работаем в кольце F2 [x]/ x7 + 1 .62 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование62 / 132Циклический код: пример кодированияПусть требуется построить циклический код длиныn = 7.Это означает, что работаем в кольце F2 [x]/ x7 + 1 .1.
Находим разложение полинома x7 + 1 на неприводимыемножители.Так как 7 = 23 − 1, то корнями x7 + 1 являются все ненулевыеэлементы поля F32 .Известно, что:каждый многочлен f над конечным полем содержит врасширении этого поля вместе с любым своим корнем β2также смежные корни вида β 2 , β 2 , . . .;если f приводим, то имеется несколько серий такихсмежных корней.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование63 / 132Циклический код: пример кодирования...Пусть α — произвольный примитивный элемент поля F = F32 .Тогда с учетом α7 = 1 находим разбиение корней x7 + 1 (= всехэлементов F ) на смежные классы: α, α2 , α4 , α3 , α6 , α5 , { 1 }.Таким образом, многочлен x7 + 1 имеет один неприводимыйделитель 1-й степени и два неприводимых делителя 3-й степени.В результате получаем разложениеx7 + 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование63 / 132Циклический код: пример кодирования...Пусть α — произвольный примитивный элемент поля F = F32 .Тогда с учетом α7 = 1 находим разбиение корней x7 + 1 (= всехэлементов F ) на смежные классы: α, α2 , α4 , α3 , α6 , α5 , { 1 }.Таким образом, многочлен x7 + 1 имеет один неприводимыйделитель 1-й степени и два неприводимых делителя 3-й степени.В результате получаем разложениеx7 + 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).2. Выбираем порождающий полином g(x).Можно выбрать любой делитель x7 + 1 ⇒ выберемg(x) = x3 + x + 1, тогда deg g(x) = 3 = m, k = n − m = 4и построен циклический (7, 4)-код.Его кодовое расстояние — надо выяснять...ПРИКЛАДНАЯ АЛГЕБРА.
Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодированиеЦиклический код: пример кодирования...3. Проведём кодирование полинома u(x) = x3 + x2 или ввекторном представлении u = [0011] (k = 4).64 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодированиеЦиклический код: пример кодирования...3. Проведём кодирование полинома u(x) = x3 + x2 или ввекторном представлении u = [0011] (k = 4).3.1.
Несистематическое кодирование:v(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2или в векторном представлении v = [0010111] (n = 7).64 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование64 / 132Циклический код: пример кодирования...3. Проведём кодирование полинома u(x) = x3 + x2 или ввекторном представлении u = [0011] (k = 4).3.1. Несистематическое кодирование:v(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2или в векторном представлении v = [0010111] (n = 7).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или в векторном представлении v = [0100011] (n = 7).Мы видим, что биты входного сообщения u воспроизводятся вкрайних правых битах кодового слова v.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЦиклические кодыКодирование циклическими кодами и декодирование64 / 132Циклический код: пример кодирования...3. Проведём кодирование полинома u(x) = x3 + x2 или ввекторном представлении u = [0011] (k = 4).3.1. Несистематическое кодирование:v(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2или в векторном представлении v = [0010111] (n = 7).3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
