אלגוריתם הפענוח מקבל כקלט את המילה הארוכה, ייתכן בתוספת שיבושים שונים שנוספו לה עקב השידור בערוץ הרועש. אלגוריתם הפענוח מנסה לשחזר את מילת המקור מתוך הקלט, כאשר היתירות שהוספה בתהליך הקידוד משמשת אותו להתמודדות עם השגיאות שקרו. תהליך הפענוח מורכב מאשר תהליך הקידוד. ריד וסולומון לא הציגו שיטת פענוח יעילה, וזו הומצאה בשנת 1967.
קוד ריד-סולומון המקוׂדֵד מחרוזת המכילה k אותיות (אות כנ"ל נקראת גם סימבול, ואורכה יכול להשתנות, ראו בהמשך) ל-n אותיות מסומן ב-RS(n,k), ומסוגל לתקן עד formula_1 שגיאות (כלומר הוא קוד ליניארי בעל הפרמטרים formula_2); הקוד מתקן שגיאות במידה המקסימלית האפשרית לקוד בעל הפרמטרים formula_3 ו-formula_4.
שימושים והרחבות.
פיתוח שיטת קידוד יעילה וכן התפתחות תקשורת הנתונים הובילו לשימוש נרחב בקודי-תיקון שגיאות ובראשם בקודי ריד-סולומון. בימינו ניתן למצוא מערכות אלקטרוניות רבות אשר עושות שימוש בקודי ריד-סולומון, דוגמת מכשירי רדיו (הן קוויים, דוגמת ערוצי DSL, והן אלחוטיים דוגמת WiMAX), תקליטורים ו־DVD, ומקודדי-וידאו. שימושים נוספים של הקוד הם לשיפור מערכות פיזור ספקטרום של מערכות תקשורת אלחוטיות, וכן בהתמודדות עם שגיאות חד-כיווניות, מהסוג הנפוץ באפיקי נתונים מהירים של מחשבים.
תוכנית וויאג'ר התאפיינה במאזן ערוץ הנמוך ביותר בערוצי תקשורת. בעקבות כך במהלך התוכנית לחללית וויאג'ר 2 היה צורך בהחלפת תוכנת תקשורת שהוחלפה במתקדמת יותר שמנצלת קוד ריד-סולומון כפול.
שמירת מידע.
קיים שימוש נרחב בקוד ריד-סולומון להתקנים שונים לשמירת מידע. במדיות רבות (בעיקר מדיות אופטיות) ההתקן עצמו גורם לשגיאות במידע השמור (למשל, עקב שריטות או פגמים אחרים) ובשל כך נדרשת יתירות במידע עצמו השמור על-גבי המדיה.
תכונות השגיאות במדיות אלו הופכות את קוד ריד-סולומון לפתרון יעיל. לרוב השגיאות הנובעות מ"פגם" אינן מפוזרות אלא מקובצות יחדיו, ומתקבל רצף (burst) של שגיאות עמו הקוד מסוגל להתמודד היטב.
תקן שמירת המידע בתקליטורים (CD) מגדיר שימוש בשתי שכבות של קוד ריד-סולומון, שיטה המכונה CIRC. השכבה הראשונה היא בעלת הפרמטרים RS(28,24), לאחר מכן מתבצעת שזירה של המידע (פיזור הביטים כך שביטים עוקבים מורחקים אחד מהשני, interleaving), והפעלת קוד RS(32,28) על המידע השזור.
השכבה הראשונה מתמודדת עם פגמים בייצור התקליטור ובדרך שבה הוא נצרב (פגמי "מיקרו"). השכבה השנייה מיועדת להתמודד עם הפרעות כגון שריטות או טביעות אצבע, בעלות שטח הפרעה גדול יותר (פגמי "מאקרו").
שימוש נוסף לקוד ריד-סולומון עבור שמירת מידע ניתן למצוא בברקודים מודרניים (דו-ממדיים). קריאת ברקודים אלו מבוצעת על ידי צילום הברקוד וזיהוי פסים או ריבועים שחורים ולבנים. זווית הצילום, המרחק, כמות האור וכן תקינות מדבקת הברקוד עצמה הם גורמים בעלי השפעה רבה על איכות הזיהוי של המידע בברקוד. מתוך הנחה שחלק מהריבועים לא יזוהו נכון, מקודד המידע באמצעות קוד ריד-סולומון ומפעונח במהירות וביעילות בצד הקורא האופטי. תקני ברקוד הכוללים קידוד ריד-סולומון הם PDF-417 ,PostBar ,MaxiCode ,Datamatrix ,קוד QR ,Aztec Code, ועוד.
שידור מידע.
אפליקציה משמעותית נוספת של הקוד היא עבור שידור מידע בתקשורת קווית או אלחוטית. אחת האפליקציות המפורסמות של קוד זה הייתה עבור המשדר של הגשושית וויאג'ר, בעת מסעה אל אורנוס ונפטון. גם במקרה זה הקוד בנוי משתי שכבות, כאשר השכבה הנוספת היא קוד קונבולוציה כגון קוד טורבו או קוד ויטרבי, אשר בעת שגיאה בתהליך הפענוח נוטים לייצר פרצי שגיאות, עמם קוד ריד-סולומון מתמודד בצורה טובה. בשיטה זו נעשה שימוש נרחב במשדרים לחלל העמוק, לרבות עבור גלילאו וגשושי משימות חקר מאדים, והפך לתקן המוסכם על ידי הוועדה המייעצת למערכות מידע בחלל (CCSDS).
הגדרה.
אינטרפולציה באמצעות פולינומים.
הרעיון המתמטי העומד מאחורי הקוד פשוט יחסית, ומבוסס על רעיון האינטרפולציה:
על מנת להגדיר את הפולינום formula_5 בצורה חד-חד ערכית, כאשר ידוע שהפולינום הוא ממעלה formula_6 לכל היותר, נדרשות formula_7 נקודות בלבד בהן הערך של הפולינום ידוע.
לדוגמה, פולינום ממעלה 1 לכל היותר, הוא קו ישר מהצורה formula_8.
כלל ידוע הוא שמספיקות שתי נקודות על מנת להגדיר קו (קיימים 2 נעלמים, ועל-כן 2 נקודות מספיקות על מנת להגדיר את הערכים formula_9 בצורה חד-ערכית). עקרון זה מתקיים גם כאשר המעלה של הפולינום גבוהה יותר.
נניח כי המטרה היא להעביר בערוץ תקשורת רועש את שני המספרים formula_9.
כאשר משדרים את המספרים ישירות, ייתכן שאחד מהם "יתקלקל" עקב הרעש והמידע יגיע באופן שגוי. גם במקרה בו כל מספר יישלח פעמיים – במידה שאחד העותקים יתקלקל, לא ניתן יהיה להבחין מי מבין העותקים הוא הנכון ומי השגוי.
שיטה אחרת היא להגדיר את הקו formula_8 ולשלוח בערוץ התקשורת את ערך הפולינום ב-4 מקומות ידועים מראש (למשל, ב-formula_12). הצד המקבל יוכל לבצע אינטרפולציה של הקו מתוך נקודות אלו ולזהות מהו הקו (הפולינום) שנשלח אליו.
גם אם נפלה טעות יחידה באחת מתוך ארבע הנקודות שנשלחו, הצד המקבל יכול לדעת מהו הקו הנכון על-פי 3 הנקודות האחרות: כל זוג נקודות מגדיר קו אחד, ולכן ארבעת הערכים שנשלחו מגדירים שישה קווים אפשרים. אם כל הערכים התקבלו באופן תקין – כל ששת הקווים יהיו זהים. לעומת זאת, אם נפלה טעות יחידה, 3 קווים יתלכדו עם הקו המקורי, בעוד שאר הקווים יהיו קווים שונים (ראו הדגמה בתמונה). כך ניתן לזהות איזו נקודה סטתה מהקו המקורי ולשחזר בהצלחה את הקו המקורי.
ככל שנשדר את ערכי הפולינום עבור יותר ויותר ערכי formula_13, היתירות תגדל, וניתן יהיה להתמודד עם מספר רב יותר של שגיאות.
קוד ריד-סולומון במובן הקלאסי.
כאמור לעיל, המטרה היא לקחת formula_7 מספרים כלשהם, שיסומנו
formula_15,
להסתכל על הפולינום שמספרים אלו הם מקדמיו,
formula_16
ולשדר את ערכי הפולינום עבור formula_17 אינדקסים ידועים מראש.
בעוד שעד כה התייחסנו אל המספרים
formula_18
כאל מספרים כלשהם, הרי ששידור "מספר כלשהו" מצריך שידור כמות לא חסומה של מידע. פתרון לבעיה זו מתקבל על ידי שימוש בקבוצה סופית של מספרים שמהווה שדה סופי בגודל n איברים, אשר יסומן formula_19.
איבר בשדה זה נקרא לרוב סימבול ומהווה את יחידת הבסיס של הקוד. על-מנת לשדר סימבול ניתן לקודד אותו לביטים או לעשות שימוש בשיטת אפנון מתקדמת שבה כל סימבול (של הקוד) מזוהה עם סימבול של האפנון. כיוון שקיימים formula_20
סימבולים אפשריים בשדה הסופי, ניתן לקודד כל סימבול על ידי formula_21 ביטים.
באופן פורמלי:
קידוד ריד-סולומון מאורך formula_20
ומממד formula_7
מעל השדה הסופי
formula_19
הוא המיפוי
formula_25
כאשר formula_26,
ו formula_27
הם כלל אברי השדה הסופי (כלל הסימבולים אפשריים). קוד ריד-סולומון הוא אוסף כלל המילים אשר ממופות על ידי המיפוי לעיל, עבור כל מילות המקור האפשריות, formula_28.
קוד ריד-סולומון במובן מודרני.
במקום לחשוב על המילה אותה אנו מקודדים, formula_29, בתור מקדמים של פולינום, אנחנו יכולים לחשוב עליה כעל ערכים של פולינום ב-formula_4 מקומות ידועים. ערכים אלו מגדירים פולינום (ממעלה לכל היותר formula_6) בצורה חד-חד ערכית בהתאם לאינטרפולציה. אם המקומות הידועים הם formula_4 האיברים הראשונים של formula_33, תחילית מילת הקוד תהא מילת המקור (כלומר, מתקבל קוד סיסטמטי).
הגדרה זו מראה כי קוד ריד-סולומון הוא מקרה פרטי של משפחת קודים רחבה יותר בשם קודי BCH. קוד BCH הוא קוד ציקלי עבורו קיים פולינום formula_34 בעל תכונות מסוימות הנקרא יוצר של הקוד, וכל מילת קוד היא מכפלה של הפולינום היוצר בפולינום המוגדר על ידי מילת המקור.
בצורה זו, קוד ריד-סולומון מוגדר על ידי היוצר
formula_35
כאשר formula_36 הוא שורש פרימיטיבי של השדה הסופי: formula_37 ולכל formula_38, formula_39. עבור מילת המקור formula_29 המגדירה את הפולינום formula_5 המילה המקודדת היא מקדמי הפולינום formula_42. משיקולי מעלות, הפולינום formula_43 הוא ממעלה
formula_44 לכל היותר, ועל כן יש לשדר formula_20 סימבולים.
ניתן להראות כי הגדרה זו שקולה להגדרה המקורית של הקוד שהוצגה במאמרם של ריד וסולומון.
פענוח קוד ריד-סולומון.
היסטוריה.
בעוד קידוד מילה בשיטת ריד-סולומון הוא משימה פשוטה וקלה, פענוח הוא משימה מסובכת הצורכת משאבים רבים. פריצת הדרך בגילוי שיטה יעילה לפענוח התרחשה בשנת 1967, על ידי המתמטיקאי אלווין ברלקמפ (Berlekamp) שהציג אלגוריתם לפענוח קוד BCH מתוך ההבנה שקוד ריד-סולומון הוא מקרה פרטי של קוד BCH.
העקרונות המתמטיים של פענוח (עבור קוד BCH) הוצגו לראשונה בשנת 1960 במאמר של פטרסון (Peterson), אשר הציג שיטה לפענוח קוד BCH בסיבוכיות של formula_46. בשנת 1968 הציע ג'יימס מסי (Massey) דרך למימוש מפענח המבוסס על אוגרי הזזה בסיבוכיות של formula_47. בשנת 1975 הציגה קבוצה של מדענים מיפן שיטה לפענוח הקוד המבוססת על אלגוריתם אוקלידס בעלת סיבוכיות דומה.
בשנת 1995 הציגו הונג ווטרלי שיטה לביצוע הפענוח בסיבוכיות formula_48.
פענוח בשיטה נאיבית.