Вернер М. Основы кодирования (2004) (1151882), страница 30
Текст из файла (страница 30)
Пакеты ATM называются ячейками - cell. Формат такойячейки представлен на рис. 3.25.1 Байты 5 6Ifiinwm Ц5.'Данные пакета14 51GFC2VPI3ЙБитVPIVCIVCIVCIРТCLPБайт 4--—~5CLPGFCНЕСРТVOVP1Приоритет потери пакетаУправление пакетомУправление ошибками в заголовкеТип данныхИдентификатор виртуального каналаИдентификатор виртуального путиРис. 3.25. Формат ячейки ЛТМ.Вся управляющая информация заголовка, занимающая 4 байта,защищена от ошибок CR.C-8 кодом из табл. 3.8. Восемь проверочныхразрядов кода CRC записываются в последний пятый байт заголов-3.13. Пример применения: ATMка и называются полем управления ошибками в заголовке ( НЕС Heder Error Control).Порождающий многочлен CRC-8 кода представляет собой произведение д{Х) = (1 + Х)р(Х), где р(Х) - примитивный многочленстепени т.
Для CRC-8 кода степень этого многочлена т = 7, длина кода га = 2 т — 1 = 127 и код содержит т + 1 = 8 проверочныхразрядов. Так как защищаемая CRC кодом информация составляет 32 бита, в стандарте ATM используется укороченный код длинып = 40 и скорость кода равна R — 32/40 = 0,8.
Такой укороченный(40,32)-код обладает высокой корректирующей способностью.Оценим вероятность необнаружимой ошибки декодирования. Укороченный (40,32)-код содержит 2 3 2 кодовых слов и имеет d m i n = 4.Будем считать, что ошибки, происходящие в канале, независимыи происходят с вероятностью Ре. Воспользуемся достаточно грубойверхней оценкой вероятности необнаружимой ошибки для линейныхблоковых кодов (2.30), получим .РтЛ=2г2Р%.(3.105)Эта верхняя оценка не учитывает особых свойств CRC кодов(см.раздел 3.11).
Из этих свойств следует, что при наличии в принятом слове четырех и более ошибок, доля необнаружимых ошибокдекодирования не превышает 1~т = 2~~7. Учитывая также, что всеошибки нечетной кратности обнаруживаются, эта доля ошибок снижается до 2~8, и, с учетом свойств CRC (40,32)-кода, верхняя оценкавероятности необнаружимой ошибки декодирования равнаР г , 2 = 2 2 4 /* 1 ."(3.106)На рис. 3.26 приведена зависимость оценок (3.105) и (3.106) от вероятности ошибки в двоичном символе Ре. При передаче информациино оптоволокну, среднее значение Ре равно 10~9 и вероятность необнаружимой ошибки декодирования не превышает 2 • 10~ .Для того, чтобы представить себе, насколько мала эта величина, приведем наглядный пример.
Пусть информация передается состандартной для ATM скоростью - 622,08 Мбит/сек, то есть каждуюсекунду в канал связи поступает 1,47-106 блоков, тогда, при непрерывной передаче, необнаружимая ошибка будет в среднем возникать15один раз в 10 лет.Реальные системы передачи данных, конечно же, не всегда соответствуют рассмотренной модели. При использовании оптоволокна качество канала может резко ухудшаться в некоторые моментыГлава 3. Циклические кодывремени. Это вызывает появление в канале пакетов ошибок большой длинны. Процесс передачи данных в такой системе можно описать с помощью диаграммы переходов с двумя состояниями (см.
рис.3.27). Этим состояниям соответствуют два режима работы декодера. В режиме исправления однократной ошибки декодер находитсяв том случае, если ранее, в течении определенного времени, ошибкив канале не фиксировались (то есть все принятые слова имели нулевой синдром). В этом случае предполагается «хорошее» состояниеканала, в котором вероятность одиночной ошибки в блоке намногопревышает вероятность многократных ошибок. Декодер остается вэтом состоянии до тех пор, пока его синдром не становится отличным от нуля. В этом случае декодер переходит в режим обнаруженияошибок. Если, при этом, синдром соответствует одиночной ошибке,то она исправляется, если обнаруживается наличие ошибки большейкратности, то весь принятый блок стирается.10°1232/>/Т «-Р,iff"ю- 25.у2 2 4 Р/ю- 3010"'Iff*10*Iff710*/»Р и с .
3.26. Оценка вероятности необнаружимой ошибки.В режиме обнаружения ошибок, попытки обнаружить и исправить ошибки уже не производятся, так как предполагается «плохое»качество канала. В этом режиме все ошибочные блоки ATM стираются. Декодер может опять вернуться в режим исправления одиночных ошибок в блоках ATM, если в течении некоторого времени онне будет обнаруживать ошибки в принятых символах.Замечание. Стертые блоки ATM не пропадают. Согласно протоколу передачи данных, в случае стирания блоков, в канал обратнойсвязи поступает запрос на их повторную передачу.3.13.Пример применения: ATMОбнаружена многратная- ошибка, ATM блок стираетсягОбнаружена однократнаяошибка, она исправляетсяОбнаруженыошибки, блокATM стираетсяРис.
3.27. Модель передачи блоков ATM по каналу с двумясостояниями.В заключении рассмотрим еще одно применение укороченного(40,32)-кода для управления ошибками в заголовке (НЕС). В силувысокой способности этого кода к обнаружению ошибок, НЕС может использоваться также для поддержания блоковой синхронизации. Опишем этот алгоритм с помощью диаграммы состояний рис.3.28.Анализ побитногосдвига заголовкаОбнаружено ееследующих друг задругом ошибочныхпакетовПоблоковыйанализ заголовковв потоке битПоблоковыйанализ заголовковв потоке битS подряд следующих блоковдекодированы правильноРис. 3.28.
Модель применения (40,32)-кода для синхронизации при передаче по технологии ATM.В начале, в состоянии «HANT» или поиска по времени, декодерГлава 3. Циклические кодыделает попытки декодирования принимаемого потока бит, побитносдвигая предполагаемое начало блока ATM. Если синдром указывает на возможно правильное декодирование заголовка блока, то декодер переходит в режим «PRESYNC» (предсинхронизация). Заголовки в принятом потоке блоков ATM декодируются, и, если при этомбыла обнаружена ошибка, декодер опять возвращается в состояние«HANT».
Если же на протяжении 5 блоков все заголовки были нродекодироваиы правильно, декодер переходит в состояние «SYNC»(синхронизация). В этом состоянии обработка информации происходит согласно рис. 3.27. Синхронизация может быть утрачена из-заошибок в канале, что обнаруживается декодером при наличии последовательных а ошибочных блоков. В этом случае декодер опятьпереходит в состояние поиска по времени «HANT».Рассмотренные примеры показывают, что применение помехоустойчивых кодов может далеко выходить за рамки только обнаружения и исправления ошибок.
Помехоустойчивые коды могут вкорне менять принципы построения систем передачи данных и улучшать их технические характеристики, поэтому, знание принциповпомехоустойчивого кодирования и областей его применения можетоказать существенную помощь нри разработке новых систем связи.З.Ц- Упражнения 215^3.14. УпражненияЗадача 3.1: Код CRC.1.
Найдите порождающий многочлен CRC (7,3)-кода;2. Приведите схему кодера систематического (7,3)-кода;3. Рассмотрите процесс кодирования информационного вектораи = (0,1,0,1) с помощью этой схемы. Найдите содержимое регистра кодера на каждом шаге кодирования;4. С помощью соответствующего кодового многочлена проверьтеправильность, кодового слова, полученного в п. 3;5. Приведите схему декодера, обнаруживающего ошибки и объясните алгоритм обнаружения ошибки в принятом слове;6. Проверьте работу декодера для случая, когда принято словог = (0,0,1,0,1,0,0,1);7.
Проведите декодирование принятого слова из п. 6 при помощи порождающей матрицы;8. Найдите максимальную длину обнаруживаемого пакета ошибок;9. Приведите пример концевого пакета ошибок максимальной длины.Решение.1. Рассмотрим примитивный многочлен третьей степени: р(Х) =Х3 + Х+1 (заметим, чтор(Х) является порождающим многочленомциклического (7,4)-кода Хэмминга). Порождающий многочлен CRC(7,3)-кода равенд(Х) = (1 + X)(l + X + X3) = X4 + X3 + X2 + 1.(3.107)2.
Схема кодера CRC (7,3)-кода представлена на рис. 3.29.лbobtb2Вычисление проверокb)I-I-I-U- u0 Mi «2 MiI*<3SiV 0 l ' | V 2 1'3 V'4 VSКодовое СЛОВОР и с . 3.29. Кодер систематического CRC (7,3)-кода.Глава 3. Циклические коды3. Работа кодера при и = (0,1,0,1) представлена в табл. 3.15.Результатом является кодовое слово v = (0,1,1, 0, 0,1, 0,1).Таблица 3.15. Вычисление проверочных символов (7,3) CRCкода с помощью схемы рис.3.29.СообщениеЬаbiъ2 ь3Коментарий001010000Инициализация1010101120111103011004-0111ТактПроверочные символы4. Вычисление кодового многочлена v(X) для информационногослова и = (0,1,0,1) в систематическом виде производится следующим образом:и(Х) =Х3 + Х• Ъ{Х) =Х4и(Х)v(X) =4Х и{Х)mod g(X) = X2 + X(3.108)+ b{X) = X7 + X5 + X2 + X,что соответствует кодовому слову v = (0,1,1,0,0,1,0,1).5. Так как CRC (7,3)-код является циклическим, то при отсутствии ошибки в канале принятый многочлен г(Х) должен делитьсяна порождающий многочлен д(Х) без остатка.
Если в результате работы декодера получен ненулевой синдром, то с уверенностью можноутверждать, что принятое слово является ошибочным. Схема вычисления синдрома представлена на рис. 3.30.При нятое словоРегистр синдромаРис. 3.30. Схема вычисления синдрома CRC (7,3)-кода.6. Работа декодера для принятого слова г = (0,0,1,0,1,0,0,1)(см. рис. 3.30) представлена в табл. 3.16 по тактам.3.14- УпражненияТаблица 3.16. Вычисление синдрома для принятого словаг = (0,0,1,0,1,0,0,1).ТактСообщениеso«100101001500111116000100700010-000148S3КоментарийИнициализацияОшибка !7. Представим принятое слово г = (0,0,1,0,1,0,0,1)) в виде многочлена и найдем остаток от деления многочлена г(Х) на д(Х)г(Х)=Х7+Х*+Хгs(X) = r(X)mod д{Х) = Хъ,(3.109)что соответствует синдрому, получаемому в предыдущем пункте.8.
Так как циклический CRC (7,3)-код образуется с помощью порождающего многочлена д(Х) четвертой степени, то все пакеты длины 4 и менее обнаруживаются.9. «Концевой» пакет ошибок длины 4 е = (0,1,0,0,0,0,1,1).Задача 3.2: Укороченный (12,8)-код Хэмминга.Рассмотрим (12,8)-код, являющийся укорочением циклического(15,11)-кода Хэмминга'. Начертите блок-схему декодера (12,8)-кодаоптимального с точки зрения сложности, исправляющего одну ошибку.Решение.Для минимизации сложности, выбернем схему декодера Меггитта, использующего вспомогательный многочлен е'(Х).
Напомним,что е'(Х) образуется умножением многочлена ошибку е(Х) на d(X),iгде d(X) = X mod g(X). В рассматриваемом примере(3.110)д(Х) = 1 +следовательно, многочлен d(X) равен(3.111)^ 218Глава 3. Циклические кодыБлок-схема декодера приведена на рис. 3.31.Принятое слово' Выходнойрегистр\ Модифи кадиясиндромаИсправление ошибкиР и с .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
