У. Питерсон - Коды, исправляющие ошибки (1267328), страница 86
Текст из файла (страница 86)
Условия следствия 12.3 прн этом удовлетворяются. Смежный класс, определяемый много- членом Р(Х), отличается от смежного класса того же цикличекого кода рассмотренного в предыдущем примере. В этом случае следствие 12,3 гарантирует исправление не менее 14 аддитивных ошибок, а также сбоев синхронизации при потере или избытке ае не более чем в 14 символов. Процедура исправления описана в доказательстве теоремы 12.6. укороченные циклические коды, исправляющие случайные ошибки [Звц Если циклический код, способный исправлять 1 случайных ошибок, укорачивается по меньшей мере на 2гс+ 1 двоичных сим* волов, где «,=[1/21, то существует смежный класс этого кода, для которого способность восстанавливать синхронизацию определяется величиной, не меньшей числа г,.
В качестве синхронизирующего многочлена Р(Х) для этого смежного класса можно выбрать, например, вычет одночлена Х" по модулю порождающего многочлепа кода д(Х). Пусть через 1(Х)д(Х) обозначено кодовое слово в укороченном циклическом (п,й)-коде, а через 1 — длина первоначального циклического кода. Тогда передаваемое слово нз смежного класса имеет вид 1(Х) =1(Х) д(Х) + Р(Х).
Многочлен Р(Х) желательно выбирать так, чтобы способность восстанавливать синхронизацию у смежно-группового кода определялась величиной г,. В случае потери синхронизации в г символов, где г( г„принимаемое слово имеет вид г (Х) = Х'1 (Х) д (Х) + Х "Р (Х) + 6, (Х) + Х"6, (Х), где 6;(Х) — многочлены степени, не большей чем г — 1, с неизвестными коэффициентами. Декодер вычйгает многочлен Р(Х) из принятого слова и находит синдром (г (Х) + Р (Х)) = ((Х + 1) Р (Х) + Ь, (Х) + Х"Ь (Х)), (12.13) где через (Х) обозначен класс вычетов (смежный класс) Х по модулю д(Х).
Если теперь в качестве многочлена Р(Х) выбрать вычет Х" по модулю д(Х), то ((Х' + 1) Р (Х) + 6, (Х) + Х"6 (Х)) = (Х"+" + 6 (Х) + Х" Ь (Х)), (12.! 4) где г+а с-!. Так как вес многочлена Х"+'+ба(Х)+Х"6~(Х) не больше чем 2г+ 1, то он является лидером смежного класса, если г ( г, = [!!2), где ! — корректирующая способность кода.
Поскольку и+г.С 1, то многочлен должен содержать член степени и+г. Но символ, соответствующий члену этой степени, не передается, и ошибка в позиции Х"+" может интерпретироваться как потеря синхронизации в г символов. При избытке синхронизации в г символов, где г ( г„ синдром имеет вид (г(Х) -(- Р(ХИ = (Х" + Х '6,(Х) + Х" "6, (Х)). (12,15) Вес этого многочлена не превышает 2г+ 1( 1, и поэтому его тоже можно выбрать в качестве лидера смежного класса. Таким образом, избыток синхронизации обнаруживается, когда декодер пытается исправить непередаваемый символ, соответствущий одночлену Х". Если н дополнение к обнаружению сдвигов синхронизации можно определить направление сдвига„ то способность кода восстанавливать синхронизацию удваивается.
Для того чтобы определить это направление, необходимо, чтобы смежный класс, используемый прн потере синхронизации, отличался от смежного класса, используемого при избытке синхронизации. Но (Х+ +6,(Х)+Х"6,(ХД У(Х" +Х '6,(Х)+Х "6,(Х)), так как каждый многочлен имеет вес, не больший 1, н они не совпадают, если ! — и ) 2г+ !. Таким образом, если имеет место потеря синхронизации в г символов, где г ((!/2), то декодер указывает на ошибку в позиции Х"+". Синхронизация может быть немедленно восстановлена.
Если же имеется избыток синхронизации в г~(!!2) символов, то декодер указывает на ошибку в позиции Х . Чтобы восстановить синхронизацию, в декодер подается следующий символ и снова вычисляется синдром. Эта процедура повторяется до тех пор, пока не окажется, что величина избыточной синхронизации больше не указывается. В этот момент и будет восстановлена синхронизация. Если в качестве многочлена Р(Х) выбран одночлен Х' — ', то аналогичные рассуждения показывают, что правила восстановления синхронизации при потере и избытке меняются местами.
Если многочлен Р(Х) выбран в виде Х" + Х' — ', то н потеря, и избыток синхронизации могут быть восстановлены за один шаг, но теперь г, ~((! — !)/2). Ло сих пор предполагалось, что принятое слово не содержит аддитивных ошибок. Но это вовсе не необходимо. Если происходит сдвиг на г символов, то при этом вводится не более 2г+! ошибок н ! — 2г — ! аддитивньж ошибок могут быть исправлены. Без уменьшения вероятности могут быть также исправлены комбинации с ббльшими весами.
Преимуществами этого метода являются простота его реализации и то, что не требуется вводить дополнительную избыточность, кроме той, что уже присутствует в коде. 12.3. Коды, которые восстанавливают синхронизацию н исправляют аддитивные ошибки Очевидно, что желательно исправлять сразу как аддитивные ошибки, так н сбои синхронизации; за это приходится платить дополнительной избыточностью. При этом требуется значительно больше смежных классов, так что число требуемых проверочных символов, грубо говоря, равно сумме числа проверочных символов, необходимых для исправления аддитивных ошибок, и числа проверочных символов, необходимых для восстановления синхронизации при отсутствии адднтивных ошибок.
(См. задачу !2.1.) В этой главе приводится три легко реализуемых способа кодирования, для которых требуется приблизительно такое количество проверочных символов. Смежно-групповые коды длн восствнонленин синхронилапин при нлличии ошибок В приведенных ниже теоремах показывается, что смежные классы циклических кодов можно использовать для восстановления синхронизации даже тогда, когда происходят случайные ошибки. Теорема 12,6. Пусть многочлен Р(Х) порождает циклический (и, й)-код, исправляющий ! ошибок, а двучлен Х" — ! делится на многочлен д,(Х), который имеет по меньшей мере один корень порядка и. Тогда смежный класс кода с порождающим многочленом в (Х) = к1(Х)Р(Х), содержащий Р(Х), может одновременно восстанавливать синхронизацию, если величина потери или избытка ее г ~ 1, и исправлять любую комбинацию из ! — г аддитивных ошибок.
Доказательство. доказательство состоит в описании процедуры декодирования, которая обеспечивает успех. Пусть 1(Х) к (Х)— многочлен первоначального циклического кода, а г(Х)к(Х)+Р(Х)— передаваемый многочлен. Согласно равенствам (12.3) и (126), пРи потере синхронизации в г символов и наличии комбинации аллитивных ошибок е(Х) принятый многочлен после вычитания Р(Х) имеет вид г(Х) — Р(Х) =Х"г (Х) й(Х) +(Х' — 1) Р(Х!+ е(Х)+ б (Х). (12.16) Так как по предположению вес многочлепа е(Х)+ б(Х) не больше (1 — г)+ с =1, то многочлен е(Х)+б(Х) является лидером смежного класса в коде, порожденном многочленом Р(Х), и е(Х)+ б(Х) можно найти, применяя процедуру декодирования для кода с порождающим многочленом Р(Х) к принятому многочлену г(Х).
После проведения этого этапа исправления получаем многочлен Х'1 (Х) д (Х) + (Х' — 1) Р (Х) . (12.17) После деления на Р(Х) и прибавления единицы многочлен принимает вид (12.18) Х'Е (Х) я1 (Х) + Х'. Пусть а — корень многочлена д1(Х) порядка п. Подстановка и в выражение (12.18) дает в результате а", что позволяет найти г. Зная г, из выражения (12 17) можно вычесть (Х' — 1)Р(Х) и циклически сдвинуть результат на г позиций, чтобы получить 1(Х) п(Х) — первоначальный кодовый многочлен. Одновременно можно определить, что произошла потери синхронизации в г символов.
Случай избыточной синхронизации аналогичен — на последнем шаге результирующее значение г будет несколько меньше чем п, или, что эквивалентно, отрицательно, и, таким образом, случай потери синхронизации отличается от случая избытка синхронизации. Ч. т. д. Теорема 12.8 является следствием этой теоремы. )7 ример. Пусть многочлен д(Х) порождает двоичный (127, Зб)- код БЧХ, исправляющий 15 ошибок, а многочлен Р(Х) порождает (127,43)-код БЧХ, исправляющий 14 ошибок.
Условия теоремы удовлетворяются, и код может одновременно восстанавливать сбои синхронизации в г < 14 символов н исправлять до 14 аддитивных ошибок с помощью процедуры, описанной в доказательстве теоремы. Расширенные циклические коды Боуз и Колдуэл (27) следующим образом определили расширенный') циклический код. Каждое кодовое слово с(Х) циклического (и',А')-кода, порожденного многочленом а,(Х), имеет внд с (Х) = 1 (Х) а (Х), (12.19) где 1(Х) — многочлен степени, меныпей чем й'. Чтобы придать коду способность восстанавливать синхронизацию, на многочлен 1(Х) ') Здесь термин «расширенный» используется в несколько ином смысле, чем ранее. См., например, равд. 8ни накладывается ограничение, а именно он должен иметь вид ((Х) )(У(Х)д,(Х)+1.
(12.20) Таким образом, может использоваться только некоторое подмножество множества кодовых слов в коде, порожденном многочленом Х„(Х). Многочлен п,(Х) имеет степень 1, показатель и( и на него делится многочлен Ь,(Х), где Ь,(Х) (Х"' — 1)/й,(Х). Многочлен ; (Х) — произвольный многочлен степени, меньшей чем й' — 1. Слово расширенного циклического кода формируется для пере дачи следующим образом.
Пустыи ~ и и через си-ь ' и си-КО1 — !)(2)в ° ° ° сКгк-!)!21... и с!» сО обозначены коэффициенты многочлена с(Х). Соответствующие коэффициенты расширенного слова суть иисфикс 1 1 СК .-!)(и-(, ° ° СЬ СО С вЂ” (, ...„С 1( .!)(21, ° °, С((т — !))21, ° ° ° ~ С(1 СО, Си — (, ° . °, Сс-(Ок-ПГ)1- ! ! суФФикс Таким образом, при формировании слова расширенного кода [(и — 1)/2) символов низшего порядка из с(Х) используются в качестве префикса, а [(и — 1)/2[ символов высшего порядка — в качестве суффикса. Этн символы, которые в действительности являются дополнительными проверками на четность, добавляются к слову так, что синхронизационый сдвиг в з ( [(пт — 1)/2[ символов просто преобразует центр кодового слова с(Х) в его циклический сдвиг Х'с(Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
