Вернер М. Основы кодирования (2004) (1151882), страница 33
Текст из файла (страница 33)
Так как кодирование должно заканчиваться в нулевом состояниикодера, добавим к информационной последовательности два нуля иполучим{v[n2}} = {1,1,1,0,1,0,1,1,0,0,1,1,0,1,0,1,0,1,0,1,1}.(4.37)Графическое отображение состояний и переходов между нимидает возможность показать весь процесс кодирования непрерывно вовремени в виде сетевой диаграммы (иногда ее называют решетчатойили треллисной диаграммой).Пример: Сетевая диаграмма кодирования сверточного (3,1,2)кода.На сетевой диаграмме рис. 4.7 для каждого временного шага показаны все возможные состояния кодера. На переходах между нимиГ234Глава 4- Свершенные коды(ребрах), в качестве веса, представлены соответствующие информационные и кодовые биты. Так как в рассматриваемом примере к = 1,из каждого состояния выходят и в каждое состояние ведут в точности 21 = 2 ребра.Замечание.
Расположение состояний по вертикали специальноподобрано таким образом, чтобы все ребра, содержащие нулевойинформационный бит, вели вниз.л+1ТактыРис. 4.7. Граф потока сигналов сверточного (3,1,2)-кода.\fy\vLA4\fLXv6TakleРис. 4.8. Кодирование информационной последовательности.На рис 4.8 показано кодирование информационной последова-74-5. Структура сверточных кодовтельности (4.36). Это кодирование начинается из нулевого состоянияSo. Так как первый информационный бит равен щЩ = 1, мы попадаем в состояние Si. Этому переходу соответствует первая тройкакодовых символов «111».
Второй информационный бит щ[1] = 1 приводит нас в состояние 5з с выработкой следующей кодовой тройки«010» и т.д. В конце кодирования мы попадаем в нулевое состояние SQ.4.5. Структура сверточных кодовВ предыдущем разделе было проведено описание сверточных кодовна основе диаграммы состояний и сетевой диаграммы. Ясно, чтообе диаграммы содержат полную информацию об исследуемом коде. Описание сверточных кодов с помощью диаграмм состояний ипереходов между ними открывает возможность более глубокого исследования их структуры и свойств.До сих нор вопросы декодирования не обсуждались. Декодированию сверточных кодов будет посвящен следующий раздел этой книги.
Однако, на основании сетевой диаграммы рис. 4.8, основные требования к хорошим кодам можно наметить уже сейчас.Каждой кодовой последовательности соответствует свой путь насетевой диаграмме, поэтому, ясно, что чем больше различий междупутями, тем легче распознать истинное кодовое слово, тем меньшевероятность ошибки декодирования.Как следует измерять различие между путями?Когда мы обсуждали свойства двоичных линейных блоковых кодов (главы 2, 3), основным критерием "различия было число несовпадающих символов, т.е. расстояние Хэмминга. Для блоковых кодов минимальное расстояние Хэмминга dmin играло особую роль, нотакже не менее важным было распределение весов слов линейногоблокового кода.
Эти же рассуждения можно применить и к сверточным кодам. В этом случае нулевым словом будем считать кодовыйвектор, состоящий из одних нулей.Если рассматривать сверточные коды с конечной длиной информационных векторов, то можно считать их линейными блоковымикодами и к ним применимы все рассуждения, проведенные в главах2иЗ.Расстояния между кодовыми словами или расстояния между путями на сетевой диаграмме будем искать в метрике Хэмминга.
Вкачестве базы используем нулевую последовательность, т.е. последовательность нулевых состояний. Без ограничения обпшости считаем,Глава 4- Свврточныекодычто кодирование начинается и заканчивается в нулевом состоянии,поэтому, ненулевой кодовой последовательности на сетевой диаграмме соответствует путь, ответвляющийся от нулевого состояния, а затем сливающийся с ним.Рассмотрим ненулевую последовательность, изображенную нарис. 4.8: Ей соответствует путь, состоящий из двух участков, ответвляющихся, а затем сливающихся с нулевым состоянием. В дальнейшем такие участки будем называть базовыми путями.
Исследованиеструктуры кода сводится к анализу базовых путей.Методику такого анализа покажем на конкретном примере.Пример: Модифицированная диаграмма состояний сверточного(3,1,2)-кода.КонецР и с . 4.9. Модифицированная диаграмма состояний сверточного (3,1,2)-кода.Возьмем диаграмму состояний, изображенную на рис. 4.6. Будемисходить из того факта, что кодирование начинается и заканчивается в нулевом состоянии So, поэтому, модифицируем эту диаграмму таким образом, чтобы состояние SQ было только или начальнымили конечным (рис. 4.9). Для дальнейшего анализа промаркируемприросты весов Хэмминга информационной или кодовой последовательностей, а также прирост длины проходимого пути.
С этой цельювведем следующие неременные: для каждой информационной «1»переменную /, для возрастания веса Хэмминга кодовой последовательности на I единиц переменную D1, и, наконец, для каждойсмены состояний - переменную J. Промаркированные таким образом переходы нанесены на диаграмму состояний рис. 4.9. В этомслучае каждому пути соответствует произведение маркеров всех переходов, из которых этот путь состоит. Например, информационной4.5.
Структура сверточных кодовпоследовательности{«[п]} = {1,1,0,0}(4.38)с последовательностью состояний{a[n]} = {S0,Si,Sr2,Sb}(4-39)в качестве весовой функции будет приписано выражениеID3J • D2J • D2J = ID7J3.(4.40)Таким образом, весовая функция любого базового пути, начинающегося и заканчивающегося нулевым состоянием содержит следующие переменные:1. / с показателем, равным весу Хэмминга информационной последовательности;2. D с показателем, равным весу Хэмминга кодовой последовательности;3.
J с показателем, равным числу переходов, осуществленных наэтом пути.Пример: Базовые пути и веса сверточного (3,1,2)-кода.В таблице 4.5 представлены четыре кратчайших базовых пути иих весовые функции сверточного (3,1,2)-кода. Самый короткий изних имеет вес Хэмминга, равный 7, то есть соответствующая ему кодовая последовательность имеет единицы в семи разрядах. Из таблицы 4.5 может создасться впечатление, что с ростом длины путейих вес Хэмминга также возрастает.
Проверим, так ли это для сверточного (3,1,2)-кода.Для ответа на этот вопрос рассмотрим модифицированную диаграмму состояний рис. 4.9 и табл. 4.5. Каждое последующее удлинение пути требует прохождения некоторой «петли» на диаграммесостояний. Так как любая петля содержит минимум один переход веса $ илн больше, то вес Хэмминга будут расти с увеличением длиныпутей, поэтому, не существует путей, отличных от нулевой последовательности, с весом Хэмминга, меньшим 7.Анализ кода с помощью модифицированных диаграмм состоянийбазируется на математической теории графов, топологии и теориисистем.V238Глава 4' Сверточные кодыТаблица 4.5.
Базовые пути и их весовые функции(.ЛГ несХэмминга информационной последовательности; О вес Хэмминга кодовой последовательности; К - длина путиВесовые функции N С КСостояния S[n]So,So,SiSis2,SoS3,Si7384953S 2 ,S 0s3, s 3 , s 2 ,SSo, s, s2, Si, S2 , SoSo,1ID J •IDJ- D J • D J =--I2Da J4 222ID J •D JD J303= ID7J3222239 5ID J •IDJ •IDJ- D J • D J =-- I D J3ID3J2 10 5D2J- IDJ-1 D2J • D2J =I2Dl0J5И.
'г- ДКаждому состоянию рис. 4.9 поставим в соответствие переменныеZe - начальному, Z\,Z2,Z3 соответственно 51,5г,5з и Zaконечномусостояниям.Определим производящую функцию как(4.41)Для узлов графа можно записать следующие уравнения состояний:Zx = ID3J• Ze + IDJ • Z2(4.42)Z2 = D J • Zx + D J • Z3(4.43)Zz = ID J • Zx + IDJ • Z3(4.44)222Za = D J • Z2.(4.45)Для решения этой системы уравнений требуется несколько шагов. Из (4.44) следуетIDJ(4.46)Используя (4.43), имеемZl=1-JDJ(4.48)\239/J^.5. Структура сверточных кодовПодставляя в (4.42), получаем1-IDJZ2 = ID3J • Ze + IDJ • Z2,D2J(4.49)что приводит кr5 2 2"" /IDг> 'Jт> = 1-IDJ-IB>J- z .r eТеперь уже вес готово для того, чтобы непосредственно связать Zaи ZeZID5 / 2Z a1JZI D 7 J= * 1-IDJ-IB>J -=Z\^и передаточная функция равнаг(^ ' / ) = ! =/ Л З г щ г ^ у(452)С помощью разложения11-Х1s= 1 + X + X + X + • • • для |Х| < 1(4.53)имеемD2)+22 22+ D ) + •••) =+I D J (17 3= ID J28+ I D J*2(4.54)23l0 495+ 7 Z3 J + • • • .+ID JРазложение (4.54) определяет характеристики сверточного (3,1,2)кода.
Члены разложения содержат всю информацию о кодовых словах любой произвольной длины, первые члены соответствуют табл.4.4.Вычисленная в примере производящая функция задает весовуюструктуру кода, так как отражает влияние весов переходов на весьсверточный кодоооо осT(I,D,J)= J2 Yl Yl t(i,d,j)fDdji,d=djTeeкоэффициент t(i,d,j)ми PDdJJ.г—1(4.55)j=m+lонределяет число базовых путей с параметра-^240Глава 4. Свершенные кодыТаблица 4.6. Порождающие многочлены (в восьмеричнойформе) оптимальных сверточных кодов со скоростями R и кодовым ограничением пс.R = 1/31/2Пс9i9idfree,9i91S3R = 1/4dfrenffi 929394dfree357557785777104151761315171013151517155233572533371225273337166337584753751353677175187133 17110133 145 17515135 135 147 163208 247 37110225 331 36716235 275 313 35722912557 663 71118463 535 733 74524561 753Минимальный выходной вес пути, начинающегося в нулевом состоянии, называется свободным расстоянием djree.
При анализе корректирующей способности кода dfree играет такую же роль, как минимальное кодовое расстояние для блоковых кодов.Сверточный код считается оптимальным, если при заданной скорости кода и памяти он имеет максимальное djree. Существует довольно много оптимальных кодов, но для их построения не существует никаких аналитических методов. Оптимальные коды находятся путем компьютерного моделирования.
В литературе приведенымногочисленные таблицы порождающих многочленов оптимальныхсверточных кодов.Пример: Порождающие многочлены оптимального сверточного(3,1,2)-кода.Для построения оптимального сверточного (3,1,2)-кода воспользуемся табл. 4.6. Для заданных параметров кода коэффициенты порождающих многочленов равны д\ = 5(8) = 101, gi = 7(8) = 111и <?з = ^(g) = 111, поэтому, порождающие многочлены этого кодаимеют следующий вид(Х)д1222= 1 + X , д2(Х) = 1 + X + X , д3 = 1 + X + X .(4.56) .На рис.
4.10 показана зависимость свободного расстояния rf/reeот длины кодового ограничения для скоростей R = 1/2, R = 1/3*и4-5. Структура сверточпых кодов=R 1/4- При увеличении длины кодового ограничения dfree возрастает, т.е. выигрыш от применения кодирования тем больше, чембольше сложность используемого кода. Свободное расстояние увеличивается также при снижении скорости кода. Здесь, однако, необходимо принимать во внимание реальный выигрыш от кодирования,измеренный в дБ отношения сигнал/шум.
Этот выигрыш зависит отконкретных схем применения сверточных кодов и не всегда можетбыть достигнут снижением скорости.Р и с . 4.10. Зависимость свободного расстояния d/ r e e от длины кодового ограничения пс.Замечание. В /7/ для каждого кода дополнительно приводится выигрыш от кодирования в дБ. Там показано, что при малых скоростях кода выигрыш от кодирования для кодов с различным dfTeeприблизительно одинаков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
