תורת הקודים

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

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

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

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

מרחק המינג

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

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

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

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

קודים לינאריים

ערך מורחב – קוד לינארי

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

משמעות הדרישה שקוד מסוים הוא מרחב וקטורי היא שהקוד סגור תחת פעולות חיבור וכפל בסקלר אשר יוגדרו להלן:

• לכל שתי מילות קוד $\ (a_{1},...,a_{n}),(b_{1},...,b_{n})\in C$, שייכת גם המילה $\ (a_{1}+b_{1},...,a_{n}+b_{n})$ לקוד.
• לכל מילת קוד $\ (a_{1},...,a_{n})\in C$ וסימן $\ x\in F$ בא"ב, שייכת גם המילה $\ (xa_{1},...,xa_{n})$ לקוד.

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

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

ראו גם

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