בדיקת יתירות מחזורית

בדיקת יתירות מחזורית (CRC) היא קוד לאיתור שגיאות בהעברת נתונים. קודם לשליחה מחשבים ערך בדיקה שמוסיפים לנתונים. בצד המקבל מחשבים שוב את ה‑CRC ומוודאים שהנתונים לא השתנו.

CRC פופולרי כי קל לממש אותו בחומרה דיגיטלית. הוא גם קל לחישוב ומתאים במיוחד לזיהוי פרצי שגיאות, שגיאות רצופות שנוצרות בערוצי תקשורת רועשים.


מושג ה‑CRC מבוסס על קודים מחזוריים. רעיון מרכזי הוא להציג רצף ביטים כפולינום מתמטי. כדי להגדיר CRC צריך לבחור פולינום יוצר. פולינום זה קובע את גודל השארית שנשארת אחרי חילוק במודולו 2. שדה סופי, מערכת מספרית עם שני ערכים בלבד (0 ו‑1), משמש כאן כי הוא מתאים לייצוג ביטים.

CRC‑n מצביע על גודל ערך הבדיקה (n ביטים). באופן טיפוסי CRC‑n יאתר כל פרץ שגיאות שאורכו קטן או שווה ל‑n ביטים. דוגמה פשוטה היא סיבית הזוגיות, שהיא למעשה CRC של 1‑bit. הפולינום המתאים לזה הוא x+1.


כדי לחשב CRC על הודעה M עם פולינום מדרגה r עושים כך:
1) מוסיפים r אפסים בסוף ההודעה.
2) מחלקים את האפנדד בהינתן הפולינום, בחישוב במודולו 2 (כלומר משתמשים ב‑XOR במקום חיסור רגיל).
3) השארית שמתקבלת היא ערך ה‑CRC. מצרפים אותה להודעה ושולחים.

המקבל מבצע את אותם שלבים ומוודא שה‑r הביטים האחרונים תואמים לשארית המחושבת. אם הם שונים, יש שגיאה בהעברה.

בדיקת יתירות מחזורית (CRC) בודקת אם נתון הגיע שלם. לפני ששולחים מחשבים מספר קטן שמוסיפים לנתונים. המחשבים בצד השני מחשבים שוב את המספר הזה.

אם המספרים זהים, הנתון הגיע כמו שצריך. אם לא, משהו השתבש בדרך.


CRC משתמש ברעיון של המרת רצף ביטים ל"פולינום". פולינום כאן זה דרך למספר את הביטים. במקום חישוב רגיל עושים חיבור בלי נשיאה, שנקרא XOR.

דוגמה קלה היא סיבית זוגיות. זו בדיקה של 1‑bit. הפולינום שלה הוא x+1.


איך מחשבים CRC:
1) מוסיפים כמה אפסים בסוף ההודעה.
2) מחלקים את המספר בפולינום בעזרת חיבור XOR.
3) השארית היא ערך ה‑CRC. מצרפים אותה ושולחים.

המקבל עושה את אותם שלבים. אם השאריות לא תואמות, המידע נשבר בדרך.