У. Питерсон - Коды, исправляющие ошибки (1267328), страница 62
Текст из файла (страница 62)
Используя приложение Г и результат предыдущей задачи, перечислите все циклические коды, исправляющие кратные ошибки, для которых метод вылавливания ошибок позволяет исправлять максимально возможное для них число ошибок. Для заданных значений и и Ь достаточно указать один код. 8.12. Двоичный циклический (31,2!)-код, входящий в число кодов, перечисленных в приложении Г, не может быть декодирован посредством метода вылавливания ошибок, если требуется исправить все комбинации ошибок веса 2 или меньше. (См. задачу 8.10.) Покажите, что, используя перестановки Х' — ьХм, каждой комбинации ошибок веса 2 или меньше можно поставить в соответствие другую комбинацию ошибок, в которой единицы расположены внутри отрезка из 1О последовательных символов.
Это означает, что такой код может быть декодирован посредством перестановочного декодирования. 8.13. Для любого и существует двоичный исправляющий две ошибки (2 — 1,2 — 1 — 2т)-код БЧХ (см. гл. 9). Для каких значений т эти коды можно декодировать посредством перестановочного декодирования, используя перестановки Х'- Хэ'? (Сначала решите задачу 8.12.) 8.14. Покажите, что для декодирования методом вылавливания ошибок с окнами циклического (п,й)-кода, исправляющего две ошибки, необходимое число окон равно наименьшему целому числу, большему или равному ((л/2)+ 1]/(и — Ь) — 1. 8.15. Выведите соотношение, аналогичное соотношению (8.23), которое характеризует способность модификации метода вылав- лазания ошибок, названной в равд.
8.9 методом проб и ошибок, „справлять ошибки при декодировании кода. Какие коды длины, не превосходящей 31, из перечисленных в приложении Г могут быть декодированы этим методом с тем, чтобы они могли исправлять максимально возможное число ошибок? 8.16. (37). Докажите, что теорема 8.!9 справедлива, даже если и, или пг делится на р. 8.17. Измените кодер для квазициклического (12,4)-кода, изображенный на фиг.
8.8, так, чтобы им можно было пользоваться для кодирования в случае, когда код имеет систематическую форму. Сравните с кодером, имеющим А ячеек, для циклического кода, рассмотренным в равд. 8.7. 8.18. Постройте кодер из л — й ячеек для квазициклического систематического кода„ 8Л9. Перестановки Х'-ь Х"' переводят символы из 1-го разряда циклического кода длины п в р(-й разряд. Покажите, что если (п,р) =1, то при этом коду ставится в соответствие эквивалентный циклический код. В задачах 8.20, 8.21 и 8.23 предполагается, что С~ и Сз — циклические коды, длины которых соответственно и, и и, взаимно просты.
Порождающие многочлены этих кодов обозначены соответственно через д~(Х) и дз(Х), а проверочные многочлены — через й,(Х) и йз(Х). Через С обозначено произведение этих циклических кодов длины п = п,пз с порождающим многочленом д(Х) и проверочным многочленом й(Х). Пусть числа а и Ь определяются условием ап~ + Ьпз — — 1. 8.20. Покажите, что д(Х) = НОД[д, [Х' ), 8з(Х'"'). Х" — Ю 8.21. Покажите, что 8(Х)=ИОК(ИОД[8,[Х' ), Х" — 1), ИОД[а,[Х'"'). Х" — 13- 8.22.
Покажите, что й(Х)=ИОД[8,(Х' ), й (Х '). Х" — 6 8.23. Для примера на стр. 291 равд. 8.14 покажите, что ~, цз' 1 ()о ю-О Указание: рассмотрите произведение 7 П <Х вЂ” а' 1= 1о1. 8.24. Рассмотрите (и, А)-код с минимальным расстоянием И = = 21+1. Чтобы исправить все комбинации ошибок веса 1 или меньше методом рандомизированного перестановочного декодиро- вания 12271, необходимо Ш перестановок. Покажите, что ). "с„' Ф= ' ' ж1 — ~1 для больших и, ~ с„', 1 ! где 1г — скорость передачи. Экспериментальные данные 12271 для значений и порядка нескольких сотен показывают, что эта граница является довольно точной. Обсудите результат.
9 Коды Боуза — Чоудхури - Хоквингема Б этой главе описываются коды, являющиеся обобщением кодов Хэмминга на случай исправления нескольких ошибок. Они образуют наилучший среди всех известных класс конструктивных (т.е. неслучайных) кодов для каналов, в которых ошибки в последовательных символах возникают независимо. Для этих кодов найдены просто реализуемые процедуры декодирования.
9.1. Граница БЧХ Нижняя граница для минимального расстояния, которая приводится в этой главе, применима ко всем циклическим кодам. Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды) составляют класс циклических кодов, порождающие многочлены которых выбраны таким образом, чтобы получить минимальное расстояние, гарантированное этой границей. Теорема 9.1. Пусть д(Х) — порождающий многочлен циклического кода длины и над 6Р(д) и пусть а", а", ..., а'е-ь — корни многочлена у(Х), быть может лежащие в расширении поля, где а — элемент порядка и. Минимальное расстояние этого кода болыие, чем наибольшее количество последовательных целых чисел по модулю и в множестве е =(е„ем...,е„ь), (ае,)ь ( е)е (ае,) ,)е-2 ... а'" 1 ае, (9.1) (аее — ь) (а ее ь)" нее Доказательство.
Пусть числа тм то+ 1, ..., гпо+ й — 2 составляют максимальное подмножество множества е, образованного последовательными по модулю п целыми числами. Как указывалось в равд. 8.2, циклический код с корнями а", а'е, ..., а' — ь совпадает с нулевым пространством матрицы Если любая линейная комбинация из !!2 — 1 столбцов матрицы (аааа') ( ааа,+1)л-1 ( в,,)аа-2 ( ' ')" ' (9.2) (ив!в+а!а-2)аа ! (вава+!1 — 2)аа 2 ежа+А -2 не равна нулю, то ясно, что не равна нулю и любая комбинация из 4> — 1 столбцов матрицы Н, и по следствию 3.1 код имеет минимальное расстояние, равное де или больше.
То, что матрица (9.2) обладает указанным свойством, можно увидеть, рассмотрев определитель, составленный из произвольного набора !!2 — 1 различных ее столбцов: (оваа)1а!а 2 ( ааа,+1)1а!а-2 (Оа а)1А-1 (Оваа+!)!а!в ! (ив!в+а!а-2)!а!в — 1 (Оваа+аЬ-2)1а2а-2 (Ова,+а!в-2)1! Вынося из каждого 1-го столбца множитель о а1!а где 1 — произ- вольное число, получаем (9.3) а!22 (1!+!2+ "'+1а!а-1) Это определитель Вандермонда (9.4) Л! Х2 ' ...
Х,' Справедливость равенства (9.4) можно проверить либо непосред- ственными вычислениями, либо с помощью следующего рассуж- дения: 1 1 ... 1 Х2 х х ...х 1 ,1А -2 (О!а!в-2) 1) Если Х; = Хь то определитель равен нулю; отсюда вытекает, что разности Х~ — Х! входят в качестве сомножителей в левую часть равенства (9.4) для всех 1 и 1, и, следовательно, левая часть равенства должна делиться на правую часть равенства. 2) В обеих частях равенства стоят многочлены одной и той же степеяи, которые должны отличаться друг от друга только постоянным множителем.
3) Этот постоянный множитель должен быть равен 1, поскольку коэффициент при 1ХзХь ... Х; ' в обеих частях один и тот же. Таким образом, из равенства (9.3) следует, что, поскольку в определителе О нет совпадающих столбцов, он обязательно отличен от нуля, и, следовательно, не существует линейно зависимых комбинаций нз йь — 1 или меньшего числа столбцов матрицы Н. В соответствии со следствием 3.1 код, являющийся нулевым пространством матрицы Н, имеет минимальное расстояние, равное самое меньшее йь. Ч.
т. д. Следствие 9.1. Циклический код, среди корней которого имеются а', а'+!, ..., а'+!М э', где сь — элемент порядка п,имеет минимальное расстояние, не меньшее дь, если (1,п) =!. Доказательство. Пусть 8 = а!. Поскольку (1,п) = 1, то порядок 8 равен и, н а' можно представить как степень элемента 8, а' = 8 ". Тогда среди корней находятся элементы 8"', 8 '+, ... ..., (! '+ж ' и утверждение следствия 9.1 следует из теоремы 9.1.
Граница БЧХ может быть доказана простым способом, если воспользоваться свойствами ассоциированного многочлена, изложенными в равд. 8.3. Напомним, что для любого кодового слова Ь=(Ь„ьЬ„м...,Ьь) циклического кода над полем ОР(д) существует такой ассоциированный многочлен а(Х) с коэффициентами из поля 6г (д ), что Ь;=а(а), 1=0, 1, ..., и — 1. (9 б) Из теоремы 8.2 следует, что ненулевые члены многочлена а(Х) соответствуют корням проверочного многочлена й(Х). Следовательно, если а ", а ', ..., а '"-" — корни д(Х), то коэффициенты при Х'Ь Х', ..., Х' -" в а(Х) равны нулю.
Если а ' а ..., а'"+" -', но ие а""+" ' являются корнями л(Х), то, поскольку (Х )=(1), а(Х) можно разложить на сомножителн (а (Х)) = (Х~~ ' ') (а' (Х)), где а'(Х) имеет степень, не большую чем п — йь. Таким образом, а(Х) имеет по крайней мере и — йь корней из множества (1,а,... ,а" '). Из равенства (9.5) следует, что кодовое слово Ь(Х) имеет по меньшей мере и — (и — йь) = йь ненулевых компонент, Этим заканчивается второй вывод границы ВЧХ. Граница из теоремы 9.1 применима ко всем циклическим кодам.
Для некоторых же кодов, в частности для БЧХ-кодов, она довольно точна. В равд. 9.3 показано, что для нескольких больших классов БЧХ-кодов она дает истинное значение минимального расстоянии. 9.2. Определение кодов Пусть а — элемент из поля 6Р(д™). При любых заданных значениях то и с(о код, порожденный многочленом д(Х), является БЧХ-кодом тогда и только тогда, когда многочлен ат(Х) являетсв многочленом наименьшей степени над 6г(д), для которого а о, а +', ..., а"'~+"-а — корни. Длина кода равна наименьшему общему кратному порядков корней. За исключением случая, когда задается только один корень а , длина кода п равна порядку е элемента о..
Так как ( аа) — па໠— 1 ( ~ам+ 1) — иамт+а и, следовательно, а" = 1, длина кода и делится на е и и не может быть меньше чем е — порядок элемента а. С другой стороны, если а'= 1, то (аа)'= 1, так что число е делится на порядок каждого элемента аа. Поэтому и не больше е, и, следовательно, и = е. Число проверочных символов и число информационных символов кода можно найти, используя способ, описанный в равд.
8.1, или процедуру из (21, гл. 121 Минимальное расстояние между кодовыми векторами пе меньше величины с(„которая называется конструктивным расстоянием. Наибольшее значение имеют двоичные БЧХ-коды, получающиеся, если в качестве а выбрать примитивный элемент поля 6г(2'") н положить то = 1, а с1о =2то+ 1 '). Тогда вектор ЩХ)) принадлежит коду тогда и только тогда, когда элементы и па сгз аааа являются корнями многочлена 1(Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
