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

מתוך המכלול, האנציקלופדיה היהודית
גרסה מ־05:51, 3 בספטמבר 2019 מאת מוטיאל (שיחה | תרומות) (החלפת טקסט – "לעתים" ב־"לעיתים")
קפיצה לניווט קפיצה לחיפוש

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

ניסוח פורמלי

קוד הוא קבוצת מילים, המורכבות ממספר קבוע של אותיות. כך, אם נסמן את קבוצת האותיות שבהן אנו משתמשים ב- , ואת אורך כל מילה בקוד ב-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 דציבלים לדוגמה).

ראו גם