З таблиці видно, що найбільшими перевагами за сукупністю параметрів характеризуються циклічні CRC-коди. Тому в якості базового коду для реалізації і дослідження вибираємо CRC-коди.
І так CRC це залишок від ділення повідомлення на поліном. Тобто все повідомлення (файл, архів) ділимо згідно модулю на деяку константу (її називають поліномом). Залишок від ділення і є CRC. Ділення виконується з використанням поліноміальної арифметики, тобто арифметики без перенесень і позик. У поліноміальній арифметиці:
0+0= 0 0-0=0
0+1 = 1 0-1=1
1+0 = 1 1-0=1
1+1 = 0 1-1=0
Видно, що додавання в поліноміальній арифметиці - це те ж, що і віднімання, тобто це операція XOR - виключне або. У підручниках із дискретної математики її позначають кружком з косим хрестиком усередині. Ми позначатиму цю операцію значком ^, як в Сі або просто «+». У поліноміальній арифметиці 100 плюс 110 рівне 10, але 100 мінус 110 теж рівне 10. Немає ні знаку, ні певного порядку бітів. Всі біти рівнозначні, і це дуже важлива властивість для CRC. Якщо переставити декілька бітів в обох доданках, ті ж біти будуть переставлені в сумі: 1010 ^ 1100=0110.
Поміняємо місцями перші два і останні два біта: 1010 ^ 0011=10 01.
Біти можна представити як коефіцієнти многочлена (полінома). Тому арифметику називають поліноміальною, а дільник в алгоритмах CRC - поліномом.
При практичній реалізації зрозуміло, ділення поліномів відрізняється від наведеного в п. 2.2. Розглянемо два алгоритми обчисленні CRC [17].
Перший простий алгоритм, у якому виконується звичайне ділення в стовпчик, але замість віднімання використовують операцію XOR:
Нехай необхідно поділити повідомлення: 1101010 на число 101 (поліном):
1101010
^101
111010
10010
=====
110
===
11
Тобто CRC=11. Саме так рахують CRC. Зауважте, що в кожному стовпчику ми віднімаємо старші біти 1-1=0. У наступних бітах можуть бути будь-які числа. Один раз ми отримали нуль в старшому біті, і нам довелося зсунути управо на 2 біта, а не на один. Отже, можна записати такий алгоритм (це не робочий код, він тільки показує алгоритм):
data - повідомлення (бітовий рядок), POLY - поліном
while(length(data)> length(POLY))
{r = TORBIT(data); // Виділяємо старший біт data
data <<= 1; //І викидаємо його з основного числа data
if(r)
data ^= POLY;
}
У стовпчиках ми зсували поліном 101 управо, кожного разу віднімаючи його з повідомлення. У цьому алгоритмі поліном залишається на місці, але ми «рухаємо» ділиме вліво. Якщо старший біт r дорівнює нулю, ми зсуваємо ще на один біт, не віднімаючи POLY. Константа POLY дорівнює поліному без старшої одиниці, тобто 01. Першу одиницю писати немає чого, оскільки двійкове число завжди починається з одиниці. Як працює цей код, легко зрозуміти на прикладі. Візьмемо те ж повідомлення 1101010 і той же поліном 101:
Крок 1. r = 1 // Відокремили перший біт
data = 101010 // r=1, тому виконуємо операцію XOR
^01
==
Крок 2. r = 1
data = 11010
^01=====
Крок 3. r = 1
data = 0010
====
0110
Крок 4. r = 0 // XOR не виконуємо
data = 110
Крок 5. r = 1
data = 10
Отже, алгоритм в цілому зрозумілий: ділимо data на POLY, отримуємо остачу CRC. І при діленні 0-1=1, 1+1=0 без перенесення.
Складність полягає в тому, що повідомлення може важити декілька мегабайт. Як же розділити його на поліном? Зверніть увагу, що при кожному проході циклу у нас міняються тільки 2 перших біта data. Значить, можна проходити через все повідомлення, читаючи в кожен момент часу невелику порцію даних (у нашому випадку - перші два біта).
Але у цього алгоритму є ще один недолік: він обробляє по одному біту повідомлення. Наприклад, для мегабайтного файлу він зробить 8 мільйонів проходів циклу, і кожного разу витягуватиме окремі біти. Є інший підхід, який прискорює підрахунок CRC мало не в десятки разів. Це використання табличних методів обчислення CRC.
Ідея табличного методу така: оброблятимемо по байту за один прохід циклу. Коли ми ділимо байт на поліном, у нас в залишку виходить деяке число, причому воно не залежить від інших байтів повідомлення. Ось це число ми можемо зберігати в таблиці для кожного ділимого байта. Маючи таку таблицю, отримуватимемо CRC для кожного байта за один прохід. Для прикладу, візьмемо слово, рівне 3 бітам, і короткий поліном 111. Хай повідомлення складається з 5 бітів, назвемо його abcde. Пройдемо наш старий алгоритм по кроках:
Крок 1. if(a)
bc ^= 11;
Крок 2. if(b)
cd ^= 11;
Крок 3. if(c)
de ^= 11;
Коли ми підрахували bcd і перейшли на другий крок, біт а вже не потрібний, і на подальші підрахунки він ніяк не впливає. Коли дійшли до останнього кроку, виявилися непотрібними біти а і b. А після третього кроку зіграв свою роль біт c, який тепер сходить із сцени. Те, що помінялися біти abc, вже не важливе, тому що на четвертому, п'ятому і так далі кроці вони не використовуватимуться. Але на цих трьох кроках якось змінилися біти de. І змінилися вони залежно від бітів abc.
Переберемо всі значення abc, починаючи з 000 і до 111:
000 (a=0, b=0, c=0) - жодне з умов не виконується, тому біти def не змінилися.
001 (a=0, b=0, c=1) - умова if(c) виконалася:
001def
^11
010 - умова if(b) виконалася, але після додавання одиниці до с виконалося також if(c). Запишемо під межею результат операції XOR над двома відповідними числами в бітах de:
Abc
010de
01
011 -- виконалася умова if(b), але біт с був при цьому обнулений, тому if(c) не спрацювало:
011de
10
100 -- спрацювала умова if(a), яка викликало if(b). В результаті біт d буде підданий операції XOR з одиницею:
100de
101 - аналогічно, але біт «c» обнулився, і результат - нульовий:
Abc 101de
Те ж саме ти можеш написати для 110 і 111. Зробимо масив t з індексами від 000 до 111, в якому зберігатимемо результати наших обчислень:
індекс значення
000 00
001 11
010 01
011 10
100 10
101 01
110 11
111 00
Тепер, використовуючи цю таблицю, розрахувати CRC можна значно швидше:
t - масив, abcdefghi - повідомлення
de ^= t[abc];
gh ^= t[def];
crc = ghi;
Якщо розширити 3-х бітне слово до 8 біт (байт) і взяти 8-бітний або 32-бітний поліном, то отримаємо готовий алгоритм для розрахунку CRC табличним методом. Схема обчислення CRC для випадку 32-бітного полінома наведена на рис. 3.1.
2. Button Control - використовується п'ять форм Button для подачі команд підрахувати CRC, перевірити CRC файла, відкриття файлу для підрахунку CRC і запису CRC файлу на диск.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
