1.3.1. Вимоги складності

Вище показано, що пошкодження повідомлення може бути виявлено, використовуючи в якості алгоритму контролю просте додавання байтів повідомлення по модулю 256:

Повідомлення : 6 23 4

Повідомлення з контрольною сумою : 6 23 4 33

Повідомлення після передачі : 6 27 4 33

Недолік цього алгоритму в тому, що він дуже простий. Якщо відбудеться кілька викривлень, то в 1 випадку з 256 не зможемо їх знайти. Наприклад:

Повідомлення : 6 4 23

Повідомлення з контрольною сумою : 6 23 4 33

Повідомлення після передачі : 8 20 5 33

Для підвищення надійності можна було б змінити розмір регістра з 8-бітного на 16 бітний (тобто підсумувати по модулю 65536 замість модуля 256), що, швидше за все, знизить імовірність помилки з 1/256 до 1/65536. Хоча це і непогана ідея, проте, вона має той недолік, що застосовується формула розрахунку яка не "випадкова" належною мірою – кожен додаваємий байт впливає лише на один байт підсумкового регістра, при цьому ширина самого регістра не має ніякого значення. Наприклад, у другому випадку підсумовуючий регістр міг би мати ширину хоч мегабайт, проте помилка все одно не була виявлена. Проблема може бути вирішена лише заміною простого підсумовування більш складною функцією, щоб кожен новий байт впливав на весь реєстр контрольної суми.

Таким чином, сформульовано дві вимоги для формування надійної контрольної суми:

Ширина. Розмір регістра для обчислень повинен забезпечувати початкову низьку ймовірність помилки (наприклад, 32 байтний регістр забезпечує ймовірність помилки 1/232).

Випадковість. Необхідний такий алгоритм розрахунку, коли кожен новий байт може вплинути на будь-які біти регістра.

Слід звернути увагу, що термін "контрольна сума" спочатку він описував досить прості підсумовуючі алгоритми, однак, в даний час він використовується у більш широкому сенсі для позначення складних алгоритмів розрахунку, таких як CRC. Алгоритми CRC дуже добре задовольняють другій умові і, крім того, можуть бути адаптовані для роботи з різною шириною контрольної суми.

Контрольна сума – число, що є функцією деякого повідомлення. Буквальне трактування даного слова вказує на те, що виконується просте підсумовування байтів повідомлення, що, очевидно, і робилося в ранніх реалізаціях розрахунків. Однак, на сьогоднішній момент, незважаючи на використання більш складних схем, цей термін має широке застосування.

Якщо складання, очевидно, не придатне для формування ефективної контрольної суми, то такою дією цілком може виявитися ділення за умови, що дільник має ширину регістра контрольної суми.

Основна ідея алгоритму CRC полягає у представленні повідомлення в вигляді величезного двійкового числа, поділ його на інше фіксоване двійкове число і використання залишку цього поділу як контрольної суми. Отримавши повідомлення, приймач може виконати аналогічну дію і порівняти отриманий залишок з "контрольною сумою" тобто переданим залишком.

Припустимо, що повідомлення складається з 2 байт (6, 23), як і в попередньому прикладі. Їх можна розглядати, як шістнадцяткове число 0617h, або як двійкове число 0000 0110 0001 0111. Припустимо, що ширина регістра контрольної суми становить 1 байт, а як дільник використовується 1001, тоді сама контрольна сума дорівнюватиме залишку від ділення 0000 0110 0001 0111 на 1001. Хоча в цій ситуації розподіл може бути виконано з використанням стандартних 32 бітних регістрів, в загальному випадку це не вірно. Тому скористаємося діленням у "стовпчик". Тільки на цей раз, воно буде виконуватися в двійковій системі числення. Ділення у двійковій системі проводиться вирахуванням дільника зі зрушенням вправо, якщо залишок більше нуля.

(6, 23)=0000 0110 0001 0111_BIN = 0617_HEX = 1559_DEC

					1024+512+16+4+2+1=1559DEC													128+32+8+4+1=173DEC
					1024	512	256	128	64	32	16	8		4	2	1	128		64	32	16		8		4		2	1
0				6				1					7					→ 0617HEX
0	0	0	0	0	1	1	0	0	0	0	1	0		1	1	1	1		0	0	1		9DEC
				–	1	0	0	1	↓	↓	↓	↓		↓	↓	↓	1		0	1	0		1		1		0	1
				=	0	0	1	1	0	0	1	0		1	1	1
					→	1	0	0	1		↓	↓		↓	↓	↓	0
						–	1	0	0	1							1
						=	0	0	1	1	1	0		1	1	1
							→	1	0	0	1			↓	↓	↓	0
								–	1	0	0	1					1
								=	0	1	0	1		1	1	1
									–	1	0	0		1	↓	↓	1
									=	0	0	1		0	1	1
										→	1	0		0	1		0
											–	1		0	0	1	1
											=	0		0	1	0	Залишок від ділення = 2

