Error correction codes...

[ה עוד אחד]

Error correction codes...

שלום

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

 

[אמיתי ר]

יש הרבה שיטות ../images/Emo13.gif

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

 

[ה עוד אחד]

ה"מורכבות" של השיטה לא משנה לי

ועדיף שתהיה מסוגלת לתקן את כל השגיאות

 

[ה עוד אחד]

אבל כמובן שאני מעדיף שיטה

לא מורכבת שמסוגלת לתקן את כל השגיאות והתוספת שלה קטנה מאד יחסית לאורך המידע. הדבר הכי חשוב לי הוא תיקון כל השגיאות, אח"כ אורך תוספת קטן והמורכבות במקום האחרון

 

[yoniBLA]

תיקון כל השגיאות זה קצת בעייתי,

אם במקרה אתה מעביר את המידע דרך איזה פרוקסי שהחליט להחליף את המידע שלך ברנדום, יהיה קשה לתקן את כל השגיאות

אתה צריך להגדיר כמה שגיאות אתה רוצה להיות מסוגל לתקן בכל X בתים, וזה מה שיקבע את גודל התוספת.

 

[ה עוד אחד]

יש לך המלצה על אלגוריתם?

 

[yossiea]

מה רע באלגוריתם CRC?

תוכל למצוא הרבה הסברים וקודים לדוגמא ברשת. הרעיון הבסיסי הוא פשוט. אתה מחלק את המידע בפולינומיאל מסויים בגודל 16 ביט או 32 ביט (לפי סטנדרט מסויים) וה-CHECKSUM זה השארית. זה נעשה עם XOR ו- SHIFT בלבד. הסיכוי לפיספוס במקרה של CHECKSUM של 32 ביט הוא נמוך מאוד. בדרך כלל מסתפקים בזה.

 

[ה עוד אחד]

CRC מתקן שגיאות?

לפי מה ששראיתי הוא רק יכול למצוא אותן... יש לך אולי קישור?

 

[גיל14]

Cyclic Redundancy Check

http://en.wikipedia.org/wiki/Cyclic_redundancy_check לפי ויקיפדיה, רק בודק אותן.

 

[yossiea]

האמת...

לא שמתי לב שאתה מבקש אלגוריתם "שמתקן" שגיאות. CRC לא מתקן שגיאות הוא רק מאתר שגיאות. זה מכניס אותנו לנושא אחר לגמרי שנקרא "תורת הקודים" ואני לא מובין כל כך גדול בתחום הזה, אני מודה. בכל אופן לפי מיטב הבנתי כמעט בלתי אפשרי לתקן את "כל" השגיאות, אבל ברור שתיקון שגיאות מחייב תוספת יתירות גדולה (ככל שאתה מתקן יותר שגיאות תצטרך תוספת גדולה יותר) הרבה יותר גדולה ממה שאתה מצפה. יש הרבה אלגוריתמים ידועים לתיקון שגיאות. אם אתה סטודנט שלומד וצריך לעשות עבודה בעצמו לא אוכל לעזור לך בעניין פשוט משום שהרקע שלי בנושא חלש. אם אתה בסך הכל מחפש אלגוריתם מוכן ורוצה פשוט ליישם אותו יש כמה אלגוריתמים טובים. חפש בויקיפדיה, יש את Reed-Solomon, Golay, Hamming, Reed-Muller ועוד רבים. זה נושא ענק ובטח שלא נכנסים לזה על רגל אחת.

 

[ה עוד אחד]

טוב! תודה לכולם ../images/Emo13.gif