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

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

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

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

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

उदाहरण

हार्डवेयर में बहुपद डिवीज़न को प्रयुक्त करने के एक उदाहरण के रूप में, मान लीजिए कि हम ASCII वर्ण W से बने 8-बिट मेसेज के 8-बिट CRC की कंप्यूटिंग करने का प्रयास कर रहे हैं, जो बाइनरी 01010111 है, डेसिमल 87₁₀, या हेक्साडेसिमल 57₁₆ होता है। उदाहरण के लिए, हम CRC-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 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₁₆ होता है। एलएसबिट-फर्स्ट में शेषफल $x^{7}+x^{4}+x^{3}$ होता है। हेक्साडेसिमल संख्या को कनवर्ट करने के लिए कन्वेंशन का उपयोग किया जाता है जो x की उच्चतम शक्ति एलएसबिट होता है; यह 19₁₆ होता है।

कार्यान्वयन

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

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

फ़ंक्शन सीआरसी(बिट ऐरे बिटस्ट्रिंग[1..लेन], इंट लेन) {
    remainderPolynomial := polynomialForm(bitString[1..n])   // First n bits of the message
    // A popular variant complements remainderPolynomial here; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x⁰   // Define bitString[k]=0 for k>len
        if coefficient of xⁿ of remainderPolynomial = 1 {
            remainderPolynomial := remainderPolynomial xor generatorPolynomial
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

कोड खंड 1: सरल बहुपद डिवीज़न § Preset to −1 § Post-invert

ध्यान दें कि यह उदाहरण कोड बाइट्स का उपयोग न करके बिट-ऑर्डरिंग कन्वेंशन को निर्दिष्ट करने की आवश्यकता से बचाता है; इनपुट 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] * xⁿ⁻¹)
        if (coefficient of xⁿ⁻¹ 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]) * xⁿ⁻⁸
        for j from 1 to 8 {    // Assuming 8 bits per byte
            if coefficient of xⁿ⁻¹ 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 प्रति पुनरावृत्ति एक से अधिक बिट लाभांश संसाधित करना।^[3] आमतौर पर, 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 में एक संक्षिप्त और सरल तालिका-संचालित कार्यान्वयन के साथ एक परिशिष्ट शामिल है।^[4] आप देखेंगे कि कोड यहां प्रस्तुत 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 संस्करण के लिए एक व्यावहारिक एल्गोरिदम है।^[5] सीआरसीटेबल एक कंप्यूटिंग का संस्मरण है जिसे मेसेज के प्रत्येक बाइट के लिए दोहराया जाना होगा (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 बिट्स पढ़ता है। ऐसा करने से सुपरस्केलर प्रोसेसर पर प्रदर्शन अधिकतम हो जाता है।^[6]^[7]^[8]^[9] यह स्पष्ट नहीं है कि वास्तव में एल्गोरिदम का आविष्कार किसने किया था।^[10]

तालिका के बिना समानांतर कंप्यूटिंग

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

c_i	CRC bit 7…0 (or 15…0) before update
r_i	CRC bit 7…0 (or 15…0) after update
d_i	input data bit 7…0
e_i = d_i + c_i	e_p = e₇ + e₆ + … + e₁ + e₀ (parity bit)
s_i = d_i + c_i+8	s_p = s₇ + s₆ + … + s₁ + s₀ (parity bit)

Bit-wise update equations for some CRC-8 polynomials after 8 bits have been shifted in
Polynomial:	(x⁷ + x³ + 1) × x (left-shifted CRC-7-CCITT)	x⁸ + x⁵ + x⁴ + 1 (CRC-8-Dallas/Maxim)
Coefficients:	0x12 = (0x09 << 1) (MSBF/normal)	0x8c (LSBF/reverse)
r₀ ← r₁ ← r₂ ← r₃ ← r₄ ← r₅ ← r₆ ← r₇ ←	0 e₀ + e₄ + e₇ e₁ + e₅ e₂ + e₆ e₃ + e₇ + e₀ + e₄ + e₇ e₄ + e₁ + e₅ e₅ + e₂ + e₆ e₆ + e₃ + e₇	e₀ + e₄ + e₁ + e₀ + e₅ + e₂ + e₁ e₁ + e₅ + e₂ + e₁ + e₆ + e₃ + e₂ + e₀ e₂ + e₆ + e₃ + e₂ + e₀ + e₇ + e₄ + e₃ + e₁ e₃ + e₀ + e₇ + e₄ + e₃ + e₁ e₄ + e₁ + e₀ e₅ + e₂ + e₁ e₆ + e₃ + e₂ + e₀ e₇ + e₄ + e₃ + e₁
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:	x¹⁶ + x¹² + x⁵ + 1 (CRC-16-CCITT)		x¹⁶ + x¹⁵ + x² + 1 (CRC-16-ANSI)
Coefficients:	0x1021 (MSBF/normal)	0x8408 (LSBF/reverse)	0x8005 (MSBF/normal)	0xa001 (LSBF/reverse)
r₀ ← r₁ ← r₂ ← r₃ ← r₄ ← r₅ ← r₆ ← r₇ ← r₈ ← r₉ ← r₁₀ ← r₁₁ ← r₁₂ ← r₁₃ ← r₁₄ ← r₁₅ ←	s₄ + s₀ s₅ + s₁ s₆ + s₂ s₇ + s₃ s₄ s₅ + s₄ + s₀ s₆ + s₅ + s₁ s₇ + s₆ + s₂ c₀ + s₇ + s₃ c₁ + s₄ c₂ + s₅ c₃ + s₆ c₄ + s₇ + s₄ + s₀ c₅ + s₅ + s₁ c₆ + s₆ + s₂ c₇ + s₇ + s₃	c₈ + e₄ + e₀ c₉ + e₅ + e₁ c₁₀ + e₆ + e₂ c₁₁ + e₀ + e₇ + e₃ c₁₂ + e₁ c₁₃ + e₂ c₁₄ + e₃ c₁₅ + e₄ + e₀ e₀ + e₅ + e₁ e₁ + e₆ + e₂ e₂ + e₇ + e₃ e₃ e₄ + e₀ e₅ + e₁ e₆ + e₂ e₇ + e₃	s_p s₀ + s_p s₁ + s₀ s₂ + s₁ s₃ + s₂ s₄ + s₃ s₅ + s₄ s₆ + s₅ c₀ + s₇ + s₆ c₁ + s₇ c₂ c₃ c₄ c₅ c₆ c₇ + s_p	c₈ + e_p c₉ c₁₀ c₁₁ c₁₂ c₁₃ c₁₄ + e₀ c₁₅ + e₁ + e₀ e₂ + e₁ e₃ + e₂ e₄ + e₃ e₅ + e₄ e₆ + e₅ e₇ + e₆ e_p + e₇ e_p
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 शेष प्राप्त करने के लिए मध्यवर्ती शेष को दूसरी पाली रजिस्टर में मानक बहुपद द्वारा विभाजित किया जाता है।^[12]

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

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

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

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

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

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

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

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

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

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

पोस्ट-उलटा

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

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

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

यह भी देखें

सामान्य वर्ग

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

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

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

संदर्भ

↑ Dubrova, Elena; Mansouri, Shohreh Sharif (May 2012). "A BDD-Based Approach to Constructing LFSRS for Parallel CRC Encoding". 2012 IEEE 42nd International Symposium on Multiple-Valued Logic. pp. 128–133. doi:10.1109/ISMVL.2012.20. ISBN 978-0-7695-4673-5. S2CID 27306826.
↑ ^2.0 ^2.1 Williams, Ross N. (1996-09-24). "A Painless Guide to CRC Error Detection Algorithms V3.00". Archived from the original on 2006-09-27. Retrieved 2016-02-16.
↑ Sarwate, Dilip V. (August 1998). "टेबल लुक-अप के माध्यम से चक्रीय अतिरेक जांच की गणना". Communications of the ACM. 31 (8): 1008–1013. doi:10.1145/63030.63037. S2CID 5363350.
↑ "Portable Network Graphics (PNG) Specification (Second Edition): Annex D, Sample Cyclic Redundancy Code implementation". W3C. 2003-11-10. Retrieved 2016-02-16.
↑ "[MS-ABS]: 32-Bit CRC Algorithm". msdn.microsoft.com. Archived from the original on 7 November 2017. Retrieved 4 November 2017.
↑ Kounavis, M.E.; Berry, F.L. (2005). "A Systematic Approach to Building High Performance Software-Based CRC Generators". 10th IEEE Symposium on Computers and Communications (ISCC'05) (PDF). pp. 855–862. doi:10.1109/ISCC.2005.18. ISBN 0-7695-2373-0. S2CID 10308354.
↑ Berry, Frank L.; Kounavis, Michael E. (November 2008). "उच्च-प्रदर्शन सीआरसी पीढ़ी के लिए नवीन तालिका लुकअप-आधारित एल्गोरिदम". IEEE Transactions on Computers. 57 (11): 1550–1560. doi:10.1109/TC.2008.85. S2CID 206624854.
↑ High Octane CRC Generation with the Intel Slicing-by-8 Algorithm (PDF) (Technical report). Intel. Archived from the original (PDF) on 2012-07-22.
↑ "सीआरसी गणना पर संक्षिप्त ट्यूटोरियल". The Linux Kernel Archives.
↑ Menon-Sen, Abhijit (2017-01-20). "Who invented the slicing-by-N CRC32 algorithm?".
↑ Jon Buller (1996-03-15). "Re: 8051 and CRC-CCITT". Newsgroup: comp.arch.embedded. Usenet: 31498ED0.7C0A@nortel.com. Retrieved 2016-02-16.
↑ Glaise, René J. (1997-01-20). "A two-step computation of cyclic redundancy code CRC-32 for ATM networks". IBM Journal of Research and Development. Armonk, NY: IBM. 41 (6): 705. doi:10.1147/rd.416.0705. Archived from the original on 2009-01-30. Retrieved 2016-02-16.
↑ Das, Arindam (2022). "लुक-अप टेबल के स्थान पर फैक्टर्ड टोप्लिट्ज़ मैट्रिसेस का उपयोग करके चक्रीय रिडंडेंसी कोड की ब्लॉक-वार गणना". IEEE Transactions on Computers. 72 (4): 1110–1121. doi:10.1109/TC.2022.3189574. ISSN 0018-9340. S2CID 250472783.
↑ Andrew Kadatch, Bob Jenkins. "Everything we know about CRC but afraid to forget". 2007. quote: "The fact that the CRC of a message followed by its CRC is a constant value which does not depend on the message... is well known and has been widely used in the telecommunication industry for long time."
↑ E.g. low-frequency RFID TMS37157 data sheet - Passive Low Frequency Interface Device With EEPROM and 134.2 kHz Transponder Interface (PDF), Texas Instruments, November 2009, p. 39, retrieved 2016-02-16, The CRC Generator is initialized with the value 0x3791 as shown in Figure 50.

बाहरी संबंध

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.

[1] Dubrova, Elena; Mansouri, Shohreh Sharif (May 2012). "A BDD-Based Approach to Constructing LFSRS for Parallel CRC Encoding". 2012 IEEE 42nd International Symposium on Multiple-Valued Logic. pp. 128–133. doi:10.1109/ISMVL.2012.20. ISBN 978-0-7695-4673-5. S2CID 27306826.

[williams96-2] 2.0 ^2.1 Williams, Ross N. (1996-09-24). "A Painless Guide to CRC Error Detection Algorithms V3.00". Archived from the original on 2006-09-27. Retrieved 2016-02-16.

[3] Sarwate, Dilip V. (August 1998). "टेबल लुक-अप के माध्यम से चक्रीय अतिरेक जांच की गणना". Communications of the ACM. 31 (8): 1008–1013. doi:10.1145/63030.63037. S2CID 5363350.

[4] "Portable Network Graphics (PNG) Specification (Second Edition): Annex D, Sample Cyclic Redundancy Code implementation". W3C. 2003-11-10. Retrieved 2016-02-16.

[5] "[MS-ABS]: 32-Bit CRC Algorithm". msdn.microsoft.com. Archived from the original on 7 November 2017. Retrieved 4 November 2017.

[6] Kounavis, M.E.; Berry, F.L. (2005). "A Systematic Approach to Building High Performance Software-Based CRC Generators". 10th IEEE Symposium on Computers and Communications (ISCC'05) (PDF). pp. 855–862. doi:10.1109/ISCC.2005.18. ISBN 0-7695-2373-0. S2CID 10308354.

[7] Berry, Frank L.; Kounavis, Michael E. (November 2008). "उच्च-प्रदर्शन सीआरसी पीढ़ी के लिए नवीन तालिका लुकअप-आधारित एल्गोरिदम". IEEE Transactions on Computers. 57 (11): 1550–1560. doi:10.1109/TC.2008.85. S2CID 206624854.

[8] High Octane CRC Generation with the Intel Slicing-by-8 Algorithm (PDF) (Technical report). Intel. Archived from the original (PDF) on 2012-07-22.

[9] "सीआरसी गणना पर संक्षिप्त ट्यूटोरियल". The Linux Kernel Archives.

[10] Menon-Sen, Abhijit (2017-01-20). "Who invented the slicing-by-N CRC32 algorithm?".

[11] Jon Buller (1996-03-15). "Re: 8051 and CRC-CCITT". Newsgroup: comp.arch.embedded. Usenet: 31498ED0.7C0A@nortel.com. Retrieved 2016-02-16.

[glaise-12] Glaise, René J. (1997-01-20). "A two-step computation of cyclic redundancy code CRC-32 for ATM networks". IBM Journal of Research and Development. Armonk, NY: IBM. 41 (6): 705. doi:10.1147/rd.416.0705. Archived from the original on 2009-01-30. Retrieved 2016-02-16.

[13] Das, Arindam (2022). "लुक-अप टेबल के स्थान पर फैक्टर्ड टोप्लिट्ज़ मैट्रिसेस का उपयोग करके चक्रीय रिडंडेंसी कोड की ब्लॉक-वार गणना". IEEE Transactions on Computers. 72 (4): 1110–1121. doi:10.1109/TC.2022.3189574. ISSN 0018-9340. S2CID 250472783.

[14] Andrew Kadatch, Bob Jenkins. "Everything we know about CRC but afraid to forget". 2007. quote: "The fact that the CRC of a message followed by its CRC is a constant value which does not depend on the message... is well known and has been widely used in the telecommunication industry for long time."

[15] E.g. low-frequency RFID TMS37157 data sheet - Passive Low Frequency Interface Device With EEPROM and 134.2 kHz Transponder Interface (PDF), Texas Instruments, November 2009, p. 39, retrieved 2016-02-16, The CRC Generator is initialized with the value 0x3791 as shown in Figure 50.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

उदाहरण

कार्यान्वयन

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

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

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

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

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

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

तालिका के बिना समानांतर कंप्यूटिंग

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

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

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

पोस्ट-उलटा

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

उदाहरण

कार्यान्वयन

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

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

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

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

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

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

तालिका के बिना समानांतर कंप्यूटिंग

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

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

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

पोस्ट-उलटा

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories