stanford-oval/wikipedia huggingface dataset:
קוד המינג
היסטוריה

בשנות ה-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 סיביות לתיקון-שגיאות יכולות פוטנציאלית גם לציין שאירעה שגיאה, וגם היכן היא אירעה.
אף על היכולת לתקן שגיאות עבור קבועי הישנות הולכים וגדלים, קוד ההישנות אינו יעיל באופן מובהק, שכן הוא מקטין את קצב ההעברה פי קבוע ההישנות, על כן היעילות של הקוד יורדת דרסטית ככל שאנו מגדילים את קבוע ההישנות במטרה לזהות ולתקן שגיאות רבות יותר, והופך את הקוד ללא מעשי במערכות זמן אמת.
קודי המינג

המינג למד את שיטות הקידוד הקיימות, כולל את שתיים-מתוך-חמש, והצליח להכליל את רעיונותיהם. תחילה, הוא קבע סימונים כלליים לתיאור המערכת, כולל סימון למספר סיביות המידע וסיביות לתיקון-שגיאות בכל בלוק. לדוגמה, קוד הזוגיות מכיל סיבית בודדת לכל מילת מידע, על כן בהנחה שמילות ASCII היו באורך 7 סיביות, המינג תיאר את קוד הזוגיות כקוד (8,7), כיוון שכל בלוק מידע הוא באורך 8 סיביות, מתוכם 7 מהווים את המידע. באופן דומה, קוד ההישנות היה מוגדר כ (3,1) (כאשר קבוע ההישנות הוא 3). "שיעור האינפורמציה" הוא המספר השני מחולק בראשון – בקוד ההישנות, לדוגמה, שיעור האינפורמציה שווה ל-1/3.
כמו כן, המינג שם לב לבעיות כאשר שתי סיביות או יותר מתהפכות, וכינה מצב זה כ"מרחק" (כיום מונח זה קרוי "מרחק המינג", על שמו). עקרונית, "מרחק המינג" הוא מספר הסיביות המינימלי שצריך לשנות במילת קוד חוקית כלשהי כדי לקבל מילת קוד חוקית אחרת. קוד הזוגיות הוא בעל מרחק 2, שכן כל שתי סיביות מתהפכות אינן מתגלות. קוד ההישנות (3,1) הוא בעל מרחק 3, שכן יש צורך לשנות לפחות 3 סיביות (כולן בשלשה אחת) כדי לקבל מילת קוד חוקית אחרת. באופן דומה, בקוד הישנות (4,1) – כל סיבית משוכפלת 4 פעמים – יש מרחק 4, על כן שגיאה של התהפכות שני ביטים ניתנת לגילוי.
המינג התעניין בשתי בעיות בבת-אחת; הגדלת המרחק ככל האפשר, כאשר באותו זמן מגדילים את שיעור המידע כמה שניתן. במהלך שנות ה-40, הוא פיתח מספר סכימות קידוד, אשר היוו שיפור דרמטי ביחס לקודים הקיימים. המפתח לכל המערכות שפיתח היה חפיפה בין סיביות הזוגיות, כך שהן היו מסוגלות לבדוק תקינות זו של זו, ולא רק של המידע עצמו.
תיאור תפקידן של סיביות הזוגיות בקוד המינג הכללי הוא די פשוט:
כל הסיביות שנמצאות במקומות שהן חזקה של שתיים משמשות כסיביות זוגיות. (אלה הסיביות שבמקומות 1, 2, 4, 8, 16, 32 וכך הלאה).
כל שאר הסיביות משמשות כסיביות מידע, אשר יש לקודד. (אלה הסיביות שבמקומות 3, 5, 6, 7, 9, 10, 11, 12, וכך הלאה).
כל סיבית זוגיות מחשבת את הזוגיות למספר מסוים של סיביות במילת הקוד. מיקומה של סיבית הזוגיות קובע את סדרת סיביות המידע שאותם היא לוקחת בחשבון:
סיבית במקום 1: בודקת את כל הסיביות במקומות האי-זוגיים בלבד, כלומר את הסיביות 1, 3, 5, 7, 9, 11, 13, 15 וכך הלאה.
סיבית במקום 2: בודקת ומדלגת לסירוגין על צמד סיביות, החל מהסיבית השנייה, כלומר בודקת את הסיביות 2, 3, 6, 7, 10, 11, וכך הלאה.
סיבית במקום 4: בודקת ומדלגת לסירוגין על 4 סיביות, החל מהסיבית הרביעית, כלומר בודקת את הסיביות 4, 5, 6, 7, 12, 13, 14, 15, 20 וכך הלאה.
סיבית במקום 8: בודקת ומדלגת לסירוגין על 8 סיביות, החל מהסיבית השמינית, כלומר בודקת את הסיביות 8 עד 15, 24 עד 31, וכך הלאה.
סיבית במקום 16: בודקת ומדלגת לסירוגין על 16 סיביות, החל מהסיבית ה16, כלומר בודקת את הסיביות 16 עד 31, 48 עד 63 וכך הלאה.
באופן כללי, סיבית זוגיות במקום n (כאשר n הוא חזקה של שתיים), בודקת ומדלגת לסירוגין על n סיביות, החל מהסיבית ה-n.
במילים אחרות, סיבית זוגיות במקום n, כאשר  n=2_{}^{k}, בודקת את הביטים אשר הסיבית הk בייצוג הבינארי של המיקום שלהם שווה ל-1. במהופך, לדוגמה, הסיבית ה-13, או 1101 בייצוג בינארי, נבדקת על ידי הסיביות 1 (=0001), 4 (=0100) ו-8 (=1000).
קודי המינג > יעילות התקורה של קוד המינג

