Cyclic redundancy check

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

CRC е код за детекција на грешки кој најчесто се користи во дигиталните мрежи и уредите за складирање за да се спречи грешка во необработените податоци. На блоковите од податоци кои поминуваат низ овој систем им се прилепува неколку битови за проверка, базирани на остатокот при полиномното делењето на бинарно преставениот податок, доколку овие вредности не се совпаѓаат постојат постапки за корекција.

CRC е наречен така бидејќи проверката на вредноста (верификација на податоците) се врши редундантно (се шири без дополнителни информации) и алгоритамот е базиран на циклични кодови. CRC се доста популарни бидејќи се лесни за имплементација во бинарен хардвер, лесни за математичка анализа, а особено добри за детекција на грешки предизвикани од шумот во преносните канали. Бидејки вредноста за проверка има фиксна должина, функцијата која ја генерира истата понекогаш се користи како хеш функција. CRC била измислена од страна на В Весли Петерсон во 1961 година, а 32-битна CRC функција на Ethernet и многу други стандарди е дело на неколку истражувачи и беше објавенa во текот на 1975 година.

Вовед[уреди]

CRC кодот е заснован на теоријата на циклични кодови за исправување грешки.Употребата на системските циклични кодови, кои енкодираат пораки со додавање на вредност за проверка со фиксна должина, со цел да се детектираат грешките во комуникациските мрежи, беше прво предложена од В. Весли Петерсон во текот на 1961 година. Цикличните кодови не само што се лесни за имплементација тие исто така се добро прилагодени за откривање на burst errors, поседователна секвенца од грешно пренесени симболи во пораката. Ова е важно затоа што burst errors се чести грешки во преносот во многу канали за комуникација, вклучувајќи магнетни и оптички уреди за складирање. Обично n-битен CRC код применет на блок податоци со произволна должина ќе детектира било каква единечна грешка не подолга од n битови и ќе детектира фракција 1-2-n од сите подолги error burst. Спецификацијата на овој CRC код побарува и дефинирање на така наречениот полином генератор. Полиномот генериран од овој полином генератор наликува на делител во полиномното делење каде количникот се отфрла, а како главен резултат се зема остатокот при делењето. Должината на остатокот е секогаш помал од должината на полиномот генериран од полином генераторот, при што одредува колку долг може да биде резултатот. Во пракса, сите го употребуваат GF( Galois field) полето. Тоа е поле од два елемента, 1или 0, за совпаѓање со компјутерската архитектура. CRC се нарекува n-битен CRC кога вредноста за проверка е n битови. За дадено n, повеќе CRC се возможни, секој со различен полином. Таков полином има највисок степен n што значи дека има n + 1 членови.Со други зборови , полиномот има должина од n+1, и неговото енкодирање побарува n+1 битови.Имајте на ум дека повеќето целобројни кодирања го испуштаат MSB или LSB битот. CRC и придружните полиноми обично имаат име во форма на CRC-n-XXX според табелата подолу. Наједноставниот код за детекција на грешки, со бит за парност, е всушност тривиален еднобитен CRC , кое користи полином генератор X+1(два члена), и има име CRC-1.

Апликација[уреди]

CRC-enabled уредот пресметува кратка, секвенца од битови со фиксна должина, позната како вредност за проверка или неправилен CRC, за секој блок на податоци кој треба да биде пратен или зачуван и прилепен на податокот, формирајќи кодирачки збор. Кога кодираниот збор ќе биде примен или прочитан, уредот или ја споредува неговата вредност за проверка со штотуку пресметаната вредност од податочниот блок, или еквивалентно, врши CRC на целокупниот кодиран збор и ја споредува добиената вредност за проверка со очекуваниот остаток. Ако проверката не се совпаѓа, тогаш блокот содржи грешка. Уредот може да превземе акција за корекција, како повторно вчитување на блокот или барање за повторно праќање. Во спротивно, податокот е примен без грешка (иако, со некоја мала веројатност, податокот може да содржи грешка).

CRC и податочен интегритет[уреди]

