(11.644) со (z) - а (z) = 5 (z) о (z).

Согласно уравнению (10.12),

co(z)-a(z)=SzXiy, П (1-ад. i ]ф1

Очевидно, коэффициент при z в этом многочлене равен ХгГг П {-Х) = ±{\\Х)Шг)=0,

i ]ф1 3 i

так как Yi = 0 для каждого слова 1-удлиненного кода. Следов тельно,

(11.645) deg[(o(z)-a(z)]<g-l.

Если К<-1, то w{K)<:k(q - l), так что g(а«) = О и 5к = < Следовательно, 5 (z) = О mod z-i , и из уравнений (11.64 и (11.645) вытекает, что

Если Sk i - 0, то получаем нулевое кодовое слово. Если S k i то положим

(11.646) T{z)

Тогда уравнение (11.644) запишется в виде

Т (Z) о (Z) = 1,

откуда Оо = 1 и

(11.647)

ог = - 2 1-{з для i = 1, 2, ... .

Если K,<z,2(f, то 5к= О, за исключением случая w (К) к (q - 1), который возможен тогда и только тогда, когда К = 2q - \ - q для некоторого /. В силу (11.646), отсюда следуе что Tj = О, за исключением случая j = ф - q. Поэтому для i -i равенство (11.647) можно заменить равенством

(11.648)

Ог=- J,Oi-{q-q)Tk i.

Если / - наибольшее число, не являющееся степенью q, для кот рого а1 .фО, то, согласно (11.648), существуют такие чис / < А - 1 и г А, что q - i = ф - (1, или / = д- -- -

За исключением случаев / = О или д% это число отрицательно. Поэтому, если / Ф q% то ok j = 0. Таким образом, а (z) - аффинный многочлен, и, согласно теореме 11.32, его корни образуют аффинное подпространство.

Доказательство утверждения 11.642. Пусть t 4) кодовое слово веса q. Согласно теореме 11.641, локаторы ненулевых позиций слова С) лежат в аффинном подпространстве поля GF (q"). По теореме 11.61 в коде содержится другое кодовое слово, С*), ненулевые координаты которого равны единице, причем они соответствуют тем же самым q локаторам. Если С<* не является скалярным кратным С), то разность между С*) и некоторым скалярным кратным С<) дает кодовое слово, вес Хэмминга которого меньше, чем д, а это противоречит БЧХ-границе для минимального веса кода, щ

Как покажет теорема 11.65, теорема 11.61 является также полезной для определения кодовых слов малого веса в некоторых негациклических кодах.

11.65. Теорема. Негациклический код с блоковой длиной (р" - 1)/2, корни порождающего многочлена которого совпадают с а, а, а, . , ., а" и их сопряженными, содержит кодовые слова веса р в метрике Ли.

Доказательство. Если К <2р - 2 и w (К) р - 1, то к = р - I. Следовательно, о (z) = П + ( + ) z], где

п Г] - элементы поля GF (р*"), линейно независимые над GF (р). Для того чтобы доказать допустимость о (z), надо установить, что изменение знака любого взаимного корня не приводит к другому взаимному корню. Если бы это было так, то J + ti = - (/ + tj) " + /) I = - 2т], что противоречит линейной независимости и г над GF (р). щ

В качестве иллюстрации к теореме 11.65 рассмотрим пример с р = 5 и m = 2. Выберем а из приложения В. Пусть = а, т] = 1, так что взаимными корнями многочлена о (z) являются а", а*, а = = -a = -а», а = -а", а С = [1, О, О, О, О, -1, О, О, 1, - 1, -1, 0] - кодовое слово негациклического кода, порождающие корни которого совпадают с а, а, а, а и их сопряженными.

Теорема 11.65 ограничивает область применения теоремы 9.34. Негациклический код, корни порождающего многочлена которого содержат а, а, а, . . ., а~, может исправлять столько же ошибок в метрике Ли, сколько и код, корнями порождающего многочлена которого являются а, а, а*, . . ., а~, хотя избыточность последнего кода почти вдвое превышает избыточность первого.

Теоремы 11.62 и 11.65 позволяют выделить кодовые слова мад веса, ненулевым координатам которых соответствуют локато лежащие в аффинном (или линейном) подпространстве поля GF Можно также найти кодовые слова малого веса в метрике Хэммщ ненулевым координатам которых соответствуют локаторы, предс ляющие собой линейные сдвиги точек аффинного подпространс поля GF (р™). В частности, имеет место следующее утвержден

11.66. Теорема. Если 1-удлиненный БЧХ-код с конструк ным расстоянием d и блоковой длиной q™ над полем GF (q) содерз кодовое слово веса d и если локаторы ненулевых координат эп кодового слова лежат в подпространстве размерности m - /с GF (q), то 1-удлиненный БЧХ-ко с блоковой длиной q и констр тивным расстоянием dc содержит кодовые слова веса йф.

Доказательство 1). Пусть (i = 1, 2, . . ., d) - лс торы ненулевых координат кодового слова веса d, и пусть У значения соответствующих координат. Тогда Yi 6 GF (g), g GF \

