У. Питерсон - Коды, исправляющие ошибки (1267328), страница 84
Текст из файла (страница 84)
Если г ~ ~и/2, то г = ьь и говорят, что код является кодом без запятой. Если код имеет степень свободы от запятой г ( и/2, то любой синхронизационный сдвиг на г или меньшее число символов может быть обнаружен, т. е. код способен обнаруживать сбой сипхрониза. ции величиной га = г. Если г ) п/2, то может быть обнаружен любой сдвиг. Если код имеет степень свободы от запятой г ( п/2, то может быть исправлен любой синхросдвиг в [г/21 или меньшее число символов.
Необходимо только просмотреть все варианты в пределах рассматриваемых [г/21 позиций. Ни при какой попытке не будет отбрасываться больше чем г символов, и, таким образом, кодовое слово будет найдено только в правильном расположении. С другой стороны, если г ) п/2, то код является кодом без запятой и может быть исправлен любой синхросдвиг. Пусть через г, обозначена способность кода восстанавливать синхронизацшо. Тогда [12.1) г в— г, = ьь, Кроме того, очевидно, что г, г. В коде без запятой никакой циклический сдвиг кодового слова не может быть кодовым словом. Таким образом, для циклического кода и даже для линейного кода степень свободы от запятой всегда равна нулю.
Кроме того, количество кодовых слов М в д-ичном коде без запятой не может пре- вышать величины д 1п. Этот результат может быть улучшен [122[; можно показать, что И » ~— ~ и (д) дам 1 (12.2) где суммирование распространяется по вой длины и, а и — функциЯ Мебиуса: 1, пЩ = О, д содержит квадратичный множитель, ( — 1)'. д = р~рз... р„, Р~ — различные простые числа. Истман [66) доказал, что граница, задаваемая выражением (12.2), достигается при всех нечетных значениях и. Случай четного и значительно сложнее, и, несмотря на значительные усилия, результаты все еще неполные.
Шольц [2691 разработал алгоритм построения кодов без запятой, которые довольно просты в реализации. Коды без запятой чувствительны к аддитивным ошибкам. Хотя и использовались коды без запятой с дополнительной способностью исправлять аддитивные ошибки [154), результатов в атой области немного. Более сильные и полезные результаты получены за счет обеспечения аффективных кодов, исправляющих аддитивные ошибки, таких, как, например, циклические коды, некоторой свободой от запятой (равд. 12,2 и 12.3). Циклические коды не свободны от запятой и позтому не способны обнаружить ошибки синхронизации.
Однако оказывается, что смежные классы циклических кодов вполне пригодны для обнаружения сбоев синхронизации и для восстановления синхронизации. Смежный класс циклического (п,й)-кода образуется прибавлением перед передачей фиксированного многочлена Р(Х) к каждому кодовому многочлену. Тогда 1(Х) =1(Х) д(Х)+ Р(Х), где д(Х) — порождающий многочлен циклического кода, 1(Х)— многочлен степени, меньшей чем й, а Р(Х) — фиксированный многочлен степени, меньшей чем а. Способность исправлять аддитивные ошибки у смежного группового кода такая же, как и у первоначального циклического кода.
Если передается многочлен 1(Х) и принимается многочлен «(Х) = =1(Х)+е(Х), то приемник на первом шаге вычитает Р(Х) из принятого многочлена г(Х). Результат равен 1(Х)д(Х)+ е(Х), н исправление ошибок может проводиться прн помощи любого метода, который применим для первоначального циклического кода, ибо имеется просто сумма слова циклического кода н комбинации ошибок.
Предположим, что передается многочлен 1(Х), в канале происходит потеря синхронизации в «символов н возникает аддитивная комбинация ошибок а(Х). Тогда принятый многочлен имеет вид «(Х) = Х'1 (Х) + е (Х) + 6, (Х) — Х"6, (Х), (12.3) где 6~(Х) — члены высших порядков из последующего слова, которые появляются как последние «символов в «(Х), а бз(Х) представляет «членов высшего порядка 1(Х), которые потеряны.
Так как 6, (Х) и 6,(Х) неизвестны декодеру и Х" = 1 для циклического кода длины п, то равенство (12.3) может быть переписано как «(Х) = Х'1 (Х) + э(Х) + 6(Х), (12.4) где 6 (Х) 63 (Х) 62 (Х) и степень 6(Х) меныпе чем «, а коэффициенты 6(Х) неизвестны. Аналогично, если имеется избыток синхронизации, «(Х)=Х '1(Х)+е(Х)+ Х" "6,(Х) — Х "бз(Х), (12.5) где 6|(Х) — члены наинизших порядков предыдущего слова, кото- рые появляются первыми в принимаемом сигнале, а бз(Х) — чле- ны низших порядков 1(Х), которые потеряны. Это может быть пере- писано как «(Х) = Х 1(Х) + е (Х) + Х '6 (Х), 6(Х) =63 (Х) — 62(Х) (12.6) где Синхронизацнонный сдвиг в «символов обнаруживается тогда и только тогда, когда многочлен (Х" — 1)Р(Х)+ 6(Х) не является кодовым словом ни при каком выборе 6(Х).
Но если « = и — л, то всегда существует некоторое 6(Х), такое, что (Х" — 1)Р(Х)+ +6(Х) делится на д(Х). Поэтому, если п(2я, то существует необнаруживаемый сдвиг из п — л или более символов. Рассуждения при избыточной синхронизации аналогичны. и снова 6(Х) имеет степень, меньшую чем «, а коэффициенты неизвестны. Равенства (12.4) и (12.6) различаются знаком перед «, а во всем остальном они очень похожи. Поэтому естественно обозначить величину потери или избытка синхронизации через «, используя знак плюс для потери и знак минус для избытка. Теперь рассмотрим вопрос определения ошибки синхронизации при отсутствии аддитивных ошибок.
Первый этап декодирования состоит в вычитании многочлена Р(Х) из принятого слова; это дает в случае потери синхронизации (Х' — 1) Р (Х) + ХЧ (Х) д (Х) + 6 (Х). г,(~[ я и/2, (12.9) и не ограничена при я - п~2. Доказательство. Если при передаче многочлена ц(Х)у(Х)+ + Р(х) происходит потеря синхронизации в гс символов, то после вычитания Р(Х) принятое слово имеет вид Х с1,(Х)д(Х)+(Х с — 1) Р(Х)+ Ь(Х), где 6(Х) — неизвестный многочлен степени, меньшей чем гы Прн избыточной синхронизации в го — 1 символов имеем аналогичный результат Х 'о(,(Х) у(Х)+ (Х-' — 1) Р (Х)+ Х-'оу(Х).
Теорема 12.1. Степень свободы от запятой в любом смежном ~лассе циклического кода при и ( 2й ограничена неравенством г(п — й — 1; (! 2,8) зго соотношение превраи!ается в равенство для смежного класса, определяемого многочленом Р(Х) = 1. Показательство. Равенство (!2.8) следует сразу из только что приведенных рассуждений. Если Р(Х) = 1, то выражение (12.7) не может делиться на д(Х) при 1( г = п — А — 1, так как степень 6(Х) по крайней мере равна г — !. Ч.
т. д. Следствие 12.1. Произвольный циклический (п,я)-код имеет смежный класс без запятой тогда и только тогда, когда я ( и/2. Имеется и другое интересное следствие теоремы 12.1. Следствие 12.2. Произвольный циклический (и, й) -код имеет смежный класс, для которого я~ )п~2, я < и/2. Из формулы (12.2) видно, что необходимо приблизительно 1оп и избыточных символов, чтобы гарантировать свободу от запятой, а во многих случаях етого достаточно (661 Следствие 12.1 утверждает, с другой стороны, что пД избыточных символов необходимо и достаточно для обеспечения свободы от запятой„если используется смежно-групповой код.
По-видимому, за удобство и простоту использования смежно-группового кода требуется платить введением значительной избыточности, Следующая теорема показывает, что неравенство в следствии 12.2 никогда не имеет места. Теорема 12.2. Способность восстанавливать синхронизацию для смежно-группового кода, полученного из циклического (п,й)-кода, ограничена величиной Теперь, если при любом выборе Р(Х) эти два результата равны при некоторых й(Х), /з(Х) Ф ~,(Х), б(Х) и у(Х)„то восстановления синхронизации не происходит.
Умножая эти двз выражения на Х"о и вычитая второе из первого, получаем С(Х)=(Х с оц(Х) — гг(Х))д(Х)+ +(Х" +" — 1)1 (Х)+Х" б(Х) — у(Х). Если ть+ то ) п — А, то степень Х'об(Х) — у (Х) равна по меныпей мере и — А, а б(Х) и у(Х) могут быть выбраны так, чтобы С(Х) делилось на д(Х). Пусть Тогда я,(Х) = Х'с~'о/,(Х) — 1,(Х) + а,(Х) при некотором дз(Х), При А == и/2, многочлен д,(Х) делится на многочлен 6(Х) = = (Х" — 1)/д(Х) для некоторых фиксированных ю,(Х) и 1,(Х). Поскольку д(Х)Ь(Х) = О, то многочлен С(Х) = О. Таким образом, в этом случае ть+ то ' и — й — 1.
Однако если А ( и/2, то ни при каких 1~(Х) и 1з(Х) многочлев д~ (Х) не делится на многочлен й(Х). Это можно заметить из следствия 12.2, которое утверждает, что при й ~ и/2 величина т, не ограничена сверху. Ч. т. д. Коды, рассмотренные выше, исправляют сдвиги синхронизации, перебирая все варианты в пределах г, позиций. Желательно, особенно для длинных кодов, избежать такого поиска н непосредственно вычислить правильно сияхронизированные позиции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
