Общие принципы построения Gk,n(x) и Hl,n(x) циклических кодов и их взаимосвязь

↑

⇐ ПредыдущаяСтр 4 из 4

Так как порождающая G_k,n(x) и проверочная H_l,n(x) матрицы представляют собой сокращенную запись одного и того же ЦК, то между ними существует или имеется следующая взаимосвязь [1-4]:

1) задание одной из матриц позволяет определить основные параметры ЦК, а именно (n, k, d₀).

2) задание одной из матриц обеспечивает возможность построения другой;

3) произведение G(x) · H^T(x) и G^T(x) · H(x)=0.

Далее кратко рассмотрим принципы построения G(x) и H(x) ЦК.

А) Способы построения G_k,n(x):

- формирование G_k,n(x) по правилу – вес проверочной части каждой строки матрицы должен быть ≥d₀ – 1 и порождающая матрица должна состоять из двух подматриц: единичной и проверочной.

                                 G_k,n(x) = ;                          (1.8)

- приписывание к строкам единичной подматрицы остатков отделения xⁿ/P(x), т.е.

                     G_k,n(x)= .              (1.9)

Порождающая матрица получается канонического типа и практически данный способ построения G(x) является модификацией способа, рассмотренного выше:

- при использовании порождающего полинома P(x), применяется следующее правило:

а) переводим порождающий полином P(x) из формы записи полинома в двоичную форму записи,

б) записываем порождающий полином в двоичной форме в качестве первой строки G(x) и дополняем ее справа (слева) нулевыми символами до получения «n» столбцов G(x);

в) выполняем (k-1) циклический сдвиг кодовых символов первой строки влево или вправо.

Записываем P(x) в качестве первой строки порожденной матрицы, дополняем нулями до n=10 и выполняем (k-1) = (5-1) = 4 циклических сдвига кодовых символов первой строки. В результате получаем следующую порождающую матрицу:

Порождающую матрицу можно построить по следующей методике:

1) переводим (можно не переводить) порождающий полином P(x) из формы многочлена в двоичную форму записи, т.е. P(x) = x⁵+x⁴+x²+1→110101;

2) умножаем P(x)= 110101 на одночлен вида x^k-1, т.е. на 1000; в результате получаем строку G(x); а далее используем циклический сдвиг (k-1) раз полученной строки G(x).

Процесс кодирования информации или процесс формирования КП записывается так:

F_i(x) = Q(x) · G_k,n(x) ,

где Q(x) – передаваемый информационный блок, содержащий k-1 двоичных символов.

Б) Способы построения проверочной матрицы H_e,n(x) ЦК:

- с использованием заданной порождающей матрицы ЦК для построения проверочной матрицы H_e,n(x) по заданной порождающей матрице G_k,n(x) записать в виде первого столбца H_e,n(x), проверочную часть второй строки G_k,n(x) записать в виде второго столбца H_e,n(x) и так далее до последней строки G_k,n(x), а далее в проверочной матрице H_e,n(x) дописать единичную матрицу;

- с использованием заданных параметров ЦК, а именно, n и h(x). Для этого необходимо проверочный полином h(x) перевести в двоичную форму записи, а записать его в виде первой строки H_e,n(x) и дописать «k» нулевым символом. Далее выполнить l-1 циклических сдвигов данной строки; в результате будет построена проверочная матрица неканонического вида. Для приведения ее к каноническому виду необходимо выполнить ряд операций над строками и столбцами.

- ЦК, корректирующие модульные ошибки, имеют более сложные правила построения проверочных матриц, так как содержат ряд единичных подматриц I(x) рангом (t_n · t_n) и ряд (или более) проверочных подматриц, h_i рангом или размерностью (l-t_n) · t_n и столбцы h_j,l каждый из которых представляют собой двоичный код номера i; т.е.

                                     i = h_j,I · 2^j-1,                            (1.10)

где Ɛ = 1- t_n.

В общем виде проверочную матрицу данного кода можно записать или представить так:

                                 H(x) =  .                        (1.11)

Из ЦК в настоящее время широкое применение в телекоммуникационных системах получили коды Рида-Маллера, достоинствами которых являются: возможность использования различных алгоритмов декодирования (алгебраических и вероятностных) и т.д.

2 ОБЩИЕ СВЕДЕНИЯ О ЦИКЛИЧЕСКИХ КОДАХ РИДА-МАЛЛЕРА

В соответствии с [1-4] коды Рида-Маллера (КРМ) относятся к групповым несистематическим (неразделимым) кодам с простым способом задания. Декодирование КРМ чаще всего реализуется мажоритарным и синдромным способоми. Однако возможно декодирование кодов по максимуму правдоподобия. В общем КРМ эквивалентны циклическим кодам с добавлением общей проверки на четность. Достоинствами данных кодов являются простота их задания и минимальная сложность реализации алгоритмов кодирования и декодирования. Недостатком КРМ является слабая (низкая) корректирующая способность; данные коды чаще всего применяются для коррекции ошибок кратностью не более трех двоичных символов.

Сущность КРМ и, следовательно, их определение состоит в следующем [1-4]: пусть F_o(x) есть кодовая последовательность (кодовый вектор), состоящая из одних логических единиц (1), а кодовые последовательности F₁(x), F₂(x),…,F_m(x) образуют строки матрицы, столбцами которой являются все двоичные наборы длиной m двоичных символов; m может иметь разное значение (величину),т.е. величина m≥2. В этом случае для любых целых чисел m и E (E<m) можно построить помехоустойчивый код длины n=2^m двоичных символов, который называется кодом Рида-Маллера E-го порядка. В реальных системах связи КРМ с порядком E>3 практически не используются.

