Презентация на тему Циклические коды

сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией

называется циклическим(CRC - Cyclic Redundance Code) (полиномиальным, кодом с циклическими избыточными проверками-ЦИП).

равномерным кодам.
Сдвиг осуществляется справа налево, при этом крайний левый

символ переносится в конец комбинации.
В циклических кодах кодовые комбинации представляются в виде многочленов, что позволяет позволяет свести действия над кодовыми комбинациями к действием над многочленами (используя аппарат полиномиальной алгебры).

обладают всеми их свойствами. Первоначально они были созданы для

упрощения схем кодирования и декодирования. Их эффек- тивность при обнаружении и исправлении ошибок обеспечила им широеое применение на практике.
Циклические коды используются в ЭВМ при последовательной передаче данных

исходного кода на образующий полином g(x), а декодирование -

в делении на g(x). Если остаток от деления не равен нулю, то произошла ошибка. Сигнал об ошибке поступает на передатчик, что вызывает повторную передачу.

процедурам умножения и деления полиномов. Для двоичных кодов эти

операции легко реализуются технически с помощью линейных переключательных схем (ЛПС), при этом получаются относительно простые схемы кодеков, в чём состоит одно из практических достоинств ЦК.

k]-кодов. Название ЦК получили из-за своего основного свойства: циклическая

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

комбинацией будет и А2 - 010110, полученная циклической перестановкой.

Отметим, что перестановка производится вместе с проверочными символами, и по правилам линейных кодов сумма 6 по модулю 2 двух разрешённых кодовых комбинаций даёт также очередную разрешённую кодовую комбинацию.
Описание ЦК связано с представлением кодовых комбинаций в виде полиномов (многочленов) фиктивной переменной "X". Для примера переведём кодовое словоА1 = 101100 в полиномиальный вид


При этом А1(X) = 1 · X5 + 0 · X4 + 1 · X3 + 1 · X2 + 0 · X1 + 0 · X0 = X5 + X3 + X2.

Циклический код с порождающим многочленом g(x)=1+x обнаруживает все ошибки

нечетной кратности.
Свойство 2. Циклический код с порождающим многочленом степени r=n-k обнаруживает любую пачку ошибок длиной r и менее.
Свойство 3. Циклический код не обнаруживает часть пачек ошибок длиной r+1

Bi (X) = Ai (X) ·X^r

+ Ri (X), где Ri (X) — остаток от деления Ai (X) ·X^r /G(X). X ^r - оператор сдвига
Ai(X) –информационные и проверочные Ri(X) символы.
В алгоритме можно выделить три этапа формирования кодовых комбинаций:
1) к комбинации первичного кода Ai(X) дописывается справа r нулей, что эквивалентно умножению Ai (X) на Xr ;
2) произведение Ai(X)·Xr делится на соответствующий порождающий полином G(X) и определяется остаток Ri(X), степень которого не превышает r - 1, этот остаток и даёт группу проверочных символов;
3) вычисленный остаток присоединяется справа к Ai (X) ·Xr.

Определить и исправить ошибку в Bi' (X), если она

имеется.
Выполним три необходимые операции,проводимые при декодировании: