Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
а | С |/| D |
::: | С/D \ вытекает, что |jD|-~ Подсчитывая сумму весов
кодовых слов нз С, получаем, что она не превышает величины
тФ] {q 1). Минимальное расстояние а€ кода С' равняется
м пни м а: I ь н о м у в ее у н е и у левого с л о в а и, с л ед о в а те
л ь н о, до л. ж н о у до в л ет в о р я т ь до к а з ыв а е м о м у н
еравенств у, так как. общее число кодовых слов ненулевого веса равно Д -
- 1, fj
(г р а и и ца Варта м ов а Г и л бе р т а). Если вып о л ¦ пня
неравенство
ТО>?(Д% ТО
;= 0
то мидсяпвует линейный (а, к)-код над полем F,- с минимальным par стояние
м. не меньшим нем д.
Д < жазат ел ь с ты к До к а ж е м чту те о р е м у пут е м построения
проверочной (п - к) х л-матрицы Я искомого кода. В качестве первого
столбца матрицы Н выберем произвольный набор длины
ч - к элементов поля Fq. В качестве второго столбца возьмем
любой набор той же длины элементов Fq, подчиненный единственному условию,
чтобы оп не равнялся произведению первого столбца нм элемент поля |б.,
Вообще предположим, что выбрано J - I столбцов, причем любые d - ! пз них
являются линейно ^зависимыми. Тогда имеется пе более
Й--Д
о
Экторов, которые являются линейными комбинациями не более
Ч(:'м Т - 2 векторов из числа выбранных j - I вектор-столбцов.
"ч л и выполняется неравенство, при веденное в условии теоремы, 10 ми ж
но выбрать /~й столбец таким образом, чтобы он был лн-веюю независимым от
любых d - 2 столбцов из числа первых 1 столбцов. Указанное построение
можно проделать таким
598
Гл. 9. Приложения конечных полей
--у-ч"-г>^аи
¦-y-L У---------¦-¦-
образом, что ранг матрицы И будет равен п - /г. По лемме 9.§( полученный
в результате иод будет иметь минимальное paccToj ние, не меньше чем d.
Для данного линейного кода С можно ввести понятие дуал| ного кода. Пусть
даны кодовые слова u ::= (щ, ,,,, ид), v = ид,.
,vn\ у Fe. Тогда нх скалярное произведение и v он редел "
равенством и v ахи} Т ... 1- ипип. Если u v 0, то словах
ц v называются ортогональными,
9.28. Определение. Пусть С - линейный (п, А)-код над
Т огд а соответствуют!! й ду ал ь н ы й (и л и о ртого нальны
л ем
ч
код С1 определяется как
: <$.
С
1
!u G1F
Я
U
' ! .
Мы знаем, что код С является 6-мерным подпространство!
д-мерного пространства f>; размерность же подпространства равна а -¦ k.
Код С1 является линейным (д, п - 6)-кодом. Н| трудно показать, что его
порождающей матрицей будет матрщ| Н - проверочная матрица кода С.
Соответственно проверочна матрицей кода С1 является матрица G -
порождающая матриц кода С.
Важную информацию о коде можно полудить, изучая в| кодовых слов. Так,
например, при определении вероятное^ ошибки декодировании нли при
исследовании некоторых алгр ритмов декодирования важно знать
распределение весов кодов слов. Существует фундаментальная связь между
распределен и весов в линейном коде и в его дуальном коде, которая
устаиавли вается в теореме 9,32.
9.29. Определение. Пусть A-t обозначает число кодовых сЛ<| с б С веса ц
где 0 <; г -С п. Тогда многочлен
П
А (х, у)
V А.^-<
( ч
ip#
от двух переменных х и у над полем комплексных чисел паз! вается
нумератором весов нлн весовой функцией кода С.
Далее нам понадобится понятие характера конечного поЛЦ (см. гл. 5).
9.30. Определение. Пусть у - нетривиальный аддитивный х| р а к те р и о л
я Т я, и п у ст ь u v о боз чача ет с к а л я р н ое н р он я в е д е к;
векторов и, v б FJ. Для фиксированного v ? определю
отображение /v' ? ? -+¦ С равенством
§ 1, Линейные коды 592
WMMwiv' Ч 1 'iT *i I h 11 '¦ ьи
. MUM'"---
' ....... 1 и"! ¦ ¦ 11 т ТЫУ 11' ¦ 1*-1- |- [ifj s
Вели V - векторное пространство над полем С комплексных чисел а f ¦-
отображение из IFJ в V, то определим отображение gr iff1 1/ равенством
?7(") = Е Xv(u)f(v), u?
v€f;
9.3!. Лемма. Пусть E - подпространство пространства ггП
\
§.<
Я
- его ортогональное, дополнение, /: !Fq В - отображенш
из векторного пространства f J е векторное пространство V нас полем СЕ й
% - нетривиальный аддитивный характер поля fq.
Тогда
S gf (u) - I ? I ? f{v).
и d В v ? Е ^
Доказательство t
? "МИ) -= ? ? Xv (и) f (V) =s ? ? х (V - И) / (V) -
,,?я u€fi V-6F'1 v€fJ"^E
= 1Е | S f (v) -1 S. ? ? XC)/(v).
vt;T-! v ^ Е -Г г В Ц $ и В В
V . и - с
Для фиксированного v §* Е1 отображение и ? Е v и является нетривиальным
линейным функционалом на Е. Тогда, используя фор м у л у (5,9), п ол у ч
а ем
Д S1 (") = I ? I У ПИ + Jf1 2 /К) 2 х(Я =
u{y ? v ?: #
= |?| ^ / (v),
v 6
Применим теперь эту лемму в случае, когда V - пространство комплексных
многочленов от двух переменных х, yt а отображение f определяется по
формуле / (v) - хП iv)yn~~w (vy где
ж (у) обозначает вес вектора v ? F?.
412. Теорема (тождество Мак-Внльямс). Пусть С ¦ линей-И-ый (п, k)-Kod над
полем Fq, а С1 -- его дуальный код. Если А (х, весовая функция кода С,
а А 1 (х, у) -весовая функция кода
А1 (ху у) - <г*А [у - х, у -f (q - 1)х).
Доказательство. Пусть /: FJ С 1х, у] - определенное выше отображение;
