Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 76
Текст из файла (страница 76)
Сверточные коды были впервые открыты Л. Финком и П. Элайесом, вскоре Возенкрафт разработал метод последовательного декодирования сверточного кода [13]. В 1967 г. появился алгоритм Витерби для оптимального декодирования сверточных кодов 161. Структура двоичного сверточного кода со скоростью Я= — показана на рис. 7.9. Свер- и точный кодер состоит нз сдвигового регистра, включающего и ячеек памяти, блока сумматоров по пюд2, входы каждого нз которых связаны с некоторыми выходами ячеек памяти регистра, опрс |немыми козффициентами Ь,-.
=(О, 1) . Выходы сумматоров считываются при помощи коммутатора Х и подаются в канал связи. Таким образом, на каждом такте в регистр сдвига последовательно поступает очередной блок из /с информационных символов источника н одновременно он освобождается от /с символов, содержащихся в его крайних правых ячейках памяти. На этом же такте формируются и выходных символов, которые последовательно считываются в канал связи.
Таким образом, если ги — скорость поступления символов в кодер, то для отсутствия растущих задержек во времени скорость передачи символов по каналу и связи должна быль не меньше чем кг — — — к„, откуда видно, что отношение й/и действительно Ь, . Ь, 1 2 / к определяет скорость сверточного кода. Величина ч (или длина регистра) обычно называется длиной кодового ограиичеиия.'> Ьгвк (Возможно и другое, более общее представление сверточного кодера в виде схемы с /с регистрами сдвига с кодовыми ограничениями ч; (/= 1, 2, ..., /г.) На вход К Выход каждого из ннх подается один информационный символ за время одного такта 1131.) На рис.
7.10 показан частный случай Рис.7.9. Структура сверточного кодера со скоростью Ь/и сверточного кода со скоростью 1/2 и В В некоторых работах длина кодового ограничения определяется числом ячеек сдвнгого регистра минус 1. длиной кодового ограничения г = 3. При нулевой информационной последовательности выходная кодовая последовательность также равна нулю.
В табл. 7.5 приведен пример формирования выходной последовательности для кодера, показанного на рис. 7.10. Выходная последовательность кодера может быть представлена как цифровая свертка входной информационной последовательности и импульсного отклика кодера (отсюда название кодов — сверточные). Таблица 7;5 Вход 0 0 1 0 0 0 1 1 0 0 О Выход 11 10 11 00 11 01 01 11 00 Сверточный код характеризуется следующими параметрами: относительной скоростью кода й = к/и и избьипочностью а=1 — й, где /с и и — число информационных и кодовых символов, соответствующих одному такту работы кодера (для кодера рис.
7.10 й=1/2); длиной кодового ограничения ч (длина регистра кодера); порождающим полинином кода, коэффициентъ1 которых описывают связи сумматоров с ячейками регистра кодера (для верхнего сумматора К('1 =1+О+В', для нижнего сумматора й1') =1ьО'). Полиномы обычно записывают сокращенно, обозначая каждые три отвода (двоичных коэффициента) как одну восьмеричную цифру (код рис. 7.10 обозначается (7,5)). Кроме перечисленных выше параметров сверточный код характеризуется свободным расстоянием Н„, под которым понимают расстояние по Хеммингу между двумя полубесконечными кодовыми последовательностями.
Если две одинаковые информационные последовательности кодировать с помощью кодера, изображенного на рис. 7.10, то соответствующие им кодовые последовательности будут совпадать друг с другом. Если в некоторый момент в одной информационной последовательности окажется символ О, а в другой 1, то с этого момента кодовые последовательности будут отличаться друг от друга независимо от дальнейшего содержания информационных последовательностей. Минимальное расстояние по Хеммингу между любыми двумя полубесконечными кодовыми последовательностями с того момента, как соответствующие им информационные последовательности начинают различаться, называется свободным расстоянием сверточного кода И„, Свободное расстояние Н, характеризует помехозащнтные свойства сверточного кода (аналогично тому как минимальное расстояние И характеризует помехозащитные свойства блочных кодов).
Оно показывает, какое наименьшее число ошибок должно произойти в канале для того, чтобы одна кодовая последовательность перешла в другую и ошибки не были обнаружены. Для кода, приведенного в нашем примере, свободное расстояние Ы„=5. Поиск хороших сверточных кодов (с наибольшим а|„при заданных Я и 1) обычно осуществляется методом перебора всех порождающих полиномов на ЭВМ.
Таблицы хороших кодов приведены в 113). Сверточные коды являются частным случаем (линейной реализацией) так называемых решетчатых кодов. Можно также полагать, что решетка является просто другим (иногда более удобным) способом представления и обычных сверточных кодов. Решеткой называется ориентированный граф с периодически повторяющейся структурой "ячеек". Каждая ячейка содержит колонки из одинакового числа вер+ шин (узлов), соединенных ребрами.
Меж- ду процедурой кодирования сверточным Рис.7.10. Саьрточный кодер со скоростью Я=1/2 КОДОМ И рЕШЕтКОй ИМЕЕтСя ВЗаИМНО ОДНО- значное соответствие, которое задается следующими правилами [61: 298 — каждая вершина (узел) соответствует внутреннему состоянию кодера; — ребро, исходящее из каждой вершины, соответствует одному из возможных символов источника (для двоичного источника из каждой вершины выходит два ребра — верхнее для 0 и нижнее для 1); — над каждым ребром отмечены значения символов, передаваемых в канал связи, если кодер находился в состоянии, соответствующем данной вершине и источник выдал символ, соответствующий данному ребру; — последовательность ребер (путь на решетке) — это последовательность символов, выданных источником.
Так, если под состоянием кодера понимать содержимое двух последних ячеек 00 памяти (2, 3) в регистре сдвига на и и рис. 7.10, то решетка с четырьмя состояниями, соответствующая данному кодеру, ] ° будет иметь вид, показанный на рис. 7.11 ш (решетка может отражать и нелинейный кодер, когда выходные символы не являются линейной функцией входных). ' о~ 0 0 Так же как и блоковые коды, сверточные допускают представление в виде полу- и бесконечных порождающих или прове- ® ® ю о рочных матриц, однако представление в виде решетки оказывается более удобным ие...
еп' как деРа,п казани гонарн.п' для описания алгоритмов декодирования. Сверточные коды имеют следующие основные преимущества перед блоковыми при их использовании для исправления ошибок. 1. Они не требуют синхронизации по блокам, а лишь синхронизации коммута- торов К (на передаче и приеме). 2. Если кодовое ограничение ч выбр ..ь равным длине блокового кода, то исправляющая способность сверточного кода оказывается больше, чем исправляющая способность такого блокового кода (при наилучшем выборе обоих кодов). 3.
Алгоритм декодирования сверточных кодов допускает простое обобщение на случай мягкого декодирования, что обеспечивает дополнительный энергетический выигрыш. 4. Сверточные коды допускают простое объединение кодирования и модуляции (так называемая кодированная модуляция или сигнально-кодовые конструкции), что особенно важно при построении энергетически эффективных систем связи для каналов с ограниченной полосой частот. Для оптимального декодирования сверточных кодов в каналах без памяти часто используется рекуррентный алгоритм декодирования Витврби (АВ).
Рассмотрим его на примере мягкого декодирования в постоянном канале с аддитивным белым гауссовским шумом. Поскольку принимаемый сигнал на к-м тактовом интервале нам известен, то можно вычислить евклидовы (или гильбертовы) расстояния между принятым сигналом и всеми возможными сигналами: т Л „, = ~ (г„(~) — в~'~(~)) Й , г' = О, 1, ..., и — 1, 1с = О, 1, ..., о 299 ГдЕ За01(Г) — ОжИдаЕМЫй В МЕСТЕ ПрИЕМа СИГНаЛ, СООтВЕтСтВуЮщИй 1'-Му СИМВОЛУ (для двоичных сигналов 1 = 0,1); а,(г) — сигнал, принятый на 7с-м тактовом интервале. Теперь можно каждому ребру решетки последовательно приписывать на 7с-х ее звеньях значения Л„,.
Оптимальное по правилу максимального правдоподобия декодирование будет тогда соответствовать выбору такого пуги на решетке (т.е. последовательности непрерывно продолжающихся ребер), что ~г Л„окгажется минимальной. Казалось бы, для решетки длины и (т.е. для последовательности переданных символов длиной и) нужно для этого перебрать 2" возможных вариантов, но в действительности это не так. Ключевой момент АВ состоит в том, что для каждой вершин на данном шаге (такте) имеется множество метрик, соответствующих соединенным с ней ребрами вершинам на предыдущем шаге можно оставить только одно ребро, которое минимизирует сумму метрик на всех предыдущих шагах. Проще всего можно пояснить данный алгоритм на простом примере. Пусть решетка имеет всего два состояния и структуру, показанную на рис. 7.12, где над ребрами подписаны соответствующие метрики.
Полагаем, что первый информационный символ О. Тогда пути, оставленные (" выжившие" ) на различных шагах, показаны на рис. 7.13 Видно, что на 4-м шаге получаем выживший путь, который в условиях наших обозначений (ориентацня ребра вниз— 1, вверх — 0) соответствует информационной последовательности 0100. Сложность АВ определяется на каждом шаге числом сравнений метрик, соединяющих все вершины, и оно ограничено величиной М', где М вЂ” число состояний решетки. Поскольку из схемы сверточного кодера получаем, что М=2" ', где ь — число ячеек памяти регистра сдвига кодера, то видим, что сложность АВ экспоненциально зависит от длины кодовых ограничений, но линейно зависит от длины передаваемой последовательности. Поэтому длина кодовых ограничений ч при использовании АВ в качестве алгоритма декодирования обычно выбирается не более 10...15, что, впрочем, оказывается вполне достаточным для получения большого энергетического выигрыша.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
