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

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

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

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

אופן הפעולה

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

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

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

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

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

ראו גם

• קוד ציקלי

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.