שיחה:קוד ריד-סולומון

הערות

1. פסקת המבוא אינה מדייקת: קוד ריד-סלומון אינו "קוד ליניארי המשמש לתיקון שגיאות" (כל קוד ליניארי משמש לתיקון שגיאות), אלא "קוד ליניארי המבוסס על אינטרפולציה של פולינומים" (אבחנה מבדלת). הקוד גם אינו "באופן כללי" הקידוד והפענוח של עצמו; הפענוח והקידוד משמשים לתרגם מידע אל הקוד וממנו, אבל הם אינם הקוד (כפי שהוא מוגדר, נכונה, בערך קוד).
2. מן הערך משתמע, חלילה, שקיים שדה סופי בן 28 איברים. האם משתמשים במקרה כזה בשדה גדול יותר ומשדרים רק 28 ערכים, או שעובדים בחוג הפשוט-למחצה הקומוטטיבי הסופי (היחיד) בגודל הזה? עוזי ו. - שיחה 21:26, 1 באוגוסט 2010 (IDT)

עוזי, תודה! הערך עדיין מכיל כמות די גבוה של אי-דיוקים (וגם סתם טעויות..) שעוד צריך ללטש ולתקן. בהמשך למה שציינת - בהחלט קיים בלבול רב בין סימבול לביט (ולמרות שכתוב שהאורך הוא ביטים, הוא למעשה סימבוליםף אני אתקן בקרוב). לגבי השאלה על השדה - עושים שימוש בשדה גדול יותר, ולכן כל סימבול ארוך יותר, אבל הקוד נשאר באותו אורך. לגבי ההערה על הפתיחה - לא בדיוק הבנתי לאיזה משפט אתה מתכוון (האם ל"קוד ריד-סלומון (Reed‪-‬Solomon Code) הינו קוד תיקון שגיאות לינארי")? אמנם תורת הקודים טוענת כי קוד נועד ל"העברה יעילה של מידע דרך מערכת מציאותית שיוצרת שגיאות ברצף", אך טענה זו לא מאד מדוייקת, ותפקיד קוד יכול להיות כלשהו (למשל, שפת הנאוואחו הינה קוד (ראה מילת קוד), ומטרתה אינה תיקון שגיאות; יש קודים שנועדו לדחיסה: ובהם אורך מילת הקוד קצר ממילת המקור, ועוד.).

לגבי ההערה על הגדרת הקוד בתור אוסף המילים לעומת אלגוריתם הקידוד/פענוח - מתמטית אתה צודק ללא צל של ספק. אני מנסה לחשוב האם קידוד למעשה לא מגדיר את הקוד חד-חד ערכית, והינו שקול להגדרת אוסף מילות הקוד. (ה"פענוח" בוודאי חסר משמעות מבחינת ההגדרה המתמטית של הקוד, אבל חשוב מהבחינה האלגוריתמית. יש לך רעיון איך להבליט את המשמעות הזו, בלי לפגוע בדייקנות בהגדרה?)

(ושוב תודה! אשמח להערות נוספות כשיושלם הערך..) Gran - שיחה 06:41, 2 באוגוסט 2010 (IDT)

כש"מאריכים" את הסימבולים, זה פוגע ביעילות הקוד, ומבחינה אינפורמטיבית שקול להארכת הקוד. בכל מקרה לדבריך אין קוד RS(24,28). מדוע בעצם לא לקודד למכפלת השדות $\ \mathbb {F} _{7}\times \mathbb {F} _{4}$? במבט ראשון נראה שכל תורת הפולינומים תעבוד שם בדיוק כמו מעל שדה.

ההגדרה הנוכחית של קוד מדברת על קבוצת מלים; אפשר לשנות ולראות בקוד פונקציה מהמקור למלת-הקוד (מה שבינתיים קראנו לו "קידוד") אבל צריך להיות עקביים. מהפונקציה אפשר לשחזר את הקוד עצמו, בהנחה שאין טעם לפזר בו מלים שאינם יכולות להתקבל בפועל. בקיצור, אני מעדיף לקבוע ש"קוד" הוא קבוצת המלים (בתמונה), וקידוד הוא הפונקציה מן המידע לקוד. יש דרכים רבות לחשב את אותו קידוד, ולכן אפשר לדבר על "קידוד יעיל", כאלגוריתם לחשב את הקידוד. עוזי ו. - שיחה 18:15, 2 באוגוסט 2010 (IDT)

