حساب عمليات التحقق من التكرار الدوري

تمت كتابة هذه المقالة كدليل أو دليل إرشادي . يُرجى المساعدة في إعادة كتابة هذه المقالة وإزالة النصائح أو الإرشادات. ( فبراير 2023 )

The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "Computation of cyclic redundancy checks" – news · newspapers · books · scholar · JSTOR (February 2023) (Learn how and when to remove this message)

يتم اشتقاق حساب فحص التكرار الدوري من رياضيات القسمة متعددة الحدود، modulo 2. في الممارسة العملية، يشبه القسمة الطويلة لسلسلة الرسائل الثنائية ، مع إضافة عدد ثابت من الأصفار، بواسطة سلسلة "متعددة الحدود المولدة" باستثناء أن العمليات الحصرية أو العمليات تحل محل عمليات الطرح. يتم تنفيذ القسمة من هذا النوع بكفاءة في الأجهزة بواسطة سجل تحويل معدّل ، ^[1] وفي البرامج بواسطة سلسلة من الخوارزميات المكافئة ، بدءًا من الكود البسيط القريب من الرياضيات ويصبح أسرع (ويمكن القول أنه أكثر تعتيمًا ^[2] ) من خلال التوازي على مستوى البايت والمقايضات بين الزمان والمكان .

توسع معايير CRC المختلفة خوارزمية القسمة متعددة الحدود من خلال تحديد قيمة سجل التحويل الأولية، وخطوة Exclusive-Or النهائية، والأهم من ذلك، ترتيب البتات ( endianness ). ونتيجة لذلك، ينحرف الكود الذي نراه في الممارسة العملية بشكل مربك عن القسمة "الخالصة"، ^[2] وقد يتحول السجل إلى اليسار أو اليمين.

كمثال على تنفيذ القسمة متعددة الحدود في الأجهزة، افترض أننا نحاول حساب CRC مكون من 8 بتات لرسالة مكونة من 8 بتات مكونة من حرف ASCII "W"، وهو ثنائي 01010111 ₂ أو عشري 87 ₁₀ أو سداسي عشري 57 _16. للتوضيح، سنستخدم متعددة الحدود CRC-8-ATM ( HEC ) . بكتابة أول بت منقول (معامل أعلى قوة لـ ) على اليسار، يتوافق هذا مع السلسلة المكونة من 9 بتات "100000111". ${\displaystyle x^{8}+x^{2}+x+1}$${\displaystyle x}$

يمكن إرسال قيمة البايت 57 ₁₆ بترتيبين مختلفين، اعتمادًا على اتفاقية ترتيب البتات المستخدمة. كل واحد منهما يولد متعدد حدود رسالة مختلف . أول بايت، هذا = 01010111، بينما أول بايت، هذا = 11101010. يمكن بعد ذلك ضرب هذه في لإنتاج متعدد حدود رسالة مكون من 16 بت . ${\displaystyle M(x)}$${\displaystyle x^{6}+x^{4}+x^{2}+x+1}$${\displaystyle x^{7}+x^{6}+x^{5}+x^{3}+x}$${\displaystyle x^{8}}$${\displaystyle x^{8}M(x)}$

يتكون حساب الباقي بعد ذلك من طرح مضاعفات متعددة الحدود المولدة . هذا يشبه تمامًا القسمة الطويلة العشرية، ولكن أبسط لأن المضاعفات الوحيدة الممكنة في كل خطوة هي 0 و1، وعمليات الطرح تستعير "من اللانهاية" بدلاً من تقليل الأرقام العليا. نظرًا لأننا لا نهتم بالحاصل، فلا توجد حاجة لتسجيله. ${\displaystyle G(x)}$

لاحظ أنه بعد كل عملية طرح، يتم تقسيم البتات إلى ثلاث مجموعات: في البداية، مجموعة مكونة بالكامل من صفر؛ وفي النهاية، مجموعة لم تتغير عن الأصل؛ ومجموعة مظللة باللون الأزرق في المنتصف وهي "مثيرة للاهتمام". يبلغ طول المجموعة "المثيرة للاهتمام" 8 بتات، وهو ما يطابق درجة كثيرة الحدود. في كل خطوة، يتم طرح المضاعف المناسب لكثيرة الحدود لجعل مجموعة الصفر أطول بمقدار بت واحد، وتصبح المجموعة غير المتغيرة أقصر بمقدار بت واحد، حتى يتبقى الباقي الأخير فقط.

