У. Питерсон - Коды, исправляющие ошибки (1267328), страница 80
Текст из файла (страница 80)
Х! Х Проверки Х'" н'+' Х("-')' Х("-')' Х< -4) ! Информация Каждая строка этой таблицы является кодовым словом первона. чальиого (п, А)-кода. Действительно, если многочлен а„!Х(" 1)(+)+ + а 2Х("-2)(+)+ ... + а,Х(+1+ аьХ) делится на многочлен д(Х!), то многочлен а )Х"-'+а„2Х"-2+ ... +а!Х+аьделится на многочлен д(Х). Пакет длины Ы или меныпе может иметь не более Ь символов из любой фиксированной строки табл. 11!. Так как каждая строка может исправлять пакеты длины Ь илн меньше, то весь код может исправить все пакеты длины Ы или меньше. Ч.
т. д. Только что описанный метод построения (п(,А!)-кода известен как метод символьного пергмгжения. Параметр ! называется степенью перемежения. Следствие 11.1. Перемгжение степени 1 укороченного ()иклического (и, А)-кода приводит к укороченному (<иклическому (п1, А()- коду, корректирующая способность которого для пакетов в ! раз превышает корректирующую способность для пакетов первоначального кода. Перемежение кода, нсправлнющего пакеты, для которого г = О, т.
е. Ь принимает максимально возможное значение, всегда приводит к коду с г = О. Таким образом„если найдены короткие коды !'абацца ! 1 ! Некоторые циклические и укороченные цинлические колы, анлашщие пакеты ошибок. 1Многочлеиы 8 (к) готси а иосьыеричной ааписи, например 35 011! 0!=Х'+Х'+Хи+11 Величина попрании" мого пакета а Поромнаюшна многочлеи и СО Скорость передачи л аы !н, а) (ХтЬЕь !) с 2 = 0, то с помощью теоремы 11.1 можно построить коды практически любой длины, способные исправлять пакеты максималыю возможной данны. Некоторые интересные коды, исправляющие пакеты, можно построить, используя приведенную виже теорему, где через В!(Х) и Ва(Х) обозначены миогочлены степени Ь вЂ” 1 или меньше, соответству!ощие пакетам, такие, что оба оии ие делятся на Х.
Теорема 11.2 (84, 220). Пусть многочлен д'(Х) порождает ииклический (и', И')-код. Предположим, что в этом коде нет слова, имеющего вид В1 (Х)+ Х!Ва(Х), 1 ( ! ( и' — 1. Пусть р(Х) — такой неприводимый многочлен степени Ь и показателя е, что (р(Х), у'(Х) ) = 1. Тогда циклический код длины и = и'е, порожденный многочленом д'(Х) = д'(Х)р(Х), имеет корректирующую способность для пакетов Ь. Доказательство. Предположим, что два пакета длины Ь или меньше В,(Х) и Х!В,(Х) при некотором 1 принадлежат одному и гому же смежному классу, построенному для (и, Й) -кода, 1 ~1 « ' и — 1.
Тогда для некоторого многочлена д!(Х) имеет место равенство Х!В (Х) + В, (Х) = в, (Х) д (Х) = д, (Х) р (Х) у' (Х). (11.2) Йногочлен Х"' — 1 н, следовательно, Хен — 1 прн любом значении 1 2Ь+ ! 0,42 0,60 0,63 0,65 0,68 0,81 0,85 0,87 0,88 0,91 0,92 0,93 0,96 0,99 (2Ь+!, 1) (7, 3) (15, 9) (27, !7) (34, 22) !50, 34) (67, 54) (1ОЗ, 88) (63, 55) (85, 75) (!31, 1!9) (169, 155) !121, 112) (290, 277) !5! 1. 499) !1023, !О!0) Ь 2Ь+ 1 0.286 0,200 О,!85 О,!76 О, 160 0,090 0,068 0,048 0,047 0,038 0,035 0,025 0,0!7 0,008 0,004 Х 1 35 17! 2 671 15!73 224 53! 36 365 !1436! 711 26Я !5 !63 55 726 ! 411 24 711 10 451 22 365 о делятся на й (Х). Таким образом, Х'В,(Х>=Х' ' В,(Х>+ у,(Х>д'(Х>, и в соответствии с равенством (11.2) х~ '" в, (х) + в, (х> = уз (х> у' (х), (1 1.3) По предположению степень многочлена р(Х) равна Ь, что по меньней мере на единицу больше, чем степень многочлена В(Х). Поэтому двучлен Х'" — 1 делится на неприводимый многочлен р(Х).
Это означает, что многочлен Х'" — 1 делится как на многочлен р(Х), так и на многочлен д'(Х). Так как вп' меньше чем и, то получаем, что Х" — 1 — многочлен наименьшей степени, который делится на многочлеп д(х) = р(Х) д'(Х). Ч. т. д. Если многочлен д'(Х) порождает код длины п' с корректирую. щей способностью для пакетов Ь, то многочлен д(х) порождает код длины и = еп' с той же корректирующей способностью. Если в качестве д'(Х) выбрать многочлен Х'ь — ' — 1, то только одно слово из соответствующего кода не может быть выражено в виде В1(Х)+Хгвз(Х), 1 ( ! и' — 1. Такой выбор й'(Х) приводит к кодам Файра (84).
Следствие 11.2 (Файр). Циклический (и, и — 2Ь вЂ” с+ 1)-код, пороясденный многочленом д(х>=(хгь ' — !) р(х>, (П.4) имеет корректирующую способность для пакетов Ь. здесь и = е(2Ь вЂ” !), где е — показатель неприводимого многочлена р(Х) степени с= Ь, так что (р(Х),хгь' — 1)=1, Доказательство теоремы 11.3 не выявляет идеи, лежащей в основе построения кодов Файра. Проверки на четность, связанные с множителем Х"-' — 1, представляют собой 2Ь вЂ” 1 перемежающихся, равномерно расположенных проверок на четность. Поскольку символы, участвующие в каждой проверке, располагаются на расстоянии 2Ь вЂ” ! друг от друга, то на каждую из этих проверок будет влиять не более чем одна ошибка в любом пакете длины 2Ь вЂ” 1 или меньше.
Таким образом, эти проверки на четность дают в некотором роде изображение пакета. Любой пакет ошибок длины где в выбирается так, чтобы степень Х~ '" Вз(х) была меньше чем и'. Равенство (11.3) противоречит гипотезе о том, что никакое кодовое слово из (и', А')-кода, порожденного многочленом д'(Х), не имеет вида В1(Х)+ХгВз(Х), 1 (! «и' — 1, за исключнием случая, когда ! — ип' = О и Вз(Х) = — В1(Х). Опустив индексы у Вь Вг в равенстве (11.2), получим В (Х>(Х'"' — 1) = а,(Х) д' (Х> = с,(Х) р (Х). Ь или меньше будет оставлять по меньшей мере Ь вЂ” 1 последоваельных проверок иа четность незатронутыми, и поэтому можно п еделить, какой символ стоит в начале пакета, Таким образом, наличие сомножителя Хть ' — 1 достаточно для того, чтобы полностью определить комбинацию ошибок, если она образует пакет длины, не большей чем Ь.
Дополнительная информация, требуемая для определения положения пакета, обеспечивается сомножителем Р(Х) В кодах Файра требуется не менее ЗЬ вЂ” 1 проверочных символов для исправления пакетов длины Ь. Следовательно, для этих кодов (1 1.5) )годы, описываемые в следуюшей теореме, или коды из равд. 11.3, полученные с помощью вычислительной машины, во многих случаях оказываются лучше, чем коды Файра.
Теорема 11.3 (35). Пусть р(Х) — такой многочлен степени Ь и показателя е, что (р(Х), Хь — 1) = 1. Тогда (и, и — 2Ь) — код, порожденный многочленом д(х) =(х' — Ц р (х), может исправлять произвольные пакеты длины Ь или меньше, которые расположены в позициях Х'ь, Х'ь+', ..., Х'ь+ь-~, О » 1( е — 1. Здесь и = еЬ. Доказательство.
Пусть В,(Х) н В,(Х) — ненулевые многочлены степени Ь вЂ” 1 или меньше. (Здесь В;(Х) может делиться на Х.! Теорема будет доказана, если показать, что ие существует кодового слова вида с(Х)=В,(Х)+ ХмВг(Х), 1=1, 2, ..., е — 1. Если В,(Х)+Х'ьВ,(Х)=у,(Х)р(Х) !Хь — 1) то, поскольку многочлен (Х'ь — 1)Вг(Х) делится на многочлен Хь — 1, В, (Х)+ В,(Х) = у,(Х)(Х' — Ц.
Но как многочлен В~(Х), так и многочлев Вь(Х) имеют степень, меньшую Ь, и поэтому должно выполняться равенство Вт(Х)= = — В~(Х). Подставляя этот результат в равенство (11.6), получаем Вг (Х) (Х' — Ц = д~ (Х) р (Х) (Х вЂ” 1). Многочлен р(Х) имеет степень Ь и неприводим, поэтому, чтобы выяолнялось последнее равенство, двучлеп Хгь — 1 должен делиться нд многочлен р(Х). Но двучлен Х'ь — 1 также делится на Хь — 1. Так как ! ( е н Х'ь — 1 является двучленом наименьшей степени, который делится иа р(Х) (Х' — !), то никакое кодовое слово ие представляется в виде В~(Х)+ХиаВ«(Х) и может быть исправлен пакет длины Ь или меньше с любой «фазой».
Ч. т. д. Кодовые слова кода, описанного в теореме 11.3, можно представить в виде е блоков по Ь символов в каждом. Эти Ь-мерные векторы можно перемежать поблочно, а ие посимвольно, так что все Ь символов из блока будут последовательно передаваться по каналу.
Блоковое перемежеиие степени ! кодов, предложенных в теореме 11.3, приводит к кодам со следующими параметрами: п=1п', Ь = !Ь' — (Ь' — 1), п — А =2!Ь', з = п — А — 2Ь = 2 (Ь' — 1), где параметры Ь' и и' совпадают с параметрами п и Ь из теоремы 11.3. Для кодов Бартона при больших 1 отношение 2Ь,'(и — А) близко к единице, следовательно, они асимптотически оптимальны относительно границы Рейгера из теоремы 4.15.
При четных умеренных по величине значениях ! эти коды лучше, чем коды Файра. Поскольку коды Бартона циклические, они могут декодироваться с помощью процедуры, описанной в равд. 11.3. Путем замены каждого элемента из 6г"(д ) его представлением над 6г(д) в виде гп-мерного вектора из (и, й)-кода над полем 6г" (д ) можно получить (лгл, Ьи)-код над полем 6г(д), Такие коды и особенно коды, полученные из кодов Рида — Соломона и перемеженных кодов Рида — Соломона, хорошо исправляют пакеты ошибок. В частности, перемежение степени ! кода Рида — -Соломона над 6г'(4"), исправляющего одиночные ошибки, приводит к коду с такими же параметрами и корректирующей способностью для пакетов, как у перемежепного поблочно кода Бартона (равенство (11.7)), причем и' принимает максимально возможное значение, равное д — 1.
(См. задачу 11.!0.) Заметим, что в коде Рида — Соломона, рассматриваемом как код иад 6г(д ), который исправляет ! ошибок, требуется 21 проверочных символов и с его помощью исправляются наряду с другими комбинациями ошибок произвольные пакеты длины 1 или меньше. Таким образом, любой код Рида — Соломона, рассматриваемый как код над 6Е(д ), оптимален в смысле границы Рейгера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
