תיקון שגיאות ריד־סולומון, צעד אחר צעד ביד

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

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

הרעיון במשפט אחד

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

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

קידוד: ארבעה מספרים מודולו 7

ניקח שני סמלי מידע, 3 ו־2, כלומר k = 2. נשתמש בהם כמקדמים של ישר: p(x) = 3 + 2x. כל החשבון נעשה מודולו 7, כך שכל ערך נשאר בין 0 ל־6.

נחשב את הישר בארבע נקודות, n = 4: p(0) = 3, p(1) = 5, p(2) = 7 mod 7 = 0, p(3) = 9 mod 7 = 2. מילת הקוד היא 3, 5, 0, 2. שניים מארבעת הסמלים הם מידע ושניים הם יתירות.

שני סמלים אבדו: לשחזר אותם

נניח שהמקומות 0 ו־2 נהרסו, ואנחנו יודעים אילו. זה נקרא מחיקה. עדיין יש לנו p(1) = 5 ו־p(3) = 2, שתי נקודות על ישר, וזה מספיק.

השיפוע הוא (2 − 5) / (3 − 1). מודולו 7, 2 − 5 = −3, שזה 4, וחלוקה ב־2 פירושה כפל בהופכי של 2, שהוא 4, כי 2 × 4 = 8 = 1 mod 7. לכן השיפוע הוא 4 × 4 = 16 = 2 mod 7. נקודת החיתוך היא 5 − 2 × 1 = 3.

הישר הוא שוב 3 + 2x. המידע חזר, וגם שני הסמלים שאבדו. עם n − k = 2 סמלי יתירות, אפשר לתקן כל שתי מחיקות.

סמל אחד שגוי: למצוא אותו

שגיאה קשה יותר ממחיקה, כי לא יודעים איפה היא. נניח שמילת הקוד מגיעה כ־3, 5, 6, 2: הסמל במקום 2 השתנה מ־0 ל־6, ושום דבר לא מסמן אותו.

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

זה הכלל באופן כללי: עם n − k סמלי יתירות אפשר לתקן עד (n − k) / 2 שגיאות במקומות לא ידועים. למצוא סמל עולה סמל יתירות אחד ולתקן אותו עולה עוד אחד, ולכן שגיאה עולה פי שניים ממחיקה. מפענחים אמיתיים לא מנסים כל פולינום; הם מחשבים סינדרומים ופותרים את מיקומי השגיאות באלגוריתמים כמו ברלקמפ־מאסי. התשובה זהה לזו שהחיפוש הזה מוצא.

המספרים שחשובים

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

למה צריך שדה סופי

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

מחשבים מעדיפים שדות בגודל 2^m, שנכתבים GF(2^m), כדי שכל סמל יהיה מספר שלם של ביטים. קודי QR משתמשים ב־GF(256), שבו כל סמל הוא בייט אחד.

גודל השדה הוא בחירה, והוא צריך לנבוע מהמידע. למידע רציף מעל אלפבית קטן, כמו עשרים חומצות אמינו, השתמשתי ב־GF(32): סמל אחד מחזיק אות אחת ונשאר עוד מקום, במקום לבזבז עליה בייט שלם. ערכת הכלים פתוחה, ב־doi.org/10.6084/m9.figshare.32963456.

סמלים, לא ביטים

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