У. Питерсон - Коды, исправляющие ошибки (1267328), страница 79
Текст из файла (страница 79)
Таким образом, евклидово-геометрический код должен содержать в своем нулевом пространстве полиномиальный код, и, следовательно, он максимальный. Теперь рассмотрим случай, когда символы кода выбираются из 6Р(//), где // = р, ч ) 1. Наибольший код, содержащий плоскости в своем нулевом пространстве, является двойственным коду, порожденному этими плоскостями. Этот код может быть оха рактеризован с помощью следующей теоремы: Теорема 10.16. Пусть ч„ч, ..., чл — л!ножество векторов с символами из 6Р(//) и ч= ~~! (1!ч!, где р! ен 6Р(// ), но все сим! ! волы ч — элементы 6Р(//), Тогда в 6Р(/1) существуют такие элементы Ь|, Ь,, ..., Ьы что ч= ~ Ь/ч!.
! ! Доказательство. Пусть р/=Ь!в+Ьна+ ... +Ь/!м !!а ', где а — элемент 6Р(д ). Тогда х л !и — ! ь л ~, р!ч!=- ~~',,», Ьца/ч; = ~ Ь/пч/+а / Ьач!+ ... !-! //е ! ... +а ' ~~'„Ь! ! !!ч!=ч. /=! Так как символы ч принадлежат 6Р(д), отсюда следует, что Х Ьнч! =0, 1«=1< / ! 2 Ьмч!=ч, ! что и требовалось доказать. Пусть через С! обозначен код, порожденный евклидовыми плоскостями размерности г+ 1 над 6Р(//), а через Ст — код, порожденный теми же плоскостями, но над 6Р(р). По теореме !0.1б множество линейно независимых над 6Р(//) векторов будет линейно независимым над 6Р(р) и обратно. Поэтому базис кода Сх может служить базисом и для С!, Порождающий многочлен кода есть наибольший общий делитель любого множества базисных многочленов, и поэтому С! и Сх порождаются одним и тем же много- членом.
Таким образом, (максимальный) евклидова-геометрический код над 6Р(//) имеет тот же самый порожда!ощий многочлен, что и (максимальный) евклидова-геометрический код над 6Р(р), в свою очередь задаваемый теоремами 10.4 или 10.15. Ион!но показать, что если коэффициенты многочлена у(Х), порождающего код, принадлежат 6Р(р), но символы кода выбираются из 6Р(р!), то этот код эквивалентен коду, полученному ч-кратным перемежением кода над 6Р(р), порожденного д(Х). Теперь рассмотрим проективно-геометрические коды с символами из 6Р(р). Теорема 10.!7. 17роективно-геометрический код порядка г двойственен полиномиа ьному кодр с параметром а = (гп — г— — 1)(р -1) доказательство теоремы следует непосредственно из теорем И),6 и 10.14 и леммы 10.8. Отметим, что, как показывает следствие 10.2, векторы, соответствующие проектнвным подпространствам размерности г, принадлежат полнномиальному коду.
Снова возникает вопрос: является ли этот код самым болыпим кодом, содержащим в своем нулевом пространстве все проективные подпространства размерностн г нли больше. Для кодов с символами из Ог(р) положительный ответ дан в работах (60, 62, 166). Если же символы кода выбираются из ОР(р ), и ) 1, то те же рассуждения, что и для евклидова-геометрическнх кодов, показывают, что порождающий многочлен для (максимального) РП-кода над ОР(р ) длины и и порядка г совпадает с порождающим много- членом кода на Ог"(р) длины и и порядка г. И в этом случае коды над ОР(р') эквивалентны кодам, полученным ч-кратным перемежением кодов над Ог" (р).
Замечания Мажоритарное декодирование было впервые использовано в процедуре Рида для декодирования кодов Маллера. Прейндж применил один из вариантов процедуры Рида к циклическим кодам и показал, что некоторые специальные коды могут быть ма>коритарно декодируемы. Ял (336) и Цирлер показали, чтодвоичные коды максимальной длины допускают мажоритарное декодирование.
Интересно, что коды, рассмотренные всеми этими исследователями, оказались частными случаями конечно-геометрических кодов. Способ декодирования кодов Галлагера (102) весьма близок к мажоритарному. Мессн (206) доказал, что все двоичные БЧХ- коды длины 15 или менее допускают мажоритарное декодирование. Значительная часть материала равд.
10.1 основана на его результатах. Рудольф (2601 впервые применил конечные геометрии для построения кодов с мажоритарным декодированием и поэтому большинство результатов, излагаемых в этой главе, является развчтнем его работы. Математический аппарат для анализа конечно-геометрических кодов разработан Касами, Линам и Питерсоном (168, 169), Уелдоном 1323, 324), Грехемом и Мак-Уильямс (126), Геталсом и Делсартом (112) и Чоу (52). Задача определения числа информационных символов конечно-геометрических кодов изучалась этими авто. рами, а также Мак-Уильямс и Манном (197) н Смитом [2821, Обобщенные коды Рида — Маллера были построены Касами, Лином и Питерсоном (169]. Обобщенным кодам Рида — Маллера посвящена также работа [62).
Большинство первоначальных результатов по полиномиальным кодам получено Касами и Лином. Залачи 10.1. Докажите, что код, двойственный обобщенному коду Рида — Маллера р-го порядка, есть также обобщенный код Рида— Маллера (и — р — 1)-го порядка. !0.2. Постройте мажоритарный декодер для двоичного (15,7)- кода ЕО. 10.3.
Постройте мажоритарный декодер для двоичного (21, 12)- кода РО. 10.4. Определите корни порождающего многочлена 8(Х) ЕО- кода 0-го порядка длины 63, соответствующего геометрии Еб(3,2'). Проверьте, что этот код имеет Нвчх = 23, дмь = 21 и й=13. 10.5. Докажите, что код, двойственный ЕО-коду, является подкодом некоторого ЕО-кода и, следовательно, также допускает мажоритарное декодирование. 10.6. Установите связь циклических кодов максимальной длины (равд. 8.5)с классом мажоритарно-декодируемых кодов и докажите, что эти коды могут быть декодированы в 1, шагов.
10.7. Покажите, что произведение двоичного (7,3)-кода РО на самого себя можно декодировачь в один шаг. !0.8. Обобщите результат задачи 10.7 и докажите, что произведение двух кодов, декодируемых в 1. шагов, с минимальными расстояниями г(, и г4 допускает декодирование в Ь шагов и при этом исправляются все комбинации из (Ас(з — !)/2 или менее ошибок. 10.9. Обобщите результат задачи 10.8 на случай, когда лишь один из кодов-сомножителей декодируем в 7. шагов. 10.10.
После решения задачи 10.9 рассмотрите произведение двух кодов, декодируемых в 7. шагов. Полностью ли ортогонализуем этот код-произведение? 1О.11. (205). Во всех процедурах мажоритарного декодирования, обсуждаемых в этой главе, ортогональные проверочные суммы на шаге 1 образуются из линейных комбинаций символов синдрома (декодирование типа 1). Так как символы синдрома являются линейными комбинациями принятых символов, то ортогональные проверочные суммы можно непосредственно представить как линейные комбинации принятых символов.
В литературе !205) эта процедура называется декодированием типа П. Постройте декодер типа П для (21,!2)-кода задачи 10.3. 10.12. Сравните сложность декодеров типов ! и П для кодов с декодированием в А шагов. 11 Циклические коды, исправляющие пакеты ошибок определим пакет ошибок длины Ь как последовательность из таких Ь ошибочных символов, что первый и последний из них отличны от нуля.
В случае циклических кодов удобно также рассматривать как пакет ошибок такие комбинации ошибок, у которых ненулевые символы занимают всего Ь позиций по обоим концам слова. В этой главе не проводятся различия между такими «циклически-круговымн» и обычными пакетами. 1(орошо реализуемые коды, исправляющие пакеты, построены как аналитическим способом, так и с помощью вычислительных машин. Для всех этих кодов найдены просто реализуемые процедуры декодирования. Таким образом, по меньшей мере с точки зрения инженера, задачу построения кодов, исправляющих пакеты, и декодеров для таких кодов можно считать решенной.
В теореме 4.15 утверждается, что корректирующая способность для пакетов Ь произвольного линейного блокового (п,й)-кода определяется условием и — й — 2Ь=г»:О. Параметр г является мерой неэффективности блокового кода, исправляющего пакеты. Для некоторых кодов, представленных в равд. 11.1 и 11.2, з = О; для многих других кодов з лишь немного больше. 11.1. Аналитические методы построения кодов Следующая теорема показывает, что длинный циклический код с хорошей корректирующей способностью для пакетов может быть построен путем применения метода перемежения к более корот- кому коду. теорема 11Л.
Если многочлен й(Х) порождает циклический (и я)-код, способный исправлять все пакеты длины Ь или меньше, то многочлен д(Хч) порождает циклический (п(, И)-код, способный исправлять пакеты длины ЬЕ Доказательство. Поскольку степень многочлена д(Х) равна и†и и многочлен Х" — 1 делится на многочлен й(Х), то степень многочлена Ы(Х') равна 1(п — Ь) и многочлен Х"' — 1 делится на многочлен й(Х'). Остается только показать, что длинный код спо.
собен исправлять пакеты ошибок длины Ь1, Проверочный многочлен кода равен А(Х'). Ь1ногочлены А(Х!), Х!А(Х!), ..., Х(" — 4-')(А(Х() задают совокупность из и — А независимых проверочных соотношений относительно информационных символов, находящихся на позициях, соответствующих одночленам Х( — ")*, Х<" — "+')', ..., Х<"-')'. Вообще многочлены Хай(Х!), Х'+)А(Х(), ..., Х(п-4 — (и+)6(Х!), О ( ! - ! — 1, задают совокупность нз и — А независимых проверочных соотношений относительно информационных символов, стоящих на позициях, соответствующих одночленам Х( 4)(+1, Х("-4+(и+), ..., Х<" (и+1.
Ясно, что никакое проверочное соотношение в любой из этих совокупностей не включает информационный символ из другого множества. Поэтому естественно изображать код в виде следующей двумерной таблицы: Х2! 'Х' ' Х (л — !)1-! Х( — 4+1)! — 1 ! Х( -4)! — 1 Х(п- 1) !-2 Хп! -1 Хп(-2 Хп<-2 (11.1) Х' 1 Х(" 4 ')!...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