לפעמים, משיקולי אפנון (למשל) רוצים להשתמש בסימבול באורך מסויים - למשל - סימבול נפוץ הוא באורך 8 ביט, ואז כל הפעולות הן $GF(2^{8})$. אם רוצים לקצר את היתירות, מקטינים את n. אני עדיין חושב שניתן להתייחס ל"קוד" כאל פונקציית ההתאמה עצמה, אבל אני מסכים שזה לא סטנדרטי ולא מקובל (והורס את האבסטרקציה, וההפרדה בין הקוד למרחב המקור). אני אשתמש בהגדרות המקובלות במקום.

הערות

1. המבוא הוא מאוד לא ידידותי. אם מטרת הערך היא להיות נגיש להדיוטות, כדאי להוסיף דוגמאות ולא להישאר ברמת ה"ערוץ תקשורת רועש/תווך שעלול להכיל שגיאות" (למשל - אפשר לדבר על שידורים סלולריים ועל DVD-ים; בפרט בכל הנוגע ל-DVD-ים אכן משתמשים בהם בריד-סולומון בפועל אם איני טועה כך שהדוגמה קולעת). גם המשך הפתיחה יחסית טכנית וקשה; עדיף קודם כל לומר שהקוד אופטימלי במובן מסויים (ולתאר את המובן הזה במילים השוות לכל נפש) ורק בסוף לדחוס את ה"לכלוך" המתמטי.
2. "במאמרם משנת 1960 הציגו ריד וסלומון שיטה יעילה ופשוטה לקידוד המידע" - טוב ויפה, אבל מה זה "המידע" המדובר שהוא זוכה לה' הידיעה?
3. "הרעיון המתמטי מבוסס על שימוש בפולינום המוגדר מעל שדה סופי, רעיון שהוצג לראשונה בשנת 1952.‏" - מה הוצג ב-1952 - הרעיון להשתמש בפולינומים מעל שדות סופיים בתורת הקודים, או הרעיון לדבר על פולינומים מעל שדה סופי? כרגע המשפט מבלבל והקורא ההדיוט עוד עלול לחשוב שמדובר על הפירוש השני (שאני מניח שאינו נכון...)
4. "תפקידו של אלגוריתם הקידוד לקחת את המילה שאנו רוצים להעביר בערוץ התקשורת (מילת המקור)..." - לטעמי עדיף להימנע מכתיבה בסגנון "אנחנו רוצים" שמתאימה יותר לסיכום תרגול באוניברסיטה ולא לאנציקלופדיה.
5. "אלגוריתם הפענוח מקבל כקלט את המילה הארוכה, ומנסה לשחזר את המילה המקורית למרות שגיאות מסוימות אשר נוצרו בעקבות רעשים בערוץ." - אז זהו, שלא, אלגוריתם הפענוח לא מקבל את המילה הארוכה אלא מילה "מקולקלת" וצריך לחדד את הנקודה הזו.
6. "עד לשנת 1967, לא הייתה ידועה שיטה לבצע פענוח יעיל של מילה מקודדת." - ויקי האנגלית אומרת 1969. אולי כדאי לתת רפרנס למאמר.
7. "קוד ריד-סולומון המקודד k סימבולים ל-n סימבולים מסומן ב-RS(n,k)" - חסרה נקודה.
8. "הרעיון המתמטי העומד מאחורי הקוד הינו פשוט ביותר" - אולי כדאי לוותר על ההדגשות הבלתי פוסקות של כמה הכל פשוט.
9. "על מנת להגדיר את הפולינום ‪f(x)‬ בצורה חד-חד ערכית..." - מעל שדה, כמובן.
10. "נניח שאנחנו רוצים להעביר בערוץ תקשורת רועש..." - אני מזכיר שוב את ההערה מלמעלה (ולו רק מכיוון שלחלק מכותבי ויקיפדיה ההרגל המגונה לטפל רק בדוגמה הספציפית שנתלוותה להערה, ולא בבעיה ה"כללית" שנמצאת בכל הערך).
11. "קל לראות..." - ניסוח של ספר לימוד/הרצאה, לא אנציקלופדיה.
12. "עוד שעד כה התייחסנו אל המספרים ai,f(x)..." - לא מתקמפל טוב אצלי מבחינת סוגריים. קורה גם בהמשך במקומות מסויימים.
13. "שידור "מספר כלשהו" מצריך כמות אינסופית של ביטים." - לא נכון. הוא מצריך כמות לא חסומה של ביטים. ממש לא אותו דבר. אני גם לא חושב שזו הסיבה שבגללה משתמשים בשדה סופי - לא מיידית, ז"א. צריך אולי לתת הסבר קצר למה אי אפשר פשוט לשדר מספרים קטנים וחסל.
14. "ניתן לקודד כל סימבול על ידי logn ביטים." - הקהל הרחב מכיר log כלוג על בסיס 10. המתמטיקאים - כלוג על בסיס e. מדמ"חניקים יעדיפו שימוש ב-lg.
15. "אם המקומות הידועים הינם k האברים הראשונים של {\mathbb F}_n, הקוד המתקבל הינו סיסטמטי." - כל עוד הקישור אדום זה לא אומר לי כלום. אולי כדאי לתת הסבר מילולי קצר? כרגע זו שורה "מבוזבזת" מבחינתי.
16. "השימוש הרב בהגדרה זו נובע מהקלות היחסית לממש מערכת המבצעת קידוד של מילה על ידי סכימת הזזות ציקליות של הפולינום היוצר, וללא צורך בביצוע אינטרפולציה אשר דורשת יותר משאבי חישוב." - לא הבנתי. בשביל קידוד בשיטה ה"קלאסית" לא צריך אינטרפולציה אלא חישוב של ערכי פולינום נתון בנקודות מסויימות. זה ה שמבצע אינטרפולציה, לא?
17. "(שנים לאחר המצאת הקוד!)" - לא כדאי להתרגש ולהתלהם, מה גם ששבע שנים זה לא עד כדי כך גדול (אפשר להביא כדוגמה בעיה של פרמה שאוילר פתר 40 שנים (!) אחרי שהחל לעבוד עליה).
18. "יש לבצע אינטרפולציה עבור כל אחת מתוך {n \choose k} האפשרויות השונות, וזהו מספר אקספוננציאלי של חישובים שאינו נחשב יעיל." - אקספוננציאלי במה? עד כה דובר על סיבוכיות רק כתלות ב-n, ואז מספר האפשרויות המדובר הוא פולינומי (עם חזקה k). צריך להכניס גם את k לדיון הסיבוכיות ואת זה לא עשית.
19. "פענוח מילה יחידה (192 ביט של מידע‏[13]) מצריך ביצוע כ-20 אלף אינטרפולציות, בעוד הזמן המוקצה לכך בתקליטור הינו כ-0.000136 שניות." - הרבה מספרים ומעט אינטואיציה. מחשבים מבצעים מיליארדי פעולות בשניה - אולי 20 אלף אינטרפולציות זה לא כזה נורא? צריך להסביר למה זה כן נורא וכמה זמן דברים כאלו עשויים לקחת.
20. "התכונות של פולינום השגיאה הינם שבכל אינקדס i בו קרתה שגיאה..." במילת הקוד "אינדקס" נפלה שגיאה באינדקסים 4-5.
21. "אבל ידוע שפולינום כנ"ל קיים." - זה השלב שבו ההדגשות החוזרות ונשנות כבר התחילו להציק לי.
22. "אם מישהו מגלה לנו מיהם הפולינומים" - גם "מישהו" וגם "מיהם" הפולינומים (ולא "מהם" - הם הרי אינם אנושיים, עד כמה שארגון צער בעלי פולינומים מנסה לטעון אחרת) - לא אנציקלופדי.
23. "תיקון מחיקות הינו "קל" יותר מאשר תיקון שגיאות". לא נכון. תיקון מחיקות הינו קל יותר מאשר תיקון שגיאות, נקודה. למה המרכאות?
24. הערה אישית לסיום - פרט לשימושיות המעשית רבה שלהם, לקודי ריד-סולומון חשיבות גדולה גם בחלקים מסויימים של מדעי המחשב התיאורטיים ובפרט בכל הקשור למשפט ה-PCP שגרסה אחת שלו מוכחת באמצעותם. חבל לי שאין התייחסות לכך בטקסט (והתייחסות רצינית יותר מאשר סתם להזכיר את מה שכתבתי כאן וחסל). גדי אלכסנדרוביץ' - שיחה 16:09, 12 באוגוסט 2010 (IDT)

