Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 32
Текст из файла (страница 32)
. , ik . Будем искать такойu ∈ F k , что ϕ(u)i1 = 1, ϕ(u)i2 = 0, . . . , ϕ(u)ik = 0. Получаемсистему линейных уравнений, матрица которой невырождена.Значит, решение u этой системы существует. Тогда ϕ(u) и естьискомое кодовое слово с k − 1 нулями.Мы доказали, что d 6 n − (k − 1) = n − k + 1.Как следует из теоремы 4.17, на кодах Рида – Соломонаграница Синглтона достигается, т. е. неравенство в ней обращается в равенство. В этом смысле коды Рида – Соломонаоптимальны.
Однако с точки зрения оценки в теореме Хэмминга дело обстоит иначе.Пример 4.19. Пусть n = 4 (т. е. мы берем значения многочленов в четырех точках поля), g = 1. Код образуют значениялинейных многочленов, кодовое расстояние 3, т. е. код исправляет одну ошибку. Напишем границу Хэмминга для таких параметров:q4q426q6.1 + 4(q − 1)n + 6(q − 1)21 + 4(q − 1)При больших q число кодовых слов в коде Рида – Соломонаближе к нижней границе, чем к верхней.Пример 4.20. Пусть n = q (т. е. мы берем значения многочленов во всех точках поля), g = 1. Код образуют значениялинейных многочленов, кодовое расстояние q − 1.
Так как2(q − 3)/2 + 1 6 q − 1 < 2(q − 1)/2 + 1,186Глава 4.Коды, исправляющие ошибкитакой код исправляет (q − 3)/2 ошибок. Напишем оценки изтеоремы Хэмминга для этих значений параметров:qnqn26q6Pq−3.P(q−3)/2i n(q − 1)i nii=0 (q − 1) ii=0При больших q нижняя оценка близка к константе(1 − 2.5e−1 )−1 ≈ 12.5,мощность кода намного больше. Но мощность кода намногоменьше верхней оценки из теоремы Хэмминга.
Покажем, чтоотношение q 2 к верхней оценке в теореме Хэмминга стремитсяк 0 при q → ∞. Имеем(q−3)/2 qq< q 2−q q(q − 1)(q−3)/2<i(q − 3)/2i=0(q−3)/213−q+(q−3)/2<q1−2q < 8q −(q−3)/2 4(q−3)/2 =q (q−3)/24=8→ 0.qq 2−qX(q − 1)i4.7. Коды Рида – МаллераПриведем еще одну оценку для кодового расстояния.Теорема 4.21 (граница Плоткина).
Кодовое расстояние dлюбого q-ичного кода длины n, содержащего q k кодовых слов,удовлетворяет неравенствуd6nq k (q − 1).(q k − 1)q(4.8)Доказательство. Минимальное расстояние между кодовыми словами не превосходит среднего расстояния:X1d6 k kρ(x, y).q (q − 1)x6=y∈CОценим, какой вклад в сумму вносит каждая позиция в кодовом слове. Для этого нужно оценить количество пар слов,различающихся в позиции i.
Обозначим через F множество4.7.187Коды Рида – Маллерасимволов кода, а для каждого i через fa,i — количество кодовыхв позиции i стоит a ∈ F . Тогда ясно, чтоP слов, у которыхka∈F fa,i = q , а количество пар слов, различающихся в i-йпозиции, равно!2XXXX22fa,i= q 2k −fa,i.fa,i fb,i =fa,i −a6=b∈Fa∈Fa∈Fa∈FПри заданной сумме чисел сумма квадратов этих чисел достигает минимума, когда все числа равны. Поэтому вклад каждойпозиции не превосходит k 2qq 2kq−1= q 2k −= q 2k= q 2k−1 (q − 1).q 2k − q ·qqqОтсюда получаем искомую оценкуd61q k (q k − 1)· nq 2k−1 (q − 1) =nq k−1 (q − 1)nq k (q − 1)=.qk − 1(q k − 1)qЕсли q является степенью простого числа, граница Плоткина достигается на кодах Рида – Маллера первого порядка.Возьмем n = q m − 1. Тогда слову длины n можно однозначносопоставить функцию F m \ {0} → F .
Код Рида – Маллерапервого порядка образуют такие слова, которым соответствуют линейные однородные функции и 0. Количество кодовыхслов также равно q m (линейная однородная функция задаетсяm коэффициентами). Поскольку любая отличная от 0 линейная однородная функция принимает нулевое значение ровнов q m−1 точках, кодовое расстояние для кода Рида – Маллерапервого порядка равно d = q m − q m−1 . Граница Плоткина вэтом случае имеет вид(q m − 1)q m (q − 1)= q m − q m−1 .(q m − 1)qОтветы, указания, решения1.1.
Ответ: да. Указание: результат операции ∗ — этообратное к сумме обратных111= + .x∗yx y1.2. Ответ: операция x ∗ y = (1 + 2xy)(x + y) на множествецелых чисел Z.1.4. Докажем, что всякий правый обратный является левым обратным: возьмем равенство x−1 ·x·x−1 = x−1 , умножимего справа на (x−1 )−1 , получаем x−1 · x = e.Докажем, что всякая правая единица является левой единицей: ex = xx−1 x = xe = x.Теперь легко проверяется единственность единицы и обратного.Пусть e, e′ — две единицы. Тогда e = e · e′ = e′ .Пусть xy = xz = e.
Поскольку y, z являются также левымиобратными, имеем: y = ye = yxz = ez = z.1.5. 1) да; 2) да; 3) да; 4) да; 5) нет; 6) нет; 7) нет; 8) да;9) нет; 10) да; 11) да; 12) нет; 13) да; 14) да; 15) да; 16) да;17) нет; 18) да; 19) нет; 20) да; 21) да; 22) да; 23) да; 24) да;25) нет 26) да; 27) да; 28) да; 29) да; 30) да; 31) да; 32) нет;33) нет; 34) да; 35) нет; 36) да; 37) нет; 38) да.1.9.
Прямое вычисление:ab = aeb = a(ab)2 b = a(abab)b = a2 bab2 = ba.1.10. Указание. Первый способ: показать, что |a| = 1 длялюбого a из данной группы G порядка n. При n > 1 взять вG элемент b = cos(ψ) + i sin(ψ) с наименьшим положительнымаргументом ψ и проверить, что G = {1, b, b2, . . . , bn−1 }.189Ответы, указания, решенияВторой способ: пользуясь теоремой Лагранжа, показать,что an = 1 для любого a ∈ G.1.11. а) Одна группа — циклическая группа третьего порядка с элементами {e, a, a2 } и таблицейeaa2a2e .aaa2eВ представлении перестановками можно положить:e = (1)(2)(3), a = (123), a2 = (132)(e — единица).Доказательство единственности см. на с. 15.б) Существуют две группы порядка 4.
По теореме Лагранжа порядки элементов должны делить 4.Первая возможность: существует элемент порядка 4. Этоциклическая группа четвертого порядка с элементами {e, a,a2 , a3 } и таблицейeaa2a3aa2a3ea2a3eaa3e.aa2В представлении перестановками можно положить:e = (1)(2)(3)(4), a = (1234), a2 = (13)(24), a3 = (1432)(e — единица.)Вторая возможность: все неединичные элементы имеют порядок 2. Поэтому группа коммутативна (задача 1.9). Есливзять любые два неединичных элемента a, b, то четвертый элемент будет их произведением: c = ab. По этим данным таблицаумножения восстанавливается однозначно:e aa eb abab bbabeaabb.ae190Ответы, указания, решенияВ представлении перестановками можно положить:e = (1)(2)(3)(4), a = (12)(34), b = (13)(24), c = (14)(23).(e — единица).Эта группа называется четверно́й группой Клейна V .в) Существуют две группы порядка 6: циклическая группаC6 и группа перестановок трех элементов S3 .1.13.
а) Указание. Проверить равенство (1i) ◦ (1j) ◦ (1i) == (ij).б) Указание. Проверить, что произведение двух транспозиций следующим образом выражается через тройные циклы:(ik) ◦ (ij) = (ijk),(ij) ◦ (kl) = (ilk) ◦ (ijk).в) Решение. Пусть G — подгруппа знакопеременной группыAn , порожденная множеством указанных тройных циклов, и i,j, k — различные числа, большие двух (при n = 3 утверждениеочевидно, а при n = 4 данное ниже доказательство упрощается).
Вместе с циклом (12i) группа G содержит обратныйэлемент (i21), поэтому G содержит(j21) ◦ (12i) ◦ (12j) = (1ij),(12j) ◦ (i21) ◦ (j21) = (2ij).При n = 4 группа G уже содержит все тройные циклы. Приn > 4 она содержит(k21) ◦ (1ij) ◦ (12k) = (ijk).Значит, G содержит все тройные циклы и по пункту б) совпадает с An .1.14. Ответ: 2.При > 3 группа Sn не коммутативна и потому не является циклической. Осталось указать два элемента, порождающих Sn . Докажем, что a = (01) и b = (012 . . . (n − 1)) порождают всю группу перестановок (здесь удобно занумероватьэлементы множества числами от 0 до n − 1). Поскольку Snпорождается транспозициями (см. пример 1.39 на с.
39), длядоказательства достаточно выразить любую транспозицию через a и b.Сначала рассмотрим транспозиции соседних элементов(i (i + 1)). Так как перестановка bk переводит i в (i + k) mod n,191Ответы, указания, решениядля перестановки bi ab−i получаем:b−ibiai−7 −→ 0 −7→ 1 −7 → i + 1,b−iabii+1−7 −→ 1 −7→ 0 −7 → i,b−iabiесли k 6= i, i + 1, то k −7 −→ k − i −7→ k − i −7 → k.Значит, (i (i + 1)) = bi ab−i .Чтобы выразить любую транспозицию через транспозициисоседних, нужно индуктивно применять равенство(ik) = (jk) ◦ (ij) ◦ (jk).Предположим, что все транспозиции вида (i (i + j)) выражаются через транспозиции соседних при j < k. Тогда имеемвыражение(i (i + k) = ((k − 1) k) ◦ (i (k − 1)) ◦ ((k − 1) k)для транспозиции (i (i + k), откуда по индукции заключаем,что всякая транспозиция выражается через транспозиции соседних.1.19.
а) Рассмотрим подгруппу H порядка d = n/k, порожденную элементом ak . Она содержит e, ak , a2k , . . . , a(d−1)k .Если (as )d = e, то sd кратно n, а s кратно k. Поэтому порядки подгрупп, порожденных элементами G \ H, отличаютсяот d. Но всякая подгруппа циклической группы — циклическая(теорема 1.27 на с. 30).
Значит, H — единственная подгруппапорядка d.б) Следует из а): любой элемент порядка d группы G порождает подгруппу порядка d, которая совпадает с H.1.23. Указание а) Рассмотреть (ab)pr и (ab)ps , где p — порядок ab. б) Рассмотреть (ab)p , где p — порядок ab, и показать,что ap = b−p = e.Пример 1. Для элементов a 6= e, b = a−1 условие (1◦ )выполнено, а (2◦ ) — нет. Утверждение б) не выполнено, таккак порядки a и b равны между собой и не равны единице, апорядок ab = e равен единице.Пример 2.
Элементы a = (12)(3), b = (123) симметрическойгруппы S3 имеют взаимно простые порядки 2 и 3. Условие(1◦ ) не выполнено, так как ab = (23), ba = (13), а условие192Ответы, указания, решения(2◦ ) выполнено. Утверждение б) не выполнено: a порядка 2,b порядка 3, ab порядка 2.в) Обе части равенства ak = bn возвести в степень s, равную порядку b.г) Пример 3. В циклической группе C8 с порождающим aэлементы a, a3 , a5 имеют порядок 8, но aa3 = a4 порядка 2,aa5 = a6 порядка 4.1.26. Обозначим через ϕ(n) количество порождающих элементов циклической группы Cn . (Это число совпадает с функцией Эйлера — количеством натуральных чисел, меньших n ивзаимно простых с n. Впрочем, этот факт в решении никак неиспользуется.)Каждый элемент a ∈ Cn порождает подгруппу hai порядкаd(a). В циклической группе есть ровно одна подгруппа порядка d (задача 1.19), поэтомуXn=ϕ(d)(∗)d|n(слева — все элементы группы, а справа — они же, но разбитыена множества порождающих элементов подгрупп).Рассмотрим элемент порядка d.
Он порождает подгруппу порядка d, элементы которой дают d решений уравненияxd = e. Других решений по условию быть не может (по теоремеЛагранжа d делит порядок группы). Значит, для любого делителя d порядка группы n либо вообще нет элементов порядка d,либо есть ровно ϕ(d) элементов порядка d. Первый случайневозможен, так как иначе нарушилось бы равенство (∗). Поэтому в группе есть элементы порядка d для любого делителя n, в том числе и для самого n. Но это и означает, чтогруппа — циклическая.1.27.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
