CRC-арифметика Програмування, уроки та приклади

Розрахунки CRC ведуться у двійковій системі числення. При проведенні CRC-вирахувань використовується спеціальна CRC-арифметика, яка, по суті, є поліноміальною арифметикою за модулем 2. Поліноміальна арифметика за модулем 2 — це ще один із видів арифметик, що використовуються для вирішення завдань у певній предметній галузі та відрізняються від звичної двійкової арифметики з циклічним переносом відсутністю переносів та обчисленням всіх коефіцієнтів за модулем 2 . У уроці 20 «ММХ-технологія мікропроцесорів Intel» підручника під час розгляду ММХ-команд ми знайомилися з однією з таких альтернативних арифметик — арифметикою з насиченням. Тепер розглянемо особливості CRC-арифметики. Отже, як зазначено вище, в основі CRC-арифметики лежить поліноміальна арифметика. За визначенням, поліном - лінійна комбінація (сума) творів цілих ступенів заданого набору змінних із постійними коефіцієнтами. Окремий випадок - поліном, що містить одну змінну:

Тут un, nu щ - елементи деякої системи алгебри S, звані коефіцієнтами; х - змінна полінома, яку можна розглядати як формальний символ без певного значення. Алгебраїчна система S зазвичай являє собою безліч цілих або раціональних чисел в діапазоні 0..m-1 із додаванням, відніманням і множенням, що виконуються за модулем т. Для нашого розгляду особливо важлива поліноміальна арифметика за модулем 2, в якій кожен коефіцієнт полінома дорівнює одному з двох значень - 0 або 1. Наприклад, шістнадцяткове значення ОЕЗп може бути представлене наступним поліномом:

1х2 7 + 1х2 6 + 1х2 5 + 0х2 4 + 0х2 3 + 0х2 2 + 1x2 1 + 1x2 °.

Якщо ввести як змінну х=2, то отримаємо наступний двійковий поліном:

1хx 7 + 1xx 6 + 1xx 5 + 0хх 4 + 0xx 3 + 0xx 2 +1xx 1 + 1хх °.

У цьому поліномі, строго кажучи, значення х не відіграє особливої ролі, так як дане двійкове число можна уявити поліномом в іншій системі числення, наприклад, шістнадцятковій: ехх 1 + 2хх °, де х = 16. При цьому зауважимо, що в тому і В іншому випадку цифри 0, 1, е, 2 — це просто цифри двійкової та шістнадцяткової систем числення. Оскільки складові двійкового полінома з нульовими коефіцієнтами не дають жодного вкладу в кінцевий результат, то їх можна просто відкинути, залишивши тільки доданки, змінні яких мають одиничні коефіцієнти:

1xx7 + 1xx6 + 1xx5 + 0xx4 + 0xx3 + 0xx2 + 1xx1 + 1хх ° - = 1xx7 +1xx6 + lxx5 + 1xx1 + 1xx0 = = x7 + x6 + x5 + x1 + x°.

Тут x = 2. Над поліномами можна виконувати арифметичні операції: додавання, множення та віднімання. Процеси виконання цих операцій для поліноміальної арифметики та звичайної арифметики багаторазової точності (див. Розділ 1) схожі. Головна відмінність у тому, що через відсутність зв'язку між коефіцієнтами полінома поняття перенесення у поліноміальній арифметиці відсутнє. Наприклад, для множення 7h (0111b) на 5h (0101b) виконуються дії:

(х2 + х1 + х °) х (х2 + х °) = (х4 + х3 + х2 + х2 + х1 + х °) - = х4 + х3 + х2 + х2 + х1 + х ° + х ° = х4 + х3 + 2х2 + х1 + 2х °.

Для того щоб отримати у відповіді 35, ми повинні взяти х рівним 2 і привести коефіцієнти у членів полінома 2х° і 2х2 до двійкових, зробивши перенесення відповідних одиниць у старші розряди: 01010 переноси 11111 результат 100011 = 35)0. У результаті отримаємо двійковий поліном х5+х'+х°. Ці міркування покликані сформулювати чергову тезу про те, що переноси, як і в звичайній арифметиці, можна виконувати у випадку, коли відома основа системи числення. Тобто доти, доки ми не знаємо х, ми неможемо виробляти та переноси. У наведеному вище прикладі ми не знаємо, що 2х2 і 2х° насправді є х3 і х1 до тих пір, поки не відомо, що х = 2. Тобто в поліноміальній арифметиці коефіцієнти при різних ступенях ізольовані один від одного і відносини між ними не визначено. Через це виникає перша дивина поліноміальної арифметики — операції додавання та віднімання в ній абсолютно ідентичні і замість них можна сміливо залишати одну. Наприклад, додавання за правилами поліноміальної арифметики за модулем 2, її далі називатимемо CRC-арифметикою, буде виконано так:

