Тема 5. Кодирование канала (часть 3) (774436), страница 2
Текст из файла (страница 2)
Такие операции легко реализуются в схеме деления (регистр сдвига с обратной свя- зью). Итак, пусть даны два полинома (г(Х) и й(Х), где У(Х) = "а+ ыгХ+ ыгХ + ... + ы„,Х и Фтхрг ла+дрХ+ЛгХ + ... +килы, причем т>р. Схема деления, приведенная на рис. 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~-Х+ Х Прямое деление полиномов дает результат, показанный нике. Х'+Х'+ )Х +Х+1 обратная связь после 4-го сдвига 3 Х + Х'+ Х' Х +Х +Х+1 т ттт 4 5 6 7 регистр после 4-го сдвига -3 Х'+ Х' обратная связь после 5-го сдвига -3 Х'+ Х'+ Х' Х3+ Х3+ Х3 Х'+ Х'+Х регистр после 5-го сдвига обратная связь после 6-го сдвига ХЗ+ Х Х'+ Х+1 регистр после 6-го сдвига обратная связь после 7-го сдвига регистр после 7-го сдвига (остаток) В.7.5.
Систематическое кодирование с (и — «)-разряднь3м регистром сдвига 8(Х) = 1+ 8~Х+ 83Х + ". + 8д -3- 1Х" + Х" ". (6.66) Следующие шаги описывают процедуру кодирования, использующую устройство, изображенное на рис. 6.18. Глава 6. Канальное кодирование: часть 3 заа Как было показано в разделе 6.7.3, кодирование с помощью циклического кода в систематической форме включает в себя вычисление битов четности, как результат деления Х" "щ(Х) по модулю 8(Х),„иными словами, делелие сиещеллого вверх (смещенного вправо) полиномиального сообщения на полиномиальный генератор 8(Х).
Сдвиг вверх приводит к освобождению места для битов четности, которые прибавляются к разрядам сообщения, что в результате дает вектор кода в систематической форме. Сдвиг вверх на л-1 разрядов сообщения является тривиальной операцией и в действительности не выполняется в схеме деления. На самом деле вычисляются только биты четности; затем они помещаются на соответствующие места рядом с битами сообщения. Полипом четности — это остаток от деления на полиномиальный генератор; он находится в регистре после л сдвигов через (л — 1)- разрядный регистр сдвига с обратной связью, показанного на рис. 6.17.
Отметим, что первые л — Зг сдвигов по разрядам — это просто заполнение регистра. У нас не может появиться никакой обратной связи, пока не будет заполнен крайний справа разряд; следовательно, мы можем сократить цикл деления, загружая входные данные с выхода последнего разряда, как показано на рис. 6.18. Слагаемое обратной связи в крайнем левом разряде является суммой входных данных и крайнего правого разряда.
Гарантия создания этой суммы — обеспечение Ха=8„2= 1 для произвольного полиномиального генератора 8(Х). Соединения схемы обратной связи соответствуют коэффициентам полиномиального генератора, которые записываются в следующем виде: од о — К разрядсе рвгистра сдвига Переключатель 2 1. При первых гг сдвигах ключ 1 закрыт лля передачи битов сообщения в (и-К)- разрядный регистр сдвига.
2. Ключ 2 установлен в нижнее положение для передачи битов сообщения на выходной регистр в течение первых й сдвигов. 3. После передачи й-го бита сообщения ключ 1 открывается, а ключ 2 переходит в верхнее положение. 4. При остальных л — а сдвигах происходит очищение кодируюших регистров, биты четности перемешаются на выходной регистр. 5. Общее число сдвигов равно и, и содержимое выходного регистра представляет собой полипом кодового слова р(Х) ч- Х" ьпз(Х). Пример 6.10. Систематическое кодирование циклического кода Используя регистр сдвига с обратной связью, показанный иа рис.
6.18, кодируйте вектор сообщения гп = 1 О 1 1 в кодовое слово (7, 4). Полиномиальный генератор й(Х) = 1 ч- Х+ Х'. Решепие Х" ()О = г((Х)й(Х) + р()О р(Х) = (Х' ч- Х + Хь) по модулю (1 ч- Х + Х ) для (п — й) = 3-разрядного регистра сдвига, показанного на рнс. 6.!9, действия будут сле- дующими. Входная очередь Номер сдвига Содержимое регистра Выход и обратная связь 389 6.7. Циклические коды !О!1 101 1О 1 Рис. 6,!В. Кодироваиие с помощью (и — Гс)-разрпдиого регистра сдвига ш= 1 0 1 1 щ(Х) = 1 + Хз + Хз Л" гпз(Х)=Х го(Х) =Х +Х +Хв 000 11О !01 100 !00 пт ° в(х)=1 Х Х Выход Переключатель 2 Риг. 61й Пример кадиравания циклическою кода (7, 4) с па- мощью (п †'к)-разрядною региснкра сдвига После четвертого сдвига ключ 1 открывается, ключ 2 переходит в верхнее лолозхение, а би- ты четности переходят в выходной регистр.
Выходное кодовое слово () = 1 0 0 1 0 1 1 или, в лслиномиальной форме, ЩХ) = 1+Х'+ Х'+ Хч. 6.7.6. Обнаружение ошибок с помощью (п- 1г)-разрядного регистра сдвига Передаваемое кодовое слово может быть искажено помехами, и, следовательно, принятый вектор будет искаженным вариантом переданного кодового слова. Допустим, что передается кодовое слово, имеющее в полнномиальном представлении внд ЩХ), а принимается вектор, в полиномиальном представлении имеющий вид Х(Х). Поскольку ()(Х) — зто полипом кодового слова, он должен без остатка делиться на полиномиальный генератор й(Х). ()(Х) = ш(Х)й(Х) (6.67) 7(Х), искаженную версию ()(Х), можно представить следующим образом: Х(Х) = ЩХ) + е(Х) . 7(Х) = г((Х)й(Х) + б(Х) .
(6.69) Здесь $(Х) — лелином степени и -Х вЂ” 1 или меньше. Соответственно, синдром — зто (п — (т)-кортеж. Используя уравнения (6.67) и (6.69), получаем следующее: е(Х) = [ш(Х) + т)(Х)) й(Х) + $(Х). (6.70) (6.68) Здесь е(Х) — полипом модели ошибки. Декодер проверяет, является ли У(Х) полино- мом кодового слова, т.е. делится ли он на й(Х) без остатка. Это осуществляется путем вычисления синдрома принятого полинома. Синдром $(Х) равен остатку от деления Х(Х) на я(Х): аакч Глава б.
Канальное кодирование: часть 1 Сравнивая уравнения (6.69) и (6.70), видим, что синдром Б(Х), полученный как Х(Х) по модулю й(Х), аналогичен остатку деления е(Х) на й(Х). Таким образом, синдром принятого полинома К(Х) содержит информацию, необходимую для исправления модели ошибки. Расчет синдрома выполняется с помощью схемы деления, почти аналогичной схеме кодирования, используемой в передатчике. Пример вычисления синдрома со сдвигом на (л - lс) разрялов регистра приведен на рис. 6.20 с использованием вектора кода, полученного в примере 6.10.
В исходном состоянии ключ 1 закрыт, а ключ 2 открыт. Принятый вектор подается во входной регистр, в котором в исходном состоянии все разряды имеют нулевое значение. После того как весь принятый вектор будет занесен в регистр сдвига, содержимое регистра — это и есть синдром. Теперь ключ 1 открывается, а ключ 2 закрывается, так что вектор синдрома теперь можно извлечь из регистра. Описанная последовательность действий имеет следующий вид. Приняты вектор 1оо1о11 лишив си каром Рис. 6.20 Пример вычисления синдрома с яомошью (я — 9)-разрядною регионра сдвига Входная очередь Номер сдвига Содержимое регистра Если вектор синдрома нулевой, считается, что принятый вектор является правильным кодовым словом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
