Прикладная алгебра. Суровый теормин (1127343), страница 2
Текст из файла (страница 2)
Полиномиальное и степенное представление элементов поля.Любой элемент циклической группы можно представить как степень примитивного элемента.Пример: слайды 265 и далее.Алгоритм нахождения всех корней многочлена f(x) над полем .Минимальные многочлены для элементов конечного поля. Алгоритмнахождения минимального многочлена.v. {(3) – слайд 129}Определение минимального многочлена.Рассмотрим поле , а в нем — какой-нибудь элемент β и будем интересоваться многочленами, длякоторых этот элемент является корнем. Многочлен m(x) называется минимальной функцией (илиминимальным многочленом, м.м.) для β, если m(x) —нормированный многочлен минимальнойстепени, для которого β является корнем.w.
Алгоритм нахождения минимального многочлена.Теорема Хэмминга. Пример построения кода Хэмминга.x. {(1) – стр. 172}Теорема Хэмминга.При 2r < n максимальное число t кодовых слов находится в пределах2( )+( )+⋯+( )012≤≤2( )+( )+⋯+( )01r – максимально допустимое число ошибок.n – длина кода.y.
{(1) – стр. 173}Пример построения кода Хэмминга.n = 2q – 1, r = 1. Для q = 3 построим код Хэмминга (длины 7).Построим таблицу: слева – диагональная матрица размерности 2q – (q+1), справа все бинарныенаборы длины q, содержащие не менее 2-х единиц. Складывая по mod 2 произвольные совокупностистрок, получаем 16 различных бинарных наборов, которыми можно закодировать 16 сообщений.1 0 0 0 1 1 00 1 0 0 1 0 10 0 1 0 0 1 10 0 0 1 1 1 1Коды БЧХ: определение, примеры кодов с исправлением одной, двух итрех ошибок.z. Определение кода БЧХ.{(3) – слайд 402 и далее}Циклический код, исправляющий кратные (2 и более) ошибки.{(5) – стр.
5}Пусть = 2 − 1, = 2 + 1 ≤ . Тогда кодом БЧХ называется (n, k, d)-линейный циклический код, вкотором порождающий многочлен g(x) определяется как минимальный многочлен для элементов, 2 , … , −1 из поля 2 , где – произвольный примитивный элемент поля 2 .Схема построения: Строим поле 2 ≅ 2 []/, − неприводимый многочлен степени n = 2m – 1.∗ Выберем в циклической группе ∗2 примитивный элемент ∈ 2 и рассмотрим его степени, 2 , … , 2 , где r – количество ошибок, которые надо исправить. В разложении многочлена − 1 выберем такие неприводимые многочлены, чтобы каждая изуказанных степеней была корнем одного из них (не всегда возможно).
Тогда есть результат перемножения этих многочленов; коды — коэффициенты многочленов из идеала () – исправляют r ошибок.aa. {(5) – стр. 6}Код с исправлением одной ошибки.Рассмотрим БЧХ-коды для случая поля 32 = 2 /( 3 + + 1) Таким образом, = 3, = 7. Полином 3 + + 1 является примитивным полиномом над 2 . Обозначим через ∈ 32 его произвольныйкорень. Построим код БЧХ, исправляющий не менее, чем t = 1 ошибку. Его порождающий полиномg(x) строится как минимальный многочлен для элементов , 2 . Эти элементы входят в один смежныйкласс (, 2 , 4 ). Поэтому () = () = 2 () = 3 + + 1.
В результате получаем (7; 4; 3)-код,являющийся кодом Хэмминга.bb.Код с исправлением двух ошибок.{(5) – стр. 6 внизу, лень переписывать длинные формулы}cc. Код с исправлением трех ошибокСлайд 405.Коды БЧХ: общая схема декодирования.{(5) – стр. 7}() = 1 + 1 + 2 2 + ⋯ + – полином локаторов ошибок.dd.Для принятого слова () найти все синдромы = ( ) ∀ = 1, … , 2ee.Найти полином локаторов ошибок () путем решения уравнения ()() + 2+1 () = Λ() спомощью расширенного алгоритма Евклида;ff. Найти все корни ()полным перебором; пусть найденные корни равны 1 , … , gg. Найти позиции ошибок = − mod , где = 2 − 1 – порядок примитивного элемента ;hh.Исправить ошибки ̂() = () + 1 + ⋯ + ii.
Найти все синдромы ̂(); если они не равны нулю, то выдать отказ от декодирования.Понятие действия группы на множестве, фиксатор и стабилизатор.Примеры.jj. {(1) – стр. 46}Действие группы на множестве.Действием группы G на множестве T называется гомоморфизм : → () биекций множества T(взаимно однозначных отображений множества T на себя)kk.
{(3) – слайд 465}Фиксатор.Фиксируем g, т.е. находим все элементы множества T ,которые перестановка g оставляет на месте{ ∈ |() = } = Fix() ⊆ ll. {(3) – слайд 465}Стабилизатор.Фиксируем t, т.е. находим все перестановки g, которые оставляют данный элемент неподвижным{ ∈ |() = } = Stab() ⊆ mm.ПримерыЛемма Бернсайда и её применение.nn.{(3) – слайды 461 и 467}Лемма Бернсайда. Отношение эквивалентности на T – ∼ ′ = ∃ ∈ : () = ′. Классы этой эквивалентностиназывают орбитами. Число орбит обозначается C(G). Лемма Бернсайда: ()=1||∑∈ |Fix()|oo.Применение.Лемма Бернсайда применяется для решения комбинаторных задач (определить числонеэквивалентных слов, перестановок, раскрасок) – слайды 481 и далее.Для применения универсального способа вычисления C(G) надо представить эквивалентные элементымножества как классы эквивалентности действия некоторой группы на этом множестве.Цикловой индекс действия группы.{(3) – слайд 492}Сопоставим каждой перестановке ∈ вес по правилу () = 1 1 ∙ … ∙ , где – количество цикловдлины k в перестановке (вики).
Цикловой индекс действия группы – средний вес подстановок в группе:1(: , 1 , … , ) = || ∑∈ ()Группы симметрий правильных многоугольников (диэдральныегруппы) и группы вращений правильных многогранников. Примеры.Их цикловые индексы.Теорема Редфилда-Пойа и её применение.{(3) – слайд 532}pp.К множеству T, |T| = N,группе G, |G|= n и действию G:T добавим множество = {1 , … , }меток. Дадим вес элементам R: ( ) = = ̅̅̅̅1, .qq.Теорема Редфилда-ПойаЦикловой индекс действия группы G на RT есть () = (: ) = (: , 1 , … , )| = +⋯+ 1rr.
Применяется в комбинаторных задачах для подсчета количества разметок данного типа (содержащихданное количество элементов конкретного цвета).Идеалы и фильтры частично упорядоченного множества. Конусы.Точные грани.ss. {(3) – слайд 575}Частично упорядоченное множество.Пару = < , ≤>, где P – непустое множество, а ≤ – рефлексивное, антисимметричное итранзитивное бинарное отношение на нём, называют частично упорядоченным множеством. Рефлексивность – x ≤ x Антисимметричность – ( ≤ ), ( ≤ ) ⟹ = Транзитивность – ( ≤ ), ( ≤ ) ⟹ ≤ tt. Порядковый идеал.Подмножество J элементов ч.у.
множества < , ≤> называется его (порядковым) идеалом, если( ∈ ), ( ≤ ) ⟹ ∈ uu.Порядковый фильтр.Подмножество F элементов P называется его (порядковым) фильтром, если ( ∈ ), ( ≤ ) ⟹ ∈ vv. Верхние и нижние конусы и грани.Пусть < , ≤> – ч. у. множество и ⊆ . Множества ∆ и ∇ , определяемые условиями∆ = { ∈ | ∀ ∈ : ≤ } и ∇ = { ∈ | ∀ ∈ : ≤ } называются верхним и нижним конусамимножества A, а их элементы — верхними и нижними гранями множества A соответственно.ww.Главные идеалы и фильтры.
= () – идеал, ∆ − фильтр P. Такие идеалы и фильтры называют главными.xx. Точные грани.Наименьший элемент в ∆ называется точной верхней гранью множества A (символически sup A).Наибольший элемент в ∇ называется точной нижней гранью множества A (символически inf A).Теорема Шпильрайна. Линейное продолжение частичноупорядоченного множества.yy.
{(3) – слайд 607}Теорема Шпильрайна.Любой частичный порядок ≤ может быть продолжен до линейного на том же множестве. Каждыйпорядок есть пересечение всех своих линейных продолжений (линеаризаций).zz. Линейное продолжение частично упорядоченного множества.Спектр и размерность частично упорядоченного множества.aaa.{(3) – слайд 622}Спектр частично упорядоченного множества.Spec() = {Pr[ ≤ ]|, ∈ , ≠ }, Pr(E) – вероятность E.bbb.{(3) – слайд 627}Размерность частично упорядоченного множества.Наименьшее число линейных порядков, дающих в пересечении данное ч.у. множество P называетсяего порядковой размерностью (символически dim(P)).Наименьшее число линейных порядков, таких, что P вкладывается в их декартово произведение,называется мультипликативной размерностью.Фундаментальная теорема о конечных дистрибутивных решётках.ccc.{(3) – слайд 696}Фундаментальная теорема.Всякая конечная дистрибутивная решётка L изоморфна решётке порядковых идеалов ч.у.
множестваеё неразложимых элементов: = ( )Соответствия Галуа.ddd.{(3) – слайд 715}Пусть P и Q – частично упорядоченные множества. Пара отображений (, ), : → , : → ,удовлетворяющая свойствам: , антиизотонны () ≥ , () ≥ ( и – операторы замыкания (на P и Q соответственно).называется соответствием Галуа между P и Q.Источники1.2.3.4.5.Ю. И. Журавлёв, Ю. А. Флёров, М. Н. Вялый – «Дискретный анализ.
Основы высшей алгебры»http://ru.wikipedia.org/СлайдыГ. Д. Ким – «Линейная алгебра»PA_coding_algorithms.pdf.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