في مثال msbit-first، يكون الباقي من متعدد الحدود هو . عند التحويل إلى رقم سداسي عشري باستخدام الاتفاقية التي تنص على أن أعلى قوة لـ x هي msbit؛ يكون هذا هو A2 ₁₆ . في lsbit-first، يكون الباقي هو . عند التحويل إلى رقم سداسي عشري باستخدام الاتفاقية التي تنص على أن أعلى قوة لـ x هي lsbit، يكون هذا هو 19 ₁₆ . ${\displaystyle x^{7}+x^{5}+x}$${\displaystyle x^{7}+x^{4}+x^{3}}$

إن كتابة الرسالة كاملة في كل خطوة، كما تم في المثال أعلاه، أمر مرهق للغاية. تستخدم التطبيقات الفعّالة سجل تحويل بت - للاحتفاظ بالبتات المثيرة للاهتمام فقط. إن ضرب الحدود في يساوي تحويل السجل بمقدار مكان واحد، حيث لا تتغير قيمة المعاملات ولكنها تتحرك فقط إلى الحد التالي من الحدود. ${\displaystyle n}$${\displaystyle x}$

فيما يلي مسودة أولية لبعض الكود الزائف لحساب CRC مكون من n بت. وهو يستخدم نوع بيانات مركب مصطنع للحدوديات، حيث xليس متغيرًا صحيحًا، بل مُنشئًا يُنشئ كائنًا متعدد الحدود يمكن إضافته وضربه وضربه في أس. إلى متعددي حدود يعني إضافتهما، modulo اثنين؛ أي إلى معاملات كل حد مطابق من كل من الحدوديين. xor

دالة crc( مصفوفة بت bitString[1..len]، int len) {
    remainderPolynomial := polynomialForm (bitString[1..n])    // أول n بت من الرسالة 
    // هناك متغير شائع يكمل remainderPolynomial هنا؛ راجع § تم ضبطه مسبقًا على −1 أدناه 
    لـ i من 1 إلى len {
        remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x 0    // قم بتعريف bitString[k]=0 لـ k>len 
        إذا كان معامل x n من remainderPolynomial = 1 {
            remainderPolynomial := remainderPolynomial مولد xor كثير الحدود
        }
    }
    // هناك متغير شائع يكمل remainderPolynomial هنا؛ راجع § عكس ما بعد أدناه 
    إرجاع remainderPolynomial
}

مقطع الكود 1: القسمة الحدودية البسيطة

لاحظ أن هذا الكود المثال يتجنب الحاجة إلى تحديد اتفاقية ترتيب البتات من خلال عدم استخدام البايتات؛ المدخلات bitStringموجودة بالفعل في شكل مصفوفة بتات، ويتم remainderPolynomialالتعامل معها من حيث العمليات الحدودية؛ يمكن أن يكون الضرب في تحولًا إلى اليسار أو اليمين، ويتم إجراء الإضافة إلى المعامل، والذي يمكن أن يكون الطرف الأيمن أو الأيسر للسجل. ${\displaystyle x}$bitString[i+n]${\displaystyle x^{0}}$

هذا الكود له عيبان. أولاً، يتطلب في الواقع سجلاً يحتوي على n +1 بت لاحتواء المعامل remainderPolynomialحتى يمكن اختباره. والأهم من ذلك، يتطلب أن يتم حشوه بـ n بت صفرية. ${\displaystyle x^{n}}$bitString

يمكن حل المشكلة الأولى عن طريق اختبار معامل قبل ضربه بـ . ${\displaystyle x^{n-1}}$remainderPolynomial${\displaystyle x}$

يمكن حل المشكلة الثانية عن طريق تنفيذ التكرارات الأخيرة بشكل مختلف، ولكن هناك تحسين أكثر دقة يتم استخدامه عالميًا، في كل من تنفيذات الأجهزة والبرامج.

نظرًا لأن عملية XOR المستخدمة لطرح متعددة الحدود المولدة من الرسالة هي عملية تبادلية وترابطية ، فلا يهم الترتيب الذي يتم به دمج المدخلات المختلفة في . وعلى وجه التحديد، لا يلزم إضافة بت معين من إلى حتى اللحظة الأخيرة عندما يتم اختباره لتحديد ما إذا كان سيتم مع . remainderPolynomialbitStringremainderPolynomialxorgeneratorPolynomial