и 2 Yiul = 0 для / = 0, 1, 2, . . ., d - 2. Пусть L* (z) - та

g-линеаризированный многочлен степени q~ над GF (q™), все ни которого лежат в GF (?"), причем среди них содержатся щ, щ, . . ., a<j- Так как размерность линейного пространства, натянз на щ, . . ., Uj, не превосходит т - к, то многоч L*{z) с такими свойствами существует. Пусть L{z) - многое дуальный к L*{z). Согласно теореме 11.35, L (z) - Uj

= Д (z - Xi,j), где Xi,j 6 GF (q). Мы утверждаем, что рас

репный БЧХ-код с конструктивным расстоянием dq*" соде! кодовое слово, локаторами всех d ненулевых координат кото являются Xi,j, 5 = 1, 2, . . ., d, 7 = 1, 2, . . ., q, причем нег вую координату с локатором Xi j можно взять равной Fj. Для дв зательства вычислим величину

Sjc = S S iXf,}- S 2 Xi, j.

1=1 j=i t=l 3=1

Так как 2 у - невзвешенная степенная симметрическая функ

рт Xi,j, то, применяя теорему 11.61, получим, что

Sk=Ii Yi 2 Вк. jui=2 . 2 Yii-

t=l J J i=i

ЁСЛП

/<d-2, to 2 Yiui = 0. Если d - i J, 10 Bk J = 0,

roe независимое доказательство этой теоремы было дано Пит

за исключением случая, когда J + i. q (К + 1), и, еле вательно, K>dq- 1. Поэтому Зк = О для О К dq - 2

Теоремы 11.61 - 11.66 показывают, как линейные и аффинные подпространства конечного поля могут быть использованы для выделения в некоторых кодах слов малого веса. К некоторым другим кодам применима иная, не связанная с аффинными подпространства-ли техника выделения слов малого веса. Пример такого рода дает теорема 11.67.

11.67. Теорема (Казами, Лин, Питерсон [1966]). Если ВЧХ-код с конструктивным кодовым расстоянием d и блоковой длиной «1 над GF (q) содержит кодовые слова веса d и если п делит п, то ВЧХ-код с конструктивным расстоянием d и блоковой длиной п над GF (q) также содержит кодовые слова веса d.

Доказательство. Локаторы первого кода являются корнями «1-й степени из единицы, а локаторы второго кода - корнями «з-й степени из единицы. Так как п делит п, то локаторы первого кода образуют подмножество локаторов второго кода. Следовательно, кодовое слово малого веса, принадлежащее первому коду, при-надлеихит и второму.

11.68. Следствие. Если d\n, то ВЧХ-код с конструктивным расстоянием d и блоковой длиной п над GF (q) содержит кодовые слова веса d.

Доказательство. БЧХ-код с конструктивным расстоя-IJ кием d и блоковой длиной d всегда содержит кодовое слово веса d. щ

