תיקון שגיאות - להגיד כמה שיותר בכמה שפחות

זה אחד השימושים המגניבים שנתקלתי בהם לריבועי גרקו

לווין בשמי הארץ

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

הלווין שולח הודעות שהתוכן שלהן הוא 0 במקרה והוא רוצה, למשל, להגיד ׳לא׳, או 1 אם הוא רוצה להגיד ׳כן׳.

זו תקשרות לא מורכבת מדי, אבל יש בה בעייתיות, והיא שלפעמים התווך רועש, והלווין יכול, למשל, לשלוח 1, אבל בדרך המסר ישתבש, ובכדור הארץ יתקבל 0.

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

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

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

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

מה אמרת?

אם למשל, בכדור הארץ מתקבלת הודעה שהתוכן שלה הוא 11. האם ניתן להסיק מכך שזה מה שהלווין התכוון לשלוח?

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

אין יותר מטעות אחת בהודעה אחת.

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

אז איפה פה הבעייתיות?

מה אם מתקבלת בכדור הארץ הודעה שהתוכן שלה הוא 01, או 10, האם אז היינו יכולים לקבוע בוודאות למה הלווין התכוון?

התשובה היא שאי אפשר. כי בשני המקרים אנחנו במרחק טעות אחת משתי המילים שהלווין יכול לשלוח - 00, ו-11.

אז מה עושים?

למה צריך לומר הכל שלוש פעמים?

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

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

אבל לפני זה, למה שלוש פעמים מספיקות?

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

מרחק בין שתי מילים הוא מספר המקומות בהם יש ספרות שונות. למשל:

• המרחק בין 000 ל-111 הוא שלוש.

• המרחק בין 001 ל-111 הוא שתיים.

• המרחק בין 001 ל-000 הוא אחד.

• המרחק בין 111 ל-111 הוא אפס.

שתי מילים הן קרובות אחת לשנייה ככל שהמרחק ביניהן קטן יותר.

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

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

ומתוך המילים בשפה, נשתמש במינוח ׳מילות קוד׳ כדי לתאר את מה שבאמת מעניין אותנו - המילים מתוך השפה שבהן מותר ללווין להשתמש.

שימו לב - אנחנו עדיין מניחים שיכולה להיות טעות אחת לכל היותר בהודעה.

אז, במקרה הקל - אם בכדור הארץ מתקבלת ההודעה 000, או 111, אז אין ספק שזו ההודעה המקורית.

ועבור כל הודעה אחרת, נפעיל עלייה את (סליחה על הקללה) פונקציית המרחק, ונבדוק למי מבין מילות הקוד היא יותר קרובה.

כך למשל, אם מתקבלת המילה 001, נשאל למי ממילות הקוד היא יותר קרובה, ל-000 או 111. ובמקרה הזה, התשובה היא - 000. וניתן לקבוע בוודאות שזה המסר שנשלח מהלווין.

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

למה זה משנה?

כי זה אומר שכל מילה שמתקבלת בכדור הארץ, תהיה בהכרח קרובה יותר לאחת ממילות הקוד, כי אף מילה לא יכולה להיות קרובה לשתי מילות הקוד במידה זהה.

דרך אחרת להסתכל על זה, היא שאם מרחק של מילה מסויימת מ-111 הוא אחד, אז המרחק שלה מ-000 הוא בהכרח שתיים.

הפסקה האחרונה מאוד חשובה להבנה. ומתוכה עולה הטענה הבאה:

(*) אם שתי מילות קוד נמצאות במרחק שלוש זו מזו, ניתן לשחזר מידע שאבד בהינתן טעות אחת לכל היותר.

נסמן את הטענה הזאת ב-(*).

אז עד כה הראנו דרך לשחזר מידע ולקבוע האם הלווין התכוון ל-000 או 111.

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

דבר אליי

אז נשאלת השאלה, האם ובאיזה אופן ניתן להגדיל את היצע מילות הקוד, תוך שמירה על היכולת לתקן שגיאות?

יש לנו שתי אפשרויות:

• להוסיף אותיות/ספרות - עד כה השתמשנו רק ב-0 ו-1, אפשר להוסיף גם 2 וכו׳.

• להוסיף/להאריך מילים - עד כה השתמשנו רק בשתי מילים, ורק באורך שלוש. אפשר לנסח עוד מילים או להאריך אותן. למשל 1111, 0000, 0011, וכו׳.

אז במי מבין האפשרויות נבחר... בשתיהן!

