У. Питерсон - Коды, исправляющие ошибки (1267328), страница 63
Текст из файла (страница 63)
Однако каждая четная степень а является корнем минимальной функции, являющейся также минимальной функцией для некоторой предшествующей нечетной степени а. Например, если т;(Х) обозначает минимальную функцию для а1, то аа, аа — корни тп~(Х), аа — корень тпа(Х), иа — корень и;(Х), а,'о — корень втз(Х) и т. д. Следовательно, можно дать следующее эквивалентное определение кода: вектор (1(Х)) принадлежит коду тогда и только тогда, когда элементы и оз стаи-! ') Эти коды извиваются БЧХ-кодами в узком смыслЕ, являются корнями многочлена /(Х). Итак, код порождается многочленом К(гп (Х) ° ~,(Х), ..., т, причем степень каждого многочлена пг;(Х), как следует из теорем 6.16 и 6.24, не превосходит пь Таким образом, степень много- члена д(Х) не превосходит тгь, и код содержит не более т/ь проверочных символов.
Полученные результаты можно сформулировать в виде следующей теоремы: Теорема 9.2. Для любых целых положительных чисел т и 1ь ( «-' и/2 существует двоичный БЧХ-код длины и = 2 — 1, исправляющий все комбинации из /ь или меньшего числа ошибок и содержащий не более т/ь проверочньсх символов.
Все БЧХ-коды с многочленом д(Х), определяемым равенством (9.6), длина которых не превосходит 1023, приведены в табл. 9.1 с указанием фактического числа проверочных символов. Приводимый в таблице параметр 1ь определяет конструктивную корректирующую способность кода и равен ((йь — !)/2].
Для многих из этих кодов, пользуясь теоремами из равд. 9.3, можво доказать, что конструктивное расстояние равно минимальному расстоянию. Берлекэмп (21, гл. 12], пользуясь результатами Манна (20Ц, разработал алгебраическую процедуру для определения количества информационных символов в БЧХ-коде. Все коды из табл. 9.1, длина которых не превосходит 15, оптимальны (232], и все коды, исправляющие двойные ошибки, квази- совершенны и, следовательно, оптимальны. Наиболее короткий код, для которого найден лучший линейный код, †э (31,16)-код с й = 7; в работе (159] предложен нециклический (31,16)-код с й=8.
Найдено около 8000 циклических кодов длины 63, лучших, чем БЧХ-коды (см. приложение Г). Большинство из них принадлежит одному узкому, бесконечному классу циклических кодов, о которых известно, что они имеют большее минимальное расстояние, чем соответствующие БЧХ-коды (17Ц. На фиг. 9.1 приведены графики зависимости скорости передачи (число информационных символов/длина кода) А/и от скорости исправления ошибок (число исправляемых ошибок/длина кода) 1/и для БЧХ-кодов с длиной до 65535. Интересно рассмотреть поведение этих кодов, когда и становится очень большим.
Из фиг. 9.1 видно, что если отношение А/и зафиксировано, то нижняя граница для 1/и с ростом и, по-видимому, стремится к нулю. Это действительно так и доказано Питерсоном (232] и Берлекэмпом (2Ц. Кроме того, в силу теоремы 9.8 (9,7) Таблица 9,!. Двоичные ВЧХ-коды в узком смысле, порождаемые примитивными влементами порядков, меньших 2'е 511 15 11 7 5 31 26 21 16 11 6 1 2 3 4 5 6 7 10 11 !3 15 57 51 45 39' 36 30 24 18 16 10 127 120 113 106 99 92 85 73 71 64 57 50 43 36 29 22 15 8 1 2 5 6 7 9 10 11 13 !4 !5 21 23 27 3! 511 1013 1003 993 983 973 963 953 943 933 923 913 903 893 1 2 3 4 5 6 В 9 РО 11 12 13 247 239 231 223 215 207 199 1 255 191 181 179 171 163 155 147 139 131 123 !15 107 99 91 87 79 71 63 55 47 45 31 29 21 13 9 502 493 484 475 466 457 448 439 430 421 412 403 394 385 376 367 358 349 340 331 322 313 В 9 1О 11 12 13 14 15 18 !9 21 22 23 25 26 27 29 ЗО 31 42 43 45 47 55 59 63 1 3 4 5 6 7 9 10 11 12 13 !4 15 16 18 19 20 21 22 23 304 29о 286 277 268 259 250 241 238 229 220 211 202 193 184 175 166 157 148 1З9 130 121 112 103 94 85 76 67 58 49 40 3! 28 19 10 25 27 28 29 30 31 36 37 38 39 41 42 43 45 46 47 51 53 54 55 58 59 61 62 63 85 87 91 93 95 109 111 119 121 Продолжеиы ° 1 102З 1023 Этот факт и то, что отношение 4/а стремится к нулю с ростом а при фиксированном отношении А/а, показывают, что отношение фактического минимального расстояния к длине также стремится к нулю.
Таким образом, эти наилучшие иэ известных конструктивных кодов в действительности очень плохие при больших п. Задача нахождения истинного минимального расстояния БЧХ- кодов рассматривается в следующем разделе. Примеры. В последних двух примерах равд. 8.1 рассматривались двоичные БЧХ-коды. Второй иэ этих кодов определялся условием, что (! (Х)) является кодовым вектором тогда и только тогда, когда сс, аэ, ..., ссю — корни многочлепа !'(Х), где а.— примитивный элемент ссР(23).
Было показано, что в этом случае а(Х)— многочлен степени 20, так что получается код с минимальным оас- г 883 87З 86З 858 848 838 828 818 8О8 798 788 778 763 758 748 738 728 7!8 708 698 688 678 668 658 648 638 628 биз 603 598 588 14 15 16 17 !8 !9 20 21 22 23 24 25 26 27 28 29 зо з! 34 35 36 З7 38 Зо 41 42 4З 44 45 46 47 578 573 563 553 543 5ЗЗ 523 513 5ОЗ 49з 483 473 463 453 44З 43З 423 413 403 393 Ззэ З78 368 358 348 ЗЗ8 З28 3!8 ЗО8 298 288 49 5О 51 52 53 54 55 57 58 59 60 61 62 63 73 74 75 77 78 79 82 83 85 86 87 89 90 91 93 95 278 268 258 248 238 228 218 208 2ОЗ 193 183 !73 163 15З 143 1ЗЗ !23 121 111 !о! 91 86 76 66 56 46 36 26 !6 11 102 !оз 106 !О7 109 по 111 115 117 118 119 !22 123 125 126 127 170 171 173 175 181 183 187 189 !91 219 223 239 247 255 0,7 О,О -„"- 0,5 0 ЦО25 Ц05 0,075 Ц10 Ц125 Ц750 Ц175 Ц20 Ц225 Ц25 2/и Фиг.
ЗЛ. Исправление сшибок некоторыми двоичными БЧХ-кодами. стоянием, равным 11, исправляющий все комбинации из 5 или меньше ошибок. Этот код, длина которого равна 2а — 1= 31, содержит 20 проверочных и 11 информационных символов. Другой код, т. е. (15,5)-код, используется далее в этой главе для подробной иллюстрации метода исправления ошибок, так что здесь приводится его более детальное описание. Вектор (1(Х)) принадлежит этому коду тогда и только тогда, когда а, ав, ... ..., ае — корни миогочлена 1(Х), причем а — примитивный элемент сгР(24). Было получено, что $'(Х) = лт~ (Х) гла (Х) глн (Х).
Если в качестве а взять корень многочлена Х'+Х+1, как зто сделано в табл. 6.1, то лт~(Х) = Хе+Х+ 1 и можно проверить, что та(Х) = Хе+ Ха+Х +Х+1, а тв(Х)= Ха+ Х+1. Таким образом, ~(Х) =(1+ Х+ Х)(1+ Х+ Х'+ Ха+ Х)(1+ Х+ Х) = + Х + Ха + Х4 + Ха + Хв + Уе )т(Х) 1~ +11 д(Х) другие интересные двоичные БЧХ-коды получаются, если выбрать в качестве я непримитивный корень 6Е(2") и положить юо= 1.
Пример. Предположим, что элемент а равен кубу примитивного элемента поля 6Г(2'). Тогда порядок а равен 21. Если минимальную функцию для аз обозначить через т;(Х), то сР' = 1 и,х, ах, к4, аз, и'~, сгм = ип — корни многочлена т~(Х) степени 6, „з дз, ггы — коРни многочлена тз(Х) степени 3. Следовательно, многочлен а(Х) = пм(Х) тз(Х) является многочленом степени 9; а, аз, аз и и4 — корни д(Х), а порождаемый этим многочленом код является БЧХ-кодом, исправляющим все двойные ошибки. Для этого кода и = 21, и — 1 = 9 и, следовательно, А=!2, В приложении Г приведены значения истинного минимального расстояния и минимального расстояния, гарантируемого БЧХ-границей„т.
е. конструктивного минимального расстояния, для всех двоичных циклических кодов длины 65 и меньше. Для непримитивных БЧХ-кодов типично резкое расхождение между г( и 4, в отличие от случая примитивных кодов, для большинства из которых при известном д справедливо равенство И = И„(см. равд. 9.3). Минимальные расстояния для большей части кодов, описываемых в этом разделе„ могут быть представлены в виде 2!а + 1 для некоторого гь Границу расстояния можно увеличить до 21, + 2, включая 1 в число корней. Минимальная функция для 1 равна Х вЂ” 1, и, следовательно, это требование влечет за собой прибавление одного проверочного соотношения, которое, как нетрудно видеть, является проверкой, включающей все символы.
Пусть С,--циклический код, порождаемый многочленом я(Х), не делящимся на Х вЂ” 1, и пусть Сз — код, порождаемый многочленом (Х вЂ” 1)д(Х). Тогда некоторый мпогочлен принадлежит Сз тогда и только тогда, когда он делится на д(Х) и Х вЂ” 1, т. е. тогда и только тогда, когда он является многочленом из Сь у которого сумма коэффициентов равна О. Другим очень важным подклассом БЧХ-кодов являются коды Рида — Соломона„получаемые при ш = та = 1. Пусть а — элемент 6Е(д) порядка и. (Если сг — примитивный элемент, то и равно своему наибольшему возможному значению д — 1.) Пусть вектор ()(Х)) является кодовым вектором тогда и только тогда, когда элементы а, а~, ..., аз-' являются корнями многочлена )'(Х). Минимальная функция для и! равна просто Х вЂ” а', так что д(Х)=(Х вЂ” а)(Х вЂ” пз)...
(Х вЂ” а~ '). (9.8) Степень многочлена я(Х) равна Й вЂ” 1. В результате получается код длины и с д — 1 проверочными символами и с минимальным расстоянием, равным д. Поскольку для кодов Рида — Соломона г( = и — А — 1, то эти коды являются сепарабельиыми с максимальным расстоянием (равд, 3.9). Таким образом, их весовое распределение определяется равенством (3.44).
Пусть г7 = р, тогда каждый о-ичный символ может быть выражен в виде набора длины пг элементов из 6Р(р). Следовательно, исправляющий 1 ошибок (д'" — 1,гг'" — 1 — 21)-код Рида— Соломона над 6Р(г!) можно рассматривать как (пг(д'" — 1), пг(г!"' — 1 — 21))-код над 6Е(р), способный исправлять произвольную комбинацию ошибок, все ненулевые символы которой располагаются в ! блоках по пг символов.
В гл. 11 показано, как, пользуясь этой идеей, построить некоторые наиболее мощные из известных кодов, исправляющих пакеты ошибок, и кодов, одновременно исправляющих пакеты и случайные ошибки. Заметим, что двойственным к коду Рида — Соломона является код Рида — Соломона, но вообще для БЧХ-кодов это неверно. 9.3. Истинный минимальный вес БЧХ-кодов Граница БЧХ (теорема 9Л) является нижней границей для минимального веса в БЧХ-кодах. Из фиг.
9.1 видно, что при любой фиксированной скорости отношение конструктивного расстояния к длине кода для примитивных БЧХ-кодов стремится к нулю, когда длина кода стремится к бесконечности. Естественно возникает вопрос: верно ли это для истинного минимального веса нли имеют ли БЧХ-коды значительно лучшие параметры по сравнению с определяемыми границей БЧХ? Недавно доказан ряд теорем, устанавливающих минимальный вес в БЧХ-кодах и других кодах (21, 43, 167, 171, 187, 235). В этой главе представлено несколько ключевых теорем, "их достаточно для того, чтобы ответить на поставленный здесь вопрос.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
