תורת הקודים

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 קודים להעברת מידע
- 1.1 מרחק המינג
- 1.2 קודים לינאריים
2 ראו גם

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

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

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

[עריכה] מרחק המינג

קודם כל נגדיר מרחק המינג בין שתי מילים בקוד שאורך מילותיו קבוע, על שם המתמטיקאי ריצ'רד המינג שפיתח את תורת הקודים. מרחק המינג יהיה מספר המקומות שבהם המילה הראשונה שונה מהמילה השנייה. קל לראות שזו מטריקה ולכן נוהגים לסמן אותו $\ d(x,y)$ כאשר $\ x , y \in C$ (C הוא הקוד).
מרחק המינג של קוד, הוא השוני המינימלי בין שתי מילות קוד שונות. בהינתן קוד C מרחק המינג שלו מסומן $\ d(C)$ .

$\ d(C)= min \left\{ d ( x, y ) : x \ne y \right\}$ .

הסימון הוא זהה ומבחינים בין השימושים השונים לפי ההקשר.

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

[עריכה] קודים לינאריים

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

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

אחרי שנזהה את אותיות הקוד עם איברי השדה בן q אברים נקבל זיהוי של הקוד עצמו עם תת קבוצה של המרחב הווקטורי $\mathbb{F}_q ^n$ , כאשר $\mathbb{F}_q$ הוא השדה שמזוהה עם אותיות הקוד, ו-n הוא אורך כל מילה בקוד. בצורה הזו מוגדרים חיבור וכפל בסקלר על איברי C, ולכן ניתן לשאול האם C הוא מרחב וקטורי מעל $\mathbb{F}_q$ או לא. אם הוא מרחב וקטורי- אז הוא קוד לינארי. בקודים לינאריים נהוג לציין את ממד הקוד כמרחב וקטורי, ולא את מספר המילים שבקוד (שהוא q בחזקה הממד).

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