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

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף Cyclic redundancy check)
קפיצה אל: ניווט, חיפוש

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

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

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

מבוא[עריכת קוד מקור | עריכה]

CRC מבוסס על תאוריה של קוד למחזור שגיאות מתוקנות. השימוש במחזור קוד שיטתי, אשר מקודד הודעות על ידי הוספה של ערך בדיקה עם גודל מתוקן, בשביל איתור שגיאות בתקשורת רשתות. CRC הוצג לראשונה על ידי וו. ווסלי פטרסון ב-1961. קודים ממוחזרים הם לא רק דוגמה להטמעה, אלא הם גם טובים במיוחד לאיתור burst errors בהודעות עם נתונים אשר נשלחות ברצף. זה חשוב בגלל שburst errors הם בעיות העברה נפוצות בערוצי תקשורת, אשר כוללים התקני אחסון מגנטיים ואופטיים. n bit CRC טיפוסי אשר מוצמד לבלוק מידע עם אורך שרירותי יאתר כל שגיאת פתע אשר לא גדולה יותר מ n bits  ויאתר 1 − 2n מהburst errors הגדולות מn bits.

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

למעשה, כל השימושים הנפוצים ב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 הביטים האחרונים שנשלחו זהים לתוצאה שהתקבלה.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Peterson, W. W. and Brown, D. T, Cyclic Codes for Error Detection, Proceedings of the IRE 49, 49(1), עמ' 228-235
P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.