קוד ריד-סולומון – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שחזור הערות שוליים |
מ LTR להערות שוליים |
||
שורה 1:
'''קוד ריד-סולומון''' (ב[[אנגלית]]: '''Reed-Solomon Code''') הוא [[קוד תיקון שגיאות]] [[קוד לינארי|לינארי]] נפוץ ושימושי ביותר,{{הערה|שם=LTR-ויקר|Stephan Wicker and Vijay Bhargava (eds.), '''Reed-Solomon Codes and their Applications''', IEEE Press, 1994.{{D}}}}
המבוסס על [[אינטרפולציה|אינטרפולציה באמצעות פולינומים]] מעל [[שדה סופי|שדות סופיים]].
הקוד מיועד להעברה אמינה של מידע ב[[ערוץ תקשורת]] רועש (כדוגמת [[טלפון סלולרי]]), שבמידע המועבר בו עלולות להיווצר שגיאות, או לשמירת מידע ב[[אמצעי לאחסון נתונים|מדיה]] שעלולה להיפגם ([[DVD]], למשל), ולכן להכיל שגיאות.
שורה 6:
[[קובץ:ReedSolomon.jpg|שמאל|ממוזער|250px|גוסטב סולומון (מימין) ואירווינג ריד]]
קוד ריד-סולומון פותחו על ידי צוות החוקרים [[אירווינג ריד]] ו[[גוסטב סולומון]] ממעבדת לינקולן (MIT Lincoln Laboratory) - מעבדת המחקר של [[מחלקת ההגנה של ארצות הברית]] ב-[[MIT]].
במאמרם משנת 1960 הציגו ריד וסולומון שיטה יעילה ופשוטה לקידוד מידע, וניתחו את כמות השגיאות שניתן לתקן בעזרת קוד זה.{{הערה|שם=LTR-rs60|I. Reed and G. Solomon, "Polynomial Codes Over Certain Finite Fields", '''Journal of the Society for Industrial and Applied Mathematics''', 8:300-304, 1960.{{D}}}} מסתבר שהקוד הוצג לראשונה בשנת 1952, כחלק ממחקר בנושא [[ריבוע לטיני|ריבועים לטיניים]],{{הערה|שם=LTR-bush|K.A. Bush, "Orthogonal Arrays of Index Unity", '''Ann. Math. Stat''', (23) 426-434, 1952.{{D}}}} אך ריד וסולומון היו הראשונים להכיר בתכונותיו לתיקון שגיאות.
השימוש בקוד לתיקון שגיאות דורש הפעלת שני [[אלגוריתם|אלגוריתמים]], ל[[מקודד|קידוד]] ול[[פענוח]]. תפקידו של אלגוריתם הקידוד לקחת מילה מסוימת (מילת המקור) ולקודד אותה למילה אחרת, ארוכה יותר, המכילה [[יתירות]] (מילת הקוד).
שורה 29:
==== שידור מידע ====
אפליקציה משמעותית נוספת של הקוד היא עבור שידור מידע ב[[תקשורת קווית]] או [[תקשורת אלחוטית|אלחוטית]]. אחת האפליקציות המפורסמות של קוד זה הייתה עבור המשדר של ה[[גשושית]] [[וויאג'ר]], בעת מסעה אל [[אורנוס]] ו[[נפטון]].{{הערה|בתחילת מסעה שידרה הגשושית תמונות ללא [[דחיסת מידע|דחיסה]] ועל כן עשתה שימוש בקוד תיקון שגיאות "פשוט". עם התרחקות הגשושית והגעתה לאורנוס ונפטון, בוצעה דחיסה של חלק מה[[קובץ תמונה|תמונות הדיגיטליות]] ועל-כן נדרש לבצע תיקון שגיאות חזק יותר, שבוצע על ידי קוד ריד-סולומון.{{הערה|שם=LTR-ויקר}}}} גם במקרה זה הקוד בנוי משתי שכבות, כאשר השכבה הנוספת היא [[קוד קונבולוציה]] כגון [[קוד טורבו]] או [[קוד ויטרבי]], אשר בעת שגיאה בתהליך הפענוח נוטים לייצר פרצי שגיאות, עמם קוד ריד-סולומון מתמודד בצורה טובה. בשיטה זו נעשה שימוש נרחב במשדרים לחלל העמוק, לרבות עבור [[גלילאו (גשושית)|גלילאו]] וגשושי משימות [[מאדים#מחקר רובוטי|חקר מאדים]], והפך לתקן המוסכם על ידי [[הוועדה המייעצת למערכות מידע בחלל]] (CCSDS).{{הערה|[http://public.ccsds.org/default.aspx אתר CCSDS].}}
== הגדרה ==
שורה 92:
=== היסטוריה ===
בעוד קידוד מילה בשיטת ריד-סולומון הוא משימה פשוטה וקלה, פענוח הוא משימה מסובכת הצורכת משאבים רבים. פריצת הדרך בגילוי שיטה יעילה לפענוח התרחשה בשנת 1967, על ידי ה[[מתמטיקאי]] [[אלווין ברלקמפ]] (Berlekamp) שהציג אלגוריתם לפענוח [[קוד BCH]] מתוך ההבנה שקוד ריד-סולומון הוא מקרה פרטי של קוד BCH.{{הערה|שם=LTR-ויקר}}
העקרונות המתמטיים של פענוח (עבור קוד BCH) הוצגו לראשונה בשנת 1960 במאמר של פטרסון (Peterson), אשר הציג שיטה לפענוח קוד BCH ב[[סיבוכיות]] של <math>\ O(n^3)</math>. בשנת 1968 הציע [[ג'יימס מסי]] (Messy) דרך למימוש מפענח המבוסס על [[אוגר הזזה|אוגרי הזזה]] בסיבוכיות של <math>\ O(n^2)</math>. בשנת 1975 הציגה קבוצה של מדענים מ[[יפן]] שיטה לפענוח הקוד המבוססת על [[אלגוריתם אוקלידס]] בעלת סיבוכיות דומה.{{
בשנת 1995 הציגו הונג ווטרלי שיטה לביצוע הפענוח בסיבוכיות <math>\ O(n\log n)</math>.{{הערה|שם=LTR-hv95|Jonathan Hong, Martin Vetterli, "Simple Algorithms for BCH Decoding", '''IEEE Transactions on Communications''' 43 (8): 2324–2333, August 1995.{{D}}}}{{הערה|[http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect27.pdf סיכום שיעור בנושא אלגוריתם ברלקמפ-וולש]{{PDF}}.}}
=== פענוח בשיטה נאיבית ===
| |||