З цього прикладу видно правила складання двійкових розрядів в арифметиці t з відсутністю переносів:

0+0=0; 0+1 = 1; 1+0=1; 1+1=0.

Операцію віднімання демонструє наступний приклад:

Правила виконання віднімання в арифметиці з відсутністю переносів:

Порівняння прикладів для складання та віднімання поліномів за модулем 2, а також правил, за якими вони виконуються, показує те, що ці дві операції CRC-арифметики ідентичні і за принципом формування результату вони аналогічні команді асемблера XOR. Мета, якою досягають усіма цими умовностями, - виключити з поля уваги всі величини (шляхом позик/переносів), що лежать за кордоном старшого розряду. Умноження в арифметиці з відсутністю переносів також виконується з урахуванням особливостей CRC-складання:

Видно, що в множенні особливостей немає, а ось додавання проміжних результатів проводиться за правилами CRC-складання. Для нашого розгляду особливий інтерес представляє операція поділу, так як в основі будь-якого алгоритму обчислення CRC лежить подання вихідного повідомлення у вигляді величезного двійкового числа, поділ його на інше двійкове число і використання залишку від цього поділу вяк значення CRC. Поділ - найскладніша з операцій CRC-арифметики. Тут необхідно ввести так зване слабке поняття розмірності: число X більше або дорівнює числу Y, якщо обидва числа мають однакову розмірність і позиції старших бітів одиничні, тобто співвідношення інших бітів X і Y для операції порівняння не має значення. Розглянемо приклади операції поділу, причому для кращого розуміння зробимо це у двох варіантах: спочатку пригадаємо, як виконується звичайний поділ (за правилами двійкової арифметики з циклічним переносом), а потім виконаємо власне CRC-поділ. Візьмемо довільну двійкову послідовність і розділимо її на деяке число за правилами двійкової арифметики з циклічним перенесенням (рис. 9.3). За правилами CRC-арифметики розподіл для наведених вище вихідних даних дасть наступний результат (рис. 9.4).

Мал. 9.3. Схема обчислення двійкового поділу (з циклічним перенесенням)

Мал. 9.4. Схема обчислення CRC-розподілу

Як бачите, результати звичайного та CRC-поділів відрізняються. Головне, щоб ви помітили особливість виконання CRC поділу. Особливу увагу зверніть на порядок формування проміжних результатів у процесі розподілу. Знесення двійкових розрядів з ділимого триває до того часу, поки розмірності проміжного бітового значення і дільника не зрівняються, які старші розряди стануть рівними 1. Після цього над двійковими розрядами виконується побитовое CRC-віднімання. Співвідношення розрядів не має значення, головне — це однакова розмірність і одиничні старші біти. У цьому випадку вважається, що віднімається більше віднімається, що тягне за собою включення 1 у приватне та виконання операції CRC-віднімання. Це і є прояв слабкого поняття розмірності. Кошик для сміття,показана на рис. 9.4 означає той факт, що приватне для процесу обчислення CRC-бітової послідовності не має ніякого значення. Реальні двійкові послідовності є результатом зчеплення часом величезної кількості окремих байтів (символів), утворюючи одне велике двійкове число, для представлення якого потрібно використовувати двійкові поліноми величезних ступенів. При цьому кожен біт у подібній послідовності довільної довжини представляється як коефіцієнт довгого полінома. Наприклад, для представлення 128-розрядного блоку необхідний поліном, що складається з 1024 доданків, а для 1024-бітного блоку необхідний поліном вже з 8192 доданками. У термінах поліноміальної арифметики двійкове число, сформоване в результаті подібного зчеплення складових блоку даних, називається поліномом даних

породжує поліпом G(x) — попередньо особливим чином обраний поліном, який ділиться вихідний поліном повідомлення;
поліном-приватне Q(x) - поліном, що вийшов як приватний від поділу поліномів D(x)/G(x);
поліном-залишок R(x) - поліном, що вийшов як залишок від поділу поліномів D(x)/G(x).

