У. Питерсон - Коды, исправляющие ошибки (1267328), страница 18
Текст из файла (страница 18)
Однако после такой замены можно поменять порядок суммирования. Теперь, приравнивая коэффициенты при Х* в левой и правой частях, находим. что В~=о ХА! Х С)Сл-'г( 1) (д 1) г-в -о Полагая Х = 1 + У в равенстве (3.26), получаем дэ Х В (1+У)~= ~'., А~( — У)!(д+(!! — 1)У) ~ (3.28) ь-в у-о Расширяя область суммирования и приравнивая коэффициенты при У"' слева и справа так же, как это делалось при выводе равенств (3.27), получим п Рй Х в,с~= ч"-'- Х л,с,",:,-(-!)'(ч — Ц"-'. (3.28) 3 т ю-о Аналогично, полагая Х= 1/(1+ У) в равенстве (3.26), получим равенство Ч'~: В,(!+У)"-'= ~ А,У'(У ( ...)"-! (336) откуда после расширения области суммирования н приравнивания коэффициентов при У"' в левой и правой частях находим а-и П ): В~С.-~ =д" ' Х А!С.":,.
(3.31) ~-о у-о Теперь можно доказать равенство (3.31). Пусть з =(зь зм ... ..., э,„) — множество гп различных целых чисел, 1 =.э;«..и, и пусть ! =(!ь !м ..., 1„) — дополнительное множество, т. е. все целые числа, заключенные между 1 и л и не вошедшие в з. Обозначим через г, подпространство всех векторов, компоненты которых с номерами э, эм ..., з могут быть ненулевыми, но компоненты с номерами гь !ь ..., ! обязательно являются нулевыми. Аналогично определим гь Тогда Р, является нулевым пространством для г',. Далее рассмотрим подпространство всех векторов из !'ь компоненты которых с номерами гь !м ..., ! равны нулю. Это подпространство является пересечением множеств У~ и г„У~ПР,.
Аналогично подпространство всех векторов из Ум компоненты которых с номерами зь зэ, ..., з равны нулю, совпадает с подпространством Р~П $'в По теореме 2.18 нулевое пространство множества У~ПГ, есть Уз Я Рь Если обозначить через д, размерность или рассмотрим теперь пары, составленные из з — совокупности гп целых чисел и вектора т, из подпространства (г1Пг",. При фиксированном выборе а число таких пар равно д ' — числу элементов в (г,Пг„. Если учесть все возможные выборы з, то общее число таких пар равно во всем с С другой стороны, каждый вектор веса 1 из г'1 содержит и — 1 нулевых компонент, н любое множество („ которое является подмножеством и — сп индексов этих компонент, будет определять множество з, которое может образовать пару с этим вектором. Существует С„""; способов выбора множества з при фиксированном т, КРоме того, имеетсЯ А; вектоРов веса 1 в множестве Рь В РезУльтате приходим к равенству Аналогично, рассматривая 1', и множество (, состоящее из и — гп целых чисел, получим следугощий результат: Х Ч"'= ХВ!Св ь Но поскольку г(с = Н, + п — й — гп и ляет единственное множество з, то а~ ~ се+с-Ь-вс во всем 1 во всем е =д" " " ~"..
р"е каждое множество г опреде- по всем в со всем е и, следовательно, ~ В,С„" ~ =Ч" ' Х АС"-Г 1-а 1 пространства 1/~П Р, н через А размерность пространства ггПг'„то Р азмерность гс 9 гс равна п — с(„поскольку это нулевое пространство для Ь~ПГ'е. С другой стороны, по теореме 2.17 размерность пространства сс В Рс равна (и — й)+(л — т) — г(с. Итак, и — с~, =(и — Ц+ (и — лг) — г(ь 3!то и есть равенство (3.31). Из него вытекает равенство (3.30), а после подстановки Х = 1/(1+ У), с тем чтобы исключить У из равенств (3.30), придем к соотношению (3.26). Ч.
т. д. Мак-Уильямс [194) приводит в своей работе два доказательства этой теоремы. Здесь приводится наиболее простое из них. Второе доказательство опирается на теорию характеров групп н приводит к более общему результату, который будет приведен здесь без доказательства. Пусть через Х(а, р), где а и ~) — элементы поля из 2/ элементов, обозначена комплекснозначная функция от а, которая является характером аддитивной группы ОР(д), соответствующим (1 (см. гл. 6).
Поскольку определение и теория характеров групп нигде больше не используются в этой книге, мы не будем приводить их здесь. Если д — простое число, то в качестве характеров могут быть выбраны функции Х(1 (1) Е Ш2 ч»!, (3.32) где е — основание натурального логарифма, а 1= 1/ — 1. Если д = р"' и и 1, то, как показано в гл. 6, а и р могут быть представлены в виде наборов длины пй компонентами которых являются элементы поля нз р элементов, и в качестве характеров могут быть выбраны функции Х(а, ~) =е! .е!!тыу»1, где а р — скалярное произведение наборов а и р. В этих обозначениях справедлива следующая теорема, которая в работе (!94) появилась как лемма 2.7: Теорема 3.15.
Пусть через а»=0, а1, ..., а 1 обозначень1 все элементы поля, а через Х», Хь ..., Х , — д независимых переменных, Р1 †'я-мерное векторное пространство, а уе†соответствуя- и(Ее ему нулевое пространство. Обозначим через А;,.1,,...,! число векторов пространства т'1, в которых элемент поля 221 появляется 1, раз, с»2 появляется 12 раз и т. д. Элемент 0 должен появиться 22 = и — 11 — 12 — ...
— 1 1 раз. Число В1,1...„1 опре- '! 2 "" »-1 деляется аналогично. Тогда 22 »-!г' » '1!Г 1' 2'"" 1 1 = д" ~ В. Х,'1 ... Х1»-,1Х'». (3.33) 1, 1,.", 1», »-' » 1' 2''"" » 1 В теореме 3.14 утверждается, что если известно лишь, сколько вскторов в пространстве у! имеют каждую возможную компози- цию, го может быть вычислено число векторов из пространства !'и имеющих каткдую Возможную композицию.
Ка первый взгляд этот результат представляется слишком сложным, чтобы его можно было где-либо использовать. Поэтому, чтобы лучше понять его структуру, рассмотрим два частных случая. Пусть сначала»! = 2. Тогда в соответствии с определением (332) Х(О, 0) = Х(0, 1) = Х(1, 0) = 1, Х(1, 1) = — 1. Пусть »х! = 1, из = О. Тогда Аь равно просто числу векторов веса », и соотношение (3.33) превращается в равенство ~„А»,(хо+ Х!)" (Хь — Х!)' = 2 ~ В! Хьих~!'. (3.34) »,=0 ! О Если положить здесь Ха = 1 и »о = и — »», то получится равенство (3.26) для двоичного случая. Рассмотрим теперь случай»7 = 3 и обозначим через ~ корень кубичиый из единицы, т. е.
~=(! +»1/3)/2. Тогда Х(с», 6) = = (,а. Тремя элементами поля являются а! — — 1, »тл — — 2 и аз = О. Тогда А,п равно числу векторов, содержащих »! компонент, равных 1, и »з компонент, равных 2, и соотношение (3.33) переходит в равенство ~ А! »,(Х»+ Хз+ Хз)иКХ! + ~~Х + Хз)п(~~Х»+ ~Ха+ Хз) »~ ! »и ! л и ~ в„„х;х,х .
рзб) ! ! и 1 Теорему 3.14 можно вывести из теоремы 3.15, полагая Хь — — 1, а все остальные Х» =Х и используя некоторые простые свойства характеров. Следующая теорема тоже выводится из теоремы 3.15, если положить Х; =Х и Х» = 1 при ! Ф. ! и сделать некоторые упрощения.
Теорема ЗА6. Пусть через В; обозначено число векторов из пространства ть ! компонент которых принимают значения»х! чь О, и пусть Аы — число векторов веса и из пространства )'», сумма компонент которых равна О, и А»,— число векторов веса з из пространства !»», сумма компонент которых не равна нулю. Тогда л ь ~ Взх = ~~» (Ар, — — ы! )(Х вЂ” 1) (Х+»! — 1)" '. (3.36) »-ь в О Плесе [239) заметила, что из тождеств Мак-Уильямс можно вывести выражение для суммы 1-х степеней весов векторов пространства: (Х л 1,»)" В,Х =)-»чв,х.
»-ь (3.37) Подставляя Х = 1 в это выражение, получаем нужный результат. Проводить дифференцирование, вообще говоря, сложно, но Плесе нашла более явную форму для выражения (3.37). Заметим, что л ~! в результате действия оператора (Х вЂ” ) на правую часть равендх,) ства (3.26) числа А; умножаются на — !Х„если ! ) 1, так что все члены, содеРжащие Аь пРи 1) 1 исчезнУт. Полезно записать окончательные соотношения для случаев 1=0,1и2: ХВ,=д.-з, ) Я вЂ” Оп-ь-! (н(д 1) А ] ! (3.38) ~~', РВ, =О"-ь-'(н (д — 1) (ло — а+ 1)— — А, (о+ 2 (и — Ц (д — 1)) + 2Аз). Первая сумма выражает просто число векторов в пространстве; вторая сумма — это сумма весов кодовых слов, а третья — сумма квадратов' весов.
Коэффициент А, принимает значение 0 тогда и только тогда, когда среди столбцов порождающей матрицы пространства Ф'з отсутствует нулевой столбец. Коэффициент Аз принимает значение 0 тогда и только тогда, когда любые два столбца порождающей матрицы пространства Уз не пропорциональны. Почти для всех кодов, представляющих интерес, и Аь и Аз равны нулю. Другое доказательство второго соотношения предлагается в задаче 3.6. Были приложены значительные усилия для определения распределения весов различных типов кодов; некоторые из этих результатов включены в гл.
9 и 10. Книга Берлекэмпа [2!) содержит исчерпывающее изложение этих вопросов. 3.9. Максимально разнесенные коды Минимальное расстояние для (н, й)-кода над полем бр(д) не превосходит н — й+ 1, поскольку существуют кодовые слова с одним только ненулевым информационным символом. Коды, для которых И = и — Й+ 1, называются максимально разнесенными кодами. (См. по этому поводу работы !!О, 91, 167).) Нетривиальных двоичных максимально разнесенных кодов не существует, но есть нетривиальные недвоичные коды. Коды Рида — Соломона, рассматриваемые в гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
