Задание систематических сверточных кодов

Систематические СК задаются:

• 1. с помощью порождающей матрицы, G;
• 2. с помощью проверочной матрицы, Н;
• 3. с помощью разностных треугольников;
• 4. с использованием совершенных разностных множеств.

Порождающая матрица систематического СК имеет более сложное построение, чем группового кода. Это определяется из-за полубесконечной структуры порождающей матрицы СК, имеющей вид:

(1.9).

где «0» — области матрицы, состоящие полностью из нулевых двоичных символов,.

m — количество порождающих матриц вида где qi, j — коэффициенты равны либо 1, либо 0.

(1.10).

Систематический ССК задается следующей порождающей матрицей (1.11) или (1,12).

(1.11).

или.

(1.12).

Проверочная матрица Н СК, как и порождающая матрица, является полубесконечной:

где n0=k0+l, l0=n0-k0, N=m+l,.

Порождающая и проверочная матрицы СК, как и у линейных кодов, связаны выражением:

G· HT= G· HT=0 .

Для систематического ССК с алгоритмом порогового декодирования проверочная матрица H задается следующим образом:

(1.14).

Из данной проверочной матрицы следует, что для ССК с R=k0/n0=(n0−1)/n0 проверочная матрица Н содержит n0-k0 строк и k0 столбцов проверочных треугольников. Для ССК с R=k0/n0=1/n0, n0=2,3… проверочная матрица Н содержит k0=1, т. е. один столбец и (n0−1) строку проверочных треугольников.

Основную информацию о самоортогональных сверточных кодах ССК несут коэффициенты левого столбца и нижней строки проверочного треугольника. Например, пусть задан проверочный треугольник следующей структуры:

(1.15).

По данному проверочному треугольнику можно определить параметры ССК с алгоритмом ПД:

• 1. Поскольку задан один проверочный треугольник, то k0=1, n0=k0+l=2, R= k0/n0 =1/n0;
• 2. Так как k0=1, то ССК задается одним порождающим полиномом, определяемым коэффициентами левого столбца и нижней строки проверочного треугольника.
• 3. Количество ненулевых членов порождающего полинома определяет число проверочных уравнений Ji, J=4. Следовательно, ССК может исправлять tисп=J/2=4/2=2 ошибки и обнаруживать tобн=d0−1=(J+1)-1=4 ошибки;
• 4. Строки проверочного треугольника, которые начинаются с ненулевых двоичных символов, формируют проверочные уравнения, размеры данных проверок и номера позиций информационных и проверочных символов, участвующих в формировании проверочных уравнений. Для данного примера имеем:

S0=i0+ep.0,.

S2=i0+i2+ep.2, (1.16).

S6=i0+i4+i6+ep.6,.

S7=i0+i1+i5+i7+ep.7.

Размеры проверок в проверочном треугольнике обозначены цифрами перед стрелками и определяются количеством ненулевых символов в строке;

5. Длина кодового ограничения nA и эффективная длина кодового ограничения ne СК равны соответственно:

nA =(m+1)*n0=(7+1)*2=16 двоичных символов.

ne =½*J2+½*J+1=½*42+½*4+1=11 двоичных символов.

Так как проверочный треугольник позволяет определить практически все параметры ССК, то разработано много способов их построения. Однако на практике наибольшее применение получили два способа их построения, а именно с помощью нахождения разностных треугольников и совершенных разностных множеств. Сущность их состоит в следующем.

Разностный треугольник представляет собой совокупность целых, действительных и неповторяющихся чисел, записанных в форме треугольника. Для ССК с R = k0/n0 количество разностных треугольников равно числу k0. Для всех разностных треугольников общим числом является «0», который не указывается в совокупности чисел однако учитывается при выборе степеней ненулевых членов порождающих полиномов. Очевидно, что число «0» определяет нулевую степень первого ненулевого члена порождающих полиномов. Степени ненулевых членов порождающих полиномов по заданным или построенным разностным треугольникам можно найти путем выбора чисел: левого крайнего столбца разностного треугольника, считывая их сверху вниз и дополняя числом «0» или, верхней строки разностного треугольника в следующей последовательности: первое число — показатель степени второго ненулевого члена порождающего полинома, сумма первого и второго числа первой строки разностного треугольника определяют показатель степени третьего ненулевого члена порождающего полинома и т. д.

Рассмотрим пример определения параметров ССК с алгоритмом порогового декодирования при следующем разностном треугольнике:

• 1. Так как задан один разностный треугольник, то k0=1, n0=k0+1=2, R=k0/n0=½ ИСК имеет один порождающий полином.
• 2. Выписывая числа левого крайнего столбца разностного треугольника, определяем показатели степеней порождающего полинома: (0,2,6,7). Следовательно, порождающий полином ССК имеет вид: g1(x)=1+x2+x6+x7. При втором способе: 0; 2+4=6; 2+4+1=7. Как правило, в литературе разностные треугольники табулированы и представлены, например, в виде совокупности цифр ((2,4,1), (3,5,2)). Это означает, что ССК имеет соответственно параметры: k0=2, n0=k0+1=3, R=k0/n0=2/3 и g1(x)=1+x2+x6+x7 и g2(x)=1+x3+x8+x10.

Разностный треугольник может быть построен, если задан проверочный треугольник и наоборот. Например, использую проверочный треугольник (1.15) можно построить разностный треугольник следующим образом.

Числа крайнего левого столбца разностного треугольника определяются как результат операции вычитания порядковых номеров строк проверочного треугольника, которые начинаются с 1. Для первого столбца получаем следующие числа: 3−1=2 (3 — номер позиции третьей строки, 1 — помер позиции первой строки); 7−1=6 и 8−1=7. Для получения чисел второго столбца за вычитаемое берем номер позиции третьей строки: 7−3=4, 8−3=5. Для получения чисел третьего столбца за вычитаемое берем номер позиции седьмой строки: 8−7=1.

Как отмечалось выше, числа, входящие в разностные треугольники, должны быть целыми, действительными и неповторяющимися. Для получения совокупности таких чисел известно достаточно много способов их нахождений, но наиболее эффективным является способ основанный на теории совершенных разностных множеств.

Совершенное разностное множество — это совокупность целых, действительных и неповторяющихся чисел 1, 2,…, причем 1<2< и разности этих чисел i — j, j<1, полученных по некоторому mod, (2) также образуют, совокупность целых, действительных и неповторяющихся чисел.

Данную совокупность полученных разностных чисел можно использовать в качестве исходных чисел для формирования разностных треугольников и выбора соответствующих порождающих полиномов ССК.

При выборе чисел для построения разностных треугольников необходимо выбирать числа с наименьшим их значением по номиналу, т.к. максимальное значение числа в построенных разностных треугольниках определяет максимальную степень m порождающих полиномов ССК.

Рассмотрим построение ССК с алгоритмом ПД с использованием совершенных разностных множеств на примере.

Пусть, например, имеется совокупность в=3+1 целых, действительных и неповторяющихся чисел (в=0, 30, 31, 32) и эта совокупность образует в2+в=32+3=12 разностей по модулю в2+в+1=32+3+1=13, которые равны следующим числам:

Полученную совокупность разностных чисел можно разбить на следующие подмножества:

Каждый из столбцов данного множества можно использовать для построения разностного треугольника. Следовательно, можно построить k0=4 разностных треугольника, и четыре ССК с R=k0/n0=½;2/3;¾;4/5 (J=4), а также можно построить при k0=3 три кода со скоростями: R=½;2/3;¾ (J=5).