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

תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות)
מ בוט החלפות: \1
אין תקציר עריכה
שורה 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</math>, מקיים תמיד
<math>d\le n-k+1</math>. קוד ריד-סלומון מקיים את השוויון. מכיוון שבקוד כלשהו ניתן לתקן לכל היותר <math>d/2</math>, קוד ריד-סלומון מסוגל לתקן כמות שגיאות מקסימלית לקוד עם פרמטרים <math>n</math> ו-<math>k</math>.}}
 
שורה 29:
 
==== שידור מידע ====
אפליקציה משמעותית נוספת של הקוד היא עבור שידור מידע ב[[תקשורת קווית]] או [[תקשורת אלחוטית|אלחוטית]]. אחת האפליקציות המפורסמות של קוד זה הייתה עבור המשדר של ה[[גשושית]] [[וויאג'ר 2|וויאג'ר]], בעת מסעה אל [[אורנוס]] ו[[נפטון]].{{הערה|קבוצה=ביאורים|בתחילת מסעה שידרה הגשושית תמונות ללא [[דחיסת מידע|דחיסה]] ועל כן עשתה שימוש בקוד תיקון שגיאות "פשוט". עם התרחקות הגשושית והגעתה לאורנוס ונפטון, בוצעה דחיסה של חלק מה[[קובץ תמונה|תמונות הדיגיטליות]] ועל-כן נדרש לבצע תיקון שגיאות חזק יותר, שבוצע על ידי קוד ריד-סולומון.{{הערה|שם=LTR-ויקר}}}} גם במקרה זה הקוד בנוי משתי שכבות, כאשר השכבה הנוספת היא [[קוד קונבולוציה]] כגון [[קוד טורבו]] או [[קוד ויטרבי]], אשר בעת שגיאה בתהליך הפענוח נוטים לייצר פרצי שגיאות, עמם קוד ריד-סולומון מתמודד בצורה טובה. בשיטה זו נעשה שימוש נרחב במשדרים לחלל העמוק, לרבות עבור [[גלילאו (גשושית)|גלילאו]] וגשושי משימות [[מאדים#מחקר רובוטי|חקר מאדים]], והפך לתקן המוסכם על ידי [[הוועדה המייעצת למערכות מידע בחלל]] (CCSDS).{{הערה|[http://public.ccsds.org/default.aspx אתר CCSDS].}}
 
== הגדרה ==
שורה 54:
<math>\ a_0,a_1,\ldots,a_{k-1}</math>,
להסתכל על הפולינום שמספרים אלו הם מקדמיו,
<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>k-1</math> לכל היותר.}}
ולשדר את ערכי הפולינום עבור <math>\ n>k</math> אינדקסים ידועים מראש.
 
בעוד שעד כה התייחסנו אל המספרים
<math>\ a_i, f(x)</math>
כאל מספרים כלשהם, הרי ששידור "מספר כלשהו" מצריך שידור כמות לא חסומה של [[מידע]]. פתרון לבעיה זו מתקבל על ידי שימוש בקבוצה סופית של מספרים שמהווה [[שדה סופי]]{{הערה|קבוצה=ביאורים|אנו זקוקים לקבוצה סופית של מספרים אשר ניתן לבצע בה פעולות חשבון בסיסיות כגון חיבור כפל וחילוק (על מנת לחשב את הפולינום), ועדיין הערך של כל פעולה כזו יהיה אחד האברים בקבוצה. זו בדיוק התכונה המתמטית של שדה סופי.}} בגודל n אברים, אשר יסומן <math>\ {\mathbb F}_n</math>.
אבר בשדה זה נקרא לרוב '''סימבול''' ומהווה את יחידת הבסיס של הקוד. על-מנת לשדר סימבול ניתן לקודד אותו ל[[ביט]]ים או לעשות שימוש ב[[אפנון|שיטת אפנון]] מתקדמת בה כל סימבול (של הקוד) מזוהה עם סימבול של האפנון. כיוון שקיימים <math>\ n</math>
סימבולים אפשריים בשדה הסופי, ניתן לקודד כל סימבול על ידי <math>\log_2 n</math> ביטים.
שורה 97 ⟵ 98:
 