يؤدي هذا إلى التخلص من الحاجة إلى التحميل المسبق للبتات nremainderPolynomial الأولى من الرسالة أيضًا:

دالة crc( مصفوفة بت bitString[1..len]، int len) {
    الباقي متعدد الحدود := 0
    // هناك متغير شائع يكمل remainderPolynomial هنا؛ راجع § Preset to −1 أدناه 
    لـ i من 1 إلى len {
        remainderPolynomial := remainderPolynomial xor (bitstring[i] * x n−1 )
         if (معامل x n−1 من remainderPolynomial) = 1 {
            ما تبقى من متعدد الحدود := (ما تبقى من متعدد الحدود * x ) مولد متعدد الحدود
        } آخر {
            الباقي متعدد الحدود := (الباقي متعدد الحدود * x )
        }
    }
    // هناك متغير شائع يكمل remainderPolynomial هنا؛ راجع § عكس ما بعد أدناه 
    إرجاع remainderPolynomial
}

مقطع التعليمات البرمجية 2: قسمة متعددة الحدود باستخدام عملية XOR للرسالة المؤجلة

هذا هو تنفيذ CRC القياسي للبتات في المرة الواحدة، وهو جدير بالدراسة؛ بمجرد فهم سبب حسابه لنفس النتيجة تمامًا مثل الإصدار الأول، فإن التحسينات المتبقية واضحة تمامًا. إذا remainderPolynomialكان طوله n بت فقط، فسيتم تجاهل معاملاته و of ببساطة. هذا هو السبب في أنك سترى عادةً متعددات حدود CRC مكتوبة بالثنائي مع حذف المعامل الرئيسي. ${\displaystyle x^{n}}$generatorPolynomial

في البرمجيات، من المناسب ملاحظة أنه في حين قد يتأخر تنفيذ xorكل بت حتى اللحظة الأخيرة، فمن الممكن أيضًا القيام بذلك في وقت أبكر. عادةً ما يكون من المناسب تنفيذ بايتxor واحد في كل مرة، حتى في التنفيذ بت في كل مرة. هنا، نأخذ المدخلات في بايتات مكونة من 8 بتات:

دالة crc( سلسلة مصفوفة البايتات [1..len]، int len) {
    الباقي متعدد الحدود := 0
    // هناك متغير شائع يكمل remainderPolynomial هنا؛ راجع § Preset to −1 أدناه 
    لـ i من 1 إلى len {
        remainderPolynomial := remainderPolynomial xor  polynomialForm (string[i]) * x n−8 
        لـ j من 1 إلى 8 {     // بافتراض 8 بتات لكل بايت 
            إذا كان معامل x n−1 من remainderPolynomial = 1 {
                ما تبقى من متعدد الحدود := (ما تبقى من متعدد الحدود * x ) مولد متعدد الحدود
            } آخر {
                الباقي متعدد الحدود := (الباقي متعدد الحدود * x )
            }
        }
    }
    // هناك متغير شائع يكمل remainderPolynomial هنا؛ راجع § عكس ما بعد أدناه 
    إرجاع remainderPolynomial
}

مقطع الكود 3: القسمة متعددة الحدود باستخدام عملية XORing للرسائل على أساس البايتات

هذا هو عادةً تنفيذ البرنامج الأكثر إحكاما، والذي يستخدم في وحدات التحكم الدقيقة عندما تكون المساحة ذات أهمية كبيرة مقارنة بالسرعة.

عند التنفيذ في أجهزة تسلسلية للبتات ، يصف متعدد الحدود المولد تعيين البت بشكل فريد؛ البت الأول المنقول هو دائمًا معامل أعلى قوة لـ ، والبتات الأخيرة المنقولة هي باقي CRC ، بدءًا من معامل وانتهاءً بمعامل ، أو معامل 1. ${\displaystyle x}$${\displaystyle n}$${\displaystyle R(x)}$${\displaystyle x^{n-1}}$${\displaystyle x^{0}}$

ومع ذلك، عندما تتم معالجة البتات بايتًا واحدًا في كل مرة، كما هو الحال عند استخدام النقل المتوازي ، أو تأطير البايت كما هو الحال في تشفير 8B/10B أو الاتصال التسلسلي غير المتزامن بنمط RS-232 ، أو عند تنفيذ CRC في البرنامج ، فمن الضروري تحديد ترتيب البتات (endianness) للبيانات؛ أي بت في كل بايت يعتبر "أولاً" وسيكون معامل القوة الأعلى لـ . ${\displaystyle x}$

