קוד המינג

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

המינג עבד במעבדות בל על מחשבים שקראו כרטיסים מנוקבים. בעיות בקריאת הכרטיסים גרמו לו לפתח שיטות אוטומטיות לתיקון שגיאות. בשנת 1950 פרסם את קוד המינג, שנותר שימושי עד היום.

לפני המינג נעשה שימוש בקודים פשוטים. שני דוגמאות מייצגות את הגישה: סיבית זוגיות וקוד הישנות (שכפול ביטים).

סיבית זוגיות (parity bit) מוסיפה ביט אחד שאומר אם מספר הביטים שערכם 1 הוא זוגי או אי-זוגי. היא מזהה שגיאות כאשר מספר הביטים שמשתבשים הוא אי-זוגי. חסרונה: אם שתי סיביות משתבשות, זוגיות לא תגלה זאת.

ב״הישנות״ משכפלים כל סיבית מספר פעמים, למשל 3 פעמים. השיטה פשוטה, אבל לא יעילה. היא דורשת הרבה סיביות ויכולה לטעות אם משתבשות יותר מסיבית אחת.

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

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

מספר הסיביות הנוספות r צריך להיות מספיק גדול כדי לציין גם את מילות הקוד וגם את כל הווריאציות של שגיאה בסיבית בודדת. מתקיים החסם m+r+1 <== 2^r. קוד המינג מממש את החסם הזה במקרים מקסימליים, ולכן הוא אופטימלי מבחינת סיביות היתרה לתיקון שגיאה בסיבית בודדת.

בגרסה הנפוצה (7,4) מוסיפים 3 סיביות זוגיות ל-4 סיביות מידע. כך ניתן לתקן כל שגיאה בסיבית אחת ולהבחין בשגיאה בשתי סיביות. ב־(11,7) יש דוגמה שבה הסינדרום מצביע על הסיבית ה־11 כשזו משתבשת.

במימוש מעשי משתמשים במטריצות G (ליצירת מילת הקוד) ו־H (לבדיקת זוגיות). מקודדים על ידי מכפלת G בווקטור המידע במודולו-2. המקבל מחשב את H·r כדי לקבל את הסינדרום. אם הסינדרום שווה לעמודה ה-i של H, השגיאה היא בסיבית ה-i וניתן לתקנה.

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

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

קוד המינג הוא דרך למצוא ולתקן טעויות בביטים (סיביות). סיבית היא יחידה קטנה של מידע. המטרה היא לתקן ביט אחד שבור.

ריצ'רד המינג עבד במעבדות בל. הוא רצה שמשדרים יהיו אמינים יותר. ב־1950 הוא המציא את קוד המינג.

סיבית זוגיות היא ביט שמראה אם יש מספר זוגי של 1 בביטים. אם המספר נשבר, יודעים שמשהו השתבש.

בדרך פשוטה משכפלים ביט שלוש פעמים. למשל 1 → 111. אם רק ביט אחד משתבש, רוב הקולות ינחו להחליט נכון.

מוסיפים כמה סיביות מיוחדות במקומות 1,2,4,8... כל סיבית מיוחדת בודקת קבוצת ביטים לפי חוק. כאשר מקבלים את המילה, מחשבים ערך שנקרא סינדרום. הסינדרום מראה איזו סיבית השתבשה. אם הסינדרום אפס, הכול בסדר.

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

אם מוסיפים סיבית בדיקה נוספת שמסתכלת על כל המילה, אפשר לדעת יותר על סוגי השגיאות.

קוד המינג עוזר לשמור על מידע מושחז ויעיל בלי להוסיף הרבה ביטים.