CRC се специјално дизајнирани за заштита од најчестите видови на грешки во комуникациските канали, каде што тие можат да обезбедат брза и разумно гаранција за интегритетот на пратената порака. Сепак, тие не се погодни за заштита против намерно менување на податоци. Прво,не постои проверка, напаѓач може да ја менува пораката и повторно да го преработи CRC и притоа замената да не биде откриена. Кога се зачувуваат заедно со податоците, CRC и криптографските хеш функции сами по себе не се заштитуваат од намерна промена на податоците. Било која апликација која побарува заштита против ваквите напади мора да користи криптографски афтентикациски механизам, како порака со афтентикациски кодиви или дигитални потписи( кои се најчесто базирани на криптографски хеш функции). Трето, CRC е линеарна функција со равенка како како резултат, дури ако CRC е енкриптирана со stream шифра (или како блок од шифри кои ефикасно преминуваат во шифри, како што се OFB или CFB), и пораката и придружниот CRC може да бидат манипулирани без знаење на енкриптирачкиот клуч. Тоа беше една од добро познатите недостатци на Wired Equivalent Privacy (WEP) протоколот.

Пресметка на CRC[уреди]

За да се пресмета n-битен бинарен CRC, битовите го претставуваат влезот во редицата и позицијата на n+1 бит го претставува CRC делителот наречен ( полиномен ).

Нека е дадена следната порака за да биде енкодирана:

11010011101100

Прво на пораката се прилепуваат онолку нули колку што највисокиот степен во полиномот генериран од полином генераторот.Следниот пример е со пресметување на 3-битен CRC ( највисокиот степен во полиномот генератор е 3).

11010011101100 000

1011

01100011101100 000

Ако влезниот бит над најлевиот бит на делителот е 0, не се прави ништо. Ако влезниот бит над најлевиот бит на делителот е 1, тогаш се добива нов деленик како резултат на XOR од стариот деленик и полиномот генератор. Делителот се поместува за 1-бит десно, и постапката се повторува се додека делителот не го достигне крајот на деленикот. Во прилог е дадена целата постапка :

11010011101100 000

1011

01100011101100 000

1011

00111011101100 000

 1011

00010111101100 000

  1011

00000001101100 000

   1011

00000000110100 000

     1011

00000000011000 000

        1011

00000000001110 000

         1011

00000000000101 000

          101 1

00000000000000 100

Кога оваа постапка ќе заврши единствени ненулти битови во редицата се последните n-битови. Овие n-битови се остатокот од делењето и исто така се вредности на CRC функцијата ( доколку избраната CRC спрецификација не побарува други постпроцедури).

Валидноста на пристигнатата порака може лесно да биде проверена со повторување на гореопишаната постапка, овој пат со додавање на вредноста за проверка наместо нули, при оваа постапка осатокот треба да биде 0 ако не се детектирани грешки. 11010011101100 100

1011

01100011101100 100

1011      
       

00111011101100 100

00000000001110 100

         1011

00000000000101 100

          101 1

0 <-reminder

Математика на CRC[уреди]

Математичката анализа на овој деленик како процес открива како да се избере деленик кој гарантира добра детекција на грешки. Во оваа анализа, броевите во низата битови се кофициенти на полином со променлива X, коефициенти коие се елементи на GF(Galois field). Множеството од бинарни полиноми е циклично односто се разгледува како прстен. Изборот на полином генератор е најважниот дел од имплементацијата на CRC алгоритамот. Полиномот мора да биде изберен така, да ја максимизира способноста за детекција на грешка , притоа минимизирајќи ја веројатноста за појава на колизии (судири). Најважен атрибут на полиномот е неговата должина (највисокиот степен плус 1 член) бидејќи директно влијае на должината на пресметана вредност за проверка.

Најчести должини за полиномот се:

· 9 bits (CRC-8) · 17 bits (CRC-16) · 33 bits (CRC-32) · 65 bits (CRC-64)


Дизајнот на CRC полиномот зависи од максималната целокупна должина на блокот за да биде заштитен (податоци + CRC битови), посакуваната функција за заштита од грешки и видот на ресурсите за имплементација на CRC. Честа заблуда е дека “најдобрите” CRC полиноми се добиени или од иредуцибилни полиноми или од иредуцибилни полиноми со фактор X+1, кои му даваат способност на самиот код да открие грешки кои влијаат на непарен број на битови. Во пракса, сите фактори опишани погоре треба да бидат земени во предвид при селекција на полиномот. Како и да е, избирањето на иредуцибилен полином може да резултира со пропуштање на грешки што се должи на тоа што некои прстени имаат нула делители.