إذا كانت البيانات مخصصة للاتصال التسلسلي ، فمن الأفضل استخدام ترتيب البتات الذي سيتم إرسال البيانات به في النهاية. وذلك لأن قدرة CRC على اكتشاف أخطاء الانفجار تعتمد على القرب في حدود الرسالة ؛ إذا لم يتم إرسال حدود الحدود المتجاورة بشكل متسلسل، فقد يُنظر إلى انفجار الخطأ المادي بطول واحد على أنه انفجار أطول بسبب إعادة ترتيب البتات. ${\displaystyle M(x)}$

على سبيل المثال، تحدد معايير IEEE 802 ( الإيثرنت ) و RS-232 ( المنفذ التسلسلي ) الإرسال على أساس البت الأقل أهمية أولاً (الطرف الصغير)، لذا فإن تنفيذ CRC البرمجي لحماية البيانات المرسلة عبر مثل هذا الرابط يجب أن يطابق البتات الأقل أهمية في كل بايت مع معاملات أعلى قوى . من ناحية أخرى، تكتب الأقراص المرنة ومعظم محركات الأقراص الصلبة البت الأكثر أهمية في كل بايت أولاً. ${\displaystyle x}$

إن ترتيب البتات من أول بت إلى أول بت أسهل قليلاً في التنفيذ في البرامج، وبالتالي فهو أكثر شيوعًا إلى حد ما، ولكن العديد من المبرمجين يجدون ترتيب البتات من أول بت إلى أول بت أسهل في المتابعة. على سبيل المثال، يستخدم امتداد XMODEM -CRC، وهو استخدام مبكر لترتيب البتات من أول بت إلى أول بت، ترتيب البتات من أول بت إلى أول بت.

حتى الآن، تجنبت شبه التعليمات البرمجية تحديد ترتيب البتات داخل البايتات من خلال وصف التحولات في شبه التعليمات البرمجية كضرب في وكتابة تحويلات صريحة من الشكل الثنائي إلى الشكل متعدد الحدود. في الممارسة العملية، يتم الاحتفاظ بـ CRC في سجل ثنائي قياسي باستخدام اتفاقية ترتيب بت معينة. في شكل msbit-first، سيتم إرسال البتات الثنائية الأكثر أهمية أولاً وبالتالي تحتوي على معاملات متعددة الحدود من الدرجة الأعلى، بينما في شكل lsbit-first، تحتوي البتات الثنائية الأقل أهمية على معاملات من الدرجة الأعلى. يمكن كتابة شبه التعليمات البرمجية أعلاه في كلا الشكلين. من أجل التحديد، يستخدم هذا متعدد الحدود CRC-16- CCITT المكون من 16 بت : ${\displaystyle x}$${\displaystyle x^{16}+x^{12}+x^{5}+1}$

// البت الأكثر أهمية أولاً (الطرف الكبير) 
// (x 16 )+x 12 +x 5 +1 = (1) 0001 0000 0010 0001 = 0x1021 
دالة crc( سلسلة مصفوفة البايتات [1..len]، int len) {
    ريم := 0
    // متغير شائع يكمل rem هنا 
    لـ i من 1 إلى len {
        rem := rem xor (string[i] leftShift (n-8))    // n = 16 في هذا المثال 
        لـ j من 1 إلى 8 {        // بافتراض 8 بتات لكل بايت 
            إذا كان rem و 0x8000 {    // اختبار معامل x 15 
                rem := (rem leftShift 1) xor 0x1021
            } آخر {
                rem := rem leftShift 1
            }
            rem := rem و 0xffff // قم بتقليص الباقي إلى 16 بت
        }
    }
    // متغير شائع يكمل rem هنا 
    return rem
}

مقطع الكود 4: القسمة القائمة على سجل التحويل، MSB أولاً

// البت الأقل أهمية أولاً (الطرف الصغير) 
// 1+x 5 +x 12 +(x 16 ) = 1000 0100 0000 1000 (1) = 0x8408 
دالة crc( سلسلة مصفوفة البايتات [1..len]، int len) {
    ريم := 0
    // متغير شائع يكمل rem هنا 
    لـ i من 1 إلى len {
        rem := rem xor string[i]
         لـ j من 1 إلى 8 {        // بافتراض 8 بتات لكل بايت 
            إذا كان rem و 0x0001 {    // اختبار معامل x 15 
                rem := (rem rightShift 1) xor 0x8408
            } آخر {
                rem := rem يمين التحول 1
            }
        }
    }
    // متغير شائع يكمل rem هنا 
    return rem
}