נמצא קודם מה מספר הסיביות המינימלי שיש להוסיף למילת מידע כדי להבטיח שניתן לתקן שגיאה בסיבית בודדת, ללא תלות בקוד התיקון. נסמן:
r – מספר הסיביות הנוספות הדרושות.
m – מספר הסיביות של המידע המקורי.
על כן, אורך מילת הקוד המתקבלת יהיה r+m.
קיימות  2^{m} מילים בינאריות שונות באורך m. כל מילה שכזו מקודדים במילה באורך m+r. עתה נשים לב שכדי לזהות שגיאה, אם נשנה את מילת הקוד בסיבית אחת כלשהי, עדיין צריכה להתקבל מילת המידע המקורית. לכן בעצם כל מילת מידע מקושרת ל-m+r+1 מילים שונות באורך m+r (מילת הקוד וכל וריאציה שלה בשינוי סיבית בודדת). על כן מבחינה מתמטית חייב להתקיים:
כלומר, מספר מילות הקוד והווריאציות עליהן חייב להיות גדול שווה למספר מילות המידע, כדי שיהיה ניתן לקודד כל מילת מידע.
מפיתוח אי השוויון הזה אנו מקבלים:
זהו כאמור חסם תחתון שכל קוד לתיקון שגיאה של סיבית בודדת חייב לקיים. נראה שקוד המינג מקיים את החסם המינימלי, כלומר קוד המינג מקיים:
בקוד המינג מוסיפים סיבית זוגיות על כל סיבית בייצוג הבינארי של מיקום הסיביות. עם r ספרות בינאריות אפשר לייצג כל מספר עשרוני עד  2_{}^{r}-1 . מכאן שבעזרת r סיביות זוגיות של קוד המינג אנו יכולים לקדד מילות מידע עד אורך  (2_{}^{r}-1)-r (כיוון שגם סיביות הזוגיות תופסות מקום במילת הקוד, הרי ש-r סיביות תמיד שמורות להן). עבור ה-m המקסימלי בהינתן r, מתקיים:
כלומר קיבלנו:
לקחנו את ה-m המקסימלי לשם פשטות החישוב. אם היינו לוקחים כל m בתחום האפשרי עבור r כלשהו, היינו מקבלים תוצאה דומה, אך היינו נאלצים לעבוד עם פונקציית הערך השלם (כיוון שאי אפשר להשתמש ב"שברי" סיביות יתירות) על אי-שוויון המתאר את החסם. בכל מקרה אפשר (ובחלק מהמקרים אף נהוג) לקחת כל הודעה באורך הקטן מ-m המקסימלי, ולהוסיף לה אפסים לסופה כדי לקבל הודעה באורך מקסימלי (כדאי לשים לב שאופן פעולה כזה לא משנה אף סיבית מהמידע או הזוגיות).
על כן, ראינו כי קוד המינג הוא אופטימלי מבחינת סיביות יתירות הדרושות לצורך תיקון שגיאה בסיבית בודדת.
דוגמה לשימוש בקוד המינג (11,7)

