Матричное представление циклических кодов

Циклический код может быть задан порождающей матрицей.

Для формирования строк порождаю­щей матрицы разделимого циклического кода берут не произволь­ные информационные комбинации кода Q(x), а только те из них, которые содержат единицу в одном разряде. Эти комбинации умножают на х^r и находят остаток от деления Q_i(x)·x^r на P(x). Обозначим полученный остаток R_i(x). Тогда i-строку порождающей матрицы записывают в виде Q_i(x)·x^r R_i(x).

Матрица, со­стоящая из этих строк, может быть представлена как две подматрицы:

где E^T_k - единичная транспонированная подматрица, содержащая Q_i(х) комбинаций информационного кода;

C_r,k - подматрица размером (kr), строки которой образованы остатками от деления R_i(x).

Порождающая матрица содержит k комбинаций циклического кода. Остальные 2^k-k-1 комбинаций получают суммированием по модулю 2 строк матрицы во всевозможных сочетаниях. Послед­няя комбинация является нулевой.

Пример

Требуется записать порождающую матрицу циклического кода (7;4), если образующий полином кода имеет вид Р(х)=х³+х+1 или в двоичном коде Р(0,1) = 1011.

По условию n=7; k=4; r=n-k=3. Следовательно, информационная часть кодовой комбинации содержит 4 элемента.

Для формирования строк порождаю­щей матрицы разделимого циклического кода составим информационные комбинации Q(x) состоящие из 4 элементов и содержащие единицу только в одном разряде. Очевидно, таких комбинаций четыре:

Найдем 1-ю строку производящей матрицы. Для этого определим остаток от деления Q₁(x)·x^r на P(x):

Будем выполнять все вычисления над двоичными числами:

Записываем первую строку порождающей матрицы в виде Q₁(x)·x^r R₁(x)=0001000 011=0001011.

Аналогично найдем 2-ю строку производящей матрицы. Остаток от деления Q₂(x)·x^r на P(x):

Как и раньше будем выполнять все вычисления над двоичными числами:

Записываем вторую строку порождающей матрицы в виде Q₂(x)·x^r R₂(x)=0010000 110=0010110.

Определяем третью строку:

^,

тогда третья строка имеет вид Q₃(x)·x^r R₃(x)=0100000 111=0100111.

Для четвертой строки имеем:

четвертая строка имеет вид Q₄(x)·x^r R₄(x)=1000000 101=1000101.

Производящая матрица G_7,4 имеет вид:

Строки матрицы G_7,4 являются первыми 4 комбинациями циклического кода. Пятая комбинация является нулевой. Остальные 11 комбинаций получаются суммированием по модулю 2 всех сочетаний строк матрицы.

Замечание: выше было сказано, что порождающая матрица может быть представлена как две подматрицы. Действительно, слева от пунктирной черты расположена единичная транспонированная матрица размера (kk) (в рассмотренном примере (44)). Она содержит информационные комбинации кода, содержащие единицу в одном разряде. Справа от пунктирной черты - подматрица размером (kr) (в примере (43)), строки которой образованы остатками от деления R_i(x).

Общие сведения об итеративном коде

Итеративные коды характеризуются наличием двух или более систем проверок внутри каждой кодовой комбинации.

Рассмотрим принцип построения итеративного кода на следующем примере. Предположим, что передаются информационные кодовые комбинации F(0,1) = 10111 00101 11100 01001 11101. Т.е. имеем 5 информационных комбинаций, каждая их которых содержит 5 элементов.

Сначала информационные элементы по группам записываются в виде таблицы:

Далее к каждой строке и к каждому столбцу дописываются про­верочные элементы в соответствии с каким-либо правилом коди­рования. Например, для кода с одной проверкой на четность по­лучим

Проверка на четность составляется таким образом, чтобы число единиц было четно по строкам, и по столбцам.

По­лученные кодовые комбинации являются комбинациями простейшего двумерного кода, проверочные разряды которого сосредо­точены в нижней строке и правом столбце. Каждый информаци­онный разряд кодовой комбинации входит в состав двух итери­руемых кодов с проверкой на четность (по строкам и столбцам). Передача комбинации итеративного кода обычно происходит по­следовательно от первой строки до последней. Приведенный код является простейшим итеративным кодом с d₀=4. Этот код об­наруживает все ошибки кратности до трех и все ошибки нечетной кратности.

Для итеративного кода верны следующие соотношения:

1. Длина кодовой комбинации

где S - кратность итерирования (количество итерируемых кодов);

n_i – число элементов в строке и в столбце с учетом проверочных элементов;

П – знак произведения.

Для рассматриваемого примера S=2, n₁=n₂=6, тогда n=6·6=36 – длина кодовой комбинации.

2. Число информационных разрядов в кодовой комбинации

где k_i – число информационных разрядов в итерируемых кодах.

В примере в обоих итерируемых кодах одинаковое число информационных разрядов (одинаковое число разрядов в строке и столбце без учета проверочных элементов), т.е. k₁=k₂=5, тогда k=k₁·k₂=5·5=25 – число информационных элементов в кодовой комбинации.

3. Минимальное кодовое расстояние

где d_0i – минимальное кодовое расстояние итерируемых кодов.

В примере d₀₁= d₀₂=2, тогда d₀= d₀₁· d₀₂=2·2=4.

В зависимости от свойств итерируемых кодов итератив­ный код может быть систематическим, и несистематиче­ским, разделимым и неразделимым и т. д.