תורת הקודים

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

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

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

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

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

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

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

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