נסתכל על מילת המידע "0110101" (באורך 7 סיביות, הנקראת משמאל לימין). לצורך ההדגמה של קוד ההמינג, צורת חישובו והשימוש בו כדי לזהות שגיאות, ראו את הטבלה שלהלן. הסימון d מציין סיביות מידע, ו-p מציין סיביות זוגיות.
תחילה מציבים את סיביות המידע במקומות המיועדים להם (המקומות שמהווים חזקות של 2 שמורים לסיביות הזוגיות), וסיביות הזוגיות מחושבות על פי המקובל (מספר אי זוגי של סיביות השוות ל-1 יתנו סיבית זוגיות השווה ל-1 גם כן).
| מילת המידע ללא סיביות הזוגיות: | p1>  | p2>  | d1> 0 | p3>  | d2> 1 | d3> 1 | d4> 0 | p4>  | d5> 1 | d6> 0 | d7> 1 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| p1 | 1 |  | 0 |  | 1 |  | 0 |  | 1 |  | 1 |
| p2 |  | 0 | 0 |  |  | 1 | 0 |  |  | 0 | 1 |
| p3 |  |  |  | 0 | 1 | 1 | 0 |  |  |  |  |
| p4 |  |  |  |  |  |  |  | 0 | 1 | 0 | 1 |
| מילת המידע עם סיביות הזוגיות: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
מילת הקוד המתקבלת (עם סיביות הזוגיות) היא "10001100101" (באורך 11 סיביות). עתה נניח, לשם הדגמה, כי הסיבית האחרונה מתקבלת באופן משובש, כלומר הופכת ל-0, והמילה המשודרת היא "10001100100". כאשר אנו באים לנתח את המילה המתקבלת, נסמן ב-1 כל סיבית זוגיות שגויה (ביחס לחישוב זוגיות של הסיביות שהיא בודקת אותם).
| מילת המידע שהתקבלה: | p1> 1 | p2> 0 | d1> 0 | p3> 0 | d2> 1 | d3> 1 | d4> 0 | p4> 0 | d5> 1 | d6> 0 | d7> 0 | בדיקת הזוגיות> 1 | סיבית זוגיות>  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| p1 | 1 |  | 0 |  | 1 |  | 0 |  | 1 |  | 0 | כישלון | 1 |
| p2 |  | 0 | 0 |  |  | 1 | 0 |  |  | 0 | 0 | כישלון | 1 |
| p3 |  |  |  | 0 | 1 | 1 | 0 |  |  |  |  | הצלחה | 0 |
| p4 |  |  |  |  |  |  |  | 0 | 1 | 0 | 0 | כישלון | 1 |
השלב האחרון הוא לחשב את הערך המספרי של סיביות הזוגיות (ערך כל סיבית זוגיות נקבע על פי מיקומה). הערך המספרי של סיביות הזוגיות המחושבות בבדיקה הוא 11, דבר שמצביע על כך שהסיבית ה-11 במילת המידע (כולל סיביות הזוגיות) היא השגויה, ויש להפוך את ערכה.
|  | p4 | p3 | p2 | p1 |  |
| --- | --- | --- | --- | --- | --- |
| בינארי | 1 | 0 | 1 | 1 |  |
| עשרוני | 8 |  | 2 | 1 | Σ = 11 |
כאשר נהפוך את הסיבית ה-11, נקבל חזרה את המילה המקורית ששודרה – "10001100101". אם נסיר את סיביות הזוגיות של קוד המינג, נחזור למילה המקורית 0110101.
יש לשים לב כי אם רק סיבית זוגיות אחת נכשלת, אז בוודאות היא הסיבית השגויה (ואפשר לבדוק זאת גם לפי שיטת הבדיקה לעיל).
לסיום, נניח כי שתי סיביות התחלפו, במקומות "x" ו-"y". אם "x" ו-"y" מוגנים על ידי אותה סיביות זוגיות, הרי שסיבית הזוגיות הזו לא תגלה את השגיאה בשניהם. אולם, לפחות סיבית זוגיות אחת תתגלה שגויה, כיוון ש-x ≠ y והם חייבים להיות שונים לפחות בסיבית אחת בייצוג שלהם (קיימת הצגה בינארית יחידה לכל מספר, וכל מספר מיוצג על ידי הצגה אחרת). על כן קוד המינג מזהה שקיימת שגיאה, אולם הוא אינו יכול להבדיל שגיאה זו משגיאות של סיבית בודדת, ובפרט לתת אינדיקציה בנוגע למקום הנכון שבו אירעה השגיאה.
קוד המינג (7,4)

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

