У. Питерсон - Коды, исправляющие ошибки (1267328), страница 73
Текст из файла (страница 73)
Используя (г+ 1)-шаговый мажоритарный декодер, реализующий алгоритм Рида, который развит для кодов Маллера, можно исправлять прн помощи ЕО-кодов ((двчх — 1)/2) случайных ошибок. Ключевая идея состоит в том, что проверочные суммы, соответствующие (г+ 1)-мерным плоскостям, которые пересекаются по данной т-мерной плоскости, ортогональны относительно проверочной суммы, соответствующей этой г-мерной плоскости.
Так как проверочные суммы, соответствующие всем (с+1)-мерным плоскостям, декодеру известны, то все проверочные суммы, соответствующие т-мерным плоскостям, можно определить с помощью одного уровня мажоритарной логики. Теперь рассмотрим полную геометрию ЕО(т, р'), включаюшую нулевую точку. Пусть Х+ 1 обозначает число (г+ 1)-мерных плоскостей, пересекающихся по данной т-мерной плоскости. Это пространство состоит из р' точек, из которых р точек лежат на г-мерной плоскости. В каждой из (г+ 1)-мерных плоскостей, пере- Из теоремы 10.1 следует, что если произошло не более 1(с!мь — 1)/2) ошибок, то декодер может правильно определить проверочные суммы, соответствующие всем г-мерным плоскостям.
Параметр Х можно рассматривать как функцию размерности центральной г-мерной плоскости. Из выражения (10.17) видно, что эта функция монотонно возрастающая. Таким образом, декодер может найти по крайней мере Х+ 1 г-мерных плоскостей, ортогональных относительно каждой (г — 1)-мерной плоскости, по крайней мере Х+! (г — 1) -мерных плоскостей, ортогональных относительно каждой (г — 2)-мерной плоскости, и т.
д. Если произошло не более ((дмь — 1)/2) ошибок, все решения будут правильными и 0-мерные плоскости, т. е. ошибочные символы, будут определены на (г+ 1)-м шаге мажоритарного декодирования. Теорема 10.5. Евклидова-геометрический ииклический код длины р' и порядка г (нулевое пространство которого содержит все (с+1)-мерные плоскости ЕО(т, р')) люжет быть мажоритарно декодирован за (г+ 1) шагов при условии, что произошло не более 1(с!мь — 1)/2) ошибок, где Р «(ы Г] ймь = Р (10.18) При р= 2 и с= т — 2 или при р = 2 н в = 1 имеет места равенство ймь = Нвчх. Для всех других значений параметров ймь ( йвчх, хотя разница относительно мала. Список двоичных евклидова-геометрическнх кодов для и (63 приведен в табл.
!0.1. В равд. 10.4 представлены некоторые модификации описанного выше основного алгоритма мажоритарного декодировании, которые применимы к ЕО-кодам, кающихся по данной г-мерной плоскости, содержится рк"+и — р~ чек, лежащих вне г-мерной плоскости. Вне г-мерной плоскости нет нн одной точки, которая может принадлежать более чем одной из этих (г+ 1)-мерных плоскостей, так как иначе какне-то две плоскости совместились бы. Кроме того, каждая точка должна лежать на одной нз (г+1)-мерных плоскостей, так как эта точка н «центральная» г-мерная плоскость полностью определяют („-» 1)-мерную плоскость, содержащую г-мерную плоскость.
Таким образом, (Х+1) (рк'+и — р"") должно быть равно р' — р'"— числу точек, лежащих вне «центральной» г-мерной плоскости. Одна из этих (г+1)-мерных плоскостей проходит через нулевую точку и поэтому не принадлежит нулевому пространству ЕО-кода. Положим амь= Х+1, тогда 8 (т — м Х+! =Ад. = . = р«(ы- -и+ рь(т- -м+ рь ! (10.17) Таблица 10.!.
Параметры даоичных еиклидоао-геометрических кодов с л~(63. Все (г+ !)-мерные плоскости принадлежат нулевому пространстау кода порядка и. Все коды с и =1 эквиаалентны кодам Рида — Маллера с одним опуцгеиным символом. Все коды с я~~31 — это коды БЧХ. Для всех унааанных кодов й равно нижней границе, определяемой теоремой !ОА Геометрия ио (ти, те) Порядок и лвчх 15 31 Пример. Двоичный (7,4)-код Хэмминга есть ЕСт-код, связанная с ним геометрия — ЕСт(3, 2), а порядок его г = 1. Пусть сс обозначает корень Ха+ Х+ 1.
Ненулевые элементы поля: о» и' и, а'=0 а'=0 ц'= 1 а'=0 а"=1 ар=! ае = 1 ат=ао 0 1 1 0 0 О 1 1 1 0 1 1 0 1 Нулевому пространству кода принадлежат все 2-мерные плоскости, н по теореме 10.4 корни сс' многочлена Ь(Х) такие, что вес 1 в двоичном представлении равен 0 или 1. Таким образом, корня й(Х) равны ссо я', ат н сс' н Ь(Х) = Ха+ Ха+ Ха+ 1 Согласно теореме 10.5, код может быть декодирован за два шага. Для осуществления второго шага должны быть определены две 1-мерные плоскости, ортогональные относительно ошибочного символа в позиции, соответствующей Хт.
(Напомним, что декодер производит предварительное умножение на Ха.) Эти плоскости могут быть найдены, если построить две 2-мерные плоскости, орто- 1 11 5 1 26 !6 6 1 57 48 42 37 22 13 7 1 3 3 5 7 15 3 7 15 31 3 5 7 9 15 23 31 63 3 7 3 5 7 15 3 7 15 31 3 5 7 9 15 21 31 63 Е0(З, 2) Е0(З, 2) Е0(4, 2) Е0(2, 2) Е0(4, 2) Е0(4, 2) Е0 (5, 2) Е0(5, 2) Е0(5, 2) Е0(5, 2) Е0(6, 2) Е0(З, 2Я) Е0(6, 2) Е0(2' 2з) Е0(6, 2) Е0(3, 2Я) Е0(6, 2) Е0(6, 2) точки Плоскости вкеоривикл ас М ас ас проверки а' а' ас 101! 0101 00! 0 1001 1! 00 1110 О 1 1! 100 1 1 0 1 1! 011 101 0 ! 0 001 Плоскости ! и 2 пересекаются по прямой, проходящей через точки ак и а'.
Плоскости 3 и 5 пересекаются по прямой, проходящей через точки а' и ае. Эти две прямые, конечно, пересекаются в точке ас, которая соответствует ошибочному символу на первой информационной позиции, так как было осуществлено предварительное умножение на Хк. Отсюда следует, что г!мь = 3. Декодер для этого кода рассмотрен в примере, следующим за теоремой 10.3, н показан на фиг. 10.3. Выше исследовались коды с символами из 6Р(р).
Более общий д-ичный случай рассмотрен в равд. 10.6. 1О.З. Проективно-геометрические коды В евклидовой геометрии две прямые или плоскости могут быть параллельны. Можно, однако, элементы 6Р(р') выбрать таким образом, чтобы построить геометрию, в которой нет параллельных прямых. 17роектиеная геометрия (РО) размерности и над 6Р(р'), обозначаемая через РО(т, р'), может быть построена из 6Р(р!"'+!!') следующим образом. Точке (и) геометрии становится в соответствие множество ненулевых элементов поля (а) =а, ар, арх, ..., а))р где а — ненулевой элемент 6Р(р! +!и) и р — примитивный элемент 6Р(р')').
Число определенных таким образом точек равно !вс+ П л — -р-Ср~ -О +, +л.+!. Пва! ') Полное н (41, ззт]. ) !!одное "вложение теории нроектннных геометрий содержится н книгах тональные относительно каждой из этих 1-мерных плоскостей. Ну- левое пространство кода содержит восемь 7-мерных векторов и семь из них — двумерные плоскости; Пусть через а обозначен примитивный элемент поля 6Г(рк'"+'>). Если (а") и (а") обозначают любые две различные точки геометрии, то прямая (1-мерная плоскость) определяется как множество точек ф"и" + !уа"), где йп и ф — всевозможные пары одновременно не равных нулю элементов 6Г(р'). При этом получится точно рм — 1 элементов 6Е(рк +'>) и р' — 1 из них всегда представляют одну точку. Таким образом, прямая состоит из р'+1 точек. Аналогично 2-мерная плоскость состоит из точек (~"а ° + (>'а" + !>ьа") при условии, что точки (а")„(и") и (а") не лежат на одной прямой, т.
е. линейно независимы. Снова (>> не могут быть все одновременно равны нулю. Вообще г-мерная плоскость определяется как множество точек 1„(> 0а "+ >> 'а" + ... + !3'~а г), где точки (а 0), (а '), ..., (ап~) линейно независимы.
Элементы р> принимают точно р'~"+» — 1 значений, так как одновременный выбор нулей запрешен. Отсюда следует, что г-мерная плоскость имеет р" +»4"-»+ ... + р'+1 точек. В проективной геометрии для любых двух различных точек А и В существует одна и только одна прямая, на которой находятся обе точки А и В. Если А, В и С не лежат на одной прямой и прямая Т. содержит точку В прямой АВ и точку Е прямой ВС, но не содержит А или В или С, то Т, содержит точку Е на прямой СА, т. е. две прямые не могут быть параллельными. Подобно евклидово-геометрическим кодам, проективно-геометрические коды являются обобщением кодов Рида — Маллера. Снова, как и в равд.
10.2, будем рассматривать коды с символами из 6Е(р). Удобно сопоставлять каждой точке РО(т', р") одну из позиций символов циклического кода длины и = р' + р'< -'>+ ... ... + р'+ 1. В частности, позиция символа, соответствующая Х', сопоставляется точке (>х>), ! = (>, 1, 2, ..., п — !.
В этом контексте г-мерная плоскость может быть сопоставлена набору длины и, который имеет единицы в разрядах, соответствующих точкам плоскости, и нули в остальных разрядах. Как обычно, этот набор длины и представляется как многочлен над 6Г(р) в алгебре много- членов по модулю Х" — !. Теперь каждый циклический сдвиг многочлена, соответствующего некоторой г-мерной плоскости, приводит к многочлену, соответствующему другой г-мерной плоскости. Если (а"), (а'~), ... ",( ) е х а ~> — линейно независимые точки первоначальной плоскости, то точки (а'~+ >), (а'~+'), ..., (а + >) определяют новую плоскость.
Это рассуждение подсказывает следуюшее определение класса циклических кодов. Проективно- геометрический циклический код порядка г и длины п = р "+ р4"'-ч>+ ... + р'+ 1 с символами из 6Р(р) определяется как наибольший циклический код, нулевое пространство которого содержит многочлены, соответствующие всем г-мерным лоск стим РСс(лс р').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
