סיכום ביקורת

במדעי המחשב סיכום ביקורת (באנגלית: Checksum) הוא קוד לזיהוי שגיאות, המאפשר זיהוי של שגיאות ובמקרים מסוימים אף את תיקונן באמצעות יתירות (כלומר באמצעות מידע עודף, באנגלית: Redundancy).

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

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

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

לדוגמה, בחלוקת המידע הבא לבתים: 0x52, 0x25, 0x62, 0x3F (סה"כ 4 בתים לפי כתיב הקסדצימלי):

מסכמים את כל הבתים ומקבלים 0x118.
מבצעים מודולו ל-256 שהוא גודל בית (שקול להורדת ביט מספר 9 והלאה) ומקבלים 0x18.
במקרים מסוימים נהוג גם לחשב משלים ל-2. במקרה זה מקבלים 0xE8. זהו סיכום הביקורת.

החסרונות של שיטה זו:
 אינה מבחינה בהוספת אפסים
 אינה מבחינה בשינוי סדר של בתים
 אינה מבחינה במספר טעויות שסכומן אפס

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

פונקציות יתירות נוספות נפוצות:
 CRC
 קוד המינג
 סיבית זוגיות (Parity Bit)
  Fletcher's checksum
  Adler-32

לפעמים מכנים כל פונקציית יתירות בשם "checksum".

 דוגמה למימוש פונקציית checksum בשפת C 
unsigned short int calculate_checksum(void *data, unsigned int bytes) {
	unsigned short int *data_pointer = (unsigned short int *)data;
	unsigned int total_sum = 0;

	// Main summing loop
	while (bytes > 1)
	{
		total_sum += *data_pointer++;
		bytes -= 2;
	}

	// Add left-over byte, if any
	if (bytes > 0)
		total_sum += *((unsigned char *)data_pointer);

	// Fold 32-bit sum to 16 bits
	while (total_sum >> 16)
		total_sum = (total_sum & 0xFFFF) + (total_sum >> 16);

	return (~((unsigned short int)total_sum));
}

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



קטגוריה:קודים לאיתור שגיאות ולתיקונן