נסתכל על אותה מילת המידע "0110101" (באורך 7 סיביות, הנקראת משמאל לימין) כאשר היא כוללת בתוכה את ה-nible (יחידת מידע של 4 סיביות) שערכו "1101" ועוד 3 סיביות המינג. נשים את המידע בטבלה הבאה ונסמן את סיביות ההמינג באות H:
| b7 | b6 | b5 | b4=H | b3 | b2=H | b1=H |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 |
כעת נחשב את ערכי סיביות ההמינג לפי קוד המינג, כך שכל סיבית המינג תהיה פעולת XOR בין כל הסיביות הסוכמות אותה, למשל 1+2=3 אז b3 יופיע גם ב-b1=H וגם ב-b2=H. עבור nible (ארבע סיביות) נקבל:
b1=b3 \oplus b5 \oplus b7
b2=b3 \oplus b6 \oplus b7
b4=b5 \oplus b6 \oplus b7
כל שנותר לעשות הוא לחשב את ערכי סיביות ההמינג לפי קוד המינג ולראות אם הן תואמות למידע שקיבלנו בהתחלה:
b1=1 \oplus 1 \oplus 1=1
b2=1 \oplus 0 \oplus 1=0
b4=1 \oplus 0 \oplus 1=0
ניתן לראות כי סיביות b1, b2 אינן תואמות למקור. נסכום אותם ונקבל את הסיבית השגויה: 1+2=3 כלומר הסיבית השגויה היא סיבית b3, נהפוך אותה ונקבל את המידע הנכון: "0100101", כאשר ה-nible הנכון הוא: "0101".
קוד המינג (7,4) > מטריצות המינג

באופן מעשי, קודי המינג משתמשים במכפלת מטריצות מיוחדות הקרויות "מטריצות המינג" כדי לממש את הפעולות של יצירת הקוד ובדיקת הזוגיות. עבור קוד המינג (7,4), משתמשים בשתי מטריצות קשורות זו לזו – מטריצת יצירת הקוד G ומטריצת בדיקת הזוגיות H:
ו-
ארבע השורות הראשונות של G מייצגות את מטריצת היחידה  I_{4}^{}, כאשר שלוש השורות האחרונות מהוות מיפוי מ-4 סיביות המידע ל-3 סיביות הזוגיות. וקטורי העמודה ב-G מהווים בסיס לגרעין של H. מטריצת היחידה מעבירה את וקטור המידע אל מעבר לשלב המכפלה (מטריצת היחידה מהווה איבר יחידה ביחס למכפלת מטריצות). בניגוד למה שנאמר לעיל, כאן סיביות הזוגיות מופיעות בסוף מילת הקוד (סידור סיביות הזוגיות כפי שהוצג מקודם נועד לנוחיות ההצגה וההבנה, ואין לו משמעות עקרונית בקוד עצמו).
באופן דומה, שלוש העמודות האחרונות של H מייצגות את מטריצת הזהות  I_{3}^{}, כאשר ארבע העמודות הראשונות מייצגות את המיפוי (הזהה למיפוי של מטריצה G) בין סיביות המידע לסיביות הזוגיות.
לצורך ביצוע האלגורתמים של יצירת הקוד והבדיקה, מייצגים את מילת המידע בתור וקטור עמודה. לדוגמה, אם מילת המידע שלנו היא "1011", נקבל את הווקטור:
קוד המינג (7,4) > קידוד המידע

