קוד המינג

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

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

היסטוריה

בשנות ה-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 (מילת הקוד וכל וריאציה שלה בשינוי סיבית בודדת). על כן מבחינה מתמטית חייב להתקיים:

(m+r+1)\cdot 2^{m}\leq 2^{m+r}

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

m+r+1\leq 2^{r}

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

m+r+1=2_{}^{r}

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

2_{}^{r}-r-1=m

כלומר קיבלנו:

m+r+1=2_{}^{r}

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

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

דוגמה לשימוש בקוד המינג (11,7)

נסתכל על מילת המידע "0110101" (באורך 7 סיביות, הנקראת משמאל לימין). לצורך ההדגמה של קוד ההמינג, צורת חישובו והשימוש בו כדי לזהות שגיאות, ראו את הטבלה שלהלן. הסימון d מציין סיביות מידע, ו-p מציין סיביות זוגיות.

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

חישוב סיביות הזוגיות של קוד המינג
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇
מילת המידע ללא סיביות הזוגיות:			0		1	1	0		1	0	1
p₁	1		0		1		0		1		1
p₂		0	0			1	0			0	1
p₃				0	1	1	0
p₄								0	1	0	1
מילת המידע עם סיביות הזוגיות:	1	0	0	0	1	1	0	0	1	0	1

מילת הקוד המתקבלת (עם סיביות הזוגיות) היא "10001100101" (באורך 11 סיביות). עתה נניח, לשם הדגמה, כי הסיבית האחרונה מתקבלת באופן משובש, כלומר הופכת ל-0, והמילה המשודרת היא "10001100100". כאשר אנו באים לנתח את המילה המתקבלת, נסמן ב-1 כל סיבית זוגיות שגויה (ביחס לחישוב זוגיות של הסיביות שהיא בודקת אותם).

בדיקת סיביות הזוגיות (סיביות שגויות מודגשות)
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇	בדיקת הזוגיות	סיבית זוגיות
מילת המידע שהתקבלה:	1	0	0	0	1	1	0	0	1	0	0	1
p₁	1		0		1		0		1		0	כישלון	1
p₂		0	0			1	0			0	0	כישלון	1
p₃				0	1	1	0					הצלחה	0
p₄								0	1	0	0	כישלון	1

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

	p₄	p₃	p₂	p₁
בינארי	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)

נסתכל על אותה מילת המידע "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), משתמשים בשתי מטריצות קשורות זו לזו – מטריצת יצירת הקוד G ומטריצת בדיקת הזוגיות H:

\mathbf {G} :={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&1&1&1\\1&0&1&1\\1&1&0&1\\\end{pmatrix}}

ו-

\mathbf {H} :={\begin{pmatrix}0&1&1&1&1&0&0\\1&0&1&1&0&1&0\\1&1&0&1&0&0&1\\\end{pmatrix}}

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

באופן דומה, שלוש העמודות האחרונות של H מייצגות את מטריצת הזהות $I_{3}^{}$ , כאשר ארבע העמודות הראשונות מייצגות את המיפוי (הזהה למיפוי של מטריצה G) בין סיביות המידע לסיביות הזוגיות.

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

\mathbf {p} ={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}

קידוד המידע

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

\mathbf {G} \cdot \mathbf {p} ={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&1&1&1\\1&0&1&1\\1&1&0&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}=\mathbf {x}

בדיקת זוגיות

אם שום שגיאה לא אירעה במהלך השידור, הרי שמילת הקוד המתקבלת r זהה למילת הקוד המשודרת x:

\mathbf {r} =\mathbf {x}

כדי לראות אם אירע שיבוש במילת הקוד, המקבל צריך להכפיל את H עם r. ביצוע המכפלה הזו (שוב במודולו-2) מניב את התוצאה:

\mathbf {H} \cdot \mathbf {r} ={\begin{pmatrix}0&1&1&1&1&0&0\\1&0&1&1&0&1&0\\1&1&0&1&0&0&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}

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

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

תיקון שגיאות

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

\mathbf {r} =\mathbf {x} +\mathbf {e} _{i}

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

עתה, אם נכפיל וקטור זה ב-H:

\mathbf {Hr} =\mathbf {H} (\mathbf {x} +\mathbf {e} _{i})=\mathbf {Hx} +\mathbf {He} _{i}

כיוון ש-x הוא המידע המשודר, הוא ללא שגיאות, ולכן תוצאת המכפלה של H ו-x הוא אפס (כפי שראינו קודם). לכן:

\mathbf {Hx} +\mathbf {He} _{i}=\mathbf {0} +\mathbf {He} _{i}=\mathbf {He} _{i}

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

לדוגמה, נניח כי המידע המתקבל הוא:

\mathbf {r} =\mathbf {x} +\mathbf {e} _{2}={\begin{pmatrix}1\\0\\1\\1\\0\\1\\0\end{pmatrix}}+{\begin{pmatrix}0\\1\\0\\0\\0\\0\\0\end{pmatrix}}={\begin{pmatrix}1\\1\\1\\1\\0\\1\\0\end{pmatrix}}

כשנבצע את המכפלה נקבל,

\mathbf {Hr} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\1\\1\\1\\0\\1\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\0\end{pmatrix}}

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

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

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

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

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

נצילות שידור

ניתן למדוד את נצילות שידור הסיביות על ידי הנוסחה:

\ \eta ={\frac {m}{m+H}}

m – מספר הסיביות במילה.
H – מספר סיביות המינג.

ראו גם

לקריאה נוספת

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

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

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

הערות שוליים

^ Hamming Code

[1] Hamming Code

[1]