קוד ריד-סולומון פותחו על ידי צוות החוקרים אירווינג ריד וגוסטב סולומון ממעבדת לינקולן (MIT Lincoln Laboratory) - מעבדת המחקר של מחלקת ההגנה של ארצות הברית ב-MIT.
במאמרם משנת 1960 הציגו ריד וסולומון שיטה יעילה ופשוטה לקידוד מידע, וניתחו את כמות השגיאות שניתן לתקן בעזרת קוד זה.[2] הקוד הוצג לראשונה בשנת 1952, כחלק ממחקר בנושא ריבועים לטיניים,[3] אך ריד וסולומון היו הראשונים להכיר בתכונותיו לתיקון שגיאות.
השימוש בקוד לתיקון שגיאות דורש הפעלת שני אלגוריתמים, לקידוד ולפענוח. תפקידו של אלגוריתם הקידוד לקחת מילה מסוימת (מילת המקור) ולקודד אותה למילה אחרת, ארוכה יותר, המכילה יתירות (מילת הקוד).
אלגוריתם הפענוח מקבל כקלט את המילה הארוכה, ייתכן בתוספת שיבושים שונים שנוספו לה עקב השידור בערוץ הרועש. אלגוריתם הפענוח מנסה לשחזר את מילת המקור מתוך הקלט, כאשר היתירות שהוספה בתהליך הקידוד משמשת אותו להתמודדות עם השגיאות שקרו. תהליך הפענוח מורכב מאשר תהליך הקידוד. ריד וסולומון לא הציגו שיטת פענוח יעילה, וזו הומצאה בשנת 1967.
קוד ריד-סולומון המקוׂדֵד מחרוזת המכילה k אותיות (אות כנ"ל נקראת גם סימבול, ואורכה יכול להשתנות, ראו בהמשך) ל-n אותיות מסומן ב-RS(n,k), ומסוגל לתקן עד שגיאות (כלומר הוא קוד ליניארי בעל הפרמטרים ); הקוד מתקן שגיאות במידה המקסימלית האפשרית לקוד בעל הפרמטרים ו-.[א]
שימושים והרחבות
פיתוח שיטת קידוד יעילה וכן התפתחות תקשורת הנתונים הובילו לשימוש נרחב בקודי-תיקון שגיאות ובראשם בקודי ריד-סולומון. בימינו ניתן למצוא מערכות אלקטרוניות רבות אשר עושות שימוש בקודי ריד-סולומון, דוגמת מכשירי רדיו (הן קוויים, דוגמת ערוצי DSL, והן אלחוטיים דוגמת WiMAX), תקליטורים ו־DVD, ומקודדי-וידאו. שימושים נוספים של הקוד הם לשיפור מערכות פיזור ספקטרום של מערכות תקשורת אלחוטיות, וכן בהתמודדות עם שגיאות חד-כיווניות, מהסוג הנפוץ באפיקי נתונים מהירים של מחשבים.
תוכנית וויאג'ר התאפיינה במאזן ערוץ הנמוך ביותר בערוצי תקשורת. בעקבות כך במהלך התוכנית לחללית וויאג'ר 2 היה צורך בהחלפת תוכנת תקשורת שהוחלפה במתקדמת יותר שמנצלת קוד ריד-סולומון כפול.
שמירת מידע
קיים שימוש נרחב בקוד ריד-סולומון להתקנים שונים לשמירת מידע. במדיות רבות (בעיקר מדיות אופטיות) ההתקן עצמו גורם לשגיאות במידע השמור (למשל, עקב שריטות או פגמים אחרים[4]) ובשל כך נדרשת יתירות במידע עצמו השמור על-גבי המדיה.
תכונות השגיאות במדיות אלו הופכות את קוד ריד-סולומון לפתרון יעיל. לרוב השגיאות הנובעות מ"פגם" אינן מפוזרות אלא מקובצות יחדיו, ומתקבל רצף (burst) של שגיאות עמו הקוד מסוגל להתמודד היטב.
תקן שמירת המידע בתקליטורים (CD) מגדיר שימוש בשתי שכבות של קוד ריד-סולומון, שיטה המכונה CIRC.[5] השכבה הראשונה היא בעלת הפרמטרים RS(28,24), לאחר מכן מתבצעת שזירה של המידע (פיזור הביטים כך שביטים עוקבים מורחקים אחד מהשני, interleaving), והפעלת קוד RS(32,28) על המידע השזור.
השכבה הראשונה מתמודדת עם פגמים בייצור התקליטור ובדרך שבה הוא נצרב (פגמי "מיקרו"). השכבה השנייה מיועדת להתמודד עם הפרעות כגון שריטות או טביעות אצבע, בעלות שטח הפרעה גדול יותר (פגמי "מאקרו").
שימוש נוסף לקוד ריד-סולומון עבור שמירת מידע ניתן למצוא בברקודים מודרניים (דו-ממדיים). קריאת ברקודים אלו מבוצעת על ידי צילום הברקוד וזיהוי פסים או ריבועים שחורים ולבנים. זווית הצילום, המרחק, כמות האור וכן תקינות מדבקת הברקוד עצמה הם גורמים בעלי השפעה רבה על איכות הזיהוי של המידע בברקוד. מתוך הנחה שחלק מהריבועים לא יזוהו נכון, מקודד המידע באמצעות קוד ריד-סולומון ומפעונח במהירות וביעילות בצד הקורא האופטי. תקני ברקוד הכוללים קידוד ריד-סולומון הם PDF-417 ,PostBar ,MaxiCode ,Datamatrix ,קוד QR ,Aztec Code, ועוד.
שידור מידע
אפליקציה משמעותית נוספת של הקוד היא עבור שידור מידע בתקשורת קווית או אלחוטית. אחת האפליקציות המפורסמות של קוד זה הייתה עבור המשדר של הגשושיתוויאג'ר, בעת מסעה אל אורנוס ונפטון.[ב] גם במקרה זה הקוד בנוי משתי שכבות, כאשר השכבה הנוספת היא קוד קונבולוציה כגון קוד טורבו או קוד ויטרבי, אשר בעת שגיאה בתהליך הפענוח נוטים לייצר פרצי שגיאות, עמם קוד ריד-סולומון מתמודד בצורה טובה. בשיטה זו נעשה שימוש נרחב במשדרים לחלל העמוק, לרבות עבור גלילאו וגשושי משימות חקר מאדים, והפך לתקן המוסכם על ידי הוועדה המייעצת למערכות מידע בחלל (CCSDS).[6]
הרעיון המתמטי העומד מאחורי הקוד פשוט יחסית, ומבוסס על רעיון האינטרפולציה:
על מנת להגדיר את הפולינום בצורה חד-חד ערכית, כאשר ידוע שהפולינום הוא ממעלה לכל היותר, נדרשות נקודות בלבד בהן הערך של הפולינום ידוע.
לדוגמה, פולינום ממעלה 1 לכל היותר, הוא קו ישר מהצורה .
כלל ידוע הוא שמספיקות שתי נקודות על מנת להגדיר קו (קיימים 2 נעלמים, ועל-כן 2 נקודות מספיקות על מנת להגדיר את הערכים בצורה חד-ערכית). עיקרון זה מתקיים גם כאשר המעלה של הפולינום גבוהה יותר.
נניח כי המטרה היא להעביר בערוץ תקשורת רועש את שני המספרים .
כאשר משדרים את המספרים ישירות, ייתכן שאחד מהם "יתקלקל" עקב הרעש והמידע יגיע באופן שגוי. גם במקרה בו כל מספר יישלח פעמיים – במידה שאחד העותקים יתקלקל, לא ניתן יהיה להבחין מי מבין העותקים הוא הנכון ומי השגוי.
שיטה אחרת היא להגדיר את הקו ולשלוח בערוץ התקשורת את ערך הפולינום ב-4 מקומות ידועים מראש (למשל, ב-). הצד המקבל יוכל לבצע אינטרפולציה של הקו מתוך נקודות אלו ולזהות מהו הקו (הפולינום) שנשלח אליו.
גם אם נפלה טעות יחידה באחת מתוך ארבע הנקודות שנשלחו, הצד המקבל יכול לדעת מהו הקו הנכון על-פי 3 הנקודות האחרות: כל זוג נקודות מגדיר קו אחד, ולכן ארבעת הערכים שנשלחו מגדירים שישה קווים אפשרים. אם כל הערכים התקבלו באופן תקין – כל ששת הקווים יהיו זהים. לעומת זאת, אם נפלה טעות יחידה, 3 קווים יתלכדו עם הקו המקורי, בעוד שאר הקווים יהיו קווים שונים (ראו הדגמה בתמונה). כך ניתן לזהות איזו נקודה סטתה מהקו המקורי ולשחזר בהצלחה את הקו המקורי.
ככל שנשדר את ערכי הפולינום עבור יותר ויותר ערכי , היתירות תגדל, וניתן יהיה להתמודד עם מספר רב יותר של שגיאות.
קוד ריד-סולומון במובן הקלאסי
כאמור לעיל, המטרה היא לקחת מספרים כלשהם, שיסומנו
,
להסתכל על הפולינום שמספרים אלו הם מקדמיו,
[ג]
ולשדר את ערכי הפולינום עבור אינדקסים ידועים מראש.
בעוד שעד כה התייחסנו אל המספרים
כאל מספרים כלשהם, הרי ששידור "מספר כלשהו" מצריך שידור כמות לא חסומה של מידע. פתרון לבעיה זו מתקבל על ידי שימוש בקבוצה סופית של מספרים שמהווה שדה סופי[ד] בגודל n איברים, אשר יסומן .
איבר בשדה זה נקרא לרוב סימבול ומהווה את יחידת הבסיס של הקוד. על-מנת לשדר סימבול ניתן לקודד אותו לביטים או לעשות שימוש בשיטת אפנון מתקדמת שבה כל סימבול (של הקוד) מזוהה עם סימבול של האפנון. כיוון שקיימים
סימבולים אפשריים בשדה הסופי, ניתן לקודד כל סימבול על ידי ביטים.
באופן פורמלי:
קידוד ריד-סולומון מאורך
ומממד
מעל השדה הסופי
הוא המיפוי
כאשר ,
ו
הם כלל אברי השדה הסופי (כלל הסימבולים אפשריים). קוד ריד-סולומון הוא אוסף כלל המילים אשר ממופות על ידי המיפוי לעיל, עבור כל מילות המקור האפשריות, .
קוד ריד-סולומון במובן מודרני
במקום לחשוב על המילה אותה אנו מקודדים, , בתור מקדמים של פולינום, אנחנו יכולים לחשוב עליה כעל ערכים של פולינום ב- מקומות ידועים. ערכים אלו מגדירים פולינום (ממעלה לכל היותר ) בצורה חד-חד ערכית בהתאם לאינטרפולציה. אם המקומות הידועים הם האיברים הראשונים של , תחילית מילת הקוד תהא מילת המקור (כלומר, מתקבל קוד סיסטמטי).
הגדרה זו מראה כי קוד ריד-סולומון הוא מקרה פרטי של משפחת קודים רחבה יותר בשם קודי BCH. קוד BCH הוא קוד ציקלי עבורו קיים פולינום בעל תכונות מסוימות הנקרא יוצר של הקוד, וכל מילת קוד היא מכפלה של הפולינום היוצר בפולינום המוגדר על ידי מילת המקור.
בצורה זו, קוד ריד-סולומון מוגדר על ידי היוצר
כאשר הוא שורש פרימיטיבי של השדה הסופי: ולכל , . עבור מילת המקור המגדירה את הפולינום המילה המקודדת היא מקדמי הפולינום . משיקולי מעלות, הפולינום הוא ממעלה
לכל היותר, ועל כן יש לשדר סימבולים.
ניתן להראות כי הגדרה זו שקולה להגדרה המקורית של הקוד שהוצגה במאמרם של ריד וסולומון.
פענוח קוד ריד-סולומון
היסטוריה
בעוד קידוד מילה בשיטת ריד-סולומון הוא משימה פשוטה וקלה, פענוח הוא משימה מסובכת הצורכת משאבים רבים. פריצת הדרך בגילוי שיטה יעילה לפענוח התרחשה בשנת 1967, על ידי המתמטיקאיאלווין ברלקמפ (Berlekamp) שהציג אלגוריתם לפענוח קוד BCH מתוך ההבנה שקוד ריד-סולומון הוא מקרה פרטי של קוד BCH.[1]
העקרונות המתמטיים של פענוח (עבור קוד BCH) הוצגו לראשונה בשנת 1960 במאמר של פטרסון (Peterson), אשר הציג שיטה לפענוח קוד BCH בסיבוכיות של . בשנת 1968 הציע ג'יימס מסי (Massey) דרך למימוש מפענח המבוסס על אוגרי הזזה בסיבוכיות של . בשנת 1975 הציגה קבוצה של מדענים מיפן שיטה לפענוח הקוד המבוססת על אלגוריתם אוקלידס בעלת סיבוכיות דומה.[7]
בשנת 1995 הציגו הונג ווטרלי שיטה לביצוע הפענוח בסיבוכיות .[8][9]
פענוח בשיטה נאיבית
הדרך הפשוטה (מבחינה רעיונית) לפענח מילת קוד, היא לבצע אינטרפולציה של כל הפולינומים המוגדרים על ידי נקודות מתוך הנקודות שמכילה מילת הקוד. כפי שמוצג בדוגמה לעיל בה שוחזר קו מתוך 4 נקודות בהן נפלה שגיאה יחידה, 3 אינטרפולציות הזדהו עם הקו הנכון, וכל אינטרפולציה אחרת הייתה שונה. באופן כללי ייתכן שמספר אינטרפולציות שגויות יתלכדו זו עם זו; עדיין, אם כל אינטרפולציה כזו תעניק "קול" אחד לטובת הפולינום שהיא מגדירה - הפולינום הנכון יזכה במרב הקולות, וכל שאר הפולינומים השגויים יזכו במספר קולות קטן (אבל ייתכן שגדול מ-1). הבעיה בשיטת פענוח זו, היא שיש לבצע אינטרפולציה עבור כל אחת מתוך האפשרויות השונות, וזהו מספר גדול[ה] של חישובים שאינו נחשב יעיל. לדוגמה, בקוד RS(28,24) אשר משמש תקליטורים, פענוח מילה יחידה (192 ביט של מידע[ו]) מצריך ביצוע כ-20 אלף אינטרפולציות (בעוד הזמן המוקצה לכך בתקליטור הוא כ-0.000136 שניות). באופן דומה, פענוח מילת קוד יחידה בקוד RS(208,192) בו נעשה שימוש ב-DVD, מצריך ביצוע כ- אינטרפולציות - פעולה אשר תימשך מספר רב של ימים בטכנולוגיה בת ימינו.
פענוח לפי סינדרום (ברלקמפ-וולש)
השיטה המודרנית לפענוח קודי ריד סולומון מבוססת על הסתכלות על הקוד כמקרה פרטי של קודי BCH, לפי אלגוריתם שפותח על ידי ברלקמפ ושופר על ידי וולש (Welch) וידוע בתור אלגוריתם ברלקמפ-וולש. להלן תיאור עקרוני של שיטת הפענוח.
נניח כי בעוד שנשלחה מילת הקוד המתאימה לפולינום
המוגדר לעיל, בצד הקולט התקבלה המילה אשר נפלו בה שגיאות לכל היותר, כלומר, עבור אינדקסים לכל היותר . כזכור, כלל הערכים הם איברים בשדה הסופי .
ניתן להגדיר פולינום שגיאה אשר יסומן . התכונות של פולינום השגיאה הן שבכל אינדקס בו קרתה שגיאה, הפולינום יקבל את הערך 0, מעלתו תהיה , והוא נדרש להיות פולינום מתוקן. הצד המקבל לא יודע לבנות את פולינום השגיאה (כי אינו יודע את האינדקסים שבהן קרו שגיאות), אבל ידוע שפולינום כנ"ל קיים.
עקרון המפתח הוא שקיים פולינום ממעלה לכל היותר, שנסמנו ומתקיים:
למשל, אם , אזי הוא ממעלה לכל היותר, והמשוואה לעיל מתקיימת לכל אינדקס [ז]. לכן אם ידועים הפולינומים ניתן לפענח את המילה המקורית על ידי ביצוע חלוקה: . לא ייתכן שקיים פולינום אחר (ממעלה לכל היותר) אשר שווה לתוצאת החלוקה, ולכן שיטה זו תשחזר את הפולינום הנכון.[ח]
ניתן למצוא את הפולינומים בצורה יעילה: יהיו המקדמים של הפולינום , ויהיו המקדמים של . כזכור, הוא פולינום מתוקן, ועל-כן . אם מציבים ב- את כל אחד מאברי השדה, מתקבלת מערכת של משוואות ליניאריות עם נעלמים (מקדמי ). מכיוון שכמות השגיאות מוגבלת ב-
מספר הנעלמים הוא , והמערכת ניתנת לפתרון.
פענוח בערוץ מחיקה
בערוצי תקשורת מסוימים הנקראים ערוצי מחיקה, השגיאה מתבטאת בכך שהצד הקולט לא מקבל כל מידע. בערוץ זה, כאשר כן נקלט מידע הוא תמיד נקלט נכון, אך לעיתים לא מגיע מידע (אירוע זה מכונה "מחיקה"). דוגמה לערוץ כזה הוא ערוץ תקשורת אופטי בו תדר מסוים מסמל "0" ותדר אחר מסמל "1": לעיתים הפוטונים הנשלחים "נבלעים", או נחסמים בתווך שבין המשדר למקלט; אך אם הפוטון הגיע לצד השני ניתן לזהות בצורה וודאית מה היה תדר הפוטון שנשלח, ומה הביט שהוא מסמל.
שגיאות מסוג זה קלות מאוד לתיקון על ידי קוד ריד-סולומון. בהנחה שבקוד RS(n,k) חלו מחיקות לכל היותר, ניתן לעשות שימוש בשאר הערכים שנקלטו ולבצע אינטרפולציה לפולינום שנשלח. מכיוון שנקודות אלו הגיעו ללא שגיאה, האינטרפולציה תצליח תמיד. מכאן שתיקון מחיקות "קל" יותר מאשר תיקון שגיאות. שיטה לתיקון שגיאות היא רבת עוצמה יותר משיטה לתיקון מחיקות: ניתן להפוך מחיקה לשגיאה על ידי כך שנגריל ערך אקראי כלשהו במקום המחיקה. מן הסתם, ערך זה יהיה שגוי ויתפרש כ"שגיאה", אך כעת ניתן להפעיל את שיטת הפענוח להתמודדות עם שגיאות. מאידך, הקושי בהימצאותן של שגיאות (לעומת מחיקות) הוא שלא ידוע מיקומן של השגיאות, ואלגוריתם הפענוח נדרש להבדיל איזו נקודה היא השגויה ואיזו התקינה.
פענוח מחיקות ושגיאות בו זמנית
כאמור לעיל, קוד ריד-סולומון מסוגל להתמודד עם מחיקות או עם שגיאות כאשר . ניתן לשלב את שני אלו ולקבל כי קוד ריד-סולומון מסוגל להתמודד עם מחיקות וגם שגיאות, כל עוד .
יעילות הקוד במקרים פרטיים שונים
קוד RS(n,k) מסוגל לתקן עד סימבולים שגויים. במידה וכל סימבול מיוצג כרצף של ביטים באורך הקוד יכול להתמודד עם לכל הפחות ביטים שגויים (המפוזרים כל אחד בסימבול שונה), אך ייתכנו מצבים בהם הקוד מסוגל להתמודד עם עד
ביטים שגויים, המקובצים כולם ב- סימבולים שונים, לכל היותר. תכונה זו הופכת את הקוד לחזק במיוחד כאשר מדובר בערוץ בינארי בו פיזור השגיאות הוא ב"פרצים" צמודים. בנוסף, כאשר משתמשים במספר שכבות קוד תיקון-שגיאות (למשל, שתי שכבות קוד ריד-סולומון כפי שקיים בתקליטורים, או קוד קונבולוציה וקוד ריד-סולומון, כפי שמצוי בגשושית וויאג'ר), במידה והקוד הפנימי אינו מצליח לתקן את השגיאה, הוא מסמן זאת עבור הקוד החיצוני. כעת קוד ריד-סולומון בשכבה החיצונית יכול להתייחס לערך המסומן כאל "מחיקה" ולשפר את יכולת תיקון השגיאות.
הרחבות
קודי ריד-סולומון פתחו עידן רחב של מחקר בתחום תורת הקודים ויישומיה. לאורך השנים בוצעו מספר שיפורים והרחבות לקוד המקורי, על מנת לקבל קודי תיקון שגיאות המתאימים לאפליקציות שונות, לשפר את קצב הקוד ולהתקרב כמה שיותר אל קיבולת הערוץ (שהיא החסם על קצב הקוד המקסימלי, כפי שהוגדר על ידי קלוד שאנון במשפט הידוע בתור משפט קידוד המקור של שנון).
יש וריאנטים של קודי ריד-סולומון המבוססים על מטריצות קושי מעל שדה מתאים.
קודי ריד-סולומון מוכללים
משפחה יותר רחבה של קודי ריד-סולומון, מתקבלת כאשר מילת הקוד מוכפלת בפולינום קבוע שהוא פרמטר של הקוד. משפחה זו נקראת קודי ריד-סולומון מוכללים, ולכל המוגדרים מעל השדה הסופי בגודל לכל הפחות, הקוד מוגדר בתור אוסף המילים המתקבל על ידי הקידוד:
הפרמטר מאפשר להקטין את אורך הקוד על ידי דגימת הפולינום בחלק מאברי השדה הסופי (המוגדרים על ידי ) ולא בכלל השדה. ניתן לראות כי קוד ריד-סולומון שהוגדר לעיל הוא מקרה פרטי של הקוד המוכלל, כאשר הם כלל אברי השדה הסופי, ו-.
פענוח רשימה
עד כה, אלגוריתמי הפענוח ידעו להתמודד עם כמות שגיאות החסומה ב-. הערך מסמל את מרחק המינג המינימלי בין שתי מילות קוד ונקרא גם מרחק הקוד. אם כמות השגיאות שקרו קטנה ממחצית מרחק הקוד - קיימת רק מילת קוד אחת שיכולה להיות זו שנשלחה ושיטות הפענוח שתוארו לעיל מצליחות לגלותהּ. נשאלת השאלה מה ניתן לעשות כאשר קרו יותר שגיאות?
במקרה זה, לא ניתן לדעת בוודאות מהי המילה שנשלחה, אבל ניתן לקבל רשימה של מילות מקור אפשריות. כל עוד מספר השגיאות שקרו קטן ממרחק הקוד - רשימה זו תהיה "קטנה": פולינומית באורך הקוד. מצד שני, אם מספר השגיאות גדול ממרחק הקוד - הרשימה תהיה ענקית: אקספוננציאלית באורך הקוד. בשנת 1997 הציע מדו סודן שיטה לבצע פענוח רשימה לקודי ריד-סולומון, בסיבוכיות פולינומית, תוצאה ששופרה בשנת 1999 וידועה בשם גורוסוואמי-סודאן (Guruswami-Sudan) על שם ממציאיה. שיטה זו מאפשרת להתמודד עם שגיאות. אם מסמנים את קצב הקוד מתקבל כי השיטה מתמודדת עם אחוז שגיאות של (כאשר החסם המקסימלי (מרחק הקוד) מהווה אחוז שגיאות של ).
בשנת 2004 הציגו פרברש וורדי (Parvaresh, Vardi) קוד המבוסס על ריד-סולומון, בו כל סימבול מהווה ערכים של שני פולינומים שונים. פענוח רשימה בשיטה הדומה לזו שהציגו גורוסוואמי-סודאן מאפשר להתמודד עם אחוז שגיאות של . הרחבה של קוד פרברש-ורדי ל- פולינומים שונים מאפשר התמודדות עם אשר עבור בחירת גדול דיו מאפשרת אחוז שגיאות של . בעוד גורוסוואמי וסודאן הראו איך לעשות שימוש בקוד ריד-סולומון עצמו, הרי שפרברש וורדי מגדירים קוד חדש (שמבוסס למעשה על שליחת מספר עותקים של מילת ריד-סולומון).
בשנת 2007 הציגו גורוסוואמי ורודרה (Guruswami, Rudra) כיצד להתקרב לחסם ולקבל קוד המתמודד עם יחס שגיאות של לכל . הקוד של גורוסוואמי ורודרה, הידוע בשם קוד ריד-סולומון מקופל (Folded Reed-Solomon Code), מראה כיצד ניתן "לקפל" את ערכי הפולינומים השונים לתוך סימבול אחד, בשיטה דומה לקוד פרברש-ורדי אך בצורה יעילה יותר. הקיפול אפשרי לאור העובדה שקיים קשר בין הפולינומים השונים הנשלחים בקוד, וקשרים אלו יכולים לשמש לחסכון בשליחת מידע, ולהגדלת יעילות הקוד.
^חסם הסינגלטון קובע כי מרחק הקוד, , מקיים תמיד
. קוד ריד-סלומון מקיים את השוויון. מכיוון שבקוד כלשהו ניתן לתקן לכל היותר , קוד ריד-סלומון מסוגל לתקן כמות שגיאות מקסימלית לקוד עם פרמטרים ו-.
^בתחילת מסעה שידרה הגשושית תמונות ללא דחיסה ועל כן עשתה שימוש בקוד תיקון שגיאות "פשוט". עם התרחקות הגשושית והגעתה לאורנוס ונפטון, בוצעה דחיסה של חלק מהתמונות הדיגיטליות ועל-כן נדרש לבצע תיקון שגיאות חזק יותר, שבוצע על ידי קוד ריד-סולומון.[1]
^אנו זקוקים לקבוצה סופית של מספרים אשר ניתן לבצע בה פעולות חשבון בסיסיות כגון חיבור כפל וחילוק (על מנת לחשב את הפולינום), ועדיין הערך של כל פעולה כזו יהיה אחד האיברים בקבוצה. זו בדיוק התכונה המתמטית של שדה סופי.
^עבור קוד המסוגל לתקן שגיאות הסיבוכיות המתקבלת היא
. לכן, עבור התמודדות עם קצב שגיאות קבוע (למשל - עשירית מהמידע המועבר הוא שגוי), נדרש והסיבוכיות המתקבלת אקספוננציאלית
ב-.
^הקוד בו נעשה שימוש הוא למעשה קוד ריד-סולומון מוכלל מעל השדה הסופי המכיל 256 איברים. אורך כל סימבול 8 ביט, ועל כן אורך מילת המקור סיביות.
^לשם דיוק מתמטי, נדרש להגדיר התאמה בין האינדקס לבין אבר מתאים בשדה הסופי. ניתן לעשות זאת על ידי התאמת האבר לאינדקס , כאשר הוא שורש פרימיטיבי של השדה (האבר מותאם ל-).
^הסיבה היא שכל פולינום שמתקבל מחלוקה זו מזדהה עם בכל הנקודות בהן לא קרתה שגיאה. קיימות יותר מ- נקודות כנ"ל, ולכן הפולינום חייב להיות שווה ל- או בעל מעלה גדולה
מ-.
הערות שוליים
^ 123Stephan Wicker and Vijay Bhargava (eds.), Reed-Solomon Codes and their Applications, IEEE Press, 1994.
^I. Reed and G. Solomon, "Polynomial Codes Over Certain Finite Fields", Journal of the Society for Industrial and Applied Mathematics, 8:300-304, 1960.
^K.A. Bush, "Orthogonal Arrays of Index Unity", Ann. Math. Stat, (23) 426-434, 1952.
Tributary of Mill Creek in Luzerne County, Pennsylvania Laurel RunLaurel Run CreekLaurel Run in the late 1800s or early 1900sPhysical characteristicsSource • locationmountain in Bear Creek Township, Pennsylvania • elevationbetween 2,000 and 2,020 feet (610 and 620 m) Mouth • locationMill Creek in Wilkes-Barre, Luzerne County, Pennsylvania • coordinates41°15′40″N 75°51′22″W / 41.2611...
Peta infrastruktur dan tata guna lahan di Komune Bruyères. = Kawasan perkotaan = Lahan subur = Padang rumput = Lahan pertanaman campuran = Hutan = Vegetasi perdu = Lahan basah = Anak sungaiBruyères merupakan sebuah komune di departemen Vosges yang terletak pada sebelah timur laut Prancis. Lihat pula Komune di departemen Vosges Referensi INSEE lbsKomune di departemen Vosges Les Ableuvenettes Ahéville Aingeville Ainvelle Allarmont Ambacourt Ame...
Mohan RajaPekerjaanSutradara, penulis naskahTahun aktif2001–sekarangOrang tuaEditor MohanVaralakshmi MohanKerabatJayam Ravi (saudara) Mohan Raja adalah seorang sutradara dan penulis cerita asal India yang utamanya berkarya dalam industri film Tamil. Setelah membuat debutnya dengan film Telugu Hanuman Junction (2001), ia membuat remake dari beberapa film Telugu ke dalam bahasa Tamil, yang dimulai dengan film Jayam (2003) yang juga meluncurkan saudaranya Ravi sebagai pemeran utama. Pran...
You can help expand this article with text translated from the corresponding article in Serbian. (October 2022) Click [show] for important translation instructions. View a machine-translated version of the Serbian article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wik...
Telefónica's virtual mobile operator in Spain and Latin America This article contains content that is written like an advertisement. Please help improve it by removing promotional content and inappropriate external links, and by adding encyclopedic content written from a neutral point of view. (April 2021) (Learn how and when to remove this template message) Tuenti Technologies, S.L.U.Company typePrivate, LimitedIndustryInternetSoftwareTelecommunicationsFounded22 February 2006; ...
Chiara LubichLahirSilvia Lubich(1920-01-22)22 Januari 1920Trento, ItaliaMeninggal14 Maret 2008(2008-03-14) (umur 88)Rocca di Papa, ItaliaKebangsaanItaliaPekerjaanAktivisPenggantiMaria Emmaus Voce Chiara Lubich (22 Januari 1920 – 14 Maret 2008) merupakan seorang pendiri Gerakan Focolare. Dia lahir pada masa fasisme di Trento, Italia di mana dia tinggal dalam kemiskinan yang parah. Ayahnya seorang sosialis kehilangan pekerjaannya karena hukuman lawan politiknya. Untuk memb...
أنتوني فاوتشي (بالإنجليزية: Anthony Fauci) فاوتشي عام 2020. معلومات شخصية اسم الولادة أنتوني ستيفن فاوتشي الميلاد 24 ديسمبر 1940 (العمر 83 سنة)بروكلين مواطنة الولايات المتحدة الأمريكية عضو في الأكاديمية الوطنية للعلوم[1]، والأكاديمية الأمريكية للفنون والعلوم[2]، وا...
American filmmaker (born 1966) For other people named James Gunn, see James Gunn (disambiguation). James GunnGunn at the 2016 San Diego Comic-ConBornJames Francis Gunn Jr. (1966-08-05) August 5, 1966 (age 57)[n 1]St. Louis, Missouri, U.S.EducationLoyola Marymount UniversitySaint Louis University (BA)Columbia University (MFA)OccupationsFilm directorfilm producerscreenwriterstudio executiveYears active1989–presentEmployerWarner Bros. DiscoveryTitleCo-chairman and Co-CEO of D...
Flemish painter and designer (1499–1592) Self-portrait as Saint George Michiel Coxie the Elder, Michiel Coxcie the Elder or Michiel van Coxcie, Latinised name Coxius[1][2] (1499 – 3 March 1592), was a Flemish painter of altarpieces and portraits, a draughtsman and a designer of stained-glass windows, tapestries and prints. He worked for patrons in the principal cities of Flanders. He became the court painter to successively Emperor Charles V and King Philip II of Spain. ...
American politician Jim NashMember of the Minnesota House of Representativesfrom the 48A districtIncumbentAssumed office January 6, 2015Preceded byErnie Leidiger Personal detailsBorn (1967-09-23) September 23, 1967 (age 56)Political partyRepublicanSpouseKimChildren6Residence(s)Waconia, Minnesota, U.S.EducationUniversity of Nebraska Omaha (BA)OccupationBusiness ownerCybersecurityLegislatorWebsiteGovernment website Campaign website James A. Nash (born September 23, 1967) is...
Aerial bombing of Dublin, Ireland during World War II Mural commemorating the bombing vteThe Blitz (1940–1941)The Blitz Belfast Birmingham Bournemouth Bristol Cardiff Clydebank Coventry Dublin Hull Graveney Marsh Leeds Liverpool Manchester Plymouth Portsmouth Sheffield Southampton Swansea During the Second World War, Dublin was first bombed early on the morning of 2 January 1941, when German bombs were dropped on the Terenure area of south Dublin.[1] This was followed, early on the ...
فحص الركبة من أنواع فحص سريري إي ميديسين 1909230 تعديل مصدري - تعديل يفحص الطبيب الركبة طبيًا أو خلال العلاج الطبيعي كجزء من الفحص الجسمي، أو عندما يعاني المريض من آلام في الركبة أو تاريخ مرضي يشير إلى اضطراب في مفصل الركبة. يتضمن الفحص عدة أجزاء: الوضعية واللون والا�...
Bill WattsBill Watts en 2005.Données généralesNom de naissance Bill WattsNom de ring Bill Watts[1]Doctor Scarlett[1]Nationalité américainNaissance 5 mai 1939 (85 ans)Oklahoma City, Oklahoma[1]Taille 6′ 3″ (1,91 m)[1]Poids 297 lb (135 kg)[1]Catcheur retraitéFédération Midth-South Wrestling AssociationWorld Championship WrestlingWorld Wrestling FederationAmerican Wrestling AssociationCarrière pro. 1962[1] - 1986[1]modifier - modifier le code - modifier Wiki...
Maurice Papon Maurice Papon år 1945.Född3 september 1910Gretz-Armainvilliers, Seine-et-Marne, Île-de-France, FrankrikeDöd17 februari 2007 (96 år)Pontault-Combault, Seine-et-Marne, Île-de-France, FrankrikeNationalitetFranskYrke/uppdragÄmbetsman, politikerKänd förKrigsförbrytare Maurice Papon, född 3 september 1910 i Gretz-Armainvilliers, död 17 februari 2007 i Pontault-Combault, Seine-et-Marne, var en fransk ämbetsman, polischef och dömd krigsförbrytare. Biografi Papon...
Iñaki WilliamsWilliams con la maglia dell'Athletic Bilbao nel 2018Nazionalità Spagna Ghana (dal 2022) Altezza185[1] cm Peso77[1] kg Calcio RuoloAttaccante Squadra Athletic Bilbao CarrieraGiovanili 200?-2009 Natacion Pamplona2009-2012 Pamplona2012-2013 Athletic Bilbao Squadre di club1 2013-2014 Baskonia18 (7)2013-2015 Bilbao Athletic32 (21)2014- Athletic Bilbao349 (77) Nazionale 2015-2017 Spagna U-2117 (3)2016 Spagna1 (0)2022- Ghana19 (...
Inclusion or adoption in Christianity of a Sabbath day Christian denominations teaching first-day Sabbatarianism, such as the Free Presbyterian Church of Ulster, observe the Lord's Day as a day of worship and rest. Many Christians observe a weekly day set apart for rest and worship called a Sabbath in obedience to Gods commandment to remember the Sabbath day, to keep it holy. Early Christians, at first mainly Jewish, observed the seventh-day (Saturday) Sabbath with prayer and rest. At the beg...
ألبرت أوفرهاوسر معلومات شخصية الميلاد 17 أغسطس 1925 سان دييغو الوفاة 10 ديسمبر 2011 (86 سنة) [1] ويست لافاييت مواطنة الولايات المتحدة عضو في الأكاديمية الوطنية للعلوم، والأكاديمية الأمريكية للفنون والعلوم الحياة العملية المدرسة الأم جامعة كاليفور�...
هيلنهآن - شيلنبيرغ شعار الإحداثيات 50°36′46″N 8°01′35″E / 50.612777777778°N 8.0263888888889°E / 50.612777777778; 8.0263888888889 [1] تقسيم إداري البلد ألمانيا[2] التقسيم الأعلى منطقة فيستر فالد كرآيس خصائص جغرافية المساحة 7.28 كيلومتر مربع (31 ديسمبر 2017)[3] ...
1979 Indian filmKadavul Amaitha MedaiTitle cardDirected byS. P. MuthuramanScreenplay byVaaliStory byGollapudi Maruti RaoStarringSivakumarSumithraCinematographyBabuEdited byR. VittalT. K. RajanMusic byIlaiyaraajaProductioncompanyTrisool FilmsRelease date 7 September 1979 (1979-09-07) CountryIndiaLanguageTamil Kadavul Amaitha Medai (transl. The stage set by God) is a 1979 Indian Tamil-language film directed by S. P. Muthuraman. The film stars Sivakumar and Sumithra. It was...