У. Питерсон - Коды, исправляющие ошибки (1267328), страница 74
Текст из файла (страница 74)
Остальная часть этого раздела посвящается определенисо порождающего многочлена Рб-кодов, минимальных расс гояний таких кодов и описанию пропедуры декодирования для них. Методы исследования таких кодов аналогичны методам исследования ЕП- кодов, изложенным в разя. 10.2. Пусть через 1(Х) обозначен многочлен в алгебре многочленов по модулю Х" — 1, соответствующий г-мерной плоскости в р(1(лс, р ), и пусть са — некоторый примитивный корень СсГ(рь"+сс ). Тогда для того, чтобы а был корнем )(Х), необходимо, чтобы и делилось на его порядок, и поэтому и должно делиться на р' — 1. Если теперь пс(а ') — корень 1'(Х), то Мпс"- !) = Х (пс ( '- ))с = О.
где сумма берется по всем ри'1+ р'(" — '1+ ...+ р''+1 значениям 1, соответствуюсцим точкам г-мерной плоскости. Но ) (и) — ~~с ((!сап а+ (1сспгс + ... + ()сгпаг), (И! 21) са, с ..... с так как каждая точка соответствует р' — 1 элементам сгг" (р4"'+сс). Таким образом, а'(а — '! будет корнем )(Х) тогда и только тогда, когда (р~асс а+ к сп с 1 „.. -1 — (1~ге г) ~а с! =О. (10.22) са сг '" Раскрывая скобки в этом выражении, получаем ~рсапаа)ьа(бсспас)"с ...
((1сгпаг)аг, (10 23) с ь где Ьа + йс + " + Ь, = ((ра — 1). Теперь по.лемме 10.1 эта сумма равна нулю, если не все й, имеют вид Ь„=й,(ра — 1), 0:- "о(г. Поэтому выражение (10.23) можно записать иначе: Х С (ра — 1)! 1(са(р 1)1(Сс (р — 1!11." (а (р — 111 аа(с ) 1 с(а ) гг(а Отсюда, учитывая лемму 10.2, непосредственно выводим, что все эти многочленные коэффициенты равны нулю по модулю р, если 1(р* — ц не равно нулю и в его представлении по основанию р есть сумма не менее (г+1) кратных р' — 1 (при 1=0 сумма (10.22) равна 1, так как ае не может быть корнем ](Х)). Эти рассуждения могут быть сформулированы в виде следующей теоремы: Теорема 10.6.
Пусть а — некоторый примитивный элемент Г2р(р"( !]). Тогда а!(» — '1, (чь О, будет корнем проверочного многочлена проективно-геометр(ьческого кода порядка г и длины п = р' + р'( -')+ ... + р'+ 1 при условии, что (в,(1(р' — Ц) ~ и В равд. 10.6 показано, что Ь(Х) имеет только корни з-веса г или меньше. Таким образом, теорема 10.6 дает с(юсоб определения числа информационных символов РО-кода; нужно только найти веса и корней Х" — 1, Однако комбинаторное выражение для этой границы найти трудно. Исключением является случай, когда г= и — 1.
Для этих разностных кодов Грехем и Мак-Уильямс [126) показали, что граница достигается и что и — Ь=(С +р 1) +1. Когда р = 2 и з = 1, РО-коды сводятся к циклическим кодам Рида — Маллера. В частности, они двойственны циклическим кодам Рида — Маллера, укороченным на один символ. Для этих кодов Ь= ЕС'„, г ! что следует из результатов равд. 5.5.
Применим нижнюю границу минимального расстояния ВЧХ к РО-кодам. Каждый элемент ]гг(рк +')) вида а'1» — '),степень которого в представлении по основанию р содержит »+ 1 или больше кратных р' — 1, есть корень д(Х), так же как и а». Теперь число з (р црг(т — г+2]-1+ + (р црг(т — г+!)+1+ (р црб(т — г+!)+ („Ц г(т-г+3)-1+ + ( Ц г(т-г+2)+1+ ( Црг(т-г+2) 1 +(р — цр' '" '+ " +(р — цр' "+ + (р Цргт — (рг(т+1) Ц (рг(т-г+1] Ц делится на р' — 1 и имеет е-вес, равный г. Следовательно, а" — корень Ь(Х).
Прибавление любого кратного многочлену р' — 1 к о увеличивает его е-вес по крайней мере до г + 1, так как з-вес прибавляемого числа не меньше 1. Таким образом, а" — наибольший корень Ь(Х), и если о (1~ р'(т+1) и 1 кратво р' — 1, то а( — ко- рень и(Х). Число последовательных корней в этом интервале равно Ю вЂ” 1)/(р' — 1). Поскольку ав также является корнем ьг(Х), то отсюда следует, что Рб-код над СгГ(р) порядка» и длины („,.( +)) 1)/(р' — 1) имеет в (вг — г+В ) д~)йвчх= в ) +!. (10.24) (рввг+ рв(вг-и+ + Рв + !) (Хгв(г-и+/тв(г — в)+ +/)в+ ]) Х)вг Положим дмь = Х+ 1, тогда нз (10.24) следует )г в (вг-г+!) дмь= ! +1=йвчх. (10.25) Так как»-мерные плоскости уже известны, (» — 1)-мерные плоскости могут быть определены с помощью одного уровня мажоритарной логики при условии, что произошло не более 1(двчх — 1)/21 ошибок.
Аналогично могут быть определены (» — 2)-мерные плоскости. Выражение (10.25) показывает, что число ортогональных проверочных сумм растет с уменьшением размерности. Следовательно, для определения 0-мерных плоскостей необходимо» вЂ” 1 шагов. Теорема 10.7. Х/роективно-геометрический циклический код длины (Р" +') — 1) /(р' — 1) и порядка» (нулевое пространство которого Известно, что для двоичных кодов с и .73 и кодов Рида— Маллера в (10.24) имеет место равенство. Для более длинных кодов этот вопрос остается пока открытым, С помощью алгоритма Рида Р(л-кодом можно исправить ((двчх — 1)/2) или меаьшеечисло слУчайных ошибок. Ключевой момент состоит в том, что»-мерная плоскость и точка вне этой плоскости определяют (»+1)-мерную плоскость.
Это следует непосредственно из определения »-мерной плоскости. Как и ранее, для ЕС-кодов декодер может определить проверочные суммы, соответствующие всем»-мерным плоскостям. Множество Х сумм, соответствующих»-мерным плоскостям, пересекающимся по некоторой (» — 1)-мерной плоскости, ортогонально относительно суммы, соответствующей этой (» — 1)-мерной плоскости.
В (» — 1) -мерной плоскости лежит р ("-)) + рва-в) + ... + р*+! точек и р'" точек принадлежат каждой из Х»-мерных плоскостей, не лежащих на этой (» — 1)-мерной плоскости. Каждая из указанных Хр' точек может лежать только на одной такой !)лоскости, и каждая точка пространства, лежащая вне центральной (» — 1)-мерной плоскости, принадлежит одной из этих»-мерных плоскостей. Следовательно, содержит все г-мерные плоскости РСе(пт, ре)1 допускает мажоритар- ное декодирование за г шагов при условии, что произошло не более 1(г(вчх — 1)721 ошибок, где с(вчх определяется выражением (10.25), Таблица 10.2.
Параметры двоичных проектнвно- геометрических кодов с ~((85. Все г-мерные плоскости лежат в нулевом пространстве кода г-го порядка. Коды с а 1 эквивалентны кодам, двойственным кодам Рида — Маллера, укороченным на один символ. Все коды с е((31 — вто коды БЧХ Геометрия ро (т. ря) Порядок Г лнчх 21 31 73 85 В табл. 10.2 приведен список двоичных проективно-геометрических кодов с и ( 85. Некоторые модифицированные процедуры декодирования, пригодные для этих Рб-кодов, описываются в равд. 10.4.
Пример. Двоичный циклический (7,3)-код есть Рб-код, основанный на проективной геометрии Рб(2, 2). Код имеет порядок г = 1, и все 1-мерные плоскости Рб(2, 2) принадлежат нулевому пространству кода. По теореме 10.6 порождающий многочлен кода имеет корни а', такие, что 1 = 0 или все 1 в двоичном представлении не менее 2. Таким образом, ао, ав, осе и ав — корни д(Х). Если в качестве а выбрать примитивный корень многочлена Ха+Ха+1, то а(Х) = Хч+ Ха+ Хв+ 1 и й(Х) Ха+Хе 1 Согласно теореме 10.7, код может быть декодирован за г = 1 шагов. Для построения декодера необходимо выбрать р '+ +р( ')'+ ... +р'+1= 7 одномерных плоскостей, принадлежащих нулевому пространству.
Их можно представить следующим образом: 3 10 4 11 25 15 5 56 41 21 45 68 24 4 4 8 6 4 8 16 4 8 16 32 1О 6 22 РП (2, 2) Рй (3, 2) РП (3, 2) Рб (2, 2е) РСе (4, 2) РП (4, 2) РП (4, 2) РП (5. 2) РСе (5, 2) РСе (5, 2) РО (5, 2) РП (2, в.) РП (3, 2е) РП (3, 2е) 1 2 1 1 3 2 1 3 2 1 1 2 1 ТочКи Плоскости иифоривции а' а' а" проверКи а' а' а' а' Ясно, что плоскости 1, 2 и 4 ортогональны относительно точки сев, соответствующей первому информационному символу, поскольку было осуществлено предварительное умножение на Хе. Отсюда следует, что е(мь = с(ве~х = 4. Декодер для этого кода показан на фнг.
10.2, Выше рассматривались коды с символами из стР(р). Коды с символами из более общего поля 6Р(д) исследуются в равд. 10.6. 10.4. Модификации основного алгоритма мажоритарного декодирования Алгебраическая процедура декодирования БЧХ-кодов позволяет осуществлять декодирование в пределах границы, задаваемой кодовым расстоянием, т. е. исправляются все ошибки веса 1 илн меньше и не исправляется ни одна ошибка большего веса. В то же время мажоритарное декодирование дает возможность исправлять также и многие комбинации ошибок веса, большего й Использование обратной свизи Предположим, что код, исправляющий 1 ошибок, допускает мажоритарное декодирование и произошло (1+1) ошибок, одна из которых исказила первый информационный символ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
