16.5. CRC (ЦИКЛИЧЕСКАЯ КОНТРОЛЬНАЯ СУММА)

CRC (Cyclical Redundancy Check) - циклический код для обнаружения ошибок.
CRC не исправляет ошибки, но позволяет их обнаруживать.

В общем то CRC это остаток от деления двоичного многочлена блока данных
на образующий полином.
Но деления не двоичного, а на поле Галуа GF(2^N).
Т.е. вместо вычитания используется XOR.

Эварист  Галуа (1811-1832).

Есть определенные трудности с тем какое число больше, какое меньше
на поле Галуа.
Потому что и сложение и вычитание - это XOR.
Пример:	1001 = 1010 + 0011    (в смысле на GF)
	1001 = 1010 - 0011
Кстати:  A + 0 = A
	 A - 0 = A
Поэтому для сравнения чисел действует правило:
	X > Y, если позиция старшей 1 в X более значима чем в Y.
А дальше все как в обычном делении.



Пример вычисления CRC:
	Блок данных:		101110101010
	Образующий полином:	10011		x^4 + x + 1
				 ----
				 размер CRC = 4 бита (т.к. полином четвертой
						      степени).

Добавляем к блоку данных 4 нулевых бита (т.к. у нас образующий полином
четвертой степени).

Деление:
	1011101010100000
	10011
	-----
	00100
	  10001
	  10011
	  --------
	  00010
	     10010
	     10011
	     -------
	     00001
		 11000
		 10011
		 -------
		 01011
		  10110
		  10011
		  ------
		  001010  
		    1010  => CRC = 1010

На посылку идет: 101110101010 1010
		 ------------ ----
		    Data      CRC

Теперь посмотрим какой результат будет для пересланного блока:


	1011101010101010
	10011
	-----
	00100
	  10001
	  10011
	  --------
	  00010
	     10010
	     10011
	     -------
	     00001
		 11010
		 10011
		 -------
		 01001
		  10011
		  10011
		  -------
		  00000
		    0000   => поделилось нацело



Не любой образующий полином подходит.
Он должен обладать следующими свойствами:

Допустим:
	T - передаваемое сообщение  (последние W бит - это CRC).
	G - образующий полином

	T mod G = 0
	
при ошибке получаем вместо T  - T(+)E, где Е - вектор ошибки
	(T(+)E) mod G = E mod G	

Обнаружение одинарных ошибок:
	E = 1000..0000
	    01.....000
		...
	    000....001
	чтобы их обнаружить наш полином должен иметь по крайней мере
	два единичных бита.

Обнаружение двойных ошибок:
	полином не должен иметь множителей вида:
		11
		101
		1001
		10001
		итд
		100...001

Обнаружение нечетного числа ошибок:
	полином должен иметь четное число единичных бит

Обнаружение пакетных ошибок
	E = 000111..11000
	E можно преобразовать в 1000.0001...1
	полином должен иметь младший бит = 1
	пока G шире чем 1..1 в E, ошибка обнаруживается

	Вероятность пакетной ошибки с длинной больше W 
	примерно равна (0.5)^W




Стандартные образующие полиномы:

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-24:		X^24 + X^23 + X^14 + X^12 + X^8 + 1
CRC-8:		X^8 + X^7 + X^6 + X^4 + X^2 + 1
CRC-4:		X^4 + X^3 + X^2 + X + 1



Вычисление CRC может легко быть проведенно аппаратно.
Для этого используются LFER (Linear Feedback Shift Register) - сдвиговые
регистры с линейной обратной связью.



 
  THIS SECTION IS UNDER CONSTRUCTION  
 


Пример LFER для CRC-16:
  


Пример LFER для CRC-32:
  


Кроме CRC LFER используются для генерации последовательности ПСЧ (псевдо-
случайных чисел).