Вернер М. Основы кодирования (2004) (1151849), страница 33
Текст из файла (страница 33)
Процесс кодирования начинается с 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.
Так как кодирование должно заканчиваться в нулевом состояниикодера, добавим к информационной последовательности два нуля иполучим{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)-кода.Для ответа на этот вопрос рассмотрим модифицированную диаграмму состояний рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