תודה גדי, אשקוד על תיקונים בקרוב. Gran - שיחה 07:04, 13 באוגוסט 2010 (IDT)

תיקונים לאור ההערות

הערות רבות ומועילות. טרחתי ותיקנתי. להלן תקציר השינויים, בהתאמה למספור ההערות:

1. באופן אישי עמדתי היא שפסקת הפתיחה מיועדת לכל, ולא לקהל ההדיוט, ועל כן צריכה להיות תמציתית ומדוייקת (ולא מסבירה ופרושת - שהרי אין מקום להגדיר את כל הדברים שצריך). אעפ"כ - העברתי את ההגדרות להמשך, ונותרנו עם פסקת מבוא קצרצרה (ומעט "פרווה"), אבל לא מאיימת על הקורא שאינו מגיע מהתחום.
2. תוקן.
3. הערתך מוכיחה את הטענה הפשוטה - כאשר הכותב רושם טענה לא ברורה, הסיבה היא שהוא עצמו לא מבין מה הוא רצה לומר. בדקתי שנית את הספרות, הבנתי שלא הבנתי, ותיקנתי בהתאם :) [רואה - ידעתי שיהיה נכון לקבל ממך הערות!]
4. מסכים. שינתי רוחבית.
5. חודד.
6. ההבדל, להבנתי, נובע מהשוני בין גרסת הכנס (1967) לגרסת הז'ורנאל וגרסאות ההמשך (היו לברלקמפ כמה מאמרים ב1968-1970). העובדה שהשיטה הראשונה הוצגה ב1969 נלקחה ממקור[1] ע"מ 13, שגם מצויין בסוף המשפט כמקור (והנה בדף השיחה יש הבהרה נוספת לנושא זה). אגב - השאלה הזו של כנס/זורנאל חוזרת שוב ושוב, ואין לי דעה ברורה בעניין. לרוב אני משתמש בגרסת הכנס כשאני מדבר על ראשוניות, ועל הגרסה הסופית כשאני מדבר על התוצאה עצמה, מה שיוצר חוסר עקביות מסויים.
7. תוקן.
8. טוב, נעדן את הפשטות (אבל זה באמת ממש ממש פשוט ;)
9. כן, אבל אין שום סיבה לחשוב שלא מוגדר שדה. כלומר - זו הערה מאד מאד מתקדמת, ולדעתי לא רלוונטי לציין כאן קיומו של שדה (כל הפסקה הזו בכלל עוסקת במספרים ממשיים, בלי להגדיר זאת, וטוב שכך).
10. קיבלתי.
11. עניין של טעם.
12. ידוע. זה בגלל שברירת המחדל הינה לא להציג כ-png. תקוותי שהמצב ישתנה בקרוב, וראה שיחת עזרה:נוסחאות#הצגת נוסחאות
13. תיקנתי, אבל אני לא בטוח שירדתי לסוף דעתך. מדוע "לא חסומה" עדיף על "אינסופית"?
14. צודק. הרגלים רעים של מדמ"חניקים.
15. צר לי שהקישור אדום, אולי בעתיד הוא וחבריו יכחילו (ואויל אפילו בעזרתי). הסברתי בחצי שורה, אבל צריך לתחום את המאמר הזה ממאמרים אחרים...
16. לא בדיוק הבנתי אותך. ההערה לא משווה לשיטה הקלאסית, ואולי זה מה שמבלבל. אני אמחק את החלק המבלבל - זה לא מידע מועיל. אכן הסיבה כנראה יותר קשורה לעבודה שכך הקוד הוא מקרה פרטי של BCH. אני לא בטוח בכך.
17. צודק, בהתחלה זה היה 9 שנים, שזה יחסית הרבה לרעיון ממש, אבל ממש פשוט..
18. הדיון צריך להשאר סביב n ולא k. הוספתי הערה להבהיר את הגודל.
19. כמה זמן לוקח 20 אלף פעולות?? לא יודע - זה תלוי בטכנולוגיה. אבל הצדק עמך - הוספתי דוגמא שתחזק את האינטואיציה - DVD ו $10^{20}\approx 2^{60}$ פעולות. זה לבטח לוקח כמה שעות עבור ענן מחשבים רציני (כפי שלוקח לפיצוח DES), או כמה ימים למחשב ביתי.
20. מזל שהפעלתי אלגוריתם לזיהוי שגיאות].
21. מיתנתי.
22. תוקן.
23. כי המילה "קל" לא מוגדרת היטב. מה זה יותר קל?? שניהם ניתנים לביצוע בזמן פולינומי. ה"קלות" נותן אינטואיציה שאחד הינו מקרה פרטי של השני.
24. מסכים, אם כי הידע שלי בנושא דל למדי - ולא יהיה לי הזמן ללמוד זאת בעצמי. אותיר זאת לשאר אנשי המדע שבינינו (או לזמנים אחרים)