К сожалению, теоремы 11.61-11.67 позволяют определять слова ; малого веса в относительно узком классе кодов. Минимальное расстояние для большинства кодов, даже для большинства БЧХ-кодов, не и.чвечтно. Из разд. 10.3 и 10.4 мы знаем, что истинное минимальное расстояние не меньше конструктивного расстояния, а во многих Г. случаях больше. В общем случае, согласно следствию 11.63, истин-Г; ное ])асстояние каждого примитивного БЧХ-кода с точностью до [ делителя числа q совпадает с конструктивным расстоянием. Практи-1; чески корректирующие возможности БЧХ-кодов часто определяются у их конструктивным расстоянием, а не истинным, так как наиболее употребительные алгоритмы декодирования не позволяют исправлять векторы ошибок, вес которых - больше половины конструктивного расстояния. В разд. 10.5, 10.6 и 11.1 были описаны улучшенные алгоритмы, позволяющие исправлять ошибки несколько большего веса; Ио даже эти алгоритмы приводят к отказам, если декодер пытается

исправить две дополнительные ошибки по сравнению с тем, гарантирует конструктивное расстояние.

С точки зрения практических приложений наиболее важн вопросами относительно любого кода являются: (1) Насколько хо код? (2) Насколько легким является его декодирование? (3) Kai его скорость передачи информации? Вопросы (1) и (2) являются hi нерными, поскольку понятия «хороший» и «легкий» могут быть ol делены только в терминах статистики шума в канале, которая пике не известна точно, и в терминах стоимости оборудования, кото сущ,ественно зависит от нынешнего состояния электронной техш Если качество кода определяется в терминах конструктивного стояния, то для частных БЧХ-кодов на вопросы (1) и (2) можно следующий приблизительный ответ: (1) существуют коды с извольным конструктивным расстоянием; (2) как было покаа в гл. 2, 7 и 10, декодирование является относительно простым, эти ответа являются обнадеживающими. В противоположи вопросам (1) и (2), вопрос (3) является точным математическим во1 сом, ответ на который будет дан в гл. 12. В гл. 13 будет показано,] в определенном смысле этот ответ является неутешительным, поскс ку существуют лучшие коды с большой блоковой длиной, име» значительно большую скорость передачи, хотя для этих кодов известны реализуемые алгоритмы декодирования.

Указание. Воспользоваться теоремой 11.52.

(b) Какую часть составляют невырожденные квадратные двоичные (пхп)-матрицы для больших ге?

(c) Сравнить полученные результаты с ответами к задаче 7.6 и вычислениями рангов для некоторых других классов матриц (Карлиц и Ходж [1956а, 1956в]; Берлекэмп [1966]).

11.6. (а) (Оре [1933, 1934], Глизон и Мэрш, Цирлер [1958]). Пусть / (г) - неприводимый многочлен над GF (д), а. F (z) - его ассоциированный линеаризированный многочлен. Доказать, что степень каждого неприводимого делителя многочлена F (z)/z равна периоду / (z).

(b) Указать неприводимые двоичные трехчлены степеней 3, 7, 15, 31, 63 п 127.

Задачи

11.1. Пусть а - корень многочлена +1. Для каждого из еле щих многочленов найти все корни, лежащие в GF (2):

(a) z3 + аЩ + a*z + а,

(b) 2* + ai8z3 + a"z2 + аЧ + 1,

(c) zs + aV + ai8z3 + аЧ + аЧ + а".

11.2. Для каждого из многочленов предыдущей задачи найти н. о. д. cj гочленом z* + 2 и найти дуальный для каждого из этих н. о. д.

11.3. Сколько неприводимых двоичных многочленов степени т, т = 3, . . ., 20, имеют линейно независимые корни?

11.4. Найти примитивный неприводимый кубический многочлен над Gi Обозначив через а его корень, выразить каждую степень а в виде многоч от а степени <;3 над GF (3). Показать, что кубическое уравнение общего над GF (3) может быть приведено к одной из трех стандартных аффинных "

(a) z + 2 = U,

(b) z 4- az = и,

(c) z = и.

(Заметим, что квадратный корень может быть вычислен как тринадцатая пень.) Подобно примеру 11,15, построить схемы для решения каждого из; трех кубических уравнений.

11.5. (а) (Ландсберг [1893]). Какая часть из дп матриц над GF (д) ра« ности т X п имеет ранг г?