Ипатов В. Широкополосные системы и кодовое разделение сигналов (2007) (1151883), страница 76
Текст из файла (страница 76)
Допустим теперь, что кодируемый поток заканчивается после некоторого большого (не меньшего ис) числа битов и дополняется ь, — 1 концевыми нулями для обнуления регистра кодера. Реализованное практически (одним из примеров служит сошаОпе) это дополнение не повлечет существенной потери в скорости, если длина кодируемого потока многократно больше длины кодового ограничения. С другой стороны, результатом его окажется сходимость всех путей в один узел, соответствующий нулевому состоянию регистра, как показывает рис. 9.6 для кода примера 9.5.
Если начальным фрагментом такого дополненного битового потока оказывается серия из некоторого числа пд последовательных нулей, за которыми ~~( 372 Глава в. Кан льное кодирование в итироконолосных системах следует бит, равный единице, можно переместить по начальных нулей в конец потока, т.е. произвести сдвиг соответствующего пути на диаграмме на по шагов влево без изменения его веса. В результате путь ответвится от нулевого пути на самом первом шаге и вновь сольется с ним не позднее, чем за по шагов от последнего концевого нуля. Вдоль этого пути могут происходить неоднократные возвраты к нулевому пути и последующие ответвления от него (см.
рис. 9.7), каждое из которых лишь увеличит вес пути. Поскольку наша цель состоит в отыскании пути минимального веса, любые ответвления от нулевого пути, кроме первого, должны игнорироваться. Суммируя сказанное, приходим к заключению, что для нахождения минимального расстояния в сверточном коде тестированию подлежат только те пути, которые отклоняются от нулевого в начале решетчатой диаграммы и после первого слияния с нулевым путем более от него не ответвляются. В теории свсрточных кодов минимальный вес такого пути традиционно называется свободным расстоянием. Обозначив его как т(у, можно видеть, к примеру, что среди всех путей с единственным отклонением от нулевого на рис. 9.6, кодовое слово 11101100 ., кодирующее битовый поток 100..., имеет наименьший вес, так что ду = 5.
Безусловно, свободное расстояние ду гарантирует исправление любых ]-1й — ] символьных ошибок (см. утверждение 9.2), однако И вЂ” 1 обычно исправляются и многие конфигурации большего числа ошибок. Существует лишь несколько примеров эффективных алгебраических правил сверточного кодирования. В основном же известные сверточные коды с хорошей корректирующей способностью были найдены с помощью компьютерного поиска ]31, ЗЗ, 93].
Нулевой путь Первое слияние Второе слияние Первое ответвление Второе ответвление Рис. В.У. Ответвления и слияния путей Вследствие рекуррентной природы алгоритмов кодирования нахождение всех возможных весов слов (весового спектра) произвольного сверточного кода оказывается не столь аналитически неподъемным, как в случае многих линейных блоковых кодов. В частности, непосредственно по решетке (или эквивалентной ей диаграмме состояний) можно построить систему линейных уравнений, решение которой приводит к точному выражению для весового спектра [2, 7, 93]. Выигрыш от кодирования, показывающий, во сколько раз можно снизить энергию сигнала на бит данных (или мощность сигнала) за счет 0.8.
С р . д 373)) кодирования нри фиксированной вероятности ошибки, является универсальным критерием эффективности того или иного кода. Это понятие применительно к кодированию сообщений ортогональными сигналами обсуждалось в 3 2.6, где отмечалось, что асимптотический выигрыш от кодирования в случае АБГШ есть выигрыш в евклидовом расстоянии. При БФМ передаче любое различие символов двух сигналов прибавляет к квадрату евклидова расстояния величину 4Е„где Е, — энергия символа.
В сверточном коде присутствует пара слов с ду несовпадающими символами и нет пары с меньшим различием (расстоянием Хэмминга). Следовательно, минимум квадрата евклидова расстояния между словами сверточного кода, передаваемыми с помощью БФМ а';„„= 4дуЕ,. Тот же параметр в случае некодированной передачи (см. 3 2.6) с~~;„„= 4.Ем что дает энергетический выигрьпп от кодирования сверточным кодом, дым,сс дуЕв Са= и = =дуЕс1 аавп,в где г1„как и ранее, скорость кода в битах на символ. Для кода примера 9. 5 В, = 1/2, ду = 5, так что С = 2,5 или около 4 дБ.
Напомним еще раз, что оценка С„, полученная таким образом, справедлива для АБГШ (не ДСК!) канала, иначе говоря, для случая мягкого декодирования. Жесткое декодирование снижает этот показатель на 2 — 3 дБ в зависимости от параметров кода и отношения сигнал — шум на символ [31, ЗЗ]. 9.3.3. Алгоритм декодирования Витерби Как уже сказано, одной из главных причин широкой популярности сверточных кодов является существование вычислительно-экономного алгоритма их декодирования.
Начнем с констатации следующего факта. утверждение 9.5. Жесткое МП декодирование бинарного кода с исправлением ошибок эквивалентно правилу минимума расстояния Хэмминга: дн(й,у) = п1шдн(п,у) => й объявляется принятым словом. (9.9) иеп Как легко видеть, это правило весьма похоже на (2.3) с единственной поправкой: в случае ДСК роль евклидова расстояния, адекватного для АБГШ канала, переходит к расстоянию Хэмминга. Для доказательства (9.9) достаточно заметить, что равенство (9.1), переписанное как ал(и,у) Р(у!и) ан(а,У)(1 р)п — Лн(а,У) (1 )и 1 — р~ дает переходную вероятность ДСК, т. е.
вероятность трансформации посланного кодового вектора и длины и в двоичное наблюдение у на вы- ~~( 374 Глава Р. Канальное кодирование в широкополосных системах ходе ДСК. Поскольку вероятность ошибки на символ в ДСК р ( 0,5, переходная вероятность Р(у~п) убывает с расстоянием Хэмминга между наблюдением у на выходе ДСК и кодовым вектором и.
Тем самым МП оценкой и принятого кодового слова является слово, ближайшее к у по Хэмминг у. Прямая реализация правила (9.9) для произвольного кода означала бы сравнение М расстояний Хэмминга от наблюдения у до всех кодовых слов. Так как чаще всего М весьма велико, подобный вариант декодирования может оказаться нереалистичным. В противовес этому благодаря специфической структуре сверточных кодов их МП декодирование не связано с чрезмерными вычислительными затратами, по крайней мере, при умеренных длинах кодового ограничения. Процедура декодирования Витерби реализует правило МП как рекуррентный или пошаговый поиск пути на решетчатой диаграмме, ближайшего к двоичному наблюдению у.
Каждый новый шаг декодирования на шнается с приема очередной группы из п символов наблюдения. На 1-м шаге декодер вычисляет расстояния между п пришедшими символами наблюдения и каждым ребром решетчатой диаграммы и прибавляет их к расстояниям от у всех путей, рассчитанным за 1 — 1 предшествующих шагов. Пошаговый пересчет расстояний с прибытием новых символов наблюдения, разумеется, осуществим для любых кодов, однако именно рекуррентная природа сверточных кодов позволяет выполнять эти рутинные вычисления весьма экономно из-за возможности моментальной отбраковки многих путей на каждом шаге. Рассмотрим все пути, проходящие иу через фиксированный узел А на 1-м шаге, как показано на рис. 9.8. Продолжение любого пути после 1'-го шага не зависит от маршрута прибытия в А, так что разные пути, проходящие через А, могут с ' ' иметь общее продолжение.
Это, однако, Шаги: /-1 1 еь1 означает, что из всех путей, исходящих из А и имеющих общее продолжение, тот, который имел минимальное расстоРм . 9.8. пУхи, ироколшлие чеРез яние от у вплоть до 1-го шага, останется узел А на им шаге ближаишим к у навсегда, поскольку общее продолжение внесет равный вклад во все расстояния. Нужно ли тогда продолжать контроль расстояний для остальных, если и так ясно, что у них нет шансов оказаться в итоге ближайшими к наблюдению? Вместо этого разумно отбросить их, удержав только путь, прибывающий в узел А с минимальным расстоянием У.З.С р д Зф от наблюдения.
Последний называется емжиешим путем, и на время целесообразно полагать его единственным для каждого узла решетчатой диаграммы на 1-м шаге (см. комментарий ниже). Текущее, т.е. вычисленное по всем символам наблюдения вплоть до 1-го шага, расстояние выжившего пути узла А от наблюдения у называется метрикой узла А. Вспомним теперь, что в любой узел входят лишь два ребра. Рис. 9.8 иллюстрирует зто на примере некоторого узла А. Два ребра, входящие в него, исходят из узлов В, С предшествующего шага и, следовательно, продолжают выжившие пути узлов В и С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