Gran - שיחה 04:59, 15 באוגוסט 2010 (IDT)

בקשר ל-13: "אינסופית" פירושה שאתה צריך לשדר אינסוף ביטים. "לא חסומה" פירושה שלכל מספר בפני עצמו, אתה צריך לשדר כמות סופית של ביטים; אלא שככל שהמספר גדל, כך גם כמות הביטים גדלה ולא ניתן לחסום אותה. בשום שלב אתה לא צריך לשדר אינסוף ביטים (אינסוף ביטים ישודרו רק אם תשדר אינסוף מספרים; ובמקרה כזה, גם אם היינו צריכים לשדר רק 0 או 1, עדיין היינו משדרים אינסוף ביטים).

בקשר ל-15, נראה לי שבכל מקרה מומלץ להסביר קצת על מה מדובר לטובת הקורא שלא יתחיל לקרוא ערך אחר עכשיו.

בקשר ל-17, אני לא חושב שהרעיון פשוט עד כדי כך, ויותר מזה - דברים לרוב נוטים להיראות פשוטים יותר בדיעבד.

בקשר ל-23, אני חושב שההגדרה של קל די ברורה בהקשר הספציפי שבו המילה הזו מופיעה, ועל כן המרכאות מיותרות. אם זה מפריע לך עדיף להשתמש במילה אחרת ולא במרכאות (שנותנות תחושה של "אה... אני לא סגור על מה שאני רוצה לומר כאן אז אני משתמש במרכאות כדי לא להתחייב" - לא משהו שצריך להופיע באנציקלופדיה). גדי אלכסנדרוביץ' - שיחה 09:34, 10 בספטמבר 2010 (IDT)

