У. Питерсон - Коды, исправляющие ошибки (1267328), страница 76
Текст из файла (страница 76)
д. Можно снова применить такой же прием и еще больше сократить число шагов. Пример. Пусть р = 2, тз = 12. Рассмотрим код Рида — Маллера 1О-го порядка. Соответствующая геометрия есть ЕО (12, 2), и все 11-мерные плоскости геометрии принадлежат нулевому пространству кода. Если известны 11-мерные плоскости, то 10-мерные плоскости определяются обычным способом. Так как 1 = (10,12) = = 2, эти плоскости можно рассматривать как 5-мерные плоскости в ЕО(6,2х). Поэтому на следующем шаге определяются 4-мерные плоскости ЕО(6,2в) (или 8-мерные плоскости первоначальной геометрии).
Новые с и т также не будут взаимно простыми, (4,6)=2, и 4-мерные плоскости ЕО(6,2 ) можно рассматривать как 2-мерные плоскости ЕО(3,2'). Тогда третий шаг декодирования состоит в определении 1-мерных плоскостей ЕО(3,2х) (или 4-мерных плоскостей первоначальной геометрии). Четвертый и последний шаги — это определение 0-мерных плоскостей ЕО(3,2') из 1-мерных.
Описанная процедура представлена на следующей схеме: 10 Схема Бвяадираваякя для ЕБ-п йвя-яе9ов длаям409Б Числа на схеме обозначают размерности плоскостей ЕО(12,2). Описанной процедуре декодирования на схеме соответствует прямая линия, соединяющая точки 10, 8, 4, О. Так как первый шаг при декодировании любого ЕО- или РМ-кода всегда задан, то на схеме он не показан. Таким образом, первоначальное декодирование в 11 шагов сводится к 4 шагам, Остальные линии на схеме изображают процедуры декодирования для других КМ- и Еб-кодов.
Например, декодирование КМ-кода 7-го порядка, нулевое пространство которого содержит 8-мерные плоскости, задается прямой 7 — б — О. Универсальный алгоритм мажоритарного декодироваввк длв линейных кодов [>23, 28Ц Любые с( — ! столбцов проверочной матрицы кода с минимальным расстоянием с(, согласно следствию 3.1, являются линейно независимыми. Поэтому в нулевом пространстве кода имеются с( — 1 векторов 1рп б>в ...11,>в л> н> 0 ...О, ' Р'" Р " Р""-" О О' (1029) 1 ры» > /Ъш,>т... бм» <„л> 0 0...
ал >, где рг и ссс — элементы 6Г(д). Сопоставление позиций н-разрядных строк матрицы (10.29) с позициями символов кода совершенно произвольно, поскольку следствие 3.1 справедливо для любых с! — 1 столбцов матрицы Н. Теперь ошибочный символ на первой позиции может быть правильно определен, если произошло не более ((с( — 1)/2) ошибок. Из матрицы (10.29) решением по большинству можно найти обобщенную проверочную сумму относительно первого символа и любых п — с( других символов. (Обобп!аннан проверочная сумма относительно символа у и п — с( других символов определяется как проверочная сумма, которая дает значение ошибочного символа на позиции у при условии, что на этих и — с( позициях ошибок не произошло.) Так как и — с( других символов в первоначальных обобщенных проверочных суммах выбираются произвольно н поэтому их можно выбрать так, чтобы у всех сумм а — с( — ! символов были общими, то из с> — 1 обобщенных проверочных сумм относительно у и и — с! других символов решением по большинству можно определить обобщенную проверочную сумму относительно у и и — с! — 1 других символов, как и прежде, при любом выборе этих и — с( — 1 символов.
Для того чтобы эти суммы были ортогональными относительно у н и — с! — 1 других символов, последние символы во всех суммах следует выбрать различными. Применяя эту редукцию и — с! раз, получим множество обычных проверочных сумм, ортогональных относительно у. Для циклического кода этого достаточно, для произвольного же линейного кода описанный прием должен повториться для каждого из й информационных символов. Очевидно, что для всех кодов, кроме простейших, этот метод и~целесообразен для реализации. Так как сложность алгоритма эстет экспоненциально с п — г( (и с большой экспонентой), то ожность его реализации примерно такая же, как и метода проб и ошибок.
10.5. Обобщенные коды ри 1= $0+ 1!ч+ ьА'+ . +1 -1д" '. (10.30) Для упрощения записи многочленов от неизвестных Хь ..., Х будем использовать следующее обозначение: (10.31) В этих обозначениях произвольный многочлен степени, меныпей д, записывается в виде ~(х)=~с,х"'. (10.32) Теперь определим д-ичный вес целого числа 1 как (Р' (1)=1О+ 1~+ ... + Е По лемме 10.3 1 делится на и — 1 тогда и только В'ч (1) делится на д — 1, Пусть а — примитивный элемент ОР(д"'). Тогда левой элемент этого поля может быть представлен в т — 1 а= ~ пап, ! ~ о (10.33) тогда, когда любой нену- виде (10.34) В этом разделе дается обобщение понятия ассоциированных многочленов, рассмотренного в равд.
8.3, и на его основе вводится естественное обобщение кодов Рида — Келлера. В теореме 10.9 эти коды описываются с использованием корней порождающих их многочленов, а в теореме 10.10 дается их точный минимальный вес, Из теоремы 10.11 видно„что для одного важного подкласса этих кодов слова минимального веса являются векторами инцидентности евклидовых плоскостей. Для другого важного подкласса, как показывает теорема 10.12, слова минимального веса суть векторы инцидентности проективных подпространств. В следующем разделе эти результаты используются для того, чтобы показать, что евклидово-геометрические и проективно-геометрические коды могут рассматриваться в новой еще более абстрактной постановке. Пусть через Х обозначен вектор (Хо,Хь ..., Х 1).
Будем представлять любое целое 1 ~ д в системе счисления по основанию и в виде где элементы аи принадлежат 6Р(д). Положим А~ —— — (аор ан, ..., аьо О 1). (10.36) Будем называть А; координатным вектором элемента Ы При этом каждый ненулевой набор длины по с компонентами из 6Р(а) соответствует некоторому 1, 0 (1 ( д — 1. Таким образом, чтобы получить все возможные значения некоторого многочлена, можно вместо Х =- (Хо, Хь..., Х ~) подставить векторы Аь Определим обоби(енпые коды Рида — Миллера следующим образом. Пусть Ь вЂ” делитель д — 1 и п =(д — 1)/Ь.
Рассмотрим множество Р(т, о/, р., Ь) многочленов /(Х) = ХС;ХО, удовлетворяющих следующим условиям: 1) С; — некоторый элемент 6Р(д); Я) /<ды 3) )У'о(/) делится на Ь и для каждого ненулевого 1 не больше р,Ь. Можно легко проверить, что это множество многочленов образует векторное пространство над 6Р(а). Размерность этого пространства равна числу членов /(Х), которые могут быть ненулевыми, т. е. числу целых, меньших д — 1, веса которых делятся на Ь и меньше или равны 1оЬ. Для каждого многочлена /(Х) построим следующий вектор: чЯ =1/(Ао), /(А1), /(Ао), ..., /(А„,)). (10.36) (!0.37) 1-о Для доказательства требуются три леммы. Лемма 10.4. Пусть со — примитивный элемент 6Р(д).
Тогда Так как связь между /(Х) и ч(/) линейная, то множество векторов ч(/), соответствующих всем /(Х) в пространстве Р(т,а,р„Ь), также образует векторное надпространство, и это подпространство есть обобщенный код Рида — Маллера. Из следующей теоремы видно, что, задав ч(/), можно вычислить /(Х).
Из этого следует, что между векторами ч(/) и много- членами /(Х) существует взаимно однозначное соответствие и поэтому два пространства имеют одну и ту же размерность. п — 1 Теорема 10.8. Пусть /(Х) = 3' С;Х<0 принадлежат Р(т, 4, 1о, Ь) е о и ч(/) =- (/(Ао), /(А),..., /(А„1)) = (оо, о„..., о„,), где п =(г/ — 1)/Ь. Тогда Доказательство. Напомним, что Х'-' — 1=(Х вЂ” ц~Ха-2+ Х'-'+ ... + Х+1) и все ненулевые элементы !гР(!1) — корни Ха-' — 1. Тогда а — 2 ~(а!)'=Ха '+ Х' '+ ... +Х-1-1~ 2=0, 2-2 если О < 1 < д — 1 ° Далее, а 2+ 12-2+ + 1! -1- 1 = — 1 гпоо(д. Ч.
т. д. Лемма 10.5. !и 1 О, если !-о ), ( — 1), если т Доказательство. т т а — 2 а — 2 л ЛЮ 2 ! 2, ! поги!! а! -о! г-о !-о где 2= !2+!!!г+ ... +! !д" '. Так как множество А! содержит все ненулевые векторы, то в позиции каждой компоненты а2; ненулевой элемент !гР(оу) оказывается о — '(д — 1) раз, а нулевой д — ' — 1 раз. Отбрасывание нулевых слагаемых дает ат-г Т "- А!2! ~ ~.' ) агап!! агт -О ао а! ат — (~ а!о)(~ аг!) ( )' агт-!) где суммирование в каждой сумме а, производится по всем ненулевым элементам ОГ(г1). По лемме 1ОА для каждого отдельного множителя последнего выражения О, если г,<~у — 1, а, ' 1 — 1, если г,=(! — 1.
Отсюда лемма следует непосредственно. Ч. т. д. Лемма 10.6. Если о — 1 делится на Ь и п = (д ' — 1)/Ь и если В'а(!) делится на Ь, то а-! Х, А)2!=О при !'<о — 1, ! о а-! Х А!готт — и( — 1) иди !=д~ — 1. ! о Доказательство. Если а — некого(!ый примитивный элемент 6Р(д'"), то (а'")» п=(а!(» '!)'» =(а» ')"» '(! =1 и, следовательно, а!ь — элемент 6Р(д). Так как а(+ !» — а!»а! то из (!0.34) и (10.35) следует, что А(+»ь а!»А! (!0.38) Поэтому о»-» (» — 01 -! -! (»»х-!У -! ь-! (), 'А~!"= ~, ~, А(!'+х„= ~ ~ (А(а'")"! = (»ы — х!/»-!»-! !»эх и! „ц] А! . »=а (=:» Но так как по предположению ()т (!) делится на Ь, то а» = 1 !» В' (!! и, следовательно, » -2 »-! А((п= ч „~~ А~(п.
(10.39) ! о (-о Отсюда, учитывая, что значение левой части выражения (!0.39) определяется из леммы 10.5, выводим лемму 10.6. Ч. т. д. Приступим теперь к доказательству теоремы. Имеем, что ~,((А!) А(» ' '1=.Я! ), С!А!(!'А((» ' !1=) С! 2 А(» ' +»! ! о (-о (=о По лемме !0.6 вторая сумма равна нулю, исключая случай когда сумма равна — и( — 1)ы. Поэтому » вЂ” 1 Х('(А!) А! ' !1= — а( — 1)" С! (10.40) » и утверждение теоремы следует из того факта, что в поле 6Р(дт») а ((о' — 1) /и) = о — 1 = — ! . Ч. т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
