चक्रीय अतिरेक जांच की गणना

चक्रीय अतिरेक जांच की गणना चक्रीय अतिरेक जांच के गणित के गणित से ली गई है|बहुपद विभाजन, मोडुलो दो। व्यवहार में, यह बाइनरी कोड संदेश स्ट्रिंग के लंबे विभाजन जैसा दिखता है, जिसमें जेनरेटर बहुपद स्ट्रिंग द्वारा निश्चित संख्या में शून्य जोड़े जाते हैं, सिवाय इसके कि एकमात्र ऑपरेशन घटाव की जगह लेते हैं। इस प्रकार का विभाजन एक संशोधित शिफ्ट का रजिस्टर द्वारा हार्डवेयर में कुशलतापूर्वक किया जाता है, और सॉफ्टवेयर में समतुल्य कलन विधि की एक श्रृंखला द्वारा, गणित के करीब सरल कोड से शुरू होकर और तेज़ (और यकीनन अधिक अस्पष्ट कोड) होता जा रहा है) बाइट-वार समानता (कंप्यूटिंग) और स्पेस-टाइम ट्रेडऑफ़ के माध्यम से।

8-बिट चक्रीय अतिरेक जांच उत्पन्न करने का उदाहरण। जनरेटर एक गैलोइस-प्रकार का लीनियर-फीडबैक शिफ्ट रजिस्टर है जिसमें जनरेटर बहुपद में x की शक्तियों (सफेद संख्या) के अनुसार XOR गेट लगाए गए हैं। संदेश स्ट्रीम किसी भी लंबाई की हो सकती है. इसे रजिस्टर के माध्यम से स्थानांतरित करने के बाद, 8 शून्य के बाद, रजिस्टर में परिणाम चेकसम है।

चेकसम के साथ प्राप्त डेटा की जाँच करना। प्राप्त संदेश को उसी रजिस्टर के माध्यम से स्थानांतरित किया जाता है जैसा कि जनरेटर में उपयोग किया जाता है, लेकिन प्राप्त चेकसम शून्य के बजाय इसके साथ जुड़ा होता है। सही डेटा से सर्व-शून्य परिणाम प्राप्त होता है; संदेश या चेकसम में एक दूषित बिट एक अलग परिणाम देगा, चेतावनी देगा कि कोई त्रुटि हुई है।

विभिन्न सीआरसी मानक एक प्रारंभिक शिफ्ट रजिस्टर मान, एक अंतिम एक्सक्लूसिव-या चरण और, सबसे गंभीर रूप से, थोड़ा ऑर्डरिंग (endianness) निर्दिष्ट करके बहुपद विभाजन एल्गोरिदम का विस्तार करते हैं। परिणामस्वरूप, व्यवहार में देखा जाने वाला कोड शुद्ध विभाजन से भ्रामक रूप से भटक जाता है,और रजिस्टर बाएँ या दाएँ शिफ्ट हो सकता है।

उदाहरण

हार्डवेयर में बहुपद विभाजन को लागू करने के एक उदाहरण के रूप में, मान लीजिए कि हम ASCII वर्ण W से बने 8-बिट संदेश के 8-बिट CRC की गणना करने का प्रयास कर रहे हैं, जो बाइनरी 01010111 है₂, दशमलव 87₁₀, या हेक्साडेसिमल 57₁₆. उदाहरण के लिए, हम सीआरसी-8-एटीएम (सीआरसी-आधारित फ़्रेमिंग) बहुपद का उपयोग करेंगे $x^{8}+x^{2}+x+1$. प्रेषित पहली बिट लिखना (उच्चतम शक्ति का गुणांक $x$) बाईं ओर, यह 9-बिट स्ट्रिंग 100000111 से मेल खाता है।

बाइट मान 57₁₆ उपयोग किए गए बिट ऑर्डरिंग कन्वेंशन के आधार पर, दो अलग-अलग ऑर्डर में प्रसारित किया जा सकता है। प्रत्येक एक अलग संदेश बहुपद उत्पन्न करता है $M(x)$. एमएसबिट-प्रथम, यह है $x^{6}+x^{4}+x^{2}+x+1$ = 01010111, जबकि lsbit-first, यह है $x^{7}+x^{6}+x^{5}+x^{3}+x$ = 11101010. फिर इन्हें इससे गुणा किया जा सकता है $x^{8}$ दो 16-बिट संदेश बहुपद बनाने के लिए $x^{8}M(x)$.

फिर शेषफल की गणना में जेनरेटर बहुपद के गुणजों को घटाना शामिल होता है $G(x)$. यह बिल्कुल दशमलव लंबे विभाजन की तरह है, लेकिन इससे भी सरल है क्योंकि प्रत्येक चरण में एकमात्र संभावित गुणज 0 और 1 हैं, और ऊपरी अंकों को कम करने के बजाय अनंत से घटाव (अंकगणित) किया जाता है। चूँकि हमें भागफल की परवाह नहीं है, इसलिए इसे रिकॉर्ड करने की कोई आवश्यकता नहीं है।

Most-significant bit first

Least-significant bit first

0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0

1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 = 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0

