Лекции по прикладной алгебре. v2.0 (1127112), страница 17

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 17)

. . (α2 )n−1  .........2rn−1. . . (α )an−10 =  0 . ... 0Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХЕсли набор a = (a0 , . . . , an−1 ) — решение указанной системы,то между kak столбцами матрицы системы есть линейнаязависимость. Поэтому достаточно показать, что любые 2rстолбцов этой матрицы линейно независимы.Теория решения СЛАУ конечным полем ничем не отличаетсяот привычной теории решения СЛАУ над R (она вовсе независит от поля задания). В частности, линейная зависимостьмежду столбцами квадратной матрицы равносильнаобращению в нуль определителя этой матрицы.Нам требуется показать, что в a не менее 2r + 1 ненулевыхэлементов ⇒ выберем из матрицы столбцы j1 , j2 , . .

. , j2r .224 / 432Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХПолучим квадратную матрицуαj1α j22j1 (α )(α2 )j2 ......(α2r )j1 (α2r )j2225 / 432...αj2r. . . (α2 )j2r ......2rj2r. . . (α )Вынесем из всех элементов столбца t общий множитель αjt .Получим, что определитель нашей матрицы с точностью доненулевого множителя αj1 +j2 +...+j2r равен11...1jjjα1α2...α 2rj1j2j2122r.(α )...(α )V = (α )............j2r−1j2r−1j2r−1 (α 1 )(α 2 ).

. . (α 2r )Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ226 / 432Это хорошо известный определитель Вандермонда.Вычисляется он над конечным полем точно так же, как и над R:YV =αjt2 − αjt1 .t1 <t2В качестве α взят порождающий элемент мультипликативнойгруппы поля F2∗2 , поэтому все степени α вплоть до (n − 1)-йразличны.Поэтому V 6= 0.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ226 / 432Это хорошо известный определитель Вандермонда.Вычисляется он над конечным полем точно так же, как и над R:YV =αjt2 − αjt1 .t1 <t2В качестве α взят порождающий элемент мультипликативнойгруппы поля F2∗2 , поэтому все степени α вплоть до (n − 1)-йразличны.Поэтому 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)Линейный код задан своей проверочной матрицей0 0 1 1 1 1H =  0 1 0 1 1 0 1 1 1 0 1 0Требуется построить порождающую матрицу кода G длясистематического кодирования, при котором биты исходногосообщения переходят в последние биты кодового слова.Найти систематическое кодирование для векторовu1 = [1 1 0]T , u2 = [1 0 1]T .Прикладная алгебраКоды, исправляющие ошибкиЗадачи231 / 432Задача (ТК-1)Линейный код задан своей проверочной матрицей0 0 1 1 1 1H =  0 1 0 1 1 0 1 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 , т.е.

с помощью эквивалентныхпреобразований строк выделить в первых трех колонкахединичную матрицу:0 0 1 10 1 0 11 1 1 01→− 001 11 1 1 0 11↔3 1 0 −−−→ 0 1 0 1 11 00 0 1 1 10 1 1 0 011←1+31 0 1 1 0 −−−−→ 00 1 1 1 1001←1+20 −−−−→10 0 0 1 11 0 1 1 0 .0 1 1 1 1Прикладная алгебраКоды, исправляющие ошибкиЗадачи233 / 432Решение (продолжение)Теперь можно построить требуемую порождающую матрицу иосуществить кодирование для u1 = [1 1 0]T , u2 = [1 0 1]T :011G=100111010101,001Прикладная алгебраКоды, исправляющие ошибкиЗадачи233 / 432Решение (продолжение)Теперь можно построить требуемую порождающую матрицу иосуществить кодирование для u1 = [1 1 0]T , u2 = [1 0 1]T :011G=100111010101,001100[v 1 , v 2 ] = G[u1 , u2 ] = 110110.101Прикладная алгебраКоды, исправляющие ошибкиЗадачи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 ∈ F2 .Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение...)В векторном виде все кодовые слова представляются как[ 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)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом α ∈ F2 [x]/(x3 + x + 1).Требуется декодировать полученный полиномw(x) = x7 + x6 + x2 + 1.Прикладная алгебраКоды, исправляющие ошибкиЗадачи236 / 432Задача (ТК-3)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом α ∈ F2 [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)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом α ∈ F2 [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)Рассмотрим код Хэмминга, ноль которого определяетсяпримитивным элементом α ∈ F2 [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, .

Характеристики

Список файлов лекций