У. Питерсон - Коды, исправляющие ошибки (1267328), страница 59
Текст из файла (страница 59)
Аналогично, так как столбцы являются кодовыми векторами кода С„ то 1(Х, а') =О при любом Х, если а' — корень д,(Х). Таким образом, Ь (Х) = О„если либо а,' является корнем д, (Х), либо а,' является корнем дг(Х). По теореме 8.!7 число кори й д(Х) равно п и,— 6,6, тогда как число элементов а',а', равно (и, — 6,)6,+ +(и, — 146, — (и, — 6,)(пг — 6,)=п~п,— 6,6г. Следовательно, других корней нет.
Ч. т. д. Следствие. Если С, и Сг — циклические кодьц длины которых п, и пг взаимно просты, с проверочными многочленами 6,(Х) и Ьг(Х), а 6(Х) — проверочный многочлен произведения кодов, то а*' является корнем 6(Х) тогда и только тогда, когда а' есть Ф корень 6,(Х), а а — корень 6,(Х), где а~ — элемент порядка пь аз в элемент порядка пг и а = а~ам Доказательство. Это утверждение непосредственно вытекает из теоремы 8.!9 и того факта, что поскольку 6(Х) = (Х вЂ” 1)/д(Х), то а' является корнем 6(Х) тогда и только тогда, когда а* не является корнем н(Х). Ч. т.
д. Теорему 8.19 и следствие из нее можно доказать, не предполагая, что п не делится на р (!3?, 187); см. также задачу 8.16). Кроме того, эти результаты непосредственно обобщаются на случай произведения большего, чем два, числа сомножителей, поскольку произведение двух циклических кодов, умноженное на третий код, является произведением трех кодов. Результаты этого раздела и тот факт, что И = г(,А, для любого произведения кодов, позволяют сделать некоторые выводы относительно минимального расстояния некоторых циклических кодов !110). (См„, например, теорему 9.3.) 8.13. Квадратично-вычетные коды В этом разделе обсуждается класс циклических кодов, обладающих интересными математическими свойствами.
Хотя ббльшая часть результатов может быть обобщена, здесь рассматринаются только двоичные коды. Целое число ! называется квадратичным вычетом простого числа р, если существует целое число Х, такое, что Х'=— ! той р. Например, 1 является квадратичным вычетом любого простого числа. Пусть а — примитивный элемент поля 6г(р). Если г— квадратичный вычет р, то г~" '"~ ~ХР = — 1 гпобр, поскольку р — 1 делится на порядок любого элемента мультипликативной группы 6Е(р).
Отсюда вытекает, что если п<Р пм чз: 1 апой р, то это число будет невычетом. Очевидно, что четные степени д являются квадратичными вычетами, и так как для любого нечетного ! число Я*')сг-'у'= д(г — паФ 1, то все нечетные степени а будут невычетами. Далее можно показать, что если р представляется в виде 8т +. 1, то 2 является квадратичным вычетом р. (См., например, (21, стр. 188).) Отсюда вытекает, что для простых чисел такого вида число д' является квадратичным вычетом тогда и только тогда, когда числа 2и', 4а', 881, ...
также являются квадратичными вычетами и совокупность квадратичных вычетов состоит из одного или более полных циклических множеств. Это значит, что многочлен Хг — 1 разлагается на множители как (Х вЂ” 1) 8„(Х) д„(Х), где корни д„(Х) являются квадратичными вычетами р, а корни д„(Х) — квадратичными нсвычетами. Циклические коды с порождающими многочленами д,(Х), (Х вЂ” 1)д,(Х), н„(Х) и (Х вЂ” 1) а„(Х) называются кзадратично-вычегными кодами.
Рассмотрим теперь отображение 1-+г!. Так как г — некоторый ненулевой элемент поля 6Е(р), это отображение задает переста- новку всех элементов поля. Таким образом, отображение Х'- Х' задает перестановку элементов кодового многочлена. Рассмотрим код, который получается в результате применения этой перестановки ко всем миогочленам в квадратично-вычетном коде, Если г(Х) — кодовое слово в квадратично-вычетном коде, то !(Х') является кодовым словом в производном коде.
Пусть а" — корень порождаюшсго многочлена первоначального кода, ! = 1, 2, (Р.Е1)/2; тогда а"' также является корнем, так как г— квадратичный вычет, Итак, ~(Х')~х е,.— — 0=)(Х)!х,.и с=1, 2, ..., "~ и поэтому производный код совпадает с первоначальным, Аналогичные рассуждения показывают, что преобразование Х*'-ьХ *', где п является невычетом числа р, сопоставляет кодам, порожденным многочленами д„(Х), д (Х), (Х вЂ” 1)д,(Х) и (Х— — 1) д„(Х), соответственно коды, порожденные многочленами п„(Х), д„(Х), (Х вЂ” 1)д (Х) и (Х вЂ” 1)д„(Х).
Если число р представляется в виде 8т+ 1, то число (р — 1)/2 четно, откуда вытекает, что — 1 является квадратичным вычетом, Аналогично, если р =- 8лт — 1, т. е. если (р+ 1)(2 нечетно, то — 1 является квадратичным невычетом. Поэтому в этом случае а„(Х) =- д, (Х ) и д, (х) = д„(х-'). Рассмотрим теперь многочлен р(Х) минимального веса д из квадратично-вычетного кода, порожденного д„(Х) (или п,(Х)). Можно показать, что г( печетно (1Ц. Произведение р(Х") р(Х") делится одновременно на д„(Х) и д,(Х), ио не делится на Х вЂ” 1 и поэтому кратно Х"-'+ Х -х+ ...
+ Х+ 1. Следовательно, в этом произведении долгкно быть по меньшей мере и членов. Таким образом, поскольку вес каждого из сомножителей равен с( и р — простое число, то Ф) и. (8.51) Если р = 8т' — 1, то член Ха появляется в произведении Р(Х) р(Х-') точно и' раз. Следовательно, для таких кодон д(г( — 1) ) п — 1. (8.52) В некоторых случаях эти результаты были весколько усовершенствованы. В частности, было показано [11), что веса всех кодовых слов в квадратично-вычетных кодах, порожденных многочленами И,(Х) или д,(Х)„могут быть представлены в виде 4! — 1 Таблица 3.2. Некоторые квадратично-вычетные коды Ссылка или 41, а в кодах. порожденных многочленами (Х вЂ” 1)а„(Х) или (Х вЂ” 1)а„(Х),— в виде 41.
Соотношения (8.51) и (8.52) определяют нижнюю границу для минимального расстояния квадратично-вычетных кодов. Другая нижняя граница получается как следствие границы для БЧХ- кодов (равд. 9.1), которая показывает, что с( больше, чем наибольшее число последовательных корней порождающего много- члена. Однако оба результата, по-видимому, не отличаются особой точностью в случае квадратично-вычетных кодов, и для тех кодов этого класса, для которых г( определено точно, с( большей частью превосходит эти границы. В табл. 8.2 перечислены некоторые (и, (а+ 1)/2) квадратичновычетные коды, лля которых известно значение с(.
Коды, для которых известна только верхняя граница для г(, приведены в книге Берлекэмпа (21). Было показано, что все квадратично-вычетные коды инвариантны относительно преобразования Х вЂ” Х', и — квадратичный вычет. Это наводит на мысль о возможности декодирования квадратично-вычетных кодов методом перестановочного декодирования (см. равд. 8.9). Поскольку эти коды инвариантны относительно значительно большей группы перестановок, чем циклические коды, то, по-видимому, можно «собрать» относительно большое число ошибок в и — й последовательных разрядах. Успехи в теоретическом исследовании этой задачи незначительны. однако вычислительный анализ показал, что при этом методе декодирования возможно исправление всех комбинаций ошибок веса (с( — 1)/2 для всех кодов, перечисленных в табл.
8.2 при а 47 11951 7 17 23 31 41 47 71 79 39 103 113 151 3 5 7 9 11 11 15 17 19 15 19 Код Хвмминга Прейнды 12441 Код Голеи Мак-Уильямс 11951 Ассмус н Мвтгсен 191 Глисон 11031 Плесе 12401 Калин 11591 Калин 11591 Калин 11591 Келии ~159) Калин 1591 Было показано, что квадратично-вычетные коды и вообще коды, построенные при помоши вычетов любой степени е, тесно связаны с квазициклическими кодами, которые рассматриваются в равд. 8.14 [44, 15Я. 8.14.
Квазнциклические коды Циклические коды могут быть реализованы посредством достаточно простых схем главным образом потому, что они инвариантны относительно большой группы псрестановок порядка и, а именно циклической группы. При попытке построить другие классы достаточно просто реализуемых кодов естественно рассмотреть классы линейных кодов, которые инвариантны относительно достаточно больших групп перестановок.
Квазицнклические коды образуют один из таких классов. Пронумеруем разряды линейного блокового (тпм«пйз)-кода числами 1, 2, ..., и = пшм Если код инварнантен относительно перестановок 1 — 1+ и, (шоб л«пз), 1= 1, 2, ..., п, (8.53) г. е. если циклический сдвиг на пз символов всегда приводит к другому кодовому слову, то такой код называется квазициклическим. При таком определении циклические коды, для которых и н А делятся на число «пчь1, являются квазицнклическими кодами.
Например, (15,5)-код БЧХ является квазициклическим при т=5. Эд««ако не эти циклические коды сейчас представляют главный интерес. Пространство строк следующей матрицы инвариантно относигельно перестановок (8.53) и поэтому является квазициклическим (тп«ь тй0) -кодом: 1Р ОР,...ОР ОР- 1Р ...ОР- (8.54) ОР, ОРз ... 1Рь 'де через 1 и О обозначаются соответственно единичная н нуле«ая матрицы порядка йм а Р« — произвольные матрицы размерн«сти лоХ(по — А0). Каждое кодовое слово состоит нз т блоков «еизменных л информационных символов, за которыми следуют «а — яо проверочных символов.
(Отметим сходство между матри«ей (8.54) и матрицей (3.13) — порождающей матрицей сверточ«ого (тпм ий0) -кода.) Проверочная матрица, соответствующая матрице (8.54), имеет вид Р ~0 г где 1 в Π— соответственно единичная и нулевая матрицы порядка и — й. Кроме того, был изучен более общий класс квазициклических кодов, который получается, если единичные и нулевые матрицы в выражении (8.54) заменить произвольными квадратными матрицами порядка йэ[42, 159). Кодирование для квазициклического кода также можно проводить при помощи регистра сдвига с А ячейками способом, совершенно аналогичным способу, применимому для кодирования циклических кодов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
