PA_full (1127144), страница 17
Текст из файла (страница 17)
. . , ↵2r(как и ').Кодовое расстояние = min e , e � элемент кода.Значит, надо доказать следующееУтверждениеЕсли многочлен 2 (') имеет корни ↵s , s = 1, . . . , 2r, то уне менее 2r + 1 ненулевого коэффициента.222 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ223 / 432Оценка кодового расстояния...ДоказательствоРассмотрим многочлен(x) = a0 + a1 x + . . .
+ an1xn 1,удовлетворяющий указанному условию.Коэффициенты (x)линейных уравнений:01↵↵22B 1 ↵(↵2 )2B@ ... ......1 ↵2r (↵2r )2составляют решение следующей системы10...↵n 1a0B a1. . . (↵2 )n 1 CCBA@ .........2rn1. . . (↵ )an 11010CBCC = B 0 C.A@ ... A0Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХЕсли набор a = (a0 , .
. . , an 1 ) � решение указанной системы,то между kak столбцами матрицы системы есть линейнаязависимость. Поэтому достаточно показать, что любые 2rстолбцов этой матрицы линейно независимы.Теория решения СЛАУ конечным полем ничем не отличаетсяот привычной теории решения СЛАУ над (она вовсе независит от поля задания). В частности, линейная зависимостьмежду столбцами квадратной матрицы равносильнаобращению в нуль определителя этой матрицы.Нам требуется показать, что в a не менее 2r + 1 ненулевыхэлементов ) выберем из матрицы столбцы j1 , j2 , . . . , j2r .224 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХПолучим квадратную матрицу0↵ j1↵ j22j1B (↵ )(↵2 )j2B@ ......(↵2r )j1 (↵2r )j2225 / 4321...↵j2r.
. . (↵2 )j2r CCA......2rj2r. . . (↵ )Вынесем из всех элементов столбца t общий множитель ↵jt .Получим, что определитель нашей матрицы с точностью доненулевого множителя ↵j1 +j2 +...+j2r равенV =11↵ j1↵ j2(↵j1 )1(↵j2 )2......(↵j1 )2r 1 (↵j2 )2r 1...1...↵j2r...(↵j2r )2....... . . (↵j2r )2r 1.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ226 / 432Это хорошо известный определитель Вандермонда.Вычисляется он над конечным полем точно так же, как и над :YV =↵ jt2 ↵ jt1 .t1 <t2В качестве ↵ взят порождающий элемент мультипликативнойгруппы поля 2⇤1)-й2 , поэтому все степени ↵ вплоть до (nразличны.Поэтому V 6= 0.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ226 / 432Это хорошо известный определитель Вандермонда.Вычисляется он над конечным полем точно так же, как и над :YV =↵ jt2 ↵ jt1 .t1 <t2В качестве ↵ взят порождающий элемент мультипликативнойгруппы поля 2⇤1)-й2 , поэтому все степени ↵ вплоть до (nразличны.Поэтому V 6= 0.Утверждение доказано: расстояние между кодовыми словамине меньше 2r + 1 ) построенный код действительноисправляет r ошибок.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХЧто дальше?Для выбора минимальных многочленов при построенииБЧХ-кодов составлены специальные таблицы.Для декодирования БЧХ-кодов используют специальноразработанные эффективные алгоритмы(например, алгоритм Питерсона-Горенстейна-Цирлера).Широко используемым подмножеством кодов БЧХявляются коды Рида-Соломона, которые позволяютисправлять пакеты ошибок.Пакет ошибок характеризуется вектором ошибок (1 �символ ошибочен, 0 � нет) таких, что первый и последнийиз них отличны от нуля.227 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды228 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств229 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать230 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачи231 / 432Задача (ТК-1)Линейный код задан своей проверочной матрицей010 0 1 1 1 1H = @ 0 1 0 1 1 0 A1 1 1 0 1 0Требуется построить порождающую матрицу кода G длясистематического кодирования, при котором биты исходногосообщения переходят в последние биты кодового слова.Найти систематическое кодирование для векторовu1 = [1 1 0]T , u2 = [1 0 1]T .Прикладная алгебраКоды, исправляющие ошибкиЗадачи231 / 432Задача (ТК-1)Линейный код задан своей проверочной матрицей010 0 1 1 1 1H = @ 0 1 0 1 1 0 A1 1 1 0 1 0Требуется построить порождающую матрицу кода G длясистематического кодирования, при котором биты исходногосообщения переходят в последние биты кодового слова.Найти систематическое кодирование для векторовu1 = [1 1 0]T , u2 = [1 0 1]T .Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешениеПорождающая матрица кода G, обеспечивающая требуемоеPсистематическое кодирование, должна иметь вид, где I3 �I3единичная матрица порядка размера 3.232 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачи232 / 432РешениеПорождающая матрица кода G, обеспечивающая требуемоеPсистематическое кодирование, должна иметь вид, где I3 �I3единичная матрица порядка размера 3.Такую матрицу можноесли привести проверочную⇥ получить,⇤матрицу H к виду I3 P , т.е.
с помощью эквивалентныхпреобразований строк выделить в первых трех колонкахединичную матрицу:20 0 1 140 1 0 11 1 1 021! 40031 11 051 0231 1 1 0 1 01$3 41 1+2! 0 1 0 1 1 05!0 0 1 1 1 13230 1 1 0 01 0 0 0 1 11 1+3 41 0 1 1 05! 0 1 0 1 1 05 .0 1 1 1 10 0 1 1 1 1Прикладная алгебраКоды, исправляющие ошибкиЗадачи233 / 432Решение (продолжение)Теперь можно построить требуемую порождающую матрицу иосуществить кодирование для u1 = [1 1 0]T , u2 = [1 0 1]T :2061661G=661640011101031077177,077051Прикладная алгебраКоды, исправляющие ошибкиЗадачи233 / 432Решение (продолжение)Теперь можно построить требуемую порождающую матрицу иосуществить кодирование для u1 = [1 1 0]T , u2 = [1 0 1]T :2061661G=661640011101031077177,0770512160660[v 1 , v 2 ] = G[u1 , u2 ] = 661641031177077.177051Прикладная алгебраКоды, исправляющие ошибкиЗадачи234 / 432Задача (ТК-2)Циклический (9, 3)-код задан своим порождающим полиномомg(x) = x6 + x3 + 1.Требуется определить минимальное расстояние кода d, а такжеосуществить систематическое кодирование полиномаu(x) = x2 + x.Прикладная алгебраКоды, исправляющие ошибкиЗадачи234 / 432Задача (ТК-2)Циклический (9, 3)-код задан своим порождающим полиномомg(x) = x6 + x3 + 1.Требуется определить минимальное расстояние кода d, а такжеосуществить систематическое кодирование полиномаu(x) = x2 + x.РешениеДля определения минимального кодового расстояния d найдёмвсе кодовые полиномы:v(x) = g(x)(ax2 + bx + c) = (x6 + x3 + 1)(ax2 + bx + c) == ax8 + bx7 + cx6 + ax5 + bx4 + cx3 + ax2 + bx + c, a, b, c 22.Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение...)В векторном виде все кодовые слова представляются как[ a, b, c, a, b, c, a, b, c ].Следовательно, минимальный хэммингов вес ненулевогокодового слова равен 3, т.е.
d = 3.235 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачи235 / 432Решение (продолжение...)В векторном виде все кодовые слова представляются как[ a, b, c, a, b, c, a, b, c ].Следовательно, минимальный хэммингов вес ненулевогокодового слова равен 3, т.е. d = 3.Систематическое кодирование полинома u(x) вычисляемнепосредственноv(x) = x6 u(x) + mod x6 u(x), g(x) == x8 +x7 +mod x8 + x7 , x6 + x3 + 1 = x8 +x7 +x5 +x4 +x2 +x.Прикладная алгебраКоды, исправляющие ошибкиЗадачи236 / 432Задача (ТК-3)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом ↵ 2 2 [x]/(x3 + x + 1).Требуется декодировать полученный полиномw(x) = x7 + x6 + x2 + 1.Прикладная алгебраКоды, исправляющие ошибкиЗадачи236 / 432Задача (ТК-3)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом ↵ 2 2 [x]/(x3 + x + 1).Требуется декодировать полученный полиномw(x) = x7 + x6 + x2 + 1.РешениеВычислим синдром с учётом ↵3 = ↵ + 1:s = w(↵) = ↵7 + ↵6 + ↵2 + 1 = ↵(↵3 )2 + (↵3 )2 + ↵2 + 1 == ↵(↵ + 1)2 + (↵ + 1)2 + ↵2 + 1 = ↵(↵2 + 1) + ↵2 + 1 + ↵2 + 1 == ↵3 + ↵ = ↵ + 1 + ↵ = 1.Прикладная алгебраКоды, исправляющие ошибкиЗадачи236 / 432Задача (ТК-3)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом ↵ 2 2 [x]/(x3 + x + 1).Требуется декодировать полученный полиномw(x) = x7 + x6 + x2 + 1.РешениеВычислим синдром с учётом ↵3 = ↵ + 1:s = w(↵) = ↵7 + ↵6 + ↵2 + 1 = ↵(↵3 )2 + (↵3 )2 + ↵2 + 1 == ↵(↵ + 1)2 + (↵ + 1)2 + ↵2 + 1 = ↵(↵2 + 1) + ↵2 + 1 + ↵2 + 1 == ↵3 + ↵ = ↵ + 1 + ↵ = 1.Далее необходимо найти полином ошибок вида e(x) = xkтакой, что e(↵) = s, т.е.
найти такое k, что ↵k = 1.Прикладная алгебраКоды, исправляющие ошибкиЗадачи236 / 432Задача (ТК-3)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом ↵ 2 2 [x]/(x3 + x + 1).Требуется декодировать полученный полиномw(x) = x7 + x6 + x2 + 1.РешениеВычислим синдром с учётом ↵3 = ↵ + 1:s = w(↵) = ↵7 + ↵6 + ↵2 + 1 = ↵(↵3 )2 + (↵3 )2 + ↵2 + 1 == ↵(↵ + 1)2 + (↵ + 1)2 + ↵2 + 1 = ↵(↵2 + 1) + ↵2 + 1 + ↵2 + 1 == ↵3 + ↵ = ↵ + 1 + ↵ = 1.Далее необходимо найти полином ошибок вида e(x) = xkтакой, что e(↵) = s, т.е. найти такое k, что ↵k = 1.Очевидно, что k = 0 ) vb(x) = w(x) + e(x) = x7 + x6 + x2 .Прикладная алгебраКоды, исправляющие ошибкиЗадачи237 / 432Задача (ТК-4)Рассмотрим код БЧХ с нулями ↵i , i = 1, .
. . , 4, где ↵ �примитивный элемент поля 2 [x]/(x4 + x + 1).Требуется найти полином локаторов ошибок (x) дляпринятого полиномаw(x) = x14 + x10 + x5 + x4 .Прикладная алгебраКоды, исправляющие ошибкиЗадачи237 / 432Задача (ТК-4)Рассмотрим код БЧХ с нулями ↵i , i = 1, . . . , 4, где ↵ �примитивный элемент поля 2 [x]/(x4 + x + 1).Требуется найти полином локаторов ошибок (x) дляпринятого полиномаw(x) = x14 + x10 + x5 + x4 .РешениеДля удобства вычислений в поле 42 построим таблицусоответствий между степенным и полиномиальнымпредставлением элементов поля.Прикладная алгебраКоды, исправляющие ошибкиЗадачи238 / 432Решение (продолжение 1;↵↵2↵3↵4↵5↵6↵7↵8↵9↵10↵11↵12↵13↵14↵15↵4 = ↵ + 1)↵↵2↵3↵+1↵2 + ↵↵3 + ↵2↵3 + ↵ + 1↵2 + 1↵3 + ↵↵2 + ↵ + 1↵3 + ↵2 + ↵↵3 + ↵2 + ↵ + 1↵3 + ↵2 + 1↵3 + 11Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 2)С помощью этой таблицы вычислим синдромы:s1 = w(↵) = ↵14 + ↵10 + ↵5 + ↵4 = ↵7 ,s2 = w(↵2 ) = (w(↵))2 = ↵14 ,s3 = w(↵3 ) = ↵12 + 1 + 1 + ↵12 = 0,s4 = w(↵4 ) = (w(↵2 ))2 = ↵13 .239 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 2)С помощью этой таблицы вычислим синдромы:s1 = w(↵) = ↵14 + ↵10 + ↵5 + ↵4 = ↵7 ,s2 = w(↵2 ) = (w(↵))2 = ↵14 ,s3 = w(↵3 ) = ↵12 + 1 + 1 + ↵12 = 0,s4 = w(↵4 ) = (w(↵2 ))2 = ↵13 .Синдромный полином � s(x) = ↵13 x4 + ↵14 x2 + ↵7 x + 1.Синдромов всего четыре, следовательно, t = 2.239 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачи239 / 432Решение (продолжение 2)С помощью этой таблицы вычислим синдромы:s1 = w(↵) = ↵14 + ↵10 + ↵5 + ↵4 = ↵7 ,s2 = w(↵2 ) = (w(↵))2 = ↵14 ,s3 = w(↵3 ) = ↵12 + 1 + 1 + ↵12 = 0,s4 = w(↵4 ) = (w(↵2 ))2 = ↵13 .Синдромный полином � s(x) = ↵13 x4 + ↵14 x2 + ↵7 x + 1.Синдромов всего четыре, следовательно, t = 2.Полином локаторов ошибок (x) является решением уравненияx2t+1 a(x) + s(x) (x) =(x), deg (x) 6 t.Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 3;x2t+1 a(x) + s(x) (x) = (x), deg (x) 6 t)Решаем с помощью расширенного алгоритма Евклида:Шаг 0.
r 2 (x) = x5 , // Инициализацияr 1 (x) = ↵13 x4 + ↵14 x2 + ↵7 x + 1,y 2 (x) = 0,y 1 (x) = 1.Шаг 1. r 2 (x) = r 1 (x)q0 (x) + r0 (x),// Делим r 2 (x) на r 1 (x) с остаткомq0 (x) = ↵2 x,r0 (x) = ↵x3 + ↵9 x2 + ↵2 x,y0 (x) = y 2 (x) y 1 (x)q0 (x) = q0 (x) = ↵2 x.Шаг 2. r 1 (x) = r0 (x)q1 (x) + r1 (x),// Делим r 1 (x) на r0 (x) с остаткомq1 (x) = ↵12 x + ↵5 ,r1 (x) = ↵14 x2 + 1,y1 (x) = y 1 (x) y0 (x)q1 (x) == 1 + ↵2 x(↵12 x + ↵5 ) = ↵14 x2 + ↵7 x + 1.240 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачи241 / 432Решение (продолжение 4)Таким образом, искомый полином локаторов ошибок(x) = ↵14 x2 + ↵7 x + 1.Прикладная алгебраКоды, исправляющие ошибкиЗадачиЗадача (ТК-5)Рассмотрим код БЧХ, нули которого определяются степенями↵, где ↵ � примитивный элемент поля 2 [x]/(x4 + x + 1).Пусть для некоторого принятого слова w(x) полином локаторовошибок (x) = ↵2 x2 + ↵6 x + 1.Требуется определить позиции ошибок в w(x).242 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиЗадача (ТК-5)Рассмотрим код БЧХ, нули которого определяются степенями↵, где ↵ � примитивный элемент поля 2 [x]/(x4 + x + 1).Пусть для некоторого принятого слова w(x) полином локаторовошибок (x) = ↵2 x2 + ↵6 x + 1.Требуется определить позиции ошибок в w(x).РешениеНайдём корни полинома локаторов ошибок полным перебором.Для вычислений будем пользоваться таблицей соответствиймежду степенным и полиномиальным представлениемэлементов поля, вычисленной выше.242 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 1;243 / 432↵4 = ↵ + 1)(↵) = ↵4 + ↵7 + 1 = ↵3 + 1,(↵2 ) = ↵6 + ↵8 + 1 = ↵3 ,(↵3 ) = ↵8 + ↵9 + 1 = ↵3 + ↵2 + ↵,(↵4 ) = ↵10 + ↵10 + 1 = 1,(↵5 ) = ↵12 + ↵11 + 1 = 0,(↵6 ) = ↵14 + ↵12 + 1 = ↵2 + ↵ + 1,(↵7 ) = ↵ + ↵13 + 1 = ↵3 + ↵2 + 1,(↵8 ) = ↵3 + ↵14 + 1 = 0,(↵9 ) = ↵5 + 1 + 1 = ↵2 + ↵,(↵10 ) = ↵7 + ↵ + 1 = ↵3 ,Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 2)(↵11 ) = ↵9 + ↵2 + 1 = ↵3 + ↵2 + ↵ + 1,(↵12 ) = ↵11 + ↵3 + 1 = ↵2 + ↵ + 1,(↵13 ) = ↵13 + ↵4 + 1 = ↵3 + ↵2 + ↵ + 1,(↵14 ) = 1 + ↵5 + 1 = ↵2 + ↵,(↵15 ) = ↵2 + ↵6 + 1 = ↵3 + 1.244 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 2)(↵11 ) = ↵9 + ↵2 + 1 = ↵3 + ↵2 + ↵ + 1,(↵12 ) = ↵11 + ↵3 + 1 = ↵2 + ↵ + 1,(↵13 ) = ↵13 + ↵4 + 1 = ↵3 + ↵2 + ↵ + 1,(↵14 ) = 1 + ↵5 + 1 = ↵2 + ↵,(↵15 ) = ↵2 + ↵6 + 1 = ↵3 + 1.Заметим, что полином локаторов ошибок (x) являетсяполиномом над полем 42 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