ध्यान दें कि प्रत्येक घटाव के बाद, बिट्स को तीन समूहों में विभाजित किया जाता है: शुरुआत में, एक समूह जो सभी शून्य है; अंत में, एक समूह जो मूल से अपरिवर्तित है; और बीच में एक नीला छायांकित समूह जो दिलचस्प है। दिलचस्प समूह 8 बिट लंबा है, जो बहुपद की डिग्री से मेल खाता है। प्रत्येक चरण में, शून्य समूह को एक बिट लंबा बनाने के लिए बहुपद के उपयुक्त गुणज को घटाया जाता है, और अपरिवर्तित समूह एक बिट छोटा हो जाता है, जब तक कि केवल अंतिम शेष न बचा हो।

एमएसबिट-प्रथम उदाहरण में, शेष बहुपद है $x^{7}+x^{5}+x$. इस परंपरा का उपयोग करके हेक्साडेसिमल संख्या में कनवर्ट करना कि x की उच्चतम शक्ति एमएसबिट है; यह A2 है₁₆. lsbit-प्रथम में शेषफल है $x^{7}+x^{4}+x^{3}$. इस परिपाटी का उपयोग करके हेक्साडेसिमल में कनवर्ट करना कि x की उच्चतम शक्ति lsbit है, यह 19 है₁₆.

कार्यान्वयन

प्रत्येक चरण पर पूरा संदेश लिखना, जैसा कि ऊपर दिए गए उदाहरण में किया गया है, बहुत कठिन है। कुशल कार्यान्वयन एक का उपयोग करें $n$-बिट शिफ्ट रजिस्टर केवल दिलचस्प बिट्स को रखने के लिए। बहुपद को इससे गुणा करना $x$ रजिस्टर को एक स्थान से स्थानांतरित करने के बराबर है, क्योंकि गुणांक मूल्य में नहीं बदलते हैं बल्कि केवल बहुपद के अगले पद तक बढ़ते हैं।

यहां एन-बिट सीआरसी की गणना के लिए कुछ छद्मकोड का पहला मसौदा है। यह बहुपदों के लिए एक काल्पनिक वस्तु संरचना का उपयोग करता है, जहाँ x एक पूर्णांक चर नहीं है, बल्कि एक कंस्ट्रक्टर (कंप्यूटर विज्ञान) एक बहुपद वस्तु (कंप्यूटर विज्ञान) उत्पन्न करता है जिसे जोड़ा, गुणा और घातांकित किया जा सकता है। को xor दो बहुपदों को जोड़ना है, मॉड्यूलो दो; अर्थात्, दोनों बहुपदों से प्रत्येक मिलान पद के गुणांकों को अलग करना।

