Вернер М. Основы кодирования (2004) (1151882), страница 31
Текст из файла (страница 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. Здесь индексы,стоящие в квадратных скобках, определяют нормированные переменные времени, то есть они указывают номера элементов соответствующих последовательностей. Нумерация элементов, как правило,начинается с нуля, поэтому иг[5], например, обозначает 6-ой элементвторой входной последовательности. Элементы с отрицательной временной переменной полагаются равными нулю.Замечание.
В дальнейшем, если это не будет приводить к путанице, лишние индексы будем опускать.П р и м е р : Свертка двоичных последовательностей.Выберем импульсный отклик системы, равный{Я[п]} = {1,0,1,1}.(4.2)Для входной последовательности{u[n]} = {1,0,1}(4.3)зv[n) = g\n] © и[п] = ^ ^ з["г]5[п — m].(4.4)получим сверткуm=0Найдем элементы v[n]Щ=дЩ 0 u[0] = i © i = iv[l]=(fl[0]©u[l])®( f l [l]©u[l]) ==(s[O]©u[2])©(fl[ll©u[l])©(S[2]0u[O]) ==(1©1)Ф(О0О)Ф(101) = 1фО©1 = О"й=№]©«[2])®( f f [2]© u [l])=(о©1)ф(1©о)е(1©1) =v[A]==(5[2]©«[2])ф(з[3]©«[1])(1©1)Ф(1©О) = 1ФО =v[5]=g[3]©u[2] = 1 0 1 = 1.v[3](4.5)4-2. Кодер и импульсный откликОбратим внимание на подробное обозначение операций в GF(2).
Вдальнейшем такое обозначение может быть опущено, если смысл операций следует из контекста.Рассмотрим теперь.реальную схему кодера сверточного кода.Пример: Кодер сверточного (2,1,3)-кода.Изображенный на рис. 4.2 кодер имеет п = 2 выходов, к = 1 входов и ггс = 3 (так как регистр кодера содержит три разряда so, si, S2).С точки зрения теории цифровой обработки сигналов - это нерекурсивная система с удвоением.ВходР и с . 4.2. Кодер сверточного (2,1,3)-кода.Две выходные последовательности v\]n\ и г>2[п] можно генерировать с помощью двух фильтров с конечными импульсными откликами ,7i [п] и д2[п] из входной последовательности и[п}.
Импульсныеотклики gi[n] и д2\р\ можно получить непосредственно из рис. 4.2.Учитывая, что при отсутствии связи между двоичными разрядамирегистра и выходами кодера соответствующие коэффициенты равнынулю, имеем= (1.0,1,1} и {92[п]} = {1,1,1,1},(4.6)что эквивалентно двум многочленам третьей степени.Задержка в регистре сдвига кодера также равна трем.На выходе кодера две последовательности vi[n] и г»гН объединяются в кодовую последовательность vfa]. Разность в обозначенияхвременных нормированных переменных п и п г объясняется удвоением частоты кодовой последовательности по сравнению с частотойинформационной последовательности.Работу схемы кодера объясним на следующем примере.
Пусть= {1,0,1},(4.7)Глава 4- Сверточные кодытогда{w,[n]} = {1,0,0,1,1,1}(4.8)и{«2[п]} = {1,1,0,1,1}.•(4.9)Объединяя эти последовательности между собой, на выходе кодераполучим{«[п2]} = {1,1,0,1,0,0,1,0,1,1,1,1}.(4.10)Рассматривая схему кодера в общем случае определим важнейшие параметры сверточных кодов. Так как в основе любого кодералежит регистр сдвига, то один бит входной информации оказываетвлияние на процесс кодирования на протяжении нескольких тактов.Здесь возникают такие понятия, как память кодера и длина кодовогоограничения.Так как в общем случае кодер может иметь несколько входов, топамять кодера определяется какт = max m,.(4-П)i=l,...,kКодовое ограничение является производным от памяти и определяет ширину области кодового слова, на которую влияет один входной бит, то естьпс = п{т + 1).(4.12)Как будет показано далее, параметры т и пс оказывают решающее влияние на корректирующую способность кода и сложностьалгоритма декодирования.Следующим важнейшим параметром является скорость кода R.Так как в общем случае к входным битам соответствуют h выходных, тоД=-.(4.13)пКак правило, число входов к невелико, поэтому, типичным являются кодовые скорости от 1/3 до 7/8.В современных сетях связи режимы обмена информацией оченьсильно зависят от ее характера, поэтому, необходимо учитывать,что отдельные реальные сообщения могут иметь различные конечные длины.
В связи с этим, в некоторых случаях реальные кодовые скорости могут быть существенно меньшими, чем R из (4.13).Это вызвано тем обстоятельством, что для сохранения корректирующей способности кода мы вынуждены добавлять в конце сообщения4-3. Полиномиальное представление 225J«хвост» из т нулей. Таким образом, если длина сообщения составляет L бит, то реальная (блоковая) скорость равнаkLB = -7Г~, 7 « Д Для L > т .(4.14)n(L + m)Для сообщений небольшой длины приходится считаться с относительной потерей скорости, равнойR<"5>Замечание.
Для очень коротких сообщений имеет смысл использовать при декодировании алгоритм «нейтрализации хвоста». Этоталгоритм при незначительном снижении корректирующей способности кода позволяет полностью избежать вставки т нулей вконце информационных блоков.4.3. Полиномиальное представлениеАналогично блоковым кодам (глава 3), сверточные коды могут бытьописаны с помощью многочленов. При этом становятся очевиднымине только сходство этих кодов, но и их различия.Будем рассматривать импульсные отклики кодеров сверточныхкодов как порождающие многочлены степени mi9ji(X) = gjifi+ gjitiX+ •••+ 9ji,mim+X K"(4.16)Переменная Х здесь играет роль «указателя сдвига» и никакойпсмысловой нагрузки больше не несет, Х означает гг-кратный сдвиготносительно некоторой точки отсчета (например, начала входнойпоследовательности).Замечание. В литературе вместо переменной X очень часто используют переменную D (от слова delay задержка - англ.).Так как мы по прежнему рассматриваем только двоичные коды,все коэффициенты многочленов принадлежат GF(2) и все операциинад многочленами выполняются по правилам арифметики по модулю 2.Аналогично блоковым кодам, процесс кодирования сверточныхкодов может быть описан с помощью порождающих многочленов(4.16).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