مقطع الكود 5: القسمة القائمة على سجل التحويل، القسمة الأقل أهمية أولاً

لاحظ أن نموذج lsbit-first يتجنب الحاجة إلى التحويل string[i]قبل xor. وفي كلتا الحالتين، تأكد من إرسال بايتات CRC بالترتيب الذي يتطابق مع اتفاقية ترتيب البتات التي اخترتها.

تستخدم عملية تحسين شائعة أخرى جدول بحث مفهرس حسب أعلى معاملات الترتيب remلمعالجة أكثر من بت واحد من الأرباح لكل تكرار. ^[3] في أغلب الأحيان، يتم استخدام جدول بحث مكون من 256 إدخالاً، واستبدال نص الحلقة الخارجية (فوق i) بما يلي:

// Msbit-أولا
rem = (rem leftShift 8) xor big_endian_table[string[i] xor ((أقصى 8 بتات من rem) rightShift (n-8))]
// Lsbit-أولا
rem = (rem rightShift 8) xor little_endian_table[string[i] xor (أقصى 8 بتات من rem)]

مقطع الكود 6: نوى التقسيم المستند إلى الجدول

تُعرف إحدى خوارزميات CRC الأكثر شيوعًا باسم CRC-32 ، والتي تستخدمها (من بين أمور أخرى) Ethernet و FDDI و ZIP وتنسيقات الأرشيف الأخرى وتنسيق صور PNG . يمكن كتابة كثير الحدود الخاص بها msbit-first كـ 0x04C11DB7، أو lsbit-first كـ 0xEDB88320. تتضمن صفحة ويب W3C على PNG ملحقًا بتنفيذ قصير وبسيط مدفوع بالجدول في C لـ CRC-32. ^[4] ستلاحظ أن الكود يتوافق مع الكود الزائف lsbit-first byte-at-a-time المقدم هنا، ويتم إنشاء الجدول باستخدام كود bit-at-a-time.

عادةً ما يكون استخدام جدول يحتوي على 256 إدخالاً هو الحل الأكثر ملاءمة، ولكن يمكن استخدام أحجام أخرى. في وحدات التحكم الدقيقة الصغيرة، يؤدي استخدام جدول يحتوي على 16 إدخالاً لمعالجة أربعة بتات في المرة الواحدة إلى تحسين السرعة بشكل مفيد مع الحفاظ على حجم الجدول صغيرًا. في أجهزة الكمبيوتر ذات سعة التخزين الكبيرة،65 536 -يمكن استخدام جدول الإدخال لمعالجة 16 بت في المرة الواحدة.

إن البرنامج المستخدم في إنشاء الجداول صغير وسريع للغاية، لذا فإن حسابها عند بدء تشغيل البرنامج يكون أسرع عادةً من تحميل الجداول المحسوبة مسبقًا من وحدة التخزين. إحدى التقنيات الشائعة هي استخدام الكود بت في كل مرة 256 مرة لإنشاء CRCs لـ 256 بايت ممكن من 8 بتات. ومع ذلك، يمكن تحسين ذلك بشكل كبير من خلال الاستفادة من الخاصية التي . فقط إدخالات الجدول المقابلة لقوى اثنين تحتاج إلى الحساب مباشرة. table[i xor j] == table[i] xor table[j]

في مثال الكود التالي، crcيحمل القيمة table[i]:

جدول big_endian_table[0] := 0
crc := 0x8000 // بافتراض حدود مكونة من 16 بت
انا := 1
افعل {
     إذا كان crc و 0x8000 {
        crc := (crc leftShift 1) xor 0x1021 // متعدد الحدود CRC 
    } else {
        crc := crc تحول إلى اليسار 1
    }
    // crc هي قيمة big_endian_table[i] ؛ دع j يتكرر على الإدخالات التي تم تهيئتها بالفعل 
    لـ j من 0 إلى i−1 {
        big_endian_table[i + j] := crc xor big_endian_table[j];
    }
    i := i تحول إلى اليسار 1
} بينما i < 256

