Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 147
Текст из файла (страница 147)
пространство матрицы И=(! () ~'...6" ') является кодом над полем )гч с минимальным расстоянием г! ) 3 тогда и только югда, когда НОД (т, о — 1) =- !. 9.21. Пусть и — примитивный элемент поля )Рэ с минимальным многочленом х" — - х — 1 над полем Кз. Найти порождающий многочлен БЧХ-кода над полем Кз длины 8 и размерности 4. Определить минимальное расстоннне этого кода. 9.22. Найти порождающий многочлен БЧХ-кода над полем !г"з размерности 12 с конструктивным расстоянием 5. 9.23. Определить размерность БЧХ-кода над полем Гз, исправляющего 5 ошнбок и имеющего длнну 80. 9.24.
Испрльзуя примитивный элемент п 6 й'гз с мнннмальным миогочленом сс' = из+ 1, найти порождающий многочлен бнйарного БЧХ-кода длнны 15, исправляющего 3 ошибки, 9.2$. Найти порождающий многочлен я (х) для бинарного (31, 3!— — - бей я (х))-БЧХ-кода с конструктивным расстоянием б = 9. 9.26. Пусть т и à — натуральные чнсла. Показать, что существует бинарный БЧХ-код длины 2~ — 1, который нсправлнет все комбинации по г илн менее ошнбок, используя прн этом не более чем шт контрольных снмволов. 9.27. Описать (!5, 13)-код Рида — Соломона над полем )г ы, определнв его порождающий многочлен н число ошибок, которое этот код может поправлять. 9.28. Доказать, что мннимальное расстояние кода Рида — Соломона с порождающим многочленом л — ! я(х) = П (х — сс') равно о, 9.29.
Определить, является лн БЧХ-кодом код, дуальиый произвольному БЧХ-коду. Аналогнчио является лн кодом Рида — Соломона код, дуальный произвольному коду Рида — Соломона? 9.30. В примере 9.43 найти локаторы ошибок, зная, что синдром полученного вектора равен (10010110)т. Найти порождающую матрицу этого кода. 9.31. Пусть бинарный БЧХ-код, нсправляющнй 2 ошибки, имеет длину 31 н задается корнем мзчногочлена ха+ ха+ 1 над полем Гзз.
Пусть синдром полученного слова имеет внд (1! 100!1101)". Найти многочлен ошибок. 9.32. Пусть а — примнтнвный элемент поля )гзз, аз = се+ 1, н пусть 3 (х) .= х'"+ хз+ х'+ ха+ хз+ х+ 1 — порождающий многочлен бинарного (15,5)-БЧХ-кода. Пусть получено слово т = — 000101!00100011. Определить перед~нное кодовое слово н сообщение, которое было закодировано. 9.33. Код С называется реверсивным, если нз того, что (а,, а„..., а„,) 6 С, счеЛУет, что н (аа м ..., а„а,„) Р С. Гл. 9. Приложения конечных полей (а) Доказать, что циклический код С вЂ”.= (и (х)) является реверсивным тогда ~ и только ~огда, когда обратная величина к любому корню многочлепа р (х) также '» является корнем многочлена о (х).
(6) Доказать, что произвольный циклический кол над полем К» является реверсивным, если . ! совпадает с некоторой степенью числа» по моду! лю п, 9.34. Пусть дан циклический (и, )г)-код, и пусть линейный (о — т, й — '~ — т)-код получен из него в результате вычеркивания гп последних строк и т ' последних столбцов в порождающей матрице этого кода, приведенной перед,' теоремой 11. 16. Показать, что получающийся при этом код, вообще говоря, пе „' ивляется циклическим, но имеет минимальное расстояние, не менынее, чем мннимальное расстояние исходного кода. (Зимечакие Такой (и т, й — т)-код,: называется укорочеккыл1 циклическим ходоль) 9.3о.
Перечислить все точки и прямые в РС (2, Кз) Нарисовать диаграмму,' всех пересечений. Перечислить все точки прямой Е и указать семейства парал-,' лельных прямы в Аб (2, К,) 9.36. В Рб (2, К») рассмотрим четырехвершинник А =(1, 1, ! + ()), В =;: = (О, 1, ))), С = (1, 1, ()), )) .= (1, 1+ (), ()), где Р— примитивный элемеитч поля Км Найти диагональные тачки этого четырехвершинника н проверить,! что они каллинеарны. 9.37. Доказать, что в Рб (2, К,) найдутся шесть тачек, никаиие три иэ" которых не лежат на одной прямой. Четыре из нич еовпадшот е тачками А, В, С„ и () из упр. 9.36, Найти оставшиеся две тачки 9.38. Найти уравнение киники, которая образована точками А, В, С, В:,,' из упр, 9.36 н точкой Е =- (1, ! + (), 1+ ()) Определить касательные к эта$(( панике и найти точку нх пересечения.
9.39. Поиазать, что не все касательные к невырожденнай конине в проек;„ тивном пространстве РС (2, $ а) пересекаются в одной точке 9.40. Доказать, что если й — множество таких точек пространства Рб (2, К»),'.,", что каждая прямая из Рб (2, К») содержит точку множества ь', то ! (. ! Гж д+ 1, ) причем равенство достигается тогда и только тогда, когда 1. является прямой! нашего пространства. 9,41. Доказать, чта среди любых т+ 3 точек конечной про»к»наной пло-)е скости порядка т найдутся три коллинеарные точки. (Замечание. Тем самыму будет показано, что овал в пространстве Рб (2, К») при нечетном д содержиз',~ максимальное число точек, обладающих тем свойством, что никакие три из иих,", не лежат на одной прямой,) 9А2. Показать, что если в проективном пространстве Рб (2, К»), где 4"; четно, у двух овалов баеве половины точек общие, та этн овалы совпадают.
9,43. Пусть» четно. Невырождеиная коника в Рб (2, К») вместе с точкой:; пересечения всех касательных к этой конике назывзется регулярным оои.юм., Показать, что если д = 2 нли у 4, то любой овал в Рб (2, К») является регух "1а лярным. 9.44. Пусть» = 2" и ! ( и < д Доказать, что множество А (хз") (см.',," теорему 9.67) яаляетси овалом я Рб (2, К») тогда и только тогда, иогда НОД (и, *1! й)= ! 9А6. Пусть д =- 2ь, й > 1, рассмотрим Рб (2, К») Показать, что (а) если йеи (() = — 2, то А (Д является овалом тогда и только тогда, когда А (7) = А (х»); (6) если бей (7) -= 4, то А (() является овалом тогда и только тогда, когда й '-.
нечетно и А ()) = А (х'). 9А6. Пусть А (7) такое же, как н а теореме 9,67, Тогда А ()) называется;Ф тримеляциойным »»илом, если аво является овалом, а много»лен 1' индуцирует: эидоморфиэм адднтивной группы поля К» Доказагь, ыо А (() является трансля- ", ционным овалом тогда и только то~да, когда выполняютея следующие условии: (а) 7(а+ Ь) = ) (о) ь ) (Ь) для веет о, ь с К», Упражнении (Ь) ( ЯвлЯетсЯ пеРестановочным многочленом полЯ г'е, йей (() < д и ((1) .=- 1; (с) ((к) х нвлпетсн пеРестановочным мпогочленом полЯ Гч со свободным членом, равным О. Доказать также, что если бей(() < д, то ) удовлетворяет условию (а) тогда и только тогда, когда он нвляетсп Р.миогочленом, где р— характеристика поля )Р .
9.47. Пусть д =. 2" и ! < и < Ь. Доказать, что А (хе") является трансляпиопиым овалом в РО (2, 9'ч), если НОД (и, й) = 1. 9.48. Определить число точек, прямых, плоскостей и гнперплоскостей э пространстве Рб (4, (г"з). Сколько плоскостей проходит через данную прнмую? 9.49. В РО (4, (('з) найти все З-пространства, проходящие через плоскость, определяемую точками (1, О, О, О, 0), (О, О, 1, О, 0) н (О, О, О, О, !!.
9.50. Показать, что число Ь-плоскостей проективного пространства РО (ш, г'ч), ! ( й < т, или, что то же самое, содержащихся в гл-плоскостях некоторой проективиой геометрии более высокой размерности над полем 5'е, равно (4 Ь! — 1) (9 — 1) „(д +' — 1) (4" " — !)(4' — 1) " (4 — !) 9.51. Показать, что система блоков (1, 2, 3), (1, 4, 7), (1, 5, 9), (1, 6, 8), (4, 5, 6), (2. 5, 8).
(2, б, 7), (2. 4, 9), (7, 8, 9), (3, 6, 9), (3, 4, 8), (3, 5, 7), образует блок. схему и определить параметры о, Ь, г, Ь и Х этой блок-схемы, 9.52. Решить следующий частный случай задачи Киркмана о школьницах. Учительница каждый день выводит на прогулку 9 девочек, построив их в три ряда по трн человека в каждом. Найти способ организовать прогулки таким образом, чтобы в течение четырех дней подряд ни одна из девочек не встречалась в одной тройке ни с одной своей одноклассницей более чем ! раз. 9.53. Пусть в школе, где учится Ь мальчиков, имеется ! спортивных команд но Ф человек в каждой команде.
Пусть команды организованы таким образом, что каждый мальчик входит в одинаковое число команд и каждая пара мальчиков гоже входит в оданаковое число команд. В какое число команд может при этом входить один мальчик н сколько раз два мальчика могут входить в одну команду? 9.54. Доказать, что если о четно, то дли симметричной (о, Ф, ййблок-схемы величина й — ?. является квадратом. 9.55.
Проверить, что (О, 1, 2, 3, 5, 7, 12, 13, 16! является разностным мно. жествам по модулю 19. Определить соответствующие параметры о, Ф и д. 9.58. Показать, что (О, 4, 5, 7) является разностным множеством по мо- голю 13, а связанная с этим разностным множеством проективная геометрия совпадает с РГ? (2, $'з). 9.57. Доказать следующее обобщение теоремы 9.76. Пусть (8з, ",пгь), '-= 1, ..., з, — система (о, Ф, ь)-разностных множеств.
Тогда если все вычеты по модулю о пРинять за элементы блок-схемы, то оз блоков вида (81, + 8,, с!?Ь + !), ! .= О, 1, ..., о — 1, ! — 1, " . з, ооразуют (о, й,?л)-блок-схему. 9.58. Пусть (.1ь! = (а!81), где а18! == г+ !Ь(шой 9), 0 < а)~1< 9, ! < -.. С / < 9. Какие из матриц !.1ь1, Ь = 1, 2, ..., 8, явлнются латинсннми квадра. тами? являютсн лн й'з' и (.'ь' ортогоиальнымн? 9.59. Латинский квадрат порядка и иазываетсн нормалиэовпнлым, если его ~ервый столбец н его первая строка представляют собой упорядоченное мно- Гл. 9, Приложения конечных полей жество (1, 2, ..., л).
Скольно существует различных нормализованных латинских . квадратов порядка и для каждого и ч.. 47 9.60. Пусть 8 — латинсний нвадрат порядка т, образованный элемрнтами'-' (1, 2, ..., гл), а М вЂ” латинский нвадрат порядка л, образованный элементами- (1, 2,,, л).
С помощью 8 и М построить латинский квадрат нарядна глп с эле-,' ментами из множества (1, 2,, щ) Х (1 2 и). 9.61. Построить три попарно ортогональных латинских квадрата порядка 4.:„ 9.62. Доказать, что если а -г 2, то существует не бачее чем и — ! попарно ' ортогональных латинских квадратов нарядна и.
9.63. Магический «зидраьт порядка и образуется целыми числами от 1 до пэ, записанными в виде матрицы размера и к и таким образом, что сумма элементов . по любой строке, любому столбцу и по обеим диагоналям равняется одному и тому же числу. Пусть А = (а!!) и В =- (ЬН) — два ортогональных латинских квадрата порядка а, образованнйе числами (О, 1, ..., и — 1). Пусть прн этоМ сумма элементов, стоящих по каждой из диагоналей матриц А или В, равнянзск ) и (и — 1)г2. Показать, что М =. (па!! -)- ЬЫ + 1) является магическим квадратом'' порядка и.
Построить магический квадрат порядка 4, используя два ортогональ- ! ных латинских нвадрата, полученных в упр. 9.61. 9.64. Найти матрицы Адамара порядков 8 и 12. 9.65. Показать, что если Иьт н Вн — матрицы Адамара, то существует ма-,*. трица Адамара Вь,а. 9.66. Показать, что из нормализованной матрицы Адамара порядка 4("„'" у) 2, можно построить симметричную (4! — 1, 2! — 1, ! — 1)-блан-схему. 9.67. Доказать, что граф состояний ЛМС иад полем Гч с невырождеиной"з основной характеристической матрицей представляет собой цикл без подходов,; 9.68. Поназать, что графы состояний, соответствующие подобным основньпа,, харантеристическим матрицам над полем йгг, являются изоморфными. (Замгчаняа.г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