=== פענוח בשיטה נאיבית ===
הדרך הפשוטה (מבחינה רעיונית) לפענח מילת קוד, היא לבצע [[אינטרפולציה]] של כל הפולינומים המוגדרים על ידי <math>k</math> נקודות מתוך <math>n</math> הנקודות שמכילה מילת הקוד. כפי שמוצג בדוגמה לעיל בה שוחזר קו מתוך 4 נקודות בהן נפלה שגיאה יחידה, 3 אינטרפולציות הזדהו עם הקו הנכון, וכל אינטרפולציה אחרת הייתה שונה. באופן כללי ייתכן שמספר אינטרפולציות שגויות יתלכדו זו עם זו; עדיין, אם כל אינטרפולציה כזו תעניק "קול" אחד לטובת הפולינום שהיא מגדירה - הפולינום הנכון יזכה במרב הקולות, וכל שאר הפולינומים השגויים יזכו במספר קולות קטן (אבל ייתכן שגדול מ-1). הבעיה בשיטת פענוח זו, היא שיש לבצע אינטרפולציה עבור כל אחת מתוך <math>{n \choose k}</math> האפשרויות השונות, וזהו מספר גדול{{הערה|קבוצה=ביאורים|עבור קוד המסוגל לתקן <math>\ t</math> שגיאות הסיבוכיות המתקבלת היא
<math>\ O(n^t)</math>. לכן, עבור התמודדות עם קצב שגיאות קבוע (למשל - עשירית מהמידע המועבר הוא שגוי), נדרש <math>\ t=\Omega(n)</math> והסיבוכיות המתקבלת [[אקספוננט|אקספוננציאלית]]
ב-<math>\ n</math>.}} של חישובים שאינו נחשב [[חישוב יעיל|יעיל]]. לדוגמה, בקוד RS(28,24){{D}} אשר משמש תקליטורים, פענוח מילה יחידה (192 ביט של מידע{{הערה|קבוצה=ביאורים|הקוד בו נעשה שימוש הוא למעשה קוד ריד-סולומון מוכלל מעל השדה הסופי <math>\ GF(2^8)</math> המכיל 256 אברים. אורך כל סימבול 8 ביט, ועל כן אורך מילת המקור <math>24\times 8=192</math> סיביות.}}) מצריך ביצוע כ-20 אלף אינטרפולציות (בעוד הזמן המוקצה לכך בתקליטור הוא כ-0.000136 שניות). באופן דומה, פענוח מילת קוד יחידה בקוד RS(208,192){{D}} בו נעשה שימוש ב-DVD, מצריך ביצוע כ-<math>10^{20}</math> אינטרפולציות - פעולה אשר תימשך מספר רב של ימים בטכנולוגיה בת ימינו.
 
=== פענוח לפי סינדרום (ברלקמפ-וולש) ===
שורה 111 ⟵ 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>i \in [0,n-1]</math> לבין אבר מתאים בשדה הסופי. ניתן לעשות זאת על ידי התאמת האבר <math>\alpha^i</math> לאינדקס <math>i\in [1, n-1]</math>, כאשר <math>\alpha</math> הוא [[שורש פרימיטיבי]] של השדה (האבר <math>0\in \mathbf F_n</math> מותאם ל-<math>i=0</math>).}}. לכן אם ידועים הפולינומים <math>\ V(x), E(x)</math> ניתן לפענח את המילה המקורית על ידי ביצוע חלוקה: <math>\ f(x) = V(x)/E(x)</math>. לא ייתכן שקיים פולינום אחר (ממעלה <math>\ k-1</math> לכל היותר) אשר שווה לתוצאת החלוקה, ולכן שיטה זו תשחזר את הפולינום הנכון.{{הערה|קבוצה=ביאורים|הסיבה היא שכל פולינום שמתקבל מחלוקה זו מזדהה עם <math>\ f(x)</math> בכל הנקודות בהן לא קרתה שגיאה. קיימות יותר מ-<math>\ k</math> נקודות כנ"ל, ולכן הפולינום חייב להיות שווה ל-<math>\ f(x)</math> או בעל מעלה גדולה
מ-<math>\ k-1</math>.}}
 
שורה 157 ⟵ 158:
* [http://www.ll.mit.edu מעבדת לינקולן ב-MIT] {{אנגלית}}
* [http://sourceforge.jp/projects/reedsolomon/ מקודד ומפענח ריד-סולומון] ב[[Java|שפת Java]] ([[קוד פתוח]]), אתר sourceforge {{אנגלית}}
 
==ביאורים==
{{הערות שוליים|קבוצה=ביאורים}}
 
==הערות שוליים==