נניח כי ברצוננו לשדר את המידע מעל ערוץ רועש. על כן, ניקח את המכפלה של G ו-p, כאשר המכפלה מתבצעת במודולו-2, ונקבל את מילת הקוד x שיש לשדר (נשים לב שמילת הקוד אכן באורך 7 סיביות, וסיביות הזוגיות מופיעות בסוף המילה):
קוד המינג (7,4) > בדיקת זוגיות

אם שום שגיאה לא אירעה במהלך השידור, הרי שמילת הקוד המתקבלת r זהה למילת הקוד המשודרת x:
כדי לראות אם אירע שיבוש במילת הקוד, המקבל צריך להכפיל את H עם r. ביצוע המכפלה הזו (שוב במודולו-2) מניב את התוצאה:
כיוון שקיבלנו את וקטור האפס, המקבל יכול להסיק כי שום שגיאה לא אירעה.
וקטור האפס מציין שלא אירעו שגיאות כיוון שכאשר וקטור המידע מוכפל עם G, הווקטור המתקבל מהמכפלה מהווה צירוף ליניארי של הבסיס של H. לכן, כל עוד לא מתבצע שום שינוי בזמן השידור, r ימשיך להיות בגרעין של H, והמכפלה תמשיך להניב את וקטור האפס.
קוד המינג (7,4) > תיקון שגיאות

עכשיו נניח כי אירעה שגיאה בסיבית בודדת. באופן מתמטי, ניתן לכתוב
כאשר ביטוי זה הוא במודולו-2, ו- \mathbf {e} _{i} הוא וקטור היחידה ה-i, כלומר וקטור עמודה שכל האיברים שלו שווים לאפס, פרט לאיבר ה-i, אשר שווה ל-1. על כן, הביטוי הנ"ל מציין כי אירעה שגיאה בסיבית ה-i של המידע.
עתה, אם נכפיל וקטור זה ב-H:
כיוון ש-x הוא המידע המשודר, הוא ללא שגיאות, ולכן תוצאת המכפלה של H ו-x הוא אפס (כפי שראינו קודם). לכן:
הכפלת H עם וקטור היחידה ה-i מניבה בתוצאה את העמודה ה-i של H, ועל כן אנו יודעים כי השגיאה אירעה בסיבית שמספר סידורה הוא כמו העמודה שקיבלנו, כלומר שהסיבית השגויה היא הסיבית ה-i, ועל כן נוכל לתקן את השגיאה בעזרת מידע זה.
לדוגמה, נניח כי המידע המתקבל הוא:
כשנבצע את המכפלה נקבל,
אשר מתאים לעמודה השנייה של H. על כן, השגיאה אירעה בסיבית השנייה, ולכן ניתן לתקנה.
לא מסובך להראות כי רק שגיאות בסיבית בודדת ניתן לתקן על ידי שימוש בסכמה זו. פרט לכך, ניתן להשתמש בקודי המינג כדי לזהות שגיאות בסיבית בודדת או בשתי סיביות, פשוט על ידי בחינת המכפלה של וקטור המידע עם H – קיימת שגיאה ודאית אם המכפלה אינה שווה לווקטור האפס. עם זאת, כפי שנאמר, בלתי אפשרי להבדיל בין שגיאות בסיבית בודדת לשגיאות בשתי סיביות בשימוש קוד המינג בלבד.
קוד המינג עם סיבית זוגיות נוספת

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

ניתן למדוד את נצילות שידור הסיביות על ידי הנוסחה:
m – מספר הסיביות במילה.
H – מספר סיביות המינג.
ראו גם

מרחק המינג
קוד גוליי
לקריאה נוספת

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

↑  Hamming Code
הלמוט מדר

