Доказательство. Пусть q р% п = {q - l)/(g - 1) пусть а - примитивный элемент поля GF (д"*) и у = oi"- Тогда у - примитивный корень степени g - 1 из единицы. Каждый нену-i левой элемент поля GF (д™) может быть однозначно записан в видв ау для некоторых i и /, О < i < «, О < / < д". Так как у - при- митивный элемент поля GF (д), то каждое i-мерное линейное под GF (д™) над GF (д) имеет вид 5 = О U {ау" /1 . ., g - 2}, где А - некоторое подмножество мно-i .,«-!}. Если \S\ = q\ то 5\0 = g»-

1) = 2 Проекцией множества S называете*

множество Р = {«Ч t g Л} элементов поля. Множество Р называете* t-мерным проективным подпространством пространства GF (д™) нг GF (д), если оно является проекцией (i + 1)-мерного линейног подпространства в GF (д™) над GF (д). В частности, если О / <; raj то а есть 0-мерное проективное подпространство. Множеству

пространство в А, к = 0, 1, жества {О, 1, .

М I = (д* -1)/(д

а""} является (п - 1)-мерным проективным под!

пространством.

Так как пересечение двух линейных подпространств - линейнс подпространство, то пересечение проективных подпространств также проективное подпространство. Так как любое i-мерное лине! ное подпространство содержится в (д™" - 1)/(д - 1) различны (i -j- 1)-мерных линейных подпространствах, то и любое (i - 1) мерное проективное подпространство содержится в (д™" -)/{я - различных i-мерных проективных подпространствах.

Декодер для ПГ-кода вычисляет проверки для символов, cooi ветствующих любому i-мерному проективному подпространству. Есл полученное слово содержит не более (д™~)/2 (д - 1) ошибочных ci волов, то декодер может определить проверки над любым (i- 1) мерным проективным подпространством. Они соответствуют разлш ным i-мерным проективным подпространствам, пересекающимс только по этому (i - 1)-мерному подпространству. После этого npi нимается пороговое решение по известным (д"""* -- 1) различ ным проверкам. Полагая i = т - г - 1 и используя индукци< по г и лемму 15.541, отсюда получим доказательство теоремы 15.54.

15.541. Лемма. Любой р-ичный ПГ-ко5 порядка {г, s) с блок вой длиной п = (д™ -1)/(д - 1) = (р™ -1)/(р- 1) удовлетворяеп проверочному уравнению на каждом (т - 1 - г)-мерном проекть ном подпространстве из GF (д™) над GF (д).

Доказательство. Достаточно показать, что характеру стическая функция любого (т - г - 1)-мерного проективного по пространства поля GF (д™) над GF (д) представляет собой кодовс слово кода, дуального к ПГ-коду порядка (г, s). Пусть Р - множес во элементов поля, лежащих в (т - г - 1)-мерном проективнс

подпространстве пространства GF (д™) над GF (д), и пусть S есть (т - г)-мерное линейное подпространство в GF (д™) над GF (д),

проекцией которого является Р. Пусть Cf -характеристическая функция Р:

Аналогично пусть С* (х) - характеристическая функция S\0 {S с исключенной точкой 0):

С(х)= 2 =сК

, г,

aes\o

Согласно теореме 15.329, С* (х) - кодовое слово циклического кода с. блоковой длиной д™ - 1, порождающие корни которого содержат а для всех тех /, для которых О < (/) < г (д - 1). Отсюда следует, что если Wq (j) г (g - 1), то

0 = С\а)= 2 I.

les\o

Если /=i(g-1)г, то получаем

О = У, * = 2

3-1) i

= у,

.£S а, ri£P

aeOF (9)\0

2 =(?-i)2ri-=- 2 --cia"-).

a, ЦР

aeGF(q)\0

Мы показали, что для характеристической функции С** (х) (т-г- - 1)-мерного проективного подпространства Р из GF (д") над GF (д) выполняется равенство =0, если ([g-l]i) < г (д-1);

следовательно, С (х) - кодовое слово кода, дуального к ПГ-коду порядка (г, s). щ

15.55. Пример. Рассмотрим двоичный ПГ-код порядка (1, 2) с блоковой длиной 21, для которого р = 2, 8 = 2, g = 4, т = 3, " = (4-1)/(4-1). Пусть д - примитивный элемент поля GF (4), я - корень примитивного кубического многочлена х + х + дх + над G/" (4). Минимальный многочлен элемента а над С/" (2) равен Л/(1) (х) = (х + х+ дх+ д) (х + х+ дх + д)=х + х + 1. -Минимальный ц1ногочлен элемента а* равен М() (х) = х" + х* + г х + X + 1; минимальный многочлен для а равен Л/С) (х) = = х + х + I. Числами вида 3f (mod 63), для которых (3i) > 3, являются (по основанию 4) 033, 124, 222 и их циклические сдвиги. Двоичная система записи дает 001111, 011011, 011110, 101010

и их двукратные сдвиги. Таким образом, для двоичного ПГ-код порядка (1,2) имеем g (х) = М" (х) М (х) М {х)=-{х + 1) {х + х + x + x-l-l) {x + xA-i) я h{x) = M(x)M(x)M{x)l = (х + l)/g (х) = 1 + х + х + х + а;". Каждый непулевой эле мент поля GF (4*) может быть записан в виде а= Аа + Bia +Cj где Ai, Bi, Ci e GF (4). Для i = 0, 1, 2, . . ., 20 получаем

i 0 1 2 3 4 5 ti 7 8 9 10 11 12 13 H 15 16 17 18 19 2G

4; 0011 52 50105 1 д 1

Bi 0 I 0 д 1 д i i д д- 0

С; 1 О О 52 52 5 1 О 52 О 1 1

1 д

52 52

д2 ffi о О О 52 52 5 15 5 5 0

Множество элементов вида Ва + С, где В, С GF (4), образуе двумерное линейное подпространство пространства GF (4) на GF (4). Проекция этого подпространства является одномерным нре ективным подпространством Р = {а°, а, а, а*, а), характери стическая функция которого задается равенством С* {х) = i -\- х

х*" + х + х = {i + X 3? + х"" + х) h {х-) Так как мне гочлен С() {х) кратен h {х), то код удовлетворяет проверочном уравнению на одномерном проективном пространстве Р.

Применимость процедуры порогового декодирования к ЕГ- и ПГ кодам определяется только тем, что эти коды удовлетворяют прове рочным уравнениям на всех аффинных или проективных подпрс странствах данной размерности. Известны и другие коды, такж удовлетворяющие проверочным уравнениям на всех аффинных ил1 проективных подпространствах, однако, как показали Делзарт Гёталс и Мак-Вильямс [1968], любой такой код - подкод либ( ЕГ-кода, либо ПГ-кода, определенных согласно 15.51 и 15.53.

Исторически характеристическая функция проективного про странства Р раньше чаще обозначалась через 9 (а;), а не через С {х)\ Этот многочлен обладает рядом интересных свойств, что показывае следующая теорема:

15.56. Теорема. Пусть Р - одномерное проективное под\ пространство в GF {q™) над GF (q), и пусть Р содержит точку а"! Пусть п = (д™-1)/(д- 1) и Q (х) = x. Тогда над полем рацио-*.

нальных чисел

е ()е (х-1) q + 1 + lix) (mod - 1), где I (х) - сумма g (д + 1) различных ненулевых степеней х. Доказательство.

е (:г) е (:г-1) = 2ж-*е(.г).

По модулю а;" - 1 каждый из многочленов Э {х), ж"Э {х), хЩ [х),... является характеристической функцией некоторого одномерного проективного подпространства из GF (д") над GF (q). Так как пересечение любых двух одномерных проективных подпространств обра-,;уот нульмерное проективное подпространство, состоящее из одной ючки, то а:Э (х) и (х) mod (а:" - 1) (исключая с.лучай i s / mod п) имеют пе более одного общего члена. Если а\ (] Р, то х" - единственный общий член многочленов xQ {х) и х~ Q (х). щ

15.561. Следствие. В предположениях теоремы 15,56 при

1)! = 3

е {х) е (х-1) = g + 1 + 2 mod (х" - 1).

Доказательство. При n = (дЗ 1)/(д 1) = gr j.

1 существует точно g (д + 1) различных ненулевых степеней X mod (V -1). I

Сопоставим проективному подпространству Р пространства CF (д™) над GF (д) множество D целых чисел mod п с помощью следующего правила:

(15.562)

dD тогда и только тогда, когда аР.

Так как Q(x)= 2 то

в{х)в{х-)== 2 S х-"-

Таким образом, согласно следствию 15.561, для одномерного иро-рктивного подпространства Р пространства GF (д) над GF [q) разности g (д -f 1) различно упорядоченных пар элементов из D должны пробегать все ненулевые числа по mod (g + g + 1) точно один раз. В силу последнего свойства D называют простым совершенным разностным множеством по mod (g + g + 1). Если q - степень простого числа, то простое совершенное разностное множество по Hiod (g2 -f g -j- 1) может быть построено no одномерному проективному подпространству в GF (q) над GF (д) в соответствии с определением (15.562). Разностные множества этого типа впервые изучались опнгером [1938] с несколько иной точки зрения. Удивительно, что ишгеровские разностные множества включают в себя все известные простые совершенные разностные множества. Эванс и Манн [1951] 1нлчазали, что рри Z) 1 600 все совершенные разностные множества являются зингеровскими, однако, пока что никому не удалось Доказать (или опровергнуть), что для некоторых больших значений д, но являющихся степенью простого числа, не существует простых совершенных разностных множеств по mod (g + g -Ь !)•

В силу взаимосвязи с простыми совершенными разностными мне жествами р-ичные ПГ-коды порядка (1, s) с блоковой длиной п = (jtj3s i)/(jrjS - называются разностными кодами. Так же, кг и все ПГ-коды порядка (1, s), разностные коды ортогонализируел в один шаг, а множество проверок, ортогональных на данном симвс ле, получается с помош,ью циклического сдвига единственного прс верочного порождающего многочлена Э {х).

Многие ЕГ- и ПГ-коды являются собственными подкодами БЧХ кодов с той же блоковой длиной и тем же конструктивным расстояш ем. В общем случае большинство ЕГ- и ПГ-кодов содержит меньше число информационных символов, чем сравнимые БЧХ-коды. Эт потеря в скорости передачи информации является той ценой, кот рую приходится платить за преимущества порогового декодирова пия. К счастью, при малых блоковых длинах эта цена не очень велика Все двоичные ЕГ- и ПГ-коды с длинами 32 совпадают с БЧХ-кода ми. Велдон [1968 Ь] построил следующую таблицу для сравнение 1-укороченных ЕГ-кодов длины 63 с соответствующими БЧХ-кодам1

Информационные символы

Проверочные сиМ волы

ЕГ- и ПГ-коды ухудшаются с ростом блоковой длины гораз;] скорее, чем БЧХ-коды. Подсчет числа информационных символе в ЕГ- и ПГ-кодах в общем случае чрезвычайно труден. Мы остано вимся только на двух частных случаях, представляющих наибольш! практический интерес: на классе ПГ-кодов, содержащем разностнь коды, и на классе ортогонализируемых в один шаг ЕГ-кодов. (Ei один класс ЕГ-кодов рассматривается в задаче 15.8.) Для определе яия числа информационных символов в этих кодах необходимо преж де доказать некоторые свойства весовых функций. В некоторых слз чаях нам придется различать Wp (х) - сумму цифр р-ичного пред ставления числа х ж Wq (х) - сумму цифр д-ичного представлег этого числа.

Для доказательства теорем 15.58 и 15.599 необходимы тольк леммы 15.571 - 15.573. Остальные леммы включены потому, что

доказательства оказываются полезными для вычисления числа информационных символов в некоторых ЕГ- и ПГ-кодах высокого порядка.

15.571. Лемма. Если q = р% О / < sm, О < х < g - 1 I Lpj определены условиями О LPJ < 9™ - 1 и Lpj = хр mod (g™ - 1), то Wq (Upj) = Wq [xp).

ms- I

Доказательство. Пусть x = 2 0<Хг<р. Тогда

t = 0

ms-i ms-i-i ms-1

,г/У = S Xip = 2 Xip + g™ 2 /p+-™% так что

i=0 i=0 t=ms-j

ms -3-1 ms-1

"V;(Uyj)= 2 2 ;/"=",(V).

i=ms - j

15.572. Лемма. Если q = p\ 0</<s и

m-ls-l

= S S Xfipq, 0<Z,,z<p,

1=0 h=0

-i-i

(V)= 2.n"""+ S Пр

fe=S-3

ft=0

где Уа= 2

m-i s-1

Доказательство. Имеем V == 2 S гр"У++

/=0 fe=s-i

m-ls-j-1 m-l s-l

-f 2 2 Xft.p+-V, так что wq{xp)- 2 2 A,,,p"+- +

=0 fe=0 1=0 h=s-j

m-is -j-1

S 2 KiP"- ,

1=0 k=0

15.573. Лемма.

u>„

(x) = X mod (g - 1).

Доказательство. Так как g = 1 mod (g - 1) для всех i, TO 2 - 2 Xiq\ Щ

15.574. Л e m m a. Справедливо неравенство Wq [x) x, причем равенство достигается тогда и только тогда, когда х < д.