Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 42

В отличие от блоковых кодов,которые описываются единственным порождающимполиномом,свёрточный код требует для своего описания нескольких порождающих полиномов - в общем случае k0n0 полиномов.Пусть

g ij (X),i = 1,...,k0 , j = 1,...,n0 - множество порождающих многочленов.Они могут быть объединены в матрицу размера k0 / n0,называемую ПОРОЖДАЮЩЕЙ МАТРИЦЕЙ ИЗ ПОЛИНОМОВ:G(X) = [g ij (X)].

При k0 большем единицы,некоторые порождающие полиномы могут равняться нулю.

Например,порождающие матрицы из полиномов кодеров для свёрточного

(12,6) и свёрточного (6,3) кодов(см.рис.)записываются в виде

G(X) = [1 X^5 + X^3 + 1] и

G(X) = [X^2 + X + 1  X^2 + 1].

ПРОВЕРОЧНАЯ МАТРИЦА H(X) ИЗ ПОЛИНОМОВ является [(n0 - k0)*n0] матрицей,элементами которой являются полиномы и которая удовлетворяет условию G(X) H^T(X) = 0.

СИСТЕМАТИЧЕСКИЙ КОДЕР для свёрточного кода имеет ПОРОЖДАЮЩУЮ МАТРИЦУ ИЗ ПОЛИНОМОВ ВИДА

G(X) = [I : P(X)], где I - единичная матрица размера k0 / k0,а P(X) - матрица полиномов размера k0 / (n0 - k0)./* Для систематических свёрточных кодов проверочную матрицу из полиномов можно сразу записать в виде

H(X) = [ - P^T(X) : I ], где I - единичная матрица размера (n0 - k0 ) / (n0 - k0). */

Н Е К О Т О Р Ы Е   П Р О С Т Ы Е   С В Ё Р Т О Ч Н Ы Е   К О Д Ы.

При рассмотрении свёрточных кодов мы ограничимся только СИСТЕМАТИЧЕСКИМИ свёрточными кодами.Кроме того,известно несколько алгоритмов декодирования свёрточных кодов.Более подробно мы будем рассматривать только АЛГОРИТМ СИНДРОМНОГО ДЕКОДИРОВАНИЯ.

Известно всего несколько конструктивных классов свёрточных кодов.В

настоящее время не известен ни один такой класс с алгебраической структурой,сравнимой со структурой кодов БЧХ,исправляющих t ошибок;

таким образом,не существует конструктивных методов поиска свёрточных кодов с большой длиной кодового ограничения.Большинство известных и используемых в настоящее время лучших свёрточных кодов было найдено поиском на ЭВМ.

Класс двоичных свёрточных кодов,исправляющих одну ошибку и называемых КОДАМИ ВАЙНЕРА - ЭША,аналогичен классу кодов Хэмминга.

Для каждого положительного целого m существует ((m + 1)2^m,(m +

+ 1)(2^m - 1)) - код Вайнера - Эша:

n0 = 2^m,k0 = n0 - 1.

ПРОВЕРОЧНАЯ МАТРИЦА H такого кода может быть построена следующим образом.Построение такой матрицы рассмотрим на примере.

Пусть необходимо построить проверочную матрицу для свёрточного

(12,9) - кода Вайнера - Эша при n0 = 4,k0 = n0 -1 = 3.Тогда

m = log 2 n0 = 2.

Вначале строится матрица B0,которая представляет собой первые n0

столбцов матрицы H.Столбцы матрицы B0 образуют приписыванием перед всеми 2^m различными наборами длины m символа 1.Расположение наборов длины m по столбцам несущественно;лишь для задания кода в систематическом виде нужно расположить нулевой набор длины m в столбце матрицы с номером n0,который соответствует проверочному символу.

│1 1 1 1│

B0 = │1 0 1 0│.

│1 1 0 0│

Матрица H получается из матрицы B0 следующим образом.Выбирают k0

копий матрицы B0,первая копия - в неизменённом виде,вторая копия представляет собой сдвиг каждого столбца B0 на 1 символ,третья копия - сдвиг каждого столбца B0 на 2 символа (в общем случае - k0 - я копия - сдвиг каждого столбца B0 на k0 - 1 символ).Проверочная матрица будет иметь вид :

│1111          │

H = │1010 1111     │

│1100 1010 1111│

Для получения других значений скорости передачи информации по каналу эти коды,так же как блоковые,можно УКОРАЧИВАТЬ.Этого можно добиться,приравнивая первые i информационных символов нулю и исключая их из передачи.

Распределение наборов длины m по столбцам матрицы B0 проивольно.

Однако,если m-мерный вектор является двоичной записью номера столбца,в котором он расположен,то декодирование может быть несколько упрощено.Нулевой набор длины m располагаетсяв проверочном столбце с номером 2^m.Тогда первый символ синдрома будет 1,если имеется ошибка в текущем (нулевом) кадре,и 0 в противном случае;другие m символов синдрома дают номер ошибочного символа,если имеет место ошибка.