| --- | --- |
אין תמונה חופשית
 לידה:  5 ביולי 1908 רוטרודה, האימפריה הגרמנית האימפריה הגרמנית
 פטירה:  12 במאי 1984 (בגיל 75) קובלנץ, גרמניה המערבית גרמניה המערבית
 מדינה:  גרמניה 
 השתייכות:  גרמניה הנאצית גרמניה הנאצית   גרמניה המערבית גרמניה המערבית
 תקופת הפעילות:  1936–1945   1956 – 1945
 דרגה:   גנרל מיור (ורמאכט)  גנרל לויטננט (בונדסוור)
 תפקידים בשירות
 מפקד דיוויזיית הפאנצר ה-7   מפקד דיוויזיית פיהרר גרנדיר
 פעולות ומבצעים
 מלחמת העולם השנייה
 עיטורים
   צלב האבירים של צלב הברזל עם עלי אלון וחרבות   צלב הברזל דרגה ראשונה   צלב הברזל דרגה שנייה
 
גנרל הלמוט מדר (בגרמנית: Hellmuth Mäder; 5 ביולי 1908 – 12 במאי 1984) היה מפקד בוורמאכט, שפיקד על כוחות במלחמת העולם השנייה.
ביוגרפיה > ראשית חייו ושירותו במלחמה

מדר נולד ב-5 ביולי 1908 ברוטרודה, שהשתייכה לאימפריה הגרמנית. בשנת 1936 התגייס מדר לוורמאכט, ועם פרוץ מלחמת העולם השנייה הוא היה קצין מטה בדיוויזיה ה-34. בתחילת המערכה על צרפת, אובר-לויטננט מדר הוביל את הפלוגה ה-14 ברגימנט הרגלים ה-522, שהיה חלק מהדיוויזיה ה-297. בחורף 1940 הוא הפך למפקד הגדוד ה-3 ברגימנט. במהלך קרבות ההגנה בחורף 1941/42 הוענק למדר עיטור צלב האבירים של צלב הברזל ב-3 באפריל 1942 על גבורה אישית חוזרת. ביולי 1942 הוא הפך למפקד רגימנט הרגלים ה-522 בדרגת מיור. במהלך מבצע כחול בקיץ 1942 בלט אוברסט לויטננט מדר בפעולותיו. בחורף 1942/43 הוקף הרגימנט שלו בסטלינגרד. לאחר לחימה קשה, מדר נפצע קשה בראשית 1943 והוטס החוצה מהכיס. לאחר החלמתו הועבר מדר לעתודת המילואים, ובאביב 1944 הוא הועלה לדרגת אוברסט ומונה למפקד חטיבת ההתערבות נארווה. עם היחידה שלו, מדר הצליח לעצור התקפות רוסיות וניסיונות לפריצת דרך מספר פעמים. לאחר פציעה נוספת הפך מדר למפקד בית הספר לנשק של קבוצת ארמיות צפון. לאחר תחילת מתקפת הקיץ הרוסית בשנת 1944, מדר הפך למפקד העיר שאולן, בין ריגה לקניגסברג. מדר הצליח להשאיר את העיר פתוחה במשך 48 שעות כדי שהכוחות הגרמנים שמצפון לעיר ייסוגו לדרומה. על הישג זה הוענק למדר תוספת עלי האלון לעיטור צלב האבירים של צלב הברזל ב-27 באוגוסט 1944. בסתיו 1944 פיקד מדר על דיוויזיית הפאנצר ה-7, ובסוף דצמבר 1944 הפך מדר למפקד חטיבת משמר הפיהרר, והוביל אותה במהלך קרב הארדנים. בינואר 1945 הורחבה החטיבה לדיוויזיית פיהרר גרנדיר ומדר הועלה לדרגת גנרל מיור. לאחר לחימה קשה עם כוחותיו בלובאן ושטטין והקרב האחרון על וינה, הוענק למדר תוספת חרבות לעיטור צלב האבירים של צלב הברזל ב-18 באפריל 1945. ב-8 במאי נפלו מדר וכוחותיו בשבי ארצות הברית, אך הוסגרו לכוחות הצבא האדום.
ביוגרפיה > לאחר המלחמה

מדר השתחרר מהשבי רק בחורף 1955. לאחר שובו לרפובליקה הפדרלית של גרמניה, הצטרף מדר לבונדסוור שהוקם לאחרונה בדרגת בריגדה-גנרל, ופיקד על בית הספר לחי"ר בהאמלבורג משנת 1956, ובשנת 1958 הוא הועלה לדרגת גנרל מיור. בשנת 1968 הוא הועלה לדרגת גנרל לויטננט. בשנת 1974 הואשם מדר בשחיתות והוא נידון לשנתיים מאסר ואף נשללה ממנו דרגתו. לאחר שחרורו התגורר מדר בקובלנץ, עד מותו ב-12 במאי 1984.
לטינית קלאסית

