האלגברה הבסיסית מאחורי הקודים הסודיים ותקשורת החלל

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

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

שני תלמידים, ארט וזק, מחליפים מסרים סודיים בשיעור המתמטיקה של גב' אל-ג'בר. ארט מגלה את הפתק האחרון של זקה כדי לחשוף את המספרים 57 ו-99. הוא יודע שהוא צריך לספק את x-קואורדינטות 3 ו-6 ליצירת הנקודות (3, 57) ו- (6, 99). אמנות מחברת כל נקודה למשוואה הליניארית y = Ax + B ומייצר את מערכת המשוואות הבאה:

57 = 3A + B

99 = 6A + B

כדי לפענח את המסר, אמנות צריכה לפתור A ו B. הוא מתחיל בהפחתת המשוואה הראשונה מהשנייה:

זה מבטל B. חלוקת שני הצדדים של המשוואה החדשה הזו ב-3 אומרת לאמנות את זה A = 14, ולאחר מכן החלפת זה בחזרה לתוך המשוואה הראשונה, 57 = 3 × 14 + B, נותן B = 15.

האמנות יודעת כעת שהקו העובר דרך (3, 57) ו- (6, 99) מתואר על ידי המשוואה y = 14x + 15. אבל הוא גם יודע שבקוד ריד-שלמה, המסר הסודי מסתתר במקדמים. הוא מפענח את ההודעה של זקה באמצעות צופן האלפבית המוסכם הפשוט שלהם: 14 הוא "N" ו-15 הוא "O", מה שאומר לאמנות שלא, זקה לא יכול לשחק במשחקי וידאו אחרי בית הספר היום.

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

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

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

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

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

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

השורה y = 14x + 15 זה בסדר לשדר את המילה בת שתי אותיות "לא", אבל מה אם התלמידים רוצים לחלוק סוד ארוך יותר? כאן נכנס לתמונה העוצמה המלאה של אלגברה, גיאומטריה ומערכות של משוואות ליניאריות.

נניח שזק רוצה לדעת איך ארט חושב שהוא יסתדר במבחן האנגלית של מחר. ארט ממיר את תשובתו בת שלוש האותיות למספרים 14, 59 ו-82 ומעביר את אלה לזק. התלמידים הסכימו מראש שכאשר משתמשים בקודי ריד-סולומון באורך 3, המספרים הפרטיים שלהם הם 2, 5 ו-6, אז זק מחבר את החלקים כדי לבנות מחדש את הנקודות (2, 14), (5, 59) ו- (6, 82).

כעת, אין פונקציה לינארית שעוברת דרך שלוש הנקודות הללו. אבל יש פונקציה ריבועית ייחודית שעושה זאת. ומכיוון שכל פונקציה ריבועית יכולה להיכתב בצורה y = Ax² + Bx + C, ניתן ליישם את אותה שיטה כללית. ההבדל היחיד הוא גודל המערכת.

מחבר כל נקודה ל y = Ax² + Bx + C מניב משוואה אחת, אז שלוש הנקודות מייצרות את המערכת הבאה של שלוש משוואות:

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

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

לדוגמה, אם אתה מחסיר את המשוואה הראשונה מהשנייה, אתה מקבל את המשוואה החדשה 45 = 21A + 3B. באופן דומה, אם מחסירים את המשוואה השנייה מהשלישית, מקבלים 23 = 11A + B. המניפולציות האלגבריות הללו מייצרות מערכת חדשה:

45 = 21A + 3B

23 = 11A + B

עכשיו יש לך מערכת "שתיים על שתיים": שתי משוואות עם שני לא ידועים. כדי לפתור אותה, אתה יכול להכפיל את המשוואה השנייה ב-3 ולהוסיף אותה למשוואה הראשונה:

שימו לב כיצד חיסול חוזר ונשנה הפך את המערכת המקורית של שלוש משוואות למשוואה אחת שניתן לפתור בקלות: A = 2. עבודה אחורה, אתה יכול לחבר A = 2 לתוך אחת מהמשוואות במערכת שניים על שתיים כדי למצוא B = 1, ולאחר מכן חבר את שני הערכים לאחת מהמשוואות המקוריות כדי לקבל C = 4. לאחר שימוש בצופן האלפבית הפשוט ב-2, 1 ו-4, זקה יודע שארט הולך לעשות "BAD" במבחן האנגלית של מחר. לפחות הוא מתאמן רבות באלגברה.

הודות לעובדה מיוחדת על פונקציות פולינום, אתה יכול להעביר הודעה בכל אורך באמצעות קודי ריד-סולומון. המפתח הוא זה: בהינתן כל n נקודות במטוס עם שונות x-קואורדינטות, יש פולינום ייחודי של "תואר" n − 1 שעובר דרכם. דרגת פולינום היא החזקה הגבוהה ביותר של משתנה בביטוי, אז פונקציה ריבועית כמו Ax² + Bx + C יש תואר 2, מאז הכוח הגבוה ביותר של x הוא 2. ולפונקציה לינארית יש תואר 1, שכן במשוואה y = Ax + B, הכוח הגבוה ביותר של x הוא 1.

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

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

פתרון אחד לבעיה זו יהיה פשוט לשלוח עותקים נוספים של הנתונים. לדוגמה, Zeke יכול לשלוח את ההודעה [14, 14, 14, 15, 15, 15] במקום [14, 15]. כל עוד ארט יודע שכל חלק בהודעה נשלח בשלושה עותקים, הוא יכול לפענח את ההודעה ולבדוק אם יש שגיאות. למעשה, אם הוא מוצא טעויות, יש לו סיכוי טוב לתקן אותן. אם ארט מקבל [14, 14, 24, 15, 15, 15], העובדה ששלושת המספרים הראשונים שונים מזהירה אותו על שגיאה, ומכיוון ששניים מהם הם 14, הוא יכול לנחש שה-24 כנראה צריך להיות 14 גם כן. במקום לבקש להתרעם על המסר, ארט יכול להמשיך בפענוח שלו. זוהי אסטרטגיה יעילה אך יקרה. בכל זמן, אנרגיה ומאמץ נדרשים לשלוח n פיסות מידע, זה דורש פי שלושה.

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

כדי לראות איך זה עובד, נניח שאתה רוצה לבדוק את ההודעה "לא" בדוגמה הראשונה. Zeke יכול פשוט לשלוח את הנוסף y-קואורדינטה 155. בהנחה שהוא וארט הסכימו על פרטי שלישי x-תאם מראש, נגיד x = 10, ארט יכול לבדוק את הנקודה השלישית הזו מול הקו שהוא פיענח. כשהוא מתחבר x = 10 לתוך y = 14x + 15 ורואה שהתוצאה היא 155, הוא יודע שלא היו שגיאות בשידור.

זה לא עובד רק עבור קווים. כדי לאפשר ל-Zeke לסמן "BAD" בדוגמה השנייה, Art יכול לשלוח y = 25. אם הם הסכימו ש-3 הוא הפרטי הנוסף x-קואורדינטה, זקה יכול לחבר x = 3 לפונקציה הריבועית שלו y = 2x² + x + 4 וודא שהנקודה (3, 25) מתאימה, שוב מאשר שידור ללא שגיאות עם עוד נקודה אחת בלבד.

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

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

תרגילים

1. באמצעות אותה סכמה שבה השתמשו בכיתה, ארט מפרסם את המספרים הציבוריים 33 ו-57 כדי ש-Zeke יוכל לפענח. מה המסר?

2. איך ארט וזק יכולים להיות בטוחים שמערכת המשוואות הנובעת מהמספרים הפרטיים שלהם x = 3 ו- x = 6 תמיד יהיה פתרון?

3. בתגובה להודעת "BAD" של ארט לגבי המבחן באנגלית, Zeke שולח בחזרה [90, 387, 534]. בהנחה שהם משתמשים באותה סכמה שבה השתמשו בכיתה, מה המסר שלו?

4. לולה שולחת לך הודעה בת שתי אותיות בתוספת מספר אחד לבדיקת שגיאות באמצעות קוד ריד-סולומון ובאותו צופן אלפבית פשוט בשימוש על ידי ארט וזקה. הסכמת בסתר על x-קואורדינטות 1, 3 ו-10 מראש, ולולה משדרת את המספרים הציבוריים [27, 43, 90]. האם ההודעה מכילה שגיאה?