סיבית שגויה אחת משנה את ההודעה
כל הודעה שמחשב שולח היא רצף של אפסים ואחדות, וכל חוט, קישור רדיו ושבב זיכרון מוסיפים לה מעט רעש. ברוב הזמן הרעש קטן מכדי להשפיע. מדי פעם הוא מזנק ברגע הלא נכון, ו־0 נקרא כ־1, או 1 כ־0. זהו היפוך סיבית.
המכונה שולחת את המילה HELLO, שמונה סיביות לכל אות, ארבע סיביות בכל פעם. כשהסצנה מתחילה, לכל סיבית יש סיכוי של 5% להתהפך. זה נשמע מעט, אבל בכל אות יש שמונה סיביות, ולכן בערך אות אחת מכל שלוש מגיעה שגויה: H הופכת ל־G או ל־J, ולמקלט אין שום דרך לדעת. סיבית שגויה נראית בדיוק כמו סיבית נכונה.
נסו: הורידו את סיכוי להיפוך סיבית ל־1%, ואחר כך העלו אותו ל־15%. ב־1% רוב המילים מגיעות שלמות; ב־15% התצוגה מתמלאת באותיות חסרות פשר. המונה שעל שולחן העבודה מראה כמה מתוך 50 הגושים האחרונים הגיעו שגויים.
זוגיות: סופרים את האחדות
התיקון הפשוט ביותר הוא לשלוח סיבית אחת נוספת, סיבית זוגיות, שנבחרת כך שמספר האחדות בגוש יהיה תמיד זוגי. אם סיבית אחת מתהפכת בדרך, הספירה הופכת לאי־זוגית והמקלט יודע שמשהו השתבש. מה שהוא לא יודע הוא איזו סיבית אשמה, ולכן הכי טוב שהוא יכול לעשות הוא לבקש את הגוש שוב.
כדי לתקן שגיאה ולא רק להבחין בה, המקלט צריך לדעת איפה השגיאה. ריצ’רד המינג פתר את זה במעבדות בל בסוף שנות ה־40, מתוסכל מכך שמחשב הממסרים שעבד עליו נעצר בכל שגיאה במהלך סוף השבוע במקום לתקן אותה. הוא פרסם את הקודים שלו ב־1950.
שלוש בדיקות חופפות
קוד המינג (7,4) מוסיף שלוש סיביות זוגיות לכל ארבע סיביות נתונים, ויוצר גושים של שבע. מספרו את המקומות מ־1 עד 7. סיביות הזוגיות יושבות במקומות 1, 2 ו־4, וכל אחת מהן מכסה קבוצה אחרת, והקבוצות חופפות:
- בדיקה A מכסה את המקומות 1, 3, 5 ו־7.
- בדיקה B מכסה את המקומות 2, 3, 6 ו־7.
- בדיקה C מכסה את המקומות 4, 5, 6 ו־7.
כשמציירים אותן כשלושה עיגולים חופפים, לכל מקום יש אזור משלו: מקום 7 נמצא בתוך שלושתם, מקום 5 רק בתוך A ו־C, ומקום 1 בתוך A בלבד. כל סיבית זוגיות נקבעת כך שבעיגול שלה יהיה מספר זוגי של אחדות.
כשסיבית אחת מתהפכת, כל עיגול שמכיל אותה הופך לאי־זוגי והשאר נשארים זוגיים. העיגולים שנכשלו חופפים באזור אחד בדיוק, ובאזור הזה יושבת האשמה. הקבוצות נבחרו כך שהדפוס הזה הוא המקום עצמו, כתוב בבסיס בינארי: קראו את הבדיקות בסדר C B A, כתבו 1 לכל בדיקה שנכשלה, והיפוך במקום 5 נותן 1 0 1, כלומר 5. המקלט הופך את הסיבית הזאת בחזרה, והגוש מתוקן.
נסו: הזיזו את בדיקה ותיקון אל בדיקות זוגיות. שלושה כרטיסי זוגיות בכחול בהיר מצטרפים לארבעת כרטיסי הנתונים, והלוח מראה את הגוש האחרון שנכשל בבדיקה, עם העיגולים שנכשלו באדום ועם המספר שהם יוצרים. המשיכו אל מתוקן וצפו במקלט מתקן את הסיבית ובתצוגה שכותבת שוב HELLO.
כשהקוד מוטעה
הקוד מניח שבכל גוש מתהפכת סיבית אחת לכל היותר. אם מתהפכות שתי סיביות, משתנות שתי קבוצות של עיגולים, והדפוס מצביע על סיבית שלישית שהייתה תקינה. המקלט הופך אותה בצייתנות, והגוש נשאר עם שלוש סיביות שגויות. העלו את סיכוי להיפוך סיבית ל־15% כדי לראות את הלוח אומר זאת. בסיכוי של 15% לכל סיבית, בערך 28 גושים מתוך 100 סופגים שני היפוכים או יותר, לעומת 48 מתוך 100 שמשתבשים בלי קוד בכלל.
ב־5% לכל סיבית המספרים מעודדים הרבה יותר. בלי קוד, 18.5% מהגושים של ארבע סיביות מגיעים שגויים. עם הקוד אובדים רק גושים שבהם התהפכו שתיים או יותר משבע הסיביות: 4.4%. ב־1% לכל סיבית הקוד מוריד את הגושים השגויים מ־3.9% ל־0.2%. המחיר הוא ששלוש סיביות מכל שבע אינן נושאות שום חלק מההודעה.
קודים בכל מקום
כל טכנולוגיה ששומרת נתונים או שולחת אותם משתמשת בקודים לתיקון שגיאות. הזיכרון בשרתים משתמש בקוד המינג עם עוד סיבית זוגיות אחת על כל הגוש, וכך הוא יכול לתקן כל היפוך בודד ולזהות, אך לא לתקן, כל שני היפוכים. קודי QR והתקליטורים שקדמו לשירותי ההזרמה משתמשים בקודי ריד־סולומון, שמתקנים רצפים שלמים של סיביות פגומות, ולכן תקליטור שרוט עדיין מתנגן וקוד QR מרוח עדיין נסרק. רשתות Wi-Fi, רשתות סלולריות וחלליות משתמשות בקודים ארוכים בהרבה, שמחשב מפענח בעזרת שקילת הסתברויות.
קלוד שאנון הראה ב־1948 שלכל ערוץ רועש יש קיבול ערוץ: קצב עליון של מידע אמין לכל סיבית שנשלחת. מתחת לקצב הזה קיימים קודים שהופכים את השגיאות לנדירות ככל שרוצים; מעליו, שום קוד לא יכול לעשות זאת. לקו שהופך 5% מהסיביות, הקיבול הוא בערך 0.71 סיביות נתונים לכל סיבית שנשלחת. הקוד של המינג פועל בקצב של 4/7, כלומר 0.57, ועדיין מעביר חלק מהשגיאות. קודים מודרניים מגיעים למרחק כחוט השערה מגבול שאנון.
מה המודל הזה משאיר בחוץ
כאן כל סיבית מתהפכת לבדה, באותו סיכוי ידוע. רעש אמיתי מגיע לעתים קרובות בפרצים שפוגעים בכמה סיביות שכנות בבת אחת, ולכן מערכות מעשיות מערבבות סיביות בין גושים לפני השליחה ומשתמשות בקודים שנבנו לפרצים. מקלטים אמיתיים גם מודדים עד כמה הם בטוחים בכל סיבית, ולא רק אם היא 0 או 1, ומפענחים טובים משתמשים במידע הזה. הקוד של המינג הוא הקוד הפשוט ביותר שמתקן שגיאות, ולא הקוד שרוב המערכות משתמשות בו היום. הניצוצות, הכרטיסים והפולסים מצוירים לשם הבהירות ומואטים פי מיליונים רבים, והמסגרות האדומות על כרטיסים שהתהפכו מראות מה שרק מי שהכיר את המקור היה יכול לראות.