У. Питерсон - Коды, исправляющие ошибки (1267328), страница 72
Текст из файла (страница 72)
В-третьих, могут быть построены коды с символами из бг(д), где д — степень простого числа. Поскольку д-нчные коды можно построить из р-нчных ко- есть пространство строк матрицы, состоящей из всех г-кратных векторных произведений т исходных векторов. Кроме того, нулевое пространство этого кода есть код Рида — Маллера (т — г— — 1)-го порядка. Теперь можно видеть, что точки, соответствующие ненулевым позициям каждого из т исходных векторов, образуют евклидову геометрию размерности т — 1 в ЕО(т,2), т.
е. (т — 1)-мерную плоскость. Пересечение двух различных (и — 1)-мерных плоскостей или представляет собой (т — 2)-мерную плоскость, или является пустым множеством. В то же время векторное произведение, используемое в определении кодов Рида — Маллера, соответствует пересечению плоскостей, сопоставляемых этим векторам. Вследствие этого нулевое пространство кода Рида — Маллера г-го порядка содержит векторы, соответствующие всем (г+ 1)-мерным плоскостям ЕО(т,2). Эти плоскости используются при декодировании по алгоритму Рида и для вывода нижней границы минимального расстояния кодов. Ниже эти рассуждения будут уточнены. Коды Рида — Маллера можно рассматривать как циклические коды с дополнительной общей проверкой на четность, так как порождающая матрица кода первого порядка есть в точности порождающая матрица кода, двойственного к коду Хэмминга с дополнительной обшей проверкой на четность.
Обозначим через 5 операцию циклического сдвига всех символов, за исключением общей проверки на четность. Если Р, и Р,— два вектора кода пер= вого порядка, то пусть дов то послелнее обобщение будет рассмотрЕно после изучения дов, р-ичных кодов. Пусть а — примитивный элемент 6Р(р' ). Тогда любой элемент а! поля может быть представлен следуюшим образом: и!=ам+апа+ ... +а~ и!а где а„ вЂ” элемент поля 6Р(р8). Здесь удобно рассматривать это векторное пространство как т-мерную евклидову геометрию над полем 6Р(р'), т. е. как ЕСт(т, р'). Эта геометрия содержит р' ' точек у„каждая из которых представляется координатным вектором аг-— -(азь ап, ..., а< пг).
Пусть через Ь обозначен элемент поля 6Р(р'). Тогда произведение Ьа! определяется обычным образом как (Ьам, Ьам,..., Ьаа п1). Для двух данных векторов ах и а; существует р' точек, координатные векторы которых имеют вид аз+ Ьав Это множество точек называется прямой линией или одномерной плоскостью. Если ам а, и аз линейно независимы, т. е. не все лежат на одной прямой, то множество рм точек, координатные векторы которых имеют вид аз+ Ь,а~+ Ьзаь образует двумерную плоскость, или просто плоскость в ЕО(т,р').
Вообще множество точек, каждая из которых является линейной комбинацией г+1 точек, не принадлежащих одновременно никакой (г — 1) -мерной плоскости, образует г-мерную плоскость. Теперь ненулевые элементы 6Р(р ') можно рассматривать как номера позиций символов циклического кода длины р' — 1 над 6Р(р). Любая г-мериая плоскость в ЕО(т',Р'), не содержащая нулевой точки, которая соответствует обшей проверке на четность, может быть сопоставлена многочлену в алгебре многочленов по ЬП3 модулю Х' — 1.
Этот многочлен будет иметь коэффициенты, равные 1, в позициях, соответствующих р'" точкам этой плоскости, и О в остальных случаях. Циклический ЕО-код порядка г и длины р' — 1 с символами из 6Р(Р) определяется как наибольший циклический код, нулевое пространство которого содержит многочлены, соответствующие всем (г+ !)-мерным плоскостям евклидовой геометрии Е6(т,р'), не проходящим через нулевую точку. Эти плоскости, как мы скоро увидим, полезны при построении алгоритма исправления случайных ошибок. О любом ЕО-коде может быть задано несколько вопросов. Каков его порождающий многочлен? Каково его минимальное расстояние? Как он декодируется? Ответы на зти вопросы даются ниже.
Если могут быть определены корни проверочного многочлена й(Х), то сразу находится и порождающий многочлен циклического (10.6) Любая (с+1)-мерная плоскость состоит из р'«'+П точек, номера позиций которых удовлетворяют соотношениям р«+ Е+ 8 р' — 1, а! — и~о+ ~««п!! + ~««п~! «,=О, 1,..., 1з=О, 1, ..., (10.6) «,+, — — О, 1, ..., р' — 1, где р — примитивный элемент поля 6Р(р') и с«'! — линейно независимые элементы поля 6Р(р'ы), как указано выше. В дальнейшем будем считать, что плоскость не содержит нулевой точки. Пусть 1(Х) — многочлен, соответствующий этой плоскости. Если а! — корень 1(Х), то ) (и!) ~ (а!)! О, (10.Т) где суммирование проводится по всем р'«"+!) значениям 1, удовлетворяющим уравнению (10.6).
Теперь рассмотрим сумму У(п!)= 2' (и'а ( (1««пе! (- . -)-(1«т+«не~+!)! (10 6) ~1' «2' ''" ~«+! Разложение этого многочлена по степеням дает (и!) '~~«~ '~ (п«о) ь (~««п !)"! (()«!+«и'ю+!) '+' (10 9) ! ь где йь+ й! + ° ° + !!г+! (10.10) Это весьма громоздкое выражение может быть значительно упрощено с помощью следующей леммы: Лемма 10.1. Пусть (1 — примитивный элемент 6Р(р'). Тогда — — й='п(р' — 1), «-ь ~ О, в противном случае, еде символ р обозначает нулевой элемент поля 6Р(р'> кода. Пусть с« — некоторый примитивный элемент 6Р(р"").
Если у«,уь ..., уь — корни всех многочленов, соответствующих (г+ 1)- мерным плоскостям, то каждый нз этих корней будет корнем по- линома й(Х) и, следовательно, Двсненее пред- ставление еь !Э 00001 ! 000101 000111 00!001 001111 010101 011011 з б 7 9 15 21 27 на р большее число раз. чем я! (и — й)! Таким образом, С„" =— Ошоб р тогда и только тогда, когда (п — гв„) > (й — гве) + (и — И вЂ” а„,), или, другими словами, тогда и только тогда, когда гвн < год+ гв„— ь. Но из и; ( й! (при некотором !) вытекает неравенство рс„ч ве+ + рв„~, и обратно.
Поэтому для того чтобы С не было сравнимо с нулем по модулю р, необходимо и достаточно, чтобы п; й! для всех !. В терминах раздела 3.5 С„"чй 0 шо!1 р тогда и только тогда, когда й — потомок п при представлении этих чисел по основанию р. Ч. т. д. Теперь мультиномиальный коэффициент в (10.12) может быть выражен следующим образом: ,и,+с(р'- 1 (с')(с,' )(с,*, е*-е)" (,—,,-х,,и — !) т-'! Это произведение не равно нулю по модулю р тогда и только тогда, когда каждый сомножитель отличен от нуля. Поэтому для того, чтобы а' было корнем д(Х), представление ! по основанию р должно содержать не менее (г+ 1) чисел, кратных р' — 1.
В про- тивном случае при некотором 1 число й!(р' — 1) не будет потомком 1 — Ар — ~, А! (р' — 1) и, согласно лемме 10.2, (1+ 1)-й множитель в=1 в (10.13) равен нулю, а а! будет корнем й(Х). Ч. т. д. Теорема 10.4. Пусть через а обозначен некоторый примитивный элемент ПР(ре ). Проверочный полинам Ь(Х) евклидово-геометри- ческого кода г-го порядка имеет среди своих корней а', если гв,(1) ~ г.
При этом з-вес числа ! (обозначаемый через гв,(1)) определяется как наибольшее число кратных р- — 1, содержащих- ся в представлении ! по основанию р. Пример. В следую1цей таблице приводится 2-вес различных зна- чений гдля р= э=2 и т=3. 8т Теорема 10.4 гарантирует, что некоторые корни Хя — 1 буут корнями «((Х).
Но из нее не следует, что не будут корнями й(Х) также и другие корни Х вЂ” 1„ однако в равд. 10.8 показано, что Ь(Х) не имеет других корней. Теорема 10.4 дает метод определения числа й информационных символов ЕС(-кода. Оказалось, что комбинаторное выражение для этой границы получить трудно. Однако для ! = и — 2 несколькими исследователями, включая Смита 1282] и Мак-Уильямс и Манна (197), был доказан следующий результат: А=и — (С !) +1. Здесь й обозначает нижнюю границу для обсужденного выше й.
Б равд. 5,5 были рассмотрены коды Рида — Маллера. Код «-го порядка был определен как пространство строк матрицы, й строк которой являются векторами инцидентности некоторых (л) — «)- мерных плоскостей ЕО (щ, 2) . Было показано, что, поскольку (т — «)-мерная плоскость и («+ Ц-мерная плоскость либо не пересекаются вовсе, либо имеют по крайней мере две общие точки, любая («+ Ц-мерная плоскость содержится в нулевом пространстве кода размерности и — й. Таким образом, коды Рида — Маллера без символа, соответствующего нулевой точке, эквивалентны ЕС!-кодам с з = 1 и р = 2. ).,ля этих кодов А=~С . Нижняя граница минимального расстояния ЕО-кодов определяется из границы БЧХ, Каждый элемент 6Р(р' ), для которого представление ! по основанию р содержит «+1 или более чисел, кратных р' — 1, есть корень п(Х). Рассмотрим представление ! по основанию р. Число ц р (-- — )+(+0+ ,( ( ц з(т — г) — ! ( ! (р — цр~(т ! и+(+(р — 2)р (т ~ !)+ 1„( ц т(т — ~+!) — ! (! ( ц ~ь(т — г)+! + (р ц р~(т — !) + + (р црвт — ! )„( (р !)рв(т — !)— р5т ря(т-~ — ) — р (т «з)+! (10.14) имеет з-вес, равный «.
Каждая из последних «строк (10.14) кратна множителю р' — 1, а две первые строки не кратны ему. Однако гели бы какой-либо коэффициент при р', 0 ~ ! ( з(т' — !' — 2) не равнялся нулю, то з-вес был бы не менее «+ 1. Тогда это слагаеиое и верхние две строки (10 14) содержали бы по крайней мере здно кратное р' — 1. Это прямо следует из леммы 10.3. Лемма 103 (183). Пусть а= аь+а~р +игры+ ° °,+аьр"'. Обозначим р'-вес числа а через гв,.
(а) = ~ а,. Тогда число а делится на р' — 1 тогда и только тогда, когда число ш (а) делится на р' — 1. Доказательство. Рассмотрим а — ш (а)= — а,(р' — 1)+а,(ры — 1)+ ... +а„(р'* — 1). (10.15) Отсюда лемма следует непосредственно. Если на р' — 1 делится одно нз слагаемых в левой части уравнения (10.15), то на него делится и другое слагаемое. Ч.т. д. Таким образом, в этом случае всегда можно найти число а, которое являйтся потомком этого слагаемого и верхних двух строк табл.
10.14 и которое делится на р' — !. Так как рьь — ри"" †' и†рн~ ' гм' есть наибольшая степень корня й(Х), то д(Х) должен иметь рн -'-П +рн †' †'н' — 2 последовательных корней. Поэтому для ЕО-кода над Ог" (р) порядка т и длины р"" — 1 д) двчх — р~оь-~-и + р (~-~-и+! (10.16) В общем случае не известно, когда в (10.16) имеет место равенство. Однако многие короткие двоичные коды и коды Рида— Маллера удовлетворяют этому условию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
