שינויים

קפיצה אל: ניווט, חיפוש

מבנים אלגבריים למדעי המחשב - ארז שיינר

נוספו 2 בתים, 11:33, 21 בדצמבר 2017
/* מרחק המינג */
*טענה: אם <math>d_{min}\geq 2n+1</math> אז הקוד מסוגל לזהות עד <math>2n</math> שגיאות ולתקן עד <math>n</math> שגיאות.
*הוכחה:
**אם כמות השגיאות קטנה או שווה ל<math>2n</math> המילה שנשלחה שהתקבלה בוודאות אינה חוקית, כיוון שהמרחק המינימלי בין שתי מילים חוקיות גדול או שווה ל<math>2n+1</math>.
**אם כמות השגיאות קטנה או שווה ל<math>n</math> יש בדיוק מילה חוקית אחת שיכולה להיות המקור.
**אחרת, ניתן להגיע ע"י n שגיאות משתי מילים חוקיות למילה שקיבלנו, כלומר המרחק בין שתי המילים החוקיות קטן או שווה ל<math>2n</math>, בסתירה.