Тема 5. Кодирование канала (часть 3) (774436)
Текст из файла
каналу, который всегда вносит ошибки в виде пакета 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. Логическая схема для реализации полиномиального деления Выше показывалось, что при циклическом сдвиге полинома кодового слова и кодиро- вании полинома сообшения применяется операция деления полиномов друг на друга.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
