Заработок в интернет постоянно и регулярно платят

Обзор основных принципов CRC.


Введение.

CRC (Cyclic Redundancy Check; буквально - циклическая проверка излишка) является очень мощным, но легко осуществляемым способом достижения надежности данных. Техника CRC используется для защиты блоков данных, называемых Frames. Используя эту технику, передатчик добавляет дополнительную n-битную последовательность к каждому блоку, называемую Frame Check Sequence (FCS). FCS содержит излишнюю (многословную) информацию о блоке, которая помогает передатчику определить наличие ошибок в блоке. CRC является одним из наиболее распространенных методов обнаружения ошибок при передаче информации. Метод завоевал популярность благодаря соединению трех преимуществ:

  1. Чрезвычайные возможности обнаружения ошибок.
  2. Малые накладные расходы.
  3. Легкость в применении.

Как работает алгоритм CRC.

Алгоритм CRC работает над бинарным полем. Алгоритм рассматривает все битовые потоки как двоичные полиномы. Получив исходный блок, передатчик рассчитывает для него FCS. FCS рассчитывается таким образом, чтобы результирующий блок (объединение исходного блока и FCS) делился без остатка на некоторый определенный ранее полином. Этот полином называется делителем, или CRC Полиномом.

Введем следующие обозначения:


Пример.

M=1010001101 (k=10) и P=110101 (n=5, n+1=6).

Тогда вычисленный передатчиком FSC будет содержать 5 бит. Пусть передатчик рассчитал FSC, и он оказался равным

F=1110 (n =5)

Тогда будет передан блок:

T=10100011011110


Основные идеи.

Основная идея CRC состоит в том, что FCS рассчитывается таким образом, что остаток от деления T на P есть ноль.

Имеет место равенство T=M * 2^n + F. Оно следует из того, что добавляя F к M, мы сдвигаем T на n бит влево и затем добавляем F к результату.

Так как мы хотим, чтобы передаваемый блок T делился нацело на P, то мы должны находить подходящий FCS (F) для каждого нового сообщения (M).

Обозначим частное от деление буквой Q, а остаток - R:

M* 2^n / P = Q + R/P.

Полученный остаток R мы используем в качестве FSC (F). Таким образом,

T = M *2^n + R

Нетрудно заметить, что такой выбор FCS делает передаваемый блок делящимся на P, так как

T/P=(M*2^n + R)/P= M*2^n/P +R/P = Q + R/P + R/P = Q + (R+R)/P,

но по правилам бинарной арифметики любое число, складываемое с самим собой (по модулю 2) дает ноль, так что T/P=Q без остатка.


Обзор процесса создания CRC:

  1. Получение исходного блока.
  2. Сдвиг этого блока на n бит влево и деление его на P.
  3. Остаток последней операции объявляется FCS.
  4. Добавление FCS к исходному блоку. Результат - блок, который надо передавать.

Обзор процесса проверки CRC:

  1. Получение блока.
  2. Деление его на P.
  3. Проверка остатка. Если он не нулевой, то в блоке была ошибка.

Можно легко видеть, что CRC алгоритм должен вычислять остаток при делении двух полиномов. Сам процесс описывается ниже.


Наиболее распространенные CRC Полиномы.

Наиболее часто применяются следующие четыре полинома:

CRC-12: x^12 + x^11 + x^3 +x^2 + x +1

CRC-16: x^16 + x^15 + x^2 +1

CRC-CCITT: x^16 + x^12 + x^5 + 1

CRC-32: x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1

CRC-12 используется для передачи потоков из шести бит и генерирует 12-битный FCS. CRC-16 и CRC-CCITT используются для 8-битовой передачи потоков, и оба генерируют 16-битный FCS. Они оба широко используются и в США, и в Европе и дают удовлетворительную защиту для большинства приложений. Приложения, в которых требуется особо высокая степень защиты, могут использовать CRC-32, который генерирует 32-битный FCS. CRC-32 используется, в частности, комитетом по стандартам локальных сетей (IEEE-802).



Заработок в интернет постоянно и регулярно платят