- •Санкт-Петербургский государственный технический университет
- •Способы задания кодов, классификация и характеристики кодов.
- •Задание сверточного кода решеткой.
- •Матричное описание сверточных кодов.
- •Код Вайнера-Эша
- •Коды Хэмминга (недвоичные)
- •Коды Хэмминга как цикличные коды
- •Проблематика исправления ошибок.
- •Алгоритм декодирования сверточных кодов.
- •Синдромное декодирование сверточных кодов.
- •Исправление пакетов.
- •Алгоритм декодирования Витерби.
- •Оценка характеристик декодирования по алгоритму Витерби.
Санкт-Петербургский государственный технический университет
Вечерний электрорадиотехнический факультет
Сверточные коды
Санкт-Петербург
2001
Сверточные коды
Общее название кодов – «непрерывные», синоним «древовидные» коды. Здесь нет разбиения информации на блоки, когда передача каждого блока независима от других блоков. Берутся гораздо меньшие порции длины k0 (называют их кадрами) и превращают в выходные кадры длины n0 > k0 . В отличие от блоковых кодов, реакция n0 на кадр из k0 символов зависит не только от содержания кадра, но и от содержания предшествующих m кадров. Древовидный код как бы имеет память, которой нет у блоковых кодов. Интерес к непрерывным кодам вызван следующими моментами:
проще способ программной реализации на современных микроЭВМ, микрокомпьютерах и ПК.
легче достигается возможность извлечения потенциала, имеющегося у кода для исправления ошибок, в частности, для алгоритма минимального правдоподобия имеется более простой вариант – алгоритм Витерби.
более удачно обеспечивается сопряжение источника и канала по скорости, меньше задержка.
Способы задания кодов, классификация и характеристики кодов.
Сказанное относительно определения непрерывного кода, иллюстрируется рисунком:
Сразу же напрашиваются определения некоторых характеристик кода:
- скорость кода;
- кодовая длина блока сверточного кода; Ряд авторов (Ивадаре) называют ее длиной кодового ограничения.
- информационная длина блока
- длина кодового ограничения
Ясно, что n – это длина последовательности, где сохраняется влияние одного (самого старого) кадра.
Если использовать четыре свойства (конечность/бесконечность длины кодового ограничения, постоянство/непостоянство во времени, линейность и систематичность), то различают решетчатый код, скользящий, блоковый и сверточный код.
Наиболее простой способ понять сущность задания сверточных кодов, которыми мы и будем далее заниматься и прояснить само название «сверточный», это вспомнить определение фильтра с конечным импульсным откликом (КИО-фильтров).
КИО – это схема умножения многочлена (информационного I) и задаваемого кодом (G). Каждый многочлен конечной степени. Набор многочленов максимально возможный равен k0xn0.
С каждого входа на каждый выход свой многочлен. Код тогда оказывается заданным матрицей образующих многочленов или схемой КИО-фильтров.
G(j)(i), i = 1,2,…, k0; j = 1,2,…, n0;
Выходная последовательность линейного фильтра есть свертка входной последовательности и «импульсной характеристики» фильтра. Поэтому код и называется сверточным.
Примеры.
k0=1 n0=2 R=1/2 m=2 n=2
n=6 k=3 (6,3)
несистематический
k0=2 n0=3 R=2/3 m=2
Обратите внимание, что для блоковых кодов бессмысленно брать g(x)=xi, а для сверточных это возможно и нужно.
Дадим теперь строгое определение характеристик n, k и n.
В примере 2, следовательно n=3 n=9 k=6.
Получим формальный алгоритм кодирования. Входной кадр k0 символов будем полагать поступающим параллельно (одновременно k0 бит), получаются на входе k0 подпоследовательностей информационных символов di(x), i=1,.., k0, или вектор-строка таких многочленов
Аналогично для выходного кодового слова, будет
Если передача по каналу последовательная, коэффициенты многочленов кодового слова перемежаются.
Операция кодирования, следовательно, задается компактно с помощью векторно-матричного произведения:
c(x)=d(x) G(x), т.е
Как и для блоковых кодов можно ввести проверочную матрицу многочленов H(x). Размерности [(n0-k0) n0]. Она должна удовлетворять условию G(x) HT(x)=0. Матрица H(x) также задает сверточный код.
Далее нам потребуется вектор синдромных многочленов, который дается уравнением
s(x)=V(x) HT(x) - это r-мерная вектор-строка из многочленов.
Для систематического сверточного кода
G(x) = [I : P(x)], где
I - единичная k0xk0 матрица
P(x) - матрица многочленов k0xr0
Для систематических сверточных кодов сразу же находится H(x) = [-PT(x):I], где
I - единичная r0xr0 матрица.
Чем лучше систематические сверточные кодеры? Легко на примере «читать», что передается как без помехоустойчивого кода, так и с ним. Но сверточный код систематический и несистематический неэквивалентны, дистанционные свойства могут различаться. Несистематические часто лучше.