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

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

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

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

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

למשל: אם הסדרה מכילה ארבעה ביטים, לדוגמה "0100", נוסיף לה עוד ביט זוגיות ("1") כדי שמספר האחדות יהיה זוגי, ונקבל "01001". אם תתרחש תקלה, והביט הראשון למשל ישתבש וייקלט כ"1" נקבל את הסדרה "11001" המכילה מספר אי-זוגי של אחדות. המקלט יבחין לפיכך שיש שגיאה וידווח.

לחובבי הסתברות: מה הסיכוי לשגיאה בקליטת סדרת נתונים באורך ארבעה ביטים, מבלי שהדבר יתגלה? נניח שאין תלות בין השגיאות בביטים שונים, והסיכוי לטעות בביט בודד הוא אלפית. במקרה כזה, הסיכוי לטעות ללא שימוש בזוגיות הוא אחד פחות הסיכוי להצלחה (שזה 0.999 בחזקת 4), וזה יוצא 0.4%. ומה יקרה אם נוסיף ביט זוגיות? בעקבות ההוספה, טעות בביט אחד תמיד תתגלה! טעות לא תתגלה רק עם שניים או ארבעה ביטים היו שגויים. כיוון שהסיכוי שארבעה ביטים ישתבשו נמוך, נתעלם ממנו. לגבי המקרה של שני ביטים שגויים: מכיוון שיש 10 אפשרויות לבחור שני ביטים מתוך חמש, הסיכוי לטעות שלא תתגלה, לפי התפלגות בינומית:

10* 0.001^2* 0.999^3 = 0.001%

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

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

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

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

טכניקה זו לתיקון שגיאות ( error-correction-code : ECC) היא מאוד שימושית ברכיבי זיכרון ובתקשורת. קיימות שלל שיטות נוספות לאיתור וטיפול בשגיאות, כמו למשל: [2]CRC. נגענו כאן רק בקצה הקרחון של הטכנולוגיות לגילוי ותיקון שגיאות. מקווים שהצלחתם לקלוט את הפוסט, לפחות בלי בעיות בזוגיות.

מקורות:

[1] קוד המינג

[2]  CRC