Классификация способов построения циклических кодов

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

- «k» разрешенных КП;

- одной разрешенной КП;

- порождающий G_r,n(x) и проверочный H_e,n(x) матриц;

-порождающего P(x) и проверочного h(x) полиномов;

- произведения примитивных полиномов m_i(x), i =1,3…

Кратко рассмотрим сущность данных способов задания (построения) ЦК, так как некоторые способы построения ЦК будут рассмотрены подробно.

1. Использование «k» разрешенных КП: данный способ построения ЦК находит ограниченное применение (системы и сети телесигнализации, а также в автоматических системах управления(САУ)) в виде низкой корректировочной способности данных кодов и достаточно высокой сложности реализации декодеров. При данном способе построения ЦК чаще всего используется (задаются) ЦК с небольшой длиной КП; n ≈ 7÷16 двоичных символов.

Сущность способа построения ЦК состоит в выборе либо одной разрешенной КП и выполнения ≤(k-1)-го циклического сдвига кодовых символов разрешенной КП, либо в псевдослучайном выборе «k» разрешенной КП с максимальным весом КП.

2. Использование одной разрешенной КП: данный способ построения ЦК состоит в модификации первого способа и сущность его состоит в следующем. Записывается разрешения КП и затем осуществляется необходимое количество циклических сдвигов кодовых символов КП; количество ЦК не должно превышать (k-1) сдвиг. Если требуется получить все 2^k, разрешенных КП, то производится посимвольное (суммирование по модулю два)  кодовых символов 1⊕2 строки, 1⊕3 строки, и т.д. до получения требуемого количества разрешенных КП.

Достоинством способа является – простота алгоритма. Недостатком способа – высокая трудоемкость построения кода и реализация кодека.

3. Использование порождающей матрицы G_r,n(x): данный способ построения ЦК, находит очень широкое применение.

При использовании G(x) могут быть построены (сформулированы) как систематические так и несистематические ЦК. Тип формируемого ЦК зависит от типа используемой G(x); а именно, если используется неканоническая G(x), то формируется несистематический ЦК, а если используется канонический или приведенно-ступеньчитая G(x), то формируется систематический ЦК. Порядок (правило) формирования КП данных кодов с использованием G(x) можно записать так:

 

F_i(x) = Q(x) · G′_k,n(x)=Q(x) · [I(x) ⋮ П(x)] – систематический ЦК;

 

F_i(x) = Q(x) · G _k,n(x) – несистематический ЦК,                          (1.4)

 

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

4. Проверочная матрица H_e,n(x), как отмечалось выше, используется как для формирования КП (для построения ЦК с заданными параметрами, т.е. (n;k;d_o)). Нулевые символы строк H(x) определяют позиции информационных символов, участвующих в формировании проверочных символов КП. При использовании H(x) чаще всего формируется систематический ЦК.

При использовании транспортированной H^T(x) чаще всего определяется или выбирается соответствующий алгоритм декодирования и чаще всего синдромный алгоритм декодирования. Правило формирования синдрома в общем виде можно записать так:

 

F (x) · H^T(x)=S(x) = 0

 

F (x) · H^T(x)=S(x) ≠ 0 ,

т.е. при отсутствии ошибок синдром S(x) =0, а при наличии ошибок S(x) ≠ 0.

5. При использовании порожденного (образующего) полинома P(x) могут быть сформированы КП либо систематического, либо несистематического ЦК. Правила формирования КП данных ЦК записывается следующим образом [1-3]:

 

F_i(x) = Q(x) · P(x) – несистематический ЦК;

 

F_i(x)=  + Q(x) · x^l=R(x) +Q(x) · x^l- систематические ЦК;(1.6)

где R(x) – проверочные символы,

Q(x) · x^l – информационные символы, сдвинутые по тактам в КП «k» на позиции.

6. При использовании проверочного полинома h(x), как и при использовании порожденного полинома P(x), могут быть сформированы как систематические, так и несистематические ЦК. ЦК, сформированные с помощью проверочных полиномов h(x), носят название дуальных кодов. Правила формирования КП с использованием h(x) в принципе записываются также, как и при использовании P(x).

7. Использование произведения примитивных полиномов m_i(x), i=1, 3,5,…P(x);h(x). Данный способ построения ЦК широкое применение получил в построении БЧХ-кодов. Порождающий полином БЧХ-кодов при использовании корней порождающего полинома записывается следующим образом:

 

                        P(x) = HOK[m₁(x) · m₃(x)…m_2t-1(x)],             (1.7)

 

где m_i(x) – примитивные полиномы, порядкового номера, который соответствует корням порождающего полинома.

 

1.5 Общие принципы построения G_{k , n} ( x ) и H_{l , n} ( x ) циклических кодов и их взаимосвязь

Так как порождающая 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]:

 

---

Дата добавления: 2018-10-27; просмотров: 445; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!