Вернер М. Основы кодирования (2004) (1151849), страница 31
Текст из файла (страница 31)
С помощью соответствующего кодового многочлена проверьтеправильность, кодового слова, полученного в п. 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.Принятое слово' Выходнойрегистр\ Модифи кадиясиндромаИсправление ошибкиР и с .
3.31. Декодер Меггитта для укороченного (12,8)-кодаХэмминга,ГЛАВА 4СВЕРТОЧНЫЕКОДЫ4.1. ВведениеВ современной информационной технике сверточные коды играюттакую же важную роль как и блоковые. Первые попытки сопоставления сверточных и блоковых кодов были сделаны в 50-е годы. Сэтого времени блоковые коды быстро нашли эффективное применение, в то время как сверточные коды оставались на заднем плане.Этот процесс продолжался до тех пор, пока в 1967 г. не был найденэффективный алгоритм декодирования сверточных кодов.
Сегоднясверточные коды играют ведущую роль в современных системах связи. Это в первую очередь относится к цифровому радиовещанию и кмобильной связи сети GSM. Сверточные коды позволяют также эффективно бороться с помехами, вызванными многолучевым распространением радиоволн. В последние годы сверточные коды получилидальнейшее развитие в связи с открытием турбо-кодов. Достаточносказать, что использование турбо-кодов в современных системах передачи данных позволило достичь скоростей передачи информацииблизких к пропускным способностям каналов.
В связи с этим весьма неожиданным обстоятельством в мобильных сетях радиовещания был принят стандарт UMTS -(Universal Mobile TelecommunicationSistem - англ.).Важнейшими отличиями сверточных кодов от блоковых являются следующие:1. Сверточные коды позволяют производить кодирование и декодирование потоков данных непрерывно во времени.2. Сверточные коды не нуждаются в блоковой синхронизации.3. Применение сверточных кодов позволяет достичь очень высокой надежности передаваемой информации.Глава 4- Сверточныекоды4. «Хорошие» сверточные коды могут быть найдены путем моделирования.Подробнее изложение теории сверточных кодов и областей ихприменения выходит за рамки этой книги.
В данной главе мы ограничимся изложением только самых необходимых теоретических основи приведем типичные примеры применения сверточных кодов. Болееподробное описание можно найти, например [5],[18],[16].4.2. Кодер и импульсный откликТермин «сверточные коды» возник из теории инвариантных линейных систем LTI (Linear Time Invariant - англ). В теории систем LTIсверткой называют характерный признак некоторой линейной операции. С точки зрения этой теории, кодирование является отображением информационной последовательности символов в кодовуюпоследовательность с помощью линейной схемы с параметрами, неменяющимися во времени.
Такое отображение наглядно показано нарис. 4.1. Последовательность информационных символов поступает в демультиплексор, который разлагает входной поток на к самостоятельных подпоследовательностей. Схему рис. 4.1 можно такжеинтерпретировать как совместное кодирование к независимых информационных последовательностей. Кодирование производится спомощью дискретной во времени схемы LTI с к входами и п выходами. Эта схема характеризуется тремя параметрами (n,fc,m), причем,параметр т определяется внутренней конструкцией кодера.ВходПринятоеслово и\щВыходКодовое словои,[и]LTI-Systemп,к,тР и с . 4.1.
Схема LTI с к входами и п выходами как кодерсверточного кода.На практике, как правило, используются двоичные сверточныекоды, поэтому, в дальнейшем мы будем говорить о последовательностях битов. В этом случае, иод линейностью схемы мы подразумева-4.2. Кодер и импульсный откликем выполнение этой схемой всех операций но правилам арифметикипо модулю 2. (т.е. в поле GF(2)).Так как декодер представляет собой дискретную схему, для егоописания будем использовать методы теории обработки дискретныхсигналов. Придерживаясь терминологии этой теории, будем говорить об информационной последовательности и[п], входных последовательностях ui[n], иг!/1])---! Wfc[n], выходных последовательностяхVi[n], V2[n],..., Vk[n] и кодовой последовательности и[пг]. Важнейшим параметром схемы LTI является импульсный отклик.
Смыслэтого параметра мы раскроем ниже.В схеме, изображенной на рис. 4.1, все выходные последовательности объединяются в одну кодовую последовательность с помощьюмультиплексора MUX. Это происходит путем поочередного считывания символов i»i[n],«2[и],... ,wn[n] при каждом фиксированном значении п.Для того, чтобы записать связь между параметрами кодера рис4.1 в компактной форме и при этом избежать путаницы, введем единые обозначения.
Фигурными Скобками будем обозначать любою последовательность символов, причем, нижние индексы используютсядля нумерации элементов последовательностей. Для импульсного отклика системы первый нижний индекс определяет номер выходнойпоследовательности, а второй - номер входной.• Входные последовательности {«J[TC]} = {UJO,UJ i,...}, при j =1,...,*;• Выходные последовательности {vj[n]} = {vjfi, Vjt\,...}, при j =l,...,n;• Информационная последовательностьк СИМВОЛОВk СИМВОЛОВ• Кодовая последовательность{v[n}}= {yho, г>2,о, • • •, ttn,q,yi,i, « 2 , ь • • •, vn,u •••}',п СИМВОЛОВп СИМВОЛОВ• Импульсный omiviuK{gji[n}} = {9jifi,9ji,i, • • .,gji,mi}С учетом введенных обозначений операцию свертки, выполняемую схемой рис.
4.1, можно записать в видекк пчг=1~i=l m=0222Глава Jf. Сверточные кодыЗамечание. Здесь символ «©# обозначает операцию линейной свертки. В дальнейшем мы будем рассматривать таксисе циклическуюсвертку «•*».Эта операция выполняется для всех выходов j. Здесь индексы,стоящие в квадратных скобках, определяют нормированные переменные времени, то есть они указывают номера элементов соответствующих последовательностей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
