PA_full (1127144), страница 12
Текст из файла (страница 12)
Определить корни многочлена g(x) = (xполе 3 [x]/(x2 + 2x + 2) легко:↵)(x2↵1) вПрикладная алгебраПоля ГалуаЗадачи147 / 432Решение (продолжение -3)4. Определить корни многочлена g(x) = (xполе 3 [x]/(x2 + 2x + 2) легко:всегда можно взять ↵ = x,откуда второй корень ↵3 = 2↵ + 1 = 2x + 1.↵)(x2↵1) вПрикладная алгебраПоля ГалуаЗадачи147 / 432Решение (продолжение -3)4. Определить корни многочлена g(x) = (xполе 3 [x]/(x2 + 2x + 2) легко:всегда можно взять ↵ = x,откуда второй корень ↵3 = 2↵ + 1 = 2x + 1.↵)(x2↵5.
Таким образом, в поле 3 [x]/(x2 + 2x + 2) многочленf (x) = x3 + x + 2 имеет корни2, x и 2x + 1.1) вПрикладная алгебраПоля ГалуаЗадачи148 / 432Нахождение корней многочлена изp [x]Алгоритм нахождения всех корней многочлена f (x) надполем Галуа p1Разложить f (x) на неприводимые множители надp:f (x) = g1 (x) · g2 (x) · . . . · gk (x).2Для каждого многочлена gi (x), i = 1, k рассмотретьрасширение p [x]/(gi (x)), в котором он будет иметь корниdeg g 1x = ↵, ↵p , . . . , ↵p i .Записать данные корни как многочлены из p [x]/(gi (x)).3Объединить все корни в одном общем расширенииm = HOK ( deg g1 , deg g2 , . . . , deg gk ).m,pгдеПрикладная алгебраПоля ГалуаЗадачи149 / 432Задача (ПГ-24)Найти минимальный многочлен m(x) 2 5 [x], который имееткорень ↵3 , где ↵ � примитивный элемент поля25=5 [x]/(x2+ x + 2).Прикладная алгебраПоля ГалуаЗадачи149 / 432Задача (ПГ-24)Найти минимальный многочлен m(x) 2 5 [x], который имееткорень ↵3 , где ↵ � примитивный элемент поля25=5 [x]/(x2+ x + 2).Решение1.
Известно, что минимальный многочлен m(x) в полехарактеристики 5 вместе с корнем ↵3 содержит все смежные с23ним (↵3 )5 = ↵15 , (↵3 )5 = ↵75 , (↵3 )5 = ↵375 и т.д.Прикладная алгебраПоля ГалуаЗадачи149 / 432Задача (ПГ-24)Найти минимальный многочлен m(x) 2 5 [x], который имееткорень ↵3 , где ↵ � примитивный элемент поля25=5 [x]/(x2+ x + 2).Решение1. Известно, что минимальный многочлен m(x) в полехарактеристики 5 вместе с корнем ↵3 содержит все смежные с23ним (↵3 )5 = ↵15 , (↵3 )5 = ↵75 , (↵3 )5 = ↵375 и т.д.22.
В поле 25 будем иметь ↵5 1 = ↵24 = 1. Поэтому здесьсмежный класс, образованный ↵3 , содержит только дваэлемента ↵3 и ↵15 ) минимальный многочлен имеетстепень 2 и может быть представлен какm(x) = (x↵3 )(x↵15 ) = x2(↵3 + ↵15 )x + ↵18 .Прикладная алгебраПоля ГалуаЗадачи150 / 432Решение (продолжение; m(x) = x2(↵3 + ↵15 )x + ↵18 )3.
Найдём коэффициенты многочлена m(x) учётом↵2 = ↵ 2 = 4↵ + 3:↵3 = ↵ · ↵2 = ↵(4↵ + 3) = 4↵2 + 3↵ == 4(4↵ + 3) + 3↵ = 4↵ + 2,↵15 = (↵3 )5 = (4↵ + 2)5 = 4↵5 + 2 == 4↵2 ↵3 + 2 = 4(4↵ + 3)(4↵ + 2) + 2 == 4(↵2 + 1) + 2 = 4(4↵ + 4) + 2 = ↵ + 3,↵3 + ↵15 = 4↵ + 2 + ↵ + 3 = 0,↵18 = ↵3 ↵15 = (4↵ + 2)(↵ + 3) == 4(4↵ + 3) + 4↵ + 1 = 3.Прикладная алгебраПоля ГалуаЗадачи150 / 432Решение (продолжение; m(x) = x2(↵3 + ↵15 )x + ↵18 )3. Найдём коэффициенты многочлена m(x) учётом↵2 = ↵ 2 = 4↵ + 3:↵3 = ↵ · ↵2 = ↵(4↵ + 3) = 4↵2 + 3↵ == 4(4↵ + 3) + 3↵ = 4↵ + 2,↵15 = (↵3 )5 = (4↵ + 2)5 = 4↵5 + 2 == 4↵2 ↵3 + 2 = 4(4↵ + 3)(4↵ + 2) + 2 == 4(↵2 + 1) + 2 = 4(4↵ + 4) + 2 = ↵ + 3,↵3 + ↵15 = 4↵ + 2 + ↵ + 3 = 0,↵18 = ↵3 ↵15 = (4↵ + 2)(↵ + 3) == 4(4↵ + 3) + 4↵ + 1 = 3.В итоге:m(x) = x2 + 3.Прикладная алгебраПоля ГалуаЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды151 / 432Прикладная алгебраПоля ГалуаЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств152 / 432Прикладная алгебраПоля ГалуаЧто надо знатьРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать153 / 432Прикладная алгебраПоля ГалуаЧто надо знатьКонечное поле и его характеристика.
Мультипликативнаягруппа, примитивный элемент поля Галуа и егонахождение. Основная теорема алгебры.Алгоритм Евклида и его применение.Теорема Безу и расширенный алгоритм Евклида.Неприводимые многочлены: существование и нахождениенеприводимых многочленов в конечных полях. Построениеконечных полей с помощью неприводимых многочленов(привести пример). Изоморфизм конечных полей.Векторное пространство многочленов. Базис в np . ПоляГалуа как векторные пространства. Подполя конечногополя.154 / 432Прикладная алгебраПоля ГалуаЧто надо знатьМинимальные многочлены над конечным полем: примерыи свойства.
Корнями какого многочлена являются всеэлементы конечного поля? Делителями какого многочленаявляются все неприводимые многочлены n-й степени?Теорема о степени любого неприводимого делителяnмногочлена xp 1 1.Теорема о корнях неприводимого многочлена. Многочленынад конечным полем: решение уравнений.Как решать уравнения, когда корней нет (алгоритмнахождения всех корней многочлена f (x)над полем Галуа p )?Мультипликативная группа расширения поля.Существование неприводимого многочлена степени n надполем p .155 / 432Прикладная алгебраПоля ГалуаЧто надо знатьЛемма о числе неприводимых нормированных многочленовиз np .
Среднее число неприводимых многочленов.Изоморфизм полей Галуа с одинаковым числом элементов.Теорема о неприводимом нормированном многочлене �делителе порождающего элемента идеала.Циклическое пространство: определение и примеры.Количество и степени неприводимых делителей xn 1.156 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды157 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств158 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать159 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды Хэмминга160 / 432Задача помехоустойчивого кодирования: подходы к решениюПо каналу с шумом проходит поток битовой информации.Модель потока: случайный некоррелированный.Модель шума: некоторые биты случайно и независимодруг от друга могут оказаться инвертированными (нетдобавлений/стираний битов) � модель случайных ошибок.Задача: обеспечить автоматическое исправление ошибок.Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды Хэмминга160 / 432Задача помехоустойчивого кодирования: подходы к решениюПо каналу с шумом проходит поток битовой информации.Модель потока: случайный некоррелированный.Модель шума: некоторые биты случайно и независимодруг от друга могут оказаться инвертированными (нетдобавлений/стираний битов) � модель случайных ошибок.Задача: обеспечить автоматическое исправление ошибок.Подход к решению:12входящий поток информации разбить на сообщения �непересекающиеся блоки фиксированной длины k.каждый блок можно кодировать �а) независимо от других � блоковое или блочноекодирование;б) в зависимости от предыдущих � свёрточноекодирование (турбо-коды и др.).Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаЗадачи блокового кодированияДалее будем рассматривать исключительно блоковое кодирование.Есть набор сообщений S1 , . . . , St , каждое длины k, которыенужно передать по каналу связи с шумом.Для обеспечения помехозащишённости вместо этихсообщений передают блоки длины n > k � кодовые слова.161 / 432Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды Хэмминга161 / 432Задачи блокового кодированияДалее будем рассматривать исключительно блоковое кодирование.Есть набор сообщений S1 , . . . , St , каждое длины k, которыенужно передать по каналу связи с шумом.Для обеспечения помехозащишённости вместо этихсообщений передают блоки длины n > k � кодовые слова.Задача (основная): построить код минимальной длины n,позволяющий восстановить сообщение, содержащее не более rошибок.Прикладная алгебраКоды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды Хэмминга161 / 432Задачи блокового кодированияДалее будем рассматривать исключительно блоковое кодирование.Есть набор сообщений S1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
