У. Питерсон - Коды, исправляющие ошибки (1267328), страница 64
Текст из файла (страница 64)
Общий метод определения минимального веса кода состоит в том, чтобы указать кодовое слово, вес которого соответствует нижней границе минимального веса. Один из вариантов этого метода состоит в нахождении циклического произведения кодов, один из подкодов которого совпадает с данным кодом н содержит кодовое слово минимального веса. (Циклическое произведение кодов рассматривается в равд.
8.12.) На этой идее основывается следующая теорема: Теорема 9.3. Пусть и, и пг — взаимно простые числа и число и, делится на а. Если БЧХ-код длины пз с конструктивным расстоянием д над 6Е(д) имеет минимальное расстояние, в точности равное д, то истинное минимальное расстояние БЧХ-када длины папа с конструктивным расстоянием ас( в точности равно аА доказательство. Пусть Сз — код длины пь а С~ — код длины п„ для ля которого д1(Х)=(Х"' — 1)ДХ вЂ” 1), Ь,(Х)= — Х' — 1.
Если элемент порядка пп то а„ао ао ..., а, ' — корни много- 1 члена а, (Х), где Ь = и,/а, а аь — корень многочлена Ь, (Х). В соответствии с границей БЧХ С, имеет минимальный вес по меньшей мере Ь. Однако многочлен у, (Х) сам имеет вес Ь, и поэтому минимальный вес кода С, в точности равен Ь. В этом коде 1, ь аьь ..., а",-" — корни многочлена Ь(Х), а все другие степени элемента а, являются корнями многочлена д, (Х). Пусть пь — элемент порядка пэ и С, — код, порожденный много- членом д (Х), корнями которого являются а, о~~, а~', ..., а~" и', но не а"'. Так как а взаимно просто с п, то а' — примитивный корень степени пз из единицы, которым можно воспользоваться для такого определения многочлена д(Х).
Рассмотрим циклическое произведение кодов С, и Сь Поскольку и, н пь — взаимно простые числа, то ы = а1гсь имеет порядок и = = п,п, и в силу следствия из теоремы 8.19 первым элементом среди элементов а, а~, аз, ..., являющимся корнем многочлена Ь(Х), является элемент ы"". Таким образом, ы, аз, ..., гь"' '— корни многочлена у(Х), и произведение кодов является подкодом БЧХ-кода длины и = п,п, с конструктивным расстоянием ай. Но в силу того, что кодовое слово веса а имеется в коде С~ и по предположению в коде Ст существует слово веса а', то в произведении кодов и, следовательно, в БЧХ-коде, содержащем это произведение, должно быть слово веса ай, т.
е. истинное минимальное расстояние БЧХ-кода в точности равно ай. Ч. т. д. Следствия 9.2 и 9.3 вытекают нз теоремы 9.3, если положить соответственно а = 1 и а =пи Следствие 9.2. Если и, и пз — взаимно простые числа и БЧХ-код с конструктивным расстоянием й и длиной пт имеет минимальное расстояние, в точности равное й, то БЧХ-код длины п,пз с конструктивньиа расстоянием й имеет минимальное расстояние, в точности равное й. Следствие 9.3. Если п~ и пт — взаимно простые числа, а БЧХ- код с конструктивным расстоянием й и длиной и, имеет минимальное расстояние, в точности равное й, то БЧХ-код длины п1пт с конструктивным расстоянием п~й имеет минимальное расстояние, равное п4. Окончательно получаем, что если число пз взамно просто с числом д, то код, построенный путем пз-кратного повторения одного информационного символа, предстанляет собой вырожденный ваРиант БЧХ-кода с конструктивным расстоянием и, и истинным Расстоянием и .
При этом указанные два следствия сводятся к следующему; Следствие 9.4. Если и = пап»„то БЧХ-код длины и с конструктивныи расстоянием и, имеет минимальное расстояние, в точности равное пз. Теоремы 9.4 и 9.5 определяют дополнительные подклассы БЧХ-кодов с известным минимальным весом. Эти результаты используют идеи, изложенные в равд. 9.4. Лемма 9.1. Степенная симметрическая функция Бь равно нулю при 1 < Ь (/ тогда и только тогда, когда элементарные симметрические функции оь равны нулю при всех Ь, не превосходящих / и не делящихся ни характеристику поля р.
Доказательство. Необходимость следует непосредственно нз тождеств Ньютона [см. равенство (9Б4)). Достаточность доказывается по индукции с применением тождеств Ньютона. Поскольку 3~ = оь то утверждение верно при ! =!. Предположим, что оно верно при 1 = 1».
Если о; = 0 для каждого й меньшего 1ь+ 1 и не делищегоса на Р, то по пРедположевиам индУкции Яь Бм ..., Яь равны нулю. Следовательно, в силу первого тождества НЬютона, содержащего ЯЬ+ь БЬ+, также равно нулю. Ч. т. д. Лемма 92. Корни многочлгна р(Х) = Хг+ и~Х!-'+ ... + а; определяют номера позиций кодового слова веса 1 в БЧХ-коде длин»ч и с конструктивным расстоянием Ы тогда и только тогда, когда: 1) иногочлен р(Х) имеет 1 различных корней в поле 6г(д ); 2) каждый корень имеет порядок и; 3) а; = 0 при произвольном й меньшем с( и взаимно простои с характеристикой поля р.
Доказательство. Если выполняются все три условия, то степенные симметрические функции корней Бь 5», ..., Ял ~ равны нулю в силу леммы 9.1 и, следовательно, корни определяют номера позиций кодового слова. Обратно, если корни р(Х) определяют номера позиций кодового слова, то условия 1) н 2), очевидно, выполняются, а, поскольку для любого кодового слова Бь Зь ...
Ял, должны равняться нулю, условие 3) следует из леммы 9.1. Ч. т. д. Теорема 9.4. Для любого Ь, 1 ( Ь ( т, пршчитивный БЧХ-код длины и = д — 1 с конструктивным расстоянием д = дь — 1 имеет иинима ьное расстояние, в точности равное о" — 1, Доказательство. Пусть О, Хп ..., Х ь, образуют произвольное подпространство поля 6г (д ) над 6г (Ч). Тогда в силу следствия 6.2 многочлен р(Х)=Х(Х вЂ” Х,)... (Х вЂ” Хь,) имеет вид р(Х)= =Х» +а,Х» '+ ... +и„Х. Поэтому многочлен р(Х)(Х удовлетворяет условиям леммы 9.2 и существует кодовое слово веса Чь — 1. Ч. т.
д. Эта теорема является также прямым следствием теорем !0.9 н 10.10, в которых утверждается, что обобщенные коды Рида— Маллера являются подкодами БЧХ-кодов и имеют минимальное расстояние, совпадающее со значением границы БЧХ. Теорема 9.5. Предполоохим, что примитивный БЧХ-код над 6р(д) длины о — 1 с конструктивным расстоянием 4, имеет минимальный вес, в точности равный йм и йь+! делится на характеристику поля р, Тогда примитивный Б ЧХ-код длины у — 1 с конструктивным расстоянием (4, + 1)9 —" — 1 при Ь) 4, имеет минимальный вес, в точности равный (йь+ 1)д "— !.
(Заметим, что условие, состоящее в том, что йь+ 1 делится на р, удовлетворяется для всех примитивных двоичных БЧХ-кодов.) Доказательство. В силу предположений н леммы 9.2 существует многочлен а(Х)=аь+ а~Х+ ... + ив,Хв, с йь корнями из поля 6г'(д'"), для которого а, = 0 при любом 1, меньшем йь и взаимно простом с характеристикой поля р. Пусть (/ — произвольное Ь-мерное надпространство поля 6г(д"'), содержащее все корни многочлена а(Х). Так как имеется йь корней н 4,( Ь, то такие подпространства, очевидно, существуют.
Для такого надпространства П найдем многочлен ф(Х) из теоремы 6.30. Заметим, что из вида многочлена д(Х) следует, что он представляет собой линейное отображение. Множество элементов, отображаемых в нуль, задает подпространство У размерности т — Ь, а множества элементов, отображаемых в каждый элемент нз П, задают различные смежные классы для ь'. Рассмотрим многочлен а(д(Х)). Произвольный элемент любого из йь смежных классов, который многочленом д(Х) отображается в корень многочлена а(Х), является корнем многочлена аф(Х)). Поэтому а(д(Х)) имеет по меньшей мере йьд -ь корней.
Но степень многочлена а(д(Х)) равна 49 — ", и поэтому а(у(Х)) полностью разлагается на множители в поле 6г (о ), Теперь Ха(Х) имеет линейный член, а показатели всех других ненулевых членов делится на р — характеристику поля 6г(д). То же самое справедливо для многочлена д(Х) и, следовательно, для много- члена д(Х) а(д(Х) ). Поэтому у(Х)а(д(Х))/Х=Х!+Ь,Х'-'+ ... +ЬЬ где /=(йь+ 1)д™ "— 1 и Ь; = О, если 1 не делится на р. Более того, д(Х)/Х и а(д(Х)) полностью разлагаются на множители. Корни многочлена д(Х)/Х являются ненулевыми элементами К а корни а(д(Х)) образуют 4, смежных классов относительно )т.
Поэтому многочлен д(Х)а(д(Х)) полностью разлагается на множители, и все его корни различны. Утверждение теоремы теперь следует из леммы 9.2. Ч. т. д. Приводимая далее простая теорема охватывает многие результаты о минимальном весе БХЧ-кодов, которые исправляют относительно мало ошибок. Теорема 9.6 (Фарр). Если т > 1+ !опт(!+1)!, то примитивный двоичный БХЧ-код длины 2'" — 1 с конструктивным расстоянием 2!+ 1 имеет минимальный вес, в точности равный 2!+ 1. Приведем лишь схему доказательства.
Некоторыми элементарными, но не простыми алгебраическими преобразованиями можно показать, что если т > 1+!о8г(!+ 1)! оы Х С,' ., > С,'4', > 2" . ! О С левой стороны в этом неравенстве стоит количество комбинаций из 1+ 1 или меньшего числа ошибок, а справа — верхняя граница числа смежных классов в БХЧ-коде с конструктивным расстоянием 2!+1. Поскольку в коде, исправляющем 1+ 1 ошибок, все комбинации из !+1 илн меньшего числа ошибок должны лежать в различных смежных классах, то в коде, исправляющем ! ошибок, число смежных классов является недостаточным для исправления !+ 1 ошибок, Таким образом, минимальное расстояние кода меньше 2(1+1)+ 1 = 21+ 3.
Опо может быть равно 2!+2 или 2!+1. Так как БЧХ-коды примитивной длины инвариантны относительно аффинной группы перестановок, то из теоремы 8.!5 следует, что минимальный вес в нечетное число. Теорема 9.5 и теорема Фарра совместно дают более сильный результат. Теорема 9.7. Если т > 1+ !оде[(йь+ 1)/2)! и й > йь, то примитивный двоичный БХЧ-код длины 2 — 1 с конструктивным расстоянием (дь+ 1)2 "— ! имеет минимальное расстояние, в точности равное (йь+1)2 -" — 1.
Окончательный ответ на вопрос, значительно ли лучше длинные БЧХ-коды, чем на это указывает граница БЧХ, дает следующая теорема: Теорема 9.8. Истинный минимальный вес примитивного БЧХ- кода с символами из бр(о) не превышает величины оде+ о — 2, где йь — конструктивное расстояние. Доказательство. ПУсть й выбРано так, что Чь — 1)йь, но Чь-' — ! к. йь. Тогда в силу теоремы 9.5 БЧХ-код с конструктивным расстоянием оь — 1 имеет минимальный вес, в точяости равный Чь — 1. Но этот код содержится в коде с конструктивным расстоянием дь, и поэтому код с конструктивным расстоянием йь имеет кодовые слова веса оь — 1. Тогда истинный минимальный вес й не больше Чь — 1.
Таким образом, й<с" — 1=9(Ч вЂ” — !)+о — ! < ой,-1-Ч вЂ” !. (9.!О) Ч. т. д. для двоичного случая теорема 9.8 утверждает, что БЧХ-код с конструктивным расстоянием до имеет минимальный вес, не больший 2до. Как видно из фиг. 9.1, гРаница БЧХ стРемитсЯ к нУлю пРи фиксированной скорости, когда длина кода стремится к бесконеч„ости. Манн (20Ц нашел формулу, связывающую количество информационных символов в двоичном БЧХ-коде и конструктивное минимальное расстояние о(о Из этой формулы вытекает, что граница БЧХ действительно стремится к нулю с ростом длины кода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
