Вернер М. Основы кодирования (2004) (1151882), страница 32
Текст из файла (страница 32)
Если входная последовательность имеет конечную длину, то^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.
Процесс кодирования начинается с So, T-e- состояния, в которомХг = Х 2 = Х 3 = 0.1. Если первый информационный бит равен «0», кодер остаетсяГлава 4- Сверточные кодыв состоянии So- На выход выдаются кодовые символы «00».Такой исход на рис. 4.4 обозначен через «0/00».2. Если первый информационный бит равен «1», кодер переходитв состояние $1 (см табл. 4.1). Выход в этом случае равен «11».Этот переход обозначен «1/11». Продолжая этот процесс вправо, можно построить всю диаграмму состояний (рис.
4.4).Диаграмма рис. 4.4 содержит всю информацию о сверточном коде. Кодирование информационной последовательности эквивалентнодвижению по некоторому неразрывному пути по диаграмме состояний. При программной реализации, например, кодирование можетбыть наиболее эффективно осуществлено исключительно с помощьюзаранее записанных в памяти таблиц переходов между состояниями.Рассмотрим такое альтернативное кодирование на.нримере.1/10о/оо/v"v"СостояниеРебро: Переход в состояние на /-ом шагеРис.
4.4. Диаграмма состояний сверточного (2,1,3)-кода.Пример: Кодирование сверточного (2,1,3)-кода с помощью таблиц переходов.Выпишем для каждого состояния два его последующих, в зависимости от значения очередного бита («0» или «1»). Для этих путейвыпишем также соответствующие пары кодовых бит. Полученныерезультаты сведены в таблицу 4.2.Рассмотрим кодирование информационной последовательностии[п] = 1,0,1,1,1. Процесс начнем из состояния So и в нем же и закончим, добавив к и[п) «хвост» из трех нулей. В результате получимпоследовательность состояний{S[n]} = {50,51,52,55,53,57,^6,64,-So}(4-32)и кодовое слово{v[n}} = {1,1,0,1,0,0,0,1,0,1,0,1,0,0,1,1}."(4.33)4-4- Граф состояний231Таблица 4.2. Таблица переходов для сверточного (2,1,3)кода.СостояниеНовое состояние S[n + 1] Кодовые биты010100100111230110245110036710014011100523100164500117670110Таблица переходов в некоторых случаях может помочь оценить качество выбранного сверточного кода.
Сравним, например, построчно пары кодовых бит в последних двух столбцах таблицы 4.2. Мыувидим, что различие между этими парами (расстояние Хэмминга)в каждой строчке максимально и равно 2. Это значит, что на начальных отрезках любых двух альтернативных путей («0» и «1»)всегда достигается максимальное расстояние Хэмминга и, поэтому,мы можем сказать, что, на первый взгляд, выбранный код являетсяхорошим. Конечно же, для более точного анализа необходимо рассматривать длинные отрезки альтернативных путей. Здесь возникает понятие свободного кодового расстояния djree, о чем пойдет речьниже.Из диаграммы состояний рис. 4.4 становится очевидным, чтосложность кодирования (а также и декодирования) возрастает с ростом числа состояний.
Число состояний, в свою очередь, однозначноопределяется количеством двоичных разрядов памяти кодера т.Для сверточного (п, к, т)-кода полная память кодера определяется как(4.34)М=г=1Заметим, что именно М последних информационных разрядов оказывают влияние на процесс кодирования. Этим разрядам соответствуют в точности 2м различных состояний схемы кодера.232Глава 4- Сверточные кодыПример: Сверточный (ЗД,2)-код.Заданы порождающие многочлены<h(X) = 1 + X,g2(X)2= 1 + X ,g3(X)2= 1+ X + X(4.35)и информационная последовательность(4.36){и[п}} = {1,1,0,0,1}.Найдите:1.
Схему кодера.2. Состояния кодера.3. Диаграмму состояний.4. Таблицу переходов между состояниями.5. Кодовую последовательность для и[п], если кодирование начинается и заканчивается в нулевом состоянии.Решение.1.*2X1*1Рис. 4.5. Схема кодера сверточного (3,1,2)-кода.2.Таблица 4.3. Состояния кодера.Состояние регистраCoCTOHHHeSi12XIi = х 2 + 2xi0001010121134-4- Граф состояний233,3.ГРис. 4.6. Диаграмма состояний сверточного (3,1,2)-кода.4.Таблица 4.4. Таблица переходов между состояниями сверточного (3,1,2)-кода.Состояние0Новое состояние S[n + 1]Кодовые биты010101000111123101010201011100323ПО0015.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
