Циклические коды.

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

циклические коды .

ЦК — это разновидность линейно группового кода отн. к систематическому коду. Циклический вектор двоичного кода удобно задавать в виде многочлена (а не комбинации 0,1). F(x)=an-1xn-1(+)an-2an-2(+)…(+)a1x(+)a0 (*)

х — основание системы счисления, в которой строится код. ai, где i=0,(n-1) — это цифры данной системы счисления. Например: x=3, ai=0,1,2. Мы рассм. Х=2, ai=0,1.

ПРИМЕР: представить числовую последовательность в виде многочлена F(x)=1x3(+)0x2(+)0x(+)1, F(x)=x3(+)1. Представление двоичных векторов в виде многочлена позволяет перейти от действий над векторами к действию над многочленами. При этом сложение векторов предполагает сложение многочленов, которое осуществляется как сумма по модулю х одноименных коэффициентов. Умножение векторов соответствует умножению по правилу умножения многочленов, деление векторов — это деление многочленов, причем операция “-“ преобразуется в операцию “+” по модулю. F1(x)=x3+x2+1, F2(x)=x+1.

1) F1(x)+F2(x)=x3+x2+x (в двоичной системе 1+1=0), 2) F1(x)*F2(x)=(x3+x2+1)(x+1)=x3+x3+x3+x2+x+1=x4+x2+x+1,

3) F1(x)/F2(x)=x2.

Основным свойством циклического кода

является: если некоторый вектор принадлежит

циклическому коду, то любой другой вектор,

полученный из данного путем произвольного числа циклических сдвигов также принадлежит

циклическому коду. Идея построения циклического кода базируется на понятии неприводимого многочлена, который делится только на самого себя и на единицу, т.е. не может быть разложен на более простые многочлены. Сам же неприводимый многочлен является делителем многочлена xn(+)1 без остатка. Неприводимые многочлены в теории циклических кодов играют роль образующих многочленов или полиномов. Эти полиномы табулированы. P(x)=x+1, P(x2)=x2+x+1, P(x3)=x3+x+1, P(x4)=x3+x2+1. Вектор циклического кода по заданному информационному слову строится следующим образом:

Пусть задано информационное слово Q(x) и многочлен P(xr ). Тогда, когда слово F(x)=Q(x)*xr + Res [Q(x)xr / P(xr )], 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.

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

G(n, k) = ||ITk x k, Pk x (n-k)||, P — матрица проверочных разрядов.

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

Q1(x)=1, Q2(x)=x, Q3(x)=x2, Q4(x)=x3.

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

Обнаружение и исправление ошибок в ЦК.

Любое кодовое слово ЦК делится на неприводимый многочлен без остатка, поэтому признаком наличия ошибки в принятом слове является ненулевой остаток от деления принятого слова на неприводимый многочлен. Однако наличие ненулевого остатка лишь говорит о факте существования ошибки, т.е. ошибки обнаруживаются, но по виду остатка нельзя судить о месте возникновения ошибки. Для коррекции t и менее ошибок используется следующий алгоритм: 1) принятое слово делится на неприводимый полином. 2) подсчитывается вес остатка. 3)Если вес не превышает корректирующую способность кода (t), то остаток суммируется с делимым и полученная сумма — есть правильное слово. Если вес остатка больше t, то принятое слово циклически сдвигается влево на один разряд, делится на P(x^r ) и анализируется вес остатка. Если вес остатка не больше t, то остаток прибавляется к делимому. Полученная сумма циклически сдвигается вправо на один разряд. Результат этой операции — скорректированное слово. Если вес остатка больше t, то делимое еще раз сдвигается влево. ПРИМЕР: ЦК задан порождающей матрицей G=

P(x³)=x³+x²+1, t=1, d_min=3

Кодовое слово: A=0001101,

слово с ошибкой: A’=0011101=x⁴+x³+x²+1,

делим столбиком A’/ P =x,

остаток Res=x²+x+1, ω(Res)=3>t (исправлять не надо). Теперь сдвигаем

A’^1y (сверху стрелкаß) = 0111010, и опять также делим Res=x+1 (ω=2)>t, опять значит не то — сдвигаем опять влево и так далее, пока не станет Res=1 (ω=1=t). Исправляем последний символ A’^3y(ß) на обратный и двигаем,àа 3. Это будет A=0001101.

Необнаруживаемые циклическим кодом ошибки.

Представим вектор одиночных ошибок в виде единичной матрицы с побочной сл. диаг. К такой матрице добавим справа матрицу, полученную от деления каждого вектора ошибок на порождающий многочлен. Дописываемая матрица называется матрицей остатков и имеет r столбцов, где r — степень порождающего многочлена. В итоге получим матрицу M^’, которую будем анализировать. Матрица одиночных ошибок:

 M’=|| I_n*n^T*(I^T_r*r/R) ||

Не обязательно знать кодовое слово, достаточно знать ошибочную строку(слово ошибок).

V=C+E.

Для изучения свойств кодов принятое слово представляем в виде суммы кодового слова C и слова ошибки E. Известно, что при делении C на порождающий многочлен остаток всегда равен 0. Т. о. для изучения свойств кода достаточно изучать остаток от деления вектора E на порождающий многочлен. Именно на этом основании и построена матрица M’. Как видно из матрицы остатков в M’, все остатки ненулевые и различны, что одиночные ошибки исправляются 100%. Кроме того, обнаруживаются 2-кратные ошибки, о чем можно узнать, построив матрицу M’’, где в k-той строке будет по 2 ошибки. При этом подматрица остатков не будет содержать 0-вых строк, однако среди них возникнут повторяющиеся строки. Аналогично для любого циклического кода. Следует сказать, что фактическое обнаруж. способность кода больше, чем гарантированная. Так для рассматриваемого кода гарантированная обнаруживающая способность =2, из общего количества 35 3-хкратных ошибок не обнаруживаются только 7, из 4-хкратных - тоже 7, не обнаруживается единственная 7-кратная ошибка. Итого не обнаруживается всего 15 ошибочных комбинаций.

Реализация схем кодирования и декодирования в ЦК.

Рассмотрим основные структуры кодеров и декодеров циклических кодов. Схемы, построенные на основе регистров сдвига, называются цифровыми фильтрами. Основа — циклический сдвиг. Чаще всего это D-триггер. n-разрядный регистр сдвига используется для циклического сдвига многочлена xⁿ-1. Каждый раз после сдвига вычисляется x*V(x)(mod(xⁿ-1)),

V(x) — некоторый начальный вектор, который помещен в этот регистр. Структура определяет выражение по модулю xⁿ-1, где n — количество регистров. х — умножение, в логике — сдвиг. Умножение на х соответствует однократному циклическому сдвигу V(x) вправо, причем старшие разряды слова находятся справа.

Обобщенная схема делительного устройства:

Данная схема делит входной полином на порождающий многочлен g(x). В начальном

состоянии все триггеры сброшены и первые

r сдвигов на выходе последнего триггера 0, т.е.

обратная связь разомкнута. Многочлен

d(x) проталкивается в схему начиная со

старших коэффициентов. После n сдвигов,

где n — степень многочлена d(x) на выходе схемы будет частное, a в самом регистре будет записан остаток от деления d(x) на g(x).

g(x)=g_r x^r + …+g1x+g0.

Пример: построить схему деления на многочлен g(x)=x⁶+x⁵+x⁴+x³+1

d(x)=11000001, d(x)(à)=10000011.

Разделить d(x)=x⁷+x⁶+1

Результат — остаток 110011 (R=x⁵+x⁴+x+1).

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