Вернер М. Основы кодирования (2004) (1151882), страница 26
Текст из файла (страница 26)
Тогда si(X) является синдромом г^'(Х), т.е. остаткомот деления циклического сдвига г(Х) на порождающий многочленд(х).Доказательство. Рассмотрим многочленп-\г(3.66)3.6. Синдром циклических кодов и контроль ошибок I87JПроизведение X • г(Х) имеет видX • г(Х) = г0Х + пХ2+ ••• + r n _ i Z " .(3.67)Циклический сдвиг многочлена г(Х) можно записать следующимобразом:r«(X)= r n _ i + r 0 X + r 1 X 2 + --- + r n _ 2 X " - I ==(3.68)r n _! • [Хп + 1] + X • г(Х).Запишем г^(Х) в виде r^(X) = a{X)g{X) + s(X), а г(Х) в видег(Х) = с(Х)д(Х) + s(X), где s(X) и s(X) синдромы многочленовг^(Х) и г(Х). Воспользуемся соотношением Хп + 1 = g{X)h{X) изтеоремы 3.2.5, тогда имеемс(Х)д(Х) + 3(Х) = rn-1h(X)g(X)+ Х[а(Х)д(Х)+ s(X)}.(3.69)Переставляя слагаемые в (3.69), получим связь между синдромамиё(Х) и s(X)X • s(X) = [c(X) + rn^h(X) + Xa(X)}-g(X) + ё{Х) .сомножительостаток(3.70)Из 3.70 непосредственно следует формулировка теоремы.
•Пример: Вычисление синдрома однократных ошибок' для циклического (7,4)-кода Хэмминга.<Ч.Н6—*\ i HРегистр синдромаРис. 3.15. Вычисление синдромов циклических сдвиговпринятого слова.Продолжим предыдущий пример. Из рис. 3.14 следует, что однократной ошибке в компоненте г§ вектора г = ( г с П , . . . ,г^) соответствует синдром s = {SQ,S\,S2) = (1,1,1) (такт п = 7). Отключиввходной регистр, получим схему, изображенную на рис. 3.15. Заметим, что исходное состояние на такте п = 0 определяется синдромомоднократной ошибки в компоненте г$.
Произведя циклические сдвиги регистра синдрома рис. 3.15, мы на каждом такте будем находить188Глава 3. Циклические кодыТаблица 3.6. Синдромы однократных ошибок циклического(7,4)-кода Хэмминга с порождающим многочленом д{х) = 1 + X + X3.Тактso012siS2Ошибочная компонента111Г5101Г6100ГО3010п4001Г25110гз6011s(X) из (3.70).
Последовательность s(X) соответствует синдромамоднократных ошибок в компонентах Гб, го и т.д. (Табл. 3.6). Значения из таблицы 3.6 полностью совпадают со значениями таблицы2.3, полученной для проверочной матрицы систематического (7,4)кода Хэмминга.Замечание. В рассмотренном примере вся таблица синдромов однократных ошибок генерируется с помощью простейшей схемы, поэтому, для кодов большей длины можно хранить в памяти декодератаблицы синдромов, а не саму проверочную матрицу.Рассмотрим связь между синдромом s(X) и многочленом ошибоке(Х). Из модели передачи информации (рис. 3.11) следует(3.71)гдеv(X) = c(X)g(X) = Xru{X) + b(X).(3.72)r(X) = a(X)g(X) + s(X),(3.73)e(X) = [a(X) + c(X)}g(X)+s(X)}(3.74)Так както'Из (3.74) следует, что e(X)mod(g(X)) = s(X).
Так как код Хэмминга исправляет все однократные ошибки, то для построения таблицы синдромов (п, А;)-кодаХэмминга в качестве е(Х) достаточно перебрать все одночлены Х°, X1,...,Хп~1- Прим. перев.3.7. Пакеты* ошибокЗнание синдрома не позволяет однозначно определить многочлене(Х). Так, например, если е(Х) делится без остатка на д[Х), то этому случаю соответствует нулевой синдром и ошибка не может бытьраспознана. В этом случае говорят о необнаружимой или остаточнойошибке декодирования.3.7.
Пакеты ошибокХарактерной особенностью циклических кодов является способностьк распознаванию пакетов ошибок. Под пакетом ошибок понимаетсягруппирование ошибок в одной ограниченной области кодового слова(рис. 3.16). Пакет ошибок можно описать многочленом видае(Х) = XjB(X).(3.75)е =(0 ... 0НШН ( ) -0)Начало пакета ошибок вj-ой компонентеПакет ошибокВ(Х) -1+Х +Х '-?ЛРис. 3.16. Вектор пакета ошибок длины 7.Если длина пакета ошибок не превосходит величины г = п — к, тостепень многочлена ошибок меньше г.
В этом случае е(Х) не делитсяна д{Х) без остатка и синдром принятого слова всегда отличен отнулевого, следовательно, пакет ошибок длины равной или меньшейг всегда распознается. Из теоремы 3.6.1 следует, что распознаетсятакже любой циклический сдвиг многочлена 5 ( Х ) степени, меньшейг, т.е. и «концевой» пакет ошибок длины меньшей или равной г (рис.3.17), всегда распознается.Циклический сдвиг пакета ошибокРис.
3.17. Вектор «концевого» пакета ошибок дайны 7.Глава 3. Циклические кодыТеорема 3.7.1. Циклический (п, /с)-код способен обнаруживать всепакеты ошибок (в том числе концевые) длины г = п — к и меньше.Помимо распознавания всех пакетов ошибок длины г и меньше,циклические коды обладают способностью обнаруживать большуючасть пакетов ошибок, длина которых превосходит г.Рассмотрим пакет ошибок длины г + 1, начинающийся в j-ойкомпоненте. Так как первая и последняя компоненты пакета ошибок отличны от нуля, всего имеется 2Г~1 возможных конфигурацийошибок. Необнаружимой является только одна из них, многочленкоторой В(Х) совпадает с д(Х), то естье(Х) = XjB(X) = Xjg(X).(3.76)Теорема 3.7.2. Для циклического (п, &)-кода доля необнаружимыхпакетов ошибок длины / = r + l = n —fc+ 1 равна 2~(г~1>,Рассмотрим пакет ошибок длины l>r + l = n — k + \, начинающийся в j-oib компоненте. Если соответствующий многочлен В(Х)делится на д(Х) без остатка, то естье(Х) = Х^В(Х) = Х*а(Х)д{Х),(3.77)то такой пакет не может быть обнаружен.Пусть коэффициенты многочлена а(Х) степени I — г — 1 имеютвид OQ, а\,...,a;_r_i.Так как пакет ошибок начинается и заканчиг2вается единицей, ао = O(_r_i = 1.
Следовательно, существует 2'~ ~наборов коэффициентов а(Х), приводящих к необнаружимым ошибкам в (3.77). С другой стороны, существует 2 ; ~ 2 различных пакетовошибок длины I и, таким образом, верно следующее утверждение.Теорема 3.7.3. Для циклического (п, А;)-кода доля необнаружимыхпакетов ошибок длины I > г + 1 = п —fc+ 1 равна 1~Т.Пример: Распознавание ошибок циклическим (7,4)-кодом Хэмминга.Рассмотрим циклический (7,4)-код Хэмминга из предыдущих примеров сг — п — А; = 3.
Так как минимальное кодовое расстояние кодаХэмминга d m i n = 3, он способен обнаруживать все двойные ошибки или исправлять одиночные. Рассматриваемый (7,4)-код Хэмминга является циклическим кодом и он способен также обнаруживатьS.8. Декодер Меггиттавсе пакеты длины г = 3.
В частности, любые три следующие друг задругом ошибки всегда обнаруживаются.Доля необнаружимых ошибок длины г + 1 = 4 равна 2~( 3-1 ) =1/4. При пакетах ошибок с длиной большей 4, не распознается только2~3 = 1/8 из них.Замечание. На практике, как правило, испдльзуются циклическиекоды с довольно большим числом проверочных разрядов, например,г = п — к = 16. Доля необнаружимых пакетов ошибок такимикодами достаточна мала.
Так, при г = 16, обнаруживается болеечем 99,9969 % пакетов длины Пи 99,9984 % пакетов длины 18 ивыше.3.8. Декодер МеггиттаПроцесс декодирования циклических кодов (как и вообще всех линейных блоковых кодов) можно разделить на три этапа:1. Вычисление синдрома;2. Определение ошибочных компонент принятого слова;3. Исправление ошибок или выдача сигнала о наличии неисправимых ошибок.Оценивая сложность обработки принятого сигнала, можно заметить, что декодирование является «узким местом», в цепи передачиинформации.
Это связано с очень большими аппаратными затратами на декодирование длинных кодов с высокой корректирующейспособностью.Для циклических кодов процедура вычисления синдромов относительно проста. Из рис. 3.12 видно, что сложность вычислениясиндрома мало зависит от длины кодового слова и определяется, восновном, числом проверочных символов.Определение ошибочных компонент по синдрому для всех линейных блоковых кодов может быть сделано, в принципе, с помощьютаблицы синдромов. Сложность реализации такого метода декодирования возрастает экспоненциально с ростом длины кодовых слови корректирующей способности кода [7]. Здесь на помощь приходятнекоторые особые свойства циклических кодов, которые позволяютсущественно упростить процесс декодирования.В настоящем разделе мы представляем достаточно простую схемудекодера двоичных циклических (п, &)-кодов в общем виде.
БудемГлава 3. Циклические кодыисходить из модели передачи информации рис. 3.11. В этой схемепринятый многочлен обозначается через г(Х), кодовый многочлен через v(X), а многочлен ошибок - через е.(Х).Первым шагом декодирования является вычисление синдрома.Здесь могут возникнуть два случая:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
