קוד ריד-סולומון

קוד ריד-סולומון (באנגלית: Reed–Solomon code) הוא קוד תיקון שגיאות לינארי נפוץ ושימושי ביותר, המבוסס על אינטרפולציה באמצעות פולינומים מעל שדות סופיים. הקוד מיועד להעברה אמינה של מידע בערוץ תקשורת רועש (כדוגמת טלפון סלולרי), שבמידע המועבר בו עלולות להיווצר שגיאות, או לשמירת מידע במדיה שעלולה להיפגם (DVD, למשל), ולכן להכיל שגיאות.

מבוא

גוסטב סולומון (מימין) ואירווינג ריד

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

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

קוד ריד-סולומון המקוׂדֵד מחרוזת המכילה k אותיות (אות כנ"ל נקראת גם סימבול, ואורכה יכול להשתנות, ראו בהמשך) ל-n אותיות מסומן ב-RS(n,k)‎, ומסוגל לתקן עד $\ {\frac {1}{2}}(n-k)$ שגיאות (כלומר הוא קוד לינארי בעל הפרמטרים $\,[n,k,n-k+1]$); הקוד מתקן שגיאות במידה המקסימלית האפשרית לקוד בעל הפרמטרים $n$ ו-$k$.

שימושים והרחבות

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

שמירת מידע

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

תקן שמירת המידע בתקליטורים (CD) מגדיר שימוש בשתי שכבות של קוד ריד-סולומון, שיטה המכונה CIRC. השכבה הראשונה היא בעלת הפרמטרים RS(28,24)‎, לאחר מכן מתבצעת שזירה של המידע (פיזור הביטים כך שביטים עוקבים מורחקים אחד מהשני, interleaving), והפעלת קוד RS(32,28)‎ על המידע השזור. השכבה הראשונה מתמודדת עם פגמים בייצור התקליטור ובדרך שבה הוא נצרב (פגמי "מיקרו"). השכבה השנייה מיועדת להתמודד עם הפרעות כגון שריטות או טביעות אצבע, בעלות שטח הפרעה גדול יותר (פגמי "מאקרו").

ברקוד דו-ממדי עבור זיהוי ממצלמת מכשיר-נייד, בתקן QR המקודד בקוד ריד-סולומון

שימוש נוסף לקוד ריד-סולומון עבור שמירת מידע ניתן למצוא בברקודים מודרניים (דו-ממדיים). קריאת ברקודים אלו מבוצעת על ידי צילום הברקוד וזיהויי פסים או ריבועים שחורים ולבנים. זווית הצילום, המרחק, כמות האור וכן תקינות מדבקת הברקוד עצמה הם גורמים בעלי השפעה רבה על איכות הזיהוי של המידע בברקוד. מתוך הנחה שחלק מהריבועים לא יזוהו נכון, מקודד המידע באמצעות קוד ריד-סולומון ומפעונח במהירות וביעילות בצד הקורא האופטי. תקני ברקוד הכוללים קידוד ריד-סולומון הם PDF-417 ,PostBar ,MaxiCode ,Datamatrix‏ ,קוד QR‏ ,Aztec Code, ועוד.

שידור מידע

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

הגדרה

אינטרפולציה באמצעות פולינומים

‫

ערך מורחב – אינטרפולציה באמצעות פולינום

הרעיון המתמטי העומד מאחורי הקוד פשוט יחסית, ומבוסס על רעיון האינטרפולציה: על מנת להגדיר את הפולינום ‪$\ f(x)$‬ בצורה חד-חד ערכית, כאשר ידוע שהפולינום הוא ממעלה $\ k-1$‬ לכל היותר, נדרשות ‪$\ k$‬ נקודות בלבד בהן הערך של הפולינום ידוע.

המחשה של אינטרפולציה עבור הקו ‪$\ f(x)=0+0.6x$‬. הנקודה השלישית התקבלה שגויה. שלוש הנקודות שהתקבלו באופן תקין נמצאות על קו יחיד, בעוד הקוים העוברים דרך הנקודה השגויה אינם מתלכדים.

לדוגמה, פולינום ממעלה 1 לכל היותר, הוא קו ישר, מהצורה $\ f(x)=a+bx$‬‬. כלל ידוע הוא שמספיקות שתי נקודות על מנת להגדיר קו (קיימים 2 נעלמים, ועל-כן 2 נקודות מספיקות על מנת להגדיר את $\ a,b$‬ בצורה חד-ערכית). עקרון זה מתקיים גם כאשר המעלה של הפולינום גבוהה יותר.

נניח כי המטרה היא להעביר בערוץ תקשורת רועש את שני המספרים ‪$\ a,b$‬‬. כאשר משדרים את המספרים ישירות, ייתכן שאחד מהם "יתקלקל" עקב הרעש והמידע יגיע באופן שגוי. גם במקרה בו כל מספר יישלח פעמיים - במידה שאחד העותקים יתקלקל, לא ניתן יהיה להבחין מי מבין העותקים הוא הנכון ומי השגוי. שיטה אחרת היא להגדיר את הקו $\ f(x)=a+bx$ ולשלוח בערוץ התקשורת את ערך הפולינום ב-4 מקומות ידועים מראש (למשל, ב-$\ x=0,1,2,3$). הצד המקבל יוכל לבצע אינטרפולציה של הקו מתוך נקודות אלו ולזהות מהו הקו (הפולינום) שנשלח אליו.

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

ככל שנשדר את ערכי הפולינום עבור יותר ויותר ערכי $\ x$, היתירות תגדל, וניתן יהיה להתמודד עם מספר רב יותר של שגיאות.

קוד ריד-סולומון במובן הקלאסי

כאמור לעיל, המטרה היא לקחת $\ k$ מספרים כלשהם, שיסומנו $\ a_{0},a_{1},\ldots ,a_{k-1}$, להסתכל על הפולינום שמספרים אלו הם מקדמיו, $\ f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{k-1}x^{k-1}=\sum _{i=0}^{k-1}a_{i}x^{i}$‬ ולשדר את ערכי הפולינום עבור $\ n>k$ אינדקסים ידועים מראש.

בעוד שעד כה התייחסנו אל המספרים $\ a_{i},f(x)$ כאל מספרים כלשהם, הרי ששידור "מספר כלשהו" מצריך שידור כמות לא חסומה של מידע. פתרון לבעיה זו מתקבל על ידי שימוש בקבוצה סופית של מספרים שמהווה שדה סופי בגודל n אברים, אשר יסומן $\ {\mathbb {F} }_{n}$. אבר בשדה זה נקרא לרוב סימבול ומהווה את יחידת הבסיס של הקוד. על-מנת לשדר סימבול ניתן לקודד אותו לביטים או לעשות שימוש בשיטת אפנון מתקדמת בה כל סימבול (של הקוד) מזוהה עם סימבול של האפנון. כיוון שקיימים $\ n$ סימבולים אפשריים בשדה הסופי, ניתן לקודד כל סימבול על ידי $\log _{2}n$ ביטים.

באופן פורמלי:

קידוד ריד-סולומון מאורך $\ n$ ומממד $\ k$ מעל השדה הסופי $\ {\mathbb {F} }_{n}$ הוא המיפוי

$RS:(a_{0},a_{1},\ldots ,a_{k-1})\to \left(f(e_{1}),f(e_{2}),\ldots ,f(e_{n})\right)$

כאשר $\ f(x)=\sum _{i=0}^{k-1}a_{i}x^{i}$, ו $\ e_{i}\in {\mathbb {F} }_{n}$ הם כלל אברי השדה הסופי (כלל הסימבולים אפשריים). קוד ריד-סולומון הוא אוסף כלל המילים אשר ממופות על ידי המיפוי לעיל, עבור כל מילות המקור האפשריות, $\ a_{i}\in \mathbb {F} _{n}$.

‬קוד ריד-סולומון במובן מודרני

במקום לחשוב על המילה אותה אנו מקודדים, $a_{0},a_{1},\ldots ,a_{k-1}$, בתור מקדמים של פולינום, אנחנו יכולים לחשוב עליה כעל ערכים של פולינום ב-$k$ מקומות ידועים. ערכים אלו מגדירים פולינום (ממעלה לכל היותר $\ k-1$) בצורה חד-חד ערכית בהתאם לאינטרפולציה. אם המקומות הידועים הם $k$ האברים הראשונים של ${\mathbb {F} }_{n}$, תחילית מילת הקוד תהא מילת המקור (כלומר, מתקבל קוד סיסטמטי).

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

$\displaystyle g(x)=\prod _{i=1}^{n-k+1}(x-\alpha ^{i})$

כאשר $\alpha$ הוא שורש פרימיטיבי של השדה הסופי: $\alpha ^{n-1}=1$ ולכל $\ j<n-1$, $\alpha ^{j}\neq 1$. עבור מילת המקור $a_{0},a_{1},\ldots ,a_{k-1}$ המגדירה את הפולינום $\ f(x)$ המילה המקודדת היא מקדמי הפולינום $\ s(x)=f(x)g(x)$. משיקולי מעלות, הפולינום $\ s(x)$ הוא ממעלה $\ n-1$ לכל היותר, ועל כן יש לשדר $\ n$ סימבולים.

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

פענוח קוד ריד-סולומון

היסטוריה

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

העקרונות המתמטיים של פענוח (עבור קוד BCH) הוצגו לראשונה בשנת 1960 במאמר של פטרסון (Peterson), אשר הציג שיטה לפענוח קוד BCH בסיבוכיות של $\ O(n^{3})$. בשנת 1968 הציע ג'יימס מסי (Massey) דרך למימוש מפענח המבוסס על אוגרי הזזה בסיבוכיות של $\ O(n^{2})$. בשנת 1975 הציגה קבוצה של מדענים מיפן שיטה לפענוח הקוד המבוססת על אלגוריתם אוקלידס בעלת סיבוכיות דומה. בשנת 1995 הציגו הונג ווטרלי שיטה לביצוע הפענוח בסיבוכיות $\ O(n\log n)$.

פענוח בשיטה נאיבית

הדרך הפשוטה (מבחינה רעיונית) לפענח מילת קוד, היא לבצע אינטרפולציה של כל הפולינומים המוגדרים על ידי $k$ נקודות מתוך $n$ הנקודות שמכילה מילת הקוד. כפי שמוצג בדוגמה לעיל בה שוחזר קו מתוך 4 נקודות בהן נפלה שגיאה יחידה, 3 אינטרפולציות הזדהו עם הקו הנכון, וכל אינטרפולציה אחרת הייתה שונה. באופן כללי ייתכן שמספר אינטרפולציות שגויות יתלכדו זו עם זו; עדיין, אם כל אינטרפולציה כזו תעניק "קול" אחד לטובת הפולינום שהיא מגדירה - הפולינום הנכון יזכה במרב הקולות, וכל שאר הפולינומים השגויים יזכו במספר קולות קטן (אבל ייתכן שגדול מ-1). הבעיה בשיטת פענוח זו, היא שיש לבצע אינטרפולציה עבור כל אחת מתוך ${n \choose k}$ האפשרויות השונות, וזהו מספר גדול של חישובים שאינו נחשב יעיל. לדוגמה, בקוד RS(28,24)‎ אשר משמש תקליטורים, פענוח מילה יחידה (192 ביט של מידע) מצריך ביצוע כ-20 אלף אינטרפולציות (בעוד הזמן המוקצה לכך בתקליטור הוא כ-0.000136 שניות). באופן דומה, פענוח מילת קוד יחידה בקוד RS(208,192)‎ בו נעשה שימוש ב-DVD, מצריך ביצוע כ-$10^{20}$ אינטרפולציות - פעולה אשר תימשך מספר רב של ימים בטכנולוגיה בת ימינו.

פענוח לפי סינדרום (ברלקמפ-וולש)

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

נניח כי בעוד שנשלחה מילת הקוד $\ s_{0},s_{1},\ldots ,s_{n-1}$ המתאימה לפולינום $\ f(x)$ המוגדר לעיל, בצד הקולט התקבלה המילה $\ r_{0},r_{1},\ldots ,r_{n-1}$ אשר נפלו בה $\ t=(n-k)/2$ שגיאות לכל היותר, כלומר, עבור $\ t$ אינדקסים לכל היותר $\ r_{i}\neq s_{i}$. כזכור, כלל הערכים הם אברים בשדה הסופי $\mathbb {F} _{n}$.

ניתן להגדיר פולינום שגיאה אשר יסומן $\ E(x)$. התכונות של פולינום השגיאה הן שבכל אינדקס $\ i$ בו קרתה שגיאה, הפולינום יקבל את הערך 0, מעלתו תהיה $\ t$, והוא נדרש להיות פולינום מתוקן. הצד המקבל לא יודע לבנות את פולינום השגיאה (כי אינו יודע את האינדקסים שבהן קרו שגיאות), אבל ידוע שפולינום כנ"ל קיים.

עקרון המפתח הוא שקיים פולינום ממעלה $\ k-1+t$ לכל היותר, שנסמנו $\ V(x)$ ומתקיים:

$V(i)=r_{i}\cdot E(i)$

למשל, אם $\ V(x)=f(x)E(x)$, אזי $\ V(x)$ הוא ממעלה $\ k-1+t$ לכל היותר, והמשוואה לעיל מתקיימת לכל אינדקס $i\in \mathbb {F} _{n}$. לכן אם ידועים הפולינומים $\ V(x),E(x)$ ניתן לפענח את המילה המקורית על ידי ביצוע חלוקה: $\ f(x)=V(x)/E(x)$. לא ייתכן שקיים פולינום אחר (ממעלה $\ k-1$ לכל היותר) אשר שווה לתוצאת החלוקה, ולכן שיטה זו תשחזר את הפולינום הנכון.

ניתן למצוא את הפולינומים $\ V(x),E(x)$ בצורה יעילה: יהיו $v_{0},v_{1},\ldots ,v_{k+t}$ המקדמים של הפולינום $\ V(x)$, ויהיו $e_{0},e_{1},\ldots ,e_{t}$ המקדמים של $\ E(x)$. כזכור, $\ E(x)$ הוא פולינום מתוקן, ועל-כן $\ e_{t}=1$. אם מציבים ב-$\ V(i)=r_{i}\cdot E(i)$ את כל אחד מאברי השדה, מתקבלת מערכת של $n$ משוואות לינאריות עם $\ (k+t+1)+(t-1)$ נעלמים (מקדמי $\ V(x),E(x)$). מכיוון שכמות השגיאות מוגבלת ב-$\ t\leq (n-k)/2$ מספר הנעלמים הוא $\ k+2t\leq n$, והמערכת ניתנת לפתרון.

פענוח בערוץ מחיקה

מודל מתמטי של ערוץ מחיקה בינארי. בהסתברות מסוימת $1-p$ הביט מגיע ליעד בצורה תקינה, ובהסתברות $p$ חלה "מחיקה" ($e$).

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

שגיאות מסוג זה קלות מאד לתיקון על ידי קוד ריד-סולומון. בהנחה שבקוד RS(n,k)‎ חלו $(n-k)$ מחיקות לכל היותר, ניתן לעשות שימוש בשאר $k$ הערכים שנקלטו ולבצע אינטרפולציה לפולינום שנשלח. מכיוון שנקודות אלו הגיעו ללא שגיאה, האינטרפולציה תצליח תמיד. מכאן שתיקון מחיקות "קל" יותר מאשר תיקון שגיאות. שיטה לתיקון שגיאות היא רבת עוצמה יותר משיטה לתיקון מחיקות: ניתן להפוך מחיקה לשגיאה על ידי כך שנגריל ערך אקראי כלשהו במקום המחיקה. מן הסתם, ערך זה יהיה שגוי ויתפרש כ"שגיאה", אך כעת ניתן להפעיל את שיטת הפענוח להתמודדות עם שגיאות. מאידך, הקושי בהימצאותן של שגיאות (לעומת מחיקות) הוא שלא ידוע מיקומן של השגיאות, ואלגוריתם הפענוח נדרש להבדיל איזו נקודה היא השגויה ואיזו התקינה.

פענוח מחיקות ושגיאות בו זמנית

כאמור לעיל, קוד ריד-סולומון מסוגל להתמודד עם $s\leq n-k$ מחיקות או עם $t$ שגיאות כאשר $2t\leq n-k$. ניתן לשלב את שני אלו ולקבל כי קוד ריד-סולומון מסוגל להתמודד עם $s$ מחיקות וגם $t$ שגיאות, כל עוד $s+2t\leq n-k$.

יעילות הקוד במקרים פרטיים שונים

קוד RS(n,k)‎ מסוגל לתקן עד $\ (n-k)/2$ סימבולים שגויים. במידה וכל סימבול מיוצג כרצף של ביטים באורך $c$ הקוד יכול להתמודד עם לכל הפחות $\ (n-k)/2$ ביטים שגויים (המפוזרים כל אחד בסימבול שונה), אך ייתכנו מצבים בהם הקוד מסוגל להתמודד עם עד $\ c(n-k)/2$ ביטים שגויים, המקובצים כולם ב-$\ (n-k)/2$ סימבולים שונים, לכל היותר. תכונה זו הופכת את הקוד לחזק במיוחד כאשר מדובר בערוץ בינארי בו פיזור השגיאות הוא ב"פרצים" צמודים. בנוסף, כאשר משתמשים במספר שכבות קוד תיקון-שגיאות (למשל, שתי שכבות קוד ריד-סולומון כפי שקיים בתקליטורים, או קוד קונבולוציה וקוד ריד-סולומון, כפי שמצוי בגשושית וויאג'ר), במידה והקוד הפנימי אינו מצליח לתקן את השגיאה, הוא מסמן זאת עבור הקוד החיצוני. כעת קוד ריד-סולומון בשכבה החיצונית יכול להתייחס לערך המסומן כאל "מחיקה" ולשפר את יכולת תיקון השגיאות.

הרחבות

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

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

קודי ריד-סולומון מוכללים

משפחה יותר רחבה של קודי ריד-סולומון, מתקבלת כאשר מילת הקוד מוכפלת בפולינום קבוע $v(x)$ שהוא פרמטר של הקוד. משפחה זו נקראת קודי ריד-סולומון מוכללים, ולכל ${{\mathbf {\alpha } }=\alpha _{1}\alpha _{2}\ldots \alpha _{n}},{\mathbf {v} }=v_{1}v_{2}\ldots v_{n}\in {\mathbb {F} }^{n}$ המוגדרים מעל השדה הסופי $\mathbb {F}$ בגודל $n$ לכל הפחות, הקוד $GRS_{\mathbf {v} ,\mathbf {\alpha } }$ מוגדר בתור אוסף המילים המתקבל על ידי הקידוד:

$GRS_{\mathbf {v} ,\mathbf {\alpha } }:(a_{0},a_{1}\ldots a_{k-1})\to (v_{1}f(\alpha _{1}),v_{2}f(\alpha _{2}),\ldots ,v_{n}f(\alpha _{n}))$

הפרמטר $\mathbf {\alpha }$ מאפשר להקטין את אורך הקוד על ידי דגימת הפולינום בחלק מאברי השדה הסופי (המוגדרים על ידי $\mathbf {\alpha }$) ולא בכלל השדה. ניתן לראות כי קוד ריד-סולומון שהוגדר לעיל הוא מקרה פרטי של הקוד המוכלל, כאשר $\alpha _{i}$ הם כלל אברי השדה הסופי, ו-${\mathbf {v} }=(1,1,\ldots ,1)$.

פענוח רשימה

עד כה, אלגוריתמי הפענוח ידעו להתמודד עם כמות שגיאות החסומה ב-$d/2\equiv (n-k)/2$. הערך $d$ מסמל את מרחק המינג המינימלי בין שתי מילות קוד ונקרא גם מרחק הקוד. אם כמות השגיאות שקרו קטנה ממחצית מרחק הקוד - קיימת רק מילת קוד אחת שיכולה להיות זו שנשלחה ושיטות הפענוח שתוארו לעיל מצליחות לגלותהּ. נשאלת השאלה מה ניתן לעשות כאשר קרו יותר שגיאות?

במקרה זה, לא ניתן לדעת בוודאות מהי המילה שנשלחה, אבל ניתן לקבל רשימה של מילות מקור אפשריות. כל עוד מספר השגיאות שקרו קטן ממרחק הקוד - רשימה זו תהיה "קטנה": פולינומית באורך הקוד. מצד שני, אם מספר השגיאות גדול ממרחק הקוד - הרשימה תהיה ענקית: אקספוננציאלית באורך הקוד. בשנת 1997 הציע מדו סודן שיטה לבצע פענוח רשימה לקודי ריד-סולומון, בסיבוכיות פולינומית, תוצאה ששופרה בשנת 1999 וידועה בשם גורוסוואמי-סודן (Guruswami-Sudan) על שם ממציאיה. שיטה זו מאפשרת להתמודד עם $n-{\sqrt {nk}}$ שגיאות. אם מסמנים את קצב הקוד $R=n/k$ מתקבל כי השיטה מתמודדת עם אחוז שגיאות של $1-{\sqrt {R}}$ (כאשר החסם המקסימלי (מרחק הקוד) מהווה אחוז שגיאות של $1-R$).

בשנת 2004 הציגו פרברש וורדי (Parvaresh, Vardi) קוד המבוסס על ריד-סולומון, בו כל סימבול מהווה ערכים של שני פולינומים שונים. פענוח רשימה בשיטה הדומה לזו שהציגו גורוסוואמי-סודן מאפשר להתמודד עם אחוז שגיאות של $1-{\sqrt[{3}]{2R^{2}}}$. הרחבה של קוד פרברש-ורדי ל-$m$ פולינומים שונים מאפשר התמודדות עם $1-{\sqrt[{m+1}]{m^{m}R^{m}}}$ אשר עבור בחירת $m$ גדול דיו מאפשרת אחוז שגיאות של $\ 1-O(R\log(1/R))$. בעוד גורוסוואמי וסודן הראו איך לעשות שימוש בקוד ריד-סולומון עצמו, הרי שפרברש וורדי מגדירים קוד חדש (שמבוסס למעשה על שליחת מספר עותקים של מילת ריד-סולומון).

בשנת 2007 הציגו גורוסוואמי ורודרה (Guruswami, Rudra) כיצד להתקרב לחסם ולקבל קוד המתמודד עם יחס שגיאות של $1-R-\epsilon$ לכל $\epsilon >0$. הקוד של גורוסוואמי ורודרה, הידוע בשם קוד ריד-סולומון מקופל (Folded Reed-Solomon Code), מראה כיצד ניתן "לקפל" את ערכי הפולינומים השונים לתוך סימבול אחד, בשיטה דומה לקוד פרברש-ורדי אך בצורה יעילה יותר. הקיפול אפשרי לאור העובדה שקיים קשר בין הפולינומים השונים הנשלחים בקוד, וקשרים אלו יכולים לשמש לחסכון בשליחת מידע, ולהגדלת יעילות הקוד.

ראו גם

• תורת הקודים
• קוד תיקון שגיאות
• קוד לינארי

קישורים חיצוניים

• מעבדת לינקולן ב-MIT (באנגלית)
• מקודד ומפענח ריד-סולומון בשפת Java (קוד פתוח), אתר sourceforge (באנגלית)

הערות שוליים

‫‫