مقطع التعليمات البرمجية 7: إنشاء جدول CRC لكل بايت في المرة، أولاً من خلال MSB

جدول النهاية الصغير[0] := 0
كرك := 1؛
انا := 128
افعل {
     إذا كان crc و 1 {
        crc := (crc rightShift 1) xor 0x8408 // متعدد الحدود CRC 
    } else {
        crc := crc تحويل يمين 1
    }
    // crc هي قيمة little_endian_table[i] ؛ دع j يتكرر على الإدخالات التي تم تهيئتها بالفعل 
    لـ j من 0 إلى 255 بواسطة 2 × i {
        little_endian_table[i + j] := crc xor little_endian_table[j];
    }
    i := i تحويل لليمين 1
} بينما i > 0

مقطع التعليمات البرمجية 8: إنشاء جدول CRC لكل بايت في المرة، أولاً LSB

في نماذج التعليمات البرمجية هذه، يكون فهرس الجدول i + jمعادلاً لـ ؛ يمكنك استخدام أي نموذج أكثر ملاءمة. i xor j

هذه خوارزمية عملية لمتغير CRC-32 من CRC. ^[5] CRCTable عبارة عن حفظ مؤقت لحساب يجب تكراره لكل بايت من الرسالة (حساب عمليات التحقق من التكرار الدوري § الحساب متعدد البتات).

وظيفة CRC32
    الإدخال: 
      البيانات: البايتات      // مجموعة من البايتات 
   الإخراج: 
      crc32: UInt32     // قيمة CRC-32 غير موقعة 32 بت 

// تهيئة CRC-32 إلى القيمة الأولية 
crc32 ← 0xFFFFFFFF 

لكل بايت في البيانات
   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 عبارة عن مجموعة من 256 ثابتًا مكونًا من 32 بت } // أنهي قيمة CRC-32 عن طريق عكس جميع البتات crc32 ^= 0xFFFFFFFFu ؛ return crc32 ؛ }      
	   
	
	         
		        
		        
	
	
	
	  
	 

توجد خوارزمية تقطيع حسب n (عادةً تقطيع حسب 8 لـ CRC32) والتي عادةً ما تضاعف أو تضاعف الأداء مقارنةً بخوارزمية Sarwate. فبدلاً من قراءة 8 بتات في المرة الواحدة، تقرأ الخوارزمية 8 n بت في المرة الواحدة. يؤدي القيام بذلك إلى تعظيم الأداء على المعالجات الفائقة . ^{[6] [7] [8] [9]}

من غير الواضح من هو الذي اخترع الخوارزمية فعليًا. ^[10]

لفهم المزايا، ابدأ بحالة التقطيع حسب 2. نرغب في حساب CRC مكون من 2 بايت (16 بت) في المرة الواحدة، ولكن النهج القياسي القائم على الجدول يتطلب جدولًا كبيرًا غير مريح يحتوي على 65536 إدخالاً. وكما ذكرنا في § توليد الجداول، تحتوي جداول CRC على الخاصية التي مفادها أن . يمكننا استخدام هذه الهوية لاستبدال الجدول الكبير بجدولين يحتوي كل منهما على 256 إدخالاً: . table[i xor j] = table[i] xor table[j]table[i + 256×j] = table_low[i] xor table_high[j]

لذا فإن الجدول الكبير لا يتم تخزينه صراحةً، ولكن كل تكرار يحسب قيمة CRC التي ستكون موجودة من خلال الجمع بين القيم في جدولين أصغر. أي أن الفهرس المكون من 16 بت "مقسم" إلى فهرسين مكونين من 8 بت. للوهلة الأولى، يبدو هذا بلا معنى؛ لماذا يتم إجراء بحثين في جدولين منفصلين، بينما تقوم خوارزمية البايت في المرة القياسية بإجراء بحثين في نفس الجدول؟

الفرق هو التوازي على مستوى التعليمات . في الخوارزمية القياسية، يعتمد مؤشر كل عملية بحث على القيمة التي تم جلبها في العملية السابقة. وبالتالي، لا يمكن بدء عملية البحث الثانية حتى اكتمال عملية البحث الأولى.

عند استخدام الجداول المقسمة، يمكن بدء عمليتي البحث في نفس الوقت. إذا كان المعالج قادرًا على تنفيذ حمولتين بالتوازي (تستطيع المعالجات الدقيقة في عشرينيات القرن العشرين تتبع أكثر من 100 عملية تحميل قيد التقدم)، فإن هذا من شأنه أن يضاعف سرعة الحلقة الداخلية.

