קוד ריד-סולומון – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט החלפות: \1איברים |
|||
שורה 60:
בעוד שעד כה התייחסנו אל המספרים
<math>\ a_i, f(x)</math>
כאל מספרים כלשהם, הרי ששידור "מספר כלשהו" מצריך שידור כמות לא חסומה של [[מידע]]. פתרון לבעיה זו מתקבל על ידי שימוש בקבוצה סופית של מספרים שמהווה [[שדה סופי]]{{ביאור|אנו זקוקים לקבוצה סופית של מספרים אשר ניתן לבצע בה פעולות חשבון בסיסיות כגון חיבור כפל וחילוק (על מנת לחשב את הפולינום), ועדיין הערך של כל פעולה כזו יהיה אחד
אבר בשדה זה נקרא לרוב '''סימבול''' ומהווה את יחידת הבסיס של הקוד. על-מנת לשדר סימבול ניתן לקודד אותו ל[[סיבית|ביט]]ים או לעשות שימוש ב[[אפנון|שיטת אפנון]] מתקדמת בה כל סימבול (של הקוד) מזוהה עם סימבול של האפנון. כיוון שקיימים <math>\ n</math>
סימבולים אפשריים בשדה הסופי, ניתן לקודד כל סימבול על ידי <math>\log_2 n</math> ביטים.
שורה 79:
===קוד ריד-סולומון במובן מודרני===
במקום לחשוב על המילה אותה אנו מקודדים, <math>a_0,a_1,\ldots,a_{k-1}</math>, בתור '''מקדמים''' של פולינום, אנחנו יכולים לחשוב עליה כעל '''ערכים''' של פולינום ב-<math>k</math> מקומות ידועים. ערכים אלו מגדירים פולינום (ממעלה לכל היותר <math>\ k-1</math>) בצורה חד-חד ערכית בהתאם לאינטרפולציה. אם המקומות הידועים הם <math>k</math>
הגדרה זו מראה כי קוד ריד-סולומון הוא מקרה פרטי של משפחת קודים רחבה יותר בשם [[קוד BCH|קודי BCH]]. קוד BCH הוא [[קוד ציקלי]] עבורו קיים פולינום <math>\ g(x)</math> בעל תכונות מסוימות הנקרא '''יוצר''' של הקוד, וכל מילת קוד היא מכפלה של הפולינום היוצר בפולינום המוגדר על ידי מילת המקור.
שורה 99:
הדרך הפשוטה (מבחינה רעיונית) לפענח מילת קוד, היא לבצע [[אינטרפולציה]] של כל הפולינומים המוגדרים על ידי <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
=== פענוח לפי סינדרום (ברלקמפ-וולש) ===
שורה 105:
נניח כי בעוד שנשלחה מילת הקוד <math>\ s_0, s_1, \ldots, s_{n-1}</math> המתאימה לפולינום
<math>\ f(x)</math> המוגדר לעיל, בצד הקולט התקבלה המילה <math>\ r_0, r_1, \ldots, r_{n-1}</math> אשר נפלו בה <math>\ t=(n-k)/2</math> שגיאות לכל היותר, כלומר, עבור <math>\ t</math> אינדקסים לכל היותר <math>\ r_i \ne s_i</math>. כזכור, כלל הערכים הם
ניתן להגדיר '''פולינום שגיאה''' אשר יסומן <math>\ E(x)</math>. התכונות של פולינום השגיאה הן שבכל אינדקס <math>\ i</math> בו קרתה שגיאה, הפולינום יקבל את הערך 0, מעלתו תהיה <math>\ t</math>, והוא נדרש להיות [[פולינום מתוקן]]. הצד המקבל לא יודע לבנות את פולינום השגיאה (כי אינו יודע את האינדקסים שבהן קרו שגיאות), אבל ידוע שפולינום כנ"ל קיים.
| |||