Тема 5. Кодирование канала (часть 3) (Материалы лекций)

каналу, который всегда вносит ошибки в виде пакета 3-битовых ошибок, и, следовательно, нет необходимости в исправлении одно- или двухбитовых ошибок. Можно ли настроить образующие элементы классов смежности так, чтобы они соответствовали только трехбитовым ошибкам? Нетрудно определить, что в последовательности из 8 бит существует (, ~ = 56 возможностей произвести трехбитовую ошибку. Если единст- венным нашим желанием является коррекция только этих 56 моделей трехбитовых ошибок, то кажется, что в нормальной матрице достаточно места (достаточное количество классоя смежности), поскольку всего в ней имеется 64 строки. Ьудет ли это работать? Однозначно, нет.

Для любого кода главным параметром, определяющим способности кода к коррекции ошибок, является Ы, . Для кода(8, 2) и', =5, а это означает, что возможно исправление только 2-битовых ошибок. Как нормальная матрица может помочь разобраться, почему эта схема не будет работать? Чтобы осуществить исправление х-битовых ошибок для группы х-битовых моделей ошибки, полная группа векторов с весовым коэффициентом х должна быть классом смежности, т.е. они должны находиться только в крайнем левом столбце.

На рис. 6.15 можно видеть, что все векторы с весовым коэффициентом 1 и 2 находятся в крайнем левом столбце нормальной матрицы и нигде более. Если мы даже и втиснем все векторы с весовым коэффициентом 3 в строку со второго номера по 5?-й, увидим, что некоторые из этих векторов снова появятся в матрице где-нибудь еше (что нарушит основное свойство нормалыюй матрицы).

На рис. 6.15 затененные блоки обозначают те 56 векторов, которые имеют весовой коэффициент 3. Взгляните на образующие элементы классов смежности, представляющие 3-битовые модели ошибки, в строках 38, 41-43, 46-49 и 52 нормалыюй матрицы. Потом посмотрите на позиции в тех же строках в крайнем правом столбце, где затененные блоки показывают другие векторы с весовым коэффициентом 3.

Видите некоторую неопределенность, сушестяуюшую для каждой строки, о которых говорилось выше, и понятно ли теперь, почему нельзя исправить все 3-битовые модели ошибки с помощью кода (8,2)? Допустим, декодер принял вектор с весовым коэффициентом 3 — 11001000, размещенный в строке 38 в крайнем правом столбце. Это искаженное кодовое слово могло появиться, во-первых, при передаче кодового слова 1 1 00 1 1 1 1, искаженного 3-битовой модели ошибки 00000111, а во-вторых, при передаче кодового слова 00000000, искаженного 3-битовой моделью ошибки 1 1 00 1 0 00. 0.7. Циклические коды Важным подклассом линейных блочных кодов являются двоичные циклические коды (сус11с сог)ез). Код легко реализуется на регистре сдвига с обратной связью; на подобных регистрах сдвига с обратной связью вычисляется синдром; алгебраическая структура циклического кода естественным образом позволяет эффективно реализовать методы декодирования.

Итак, линейный код (и, к) называется циклическим, если он обладает следующим свойством. Если и-кортеж () = (и,, иь иь ..., и„,) является кодовым словом в подпространстве Я, тогда ()(1) = (и„ь и,, иь кь ..., и„,), полученный из () с помощью циклического сдвига, также является кодовым словом в Я. Или, вообще, Щ) = (и„„и„„ь ..., и„ь и,, иь ..., и„,,), полученный! циклическими сдвигами, является кодовым словом в Б.

382 Глава б. Канальное кодирование:часть 1 Компоненты кодового слова 1) = (ие, иь иь ..., и„,) можно рассматривать-как коэффициенты полинома ЩХ): С(Л) = ие + и,Х+ и,Х + „. ь и„,Л (6.54) Полиномиальную функцию ~1(Х) можно рассматривать как "заполнитель" разрядов кодового слояа 1)„т.е, вектор и-кортежа описывается полиномом степени и-1 или меньше. Наличие или отсутствие каких-либо членов в пслиноме означает наличие 1 или О в соответствующем месте л-кортежа. Если и„;й компонент отличен от нуля, порядок полинома равен и-1. Удобство такого полиномиального представления кодового слова станет более понятным по мере дальнейшего обсуждения алгебраических свойств циклических кодов.

6.7.1. Алгебраическая структура циклических кодов Х'О(Х) 1)со(Х) ( ) (6.55,а) или, умножая обе части ураянения на Х" + 1, Х'О(Х) =о(Х)(Х" + 1)+О" (Х), остаток (6.55,б) что в модульной арифметике можно описать следующим образом: 1)~'~(Х) = Х()(Х) по модулю (Х" + 1) . (6.56) Здесь "х по модулю у" означает остаток от деления х на у. Ниже справедливость вы- ражения (656) демонстрируется для случая 1= 1.

()(Х)=ив+и,Х+изХ +...+и„зХ" +и„,Х" ХЦХ) = иеХ е и~Х + игХ + ... + и„зХ" ~-ь и„~Х" К последнему выражению прибаяим и вычтем и„, или, поскольку мы пользуемся арифметическими операциями по модулю 2, можем прибавить и„, дважды. ХЬ(Х) = ц 1+исХ+и~Х +изХ + "+ид, зХ" '+и„|Х" +ид ~ =() (Х)+ик 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. Логическая схема для реализации полиномиального деления Выше показывалось, что при циклическом сдвиге полинома кодового слова и кодиро- вании полинома сообшения применяется операция деления полиномов друг на друга.