من الواضح أن هذه التقنية يمكن توسيعها لتشمل العديد من الشرائح التي يمكن للمعالج الاستفادة منها.

عندما يساوي عرض التقطيع حجم CRC، يحدث تسريع طفيف. في جزء من خوارزمية Sarwate الأساسية حيث يتم تحويل قيمة CRC السابقة بحجم البحث في الجدول، يتم تحويل قيمة CRC السابقة بالكامل (ما تبقى هو صفر بالكامل)، وبالتالي يمكن إزالة XOR من المسار الحرج.

تتكون الحلقة الداخلية المقطعة بواسطة n الناتجة من:

1. XOR CRC الحالي مع البايتات n التالية من الرسالة،
2. ابحث عن كل بايت من القيمة الناتجة في جداول الشرائح n ، ثم
3. قم بإجراء عملية XOR على النتائج n للحصول على CRC التالي.

لا تزال هذه الخاصية تتضمن ضرورة اكتمال جميع عمليات التحميل في الخطوة الثانية قبل بدء التكرار التالي، مما يؤدي إلى توقفات منتظمة لا يتم خلالها استخدام نظام ذاكرة المعالج (خاصة ذاكرة التخزين المؤقت للبيانات). ومع ذلك، عندما يتجاوز عرض التقطيع حجم CRC، تظهر زيادة كبيرة في السرعة الثانية.

يرجع هذا إلى أن جزءًا من نتائج الخطوة الأولى لم يعد يعتمد على أي تكرار سابق. عند استخدام XOR لـ CRC مكون من 32 بتًا مع 64 بتًا من الرسالة، فإن نصف النتيجة عبارة عن نسخة من الرسالة ببساطة. إذا تم ترميزها بعناية (لتجنب إنشاء اعتماد خاطئ على البيانات )، فيمكن أن تبدأ نصف عمليات تحميل جدول الشرائح قبل اكتمال تكرار الحلقة السابق. والنتيجة هي عمل كافٍ لإبقاء نظام ذاكرة المعالج مشغولاً باستمرار ، مما يحقق أقصى أداء. وكما ذكرنا، في المعالجات الدقيقة بعد عام 2000، يكون التقطيع حسب 8 كافيًا بشكل عام للوصول إلى هذا المستوى.

لا توجد حاجة خاصة لأن تكون الشرائح بعرض 8 بتات. على سبيل المثال، سيكون من الممكن تمامًا حساب CRC 64 بتًا في المرة الواحدة باستخدام خوارزمية الشريحة حسب 9، باستخدام 9 جداول بحث تحتوي على 128 إدخالاً للتعامل مع 63 بتًا، ويتم التعامل مع البت رقم 64 بواسطة خوارزمية البت في المرة الواحدة (وهي في الواقع جدول بحث يحتوي على بت واحد ومدخلين). سيؤدي هذا إلى تقليص حجم الجدول إلى النصف تقريبًا (من 8×256 = 2048 إدخالاً إلى 9×128 = 1152) على حساب تحميل إضافي يعتمد على البيانات لكل تكرار.

يمكن أيضًا إجراء التحديث المتوازي لبايت أو كلمة في كل مرة بشكل صريح، دون جدول. ^[11] يُستخدم هذا عادةً في تنفيذات الأجهزة عالية السرعة. لكل بت، يتم حل معادلة بعد تحويل 8 بتات. تسرد الجداول التالية معادلات بعض الحدوديات المستخدمة بشكل شائع، باستخدام الرموز التالية:

ر 0 ←
ر 1 ←
ر 2 ←
ر 3 ←
ر 4 ←
ر 5 ←
ر 6 ←
ر 7 ←

0
ه 0 + ه 4 + ه 7 
ه 1 + ه 5 ه 2 + ه 6 
ه 3 + ه 7      + ه 0 + ه 
4 + ه 7 ه 4     + ه 1 
+ ه 5 
ه 5 + ه 2 + ه 6 
ه 6 + ه 3 + ه 7                          