КРМ E-го порядка содержит в качестве базиса (основы) кодовые последовательности F₀(x), F₁(x),…,F_m(x) и все поэлементные (полуразрядные) произведения E или меньшего числа этих последовательностей. В данном определении поэлементные произведения кодовых последовательностей (условно: a=(a₁a₂…a_n) и b=(b₁b₂…b_n)) задается формулой a·b=(a₁·b₁,a₂·b₂,…,a_n·b_n).

КРМ E-го порядка дуален (двойственен) помехоустойчивому коду (m--E-1) порядка.

КРМ E-го порядка длины n=2^m двоичных символов задается (строится) порождающей матрицей вида [1-4]:

                                       G(x) = ,                                (2.1)

где G₀(x) – кодовый вектор (кодовая последовательность) длиной n=2^m двоичных символов, состоящих из одних ″1″;

G₁(x) – матрица размерности (m·2^m), содержащая в качестве столбцов все двоичные m-последовательности;

G_E (x) – матрица, строки которой получаются из строк матрицы G₁(x) как все возможные произведения E строк из матрицы G₁(x); для определенности обычно принимают, что первый столбец в G₁(x) состоит из одних ″0″, а последний из одних ″1″.

Коды Рида-Маллера имеют простые выражения для определения основных параметров данных кодов, а именно n=2^m двоичных символов – длина кодовой последовательности: k =  двоичных символов – длина или количество информационных символов;

d₀=2^m-E – минимальное кодовое расстояние;

d =  – кодовое расстояние.

Кроме того, возможно определение параметров КРМ по следующей методике: длина кодовой последовательности определяется рангом порождающей, т.е. n=2^m.

Параметры k и l=n-k КРМ E-го порядка можно определить используя следующие выражения:

          k = 1+  +  + … + , двоичных символов   (2.2)

l = n – r = 1+  +  + … + , двоичных символов (2.3)

Далее установим связь КРМ с другими линейными блоковыми кодами. КРМ нулевого порядка (E-0) является (n, k)=(n, 1) – кодом и соответствует коду с повторением и использует мажоритарный алгоритм декодирования. Минимальное кодовое расстояние такого кода равно d₀=2^m, а так как в этом случае m=2, то d₀=2²=4.

КРМ первого порядка (E=1) тесно связаны с кодами максимальной длины, которые, в свою очередь, дуальны кодам Хэмминга. Если начать построение помехоустойчивого кода с построения кода максимальной длины и расширять его путем добавления общей проверки на четность, то получим ортогональный код. Данный код имеет длину n=2^m двоичных символов и вес каждой ненулевой кодовой последовательности равен w_i= d = 2^m-1. Следовательно, любые две кодовые последовательности совпадают в 2^m-1 позициях и различаются в остальных 2^m+1 позициях. Используя этот код с противоположными сигналами, получим множество из 2^m ортогональных сигналов для 2^m кодовых последовательностей; отсюда и название ортогональных сигналов.

КРМ первого порядка получаются непосредственно из ортогонального кода добавлением кодовой последовательности состоящей из ″1″. Если же рассматривать передаваемые сигналы, то эта процедура эквивалентна добавлению дополнительных сигналов к первоначальному множеству ортогональных сигналов. По этой причине полученный код называют биортогональным кодом [3,4].

Рассмотрим принцип построения КРМ с использованием методики построения КРМ, приведенной в [1] и следующих исходных данных кода: m=4 и E=3. Следовательно, необходимо определить все параметры КРМ третьего порядка. Далее определяем параметры кода n, k и d₀:

n=2^m=2⁴=16, двоичных символов – длина кодовых последовательностей;

k = 1+  +  +  = 1 + C¹_m + C²_m + C³_m = 1 + 4 + 6 + 4 = 15, двоичных символов – длина информационного блока;

d₀=2^m-E=2^4-3=2.

Данный КРМ задается порождающей матрицей вида

                                       G(x) = .                                (2.4)

Строим порождающие матрицы G₀(x), G₁(x), G₂(x) и G₃(x) данного кода.

Порождающая матрица G₀(x) содержит одну строку (обозначим строку буквой a₀) логических единиц с количеством равной n=2^m=2⁴=16 двоичных символов и имеет следующий вид:

                       G₀(x) = [1111111111111111] = [a₀].               (2.5)

Порождающая матрица G₁(x) содержит m=4 строки; первая строка матрицы  =  = 8 логических нулей (0) и логических единиц (1). Последующие строки данной матрицы строятся аналогичным способом, т.е. делением последовательностей 1 и 0 строк на два. Порождающая матрица G₁(x) имеет следующее построение:

                    G₁(x) =  = .             (2.6)

Из данной матрицы видно, что столбцы матрицы представляют собой последовательность чисел, записанных в двоичной системе счисления; младшие разряды (символы) внизу. Следовательно, столбцы G₁(x) можно рассматривать как последовательности состояний двоичного суммирующего счетчика, что условно можно представить так:

                                         G(x) = ,                                  (2.7)

где 1 – последовательность из одних 1,

S_δ1 – последовательность состояний последнего (старшего) разряда счетчика,

S_δm – последовательность состояний первого (младшего) разряда счетчика.

Примечание: перестановка столбцов и строк порождающей матрицы приводит к эквивалентным кодам. Строки в порождающих матрицах линейно независимы. Поскольку матрица G₁(x) имеет четыре строки, то матрица G2(x) будет иметь  =  = 6 строк, которые получаются путем покомпонентного (поэлементного) перемножения строк матрицы G₁(x) [1-4]:

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?