קוד ריד-סולומון – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ קישורים פנימיים |
אין תקציר עריכה |
||
שורה 11:
אלגוריתם הפענוח מקבל כקלט את המילה הארוכה, ייתכן בתוספת שיבושים שונים שנוספו לה עקב השידור בערוץ הרועש. אלגוריתם הפענוח מנסה לשחזר את מילת המקור מתוך הקלט, כאשר היתירות שהוספה בתהליך הקידוד משמשת אותו להתמודדות עם השגיאות שקרו. תהליך הפענוח מורכב מאשר תהליך הקידוד. ריד וסולומון לא הציגו שיטת פענוח [[חישוב יעיל|יעילה]], וזו הומצאה בשנת 1967.
קוד ריד-סולומון המקודד מחרוזת המכילה k אותיות (אות כנ"ל נקראת גם סימבול, ואורכה יכול להשתנות, ראו בהמשך) ל-n אותיות מסומן ב-RS(n,k){{כ|ימינה=כן}}, ומסוגל לתקן עד <math>\ \frac{1}{2}(n-k)</math> שגיאות (כלומר הוא [[קוד לינארי]] בעל הפרמטרים <math>\,[n,k,n-k+1]</math>); הקוד מתקן שגיאות במידה המקסימלית האפשרית לקוד בעל הפרמטרים <math>n</math> ו-<math>k</math>.{{
<math>d\le n-k+1</math>. קוד ריד-סלומון מקיים את השוויון. מכיוון שבקוד כלשהו ניתן לתקן לכל היותר <math>d/2</math>, קוד ריד-סלומון מסוגל לתקן כמות שגיאות מקסימלית לקוד עם פרמטרים <math>n</math> ו-<math>k</math>.}}
שורה 29:
==== שידור מידע ====
אפליקציה משמעותית נוספת של הקוד היא עבור שידור מידע ב[[תקשורת קווית]] או [[תקשורת אלחוטית|אלחוטית]]. אחת האפליקציות המפורסמות של קוד זה הייתה עבור המשדר של ה[[גשושית]] [[וויאג'ר 2|וויאג'ר]], בעת מסעה אל [[אורנוס]] ו[[נפטון]].{{
== הגדרה ==
שורה 55:
להסתכל על הפולינום שמספרים אלו הם מקדמיו,
<math>\ f(x)=a_0 +a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1} = \sum_{i=0}^{k-1} a_ix^i</math>
{{
ולשדר את ערכי הפולינום עבור <math>\ n>k</math> אינדקסים ידועים מראש.
בעוד שעד כה התייחסנו אל המספרים
<math>\ a_i, f(x)</math>
כאל מספרים כלשהם, הרי ששידור "מספר כלשהו" מצריך שידור כמות לא חסומה של [[מידע]]. פתרון לבעיה זו מתקבל על ידי שימוש בקבוצה סופית של מספרים שמהווה [[שדה סופי]]{{
אבר בשדה זה נקרא לרוב '''סימבול''' ומהווה את יחידת הבסיס של הקוד. על-מנת לשדר סימבול ניתן לקודד אותו ל[[סיבית|ביט]]ים או לעשות שימוש ב[[אפנון|שיטת אפנון]] מתקדמת בה כל סימבול (של הקוד) מזוהה עם סימבול של האפנון. כיוון שקיימים <math>\ n</math>
סימבולים אפשריים בשדה הסופי, ניתן לקודד כל סימבול על ידי <math>\log_2 n</math> ביטים.
שורה 98:
=== פענוח בשיטה נאיבית ===
הדרך הפשוטה (מבחינה רעיונית) לפענח מילת קוד, היא לבצע [[אינטרפולציה]] של כל הפולינומים המוגדרים על ידי <math>k</math> נקודות מתוך <math>n</math> הנקודות שמכילה מילת הקוד. כפי שמוצג בדוגמה לעיל בה שוחזר קו מתוך 4 נקודות בהן נפלה שגיאה יחידה, 3 אינטרפולציות הזדהו עם הקו הנכון, וכל אינטרפולציה אחרת הייתה שונה. באופן כללי ייתכן שמספר אינטרפולציות שגויות יתלכדו זו עם זו; עדיין, אם כל אינטרפולציה כזו תעניק "קול" אחד לטובת הפולינום שהיא מגדירה - הפולינום הנכון יזכה במרב הקולות, וכל שאר הפולינומים השגויים יזכו במספר קולות קטן (אבל ייתכן שגדול מ-1). הבעיה בשיטת פענוח זו, היא שיש לבצע אינטרפולציה עבור כל אחת מתוך <math>{n \choose k}</math> האפשרויות השונות, וזהו מספר גדול{{
<math>\ O(n^t)</math>. לכן, עבור התמודדות עם קצב שגיאות קבוע (למשל - עשירית מהמידע המועבר הוא שגוי), נדרש <math>\ t=\Omega(n)</math> והסיבוכיות המתקבלת [[אקספוננט|אקספוננציאלית]]
ב-<math>\ n</math>.}} של חישובים שאינו נחשב [[חישוב יעיל|יעיל]]. לדוגמה, בקוד RS(28,24){{D}} אשר משמש תקליטורים, פענוח מילה יחידה (192 ביט של מידע{{
=== פענוח לפי סינדרום (ברלקמפ-וולש) ===
שורה 112:
עקרון המפתח הוא שקיים פולינום ממעלה <math>\ k-1+t</math> לכל היותר, שנסמנו <math>\ V(x)</math> ומתקיים:
<div style="text-align: center;"><math> V(i)=r_i\cdot E(i) </math></div>
למשל, אם <math>\ V(x)=f(x)E(x)</math>, אזי <math>\ V(x)</math> הוא ממעלה <math>\ k-1+t</math> לכל היותר, והמשוואה לעיל מתקיימת לכל אינדקס <math>i \in \mathbb F_n</math>{{
מ-<math>\ k-1</math>.}}
שורה 151:
==ביאורים==
{{
==ראו גם==
|