Рис.1.3 — Схема ділення у двійковій системі числення

Робимо перевірку:

1559 / 9 = 173 та залишок 2;

0000 0110 0001 0111 / 1001 = 10101101 та залишок 0010;

10101101 = 173;

0010 = 2;

Ділення у двійковій системі числення виконано вірно.

В десятковому вигляді це буде звучати так: "частка від ділення 1559 на 9 дорівнює 173 і 2 в залишку".

Хоча вплив кожного біта вихідного повідомлення на частку не настільки істотний, однак 4 бітний залишок під час обчислень може радикально змінитися, і чим більше байтів є у вихідному повідомленні (у діленому), тим сильніше змінюється кожного разу величина залишку. Ось чому поділ виявляється застосовується там, де звичайне складання працювати відмовляється.

У нашому випадку передача повідомлення разом із 4 бітною контрольною сумою виглядала б (у шістнадцятковому вигляді) наступним чином: 06172, де 0617 - це саме повідомлення, а 2 - контрольна сума. Приймач, отримавши повідомлення, міг би виконати аналогічне поділ і перевірити, дорівнює чи залишок переданому значенню (2).

Хоча арифметичне ділення, описане вище, дуже схоже на схему розрахунку контрольної суми, званої CRC, сам же алгоритм CRC трохи більш складний, і, щоб зрозуміти його, необхідно зануритися в теорію цілих чисел.

Поліном є дільником CRC алгоритму. Усі CRC алгоритми засновані на поліноміальних обчисленнях, і для будь-якого алгоритму CRC можна вказати, який поліном він використовує.

Замість подання дільника, діленого (повідомлення), частки і залишку у вигляді позитивних цілих чисел можна представити їх у вигляді поліномів з двійковими коефіцієнтами або у вигляді рядка біт, кожен з яких є коефіцієнтом полінома. Наприклад, десяткове число 23 у шістнадцятковій системі числення має вигляд 17, а в двійковому – 10111, що збігається з поліномом:

1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0 або, простіше:

x^4 + x^2 + x^1 + x^0

І повідомлення, і дільник можуть бути представлені у вигляді поліномів, з якими, як і раніше можна виконувати будь-які арифметичні дії. Припустимо, що хочемо перемножити, наприклад, 1101 і 1011. Це можна виконати, як множення поліномів:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)

= (x^6 + x^4 + x^3

+ x^5 + x^3 + x^2

+ x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Тепер для отримання правильної відповіді необхідно вказати, що Х дорівнює 2 (двійкова система числення), і виконати перенесення біта від члена 3*x^3.

В результаті отримаємо:

x^7 + x^3 + x^2 + x^1 + x^0

Все це дуже схоже на звичайну арифметику, з тією лише різницею, що основа у нас лише передбачається, а не чітко вказано. Якщо "X" невідомий, то не можемо виконати перенесення. Невідомо, що 3*x^3 – це те ж саме, що і x^4 + x^3, бо не знаємо, що X=2. У поліноміальній арифметиці зв'язки між коефіцієнтами не встановлені, і, тому, коефіцієнти при кожному членові полінома стають строго типізованими – коефіцієнт при x^2 має інший тип, ніж при x^3.

Якщо коефіцієнти кожного члена полінома повністю ізольовані один від одного, то можна працювати з будь-якими видами поліноміальної арифметики, просто змінюючи правила, за якими коефіцієнти працюють. Одна з таких схем для нас надзвичайно цікава, а саме, коли коефіцієнти складаються за модулем 2 без переносу – тобто коефіцієнти можуть мати значення лише 0 або 1, перенесення не враховується. Це називається "поліноміальна арифметика за модулем 2".

Повертаючись до попереднього прикладу:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)

= (x^6 + x^4 + x^3

+ x^5 + x^3 + x^2

+ x^3 + x^1 + x^0)

= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

За правилами звичайної арифметики, коефіцієнт члена 3*x^3 розподіляється по іншим членам полінома, використовуючи механізм перенесення і припускаючи, що X=2. В "поліноміальній арифметиці за модулем 2" не відомо, чому дорівнює "X", переносів тут не існує, а всі коефіцієнти розраховуються за модулем 2.

В результаті одержуємо:

= x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

Таким чином, поліноміальна арифметика за модулем 2 – це фактично двійкова арифметика за модулем 2 без урахування переносів. Хоча поліноми мають зручні математичні засоби для аналізу CRC алгоритмів і алгоритмів корекції помилок, для спрощення вони будуть замінені, на безпосередньо арифметичні дії в системі, з якою вони ізоморфні (відносно еквівалентні), а саме в двійковій системі арифметики без переносів.