Лекции по прикладной алгебре. v2.0 (1127112), страница 18
Текст из файла (страница 18)
. . , 4, где α —примитивный элемент поля F2 [x]/(x4 + x + 1).Требуется найти полином локаторов ошибок σ(x) дляпринятого полиномаw(x) = x14 + x10 + x5 + x4 .Прикладная алгебраКоды, исправляющие ошибкиЗадачи237 / 432Задача (ТК-4)Рассмотрим код БЧХ с нулями αi , i = 1, . . . , 4, где α —примитивный элемент поля F2 [x]/(x4 + x + 1).Требуется найти полином локаторов ошибок σ(x) дляпринятого полиномаw(x) = x14 + x10 + x5 + x4 .РешениеДля удобства вычислений в поле F42 построим таблицусоответствий между степенным и полиномиальнымпредставлением элементов поля.Прикладная алгебраКоды, исправляющие ошибкиЗадачи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Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 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.239 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиРешение (продолжение 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)Рассмотрим код БЧХ, нули которого определяются степенямиα, где α — примитивный элемент поля F2 [x]/(x4 + x + 1).Пусть для некоторого принятого слова w(x) полином локаторовошибок σ(x) = α2 x2 + α6 x + 1.Требуется определить позиции ошибок в w(x).242 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачиЗадача (ТК-5)Рассмотрим код БЧХ, нули которого определяются степенямиα, где α — примитивный элемент поля F2 [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) являетсяполиномом над полем F42 .
Поэтому здесь не выполняетсясвойство σ(α2 ) = (σ(α))2 .244 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачи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) являетсяполиномом над полем F42 .
Поэтому здесь не выполняетсясвойство σ(α2 ) = (σ(α))2 .Обратные элементы для обнаруженных корней α5 и α8 равны,соответственно, α10 и α7 . Отсюда получаем, что полиномошибокe(x) = x10 + x7 .Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды245 / 432Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств246 / 432Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать247 / 432Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьЗадачи построения кодов, исправляющих ошибки.Основные понятия метрики на единичном кубе.Групповые коды: определения, свойства.
Кодовоерасстояние. Построение кода как задача плотной упаковки.Теорема Хэмминга. Пример построения кода Хэмминга.Циклические коды: определение, построение идекодирование.Коды БЧХ как частный случай циклических кодов. Идеяпостроения кода БЧХ и оценка его кодового расстояния.Коды БЧХ: алгоритмы кодирования и декодирования.248 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды249 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств250 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать251 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множестве252 / 432Действие группы на множестве: два определенияГруппа G = h G, ◦, e i, |G| = n.Множество T , |T | = N .Bij(T ) — множество всех биекций на T.Symm(T ) — симметрическая группа множества T :Symm(T ) = h Bij(T ), ∗, 1T i ,Прикладная алгебраТеория перечисления ПойаДействие группы на множестве252 / 432Действие группы на множестве: два определенияГруппа G = h G, ◦, e i, |G| = n.Множество T , |T | = N .Bij(T ) — множество всех биекций на T.Symm(T ) — симметрическая группа множества T :Symm(T ) = h Bij(T ), ∗, 1T i ,Определение (1)α ∈ Hom ( G, Symm(T ) ).Действие α группыGна множестве T : символически —G α: T .Прикладная алгебраТеория перечисления ПойаДействие группы на множестве253 / 432Действие группы на множестве: два определения...Определение (2)α = h G, T ; ◦, ∗, e, 1T i ,где◦G × G → G — групповая операция;∗G × T → T — новая операция.Аксиомы для операций:e ∗ t = t;(g ◦ h) ∗ t = h ∗ (g ∗ t).Запись операции ∗: g(t) = t 0 .Аксиомы: e(t) = t и (g ◦ h)(t) = h(g(t)).Т.е.
g — перестановки на T , обладающие вышеуказаннымисвойствами.Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРис. 2. K определению действия группы на множестве254 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеДля данной перестановки g:Введём отношение эквивалентности ∼g на T —deft ∼g t 0 = ∃ k g k (t) = t 0 .Классы эквивалентности называют g-циклами. Всего C(g)циклов (классов эквивалентности).Количества циклов длины 1, 2, . .
. , N обозначаютν1 , ν2 , . . . , νN или ν1 (g), ν2 (g), . . . , νN (g).255 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множестве255 / 432Для данной перестановки g:Введём отношение эквивалентности ∼g на T —deft ∼g t 0 = ∃ k g k (t) = t 0 .Классы эквивалентности называют g-циклами. Всего C(g)циклов (классов эквивалентности).Количества циклов длины 1, 2, . . . , N обозначаютν1 , ν2 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
