Вернер М. Основы кодирования (2004) (1151849), страница 34
Текст из файла (страница 34)
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приблизительно одинаков. При этом, однако, предполагается согласование алгоритма декодирования и канала, и, поэтому, этотрезультат не может быть распространен на общий случай.Особый класс сверточных кодов образуют так называемые катастрофические сверточные коды.
Они не пригодны для использования, так как приводят к катастрофическому размножению ошибок.Рассмотрим пример катастрофического кода, а заодно научимся распознавать класс катастрофических кодов.Пример: Катастрофический сверточный (2,1,2)-код.Пусть сверточный код задан следующими многочленамиgi(X) = l + .1. Постройте схему кодера;(4.57)242Глава 4- Сверточиые коды2.
Постройте диаграмму состояний;3. Закодируйте нулевую последовательность, т.е{и[п}} = {0,0,0,...};.4. Закодируйте последовательность {«[ п ]} = {1,1,1,...};5. Предположим, что при передаче последовательности единицпроизошли ошибки в первом, втором и четвертом битах кодовой последовательности. Как много ошибочных бит в информационной последовательности появится при декодировании?6. Как но диаграмме состояний можно определить, что код является катастрофическим?Решение/1.Рис. 4.11. Схема кодера сверточного (2,1,2)-кода.2.1/00Рис. 4.12.
Диаграмма состояний сверточного (2,1,2)-кода.3. Так как кодирование начинается из нулевого состояния и мывсе время в нем остаемся, кодовым словом будет нулевая последовательность.4. Информационной последовательности единиц соответствуетпоследовательность состояний[*)} = {So,Si,S3,S3,...},(4.58)4-5.
Структура сверточных кодов 243,что приводит к кодовой последовательности{t»[n2]} = {1,1,0,1,0,0,0,0,...}.(4.59)5. Если первый, второй и четвертый биты в (4.59) приняты ошибочно как «0», то декодер примет решение, что была передана нулевая информационная последовательность. Здесь мы имеем граничный случай - размножение ошибок.6. Признаком катастрофичности кода является появление «петли» в модифицированной диаграммые состояний, в которой соответствующие кодовые символы являются нулевыми. На диаграммесостояний рис.
4.12 при переходе из состояния 5з в состояние 5з вессоответствующих кодовых символов равен нулю.В заключении рассмотрим систематические сверточные коды.Эти коды используются достаточно редко, так как в них не достигается оптимальное свободное кодовое расстояние djTee. Тем не менее, внекоторых приложениях, например, при треллисной модуляции, применение систематических сверточных кодов весьма желательно [12].Пример: Систематический сверточный (2,1,1)-код.Систематический код задан порождающими многочленамиSi = 1 и 92(Х)(4.60)= 1 + Х.1. Постройте схему кодера;2.
Постройте диаграмму состояний;3. Определите dfree с помощью весовой функции кода;4. Является ли код катастрофическим?Решение.1.•v,1Рис. 4.13. Схема кодера систематического сверточного(2,1,1)-кода.^244Глава 4- Сверточные коды2.1/11о/оо/(So)(sT) f i/io0/01Рис. 4.14. Диаграмма состояний систематического сверточного (2,1,1)-кода.3. Вычисление dfree с помощью весовой функции.НачальноесостояниеРис. 4.15.
Модифицированная диаграмма состояний сверточного (2Д,2)-кода.Для состояний в узлах рис. 4.15 имеют место два равенстваZx= ID2JZe + IDJZl(4.61)Za= DJ-Zy.(4.62)Связь между входом и выходом определяется как( 4 6 3 )<и, следовательно, получаем весовую функциюT(I, D, J) = ID3J2(1= ID3J2+ IDJ + I2D2J2+ I3D3J3+ I2DAJ3J 4 + / 4 £ > 6 J5 + • • • .+ I3Db+ •••)=( 4 -64)Учитывая, что dfree определяется наименьшим показателем D в весовой функции, имеемdfree = 3.(4.65)4. Код не является катастрофическим, так как единственная«петля» на модифицированной диаграмме состояний обладает весомIDJ и, следовательно, повышает вес кодовой последовательности наединицу.4-6.
Декодирования по максимуму правдоподобия4.6. Декодирования по максимум/ правдоподобияДля декодирования сверточных кодов имеются две альтернативы:последовательное декодирование и алгоритм Витерби.Алготитмы последовательного декодирования - стек-алгоритмили алгоритм Фано могут рассматриваться как методы проб и ошибок при поиске правильного пути на кодовом дереве. В ряде приложений использование последовательного декодирования может бытьвесьма эффективным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
