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

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

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

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

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

उदाहरण

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

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

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

Most-significant bit फर्स्ट

Least-significant bit फर्स्ट

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₁₆ होता है। एलएसबिट-फर्स्ट में रेमैंडरफल $x^{7}+x^{4}+x^{3}$ होता है। हेक्साडेसिमल संख्या को कनवर्ट करने के लिए कन्वेंशन का उपयोग किया जाता है जो x की उच्चतम पॉवर एलएसबिट होता है; यह 19₁₆ होता है।

इम्प्लीमेंटेशन

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

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

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial := 0
    // A popular variant complements remainderPolynomial here; see § 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

}

कोड फ्रेगमेंट 1: सरल पॉलीनोमियल डिवीज़न

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

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

पहली समस्या को $x$ से गुणा करने से फर्स्ट रेमैंडरपॉलीनोमियल के $x^{n-1}$ गुणांक का परीक्षण करके हल किया जा सकता है।

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

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

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

function crc(byte array string[1..len], int len) {
    remainderPolynomial := 0
    // A popular variant complements remainderPolynomial here; see § 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
}

कोड फ्रेगमेंट 2: डिफर्ड XORing के साथ पॉलीनोमियल डिवीज़न

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

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

function crc(byte array string[1..len], int len) {
    remainderPolynomial := 0
    // A popular variant complements remainderPolynomial here; see § 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$ में मैप करना चाहिए। दूसरी ओर, फ्लॉपी डिस्क और अधिकांश हार्ड ड्राइव फर्स्ट प्रत्येक बाइट का सबसे महत्वपूर्ण बिट लिखते हैं।

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

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

// Most significant bit first (big-endian)
// x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021
function crc(byte array string[1..len], int len) {
    rem := 0
    // A popular variant complements rem here
    for i from 1 to len {
        rem  := rem xor (string[i] leftShift (n-8))   // n = 16 in this example
        for j from 1 to 8 {   // Assuming 8 bits per byte
            if rem and 0x8000 {   // if leftmost (most significant) bit is set
                rem  := (rem leftShift 1) xor 0x1021
            } else {
                rem  := rem leftShift 1
            }
            rem  := rem and 0xffff      // Trim remainder to 16 bits
        }
    }
    // A popular variant complements rem here

    return rem
}

'कोड फ्रेगमेंट 4: शिफ्ट रजिस्टर बेस्ड डिवीज़न, एमएसबी फर्स्ट

// Least significant bit first (little-endian)
// x^16+x^12+x^5+1 = 1000 0100 0000 1000 (1) = 0x8408
function crc(byte array string[1..len], int len) {
    rem  := 0
    // A popular variant complements rem here
    for i from 1 to len {
        rem  := rem xor string[i]
        for j from 1 to 8 {   // Assuming 8 bits per byte
            if rem and 0x0001 {   // if rightmost (most significant) bit is set
                rem  := (rem rightShift 1) xor 0x8408
            } else {
                rem  := rem rightShift 1
            }
        }
    }
    // A popular variant complements rem here

    return rem
}

कोड फ्रेगमेंट 5: शिफ्ट रजिस्टर बेस्ड डिवीज़न, एलएसबी फर्स्ट

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

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

मल्टी-बिट कंप्यूटिंग

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

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

// Msbit-first
rem = (rem leftShift 8) xor big_endian_table[string[i] xor ((leftmost 8 bits of rem) rightShift (n-8))]
// Lsbit-first

rem = (rem rightShift 8) xor little_endian_table[string[i] xor (rightmost 8 bits of rem)]

कोड फ्रेगमेंट 6: टेबल आधारित डिवीज़न के कोर

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

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

टेबल जनरेट करना

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

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

big_endian_table[0] := 0
crc := 0x8000 // Assuming a 16-bit polynomial
i := 1
do {
    if crc and 0x8000 {
        crc := (crc leftShift 1) xor 0x1021 // The CRC polynomial
    } else {
        crc := crc leftShift 1
    }
    // crc is the value of big_endian_table[i]; let j iterate over the already-initialized entries
    for j from 0 to i−1 {
        big_endian_table[i + j] := crc xor big_endian_table[j];
    }
    i := i leftshift 1

} while i < 256

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

little_endian_table[0] := 0
crc := 1;
i := 128
do {
    if crc and 1 {
        crc := (crc rightShift 1) xor 0x8408 // The CRC polynomial
    } else {
        crc := crc rightShift 1
    }
    // crc is the value of little_endian_table[i]; let j iterate over the already-initialized entries
    for j from 0 to 255 by 2 × i {
        little_endian_table[i + j] := crc xor little_endian_table[j];
    }
    i := i rightshift 1

} while i > 0

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

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

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

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

Function CRC32
   Input:
      data:  Bytes     // Array of bytes
   Output:
      crc32: UInt32    // 32-bit unsigned CRC-32 value

// Initialize CRC-32 to starting value
crc32 ← 0xFFFFFFFF

for each byte in data do
   nLookupIndex ← (crc32 xor byte) and 0xFF
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex]  // CRCTable is an array of 256 32-bit constants

// Finalize the CRC-32 value by inverting all the bits
crc32 ← crc32 xor 0xFFFFFFFF
return 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	सीआरसी bit 7…0 (or 15…0) before update
ri	सीआरसी 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 सीआरसी-8 पॉलीनोमियलs after 8 bits have been shifted in

पॉलीनोमियल:	(x7 + x3 + 1) × x (left-shifted सीआरसी-7-CCITT)	x8 + x5 + x4 + 1 (सीआरसी-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 सीआरसी-16 पॉलीनोमियलs after 8 bits have been shifted in

पॉलीनोमियल:	x16 + x12 + x5 + 1 (सीआरसी-16-CCITT)		x16 + x15 + x2 + 1 (सीआरसी-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);

टू-स्टेपीय कंप्यूटिंग

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

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

ब्लॉकवार कंप्यूटिंग

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

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

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

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

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

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

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

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

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

पोस्ट-उलटा

उसी प्रकार की त्रुटि मेसेज के अंत में हो सकती है, भले ही मेसेजों के अधिक सीमित सेट के साथ। किसी मेसेज में 0 बिट जोड़ना उसके पॉलीनोमियल को x से गुणा करने के बराबर है, और यदि यह फर्स्ट सीआरसी पॉलीनोमियल का गुणज था, तो उस गुणन का परिणाम भी होगा। यह इस तथ्य के समतुल्य है कि, चूँकि 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.