קוד המינג  hamming code

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

קוד לגילוי שגיאות

error detecting code

קוד לתיקון שגיאות

error correcting code

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

סיבית ביקורת

checkbit

מילת קוד

codeword

כדי להבין כיצד ניתן לגלות שגיאות ולתקנן, נבחן תחילה את טיבן של שגיאות שידור. מסגרת המשודרת בערוץ מכילה בדרך כלל m סיביות נתונים ו r סיביות ביקורת (checkbits). נסמן ב n את מספר הסיביות במסגרת (n=m+r). n הסיביות מכונות לעיתים מילת קוד (codeword).

.

מרחק המינג

Hamming distance

בהינתן שתי מילות קוד ניתן לקבוע בכמה סיביות הן שונות זו מזו. לדוגמה, שתי מילות הקוד 10001001 ו- 10110001 שונות בשלוש סיביות. מספר הסיביות השונות בין שתי מילות קוד מכונה מרחק המינג (Hamming distance), או בקיצור המרחק בין שתי המילים. את מרחק המינג בין שתי מילים אפשר למצוא ע"י ע"י ביצוע פעולת XOR על שתי המילים, וספירת מספר הסיביות בתוצאה שערכן "1". המשמעות של מרחק המינג בין שתי מילים היא שאם המרחק בין שתי מילות קוד הוא d, הרי שאם שודרה אחת המילים ואירעו d שגיאות שידור, ייתכן שנקבל את המילה השנייה.

.

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

.

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

.

קוד סיבית הזוגיות

parity bit code

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

.

כדוגמה לקוד תיקון שגיאות, נתבונן בקוד, שבו אבע מילות קוד חוקיות: 1111111111, 1111100000, 0000011111, 0000000000. המרחק של קוד זה הוא 5, ומכאן שניתן לתקן בעזרתו שתי שגיאות. אם נקלטה לדוגמה מילת הקוד 0000000111, היא תתוקן למילת הקוד 0000011111. אם אכן אירעו שתי שגיאות לכל היותר יהא התיקון נכון. אם אירעו שלוש שגיאות, והמילה שנשלחה היתה למעשה המילה 0000000000, יהא התיקון שגוי.

.

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

.

קוד המינג

Hamming code

קוד המינג (Hamming code) מאפשר תיקון של שגיאה אחת, תוך שימוש במספר מזערי של סיביות ביקורת. לפי קוד המינג, ממוספרות n הסיביות של מילת הקוד משמאל לימין, כאשר המספר של הסיבית השמאלית ביותר הוא 1, של זו שמימין לה 2, וכן הלאה. כל הסיביות שמספרן הסידורי הוא חזקה שלמה של 2 (סיבית מספר 8,4,2,1, וכן הלאה) הן סיביות ביקורת, ואילו שאר הסיביות (3,5,6,7 וכן הלאה) הן סיביות נתונים.

.

סיביות מילת קוד בקוד המינג מחולקות לקבוצות של סיביות, שאינן בהכרח זרות זו לזו. כל אחת מ r סיביות הביקורת משמשת כסיבית זוגיות של אחת הקבוצות. כדי לקבוע לאילו קבוצות שייכת סיבית נתונים שמספרה k, יש לרשום את המספר k שסכום של חזקות של 2. לדוגמה, 1+2+8=11, ולכן סיבית 11 תהא בקבוצות של סיביות הביקורת 1, 2 ו 8. לעומת זאת 1+4+8+16=29, ולכן סיבית מספר 29 תהא בקבוצות של סיביות הביקורת 1, 4, 8 ו 16.

.

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

.

באיור למטה, מודגם קידוד תווי ASCII, בני 7 סיביות (m=7), למילות קוד בנות 11 סיביות לפי קוד המינג. קל לראות כי עבור m=7, הערך המזערי של r שמקיים את הדרישה (m+r+1) <= 2^r הוא r=4. ואמנם מוספות בקוד המינג שבדוגמה ארבע סיביות ביקורת.

.

ריצ'ארד המינג

ממציא הקוד

יליד ארה"ב

נולד: 11/02/1915

נפטר: 07/01/1998

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

.