Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 146
Текст из файла (страница 146)
также СЬПбз 111, НаП 181, Мапп 121, Кузег 1! 1, 5!гее[, %аПгз 1!1, Ча)с[а (21. Теорема 8.83 получена в работе МасЬ[е!зЬ [! ) (см. также Мапл (! 1, [2), Кузег [11). Ортогональные латинские квадраты впервые изучались Эйлером (Еи!ег [! )), который выдтинул гипотезу о том, что для и = 2 (шос[ 4) не существует пары ортогональных латинских квадратов порядка л. В работе Таггу 111 этот результат был подтвержден для случая и = 8, однако Воуз и Шрикханд (Вове, ВЬгркЬапде [2)) опровергли гипотезу Эйлера, построив пару ортогональных латинских квадратов порядка 22. Вскоре после этого Паркер (Раг[сег [! 1) нашел пару ортогональных латинских квадратов порядка !О.
И наконец, в работе Вове, БЬНЬЬапбе, Раг[сег [11 показано, что для любого и > 8 существует пара ортогональных латинских квадратов порядка л. С этой тематикой связаны также работы Вове, 8Ьг!ЬЛапде 13) и Раг!сег [21. В статьях Вове К. С. П[, 5[ечепз %. [.. [11 показано, что конечная проективная плоскость порядка и существует тогда и только тогда, когда существует множество из л — 1 попарно ортогональных латинских квадратов порядка и. Необходимо отметить, что множество, состоящее из взаимно ортогональных латинских квадратов порядка л, не может содержать более а — 1 квадратов. Вопросы применения схем инцидентностн и ортогональных латинских квадратов при планировании статистических экспериментов обсуждаются в работах Мапп [21, КадЬачагао (! 1, Ча)ба 121.
Оригинальный подход к вопросам планирования экспериментов можно найти в книге Р!зЬег Н 1. Матрицы Адамара исследуются во многих книгах по комбинаторике (см., например, НаП !81, чап 1.!п[ 12)). При этом используются разные методы их построения (см. Вапшег[, НаП [11, ЕЛ!!сЛ [! 1, Ра[еу (31, %аПпь 5[тес[, %аП!з [! 1). Вопросы использования матриц Адамара в теории кодирования изучались в работах Вове, БЬгПсЬапде [11, Оо)ошЬ, Вапшег! [!1, Мас%!П!ашз, 16» Гл, 9.
Прнложення конечных полей Ыоапе 11, сЛ 2!. В последней книге также содержится обзор' их применения в других областях математики. Матрицы сходны]г типов изучались в работах Ве[ечс!сЛ [11, Вц!зоп [1], Ре!заг[е4) бое!Ла!з, 5еЫе! 1! ), Сое!Ла!з, 5еЫе! [11, Мас%И[!апсз (4)'„'"~ %а!Из, Ыгее(, %аИ(з (11. я $ б. Прекрасными источниками сведений по системам с конеч-") ным числом состояний (или просто конечным автоматам) и линей''й иым модулярным системам являются книги АгЬсЬ, Еа!Ь, Ка!псагтя.
1! ], Воой [11, РогпЛоИ, НоЛп 11, сЛ. 1, 81, СсИ! 111, 12), Наг):;,у пзоп (11, Хас[еЛ, Резоег [1), Хас[еЛ, Ро1ай [1, сЛ. 2), В последней!::)с книге содержится много ссылок на работы по линейным модуляр-.:д иым системам. Некоторые классические работы по данной тема-'й тике собраны в сборнике под редакцией Каутца (Кап1х [1)~~ (см. также СгоччеИ [1], Е[зраз [11, Рг!есйапс( [! 1, НцИспап [! ))'„:4 Условия, при которых конечный автомат можно реализовать в вид()'-, линейной модулярной системы, изучались в работах Е!сЛпег [1 и НагИсе[, Махаон [! 1, а также в ряде других работ. В стать~ МаИцй, СИ! (1) показано, как линейную модулярную системф'"; иад кольцом 7/(т) можно разложить на линейные модулярнм~'. системы над конечными полями. Линейные модулнрные система!':;" над кольцами 7с (лс) изучались также в работе ВоИпсап [2К''-' Калман (Ка1гпап 111, 12!) изучал линейные модулярные снсте с точки зрения динамических систем.
За детальным обсуждеии свойств рациональных канонических форм матриц отсылаем к р ботам РогпЛоИ, НоЛп 11, сЛ. 7] и Негз1е[п (4, сЛ. 6 Л Кратко упомянем некоторые другие приложения конечн полей. На арифметике конечных полей может быть основан т ретический анализ переключательных цепей (см.
Сгееп, Тау (11, [31, Мо!сб! 11 1 — [41, Мо[зИ, Ророч[с[ 111, Мцгайап ', Йе 111, Кш1еапц [11, ЧаЫа 111). Конечные поля используются п вычислении переключательных функций (см. Веп]ац!Лг!1, гСееФ4)~ (! 1, 121, Рач[о, РезсЛаспрен ТЛауье 111, 1.аЬцпес, 5!1пИсоч [! 1,;, Ргас1Лап [11, Та[саЛазЛ( [1], ТЛаузе [1), Ъ'!п 111) и обгцих логиче ских функций (см. Кагрочз[су [1!). Мендельсон (Мепс(е!зоЛп [2]г'; использовал конечные поля для моделирования квазигрупповых,' тождеств, Свойства конечных полей находят разнообразные прин менения в криптографии (см. Ве[сег, Р[рег (! ], (2]„Вгахч[еу, 1.еч!пе [! 1, Соорег 1! ], РИИе, НеИспап [1], Наг!хо[а, меч[не 111, Нег!ез!апс,,)оЛаппеззоп 111, НегьЛеу (1], КопЬе[пс [! 1, Кг!з Лпапшгйу, КаспасЛапс(гап [11, [.еч[пе, Вгачс!еу [1), [21, 1.еч[пе, ' Наг!хч(й 111, РоЛИд, НеИвап (! ), Ыоапе (21).
В статье йеб[пЬо [! 1 изучались приложения конечных полей к исследованию ма- . тричных процессоров, в работе [х!сЛо!зоп [1] они применялись при вычислении конечных преобразований Фурье, а в работ~ ЕпдИзЛ (11 свойства конечных полей применялись к анализу алгоритмов. Упражнения 661 [В работах Тх[азшап, Ч!а«[п!х, 2!п]«[1*1, Цфасман )1'1 и Влэдуц, Кацман, Цфасман [1*1, основанных на идее работы Гоппы !21 н оценках рациональных точек на кривых большого рода над конечным полем (см. Манин 15), 1Ьага [1)), были получены новые результаты, относящиеся к теории кодирования.
В работах Шпарлинского 12* 1, 15* 1 предложен одни комбинаториый метод, который применяется к некоторым задачам теории кодирования. По тематике девятой главы имеются также работы: «]е Чгое«[! )]э), Не[[еэе!Ь [1*1, [.!41, )ч!ег[егге!(ег [1э), ОЬегх(, [)цг [1"), Тарре [1*), Варшамов, Тененгольц [1*), Вишневский [1*), !2'), Гоппа [1*], [2*), Думер, Зиновьев [1*] и Сидельников )1*1, )2*]. — Перев.) Упражнения 9.1, Найти все кодовые слова, определить минимальное расстояние и найти проверочную матрицу бинарного линейного (5,3)-кода, задаваемого порожда ющей матрицей 9.2. Доказать, что линейный код может обнаруживать з или меньшее число ошибок тогда и только тогда, когда его минимальное расстояние л' ~ з+ 1.
9.6. Доказать, что расстояние Хэннинга является метрикой в простран. стае Гл. 9.4. Пусть Н вЂ” проверочная матрица некоторого линейного кода, Доказать, что код имеет минимальное расстояние и' тогда и только тогда, когда любые 6 — 1 столбцов матрицы Н линейно независимы и при этом имеется л' линейно зависимых столбцов.
9.6. Доказать, что если линейный (л, А).код имеет минимальное расстояние л, то л — А+ 1 'э д (граница Сингл«тона). 9.6. Пусть ох — порождающая матрица линейного (л,, А).кода с минимальным расстоянием бь а о« вЂ” порождающая матрица линейного (лэ, й)-кода с минимальным расстоянием 6«. Показать, что линейные коды с порождающими матрицами (' ~~) (а, б,) являются (л,+ лх, 26)-кодом н (л, + лэ, А)-кодом с минимальнымн расстояниями ппп (0х, Из) и г( > 6«+ 0з соответственно, 9.7. Пусть даны натуральные числа А и л. Доказать, что если бинарный линейный (л, А)-код имеет минимальное расстояние л = ле, то л х л + Лх+ " + Ль-х где ог~, = [(6! + 1)!2], 1 = 6, 1, ..., й — 2. Здесь [ л ] обозначает наибольшее целое число, ие превосходящее х. 9.6.
Код С Ы ]Г'" называется совершеллыл, если для некоторого целого — е числа г шары В«(с) радиуса ! с центром в кодовых словах с попарно не пересекаются н «заполняютэ все пространство Ц, т, е. [] В,(С) =(Г,". сбс Гл. 9. Приложения конечных полей 662 Доказать, что в бинарном случае коды Хзмминга н коды с повторением нечетной,.
длины являются сонершенными кодами. 9.9. Пользуясь определением нз упр. 9,8, показать, что все коды Хэмминга ., над полем !!гг являются совершеннымн. 9.10. Два линейных (л, я)-кода с, и с, иад полем Рч называютсн эквива-' лентными, если кодовые слова кода С, можно получить из кодовых слов кода С„ с помощью некоторой фиксированной перестановки координат в словах из кода С,. Пусть 6 — порождающая матрица линейного кода С. Показать, что любая пере... становка строк матрицы 6 или любая перестановка столбцов этой матрицы при.', водит к горождающей матрице некоторого линейного кода, эквивалентного ',, коду С.
9.!!. Используи определение эквивалентности кодов из упр. 9.10, по,, казать, что бинарные линейные коды с порождающими матрицами 6т = 0 1 1 1 и 6э = 0 ! 1 1 являются эквивалентнымн. 9.12. пусть с — линейный (л, я)-код. доказать, что размерность с рава~~ л — й. 9.! 3. Доказать, что для любого линейного кода С выполняется соотношенйй;; (Сь)х = С. 9.14. Доказать, что для любых линейных кодов С, и С иад полем г14)9 имеющих одинаковую длину, справедливо соотношение(С, + Сз)~ = Сь ПСэь,' 9.15. Пусть С вЂ” бинарный (л, 1)-код с повторением. Доказать, что код ннляегся (и, л — 1)-кодом с проверкой на четность. ,й 9.19. Найти порождающую матрицу и нсе кодовые слова (7,3)-кода, дуал ' ного к бинарному коду Хзммннга С,, 9.!7. Определить дуэльный код С~ для кода, определенного в упр.
9.! ' Получить таблицу смежных классов пространства й"~~ по модулю С, найти лидш ров смежных классов и соответствующие синдромы. Если полученное слова( имеет вид у = О!001, то какой вид должно, по всей веронтности, было имат)(г" переданное сообщениеэ 9.!9. Применяя теорему 9.32 к бинарному линейному коду С =- (000, 011"„ 101, 1!0), найти его дуальный код и нумераторы весов, а также проверить тФ,.' ждество Мак. Вильямс. ' Й 9.19. Пусть С вЂ” бинарный линейный (л, й)-код с нумератором весов л А (х, у) = ~" Агх!у" г=а и пусть Ах (х, у) = Х А1-хгул — 1 г=-а — нумератор дуального кода С .
Показать, что для и = О, 1, ... справедливо следующее равенство: и л и ь г(л — !) 663 Упражнения ~де 1=- е — числа Стнрлннга второго рода, а бниомиальный коэффнцнент ( й ) полагается равным 0 для Ь > гл н А с. О, Выписать в явном виде полученные тождества для г =: О, 1, 2. 9.20. Пусть л:.— (йм — 1)l(д — 1), а () — примитивный корень «.й степени нз единицы в поле Г м, т > 2. Доказать, что нуль.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