फ़ंक्शन सीआरसी(बिट ऐरे बिटस्ट्रिंग[1..लेन], इंट लेन) {
    शेषबहुपद := बहुपदफार्म(बिटस्ट्रिंग[1..n]) //संदेश का पहला एन बिट्स
    // एक लोकप्रिय संस्करण यहां शेषबहुपद का पूरक है; देखना § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x0   // Define bitString[k]=0 for k>len
        if coefficient of xn of remainderPolynomial = 1 {
            remainderPolynomial := remainderPolynomial xor generatorPolynomial
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

कोड खंड 1: सरल बहुपद विभाजन

ध्यान दें कि यह उदाहरण कोड बाइट्स का उपयोग न करके बिट-ऑर्डरिंग कन्वेंशन को निर्दिष्ट करने की आवश्यकता से बचाता है; इनपुट bitString पहले से ही एक बिट ऐरे के रूप में है, और remainderPolynomial बहुपद संक्रियाओं के संदर्भ में हेरफेर किया जाता है; से गुणा $x$ बाएँ या दाएँ बदलाव, और का जोड़ हो सकता है bitString[i+n] को किया जाता है $x^{0}$ गुणांक, जो रजिस्टर का दायां या बायां छोर हो सकता है।

इस कोड के दो नुकसान हैं. सबसे पहले, इसे रखने के लिए वास्तव में n+1-बिट रजिस्टर की आवश्यकता होती है remainderPolynomial वैसा ही किया $x^{n}$ गुणांक का परीक्षण किया जा सकता है। इससे भी महत्वपूर्ण बात यह है कि इसकी आवश्यकता है bitString n शून्य बिट्स के साथ गद्देदार होना।

पहली समस्या का परीक्षण करके हल किया जा सकता है $x^{n-1}$ का गुणांक remainderPolynomial इससे पहले कि इसे गुणा किया जाए $x$.

दूसरी समस्या को अंतिम n पुनरावृत्तियों को अलग ढंग से करके हल किया जा सकता है, लेकिन एक अधिक सूक्ष्म अनुकूलन है जिसका उपयोग हार्डवेयर और सॉफ्टवेयर दोनों कार्यान्वयनों में सार्वभौमिक रूप से किया जाता है।

क्योंकि संदेश से जनरेटर बहुपद को घटाने के लिए उपयोग किया जाने वाला XOR ऑपरेशन क्रमविनिमेय और साहचर्य है, इससे कोई फर्क नहीं पड़ता कि विभिन्न इनपुट किस क्रम में संयुक्त हैं remainderPolynomial. और विशेष रूप से, का एक दिया गया बिट bitString में जोड़ने की आवश्यकता नहीं है remainderPolynomial अंतिम क्षण तक जब यह निर्धारित करने के लिए परीक्षण किया जाता है कि क्या करना है xor साथ generatorPolynomial.

इससे प्रीलोड करने की आवश्यकता समाप्त हो जाती है remainderPolynomial संदेश के पहले n बिट्स के साथ:

'फ़ंक्शन' सीआरसी (बिट सरणी बिटस्ट्रिंग [1..लेन], इंट लेन) {
    शेषबहुपद := 0
    // एक लोकप्रिय संस्करण यहां शेष बहुपद का पूरक है; देखना § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial xor (bitstring[i] * xn−1)
        if (coefficient of xn−1 of remainderPolynomial) = 1 {
            remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
        } else {
            remainderPolynomial := (remainderPolynomial * x)
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

कोड खंड 2: विलंबित संदेश XORing के साथ बहुपद विभाजन

यह मानक बिट-ए-टाइम हार्डवेयर सीआरसी कार्यान्वयन है, और अध्ययन के योग्य है; एक बार जब आप समझ जाते हैं कि यह पहले संस्करण के समान परिणाम की गणना क्यों करता है, तो शेष अनुकूलन काफी सरल हैं। अगर remainderPolynomial केवल n बिट लंबा है, तो $x^{n}$ इसके और के गुणांक generatorPolynomial बस त्याग दिए जाते हैं. यही कारण है कि आप आमतौर पर सीआरसी बहुपदों को बाइनरी में लिखे हुए देखेंगे, जिसमें प्रमुख गुणांक हटा दिया जाएगा।

सॉफ़्टवेयर में, यह नोट करना सुविधाजनक है कि कोई भी देरी कर सकता है xor प्रत्येक बिट का अंतिम क्षण तक, इसे पहले करना भी संभव है। इसे निष्पादित करना आमतौर पर सुविधाजनक होता है xor एक समय में एक बाइट, यहां तक ​​कि इस तरह से एक-एक बार कार्यान्वयन में भी:

फ़ंक्शन सीआरसी(बाइट ऐरे स्ट्रिंग[1..लेन], इंट लेन) {
    शेषबहुपद := 0
    // एक लोकप्रिय संस्करण यहां शेषबहुपद का पूरक है; देखना § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial xor polynomialForm(string[i]) * xn−8
        for j from 1 to 8 {    // Assuming 8 bits per byte
            if coefficient of xn−1 of remainderPolynomial = 1 {
                remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
            } else {
                remainderPolynomial := (remainderPolynomial * x)
            }
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

कोड खंड 3: बाइटवाइज संदेश XORing के साथ बहुपद विभाजन

यह आम तौर पर सबसे कॉम्पैक्ट सॉफ़्टवेयर कार्यान्वयन है, जिसका उपयोग माइक्रोकंट्रोलर्स में तब किया जाता है जब स्पेस प्रीमियम ओवर स्पीड पर होता है।

बिट ऑर्डरिंग (एंडियननेस)

जब बिट-सीरियल आर्किटेक्चर हार्डवेयर (कंप्यूटर) में लागू किया जाता है, तो जनरेटर बहुपद विशिष्ट रूप से बिट असाइनमेंट का वर्णन करता है; प्रेषित पहला बिट हमेशा उच्चतम शक्ति का गुणांक होता है $x$, और आखरी बात $n$ प्रेषित बिट्स सीआरसी शेष हैं $R(x)$, के गुणांक से प्रारंभ करते हुए $x^{n-1}$ और के गुणांक के साथ समाप्त होता है $x^{0}$, अर्थात् 1 का गुणांक।

हालाँकि, जब बिट्स को एक समय में एक बाइट संसाधित किया जाता है, जैसे कि समानांतर ट्रांसमिशन का उपयोग करते समय, 8बी/10बी एन्कोडिंग या आरएस-232-शैली एसिंक्रोनस सीरियल संचार के रूप में बाइट फ़्रेमिंग, या सॉफ़्टवेयर में सीआरसी लागू करते समय, डेटा के बिट ऑर्डरिंग (एंडियननेस) को निर्दिष्ट करना आवश्यक है; प्रत्येक बाइट में कौन सा बिट पहले माना जाता है और उच्च शक्ति का गुणांक होगा $x$.

यदि डेटा धारावाहिक संचार के लिए नियत है, तो बिट ऑर्डर का उपयोग करना सबसे अच्छा है जिससे डेटा अंततः भेजा जाएगा। ऐसा इसलिए है क्योंकि सीआरसी की विस्फोट त्रुटियों का पता लगाने की क्षमता संदेश बहुपद में निकटता पर आधारित है $M(x)$; यदि आसन्न बहुपद शब्दों को क्रमिक रूप से प्रसारित नहीं किया जाता है, तो बिट्स के पुनर्व्यवस्था के कारण एक लंबाई की भौतिक त्रुटि विस्फोट को लंबे विस्फोट के रूप में देखा जा सकता है।

उदाहरण के लिए, आईईईई 802 (ईथरनेट) और आरएस-232 (आनुक्रमिक द्वार ) दोनों मानक कम से कम महत्वपूर्ण बिट पहले (लिटिल-एंडियन) ट्रांसमिशन को निर्दिष्ट करते हैं, इसलिए ऐसे लिंक पर भेजे गए डेटा की सुरक्षा के लिए एक सॉफ्टवेयर सीआरसी कार्यान्वयन को प्रत्येक बाइट में कम से कम महत्वपूर्ण बिट्स को उच्चतम शक्तियों के गुणांक में मैप करना चाहिए। $x$. दूसरी ओर, फ्लॉपी डिस्क और अधिकांश हार्ड ड्राइव पहले प्रत्येक बाइट का सबसे महत्वपूर्ण बिट लिखते हैं।

lsbit-first CRC को सॉफ़्टवेयर में लागू करना थोड़ा आसान है, इसलिए इसे कुछ हद तक सामान्य रूप से देखा जाता है, लेकिन कई प्रोग्रामर MSbit-first बिट ऑर्डर का पालन करना आसान पाते हैं। इस प्रकार, उदाहरण के लिए, एक्सएमओडीईएम-सीआरसी एक्सटेंशन, सॉफ्टवेयर में सीआरसी का प्रारंभिक उपयोग, एमएसबिट-प्रथम सीआरसी का उपयोग करता है।

अब तक, स्यूडोकोड ने स्यूडोकोड में बदलावों को गुणन के रूप में वर्णित करके बाइट्स के भीतर बिट्स के क्रम को निर्दिष्ट करने से परहेज किया है। $x$ और द्विआधारी से बहुपद रूप में स्पष्ट रूपांतरण लिखना। व्यवहार में, सीआरसी को एक विशेष बिट-ऑर्डरिंग कन्वेंशन का उपयोग करके एक मानक बाइनरी रजिस्टर में रखा जाता है। एमएसबिट-प्रथम रूप में, सबसे महत्वपूर्ण बाइनरी बिट्स पहले भेजे जाएंगे और इसलिए इसमें उच्च-क्रम बहुपद गुणांक होंगे, जबकि एलएसबिट-प्रथम रूप में, कम से कम महत्वपूर्ण बाइनरी बिट्स में उच्च-क्रम गुणांक होंगे। उपरोक्त छद्म कोड दोनों रूपों में लिखा जा सकता है। ठोसता के लिए, यह 16-बिट CRC-16-CCITT बहुपद का उपयोग करता है $x^{16}+x^{12}+x^{5}+1$:

// सबसे महत्वपूर्ण बिट पहले (बड़ा-एंडियन)
// x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021
'फ़ंक्शन' सीआरसी (बाइट सरणी स्ट्रिंग [1..लेन], इंट लेन) {
    रेम := 0
    // एक लोकप्रिय संस्करण यहाँ रेम को पूरक करता है
    'के लिए' मैं 'से' 1 'तक' लेन {
        रेम := रेम 'एक्सओआर' (स्ट्रिंग[आई] 'लेफ्टशिफ्ट' (एन-8)) // एन = 16 इस उदाहरण में
        'for' j 'from' 1 'to' 8 {// प्रति बाइट 8 बिट्स मानते हुए
            'यदि' रेम 'और' 0x8000 {// यदि सबसे बायां (सबसे महत्वपूर्ण) बिट सेट है
                रेम := (रेम 'लेफ्टशिफ्ट' 1) 'एक्सओआर' 0x1021
            } 'अन्य' {
                रेम := रेम 'लेफ्टशिफ्ट' 1
            }
            रेम := रेम 'और' 0xffff // शेष को 16 बिट्स तक ट्रिम करें
        }
    }
    // एक लोकप्रिय संस्करण यहाँ रेम को पूरक करता है
    'वापसी' रेम
}

'कोड खंड 4: शिफ्ट रजिस्टर आधारित प्रभाग, एमएसबी प्रथम'

// सबसे कम महत्वपूर्ण बिट पहले (लिटिल-एंडियन)
// x^16+x^12+x^5+1 = 1000 0100 0000 1000 (1) = 0x8408
'फ़ंक्शन' सीआरसी (बाइट सरणी स्ट्रिंग [1..लेन], इंट लेन) {
    रेम := 0
    // एक लोकप्रिय संस्करण यहाँ रेम को पूरक करता है
    'के लिए' मैं 'से' 1 'तक' लेन {
        रेम := रेम 'xor' स्ट्रिंग[i]
        'for' j 'from' 1 'to' 8 {// प्रति बाइट 8 बिट्स मानते हुए
            'अगर' रेम 'और' 0x0001 {// अगर सबसे दाहिना (सबसे महत्वपूर्ण) बिट सेट है
                रेम := (रेम 'राइटशिफ्ट' 1) 'एक्सओआर' 0x8408
            } 'अन्य' {
                रेम := रेम 'राइटशिफ्ट' 1
            }
        }
    }
    // एक लोकप्रिय संस्करण यहाँ रेम को पूरक करता है
    'वापसी' रेम
}

'कोड खंड 5: शिफ्ट रजिस्टर आधारित प्रभाग, एलएसबी प्रथम'

ध्यान दें कि lsbit-पहला फॉर्म शिफ्ट करने की आवश्यकता से बचाता है string[i] से पहले xor. किसी भी स्थिति में, सीआरसी के बाइट्स को उस क्रम में प्रसारित करना सुनिश्चित करें जो आपके चुने हुए बिट-ऑर्डरिंग सम्मेलन से मेल खाता हो।

मल्टी-बिट गणना

सरवटे एल्गोरिदम (एकल लुकअप तालिका)

एक अन्य सामान्य अनुकूलन उच्चतम क्रम गुणांक द्वारा अनुक्रमित लुकअप तालिका का उपयोग करता है rem प्रति पुनरावृत्ति एक से अधिक बिट लाभांश संसाधित करना। आमतौर पर, 256-एंट्री लुकअप टेबल का उपयोग किया जाता है, जो बाहरी लूप (ऊपर) की बॉडी को प्रतिस्थापित करता है i) साथ:

// एमएसबिट-प्रथम
रेम = (रेम लेफ्टशिफ्ट 8) xor big_endian_table[स्ट्रिंग[i] xor ((रेम के सबसे बाएं 8 बिट्स) राइटशिफ्ट (n-8))]
// एलएसबिट-प्रथम
रेम = (रेम राइटशिफ्ट 8) xor tiny_endian_table[string[i] xor (रेम के सबसे दाएँ 8 बिट्स)]

कोड खंड 6: तालिका आधारित विभाजन के कोर

सबसे आम तौर पर सामने आने वाले सीआरसी एल्गोरिदम में से एक को सीआरसी-32 के रूप में जाना जाता है, जिसका उपयोग (अन्य के अलावा) ईथरनेट, एफडीडीआई, ज़िप (फ़ाइल प्रारूप) और अन्य संग्रह प्रारूप, और पोर्टेबल नेटवर्क ग्राफिक्स छवि प्रारूप द्वारा किया जाता है। इसके बहुपद को msbit-first को 0x04C11DB7, या lsbit-first को 0xEDB88320 के रूप में लिखा जा सकता है। पोर्टेबल नेटवर्क ग्राफ़िक्स पर W3C वेबपेज में CRC-32 के C में एक संक्षिप्त और सरल तालिका-संचालित कार्यान्वयन के साथ एक परिशिष्ट शामिल है। आप देखेंगे कि कोड यहां प्रस्तुत lsbit-first byte-at-a-time छद्मकोड से मेल खाता है, और तालिका बिट-एट-ए-टाइम कोड का उपयोग करके बनाई गई है।

256-प्रविष्टि तालिका का उपयोग करना आमतौर पर सबसे सुविधाजनक होता है, लेकिन अन्य आकारों का उपयोग किया जा सकता है। छोटे माइक्रोकंट्रोलर में, एक समय में चार बिट्स को प्रोसेस करने के लिए 16-एंट्री टेबल का उपयोग करने से टेबल को छोटा रखते हुए उपयोगी गति में सुधार होता है। पर्याप्त भंडारण वाले कंप्यूटरों पर, a 65536-एंट्री टेबल का उपयोग एक समय में 16 बिट्स को प्रोसेस करने के लिए किया जा सकता है।

तालिकाएँ उत्पन्न करना

तालिकाएँ उत्पन्न करने वाला सॉफ़्टवेयर इतना छोटा और तेज़ है कि स्टोरेज से पूर्व-गणना की गई तालिकाओं को लोड करने की तुलना में प्रोग्राम स्टार्टअप पर उनकी गणना करना आमतौर पर तेज़ होता है। एक लोकप्रिय तकनीक 256 संभावित 8-बिट बाइट्स के सीआरसी उत्पन्न करने के लिए 256 बार बिट-ए-टाइम कोड का उपयोग करना है। हालाँकि, उस संपत्ति का लाभ उठाकर इसे महत्वपूर्ण रूप से अनुकूलित किया जा सकता है table[i xor j] == table[i] xor table[j]. केवल दो की शक्तियों के अनुरूप तालिका प्रविष्टियों की सीधे गणना करने की आवश्यकता है।

निम्नलिखित उदाहरण कोड में, crc का मान रखता है table[i]:

big_endian_table[0] := 0
crc := 0x8000 // एक 16-बिट बहुपद मानकर
मैं := 1
'करना' {
    'अगर' सीआरसी 'और' 0x8000 {
        सीआरसी := (सीआरसी 'लेफ्टशिफ्ट' 1) 'एक्सओआर' 0x1021 // सीआरसी बहुपद
    } 'अन्य' {
        सीआरसी := सीआरसी 'लेफ्टशिफ्ट' 1
    }
    // सीआरसी big_endian_table[i] का मान है; j को पहले से आरंभ की गई प्रविष्टियों पर पुनरावृति करने दें
    'के लिए' j 'से' 0 'से' i−1 {
        big_endian_table[i + j] := crc 'xor' big_endian_table[j];
    }
    मैं := मैं 'लेफ्टशिफ्ट' 1
} 'जबकि' मैं <256

'कोड खंड 7: बाइट-एट-ए-टाइम सीआरसी टेबल जनरेशन, एमएसबी पहले'

थोड़ा_एंडियन_टेबल[0] := 0
सीआरसी := 1;
मैं := 128
'करना' {
    'अगर' सीआरसी 'और' 1 {
        सीआरसी := (सीआरसी 'राइटशिफ्ट' 1) 'एक्सओआर' 0x8408 // सीआरसी बहुपद
    } 'अन्य' {
        सीआरसी := सीआरसी 'राइटशिफ्ट' 1
    }
    // सीआरसी tiny_endian_table[i] का मान है; j को पहले से आरंभ की गई प्रविष्टियों पर पुनरावृति करने दें
    'के लिए' जे 'से' 0 'से' 255 'द्वारा' 2 × आई {
        लिटिल_एंडियन_टेबल[आई + जे] := सीआरसी 'एक्सओआर' लिटिल_एंडियन_टेबल[जे];
    }
    i := मैं 'राइटशिफ्ट' 1
} 'जबकि' मैं > 0

'कोड खंड 8: बाइट-एट-ए-टाइम सीआरसी टेबल जनरेशन, एलएसबी पहले'

इन कोड नमूनों में, तालिका अनुक्रमणिका i + j के बराबर है i xor j; आप जो भी फॉर्म अधिक सुविधाजनक हो उसका उपयोग कर सकते हैं।

सीआरसी-32 एल्गोरिथ्म

यह सीआरसी के सीआरसी-32 संस्करण के लिए एक व्यावहारिक एल्गोरिदम है। सीआरसीटेबल एक गणना का संस्मरण है जिसे संदेश के प्रत्येक बाइट के लिए दोहराया जाना होगा (Computation of cyclic redundancy checks § Multi-bit computation).

<स्पैन स्टाइल=रंग:हरा; >फ़ंक्शन CRC32
   इनपुट:
      डेटा: बाइट्स <स्पैन शैली = रंग: हरा; >// बाइट्स की सरणी
   आउटपुट:
      crc32: UInt32 // 32-बिट अहस्ताक्षरित सीआरसी-32 मान

<स्पैन स्टाइल=रंग:हरा; >// प्रारंभिक मूल्य पर CRC-32 प्रारंभ करें
crc32 ← 0xFFFFFFFF

प्रत्येक बाइट के लिए in डेटा करें
   nLookupIndex ← (crc32 xor बाइट) और 0xFF
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] // CRCTable 256 32-बिट स्थिरांकों की एक सरणी है

<स्पैन स्टाइल=रंग:हरा; >// सभी बिट्स को उल्टा करके CRC-32 मान को अंतिम रूप दें
crc32 ← crc32 xor 0xFFFFFFFF
वापसी crc32

C में, एल्गोरिथ्म इस प्रकार दिखता है:

#include <inttypes.h> // uint32_t, uint8_t

uint32_t CRC32(const uint8_t data[], size_t data_length) {
	uint32_t crc32 = 0xFFFFFFFFu;
	
	for (size_t i = 0; i < data_length; i++) {
		const uint32_t lookupIndex = (crc32 ^ data[i]) & 0xff;
		crc32 = (crc32 >> 8) ^ CRCTable[lookupIndex];  // CRCTable is an array of 256 32-bit constants
	}
	
	// Finalize the CRC-32 value by inverting all the bits
	crc32 ^= 0xFFFFFFFFu;
	return crc32;
}

एकाधिक तालिकाओं का उपयोग करके बाइट-स्लाइसिंग

एक स्लाइस-बाय-एन (आमतौर पर सीआरसी32 के लिए स्लाइस-बाय-8; एन ≤ 64) एल्गोरिदम मौजूद है जो आमतौर पर सरवटे एल्गोरिदम की तुलना में प्रदर्शन को दोगुना या तिगुना कर देता है। एक समय में 8 बिट्स पढ़ने के बजाय, एल्गोरिदम एक समय में 8N बिट्स पढ़ता है। ऐसा करने से सुपरस्केलर प्रोसेसर पर प्रदर्शन अधिकतम हो जाता है। यह स्पष्ट नहीं है कि वास्तव में एल्गोरिदम का आविष्कार किसने किया था।

तालिका के बिना समानांतर गणना

एक समय में किसी बाइट या शब्द का समानांतर अद्यतन बिना तालिका के भी स्पष्ट रूप से किया जा सकता है। इसका उपयोग आमतौर पर हाई-स्पीड हार्डवेयर कार्यान्वयन में किया जाता है। प्रत्येक बिट के लिए 8 बिट्स को स्थानांतरित करने के बाद एक समीकरण हल किया जाता है। निम्नलिखित तालिकाएँ निम्नलिखित प्रतीकों का उपयोग करके कुछ सामान्य रूप से उपयोग किए जाने वाले बहुपदों के समीकरणों को सूचीबद्ध करती हैं:

ci	CRC bit 7…0 (or 15…0) before update
ri	CRC bit 7…0 (or 15…0) after update
di	input data bit 7…0
ei = di + ci	ep = e7 + e6 + … + e1 + e0 (parity bit)
si = di + ci+8	sp = s7 + s6 + … + s1 + s0 (parity bit)

Bit-wise update equations for some CRC-8 polynomials after 8 bits have been shifted in

Polynomial:	(x7 + x3 + 1) × x (left-shifted CRC-7-CCITT)	x8 + x5 + x4 + 1 (CRC-8-Dallas/Maxim)
Coefficients:	0x12 = (0x09 << 1) (MSBF/normal)	0x8c (LSBF/reverse)
r0 ← r1 ← r2 ← r3 ← r4 ← r5 ← r6 ← r7 ←	0 e0 + e4 + e7 e1 + e5 e2 + e6 e3 + e7 + e0 + e4 + e7 e4 + e1 + e5 e5 + e2 + e6 e6 + e3 + e7	e0 + e4 + e1 + e0 + e5 + e2 + e1 e1 + e5 + e2 + e1 + e6 + e3 + e2 + e0 e2 + e6 + e3 + e2 + e0 + e7 + e4 + e3 + e1 e3 + e0 + e7 + e4 + e3 + e1 e4 + e1 + e0 e5 + e2 + e1 e6 + e3 + e2 + e0 e7 + e4 + e3 + e1
C code fragments:	uint8_t c, d, e, f, r; … e = c ^ d; f = e ^ (e >> 4) ^ (e >> 7); r = (f << 1) ^ (f << 4);	uint8_t c, d, e, f, r; … e = c ^ d; f = e ^ (e << 3) ^ (e << 4) ^ (e << 6); r = f ^ (f >> 4) ^ (f >> 5);

Bit-wise update equations for some CRC-16 polynomials after 8 bits have been shifted in

Polynomial:	x16 + x12 + x5 + 1 (CRC-16-CCITT)		x16 + x15 + x2 + 1 (CRC-16-ANSI)
Coefficients:	0x1021 (MSBF/normal)	0x8408 (LSBF/reverse)	0x8005 (MSBF/normal)	0xa001 (LSBF/reverse)
r0 ← r1 ← r2 ← r3 ← r4 ← r5 ← r6 ← r7 ← r8 ← r9 ← r10 ← r11 ← r12 ← r13 ← r14 ← r15 ←	s4 + s0 s5 + s1 s6 + s2 s7 + s3 s4 s5 + s4 + s0 s6 + s5 + s1 s7 + s6 + s2 c0 + s7 + s3 c1 + s4 c2 + s5 c3 + s6 c4 + s7 + s4 + s0 c5 + s5 + s1 c6 + s6 + s2 c7 + s7 + s3	c8 + e4 + e0 c9 + e5 + e1 c10 + e6 + e2 c11 + e0 + e7 + e3 c12 + e1 c13 + e2 c14 + e3 c15 + e4 + e0 e0 + e5 + e1 e1 + e6 + e2 e2 + e7 + e3 e3 e4 + e0 e5 + e1 e6 + e2 e7 + e3	sp s0 + sp s1 + s0 s2 + s1 s3 + s2 s4 + s3 s5 + s4 s6 + s5 c0 + s7 + s6 c1 + s7 c2 c3 c4 c5 c6 c7 + sp	c8 + ep c9 c10 c11 c12 c13 c14 + e0 c15 + e1 + e0 e2 + e1 e3 + e2 e4 + e3 e5 + e4 e6 + e5 e7 + e6 ep + e7 ep
C code fragments:	uint8_t d, s, t; uint16_t c, r; … s = d ^ (c >> 8); t = s ^ (s >> 4); r = (c << 8) ^ t ^ (t << 5) ^ (t << 12);	uint8_t d, e, f; uint16_t c, r; … e = c ^ d; f = e ^ (e << 4); r = (c >> 8) ^ (f << 8) ^ (f << 3) ^ (f >> 4);	uint8_t d, s, p; uint16_t c, r, t; … s = d ^ (c >> 8); p = s ^ (s >> 4); p = p ^ (p >> 2); p = p ^ (p >> 1); p = p & 1; t = p | (s << 1); r = (c << 8) ^ (t << 15) ^ t ^ (t << 1);	uint8_t d, e, p; uint16_t c, r, f; … e = c ^ d; p = e ^ (e >> 4); p = p ^ (p >> 2); p = p ^ (p >> 1); p = p & 1; f = e | (p << 8); r = (c >> 8) ^ (f << 6) ^ (f << 7) ^ (f >> 8);

दो-चरणीय गणना

चूँकि CRC-32 बहुपद में बड़ी संख्या में पद होते हैं, एक समय में शेष बाइट की गणना करते समय प्रत्येक बिट पिछले पुनरावृत्ति के कई बिट्स पर निर्भर करता है। बाइट-समानांतर हार्डवेयर कार्यान्वयन में इसके लिए मल्टीपल-इनपुट या कैस्केड XOR गेट्स की आवश्यकता होती है जो प्रसार विलंब को बढ़ाता है।

गणना गति को अधिकतम करने के लिए, 123-बिट शिफ्ट रजिस्टर के माध्यम से संदेश को पारित करके एक मध्यवर्ती शेष की गणना की जा सकती है। बहुपद मानक बहुपद का सावधानीपूर्वक चयनित गुणज है, जैसे कि पद (फीडबैक टैप) व्यापक रूप से दूरी पर हैं, और शेष का कोई भी बिट प्रति बाइट पुनरावृत्ति में एक बार से अधिक XORed नहीं है। इस प्रकार केवल दो-इनपुट XOR गेट, सबसे तेज़ संभव, की आवश्यकता है। अंत में सीआरसी-32 शेष प्राप्त करने के लिए मध्यवर्ती शेष को दूसरी पाली रजिस्टर में मानक बहुपद द्वारा विभाजित किया जाता है।

ब्लॉकवार गणना

शेष की ब्लॉक-वार गणना किसी भी सीआरसी बहुपद के लिए हार्डवेयर में राज्य अंतरिक्ष परिवर्तन मैट्रिक्स को गुणनखंडित करके की जा सकती है, जो शेष को दो सरल टोप्लिट्ज मैट्रिक्स में गणना करने के लिए आवश्यक है।

एक-पास चेकिंग

किसी संदेश में सीआरसी जोड़ते समय, प्रेषित सीआरसी को अलग करना, उसकी पुन: गणना करना और प्रेषित सीआरसी के विरुद्ध पुन: संगणित मूल्य को सत्यापित करना संभव है। हालाँकि, आमतौर पर एक सरल तकनीक होती है हार्डवेयर में उपयोग किया जाता है।

जब सीआरसी सही बाइट ऑर्डर (चयनित बिट-ऑर्डरिंग कन्वेंशन से मेल खाते हुए) के साथ प्रसारित होता है, तो एक रिसीवर संदेश और सीआरसी पर समग्र सीआरसी की गणना कर सकता है, और यदि वे सही हैं, तो परिणाम शून्य होगा। यह संभावना यही कारण है कि अधिकांश नेटवर्क प्रोटोकॉल जिनमें सीआरसी शामिल है, अंतिम सीमांकक से पहले ऐसा करते हैं; सीआरसी की जांच के लिए यह जानना जरूरी नहीं है कि पैकेट का अंत निकट है या नहीं। वास्तव में, कुछ प्रोटोकॉल सीआरसी का उपयोग अंतिम सीमांकक - सीआरसी-आधारित फ़्रेमिंग के रूप में करते हैं।

सीआरसी वेरिएंट

व्यवहार में, अधिकांश मानक रजिस्टर को ऑल-वन पर प्रीसेट करने और ट्रांसमिशन से पहले सीआरसी को उल्टा करने को निर्दिष्ट करते हैं। इससे सीआरसी की परिवर्तित बिट्स का पता लगाने की क्षमता पर कोई प्रभाव नहीं पड़ता है, लेकिन यह संदेश में जोड़े गए बिट्स को नोटिस करने की क्षमता देता है।

=== −1 === पर प्रीसेट सीआरसी का बुनियादी गणित उन संदेशों को स्वीकार करता है (सही ढंग से प्रसारित माना जाता है) जिन्हें बहुपद के रूप में व्याख्या किए जाने पर, सीआरसी बहुपद का एक गुणक होता है। यदि कुछ अग्रणी 0 बिट्स को ऐसे संदेश से जोड़ा जाता है, तो वे बहुपद के रूप में इसकी व्याख्या को नहीं बदलेंगे। यह इस तथ्य के समतुल्य है कि 0001 और 1 एक ही संख्या हैं।

लेकिन यदि प्रेषित किया जा रहा संदेश अग्रणी 0 बिट्स की परवाह करता है, तो ऐसे परिवर्तन का पता लगाने के लिए बुनियादी सीआरसी एल्गोरिदम की अक्षमता अवांछनीय है। यदि यह संभव है कि एक ट्रांसमिशन त्रुटि ऐसे बिट्स को जोड़ सकती है, तो एक सरल समाधान यह है कि शुरुआत करें rem शिफ्ट रजिस्टर को कुछ गैर-शून्य मान पर सेट किया गया; सुविधा के लिए, आमतौर पर ऑल-वन्स मान का उपयोग किया जाता है। यह गणितीय रूप से संदेश के पहले एन बिट्स को पूरक करने (बाइनरी नोट) के बराबर है, जहां एन सीआरसी रजिस्टर में बिट्स की संख्या है।

यह सीआरसी निर्माण और जांच को किसी भी तरह से प्रभावित नहीं करता है, जब तक जनरेटर और चेकर दोनों समान प्रारंभिक मूल्य का उपयोग करते हैं। कोई भी गैर-शून्य प्रारंभिक मान काम करेगा, और कुछ मानक असामान्य मान निर्दिष्ट करते हैं, लेकिन सभी का मान (दो में −1 पूरक बाइनरी) अब तक का सबसे आम है। ध्यान दें कि एक-पास सीआरसी जनरेट/चेक पूर्व निर्धारित मूल्य की परवाह किए बिना, संदेश सही होने पर भी शून्य का परिणाम देगा।

पोस्ट-उलटा

उसी प्रकार की त्रुटि संदेश के अंत में हो सकती है, भले ही संदेशों के अधिक सीमित सेट के साथ। किसी संदेश में 0 बिट जोड़ना उसके बहुपद को x से गुणा करने के बराबर है, और यदि यह पहले CRC बहुपद का गुणज था, तो उस गुणन का परिणाम भी होगा। यह इस तथ्य के समतुल्य है कि, चूँकि 726, 11 का गुणज है, इसलिए 7260 भी है।

एक समान समाधान संदेश के अंत में लागू किया जा सकता है, संदेश में जोड़ने से पहले सीआरसी रजिस्टर को उल्टा कर दिया जा सकता है। फिर, कोई भी गैर-शून्य परिवर्तन करेगा; सभी बिट्स को उलटना (ऑल-वन्स पैटर्न के साथ XORing) सबसे आम है।

इसका एक-पास सीआरसी जाँच पर प्रभाव पड़ता है: संदेश सही होने पर शून्य का परिणाम उत्पन्न करने के बजाय, यह एक निश्चित गैर-शून्य परिणाम उत्पन्न करता है। (सटीक होने के लिए, परिणाम व्युत्क्रम पैटर्न का सीआरसी (गैर-शून्य प्रीसेट के बिना, लेकिन पोस्ट-इनवर्ट के साथ) है।) एक बार जब यह स्थिरांक प्राप्त हो जाता है (एक मनमाना संदेश पर एक-पास सीआरसी उत्पन्न/चेक करके सबसे आसानी से), इसका उपयोग उसी सीआरसी एल्गोरिथ्म का उपयोग करके जांचे गए किसी भी अन्य संदेश की शुद्धता को सत्यापित करने के लिए सीधे किया जा सकता है।

यह भी देखें

सामान्य वर्ग

• कोड सुधारने में त्रुटि
• हैश फ़ंक्शंस की सूची
• समता (दूरसंचार) बहुपद के साथ 1-बिट सीआरसी के बराबर है x+1.

गैर-सीआरसी चेकसम

• एडलर-32
• फ्लेचर का चेकसम

बाहरी संबंध

• JohnPaul Adamovsky. "64 Bit Cyclic Redundant Code – XOR Long Division To Bytewise Table Lookup".

• Andrew Kadarch, Bob Jenkins. "Efficient (~1 CPU cycle per byte) CRC implementation". GitHub.