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

בדיקת יתירות מחזורית (באנגלית: Cyclic redundancy check, או בקיצור CRC) היא סוג של קוד לאיתור שגיאות המשמש לאיתור שגיאות בהעברת נתונים.

לפני העברת המידע מחושב ה־CRC ומתווסף למידע המועבר. לאחר העברת המידע, הצד המקבל מאשר באמצעות ה־CRC שהמידע הועבר ללא שינויים.

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

מבוא

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

${\text{CRC-}}n$ סיביות טיפוסי אשר מוצמד לבלוק מידע באורך שרירותי יאתר כל שגיאת פתע שאינה גדולה מ-$n$ סיביות ויאתר כמות של $(1-2^{-n})$ מפרצי שגיאות הגדולות מ-$n$ סיביות.

אפיון של קוד CRC דורש הגדרה של מה שנקרא פולינום יוצר. הפולינום הזה נעשה מחלק של ה-polynomial long division, אשר לוקח את ההודעה כמחולקת ומחסיר את המנה והיתרה היא התוצאה. האזהרה החשובה היא כאשר המקדם הפולינומי שחושב בהתאם לשדה הסופי האריתמטי, כך שפעולה נוספת יכולה לממש רוחב בתים מקבלים (אין משיכה בין ספרות). הגודל של השארית הוא תמיד נמוך מהגודל של המחולל הפולינומי, אשר ממחיש כמה גדולה התוצאה יכולה להיות.

למעשה, כל השימושים הנפוצים ב-CRC משתמשים בשדה סופי של שני אלמנטים. שני האלמנטים בדרך כלל נקראים 1 ו-0, שבאופן נוח ביותר תואם לארכיטקטורה של המחשב.

CRC נקרא n-bit כאשר ערך הבדיקה בגודל n-bit. ל-n נתון, יש מספר CRC אפשריים, כל אחד כזה בפולינום שונה לפולינום כזה יכול להיות n כמעלה הגבוהה ביותר, כלומר n+1 ביטויים. במילים אחרות, לפולינום בגודל של n+1, הקידוד שלו דורש n+1  בתים. רוב הפולינומים מאפיינים ירידה בביט של ה-MSB או LSB, מכיוון שהם תמיד 1. ל-CRC והפולינום המקושר יש שם במבנה הזה  CRC-n-XXX.

מערכת איתור הבעיות הפשוטה ביותר, סיבית זוגיות, הוא למעשה CRC של 1-bit. הפולינום המתאים הוא x+1 (שני ביטויים) ושמו הוא CRC-1.

אופן הפעולה

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

בהינתן פולינום יוצר מדרגה r ובהינתן הודעה M שברצוננו לקדד, עלינו לבצע את הפעולות הבאות:

1. נוסיף r אפסים מימין להודעה.
2. נחלק בפולינום (תוך שימוש בחילוק של השדה מודולו 2)
3. נחסר את השארית תוך שימוש ב-xor במקום בחיסור רגיל.

נצרף את התוצאה שקיבלנו מימין להודעה המקורית ונשלח.

כמו בכל קידוד Checksum, הצד המקבל יבצע את שלבים 1 ו-2 ויוודא ש-r הביטים האחרונים שנשלחו זהים לתוצאה שהתקבלה.

ראו גם

• cksum
• סיכום ביקורת

קישורים חיצוניים

• בדיקת יתירות מחזורית, באתר MathWorld (באנגלית)