ه 0     + ه 4 + ه 1 + ه 0    + ه 5 + ه 2 + ه 1 
ه 1 + ه 5 + ه 2 + ه 1    + ه 6 + ه 3 + ه 2 + ه 0 
ه 2 + ه 6 + ه 3 + ه 2 + ه 0    + ه 7 + ه 4 + ه 3 + ه 1 
ه 3 + ه 0 + ه 7 + ه 4 + ه 3 + ه 1 
ه 4 + ه 1 + ه 0 
ه 5 + ه 2 + ه 1 
ه 6 + ه 3 + ه 2 + ه 0 
ه 7 + ه 4 + ه 3 + ه 1                                         

 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 );     
 
     
               
           

ر 0 ←
ر 1 ←
ر 2 ←
ر 3 ←
ر 4 ←
ر 5 ←
ر 6 ←
ر 7 ←
ر 8 ←
ر 9 ←
ر 10 ←
ر 11 ←
ر 12 ←
ر 13 ←
ر 14 ←
ر 15 ←

س 4 + س 0 
س 5 + س 1 
س 6 + س 2 
س 7 + س 3
      س 4
      س 5   + س 4 + س 0
      س 6   + س 5 + س 1
      س 7   + س 6 + س 2 
ج 0        + س 7 + س 3 
ج 1     + س 4 
ج 2 + س 5 
ج 3 + س 6 
ج 4 + س 7   + س 4 + س 0 
ج 5   + س 5 + س 1 
ج 6   + س 6 + س 2 
ج 7   + س 7 + س 3                                                                                        

ج 8      + ه 4 + ه 0 
ج 9   + ه 5 + ه 1 
ج 10   + ه 6 + ه 2 
ج 11   + ه 0   + ه 7 + ه 3 
ج 12   + ه 1 
ج 13   + ه 2 
ج 14   + ه 3 
ج 15   + ه 4 + ه 0   ه 0   + ه 5 + ه 1   ه 1   + ه 6 + ه 2   ه 2   + ه 7 + ه   3 ه 3   ه 4 + ه 0   ه 5 + ه 1   ه 6 + ه 2   ه 7 + ه 3                                               
   
   
   
   
   
   
   
   

 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 )؛    
   
 
     
       
      
        
        
       

ر 0 ←
ر 1 ←
ر 2 ←
ر 3 ←
ر 4 ←
ر 5 ←
ر 6 ←
ر 7 ←
ر 8 ←
ر 9 ←
ر 10 ←
ر 11 ←
ر 12 ←
ر 13 ←
ر 14 ←
ر 15 ←

          س س
     0 + س س    س 1 + س 0    س 2 + س 1    س 3 + س 2    س 4 + س 3    س 5 + س 4    س 6 + س 5 
ج 0 + س 7 + س 6 
ج 1 + س 7 
ج 2 
ج 3 
ج 4 
ج 5 
ج 6 
ج 7 + س س      
       
       
       
       
       
                      

ج 8     + ه ص 
ج 9 
ج 10 
ج 11 
ج 12 
ج 13 
ج 14 + ه 0 
ج 15 + ه 1 + ه 0    ه 2 + ه 1    ه 3 + ه 2    ه 4 + ه 3    ه 5 + ه 4    ه 6 + ه 5    ه 7 + ه 6    ه ص + ه 7    ه ص      
   
   
   
   
   
   
   
        

 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 يحتوي على عدد كبير من الحدود، فعند حساب الباقي بايتًا واحدًا في كل مرة، يعتمد كل بت على ما يصل إلى 8 بتات من التكرار السابق. في تنفيذات الأجهزة المتوازية للبايتات، يتطلب هذا إما بوابات XOR ذات 8 مدخلات أو متتالية مما يزيد من تأخير الانتشار .

لتعظيم سرعة الحساب، يمكن حساب الباقي الوسيط عن طريق حساب CRC للرسالة أولاً modulo x ¹²³ + x ¹¹¹ + x ⁹² + x ⁸⁴ + x ⁶⁴ + x ⁴⁶ + x ²³ + 1. هذا مضاعف تم اختياره بعناية لكثيرة حدود CRC-32 بحيث تكون الحدود (صنابير التغذية الراجعة) على الأقل 8 مواضع منفصلة. وبالتالي، يمكن تقدم سجل تحويل 123 بت بمقدار 8 بتات لكل تكرار باستخدام بوابات XOR ذات مدخلين فقط، وهي الأسرع الممكنة. أخيرًا، يمكن تقليل الباقي الوسيط modulo متعدد الحدود القياسي في سجل تحويل ثانٍ للحصول على باقي CRC-32. ^[12]