Між переліченими поліномами існують такі відносини: D(x)=Q(x)xG(x)+R(x), Q(x)=(D(x)-R(x))/G(x) . Ці співвідношення призводять до наступних основоположних для подальшого розгляду тез:

операція поділу двох двійкових поліномів D(x)/G(x), де G(x)*0, дає як результат поліном-приватне Q(x) і поліном-залишок R(x), що задовольняють умовам: D(x) =Q(x)xG(x)+R(x);
залишок від поділу двох поліномів R(x) є двійковим числом, яке після віднімання з D(x) дає в результаті ще один поліном, що ділиться без залишку на G(x); що виходить в результаті цьогоділення приватне Q(x) відкидається через непотрібність, а поліном-залишок R(x) називають CRC (Cyclic Redundancy Code).

З наведеного вище описи загальної схеми обчислення CRC виникає низка питань: що є цей магічний дільник G(x), який його розмір? Вибір полінома G(x), що породжує, — досить складне завдання. Перерахуємо деякі важливі властивості, які повинні враховуватись при цьому.

Число розрядів (кількість членів) у поліномі-залишку R(x) безпосередньо визначається довжиною самого породжуючого полінома G(x). Вибір G(x) довжиною п гарантує, що полином-залишок від розподілу R(x) матиме розрядність трохи більше, ніж п-1. Це випливає із загальної властивості операції поділу, яка передбачає, що залишок від поділу повинен бути меншим від дільника.
Що породжує поліном G(x) має бути поліноміально простим. Це означає його неподільність націло на поліноми зі значенням у діапазоні від 2 до самого себе.
Здатність породжує полінома G(x) до виявлення помилок, специфічних передачі даних каналами зв'язку. Це такі помилки, як помилки в одному, двох, непарному кількості бітів, а також помилки блоку бітів. Вище ми зазначали, що простіші методи виявлення помилок передачі не здатні виявити з достатньою мірою ймовірності більшість таких типів помилок.

Для більшості алгоритмів обчислення CRC значення полінома, що породжує, відомо заздалегідь і, більше того, затверджено відповідними стандартами. Тому програмісту без особливої потреби не варто втрачати часу і сил на винахід нового значення полінома, що породжує G(x). Наведемо значення деяких широко відомих поліномів, які використовуються практично.

х'6 + х12 + х5 + х ° - поліном 1021h, що використовується в протоколі XMODEMта похідних від нього протоколах передачі даних. Він стандартизований у специфікації V.41 МККТТ «Кодонезалежна система контролю помилок». Ш х16 + х5 + х2 + х ° - поліном 8005h, що використовується в протоколі двійкової синхронної передачі фірми IBM. Він також стандартизований у додатку А «Процедура корекції помилок кінцевого обладнання лінії з використанням асинхронно-синхронного перетворення» до стандарту V.42 МККТТ. Цей поліном широко відомий як поліном, що використовується в алгоритмі обчислення CRC - CRC16.
x32+x26+x23+x22+x16+x12+x"+xlo+xs+x7+x5+x4+x2+x1+x0 - поліном 04clldb7h, який використовується в алгоритмі обчислення CRC - CRC32 і також стандартизований у стандарті V.42 МККТТ Цей поліном, зокрема, використовується в технології локальних обчислювальних мереж Ethernet, необхідно зазначити, що обчислення за алгоритмом CRC32 часто проводять і з іншим поліномом: 0edb88320h:
x32+x31+x30+x29+x27+x26+x24+x23+x21+x20+ х19+х15+х9+х8+х5. Останній поліном використовують різноманітні архіватори. Поліном 0edb88320h - це дзеркальне відображення полінома 04clldb7h.

Насамкінець зазначимо, чому вигідно збільшувати число розрядів CRC. Вище вже було зазначено, що алгоритм обчислення CRC за своєю суттю є одним із можливих (і непоганих) алгоритмів хешування. Розрядність полінома G(x) 16 біт, що породжує, забезпечує до 65 535 значень хеш-функції. Збільшення розрядності полінома G(x) до 32 бітів призводить до розширення набору значень хеш-функції вже до 4 294 967 295. з нуля). Наприклад, для полінома 1011 з наведеного вище прикладу (див. рис. 9.4) ступінь дорівнює 3.висновків відзначимо, що CRC-арифметика відрізняється від двійковою відсутністю переносів/позик, а CRC-віднімання та додавання виконуються за тими самими правилами, що і команда асемблера XOR, що і обумовлює її важливу роль при обчисленні значень CRC.