Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 133
Текст из файла (страница 133)
В качестве второго столбца возьмем и ьб й иабор той же длины элементов Гч, подчииеииый единюж виолу условпкь !Тобы ои ие равиялся ироизведеиию первого г" .ии,л пв элемепт поля Кч. Вообще предположим, что вьпбрвио толбцов, причем л~обые ь! — 1 из иих являются линейно ие ищщ имыып, Тогда имеется ие более ь хи')и~в, которые яВляются лппейиыми комбииациями ис" более 1И,, -- '2 векторов пз числа выбранных ) — 1 вектор-столбэцов. ' ьи выполняется неравенство, приведенное в условии теоремы, " м~окио выбрать !хй столбец таким образом. чтобы ои был ли"'' н~ независимым от любых д — 2 столбцов из числа первых столбцов, Указаииое построение можно проделать таким Гл. 9.
Прнложепил копечныл полей ввв образом, что ранг матрицы Н будет равен л — )е. По лемме 9 г полученный в результате код будет иметь минимальное рассто иие, ие меньше чем Ь(. Для данного лииейножз кода С" можно ввести иопятие дуал ного кода. Пусть даны кодовые слова и (и,, ..., и„), ч = (и„;. ..., Ол) С К,",. ТогДа их скаллРн 5в лРшьзввденив и ч оиРеДел ' равенством и ч и1155 ~ ..
' илол, Если и ч О, то слова ' и ч иазывак5тся орт55аоцальаыиа. 9.28. Оиределеиие. Пусть С вЂ” лииейпый (л, lг)-код иад и 5!ем Го. Тогда соотВетстВующий дральмьеа' (или 55/7л50бональны код С вЂ” ' Оиреде1яется как С:-.= (иге 'е')и У вЂ” 0 для всех чс С), Мы зиаем, что код С является )г-мерным иодиростраиство л-мерио1о пространства )5,; размерность же иодиространства С равна и — /г. Код С ° является линейным (а, и -- й)-кс5дом. Н трудио показать, что его порождающей матрицей будет матри Н вЂ” - ироверочиая матрица кода С.
Соответственно проверочи матрицей кода С' является матри1га Π— порождающая матри кода С. Важную информацию о коде можно получить, изучая в кодовых слов. Так, например, ири определении вероятное ошибки декодироваиия или ири исс.1едоваиии некоторых алг ритмов декодирования важно звать распределение весов кодов слов. Существует фундаментальная связь между распределеии весов в линейном коде и в его дуальиом коде, которая устаиавл вается в теореме 9.32. 9.29.
Определение. Пусть Л; обозиачает число кодовых сл, с Е С веса С где и:,' 1' =-. и. Тогда многочлеи Л (л, р) -= 2 Лот'уп о от двух иеремеиных .с и у иад нолем комплексных чисел иаз нзется нулевратором вссов или ввс5лк5й функцией кода С. Далее иам понадобится понятие характера коиечиого иол (см. гл. 5). 9.30. Определение. Пусть у — иетривиальиый адд11тивиый х РактеР полЯ (Ге, и пУсть и У обозначает скалЯРное иРоизвеДеи ВектоРОВ и, У ~ ге.
Для фиксиРОВаииОГО У ~ ге Оийедели отображение 2,: К„- С равенством у.(и) =- 2(у и), и~1„". й К Линейные коды 11гли у -- векторное пространство над полем С комплексных чисел, отображение из Ц в )г, то определим отображение а~ Г равенством уг(")-. Е ~.(п)Р(»), иЕ1г'„', о 1,31. Лемма. Пусть Š— надпространства пространства (г сео орли сональное дополнение, г': Г~ -«1' — отобраясенш и нз мытарного пространства ~Т« в вскгпорное пространство )г нас я, и ч С, и у — негпривиальный аддитивный характер поля го '~'о, ди Е уг(п) =!Е! Е Р(»). 6е «Ге — ' П кпзательсгнво, з' У1«)=- Х .й' х.(п)1'()= 2 Е х(» «)Р(»)=- « ' «бе сел ,сап «Ее ==-~Е~ Х П)-1 Е Х Е у.(с)1(»). «сг~ «Фе' '611««се ««=с Для фиксированного» Ф Е' отображение и ~ Е».п является пс.пиапальиым линейным функцисшалом на Е. Тогда, используя ф:~рмулу (5.9), получаем а;(и)::-.
) Е/ ~~1, 1(») + — ' ~~1, 1(») ~~1„Х(с) =-. «в с «еез Фе~ с 11'я = ~Е~,1, 0») П «еез 11рименим теперь зту лемму в случае, когда Р— простран- «1по комплексных многочлепов от двух переменных х, у, а ото- бражение ( определяется по формуле ~ (») -- х ~«~у" — ~«~, где и (»1 обозначает вес вектора» Е Ц. 9.32.
Теорема (тождество Мак-)зильямс). Пусть С -- линей- ный (и, й)-код над полем Г„а Сг — его дуальный код. Если А (х, У) весовая фунщия кода С, а А ' (х, у) — весовая функиия кода то Аз(х, у) =д — 'А(у — х, у+(д- 1)х). Показательство. Пусть 1: К» — ~ г: !х, у! — определенное выше отображение; тогда весовую функцию кода Сз можно предстази' ь в виде А'(х у) = К 1(»)- «С се Гл. В. Приложения конечных полей Пусть аг — отображение, заданное выше (см. определение 9.30)' для о ~ (гч положим 1, если очаО, О, если о =- О.
Тогда для и =- (иь ..., а„) б К получаем йо(и) = ~л 3(ч и)х«ч«>дл-нч«> = «Г е, Е Х(неох + -г инин) 'л Е д « .Х! "|Р' ' !ен!и( ! "1!)'''' '( !ен!)— — П [3(и,о,)х!"'!у' !'*'!1=- «« "'«нЕ$'е Л П ~ (3(и;о!х1 « ~у' — г е ~1, '= ' «Еуе В случае когда и~ -— — О, справедливо равенство у (иго) =- у, (О) —: 1, а следовательно, соответствующий сомиожитель в последне ' произведении равен (д — 1) х ',- и.
Прп и; чь 0 соответствующи сомножитель равняется у+ х Е Х (о) =- у — х. «с т' Таким образом, йг(ц) =(у — х) '"'(у ' (д — 1)х)" "'"'. Из леммы 9.31 следует, что »С(Аз (х, у) =- »С! ~' )(ч) = ~' уз(и) =. А(у — х, у+(д — 1)х) «6сх нас И наконец, ! С! =- де по условию теоремы. Тем самым теорема доказана. (:».
9.33. Следствие. В весовых функциях А (х, у) и А' (х, у, положим х -- г, у =- !. Полученные при мпом многочлены обозна чим через А (г) и Ах (г) соответственно. Тогда тождество Мак Виль.чмс можно записать в виде Ал(г)==-д «(! ! (д -1) )" А( +, ). 9,34. Пример. Пусть С вЂ” бинарный код Хэммиига длииЫ и = 2 — 1 и размерности и — т над Ге. Порождающей матри-', цей его дуального кода С' является проверочная матрица Н: 2. Цкклкческке коды ОО! Эга матрица состоит вз всех возможных ненулевых столбцов длины т над полем Гг.
Код С~ состоит из цулевого век,о;л и 2" — 1 векторов веса 2"' — '. Таким образом, весовая функввл кода С„ равняется у" ~ (2"' — 1)х"к 'уг"' 1)ы теореме 9.32 весовая функция кола С„, определяется формулой 1 А1х, у) == — —,, ((у '- х)" ! п(у — х)<" е'ггк(у ~ х)1" лпк). !1,гг: Л (г) — Л (г, 1), т. е. А (г) — ~~Агг'.
Тогда нетрудно Гг а вр жсритгь что А (г) удовлетворяет дифференциальному уравнению (1 -- е )- 1 ' (1 ь их).4 (7) .==- (1,' е)" к лА (г) с ввчггльным условием А (0) . Л, = 1. Зто эквивалентно соотш юсин~о С4 = ( ) — .4; „-(а — гл-2).4; и г== 2. 3,, Гц в,гчальными условиямн Л„.= 1, Л, — О. 'г) $ 2. Циклические коды 1(иклнческие коды — это особая разновидность линейных к Шов, они отличаются достаточно хорошо изученной математичегкой структурой и удивительно просты в реализации, 9.35. Определение.
Линейный (п, )г)-код С над полем )Гч вазывается циклическим, если из того, что вектор (а„а„..., а„,) врвпадлежит С, следует, что его циклический сдвиг (а... ак, ... и„,) принадлежит С. '. настовщего момента мы будем предполагать, что НОД (и, Ч) 1. Обозначим через (х" — 1) идеал кольца ~ (х), порождепвыи многочленом х" — 1 ~ Гч (х).
Тогда все элементы факторкгс ьца ~ч!х)/(х" — 1) можно пРедставлить многочлепами степени, меньшей чем л. Очевидно, что это факторкольцо изоморфио как векторное пространство над полем К,, а изоморфизм гик ет вид ап 1)- ~ силу существования указанного изоморфизма мы будем пред. сгавлвть элементы Кч 1х))(хк — 1) или в виде миогочленов стеменыпей чем и, которые рассматриваются по модулю -- '., или в виде векторов или слов над полем !)'л.
Умножение 602 Гл. 9. Приложения конечных полей многочленов по модулю хп — 1 мы определяем обычным образо если 1Е Е, !х!1(хп — !1, уы уи Е ')а !х), то (бух - 1 означаеФ что а,ил = ) (апой (хп — 1)). Циклический (л, й)-код С можно получить путем умножени.' каждого сообщения, содержащего Ф информационных символ (и которое мы отождествляем с многочленом стецсни, меньше чем й), на фиксированный многочлен у(х) степени н — и, г ' д (х) является делителем хп — !. лйпогочлены у (х), ха (х),,г ..., хл — 'д (х) соответствуют кодовым словам кода С.
1!орождающа матрица кода С имеет внд 'ао ах . Ип л О уп йх 0 0 0 0 О О О к~п-л О дп где д (х) — Уп + 1ххх —,' ...! ди лхп — ". Очевидно, что стРоки м трицы 6 линейно независимы, и, таким образом, ранг матрицы равен 1г' — размерности кода С. Если й(х) .. (хп — 1)1а(х) -=-. й,' ,л, (х) -,' -1- йлх', то матрица 0 0 0 0 Н вЂ”-- йь йо О О йл йл, О йл йл 0 "л "л-г является ироверочной матрицей кода С. Код с порождающ матрицей Н, т, е, код, дуальный к коду С, ~анже является цикл ческим кодом.
Так как мы отождествляем векторы (а,, а„..., а„,) над ц лем гч и многочлены а, з а,х -,'— ... + а,хч — ' над тем же и лем, то код С можно рассматривать как подмножество факто' кольца Г !х !1(х" — 1). 9.36. Теорема. Линейныи код С является циклическим тог и только тогда, когда он будет идеалом кольца Е (х)1(хп — ) Доказательство. Если С является идеалом и (а„, а„..., ап т)„ Е С, то и х (аь ц а,х -~п,'- ап,хч -') = (оп,, а„..., а„а) Е С. Обратно, если из того, что (а,, а,, ..., а„,) Е С, следует, что (а„„а,,, а„,) Р С, то для любого многочлена а (х) е многочлен х а (х) также принадлежит С, а следовательно, х'а (х) с С, хча (х) Р С и т. д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
