حاسبة القسمة الطويلة CRC / XOR / modulo 2

كيف تستخدم حاسبة CRC / XOR / modulo 2

لحساب CRC بقسمة modulo 2، اتبع هذه الخطوات الأربع:

• أدخل الرسالة الثنائية (بتات البيانات) في الحقل الأول.
• أدخل كثير الحدود المولّد كبتات ثنائية في الحقل الثاني.
• تُلحق الحاسبة (n − 1) صفراً، حيث n طول المولّد.
• انقر احسب للـ XOR عبر الرسالة واقرأ الباقي كـ CRC.

الناتج يُتجاهل عادة في عمل CRC — الباقي هو المجموع الاختباري الذي يُلحق بالرسالة قبل الإرسال.

CRC وحساب modulo 2

فحص التكرار الدوري يكتشف أخطاء الإرسال بمعاملة الرسالة ككثير حدود ثنائي كبير وقسمتها على كثير حدود مولّد متفق عليه. القسمة في modulo 2 (GF(2))، حيث الجمع والطرح متطابقان ويساويان XOR — لا حمل ولا استلاف. الباقي من هذه القسمة هو CRC. عندما يقسم المستقبل الرسالة + CRC على نفس المولّد، باقٍ 0 يعني عدم اكتشاف خطأ. هذه الحاسبة تعيد ذلك العمل bitwise بالضبط.

كيف تعمل قسمة CRC modulo 2

الحاسبة تحسب CRC عبر خمس إجراءات داخلية:

• تُلحق (n − 1) صفراً للرسالة، حيث n عدد بتات المولّد.
• تُحاذي المولّد تحت أيسر 1 bit في الباقي الحالي.
• تُ XOR المولّد في تلك البتات (طرح modulo 2 بلا استلاف).
• تنتقل إلى leading 1 التالي وتكرر محاذاة XOR.
• تتوقف عندما تبقى بتات أقل من المولّد؛ تلك البتات هي CRC.

كل bit ناتج 1 حيث يُ XOR المولّد و0 في غير ذلك، لكن لـ CRC الباقي النهائي فقط يهم.

صيغة قسمة CRC

حاسبة CRC / XOR / modulo 2 تحسب CRC = (M(x) · xⁿ⁻¹) mod G(x) في GF(2)، حيث M(x) الرسالة، G(x) المولّد من n بت، وكل الجمع XOR. الإطار المرسل M(x)·xⁿ⁻¹ + CRC، الذي G(x) يقسمه بالضبط. في الاستقبال، باقٍ 0 يؤكد السلامة.

مسائل مثال CRC / XOR

هذه الأمثلة تعرض قسمة modulo 2 مع XOR في كل خطوة.

مثال 1 — رسالة 1101، مولّد 101

1. طول المولّد 3، إذن ألحق 2 صفراً: 1101 تصبح 110100.
2. XOR 101 في البتات الأولى بشكل متكرر: 110100 → 011100 → 001000 → 000010.
3. آخر 2 بت، 10، هما باقي CRC.

مثال 2 — لماذا الطرح هو XOR

1. في modulo 2، 1 + 1 = 0 و1 − 1 = 0، فالجمع والطرح نفس العملية.
2. تلك العملية هي XOR bitwise، بلا حمل أو استلاف.
3. إذن كل خطوة قسمة XOR واحدة للمولّد في البتات الحالية.

مثال 3 — تحقق المستقبل

1. ألحق CRC للرسالة واقسم على نفس المولّد.
2. XOR للأسفل كما قبل.
3. باقٍ 0 يعني عدم اكتشاف خطأ.

طول المولّد 3، إذن ألحق 2 صفراً: 1101 تصبح 110100.
XOR 101 في البتات الأولى بشكل متكرر: 110100 → 011100 → 001000 → 000010.
آخر 2 بت، 10، هما باقي CRC.

في modulo 2، 1 + 1 = 0 و1 − 1 = 0، فالجمع والطرح نفس العملية.
تلك العملية هي XOR bitwise، بلا حمل أو استلاف.
إذن كل خطوة قسمة XOR واحدة للمولّد في البتات الحالية.

ألحق CRC للرسالة واقسم على نفس المولّد.
XOR للأسفل كما قبل.
باقٍ 0 يعني عدم اكتشاف خطأ.

مسائل CRC محلولة

كيف تحسب CRC لـ 10110 بمولّد 1011؟

ألحق 3 أصفار (طول المولّد 4) للحصول على 10110000، ثم XOR للأسفل. حاذِ 1011 تحت كل leading 1 وXOR: 10110000 → … → آخر 3 بتات تشكل باقي CRC. يُلحق الباقي بـ 10110 ليصبح الإطار الكامل قابلاً للقسمة على 1011 بلا باقٍ.

لماذا باقٍ 0 يعني أن البيانات سليمة؟

المرسل اختار CRC بحيث يكون الإطار المرسل مضاعفاً دقيقاً للمولّد. أي مضاعف لـ G(x) مقسوماً على G(x) يترك باقياً 0. إن قلبت بتات في الطريق، الإطار عادة لا يعود مضاعفاً، فيترك قسمة المستقبل باقياً غير صفري، مُعلّماً خطأ.

أخطاء شائعة في CRC / modulo 2

قسمة CRC modulo 2 تُنتج 5 أخطاء متكررة:

• استخدام طرح ثنائي عادي مع استلاف بدلاً من XOR.
• إلحاق عدد خاطئ من الأصفار (يجب أن يكون طول المولّد ناقص واحد).
• محاذاة المولّد تحت 0 bit بدلاً من leading 1.
• التعامل مع حمل كأنه موجود في GF(2).
• الإبلاغ عن الناتج كـ CRC بدلاً من الباقي.

حاسبة CRC / XOR / modulo 2 تُ XOR في كل خطوة، تُلحق الأصفار الصحيحة، وتُرجع الباقي كمجموع اختباري.

الأسئلة الشائعة