Лекции по прикладной алгебре. v1.1 (1127111), страница 12

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

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

. . + an−1 xn−1 ,удовлетворяющий указанному условию.Коэффициенты ψ(x) составляют решение следующей системылинейных уравнений:1αα2...αn−1a00 1 α2 (α2 )2 . . . (α2 )n−1   a1  =  0 . ... .................. 2r2r22rn−11 α(α ) .

. . (α )an−10153 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХЕсли набор a = (a0 , . . . , an−1 ) — решение указанной системы,то между kak столбцами матрицы системы есть линейнаязависимость. Поэтому достаточно показать, что любые 2rстолбцов этой матрицы линейно независимы.Теория решения СЛАУ конечным полем ничем не отличаетсяот привычной теории решения СЛАУ над R (она вовсе независит от поля задания).

В частности, линейная зависимостьмежду столбцами квадратной матрицы равносильнаобращению в нуль определителя этой матрицы.Нам требуется показать, что в a не менее 2r + 1 ненулевыхэлементов ⇒ выберем из матрицы столбцы j1 , j2 , . . . , j2r .154 / 160Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХПолучим квадратную матрицуαj1α j22j1 (α )(α2 )j2 ......(α2r )j1 (α2r )j2155 / 160...αj2r. . . (α2 )j2r ......2rj2r. .

. (α )Вынесем из всех элементов столбца t общий множитель αjt .Получим, что определитель нашей матрицы с точностью доненулевого множителя αj1 +j2 +...+j2r равен11...1jjjα1α2...α 2rj1j2j2122r.(α )...(α )V = (α )............j2r−1j2r−1j2r−1 (α 1 )(α 2 ). . . (α 2r )Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ156 / 160Это хорошо известный определитель Вандермонда.Вычисляется он над конечным полем точно так же, как и над R:YV =αjt2 − αjt1 .t1 <t2В качестве α взят порождающий элемент мультипликативнойгруппы поля F2∗2 , поэтому все степени α вплоть до (n − 1)-йразличны.Поэтому V 6= 0.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХ156 / 160Это хорошо известный определитель Вандермонда.Вычисляется он над конечным полем точно так же, как и над R:YV =αjt2 − αjt1 .t1 <t2В качестве α взят порождающий элемент мультипликативнойгруппы поля F2∗2 , поэтому все степени α вплоть до (n − 1)-йразличны.Поэтому V 6= 0.Утверждение доказано: расстояние между кодовыми словамине меньше 2r + 1 ⇒ построенный код действительноисправляет r ошибок.Прикладная алгебраКоды, исправляющие ошибкиКоды БЧХЧто дальше?Для выбора минимальных многочленов при построенииБЧХ-кодов составлены специальные таблицы.Для декодирования БЧХ-кодов используют специальноразработанные эффективные алгоритмы(например, алгоритм Питерсона-Горенстейна-Цирлера).Широко используемым подмножеством кодов БЧХявляются коды Рида-Соломона, которые позволяютисправлять пакеты ошибок.Пакет ошибок характеризуется вектором ошибок (1 —символ ошибочен, 0 — нет) таких, что первый и последнийиз них отличны от нуля.157 / 160Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды158 / 160Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел IIКоды БЧХЧто надо знать159 / 160Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьЗадачи построения кодов, исправляющих ошибки.Основные понятия метрики на единичном кубе.Групповые коды: определения, свойства.

Кодовоерасстояние. Построение кода как задача плотной упаковки.Теорема Хэмминга. Пример построения кода Хэмминга.Циклические коды: определение, построение идекодирование.Коды БЧХ как частный случай циклических кодов. Идеяпостроения кода БЧХ и оценка его кодового расстояния.Коды БЧХ: алгоритмы кодирования и декодирования.160 / 160.

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

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