Вернер М. Основы кодирования (2004) (1151882), страница 24
Текст из файла (страница 24)
Процесс нахождения остатка Ь(Х) в соответствии с алгоритмом деления Евклидапоказан в табл. 3.2. В результате получимХ3и{Х) = (X + X3)g{X) +X + X2.(3.33)Глава 3. Циклические кодыТаблица 3.2. Определение проверочных символови(Х) = 1 + X3 и д(Х) = 1+Х +Х3.X6Л: 5X4X2100X11000=Х3и(Х)1011000=Х3д(Х)--10000= Х3и(Х)10110= Хд(Х)--110= Ь(Х)+дляХ3д(Х)Так как кодовый многочлен определяется как3v{X) = Ь(Х) + Х и(Х),(3.34)то1001).(3.35)Повторяя процесс кодирования для всех 16 возможных информационных векторов, получим систематический циклический (7,4)-код.Его информационные и кодовые векторы приведены в табл 3.3.
Заметим, что циклический систематический (7,4)-код, образованныйпорождающим многочленом 1 + X + X3, совпадает с рассмотреннымнами ранее систематическим (7,4)-кодом Хэмминга (см. табл. 2.1).3.4. Порождающая и проверочная матрицыЦиклические коды образуют подмножество линейных блоковых кодов и, помимо общих особенностей линейных блоковых кодов, ониобладают некоторыми специфическими свойствами и методами описания. Рассмотрим сначала порождающую матрицу циклическогокода.
В соответствии с теоремой 3.2.3, каждый многочлен циклического кода может быть представлен в виде произведенияv(X) = a{X)-g{X) = aog(X)+a1Xg(X)+ - • •+ak_xXk-lg(X).(3.36)Заметим, что каждое слагаемое в (3.36) представляет собой сдвигпорождающего многочлена д{Х), которому соответствует векторg=(3.37)3.4- Порождающая и проверочная матрицы[73jТаблица 3.3.
Циклический (7,4)-код, образованный порождающим многочленом д(Х) = 1 + X + X3 в систематическом виде.ИнформационноеКодовоеИнформационноесловословословослово0000000 00000001101 0001Кодовое1000ПО 10001001011 10010100011 01000101ПО 01011100101 11001101000 11010010111 0010ООП010 ООП1010001 10101011100 1011ОНО100 ОНО0111001 о т1110010 11101111111 1111поэтому, кодовый вектор v, соответствущий многочлену v(X), можетбыть представлен в виде произведения информационного вектора ана порождающую матрицу Gv(3.38)lxn —где порождающая матрица G имеет вид/ 1 91 91 ••• 9т-\ОG/cxn —19\••• 9г-21О9г-110 0 1О--5r09\0\О(3.39)_i92•••flr-i1 /Пример: Порождающая и проверочная матрица циклического(7,4)-кода Хэмминга.Используя уже известный порождающий многочлен д(Х) = 1 +X + X3 (3.24), получим порождающую матрицу несистематическогоциклического (7,4)-кода1 1 0 1 0 00 1 1 0 1 00 0 1 1 0 10 0 0 1 1 00001(3.40)Глава 3.
Циклические коды.Как уже указывалось ранее, кодовое векторное пространство, образованное порождающим многочленом д(Х) = 1+Х+Х3, совпадает слинейным векторным пространством (7,4)-кода Хэмминга , следовательно матрицу G из (3.40) можно также рассматривать, как порождающую матрицу циклического кода Хэмминга в несистематическойформе.Путем элементарных матричных преобразований порождающаяматрица G из (3.40) может быть приведена к систематическому виду. Так как каждая строка матрицы G является кодовым словом,замена любой строки суммой этой строки с другой, отличной от нее,не меняет кодового векторного пространства (меняется лишь система соответствий между информационными и кодовыми векторами).Заменим в (3.40) вначале третью и четвертую строку их суммами спервой строкой и, далее, полученную четвертую строку - ее суммойс первой.
В результате, получим порождающую матрицу систематического циклического кода Хэмминга, совпадающую с (2.2),G4x7,- (Р 4 хз1,•0Х4) = I !111!00 1 0 0 0 \1 0 1 0 0! 0 0 ! 01 0 0 0 1 /(3.41)Возьмем информационный вектор из (3.30) и = (1 0 0 1). Ему будетсоответствовать кодовый вектор= u©G4x7'1 1 0 1 0 0 0 \0110100= (011 1001),= (1001)01110010,1010001/(3.42)что совпадает с полученным ранее (3.35) кодовым вектором систематического циклического кода и табл. 3.3.Проверочная матрица циклического систематического (7,4)-кодаможет быть получена из порождающей матрицы G' (3.41) по рассмотренным ранее формальным правилам. Здесь, однако, мы хотимполучить проверочное соотношение и построить проверочную матрицу, исходя только из свойств циклических кодов.
Для этого, воспользуемся 'сформированным ранее утверждением 3.2.5 о том, чтоппорождающий многочлен д(Х) делит Х + 1 без остатка. Следовательно, можно написатьXn + l = h(X)-g(X).(3.43)3-4- Порождающая и проверочная матрицы I75 ,Так как кодовый многочлен можно представить в виде(3.44)= a(X)-g(X),то, с учетом (3.43), произведение v(X)h(X)равноv{X) • h(X) = a(X) • h{X) • g(X) =п(3.45)п= а(Х) • [1 + Х ] = а{Х) + а(Х)Х .Так как степень многочлена а(Х) не превышает к — 1, правая частькравенства (3.45) не содержит в качестве слагаемых члены с Х ,+11X• • • X™" .
Используя это условие для коэффициентов произведения v(X)h(X), можно записать п — к проверочных равенствviOhk®=0=0vk+i © h0vk+\ ©vk ©(3.46)Эти равенства можно записать в матричной форме.. Введя проверочную матрицу(hk hk-i hk-2hi0 hk hk-i hk-2H( n -fc) X n=00hkh0hhk-i hk-2/*o00AiЛо0•••hk. hk-i hk-2^(3.47)••.00... ооhi ho)получим уже известное матричное уравнение для синдромного декодированияv © Н г = 0.(3.48)Определение 3.4.1. Пусть задай порождающий многочлен д(Х)степени г = п — к циклического (п, &)гкода С. В этом случае, многочлен h{X) степени к такой, что Хп + 1 = g(X)h(x) называетсяпроверочным многочленом.Многочлен, взаимо обратный проверочному многочлену h(X), т.емногочлен Xk(h(X~1))= hk + hk-iX+ ••• + hoXkя в л я е т с я порож-дающим многочленом (п, п — /г)-кода Gj, дуального коду С.Замечание.
Преобразованию Xlh(X~l)отображение его коэффициентов.соответствует зеркальноеI 76Глава 3. Циклические кодыПример: Порождающий многочлен кода, дуального циклическому (7,4)-коду Хэмминга.Рассмотрим опять циклический код с порождающим многочленом д(Х) = 1 + X + X3 из (3.24). Из разложения на множителиX7 + 1 (3.23) следует, что его проверочный многочлен имеет видh(x)= (1 + X) • (1 + X2 + х3) = 1 + X + X2 + X4,(3.49)поэтому, порождающий многочлен дуального кода определяется какX4h(X~1)= X4 + Xs + X2 + l(3.50)и он порождает циклический (7,4)-код.Теперь перед нами стоит задача получить порождающую матрицу систематического циклического (п, &)-кода, с заданным порождающим многочленом д(Х), не прибегая к элементарным преобразованиям матрицы (3.39). Здееь ключевая идея будет состоять в том,что любые к линейно независимых векторов, делящихся на д{Х), образуют одно и то же кодовое векторное пространство.
Надо лишьвыбрать эти векторы таким образом, чтобы им соответствовала порождающая матрица систематического (п, А;)-кода.г+гПредставим Хв виде'гдеГ = 0,1, - - -fc— 1Xr+i = сц(Х)д(Х) + bi{X),(3.51)иi(X) = bifl + щ^Л + • • • + OjiT._iA.(3.52)Равенству (3.51) соответствуют к линейно независимых кодовых многочленаVi(X) = <ь(Х)д(Х) - Xr+i + bi(X).(3.53)Таким образом, векторное пространство систематического циклического (п, &)-кода «натянуто» на набор к векторов Хг+г + bi(X), гдег = 0,1, • • • А; — 1. Здесь единицы при Хг+г образуют единичную подматрицу и являются признаком независимости базисных многочленов Vi(X).Порождающая матрица, соответствующая (3.53), имеет вид^0,0^0,1"0,2••'&0,г-1Oj оb\ iЬ\ 2 * • *V.b\r—\'.frfc-i,ob f c - i , i b f c - i , 2 •••Pfcxrfyt-1,,—1 0•••00 1 * •• 0.
. . .1 0 1 ••• 0Ifcxfc.(3.54)N3.5. Схемная реализация циклического кодирования 177Таблица 3.4. Определение порождающей матрицы в систематическом виде.Многочлен из (3.51)Базовый кодовый многочленX =д(Х) + 1 + Хvo(X) = 1 + Х + Х3X4 —Хд(Х) + Х + Х2r-iX3ъ24vt(X) = 1 + Х + Хх —(X + 1)д(Х) + 1 + X + ХX6 —(х3 + Х + 1)д(Х) + 1 +22х22ьMX) = 1 + Х + Х' + Хv3(X) = 1 + X2 + X 6Как уже доказывалось ранее, проверочная матрица систематического кода образуется из (3.54) в формегхп — \*-rxr *^ )•\о.0о)Пример: Порождающая матрица систематического циклического (7,4)-кода Хэмминга.Найдем порождающую матрицу систематического циклического(7,4)-кода но уже известному порождающему многочлену д(Х) =31 + X + X из (3.24).
Для этой цели определим, вначале, разложениег+гХсогласно (3.51) и базисные кодовые многочлены Vi(X) из (3.53)для г = 0,1,2,3 (табл. 3.4).Порождающая матрица непосредственно строится по базиснымкодовым многочленам vo(X),V\(X),V2{X),V3(X) и полностью совпадает с (3.42)1 10 11 11 0'4x3011110000 01 00 10 00001(3.56)14x43.5. Схемная реализация циклического кодированияВажнейшее преимущество циклических кодов по сравнению с другими методами кодирования заключается в простоте их техническойреализации. Использование в схемах кодеров и декодеров регистров178Глава 3.
Циклические кодыТаблица 3.5. АлгоритмЕвклида деления многочленаf(x) = 1 + X + X2 + X4 на д(х) = 1 + X2.X4X*-X2+X+- 12/WХ2д{Х)XX+1Остатоксдвига с обратными связями, позволяет просто и достаточно эффективно защищать от ошибок информационные массивы очень большой длины.Замечание. Эта особенность присуща всем, циклическим кодамнад полями Галуа.
Для простоты изложения, здесь мы ограничимся только двоичными кодами, т.е. циклическими кодами nadGF(2).Так как процедура деления многочленов является основной в кодерах и декодерах циклических кодов, покажем, прежде всего, какэта процедура может быть реализована с помощью регистров сдвигас обратными связями. Для начала, сопоставим деление многочленаf{X) = 1+Х+Х2+ХА на многочлен д(Х) = 1+Х2 по алгоритму Евклида (табл. 3.5) с его схемной реализацией (рис.
3.5). В таблице 3.5делитель д(Х) домножается на X2, так как степень f(X) равна 4 ивычитается из делимого f(X). В результате, полученный многочленимеет степень, меньшую д(Х), так что мы сразу же имеем остатокот деления f(X) на д(Х). Аналогичная процедура имеет место и нарис. 3.5, однако, здесь требуется три такта для того, чтобы младшиеразряды f{X) заняли место остатка.Р и с .
3.5. Схема деления многочлена \+Х+Х2+Х4: 1+Х2.Теперь рассмотрим схемную реализацию деления двоичных многочленов в общем случае. Пусть заданы: делимое степени тf(X) = /оf2X2+ ••• +fmX"(3.57)3.5. Схемная реализация циклического кодирования179)и делитель степени г, причем, г <тд(Х)= д0 + дхХ + д2Х2+ ••• +дгХг.(3.58)В результате деления мы должны получить разложение(3.59)= a(X)g(X)+b(X)с сомножителем а(Х) степени m - г и остатком Ъ{Х) со степенью, напревышающей г — 1.Схема деления многочленов общего вида представлена на рис.3.6.Сначала регистр сдвига полностью загружается старшими разрядами делимого.
Ключ 51 включен, а переключатель 52 находитсяв верхнем положении. Далее'начинается сам процесс деления. В первом такте производится сдвиг содержимого регистра на один разрядвправо. Так как fm = 1, эта единица, в соответствии с коэффициентом двигателя д(Х), суммируется с аналогичными разрядами делимого. В результате, мы получаем укороченный многочлен(3.60)со степеньюdeg[f{X)} = кг < т.(3.61)Эта же единица заносится в регистр формирования а(Х) при замкнутом переключателе 52 и в дальнейшем не меняется.Регистр сдвига с обратной связью1=т-гЧастное |а„-,|'"1 аг | а\ \ До | * | A S 2Остаток\Ь,-ijfl Ь% I Ьр ГРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