Предноста од избирање на примитивен полином како генератор за CRC код е тоа што резултантниот код има максимална должина на блок. Ако r е степенот на примитивнот полином генератор, тогаш максималната блок должина е 2 ^ {r} – 1 , и придружниот бит има можност да детектира единечна или двојна грешка. Оваа ситуација може да се подобри. Ако ние користиме генератор полином g(x) = p(x)(1 + x), каде p(x) е примитивен полином со степен r-1, тогаш максималната блок должина е 2^{r - 1} – 1, и кодот е способен за детектирање на единечна, двојна или тројна грешка.

Полиномот g(x) кој дозволува друга факторизација може да биде изберен со цел да ја балансира максималната блок должина со посакувана моќност за детекција на грешки. BCH кодовите се моќна класа на такви полиноми. Тие ги вклучуваат двата примери опишани погоре. Без оглед на иредуцибилноста на полином генераторот со степен r, ако тој вклучува “ +1 “ член, кодот ќе биде способен за детекција на грешни шаблони ограничени во прозорец од r последователни битови. Овие шаблони се наречени "error bursts".

Спецификација на CRC[уреди]

Концептот на CRC како код за детекција на крешки станува комплициран кога имплементаторите или стандардните комисии почнуваат да го користат во практичните системи. Во прилог се дадени некои од компликациите:

· Понекогаш самата имплементација предефинира фиксна битова шема која треба да биде проверена. Тоа е корисно кога периодичните грешки може да внесат нули на почетокот на пораката во спротивно ке ја остават вредноста за проверка на промената.

· Редослед на битови: Некои шеми го разгледуваат подредувањето на битови најпрво, што за време на делењето значи најлево, што е обратно од нашето сфаќање за подредување по големина. Оваа конвенција добива смисла која сериските преноси се CRC проверени во хардерот, бидејќи некои широко распространети сериски преноси ги пренесуваат бајтите по принципот на “најмалку знајачниот бит прво”.

· Редослед на бајти: Со повеќе кратните CRC, може да биде збонувачки дали прво пренесениот бајт е најмалку значајниот или најмногу значајниот бајт. На пример некои 16 битни шеми ги менуваат бајтите за проверка на вредноста.

· Пропуст при најзначајниот бит во полиномот-делител: Се додека најзначајниот бит е секогаш 1, n-битниот CRC мора да биде да биде дефиниран со n+1 битен деленик. Некои автори сметаат дека не е потребно да се спомне најзначајниот бит во деленикот.


Овие компликации значат дека постојат три начини да се престави полиномот како цел број: првите две се пресликување во бинарни броеви, а третиот е број пронајден во весниците на Koopman. Полиномот x^4 + x + 1 може да биде преведен како:

*0x3 = 0b0011, x4+x3+0x2+1x1+1x0
*0xC = 0b1100, 1x0+1x1+0x2+0x3+x4
*0x9 = 0b1001, 1x4+0x3+0x2+1x1+x0

Највеќе користени стандарди за CRC[уреди]

Голем број на циклични кодови за проверка беа инкорпорирани во некои технички стандарди. Во никој случај тоа не значи дека има еден алгоритам, или еден на секој степен. Koopman и Chakravarty препорачувааат избирање на полином во согласност со барањата на апликацијата и очекуваната должина на пораката. Бројот на различни CRC во пракса ги збунува програмерите. Постојат три полиномни репорти за CRC-12 , шеснаесет конфликти дефиниции за CRC-16, и шест за CRC-32.

Полиномите кои се најчесто користени не се најефикасните. Помеѓу 1993 и 2004, Koopman, Castagnoli и други специјалисти за полиноми до 16-бита, и со 24 и 32-бита , пронајдоа примери со многу подобри перформанси. Особено iSCSI и SCTP присвоија едно од овие откритија, CRC-32C (Castagnoli) polynomial.

Табелата подолу ги прикажува само полиномите на различни алгоритми во употреба. Вариации на одредени протоколи може да се наменети за прединверзија, пост-инверзија и обратен бит опишан погоре. На пример, CRC32 користен во Gzip и Bzip2 го користат истиот полином , но Bzip2 воведува обратен редослед на битовите, а Gzip не.

CRC во неслободните протоколи може да користи не тривијална почетна вредност но тоа не додава криптографски сила на алгоритам. Непознат код за детекција може да биде карактеризиран како CRC , и како таков може целосно да се искористи.