Скляр Б. Цифровая связь (2003) (1151859), страница 86
Текст из файла (страница 86)
Если и„;й компонент отличен от нуля, порядок полинома равен и-1. Удобство такого полиномиального представления кодового слова станет более понятным по мере дальнейшего обсуждения алгебраических свойств циклических кодов. 6.7.1. Алгебраическая структура циклических кодов Х'ЩХ) 1)со(Х) ( ) (6.55,а) или, умножая обе части ураянения на Х" + 1, Х'О(Х) =о(Х)(Х" + 1)+О" (Х), остаток (6.55,б) что в модульной арифметике можно описать следующим образом: 1)~'~(Х) = Х()(Х) по модулю (Х" + 1) .
(6.56) Здесь "х по модулю у" означает остаток от деления х на у. Ниже справедливость вы- ражения (656) демонстрируется для случая 1= 1. ()(Х)=ив+и,Х+изХ +...+и„зХ" +и„,Х" ХЦХ) = иеХ е и~Х + игХ + ... + и„зХ" ~-ь и„~Х" К последнему выражению прибаяим и вычтем и„, или, поскольку мы пользуемся арифметическими операциями по модулю 2, можем прибавить и„, дважды. ХЬ(Х)=и„1+исХ+и~Х +изХ + "+иьаХ +и„|Х" +и„, =()~ ~(Х)+и„1(Х" + ) ()ш(Х) Поскольку порядок ()'п(Х) равен л — 1, этот полипом не делится на Х" + 1.
Таким обра- зом, используя уравнение (6.55,а), можно записать следующее: ()г "(Х) = ХС(Х) по модулю (Х" + 1). Обобщая, приходим к уравнению (6.56). Ю"'(Х) = ЗЛ~(Х) по модулю (Х" + 1) б.?. Циклические коды 383 В кодовых словах, выраженных в полиномиальной форме, циклическая природа кода проявляется следующим образом. Если ЩХ) является. кодовым словом, представленным полиномом порядка (и — 1), то 1)"'(Х) — остаток от деления ХЧ3(Х) на Л + 1— также является кодовым словом. Иными словами, Пусть 1) = 1 1 О 1 лля и = 4.
Выразите кодовое слово в полиномиальной форме и, используя уравнение (6.56), выполните третий циклический сдвиг кодового алова. Решение ()(Х) = 1 ь Х + Х' пояином записан в порядке возрастания степени Л"13(Х)=Х +Л ьХ, где(=З Разделим ХЧ)(Х) на Х" + 1 и найдем остаток, используя полиномиальное деление. Х + Х + Х х + Х Х + Х + Х Х + 1 1 остаток ()1 !(Х) Х + Х + Записываем остаток в порядке возрастания степеней: 1+ Х'+ Х', кодовое слово 1уп = 1 О 1 1 представляет собой трн циклических сдвига () = 1 1 О 1.
Напомним, что лля двоичных кодов операция сложения выполняется по модулю 2, так что ь 1 = — 1, и, следовательно, е расче- тах знаки "минус" не отражены. 6.7.2. Свойства двоичного циклического када С помощью иалиномиальноги генератора можно создать циклический код, почти так же как создавались блочные коды с использованием матрицы генератора. Полиномиальный гене- ратор 8(Х) для циклического кода (и, Л) является единственным и имеет следующий вид: 8(Х) =8,+Х,Х- Х,Х'+ ... +г,хг. (6.57) Здесь 8ь и 8,, должны быть равны 1. Каждый полипом кодового слова в подпространстве имеет вид ЩХ) = щ(Х)й(Х), где ЩХ) — полипом степени и — 1 или меньше. Следовательно, полином сообщения щ(Х) будет иметь следующий виа: гп(Х) = т, + т,Х+ ьи,Х + ...
+ т„„,Х" г (6.58) Всего в кодс (и, /с) существует 2" " полинома кодовых слов и 2" вектора кода. Поэтому на каждый вектор кода должен приходиться один полином кодового слова. и-Р=А или р=и — А Отсюда следует, что 8(Х), как показано в уравнении (6.57), должен иметь степень и — /с, и каждый полипом кодового слова в коде (и, Л) можно выразить следующим образом: ЩХ) =(те ьт,Х+тзХ + ... +ив,Х" ') 8(Х). (6.59) () будет считаться действительным кодовым словом из подпространства Б тогда и только тогда, когда 1)(Х) делится на 8(Л) без остатка.
384 Глава 6. Канальное кодирование: часть 1 Пример 6.7. Циклический сдвиг вектора кода ~Х', ! Полиномиальный генератор й(Х) циклического кода (л,й) является множителем Х +1, т.е. Х" + 1 =й(Х)п(Х). Например, Хз + 1 (1 + Х + Хз)(1 + Х + Х2 + Х4) 6.7.3. Кодирование в систематической форме В разделе 6.4.5 мы ввели понятие систематическая ((орма и рассмотрели уменьшение сложности, которое делает эту форму кодирования более привлекательной. Теперь мы хотим использовать некоторые алгебраические свойства циклического кода для развития процедуры систематического кодирования. Итак, вектор сообщения можно записать в полиномиальной форме следующим образом: 2 ..~ -1 щ(Х) =~л,=т,Х+ тзХ + ...
+ т~,л (6.60) В систематической форме символы сообщения используются как часть кодового слова. Мы можем сдвинуть символы сообщения в к крайних правых разряда кодового слова, а затем прибавить биты четности, разместив их в крайние левые л — Х разряды. Таким образом, осуществляется алгебраическая манипуляция полинома сообщения, и он оказывается сдвинутым вправо па л — 1 позиций.
Если теперь умножить щ(Х) на Х" ', мы получим сдвинутый вправо полинам сообщения: Х" гга(Х)=те)(" ~+тХ" ~+ +...+ть,Х" (6.61) Если далее разделить уравнение (6.61) на й(Х), результат можно представить в сле- дующем виде: Х" '1п(Х) = е(Х)й(Х) + р(Х). Здесь остаток р(Х) записывается следующим образом: (6.62) р(Х) =рв+ р~Х+рзХ + .. + р,-ь- Х" Также можно записать следующее: р(Х) = Х" га(Х) по молулю й(Х). (6.63) Прибавляя р(Х) к обеим частям уравнения (6.62) и исполмуя сложение по модулю 2, получаем следующее: р(Х) + Х" га(Х) = е(Х)й(Х) = ()(Х).
(6.64) Левая часть уравнения (6.64) является действительным полиномом кодового слова, так как это полинам степени л — 1 или менее, который при делении на й(Х) лает нулевой остаток. Это кодовое слово можно записать через все члены полинома; Р(Х)+Х щ(Х)=ра+р~Х+рзХ +" +р~-~ ~Х" +теХ +тХ" + "+тс-1Х Полином кодового слова соответствует вектору кода 6.7. Циклические коды 386 Используя й(Х) = 1+ХьХ' как полиномиальный генератор степени л — к= 3, можно полу- чить циклический код (и, А) =(7, 4). Или же с помощью й(Х) = 1+ Х+ Х'+ Х", где л- к=4, можно получить циклический код (7, 3). Итак, если й(Х) является полиномом степени л -/г и множителем Х" + 1, то й(Х) однозначным образом генерирует циклический код (и, А).
и=(и.и...,р.. ы р. ~...,и,). ,-х р (6,65) бит сасбщсррии бнт чстнасти Пример 6.8. Циклический код в систематической форме С помошью полипомиального генератора й(Х) = 1+ Х+ Х' получите систематическое кодо- вое слово из набора кодовых слов (7, 4) лля вектора сообшения ш = 1 0 0 1 1. Решение ш(Х) = 1 + Х + Хг, л = 7, А = 4, л — /г=З; Х' пг(Х)=Х(1+Х +Х)=Х +Х +Ха Разделив Х" 'ш(Х) на й(Х), можно записать следующее: т'+х' ° х'-а х+х'+х'р С х+х'г ,ррхр р„,р ррхр, р<хр Используя уравнение (6.64), получаем следуюшее: ()(Х) = р(Х) + Хгш(Х) = 1 + Х' + Х + Ха ()щ 100 1011 биты четяостя биты сообщения 6.7.4.
Логическая схема для реализации полиномиального деления Выше показывалось, что при циклическом сдвиге полинома кодового слова и кодиро- вании полинома сообшения применяется операция деления полиномов друг на друга. Такие операции легко реализуются в схеме деления (регистр сдвига с обратной свя- зью). Итак, пусть даны два полинома (г(Х) и й(Х), где У(Х) = "а+ ыгХ+ ыгХ + ... + ы„,Х и Фтхрг да+лрХ+дгХ + ... +килы, причем т>р.
Схема деления, приведенная на рис. 6.16, выполняет полиномиальное деление ы'(Х) на й(Х), определяя, таким образом, частное и остаток: р Ч(Х)+ ч(х) р(х) й(х) й(х) к следующий значащий коэффициент в Глава б. Канальное кодирование:часть 1 В исходном состоянии разряды регистра содержат нули. Коэффициенты тт(Х) поступают и продвигаются по регистру сдвига по одному за такт, начиная с коэффициентов более высокого поРЯдка. После Р-го сдвига частное на выходе Равно Яы гы„; это слагаемое наивысшего порядка в частном. Далее для каждого коэффициента частного ф из делимого нужно вычитать полином х)я(Х). Это вычитание обеспечивает обратная связь, отображенная на рис. 6.16.
Разность крайних слева р слагаемых остается в делимом, а слагаемое обратной связи х)4(Х) формируется при каждом сдвиге схемы и отображается в виде содержимого регистра. При каждом сдвиге регистра разность смешается на один разряд; слагаемое наивысшего порядка (которое по построению схемы равно нулю) удаляется, в то время ка Ъ'(Х) перемешается на его место. После всех ш+ 1 сдвигов регистра, на выход последовательно выдается частное, а остаток остается в регистре. 3 о - т -~ и» (первым идет хозффициент старшей степени) Пример 6.9. Схема полиномнального деления Используя схему деления, показанную на рис. 6.16, разделите тг(Х) = Х'+ Х'+ Ле (Ъ'=00010 ! 1) на й(Х)= (1+ Х+ Х').
Найдите частное н остаток. Сравните реализацию схемы и действия, происходящие при прямом делении полиномов. Реигенне Схема деления должна выполнить следующее действие: Х'+ Хз+ Хе р(Х) Х Хз 1 Х Хз Полинам обратной связи Вход 0001011 Выход Рис. 6.17, Стема деления дяя примера 69 Необходимый регистр сдвига с обратной связью показан на рис. 6.17. Предположим, что первоначально регистр содержит нули. Схема выполнит следующие шаги. Входная очередь Номер сдвига Содержимое регистра Выход и обратная связь После четвеРтого сдвига коэффициенты частного !а,), последовательно поступающие с выхола, выглядят как 1 1 1 1 или же полипом частного имеет вид с)(Х) = 1 + Х + Х' + Х'.
Ко- 6.7. Циклические коды 387 0001011 000101 00010 0001 000 00 0 Рис. 6.16. Погинеская схема дяя реализации пояинаниаяьного деления 000 1ОО 110 011 011 1!! !О! 100 эффипиенты остатка (р,) имеют виа 1 О О, т.е. поливом остатка имеет виа р(Х) = 1. Таким образом, схема выполнила следующие вычисления: ХЗ „Хз Хб 2 3 3 -1+Х+Х +Х + 1+Х+ Х' 1~-Х+ Х Прямое деление полиномов дает результат, показанный нике.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
