Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
алфавитом из 26 букв. Важный вклад в основание общей теори# линейных
кодов был сделан в работах Golay 111, Hamming Muller 111, Reed [1],
Slepian [i], 12], [3]. По поводу кратко^ истории алгебраической теории
кодирования мы отсылаем чит!^ теля к превосходному сборнику статей под
редакцией Блей Blake Ц].
Детальное изучение алгебраической теории кодирования можш найти в-книгах
Berlekamp [4], Blake, Mullm Ц], Duske, J ii sen [1], Lin [2],
MacWilliams, Sloane 12] (последняя книга сн жена обширной библиографией),
а также в книгах McEiiece [§ Peterson, Weldon [1], van Lint [i ], von
Ammon, Trondle Ii if Удалов, Супрун 11]. Некоторые книги по прикладной
алгеб также содержат материал по алгебраической теории кодиревЩ ния, см.,
иапример, книги Birkhoff, Bartee 111, Dornhoff, Но 11], Lidl, Pilz [1],
Lidl, Wiesenbauer [i 1. Обзорами по теор кодирования являются работы
Berlekamp [8], Kautz, Levitt 11 Sloane Ii] и Добрушин 111. Книги,
вышедшие под редакци^Щ Берлекэмпа (Berlekamp [9]) и Манна (Mann [5 ]),
представлязЛ^ собой интересные сборники работ по теории кодирования.
Коды Хеммиига были введены в работах Golay 11 ] и HafflMl ming [I], По
поводу различных границ для кодов см. рабаш? Hamming 11] (граница
Хэмминга), Plot kin [i] (граница Плот кина), Singleton [i 1 (граница
Сииглетона) (см. упр. 9.5), Gil bert [i], Варшамов [i ] (граница Гилберта
-Варшамова), Teof рема 9.32 была получена в работе MacWilliams П].
Приведенной нами доказательство этой теоремы заимствовано у ван Лннт#
(van Lint И ]). Другие доказательства этой теоремы можно найти в книгах
Berlekamp 14, ch. 16], МсЕНесе [6, ch. 7], а также Chang, Wolf. И ].
Аналог этого результата для нелинейных кодов приводится в работе
MacWilliams, Sloane, Goethals П L Равенство из упр. 9.19 получено в
работе Pless 11].
Широко изучались совершенные коды (см. упр. 9.8 н 9.9); Помимо двух
совершенных линейных кодов, приводимых в этих
т
т
•Ч>;Е
й.
Комментарии
655
упражнениях, существуют два совершенных линейных кода* юлученных Голеем в
работе Golay 11 j, а именно (23, 12)-код над полем F2 и (11, 6)-код над
полем F3- В работе Tietavainen [14 3 показано, что пр<щзвольный (линейный
или нелинейный)
совершенный код С s FJ или содержит только одно кодовое
слово, нли совпадает с FJ, "ли является бинарным кодом с повторением
нечетной длины, или имеет те же параметры (т. е. ллину, число кодовых
слов н минимальное расстояние), что и эдин из кодов Хэмминга или Голея
(см. также Зиновьев, Леонтьев [1 1 и Tietavainen [153). Известно, что
любой код, параметры которого совпадают с параметрами одного из кодов
Голея, сам жвивалентен соответствующему коду Голея (см. Deisart, Goet-
tals [3 3, MacWilliams, Sloane [2, ch. 201). В работах Lindstrom
1], Schonheim [21 и Васильев Ю. Л. [11 построены нелиней-iые совершенные
коды с теми же параметрами, что и у кодов Хэмминга. Прекрасные обзоры
результатов, касающихся совершенных кодов, содержатся в книгах
MacWilliams, Sloane [2, :h. 6] и в статьях van Lint [31, [41.
Взаимосвязь между теорией кодирования и комбинаторикой шособствует
развитию обеих дисциплин. Имеются многочислен*
¦ ые примеры того, как техника, разработанная для одной из этих областей,
позволяет получать результаты, применимые в другой области. Так,
например, результат, эквивалентный границе Хэмминга для кодов, был
получен Pao (Rao С. R. [13) еще задолго до зарождения кодирования в связи
с исследованием комбинаторных схем. Много интересных результатов,
связывающих теорию кодирования и комбинаторику, можно найти в работах
4ssmus, Mattson ИЗ, [23, Blake [2], Cameron, van Lint [13, [2],
MacWilliams, Sloane [2 3. Конечные геометрии использовались в работах
Rudolph ИЗ, Lin [13, Delsarte P. [13, Sachar [11 и ряде других для
построения и анализа различных кодов. Геометрия кодов подробным образом
разбирается в монографии Берлекэмпа (Berlekamp [4, ch. 15 3) и в книге
Peterson, Weldon [1, ch. 10 j.
§ 2. Циклические коды были введены в работе Prange [13. Другими ранними
работами по циклическим кодам являются статьи Abramson [1 3, Green, San
Soucie [1 3, Peterson, Brown [1 3, Prange [2], Yale [ 1J. В работе
Elspas, Short [13 изучалась связь между циклическими кодами и
каноническим разложением порождающего многочлена, а в работе Zetterberg
ill рассматривались неприводимые циклические коды.
Связь между многочленами по модулю хп - 1 и циклическими ходами длины п
исследовалась Мак-Вильямс (MacWilliams 12 3), Питерсоном и Брауном
(Peterson, Brown 111). Многочлены по модулю хп - 1 также связаны с
алгеброй циркуляитных матриц
G56 Гл. 9. Приложения конечных полей ^
а
а
ш
5/*;3
.< У* -
'Ш
• W
¦-rii
&
ш
размера пхп (см. Kariin fi 3). Связь между линейными рекур| рентными
последовательностями, регистрами сдвига и цикли*ш| скими кодами
исследовалась в работах Abramson 11], Berlekanj; " [4, ch. 5j, Green, San
Sonde П ]> Peterson, Weldon Ц, ch. &Ж Prange f2], Yale 11], Zetterberg fl
