הצגת המקור של הדף "בדיקת יתירות מחזורית"

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

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

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

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

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

אפיון של קוד CRC דורש הגדרה של מה שנקרא [[פולינום יוצר]]. הפולינום הזה נעשה מחלק של ה-[[polynomial long division]], אשר לוקח את ההודעה כמחולקת ומחסיר את המנה והיתרה היא התוצאה. האזהרה החשובה היא כאשר ה[[מקדם (מתמטיקה)|מקדם]] הפולינומי שחושב בהתאם ל[[שדה סופי|שדה הסופי]] האריתמטי, כך שפעולה נוספת יכולה לממש רוחב בתים מקבלים (אין משיכה בין ספרות). הגודל של השארית הוא תמיד נמוך מהגודל של המחולל הפולינומי, אשר ממחיש כמה גדולה התוצאה יכולה להיות.{{הערה|{{צ-מאמר|מחבר = Peterson, W. W. and Brown, D. T|שם = Cyclic Codes for Error Detection|כתב עת = Proceedings of the IRE 49|כרך = 49(1)|עמ = 228-235}}}}

למעשה, כל השימושים הנפוצים ב-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 שברצוננו לקדד, עלינו לבצע את הפעולות הבאות:
# נוסיף r אפסים מימין להודעה.
# נחלק בפולינום (תוך שימוש בחילוק של ה[[שדה (מבנה אלגברי)|שדה]] [[מודולו]] 2)
# נחסר את השארית תוך שימוש ב-[[xor]] במקום בחיסור רגיל.
נצרף את התוצאה שקיבלנו מימין להודעה המקורית ונשלח.

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

==ראו גם==
* [[cksum]]
* [[סיכום ביקורת]]

==קישורים חיצוניים==
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:פונקציות גיבוב]]
[[קטגוריה:קודים לאיתור שגיאות ולתיקונן]]