| --- | --- |

 ראו גם:  שפה • כתב • רשימת שפות
 
לטינית קלאסית (בלטינית: Lingua·Latīna או Prīsca Latīnitās) היא צורת הלטינית הספרותית המוכרת כשפה תקנית ספרותית שהייתה בשימוש על ידי סופרים מהרפובליקה הרומית המאוחרת והאימפריה הרומית המוקדמת. היא הייתה בשימוש משנת 75 לפני הספירה ועד המאה ה-3 לספירה, אז התפתחה ללטינית מאוחרת. בתקופות מאוחרות יותר, היא נחשבה ללטינית טובה או ראויה, כאשר הגרסאות השפה לאחר מכן נתפסו כמנוונות או כמושחתות. המילה לטינית מובנת כעת כברירת מחדל כמשמעותה "לטינית קלאסית"; לדוגמה, ספרי לימוד לטינית מודרניים מלמדים כמעט אך ורק לטינית קלאסית.
מרקוס טוליוס קיקרו ובני דורו של הרפובליקה המאוחרת התייחסו לשפה הלטינית, בניגוד לשפות אחרות (כמו יוונית), כ-lingua latina או sermo latinus. עם זאת, הם הבחינו בשפת העם הרווחת בתור לטינית וולגרית (sermo vulgaris ו-sermo vulgi).
הלטינית הייתה שפה מדוברת וכתובה. זו הייתה השפה הנלמדת בבתי הספר. לפיכך חלו עליה כללים מחייבים, וכאשר נלקחו בחשבון נושאים מיוחדים כמו שירה או רטוריקה, חלו כללים נוספים. מאז שהלטינית המדוברת נכחדה (לטובת ההתפתחות הבאה), כללי הטקסטים של פוליטוס (מהוקצעים) עשויים לתת מראה של שפה מלאכותית. עם זאת, הלטינית הייתה צורה של סרמו (שפה מדוברת), וככזו, שמרה על ספונטניות.
התקנים, המחברים והמדריכים מהתקופה הלטינית הקלאסית היוו את המודל לשפה שנלמדה והייתה בשימוש בתקופות מאוחרות יותר ברחבי אירופה ומחוצה לה. בעוד שהלטינית ששימשה בתקופות שונות חרגה מהלטינית ה"קלאסית", נעשו מאמצים מעת לעת ללמוד מחדש וליישם מחדש את המודלים של התקופה הקלאסית, למשל על ידי אלקווין בתקופת שלטונו של קרל הגדול, ומאוחר יותר בתקופת הרנסאנס, ויצרו את הצורה הקלאסית ביותר של לטינית הידועה כיום בשם נאו-לטינית.
מבנים פילולוגיים > קלאסי

"לטינית טובה" בפילולוגיה ידועה בתור ספרות לטינית "קלאסית". המונח מתייחס לרלוונטיות הקנונית של יצירות ספרותיות שנכתבו בלטינית בשלהי הרפובליקה הרומית, ובאימפריה הרומית המוקדמת עד האמצעית. "כלומר, השתייכות לקבוצה בלעדית של מחברים (או יצירות) שנחשבו לסמלים של ז'אנר מסוים."  המונח classicus (בזכר רבים classici) הומצא על ידי הרומאים כדי לתרגם ליוונית ἐγκριθέντες (encrithentes), המתייחס למחברים שכתבו בצורה של יוונית שנחשבה למודל חיקוי. לפני כן, המונח classis, בנוסף להיותו צי ימי, היה מעמד חברתי באחת מהחלוקות הדיאכרוניות של החברה הרומית בהתאם לבעלות על רכוש על פי החוקה הרומית. המילה היא תעתיק של יוונית κλῆσις (clēsis, או "קריאה") המשמשת לדירוג מגויסי צבא לפי רכוש ממעמד ראשון עד חמישי.
מבנים פילולוגיים > קנוני

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

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