Циклічний надлишковий код: відмінності між версіями
| [перевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Shynkar (обговорення | внесок) |
|||
Рядок 1:
'''Циклі́чний надлишко́вий код''' ({{lang-en|Cyclic redundancy check}}, CRC) — алгоритм обчислення [[Контрольна сума|контрольної суми]], призначений для [[Виявлення і виправлення помилок|перевірки цілісності даних]]. CRC є практичним додатком завадостійкого [[кодування]], заснованому на певних математичних властивостях [[Циклічний код|циклічного коду]].
== Введення ==
Поняття [[Циклічний код|циклічні коди]] достатньо широке. У англомовній літературі CRC розшифровується двояко в залежності від контексту: ''Cyclic Redundancy Code'' або ''Cyclic Redundancy Check.'' Під першою розшифровкою розуміють математичний феномен циклічних кодів, під другою — конкретне застосування цього феномену як [[Геш-функція|геш-функції]].
== Завадостійке кодування ==
Рядок 12 ⟶ 15:
При передачі пакетів по реальному каналу, зрозуміло, можуть виникнути спотворення вихідної інформації внаслідок різних зовнішніх впливів: електричних наводок, поганих погодних умов і багатьох інших. Сутність методики в тому, що при хороших характеристиках [[Хеш-функція|хеш-функції]] в переважній кількості випадків помилка в повідомленні призведе до зміни обчисленого на прийомі значення CRC. Якщо вихідна і обчислена суми не рівні між собою, приймається рішення про недостовірність отриманих даних, і можна запитати повторну передачу пакета.
== Математичне описання ==
Алгоритм CRC базується на властивості [[ділення з остачею]] двійкових [[Многочлен|многочленів]], тобто многочленів над [[Скінченне поле|скінченним полем]] <math>GF(2)</math>. Значення CRC є по суті остачею від ділення многочлена, відповідного вхідним даним, на деякий фіксований породжуючий многочлен.
Кожній послідовності бітів <math>a_0, a_1, ..., a_{N-1}</math> взаємно однозначно зіставляється двійковий многочлен <math>\textstyle \sum_{n=0}^{N-1} \displaystyle a_nx^n</math>, послідовність коефіцієнтів якого представляє собою початкову послідовність. Наприклад, послідовність бітів 1011010 відповідає многочлену:<blockquote><math>P(x) = 1\cdot x^6 + 0\cdot x^5 + 1\cdot x^4 + 1\cdot x^3 + 0\cdot x^2 + 1\cdot x^1 + 0\cdot x^0 =
x^6 + x^4 + x^3 + x^1.</math></blockquote>Кількість різних многочленів степені меншої <math>N</math> дорівнює <math>2^N</math>, що збігається з числом всіх двійкових послідовностей довжини <math>N</math>.
Значення контрольної суми в алгоритмі з породжуючим многочленом <math>G(x)</math> степені <math>N</math> задається як бітова послідовність довжини <math>N</math>, яка представляє многочлен <math>R(x)</math>, отриманий в остачі при діленні многочлена <math>P(x)</math>, який представляє вхідний потік біт, на многочлен <math>G(x)</math>:<blockquote><math>R(x) = P(x)\cdot x^N\bmod\ G(x) </math></blockquote>де
: <math>R(x)</math> — многочлен, який представляє значення CRC;
: <math>P(x)</math>— многочлен, коефіцієнти якого представляють вхідні дані;
: <math>G(x)</math> — породжуючий многочлен;
: <math>N</math> — степінь породжуючого многочлена.
Множення <math>x^N</math> здійснюється приписуванням нульових бітів до вхідної послідовності, що покращує якість гешування для коротких вхідних послідовностей.
При діленні з остачею початкового многочлена на породжуючий многочлен <math>G(x)</math> степені <math>N</math> можна отримати <math>2^N</math> різних остач від ділення. <math>G(x)</math> найчастіше є [[Незвідний многочлен|незвідним многочленом]]. Зазвичай його підбирають відповідно до вимог до геш-функції у контексті кожного конкретного застосування. Проте, існує багато стандартизованих породжуючих многочленів, обладаючих гарними математичними та кореляційними властивостями (мінімальне число [[Колізія хеш-функції|колізій]], простота обчислення), деякі з котрих приведені нижче.
== Обчислення CRC ==
=== Параметри алгоритму ===
== Див. також ==
| |||