קוד המינג

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

היסטוריה

בשנות ה-40 של המאה ה-20, ריצ'רד המינג עבד במעבדות בל על המחשב האלקטרו-מכני "Bell Model V", אשר הקלט שלו הוזן בעזרת כרטיסים מנוקבים. עקב חוסר מהימנותו של קורא הכרטיסים, שגיאות בקריאת הכרטיסים היו דבר שבשגרה, ולכן במהלך ימי השבוע, קוד מובנה מיוחד במחשב היה מוצא שגיאות ומדליק נורות כך שמפעילי המחשב יכלו לתקן ידנית את הבעיות. לאחר שעות העבודה ובמהלך סופי השבוע, כאשר מפעילי המחשב לא היו נוכחים, כל שהמחשב יכול לעשות היה לנטוש את המשימה שבה התגלו שגיאות ולהמשיך למשימה הבאה.
המינג עבד בסופי שבוע, ונעשה מתוסכל יותר ויותר מהצורך להפעיל מחדש את התוכניות שלו עקב התקלות של קורא הכרטיסים. בשנים שלאחר מכן הוא שקד על בעיית תיקון-השגיאות ופיתח שורה של אלגוריתמים רבי-עוצמה לטיפול בבעיה. בשנת 1950 הוא פרסם את מה שידוע כיום כקוד המינג, אשר נשאר בשימוש במספר יישומים גם כיום.

קודים קודמים להמינג שנמצאו בשימוש

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

סיבית זוגיות

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

קוד שתיים-מתוך-חמש

בשנות ה-40 של המאה ה-20, מעבדות בל השתמשו בקוד מתוחכם מעט יותר הקרוי קוד שתיים-מתוך-חמש. קוד זה הבטיח כי כל בלוק של חמש סיביות הכיל בדיוק שתי סיביות עם הערך 1. המחשב יכל לזהות שאירעה שגיאה, אם לא היו בדיוק שתי סיביות עם הערך 1 בכל בלוק. עם זאת, גם קוד זה היה מסוגל לזהות בוודאות רק שגיאות בסיבית בודדת; אם סיבית אחת התהפכה ל-0 ואחרת התהפכה ל-1 באותו הבלוק, הכלל של שתיים מתוך חמש היה נשאר תקף, והשגיאה לא הייתה מתגלה.

הישנות

קוד נפוץ נוסף באותו הזמן ביצע שכפול של כל סיבית מידע מספר קבוע של פעמים, במטרה להבטיח שהוא ישודר באופן תקין. למשל, אם הסיבית הנשלחת היא 1, וקבוע ההישנות הוא 3, קוד ההישנות המשודר היה "111". אם שלושת הביטים המתקבלים אינם זהים, הרי שבוודאות אירעה שגיאה. אם ערוץ השידור נקי מספיק מהפרעות, הרי שניתן להניח כי באופן סביר רק סיבית אחת לכל היותר תשתנה בכל שלשה. על כן, 001, 010, וכן 100 הצביעו על כך ששודר 0, ואילו 110, 101, וכן 011 הצביעו על כך ששודר 1, על פי עקרון הרוב כאשר כל סיבית בשלשה מהווה "קול הצבעה" בנוגע לערכה המקורי של הסיבית המשודרת.
קוד כזה, אשר מסוגל לשחזר את ההודעה המקורית בהינתן שגיאות בהודעה המשודרת נקרא קוד לתיקון שגיאות, אולם קודים שכאלה אינם מסוגלים לתקן את כל השגיאות. בדוגמה שלנו (שידור 1 כ"111"), אם בעקבות רעש בערוץ שתי סיביות בשלשה היו מתחלפות והיה מתקבל לדוגמה "001", הרי שהמערכת לא הייתה מזהה את השגיאה כראוי, ואף מסיקה באופן שגוי כי הסיבית המקורית הייתה 0. אם היינו מגדילים את קבוע ההישנות ל4 (כלומר היינו משכפלים כל סיבית 4 פעם), היינו מסוגלים לזהות את כל השגיאות הכוללות שיבוש של לכל היותר 2 סיביות, אולם לא היינו מסוגלים לתקן אותם (כי אז היה נוצר מצב של "תיקו" בערכי הסיביות המשודרות); אם קבוע ההישנות הוא 5, ניתן לתקן שגיאות אלה, אולם לא ניתן לזהות את כל השגיאות הכוללות שיבוש ב־3 סיביות.
אם נוסיף עוד סיביות לתיקון-שגיאות להודעה, ואם ניתן לארגן ששגיאות בסיביות מידע שונות יפיקו תוצאות שגיאה שונות, יהיה ניתן לזהות את הביטים השגויים. בהודעה באורך 7 סיביות, ישנן 7 שגיאות סיבית-בודדת אפשריות, על כן 3 סיביות לתיקון-שגיאות יכולות פוטנציאלית גם לציין שאירעה שגיאה, וגם היכן היא אירעה.
אף על היכולת לתקן שגיאות עבור קבועי הישנות הולכים וגדלים, קוד ההישנות אינו יעיל באופן מובהק, שכן הוא מקטין את קצב ההעברה פי קבוע ההישנות, על כן היעילות של הקוד יורדת דרסטית ככל שאנו מגדילים את קבוע ההישנות במטרה לזהות ולתקן שגיאות רבות יותר, והופך את הקוד ללא מעשי במערכות זמן אמת.

קוד המינג (7,4)

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

קוד המינג עם סיבית זוגיות נוספת

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