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

Содержание

• 
  Слайд 1

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

  Выполнил: Студент группы КТ-10-1 Золотаренко М.С.

• 
  Слайд 2
  

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

• 
  Слайд 3
  

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

• 
  Слайд 4
  

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

• 
  Слайд 5
  

  Один из вариантов циклического кодирования заключается в умножении исходного кода на образующий полином g(x), а декодирование - в делении на g(x). Если остаток от деления не равен нулю, то произошла ошибка. Сигнал об ошибке поступает на передатчик, что вызывает повторную передачу.

• 
  Слайд 6
  

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

• 
  Слайд 7
  

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

• 
  Слайд 8
  

  Если, например, А1 - 101100, то разрешённой кодовой комбинацией будет и А2 - 010110, полученная циклической перестановкой. Отметим, что перестановка производится вместе с проверочными символами, и по правилам линейных кодов сумма 6 по модулю 2 двух разрешённых кодовых комбинаций даёт также очередную разрешённую кодовую комбинацию. Описание ЦК связано с представлением кодовых комбинаций в виде полиномов (многочленов) фиктивной переменной "X". Для примера переведём кодовое словоА1 = 101100 в полиномиальный вид При этом А1(X) = 1 · X5 + 0 · X4 + 1 · X3 + 1 · X2 + 0 · X1 + 0 · X0 = X5 + X3 + X2.

• 
  Слайд 9
  
• 
  Слайд 10
  

  Ряд свойств, характеризующих корректирующую способность циклических кодов.

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

• 
  Слайд 11
  

  Рассмотрим процедуру кодирования по алгоритму: 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.

• 
  Слайд 12
  
• 
  Слайд 13
  

  Принятая кодовая комбинация ЦК (7,4) имеет вид Bi'(X)=1011110. Определить и исправить ошибку в Bi' (X), если она имеется. Выполним три необходимые операции,проводимые при декодировании:

• 
  Слайд 14
  
• 
  Слайд 15
  

  1) в соответствии с алгоритмом (4.17) производим деление: