תוכנית תיקון שגיאות 'קסומה' הוכחה כלא יעילה מטבעה | מגזין קוונטה

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

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

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

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

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

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

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

כוח במספרים

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

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

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

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

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

לחשוב באופן גלובלי ולפעול באופן מקומי

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

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

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

"זו תפיסה ממש מחמירה", אמר קוטארי.

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

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

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

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

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

"אקספוננציאלי במקרה הזה הוא רע מאוד", אמר דביר. אבל האם זה בלתי נמנע?

ניתן לתיקון או לפענוח?

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

"ברגע שאתה הולך לשלוש, הידע שלנו הופך להיות מאוד מעורפל", אמר קוטארי.

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

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

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

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

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

לוגיקה בהשאלה

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

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

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

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

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

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

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

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

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

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