Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 144
Текст из файла (страница 144)
дующий результат позволяет решить поставленную задачу. 9.96. Теорема. Пусть р (х) — нормированный неприводи многочлен над полем Кч, дей (р (х)) = д, и пусть Г» = огг) (р (х)")га Тогда цикловая сумма матрицы М (р (х)') определяется формула(тл (1 1)," ( ~ !1) !'( г 12!+ ''' + ( г ~(ч)4~ й В итоге мы получили следующий алгоритм для определени ' цикловой суммы ЛМС ий'над полем Кч с невырожденной основн ' характеристической матрицей А: ,.4 С1. Найти элементарные делители матрицы А; пусть это б,",' дут многочлены у, (х), ..., у (х). С2.
Пусть йц (х) = ); (х) ', где ~; (х) — нормированный приводимый многочлен над полем Кч. Найти порядки г(0 ",, = огд (Л (х)). СЗ. Для 1=: 1, 2, ..., ш и й — - 1, 2, ..., т; найти порядк 4п =- огд(), (х)"), воспользовавшись формулой 4о =- 4пр.ь где р — характеристика поля Гч, а с» — наименьшее целое числ(йч такое, что р'» ) Ь (см. теорему 3.6). С4. Пользуясь теоремой 9,96, найти цикловые суммы Зг' для матриц М (йц (х)), ! = 1, 2, ..., ш. С5. Тогда цикловая сумма Х системы й'задается формулами!~' 21~2 " 2Ю. 9.9Т.
Пример. Г!усть основная характеристическая ма'-' трица ЛМС .«т над полем 1Г» имеет вид 1О 0 1 0 О! 1 0 1 0 0 А= 0 0 0 0 0 ! 0 О О 1 1 Комментарии В этом случае Э(х) — х +ха+х+1=(х+1)', ?,(х)=- +1 т,==3, ~ (х) — х +х+! Выполнив шаги С2 н СЗ, получаем то' -- 1, 1!," =- 2, ~.','' — 4, — 3.
Тогда по теореме 9.96 Х, = (1, 1) + (1, 1) + (1, 2) + (1, 4) =-- = — (2, 1) -! (1, 2) + (1, 4), Ха =- (1, 1) + (1, 3? и, следовательно, — л а~а =- [(2, 1) .); (1, 2) -~- (1„4) 1 [(1, 1) [- (1, 3) [ =-. -- (2, 1) + (1, 2) -'Е (2 3) 4- (1, 4) -1- (1,'6) -1- (1, 12) Таким образом, граф состояний ЛМС .Х содержит два цикла длины 1, один цикл длины 2, два цикла длины 3 и по одному циклу длин 4, 6 и 12. П Из шага С5 можно получить, что порядки состояний ЛМС л задаются формулой НОКер[а",, ф ..., [а ') для всех возможных комбинаций целочисленных значений пара- метров й,, ..., й„, О < й; < то Если мы хотим найти все возмож- ные значения порядков состояний системыМ, не вычисляя пред- варительно ее цикловую сумму, то можно воспользоваться сле- дующей теоремой.
9.98. Теорема. Лусть я — 7МС с невырожденной основной характеристической матрицей А. Пусть минимальный многочлен матрицы А имеет каноническое разложение т (х) = р, (х) ' ". р, (х) ', и пусть тац' = огй (рт (х)"). Тогда значения порядков состояний системы лТ вЂ” зто все целые числа вида НОК(1~",, 1,",!, ..., 6",'), где 0.<йз <Ьз 1.</~<с Комментарии 5 1. Теорема Шеннона, о которой говорится во введении к настоящей главе, была получена в работе Впаппоп [11 (см.
также Вйаппоп, %еауег [1[). Эта работа знаменует начало теории информации как математической дисциплины. Доказательства этой теоремы Шеннона, а также обоснования теории информации 654 Гл. й, Приложения коленных полей можно найти в книгах АЬгатзоп 121, Анй [11, Оц!а4ц 1! ) (в по.р следией приводится подробная библиография по теории инфор.- мации), а также в монографиях МсЕВесе 161 и %о[!оеч1!х [! ).: Теория кодирования с точки зрения информации изучается в ра. ботах Ва!а1егЬЬпап [!1, Оа!!адег (1), !пас!з [11, !.цс[еу, 5а[х,, %е!доп [11, МсЕ!!есе [6], 5!ер[ап 141.
Первый нетривиальный пример кода, исправляющего ошибки,.:,' иад конечным полем появляется в фундаментальной работе Шен.', нона (5Ьаппоп 1! 1). Этот код называется теперь (7, 4)-кодом„, Хэмминга, и его построение приписывается Хэммингу (см. Наш.й) 1п!пд [1 1). Ранее в работе Рг!едшап, МепдеЬоЬп 11] изучалнсй;~ коды длины 5 с минимальным расстоянием не меньше чем 2 иад,',, ллфавитом из 26 букв. Важный вклад в основание общей теоривз, линейных кодов был сделан в работах Оо!ау 111, Нашш!пд [1],!, Мц[!ег [11, [(еее[ [! 1, 5[ер!ап 11), [2), [31. По поводу краткой;, истории алгебраической теории кодирования мы отсылаем чита[у геля к превосходному сборнику статей под редакцией Блейки)' В!а[ее [! 1.
Детальное изучение алгебраической теории кодирования можне)" найти в книгах Вег[ейашр [41, В!айе, Мцйп [11, 0цз]ее, Зйгиепйн: эеп [! ], 11п [21, Масеч'!1!!ашз, 5!оапе [21 (последняя книга сн жена обширной библиографией), а также в книгах МсЕ[!есе [6 Ре1егэоп, Юе!доп [1], чап ]!п! 111, чоп Апипоп, Тгопе[[е Ц, и Удалов, Супруи [! 1. Некоторые книги по прикладной алгеб'" также содержат материал по алгебраической теории кодировв ' пия, см., например, книги В!г[еЬо!1, Ваг1ее [11, 0огпЬо!1, Но' 1!1, ! !61, Р!1г [11, $.161, ЪЧ!езепЬацег [11. Обзорами по теорие кодирования являются работы Вег!ейашр [8), Кап[к, Ееч|!! 11,. Ыоапе [1! и Добрушин 111. Книги, вышедшие под редакцивф' Берлекэмпа (Вег!е[сатр [91) и Манна (Мапп [51), представляийФ';:. собой интересные сборники работ по теории кодирования. Коды Хемминга были введены в работах Оо!ау [11 и Нашнгр гп!пд 1! 1.
По поводу различных границ для кодов см. работы' Нашш!пи [11 (граница Хзмминга), Р!о![е!п 111 (граница Плотд[ кина), 5!пи!е!оп 111 (граиица Сияглетоиа) (см. упр. 9.5), б!!':";, Ьег! [11, Варшамов [11 (граница Гилберта — Варшамова). Тео ' ), рема 9,32 была получена в работе Мас1лг!1!1атз [! 1. Приведеннов '.'! нами доказательство этой теоремы заимствовано у ван Лиитв,''" (чап Е!п! 1! 1). Другие доказательства этой теоремы можно найти в книгах Вег[е[еашр [4, сЬ. 161, МсЕ!!есе [6, сЬ. 71, а также „.' СЬапц, ЪЧо[1 [! ].
Аналог этого результата для нелинейных ко- ' дов приводится в работе Мас%!!!!ашз, 5[папе, СоерпаЬ 11),' Равенство из упр. 9.!9 получено в работе Р!езз 1! 1. Широко изучались совершенные коды (см. упр, 9.8 и 9.9). Помимо двух совершенных линейных кодов, приводимых в этих: Коммеитарии пражненнях, существуют два совершенных линейных кода, юлученных Голеем в работе Со(ау !1), а нменно (23, 12)-код пад полем Га н (11, 6)-код над полем [Га. В работе Т1е1ата!пеп [!4] показано, что прчнзвольный (линейный нлн нелинейный) совершенный код С ~ [Га нлн содержит только одно кодовое лоно, нлн совпадает с Г",, нлн является бинарным кодом с по~горением нечетной длины, нлн имеет те же параметры (т.
е ,лину, число кодовых слов н минимальное расстояние), что н ~дни нз кодов Хэммннга нлн Голея (см. также Зиновьев, Леон;ьев П ] н Т!е1ата!пеп П5!). Известно, что любой код, параметры аоторого совпадают с параметрами одного нз кодов Голеи, сам ~квнвалентен соответствующему коду Голея (см. (аеЬаг1, бое1- а!з (31, Мас%!!!!ашз, 5!папе [2, сЬ. 201). В работах 11пбз1гбш 1], БсЬбпЛе]ш [2] н Васильев Ю.
Л. П1 построены нелнней~ые совершенные коды с теми же параметрами, что н у кодов Хэммннга. Прекрасные обзоры результатов, касающихся совер.пенных кодов, содержатся в книгах Мас%!1!!ашз, Яоапе 12, Ь. 61 н в статьях чап 1!п( 131, !4 ). Взаимосвязь между теорией кодирования н комбннаторнкой пособствует развптню обеих дисциплин. Имеются многочисленые примеры того, как техника, разработанная для одной нз этих областей, позволяет получать результаты, применимые в другой области. Так, например, результат, эквивалентный границе Хэммннга для кодов, был получен Рао (йао С. й.
П 1) еще задолго до зарождения кодирования в связи с исследованием комннаторных схем. Много интересных результатов, связывающих .еорню кодирования н комбннаторнку, можно найти в работах Аэзшпз, Ма1Ьоп П), [2], В!а[ге [2), Сашегоп, тап (.[п1 П1, [2), Маг%!!1[вша, 5[оапе [21.
Конечные геометрии нспользовалнсь в работах йцдо[рЬ П ), 1[п П ), (ЗеЬаг1е Р. П ), Басйаг П) н ряде других для построения н анализа различных кодов. Геометрия кодов подробным образом разбирается в монографии Берлекэмпа (Вег!екатр [4, сЬ. 15]) н в книге Ре1егзоп, Же(- ;1оп П, сЬ. 10]. $2. Циклические коды были введены в работе Ргапяе П ]. Другнмн ранними работами по цнклнческнм кодам являются статьи АЬгашзоп П ], бгееп, Бап Бопс!е П 1, Ре1егзоп, Вгоч'и П ], Ргапке (2], Уа(е П ]. В работе Е!зраз, Яюг1 П ] изучалась связь между цнклнческнмн кодами н каноннческнм разложением порожзающего многочлена, а а работе Ее11егЬегд [! ) рассматривались ~епрнводнмые циклические коды. Связь между многочленамн по модулю ки — 1 н цнклнческнмн иодамн длины а исследовалась Мак-Внльямс (Мас%1!!(ашз 121), Пнтерсоном н Брауном (Ре1егзоп, Вговп П 1).
Многочлены по ~одулю к" — 1 также связаны с алгеброй цнркулянтных матриц Гл. й. Приложения конечных полей размера пхп (см. Каг1]п [11). Связь между линейными рекур рентными последовательностями, регистрами сдвига и циклич:, скими кодами исследовалась в работах АЬгашзоп [11, Вег(е(еаш [4, сЬ. 5), Огееп, Бап Боцс]е 111, Ре1егзоп, Же!доп [!, сЬ. 8:.
Ргапде [21, Уа(е 1! ], Хе11егЬегн [! 1, 21ег!ег !51. Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды) были вве-' дены в работах НосццепйЬеш !1], Вохе, Рау-СЬаце(Лцг] [11 длн бинарного случая и в работе Оогепз1е(п, Бег!ег [11 для случая,. произвольного конечного поля. Питерсон показал (см. Ре1егзоп', !! 1), что БЧХ.коды являются циклическими кодами. Другими ос-, новополагающими работами по БЧХ-кодам являются статьи „ Вохе, Рау-СЬацг(Лиг[ (2) и Ма[(ноп, Бо[ошоп [! 1. Обобщения тео-, „ ремы 9.45 можно найти в работе Наг1тапп, Тхепн [! 1, Результаты, о минимальном расстоянии и распределении весов и БЧХ-кодах х можно найти в работах Вег!ейатр (5), Оо[с1тап, К1]шап, Бшо(а,! [!1, МасЖ]11]ашз, Ыоапе [2, сЬ. 91, Ре!егзоп [21 и Ре1егзоп, ', Ъ'е!боп [1, сЬ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
