PA_full (1127144), страница 16
Текст из файла (страница 16)
. . g k 1 ] данного кодабазисные векторы g i соответствуют полиномам xi g(x),i = 0, k 1.Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды210 / 432Циклические коды: систематическое кодирование...Систематическое кодирование.Образуем полином xm u(x) (степени ng(x) с остатком:1) и поделим его наxm u(x) = g(x)q(x) + r(x) и deg r(x) < m.Тогдаxm u(x) + r(x) = g(x)q(x) 2 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.Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклический код: пример кодированияПусть требуется построить циклический код длины n = 7.1. Находим разложение полинома x7 + 1 на неприводимыемножители.Так как 7 = 23 1, то корнями x7 + 1 являются все ненулевыеэлементы поля F = 32 .
Известно, что каждый многочлен над2 содержит в расширении этого поля вместе с любым своим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Прикладная алгебраКоды, исправляющие ошибкиЦиклические коды213 / 432Циклические коды: декодированиеОпределениеНазовём синдромом принятого полинома w(x), являющимсязакодированным линейным циклическим (n, k)-кодом спорождающим полиномом g(x) некоторого сообщения и,возможно, содержащего ошибки (инвертированные биты),полином s(x) ⌘g(x) w(x).Свойства синдрома w(x):0 6 deg s(x) < m = nk;s(x) ⌘g(x) v(x) + e(x) ⌘g(x) e(x) ⌘xn +1 w(x)h(x);s(x) ⌘ 0 , w(x) � кодовое слово;Прикладная алгебраКоды, исправляющие ошибкиЦиклические кодыЦиклические коды: декодирование...
и свойстваДекодирование циклического кода проходит по той же схеме, чтои декодирование линейного кода: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 = 2k218 / 4321Рассматриваемый далее способ построения �хорошего� кода,исправляющего �много� ошибок предложили Радж ЧандраБоуз и Двайджендра Камар Рей-Чоудхури в 1959 г.
инезависимо Алексис Хоквингем в 1960 г.Они называются кодами Боуза-Чоудхури-Хоквингема илиБЧХ-кодами (BCH, Bose-Chaudhuri-Hocquenghem) � это классциклических кодов, исправляющих кратные (2 и более) ошибки.Теоретически коды БЧХ могут исправлять произвольноеколичество ошибок, но при этом существенно увеличиваетсядлина кодового слова (что приводит к уменьшению скоростипередачи данных и усложнению приёмно-передающейаппаратуры).Коды Хэмминга � частный случай БЧХ-кодов.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХУточнение описанной выше схемы при n = 2m� конкретизирующей выбор идеала:219 / 4321�Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХУточнение описанной выше схемы при n = 2m219 / 4321�� конкретизирующей выбор идеала:1Строим поле n2 ⇠= 2 [x]/(f ), f � неприводимыймногочлен степени n = 2m 1.2Выберем в циклической группе n⇤2 порождающий(примитивный) элемент ↵ 2 n⇤ирассмотрим его степени222r↵, ↵ , .
. . , ↵ ,где r � число ошибок, которые нужно уметь исправлять.3В разложении многочлена xn 1 выберем такиенеприводимые многочлены, чтобы каждая из указанныхстепеней была корнем одного из них (это непростосделать, и даже не всегда возможно). Тогда:' есть результат перемножения этих многочленов;коды � коэффициенты многочленов из идеала (');эти коды исправляют r ошибок (будет доказано далее).Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ220 / 432Построение кода БЧХ, исправляющего 3 ошибкиПример (m = 4, многочлен для разложения: x151)Пусть нужен код, исправляющий 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 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
