קוד תיקון שגיאות

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף תיקון שגיאות)
קפיצה לניווט קפיצה לחיפוש

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

ניסוח פורמלי[עריכת קוד מקור | עריכה]

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

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

קודי תיקון שגיאות פשוטים[עריכת קוד מקור | עריכה]

הקוד הפשוט ביותר לתיקון שגיאות הוא פשוט קוד החזרה- חוזרים על המסר המשודר מספר פעמים. אם בתחילה המרחק המינימלי שבין שתי מילים בקוד היה d אז בקוד שבו יש חזרה נוספת על המסר, המרחק המינימלי הוא כבר 2d וכן הלאה- קוד שמילותיו הן פשוט n חזרות על מילות הקוד המקורי הוא קוד שהמרחק המינימלי בין מילותיו הוא nd.

לדוגמה נניח שהקוד המקורי הוא פשוט {0,1} (הקוד הבינארי הפשוט), קוד זה הוא בעל מרחק 1, ובו לא ניתן לזהות שגיאות. אם נחזור על כל דבר פעמיים, נקבל את הקוד {00,11}. זה קוד עם מרחק 2, ולכן ניתן לזהות שגיאה בשידור (תתקבל המילה 01 או 10, שבוודאי לא שודרה), אבל לא לתקן אותה: אם התקבל 01 לא ניתן לדעת אם שודר במקור 00 או 11. אם נחזור על כל דבר שלוש פעמים, נקבל את קוד החזרה {000,111}. זה קוד עם מרחק 3, ובו כבר ניתן לא רק לזהות, אלא גם לתקן טעות אחת: אם התקבל 001 אז כנראה שודר 000.

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

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

קודים מורכבים[עריכת קוד מקור | עריכה]

אפשר להשתמש באמצעים אלגבריים מתוחכמים לבניית קודים מאוד חזקים מבחינת כמות המילים שניתן לקודד בהם, לעומת המרחק המינימלי בין מילות הקוד. לדוגמה, ניתן ליצור קוד תיקון שגיאות שישדר מידע של שלושה ביטים, A, B ,C. הקוד יורכב משלוש אותיות שהן פשוט הביטים עצמם ואחריהן שלוש קומבינציות ה-XOR ביניהם - AxB, AxC, BxC. קוד זה הוא בן 8 מילים שונות (מידע של שלושה ביטים), אורכו הוא 6 והמרחק בין כל שתי מילים שונות בקוד גדול או שווה ל-3.

קיימים קודים חזקים כלליים כמו קודי המינג, קוד LDPC,‏ Trellis, קוד ריד-סולומון ועוד.

באופן כללי, קודי התיקון מתחלקים לשתי קבוצות: קוד בלוק ו קוד קונוולוציה.

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


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

שיטת VLRC מאפשרת זיהוי מיקום השגיאה הבודדת ותיקונה, זיהוי של שתי שגיאות ללא תיקון ורק במקרה ויש 4 שגיאות בצורת מלבן- שיטה זו לא מגלה את השגיאה. צורת מלבן הכוונה לשתי שגיאות בטור ושתי שגיאות בשורה.

שיטת Check Sum היא שיטה יחסית פשוטה. במידה ויש שתי טעויות באותו המקום (1 כלפי מעלה ו1 כלפי מטה) אז לא מתקבלת הודעת שגיאה.

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

שיטת Code Hamming בניית code hamming: 1. רושמים מספרים החל מ-1 בסדר עולה. מקומות של 4^2 (1,2,4,8..) ומסמנים ב-X. 2. מעבירים מספר מהקסה לבינארי. 3. לוקחים מיקום של כל האחדים שנמצאים בשידור ורושמים בצד את המיקום שלו בבינארי. 4. עושים xor בין כל המספרים שנמצאים בעמודה. המס' המתקבל הוא code hamming. 5. ניתן לשדר את המידע ו- code hamming ב-2 שיטות: שיטה ראשונה- שולחים מידע ואז שולחים קוד. שיטה שנייה- מעתיקים קוד לתוך מילת שידור במקומות שבהם נמצא x ואז שולחים את המידע יחד עם קוד בפנים.


ראו גם[עריכת קוד מקור | עריכה]