הגיבור שיציל את היום

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

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

אז, אם להיות קצת יותר ספציפי:

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

כל מילת קוד חדשה שניצור תהיה צירוף באורך ארבע שיהיה מורכב משלושת הספרות - 1, 2, 3 (ביי ביי 0).

אז למשל, הנה כמה דוגמאות למילים מתאימות - 1231, 2332, 1111. זה לא אומר שהן אכן יהיו מילות קוד שישמשו אותנו, אלא רק שהן עומדות בדרישות היבשות.

אז איך בוחרים מילות קוד?

נמחיש זאת בעזרת דוגמה - פתרון של ריבוע גרקו בגודל 3X3 (או - מסדר שלוש).

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

גרקו האיום

הגענו לשלב הקסם.

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

ניצור מילת קוד לכל משבצת

נפצל אותו לשני ריבועים שונים.

מה קורה כאן?

מבין הריבועים למטה:

• הריבוע הימיני, הוא העתק מדויק של הפתרון של הספרות מהריבוע העליון.

• הריבוע השמאלי, הוא העתק מדויק של הפתרון של האותיות מהריבוע העליון, כשכל אות הוחלפה בספרה באופן הבא: א-1, ב-2, ג-3.

(קחו רגע לוודא שזה ברור).

עכשיו ניצור ריבוע שלישי, ואחרון, באופן הבא - עבור כל אחת מבין תשע המשבצות, ניצור מספר בן ארבע ספרות:

• הספרה הראשונה תהיה מספר השורה של אותה משבצת (1, 2, או 3).

• הספרה השנייה תהיה מספר העמודה של אותה משבצת (1, 2, או 3).

• הספרה השלישית תהיה הספרה שנמצאת באותה משבצת בריבוע השמאלי (1, 2, או 3).

• הספרה הרביעית תהיה הספרה שנמצאת באותה משבצת בריבוע הימיני (1, 2, או 3).

לדוגמה, נבחר את המשבצת השמאלית התחתונה:

• מספר השורה - 3.

• מספר העמודה - 1.

• הספרה בריבוע השמאלי באותה משבצת - 1.

• הספרה בריבוע הימיני באותה משבצת - 2.

נחבר הכל יחד, וקיבלנו - 3112.

נעשה זאת עבור כל המשבצות, ונקבל:

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

אתם מוזמנים לבדוק זאת, בחרו שתי מילים באקראי, ותראו שהמרחק ביניהן הוא לפחות שלוש. למשל 3112 ו-3323, שני המספרים מופיעים על הריבוע ויש להם ספרות שונות בשלושה מיקומים.

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

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

(פרסומת)

סוד הקסם

למי שרוצה קצת להעמיק, הסיבה (הלוגית) לכך שהדבר הזה עובד היא ש:

אין שתי מילות קוד שונות עם שתי ספרות זהות באותם המיקומים.

תחשבו על זה רגע, זה היה יכול להיות מאוד בעייתי. כי אם למשל 1123 ו-1132 היו מילות קוד, מה היה קורה אם בגלל טעות, היה מתקבל בכדור הארץ 1133, או 1122?

במילים אחרות, אם לשתי מילות קוד שונות יש אותן שתי ספרות באותם המיקומים, המרחק ביניהן הוא לא שלוש.

וזה מוביל למסקנה החביבה:

(**) כל אחת ממילות הקוד החדשות ניתנת לשחזור באמצעות שתי ספרות בלבד.

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

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

1. שתי הספרות הראשונות. למשל 11, אז מספיק להציץ בפתרון של הריבוע גרקו, בשורה הראשונה והעמודה הראשונה, ולהבין מיד את ההמשך, שבמקרה הזה יהיה 33.

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

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

   
   

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

זה כמובן בהינתן וידוע לנו הפתרון המדויק.

(פרסומת)

עובדת בונוס

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

והיא נראית ככה (וזה מפחיד גם אותי):

ניתן ליצור קוד לשחזור E טעויות שיכיל q2 מילים באורך 2E + 2, בעזרת q ספרות אם ורק אם קיימים 2E פתרונות של ריבועים לטיניים אורתוגונליים זה לזה מסדר q.

הקיצר זה עוד מסתבך יופי יופי.

אם קראתם עד כאן, מקווה שנהניתם!

שימו את המייל איפה שצריך כדי שאנדנד לכם בנימוס כשיוצא פוסט חדש.

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

או בgood old ויקיפדיה.

או בשאר הפוסטים כאן באתר :)