У. Питерсон - Коды, исправляющие ошибки (1267328), страница 87
Текст из файла (страница 87)
Поэтому, даже если имеется сбой, способность исправлять аддитнвные ошибки кода, порожденного много- членом дс(Х), не ухудшается. Точнее, если к слову циклического кода Х'с(Х) добавляется комбинация ошибок е(Х), которая исправляется циклическим кодом, порожденным многочленом д,(Х), то принятый набор длины и имеет вид г(Х) = Х'с(Х)+ е(Х). Заметим, что потеря синхронизации соответствует положительному значению з. Но поскольку многочлен Х'с(Х) как раз и является кодовым словом циклического кода, порожденного много- членом а,(Х), а е(Х) — по предположению набор ошибок, который может быть исправлен, то декодер может определить кодовое слово Х'с(Х). Но в силу равенств (12.19) н (12.20) Хис (Х) =- /12(Х) [Х'!'(Х) С,(Х) + Х'). (12 21) Деление этого результата на известный многочлен д,(Х) дает вычет (Хв/'(Х)д,(Х)+ Х') по модулю й,(Х).
Но так как й,(Х) целится на п,(Х), то остаток от деления этого вычета на п.(Х) сравним с Х' по модулю д,(Х) и называется синдромом синхронизации. Если — ((гп — 1)/2) ( з ( [(гп — 1)/2), то никакие два нз этих синдромов не совпадают, поскольку в противном случае многочлен Х' — 1, 1( т, делился бы на многочлен д,(Х), что по предположению не может быть. Таким образом, декодер может определять величину з. Зная величину з, можно определить 1'(Х), и процедура декодирования заканчивается. Несмотря на кажущуюся сложность, эта процедура довольно просто реализуется.
Принятое ранее предположение о том, что способность исправлять ошибки синхронизации в обоих направлениях одинакова, не необходимо. Если более вероятны сдвиги в одном из направлений, то можно обеспечить большую корректирующую способность в том направлении, где это желательнее. Теорема 12.7. Пусть д,(Х) — порождающий многочлен циклического (и', й')-кода. Тогда ранее построенный расширенный циклический (и'+2г, А' — 1)-код может исправлять все сдвиги синхронизации в г или менее символов и одновременно произвольный набор ошибок, исправляемых первоначальным кодом. Еше один способ восстановления синхронизации и исправления ошибок Предлагались и другие методы построения кодов для исправления синхроннзационных сдвигов.
За исключением кода, который описан ниже (199), эти коды, по-видимому, ие так эффективны, как расширенные циклические коды. Предположим, что 2г,+1 информационных символов высшего порядка в циклическом коде, исправляющем аддитивные ошибки, таковы: 00...0 11...1. г,+1 г Здесь символ наивысшего порядка расположен слева. Символы 0 н ! являются элементами поля ПР(в). Сдвиг синхронизации на г, или меньше символов всегда приводит к циклическому сдвигу переданного кодового слова. Таким образом, произвольный исправимый набор аддитивных ошибок может быть исправлен, несмотря на синхроннзационную помеху. Расположение первых 2г,+ 1 символов исправленного слова единственным образом определяет сдвиг синхронизации.
Следовательно, код имеет способность восстанавливать синхронизацию, равную г,. Построенный таким образом код представляет собой [и й — 2г,— 1)-код. При малых значениях г, такие коды несколько чше, чем расширенные циклические коды; при ббльших значе„нях г, верно обратное утверждение. Смежно-групповые коды, описанные в этом разделе, требуют ббльшую избыточность, но в отсутствие ошибок исправляют сбои синхронизации, при потере ее или избытке, большей величины, а при отсутствии сбоев синхронизации они исправляют больше аддитивных ошибок. Замечании Под общим названием <синхронизация» обычно объединя|от многие разные проблемы. В этой главе была рассмотрена только задача восстановления синхронизации блоков и слов с использованием кодов, близко связанных с блоковыми кодами, исправляю- шими аддитивные ошибки. Коды без запятой впервые изучены Голомбом, Гордоном и Уелчем [122].
Их работа стимулировалась исследованиями по передаче генетической информации [59], при которой, по-видимому, используется код без запятой. Некоторые исследователи [154] рассматривали задачу исправления кодами без запятой аддитивных ошибок в дополнение к ресинхронизации. Смежно-групповые коды для целей синхронизации были предложены Стиффлером [288], который доказал некоторые варианты теорем 12.1 и 12.2. Эти коды также излучались Леви [181], Фреем [!00], Тонгом [301, 304] и др. Многое из изложенного в равд.
12.2 и 12.3 принадлежит Тонгу. Расширенные циклические коды, описанные в равд. 12.3, были предложены Боувом, Колдуэллом [27] и Уелдоном [325]. Модификация этих кодов, названная кодами подмножеств, предложена Товаресом и Фукудой [298]. Эти коды, по-видимому, могут конкурировать со смежно-групповыми кодами при восстановлении синхронизации. Задача синтеза кодов для исправления ошибок синхронизации в противоположность восстановлению ее сдвигов изучалась Улменом [3081 Он предложил класс кодов, исправляющих комбинации ошибок, вызванных выпадением или вставкой одного символа, но зато обладающих большой избыточностью. Задачи 12.1. Покажите, что для смежно-группового кода, построенного по двоичному циклическому коду, множество всех векторов, получающихсн в результате потери или избытка синхронизации в г символов, рамещается в 2" смежных классах.
12.2. Найдите границу Хемминга для количества проверочных символов в смежно-групповом коде, построенном по циклическому коду, оценив число смежных классов для следующих случаев: а) синхронизация восстанавливается при отсутствии аддитивных ошибок; б) исправляются аддитивные ошибки или восстанавливается синхронизация; в) одновременно восстанавливается синхронизация и исправляются аддитнвные ошибки. 12.3. Определите синдром при потере или избытке синхронизации в один двоичный символ для примера из равд. 12.2. 12.4. Сравните два метода построения кодов из рззд. 12.2, построив двоичные коды, исправляющие случайные ошибки, со следующими параметрами: КОлнчество исправляемых случайаыч ошибок Сиособность восстанавливать Циклический.
кол сннхрониеаиню и (15, 7) 1 2 3 1 3 5 10 (63, 45) ~~с( — 4е — 3 ~ ~к — е — 2~~ и синхронизация может быть восстановлена при наличии е или меньшего количества ошибок. Сравните коды этого типа с кодами из равд. 12.3. 12.5 (Товарес, Фукуда). Рассмотрите смежно-групповой циклический (и, Й)-код с минимальным расстоянием б(. Если зтот код применяется для исправления только е (((б( — 1)/21 ошибок, то его способность восстанавливать синхронизацию определяется ве- личиной )3 Сверточные коды, исправляющие случайные ошибки Оказалось, что применить хорошо разработанные разделы математики к синтезу и декодированию сверточных кодов нелегко.
тем не менее к настоящему времени найдено много интересных и полезных кодов, н можно надеяться, что в будущем их будет еще больше. В этой и последующих главах особое внимание уделено двоичным кодам. Результаты равд. 13.1 и 13.2 применимы ко всем свергочным кодам, включая и коды, исправляющие пакеты ошибок, которые рассматриваются в гл. !4, 13.1. Кодирование и вычисление синдрома На фиг 13.1 схематически изображен кодер для сверточного (тп„тяо)-кода. Кодер преобразует йо информационных символов ,элементов поля бГ(дЦ, поступающих на его вход в ло выходных кодовых символов, ло) йо. Выходные символы являются линейными комбинациями над полем 6Г(д) входных символов из предшествующих т блоков.
Кодер обрабатывает поступающую информацию параллельно (одновременно в нескольких каналах), но зслн требуется осуществить последовательный прием, то возникает необходимость в дополнительном преобразовании. Существуют кодеры для сверточных кодов двух типов. На фиг. 13.2 показан кодер, содержащий й ячеек, который может быть использован для всех кодов; такие кодеры будут рассмотрены ниже. Кодер с и — А ячейками может быть использован для систематического кода; такой кодер и будет рассмотрен здесь.
Порождающая матрица сверточного (тио, тйо)-кода, приветенная в соотношении (3.!2), имеет вид б, б, ... б бо ° ° ° б -о (13.1) бо Пусть через дс(1,1) обозначен (1,1)-й элемент магрнцы б~ порядка Фяг. 13.1. Общая схема кодера для саерточяого (и, /г)-кода. яа Х па 1= 0, 1, .„, т — 1; определим субпорождающнй много- член йгг(В)=да(1.
1)+д!(1. Д1)+ . +д -!(! 1) О Символом О обозначен оператор задержки, введенный в гл, 7. Матрица б полностью определяется йопо субпорождающими многочленами. л! — ! Пусть т,(()) = ~ т!о0! — многочленное представление ни!=о формационной последовательности, поступившей на !'-й вход кодера. Тогда кодирование может рассматриваться как процесс формирования Йопо произведений т1(0) яц(й) 1= 1 2„,. йо у'= 1, 2, . " по. При этом по выходных последовательностей представляются в виде а. сг(Я= Х т,Я)й!1(О) 1=1, 2, ..., по* ! ! а 1-й символ кодового блока в момент времени и — 1 определяется коэффициентом при 0 -', который равен 2тмп,а 1(1, 1)+тип (г, 1)+ ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