הערות

• בפסקה "יעילות הקוד במקרים פרטיים שונים" לא הבנתי למה "במידה וכל סימבול מיוצג כרצף של ביטים באורך c הקוד יכול להתמודד עם לכל הפחות (n − k) / 2 ביטים שגויים (המפוזרים כל אחד בסימבול שונה), ולכל היותר עם c(n − k) / 2 ביטים שגויים (המקובצים כולם באותם (n − k) / 2 סימבולים)"? בשני המקרים יש (n-k)/2 סימבולים שגויים לא?
• במשפט "קודי ריד-סלומון פתחו עידן רחב של מחקר בתחום תורת הקודים ויישומיה" - צריך כנראה להיות "עידן חדש"

ערן - שיחה 09:55, 21 באוגוסט 2010 (IDT)

בשניהם יש אותו מספר של סימבולים שגויים, אך מכיוון שכל סימבול מהווה c ביטים - יכול להיות שסימבול שגוי הוא למעשה הסימבול המתקבל על ידי ביט שגוי יחיד, או סימבול המתקבל על ידי שינוי כלל c הסיביות. במילים אחרות - לעיתים כאשר נופלות c שגיאות ב c סיביות רצופות - רק סימבול יחידי "נפגע" ומשתבש.. הכתוב מעט מטעה כעת, אני חושב שאני מבין את ממה נובע הבלבול. תודה. Gran - שיחה 07:24, 22 באוגוסט 2010 (IDT)

