22. Понятие о циклических кодах. Порождающие многочлены. Структура кодового слова.

ЦК – это разновидность линейно группового кода отн. к систематическому коду. Обладает Доп.св-вом: любой циклический сдвиг кодового слова порождает другое кодовое слово. Циклический вектор двоичного кода удобно задавать в виде многочлена (а не комбинации 0,1). F(x)=a_n-1x^n-1(+)a_n-2х^n-2(+)…(+)a₁x(+)a₀ (*)

ai–коэф-ты,кот могут принимать значения 0 и 1. Представление двоичных векторов в виде многочлена позволяет перейти к действию над многочленами. Действия над многочленами: 1)сложение 2)умножение 3)деление

Основным понятием, на котором базируется построение циклического кода является неприводимый многочлен, который делится только на самого себя и на единицу, т.е. не может быть разложен на более простые многочлены. Коэф-т при старшей степени многочлена равен 1. Неприводимые многочлены в теории циклических кодов играют роль образующих многочленов или полиномов. Эти полиномы табулированы. P(x)=x+1, P(x²)=x²+x+1, P(x³)=x³+x+1, P(x³)=x³+x²+1. Вектор циклического кода по заданному информационному слову строится следующим образом:

Пусть задано информационное слово Q(x) и многочлен P(x^r). Тогда, кодовое слово С(x)=Q(x)*x^r + Res [Q(x)x^r / P(x^r)], Q(x) – информационное слово, которое надо закодировать. P(x) – порождающий многочлен.

Пример (КОДИРОВАНИЯ В ЦИКЛИЧЕСКОМ КОДЕ): число, которое подлежит кодированию – 0111. P(x3)=x3+x2+1, Q(x)=x2+x+1, r = 3, Q(x)*xr = x5+x4+x3, P(x)=x5+x4+x3+R, столбиком делим Q(x)*xr / P(xr ) = x2+1, остаток R=1.

ОТВЕТ: F(x)=x5+x4+x3+1 => 0111 001.

Циклический код, как и всякий систематический код код может быть задан в виде порождающей матрицы. Структура этой матрицы:

G(n, k) = ||I^T_k*k, Pr_*k||, P – матрица проверочных разрядов.

П РИМЕР: ПОСТРОИТЬ ПОРОЖДАЮЩУЮ МАТРИЦУ G(7,4) ЦК

Дано: n=7, k=4 P(x3)=x3+x2+1

Решение: Q1(x)=1, Q2(x)=x, Q3(x)=x2, Q4(x)=x3. Умножаем их еще на х³ так как P(x3).

Чтобы найти значения, которые потом вписать в правую часть матрицы, надо произвести деления столбиком получившихся членов и найти остатки, которые потом в соответствии с присутствующими степенями х преобразовать в двоичный вид и записать в правую часть. Res[Q(x)x3/P(x3)] - ? Надо 4 раза поделить. Делим на P, соответственно x3, потом x4, x5, x6.

22. Кодирование в систематическом и несистематическом циклическом коде.

ЦК можно построить как систематический, так и несистематический. Систематический строится в соответствии с C(x)=Q(x)*xr (+)Res[Q(x)xr / P(xr )]. Чтобы построить в несистематическом: C1(x)=Q(x)*P(x). Для реализации кодирования и декодирования используются специальные регистры сдвига с обратными связями или без них, которые в зависимости от конкретной схемы реализуют либо умножение, либо деление на порождающий многочлен (декодирование).

22. Порождающая матрица циклического кода

Т.к циклический код может быть представлен представляет собой сист ЛГК, он может быть представлен в виде порождающей матрицы. G(n,k)=[I^T _kk P_rk] –единичная матрица с побочной диоганалью.Р- матрица остатков от деления выражений Q(x)*x^r /p(x)^r . При наличии порожд матр все множество кодовых слов может быть получено путем всевозможных линейных комбинаций строк порождающей матрицы,включая 0 строку, поскольку она явл-ся единичным элементом группы для множ-ва кодовых слов. Алгоритм построения порождающ матрицы:

по заданному значению N, T, b определяется кол-во строк матр, кодовое расст d, из которых орпеделяется необходимое кол0во проверочных столбцов. По кол-ву проверочных столбцов r опред-ся степень неприводимого многочлена, затем из таблицы неприводимых многочленов выбирается один, степень которого равна r. В соответствии с формулой вычисляются все кодовые слова, входящие в порождающую матрицу. Затем проверка все ли строки порождающей м/цы имеют вес не меньше чем d. Если не выполняется то возварат, к таблиые неприводимых многочленов и использование другого.Если веса всех строк удовлетворяют требованию, то вычисляется расстояния по Хемингу м/у всеми возможными парами строк матрицы. Если хотя бы для одной пары не выполняется условие p>=d , то возврат на таблицу.Если для всех множеств степени r не вып-ся условие , то возврат на таблицу и увелечение на 1 значения r.

22. Алгоритм построения циклического кода с заданными свойствами. Как в любом коде, порождаемом матрицей все кодовые слова могут быть получены как все возможные линейные комбинации строк матрицы. Построение ЦК с заданными свойствами связано с выбором порождающего многочлена. В первую очередь это степени полинома n, которая равна количеству столбцов порождающей матрицы. Степень r определяется по специальным таблицам, в которых связаны следующие характеристики кодов: n – длина кода, k – количество информационных разрядов, d – кодовое расстояние => r. Рассмотрим принцип построения таблиц. Если имеется r проверенных разрядов, то это число степеней свободы. Если код должен иметь t=1, то 2r – 1 ≥ C1m (количество одиночных ошибок), если t=2, то 2r –1 ≥ C1m+C2m, r ≥ ]log2(C1m+…+Ctm+1)[. После получения порождающей матрицы G по заданному неприводимому полиному и по исходным требованиям осуществл-ся проверка полученного решения. Провер-ся вес каждой строки порожд матрицы ωi ≥ d_min. Расcт-е по Хэммингу между любой парой строк в порождающей матрице должно быть не меньше d_min. Если хоть одно условие не выполнится, то необходимо заменить неприводимый многочлен P(xr ), либо на другой многочлен этой же степени, либо на многочлен большей степени