Вернер М. Основы кодирования (2004) (1151849), страница 32
Текст из файла (страница 32)
Нумерация элементов, как правило,начинается с нуля, поэтому иг[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).
Если входная последовательность имеет конечную длину, то^226Глава 4- Сверточные кодымы фактически имеем дело с блоковым кодированием, поэтому, j-ювыходную последовательность можно представить в виде.,кVj(X) = 52gji{X)ui(X).(4.17)г=1Так как имеется п выходов и кодовый многочлен образуется их перемешиванием, удобно записатьпv(X) = Y,XJ~\(Xn)-(4-18)В этом случаепкv(X) = Y,X>-1 ^9ц(Хп)щ{Хп).(4.19)Поясним сказанное на примере сверточного (2,1,3)-кода.П р и м е р : Представление сверточного (2,1,3)-кода в виде многочлена.В соответствии с рис. 4.2, имеемдх = 1 + X2 + X3 и да = 1 + X + X2 + Xs.(4.20)В качестве информационной последовательности выберем{u|n]} = {1,0,1,1,1}.(4.21)Этой последовательности соответствует многочлени{Х) = 1 + X2 + Хг + Х\(4.22)поэтому,i»i(X) =v2(X)(4.23)u(X)-gi(X)=234237=(1 + Х=и{Х) - 5 2 = 1 + Х + Х3 + Х* + Х5 + Х7.+Х+ Х )(1 + Х+ Х ) = 1+ ХСогласно (4.8), кодовый многочлен определяется какv{X)=22vx{X ) + Xv2(X )=(4.24)иЫ+ Х +Х +15Х ,4-3.
Полиномиальное представлениечто соответствует кодовому слову{«[п2]} = {1,1,0,1,0,0,0,1,0,1,0,1,0,0,1,1}.(4-25)Для того, чтобы показать связь между блоковыми и сверточнымикодами, представим процесс кодирования сверточных кодов в видепроизведения информационного вектора и = (ui,« 2 , Щ • • •) И а п о "рождающую матрицу GV= U0G :/G0Gi G2-- GmОО О О •Л0 G0GiGm_i G m 0 0 00 0 GoG m _ 2Gm_i G m О О(4.26)Так как информационный вектор может иметь бесконечную длину,матрица G не ограничена справа и снизу, поэтому, ее часто называют полубесконечной. Если вектор и конечен, то мы имеем дело снесколько специфичным блоковым кодом.Порождающая матрица G составлена из регулярных подматрицGo,Gi,-- , G m , каждая из которых определяется импульсным откликом кодераG, =9u,i 921,1912,1 922,19nl,l9n2,l\ 9lk,l 92k,l9nk,l(4.27)Рассмотрим построение матрицы G на примере сверточного (2,1,3)кода.Пример: Порождающая матрица сверточного (2,1,3)-кода.Рассмотрим уже знакомый нам сверточный код с параметрамик = 1,п = 2, т = 3, импульсные отклики которого равныЫ " ] } = {1,0,1,1} и Ы " ] } = {1,1,1,1}.(4-28)Этот код имеет т + 1 = 4 внутренних подматриц, которые определены какGo = (</п,о 521,0) = (1 1)G i = (#п,1 <?2i,i) = (0 1)G2 = (ffll,2 #21,2) = (1 1)G3 = (311,3 521,з) = (1 !)•(4.29)Глава 4- Свершенные кодыТогда порождающая матрица равна/ 1 1 0 1 1 1 1 1 0 0 0 00 0 1 1 0 1 1 1 1 1 0 00 0 0 0 1 1 0 1 1 1 1 1(4.30)Самым простым способом проверки правильности (4.30) является кодирование информационного вектора (100- --0).
В этом случае, результатом должны быть чередующиеся друг с другом импульсныеотклики кодера. Таким образом( 1 0 0 •••)/ 1 1 0 1 1 1 1 1 0 0 0 0 ••• \0 0 1 1 0 1 1 1 1 1 0 0 ••= (4.31)0 0 0 0 1 1 0 1 1 1 1 1 •••/= ( 1 1 0 1 1 1 1 1 О-• • ) ,что и совпадает с ожидаемым результатом.С другой стороны, из свойства линейности схемы кодера следует,что все строки матрицы равны, и, начиная со второй, сдвинуты нап позиций относительно предыдущих. Это обстоятельство еще разподтверждает правильность найденного решения.4.4. Граф состоянийРегистры кодеров содержат ограниченное число двоичных разрядов,следовательно, число состояний, в котором может находиться кодер,всегда конечно. Именно поэтому процесс кодирования можно описать как последовательность смены состояний кодера.
Такой подходявляется ключевым и ведет к более глубокому пониманию свойствсверточных кодов. Более того, он способствует разработке эффективных алгоритмов кодирования и декодирования. Мы разовьем этуидею на нескольких примерах.Пример: Описание состояний сверточного (2,1,3)-кода.Скопируем схему кодера рис. 4.2 с единственной разницей: вместоразрядов регистра сдвига поставим переменные Xi,X2 и Х$. Такаямодифицированная схема представлена на рис. 4.3.
'4-4- Граф состояний229Jхъ XР и с . 4.3. Граф потока(2,1,3)-кода.состоянийкодерасверточногоТак как Х\, Х2, Хз - двоичные переменные, то кодер, изображенный на рис. 4.3, может находиться в одном из 2 3 = 8 состояний. Этисостояния пронумерованы в лексикографическом порядке и приведены в таблице 4.1. Нумерация состояний может быть произвольной, однако, лексикографический порядок наиболее удобен для программной реализации.Таблица 4.1. Таблица состояний.Состояние регистраСостояние SjХзХ2XIг = хз + 2x2 + 2 2 ц00001001010211030014101501161117Смена состояний регистра кодера происходит следующим образом: переменные Xj и Хг заменяются на Хг и Хз соответственно, а вразряд Хз загружается новый информационный бит, поэтому, каждое состояние может переходить только в два последующих в зависимости от того, «О» или «1» были поданы на вход регистра сдвига.Все возможные смены состояний, их зависимость от загружаемогобита, а также кодовые символы для этих переходов показаны на рис.4.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