שם הערך

בהתאם לכתיב האנגלי, Solomon, נראה לי שהשם הראוי לערך הוא קוד ריד-סולומון. דוד שי - שיחה 23:19, 31 באוגוסט 2010 (IDT)

כמה הערות

בסך הכל מדובר בערך נחמד ונראה לי שגם אני, ההדיוט במדעי המחשב, הבנתי את הרעיון הבסיסי. בכל זאת, יש לי כמה הערות (הן רלוונטיות לגרסה לשיפוט, אולי המצב השתנה מעט מאז):

1. המונח "קוד BCH" האדום חוזר בערך מספר פעמים ללא הבהרה מספקת. אם לא יוכחל בקרוב, כדאי לתת לפחות הסבר קצר.
2. הקישור למילה "תחילית" לא מתאים ומקשר למונח בלשון.
3. לדעתי הערות 6, 9 ו-16 צריכות להיות משולבות בגוף הכתוב.
4. נעשה שימוש במונח "סימבול" לפני הגדרתו (מופע ראשון בפסקה 1.0, הגדרה ב-2.2).
5. השימוש במונח האדום "חסם הסינגלטון" הופך את המשפט בו הוא מופיע לבלתי מובן.
6. בפרק על הקוד במובן המודרני יש הרבה קישורים אדומים והערך לא מנסה לכפר על היעדרם בהסבר קצר. אינני יודע עד כמה הדבר אפשרי, ולכן הערה זו מושארת לשיקול הכותב.
7. לא הצלחתי להבין איך מתבצע בפועל הפענוח המתואר בפרק 3.3. דוגמה יכולה להיות מאוד מועילה.
8. אם הבנתי נכון, בפרק 4.1 הכתוב "מבליע" את המעבר מפולינום לווקטור.

שמעון ~ שיחה ~ העם דורש פיזיקה! 19:33, 13 בספטמבר 2010 (IST)

שמעון, תודה על ההערות. הכחלתי את חסם סינגלטון, ותיקנתי חלק מההערותיך. אולי מישהו יקח על עצמו את המשימה לכתוב ערך על קודי BCH. זו אינה משימה פשוטה כלל ועיקר. Gran - שיחה 17:07, 16 בספטמבר 2010 (IST)

קישור שבור

במהלך מספר ריצות אוטומטיות של הבוט, נמצא שהקישור החיצוני הבא אינו זמין. אנא בדקו אם הקישור אכן שבור, ותקנו אותו או הסירו אותו במקרה זה!

• http://www.usna.edu/Users/math/wdj/reed-sol.htm
  • In קוד ריד-סולומון on 2013-05-05 09:54:38, 404 Not Found
  • In קוד ריד-סולומון on 2013-05-16 03:22:48, 404 Not Found

--Matanyabot - שיחה 06:23, 16 במאי 2013 (IDT)

ערך ויקפדיה מעולה

ערך מעולה. שלם, אובייקטיבי, אמין עם רמת כתיבה גבוהה. הודעה זו נכתבה באמצעות מערכת המשוב. 
‫82.166.0.86‬ 11:58, 9 באפריל 2024 (IDT)