У. Питерсон - Коды, исправляющие ошибки (1267328), страница 85
Текст из файла (страница 85)
Следующая теорема показывает, что это сделать можно и даже нетрудно и что при таком ограничении на декодер лишь незначительно уменьшается способность кода восстанавливать синхронизацию. Теорема 12.3. Пусть д(Х) порождает циклический (п,й)-код, а многочлен Р(Х) степени з 1 не делится на Х.
Тогда для смежного класса, образованного многочленом д(Х) и содержшцего Х-'Р (Х), ~л — э — г — 1~ Доказательство, Доказательство представляет собой просто метод определения величины сдвига. После вычитании Х-'Р(Х) нз принятой последовательности декодер производит умножение на Х'~+ и деление на а(Х). Следующие рассуждения показывают, что величина сдвига может быть теперь легко определена. рассмотрим сначала случай потери синхронизации. Согласно равенству (12А), при 1(Х)= 1(Х)ц(Х)+ Х 'Р(Х) и е(Х) = 0 Х""Е.(Х) — Х 'Р(ХИ= Х ~ ~ 1(Х)д(Х) +(Х вЂ” 1) Х 'Р(Х) + Х с~~б(Х).
(12.10) Наивысшая степень во втором слагаемом равна «+'«,'+з, а наинизшая степень равна «,. Коэффициенты при этих степенях ненулевые, Наивысшая степень в последнем слагаемом меньше чем «) «,-1-1, а наинизшая — не меньше чем «,+1. Так как «'+ 1 «,+з(2с;+э <в — /г, то цри делении равенства (12.10) на й(Х) последние два слагаемых остаются в остатке. Заметим, что величина сдвига «может быть определена вычитанием «,+ з из наивысшей степени остатка. Далее рассмотрим случай избытка синхронизации. Тогда в соответствии с формулой (12.6) Х' +'ь«(Х) — Х 'Р(Х))= =Х ' 1(Х) д(Х)+ 1,Х "— 1)Х'~Р(Х)+ Х'а+'-"б(Х) (12 11) Наивысшая степень во втором слагаемом равна «,+ з, а наинизшая степень равна «,.— «.
Коэффициенты при этих степенях иену. левые. Наивысшая степень в последнем слагаемом меньше чем «, +1, а наинизшая — не меньше чем «,+ 1 — «. Так как «,+э ( (и — й, то остаток, получающийся после деления на д(Х), состоит как раз из последних двух слагаемых. Этот случай можно отличить от потери синхронизации благодаря тому факту, что здесь наинизшая степень меньше чем «„что невозможно при по. тере синхронизации. Аналогично наивысшая степень при потере синхронизации больше чем «,+ з, что здесь невозможно.
Окончательно величина избыточной синхронизации может быть най. дена вычитанием иаинизшей степени ненулевого слагаемого из « Таким образом, при анализе синдрома этого вида можно различить все случаи. Ч. т. д. Очевидно, что для восстановления синхронизации при отсутствии ошибои лучше всего выбирать Р(Х) = Х+1; тогда э= 1 и «с=Ил л — 2)12). При этом значении з требуется на один проверочный символ больше, чем это следует нз границы, приведенной в теореме 12.2. Следствие 12.2 гарантирует, что граница может быть достигнута с помощью процедуры поиска. С другой стороны, реализовать метод, содержащийся в доказательстве теоремы 12.2, чрезвычайно просто. 12.2, Коды, которые восстанавливают синхронизацию или исправляют аддитивные ошибки Существует несколько методов, использующих смежно-групповые коды, для исправления аддитивных ошибок и восстановления синхронизации, которые гарантируют восстановление синхронизации в любом принятом слове, не содержащем аддитивных ошибок.
Для этого требуется, чтобы два полученных сигнала, соответствующие двум различным ошибкам синхронизации, двум различным комбинациям случайных ошибок, которые могут быть исправлены, или одной ошибке синхронизации н одной комбинации случайных ошибок, лежали в различных смежных классах. Циклические коды, исправляющие пакеты ошибок !3041 Пусть многочлен д(Х) порождает циклический (л,А)-код, который используется лишь для исправления всех пакетов длины Ь или меньше. Если смежный класс этого кода определяется много- членом Р(Х) и имеется потеря синхронизации в «символов, то принятое слово имеет вид (см. формулу (12.7)) (Х вЂ” 1) Р (Х) + Х'с (Х) + 6 (Х), (!2.12) где с(Х) — передаваемое кодовое слово, а б(Х) — многочлен степени « — 1 или меньше с неизвестными коэффициентами.
Предполагается, что аддитивных ошибок нет. Если теперь многочлен Р(Х) выбран так, что Р(Х) =Х" 1+ 1, то синдром принятого слова, как это следует из равенства (!2.12), совпадает с вычетом [Х' ' — 1+ А — Х" '+6(Х)1шоб д(Х). Этот выче~ совпадает с синдромом расположенного на концах слова циклического пакета длины «+2 с ошибками в позициях Х' и Х"-'. Если Ь ) «+2, то он является лидером смежного класса. При наличии избытка синхронизацни в «символов синдром снова был бы таким пакетом длины «+2, но с ошибками в позициях Хо и Х" Поскольку эти циклические пакеты пе похожи на обычные пакеты, их смежные классы можно использовать для восстановления синхронизации.
Правило синхронизации формулируется следующим образом. Если обнаружен расположенный на концах слова циклический пакет длины «+ 2 с ошибками в позициях Х" и Х" — ', то это означает, что произошла потеря синхронизации в «символов. Если обнаружен расположенный на концах слова циклический пакет длины г+ 2 с ошибками в позипиях Хе и Х" " ', то это означает, что имеется избыток синхронизации в г символов. Теорема 12.4. Пусть полинам у(Х) порождает циклический (и й)-код с коРРектиРУюЩей способностью длл пакетов Ь. Если зтот код используется только для исправления пакетов длины Ь или меньше, то смежно-групповой код, определяемый многочленом Р(Х) = Х" — '+ 1, может восстанавливать синхронизацию при потере или избытке в г, = Ь вЂ” 2 или меньше символов.
Граница Рейгера, введенная в теореме 4.15, утверждает, что для блоковых кодов, исправляющих пакеты ошибок, Для многих хороших циклических кодов, исправляющих пакеты ошибок, величина Ь равна или близка к (и — я)/2. Таким образом, как показывает теорема 12.2, зти коды при восстановлении синхронизации близки к оптимальным. циклические кеды, испркиляюисие случайные ошибки (ЗОЦ Следующие две теоремы показывают, что смежные классы некоторых БЧХ-кодов обладают способностью восстанавливать синхронизацию. Теорема 125. Пусть у(Х)= д1(Х)Р(Х) — порождающий много- член циклического (п, й)-кода с минимальным расстоянием не меньше чем 21+ 1, лсногочлен Р(Х) порождает циклический код с минимальным расстоянием й1 и многочлен д,(Х) имеет по меньшей мере один корень порядка и.
Тогда для смежно-группового кода, содержащего многочлен Х 'Р(Х), никакой смежный класс, соответствующий патере или избытку синхронизации в г символов, не совпадает со смежным классом, который соответствует ка«ому-либо другому сбою синхронизации как при ее потере, так и при избытке, или со смежным классом, соответствующим 1 или меньшему количеству ошибок, если 1т~< й,— 1 и ~г~(з/2, где з — степень многочлена д,(Х). доказательство.
То, что смежные классы, соответствующие различным сбоям синхронизации как при потере, так и при избытке, не совпадают, следует из теоремы 12.3. Пусть многочлен т~(Х) соответствует потере синхронизации в г символов, а много- член ге(Х) — набору из 1 или меньшего количества ошибок. Тогда они принадлежат одному смежному классу, если многочлеп гк(Х)— — «,(Х) делится на многочлен у(Х), Но в соответствии с равен.
ством (12.4) ге (Х) — г~ (Х) = 12 (Х) + е (Х) — Х'1~ (Х) — 6 (Х) = =~!з(Х) — Х'1,(Х)1д(Х)+(Х' — 1)Х 'Р(Х)+е(Х) — 6(Х) Поскольку по условию многочлен е(Х) — 6(Х) имеет вес, меньший числа йь то он не может делиться на многочлен Р(Х) и тем более на д(Х), если только многочлен е(Х) — 6(Х) не равен О. Б последнем случае многочлен гз(Х) — г,(Х) делится па многочлен д(Х), если на д(Х) делится многочлен (Х' — 1)Р(Х), что эквивалентно делению многочлена Х" — 1 на многочлен д, (Х). Ограничение, наложенное на многочлен н,(Х), эту последнюю возможность исключает, и, следовательно, многочлен гз(Х) — г~(Х) не может делиться на д(Х). Доказательство в случае избытка синхрояизации аналогично. ь1.
т. д. Пример. Пусть многочлен д(Х) порождает (127,36)-код Бь1Х, исправляющий' 15 ошибок, а многочлен Р(Х) порождает (127,57)- код БЧХ, исправляющий 11 ошибок. Многочлен д~(Х) удовлетворяет условиям теоремы 12.5, а его степень з = 21. Тогда й — 1= = 2.11+ 1 — 15 = 8 и [з/2)= 1О. Из теоремы 12.5 следует, что смежный класс (!27,36)-кода, для которого в качестве Р(Х) выбран порождающий многочлен (127,57)-кода, позволяет неправ. лить любую комбинацию из 15 ошибок или восстанавливать синхронизацию, если величина потери или избытка синхронизации не превышает 7 символов при условии, что сбой синхронизации и случайные ошибки не происходят одновременно.
Возможная процедура исправления ошибок состоит в проверке ошибок синхронизации, как описано далее при доказательстве теоремы 12.6. Если синдром имеет искаженный вид, то используется процедура исправления случайных ошибок. Эти этапы исправления ошибок могут следовать и в противоположном порядке. Аналогичный результат получается в виде следствия из теоремы 12.6 равд.
12.3. В этом же разделе можно сформулировать следующее утверждение: Следствие 12.3. Пусть многочлен Р(Х) порождает циклический (п,й)-код, исправляющий ! ошибок, и пусть двучлен Х" — 1 делится на многочлен а,(Х), который имеет по меныией мере один корень порядка и. Тогда смежный класс кода, порожденного многочленом д(Х)= Р(Х)н,(Х), содержащий многочлен Р(Х), восстанавливает синхронизацшо, если величина потери или избытка не превышает ! символов при условии, что не происходит аддитивных ошибок. Этот смежный класс исправляет не менее ! аодитивных ошибоК если не происходит ошибок синхронизации. !трипер. Пусть многочлен д(Х) порождает двоичный (127, 36)- од ВЧХ, исправляющий 15 ошибок, н миогочлен Р(Х) порождает (127, 43)-код, исправляющий 14 ошибок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
