קוד תיקון שגיאות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
התחלת שכתוב |
המשך שכתוב |
||
שורה 7:
לקודים מתקני שגיאות יש את היכולת לזהות שהתרחשה שגיאה, ויותר מזה- גם לזהות מה היתה המילה המקורית. היכולת הזו נובעת ממרחק הקוד הגדול. למעשה לפי אותו רעיון כמו בזיהוי השגיאות- ניתן לתקן שגיאות במסר כל עוד מספר השגיאות קטן ממש ממחצית המרחק של הקוד. אחרת יכולות להיות שתי מילים שונות בקוד שמרחקן מהמסר שהתקבל הוא המינימלי מבין כל מילות הקוד, ולכן לא ניתן להכריע איזו מילה נשלחה במקור.
==קודי תיקון שגיאות פשוטים==
הקוד הפשוט ביותר לתיקון שגיאות הוא פשוט קוד החזרה- חוזרים על המסר המשודר מספר פעמים. אם בתחילה המרחק המינימלי שבין שתי מילים בקוד היה 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):
:<math>: \ C^+ = \left\{ (x_1, . . . , x_k , x_{k+1} ) : x_1 + . . . x_k + x_{k+1} = 0 \right\} </math>
ספרת הביקורת מעלה את המרחק בין שתי המילים הקרובות ביותר בקוד ב-1.
==קודים מורכבים==
באמצעים אלגבריים מתוחכמים לבנות קודים מאוד חזקים מהבחינה של כמות המילים שלהם מול המרחק המינימלי בין מילות הקוד.
לדוגמה, ניתן ליצור קוד תיקון שגיאות שישדר מידע של שלושה [[ביט|ביטים]], A, B ,C. הקוד יורכב משלוש אותיות שהן פשוט הביטים עצמם ואחריהן שלוש קומבינציות ה-[[XOR]] ביניהם - AxB, AxC, BxC. קוד זה הוא בן 8 מילים שונות (מידע של שלושה ביטים), אורכו הוא 6 והמרחק בין כל שתי מילים שונות בקוד גדול או שווה ל-3.
באופן כללי, קודי התיקון מתחלקים לשני קבוצות: [[קוד בלוק]] ו [[קוד קונוולוציה]].
את ה"כוח" של קוד התיקון מודדים בדרך כלל בהגבר (לדוגמה 3 [[דציבל|דציבלים]]
==ראו גם==
| |||