|
'''תורת הקודים''' היא תחום ב[[מתמטיקה]] וב[[מדעי המחשב]] שעוסק בהעברה יעילה של מידע דרך מערכת מציאותית שיוצרתשעשויות ליצור שגיאות ברצף המידע המועבר. בתורת הקודים מפותח מושג ה[[קוד]] וכן גם כלים שמאפשרים הבחנה ותיקון שגיאות במידע המתקבל.
==קודים להעברת מידע==
בעיה זו נעשתה חריפה במיוחד בתקשורת בין מחשבים, בה שינוי של [[ביט]] אחד במסר יכול להרוס את החישוב כולו.
קודםעל כלמנת להתמודד עם שגיאות אלו מוקטים במספר שיטות: ראשית, אפשרניתן ליצור קוד (או שפה) בה אורך כל המילים הוא זהה. בצורה הזוזו ניתן לבודד בעיהאת הבעיה ולהתמודד עם כל מילה בפני עצמה (אם כי דילוג על אות יוביל לשגיאה מצטברת). דברשיטה נוסףנוספת שאפשרהיא לעשות כדי להתגבר על הבעיה ה הוא להגדיל אתהגדלת השוני בין מילות הקוד או השפה,. וכךכך לאפשרמתאפשר זיהוי ואפילו תיקון של שגיאות מספיק מעטות. הרעיון הבסיסי הוא שאם שולחים מסר ב[[קוד]] מסוים, ניתן להשוות את המסר השגוי שהתקבל למילותאל מילות הקוד ולקחתהאפשריות, אתולהחליט כי המילה ששודרה הינה מילת הקוד שהכי קרובה למסר (או את אחת מהמילים הקרובות ביותר), מתוך הנחה שבתהליך העברת המסר לא חלו יותר מדי שגיאות.
===מרחק המינג===
קודם כל נגדיר [[מרחק המינג]] הינו מדד למרחק בין שתי מילים בקוד שאורך מילותיו קבוע, הקרוי על שם ה[[מתמטיקאי]] [[ריצ'רד המינג]] שפיתח את תורת הקודים. מרחק המינג יהיהמוגדר בתור מספר המקומות שבהם המילה הראשונה שונה מהמילה השנייה. קל לראות שזושמד זה מהווה [[מטריקה]] ולכן נוהגים לסמן אותו <math>\ d(x,y)</math> כאשר <math>\ x , y \in C</math> (C הוא הקוד). <br>
'''מרחק המינג של קוד''', הוא השוני המינימלי בין שתי מילות קוד שונות. בהינתן קוד C מרחק המינג שלו מסומן <math>\ d(C)</math>.
:<math>\ d(C)= min \left\{ d ( x, y ) : x \ne y \right\}</math>.
הסימון הוא זהה ומבחינים בין השימושים השונים לפי ההקשר.
מכאן מתקבלת אפשרות להעריך קוד על פי מספר קריטריונים בסיסיים - מספר האותיות שבהן משתמשים בקוד, אורך כל מילה בקוד, מספר המילים בקוד (עושר השפה) ומרחק הקוד (היכולת לתקן שגיאות). למעט מספר האותיות בקוד, שזההקשור יותרלאמצעי ענייןהטכנולוגי שלבו טכנולוגיהמשתמשים לתקשורת (למשל, האם מעבירים מסרים בשפה [[בסיס בינארי|בינארית]] או דווקא בשפה [[טרינרי|טרינרית]]), שאר המאפיינים ניתנים לשינוי ולשליטה מסוימת על ידי יוצרי הקוד. מאפיינים אלו עומדים אחד מול השני - הגדלת המרחק של הקוד מצמצמת את מספר המילים האפשריות, ואמנם על ידי הגדלת אורך המילים בקוד ניתן להגדיל הן את המרחק והן את מספר המילים אך בכך גם מגדילים את הסרבול של הקוד ואת מספר השגיאות הממוצע שהוא סופג בעת העברתו. כאשר קובעים את אורך הקוד ואת המרחק שלו, מספר המילים האפשריות בקוד הוא מוגבל. קודים שמספר המילים בהם הוא מקסימלי, עבור אורך מילה ומרחק קוד קבועים, נקראים קודים אופטימליים, ועיקר תורת הקודים הוא בחיפוש וחקירה של קודים כאלו.
===קודים לינאריים===
* לכל מילת קוד <math>\ (a_{1}, ..., a_{n}) \isin C</math> וסימן <math>\ x\isin F</math> בא"ב, שייכת גם המילה <math>\ (xa_{1}, ..., xa_{n})</math> לקוד.
יש להעיר שעל מנת שיוגדרו פעולות הכפל והחיבור בצורה נאותה, הא"ב המגדיר את הקוד צריך להיות [[שדה סופי|שדה]], ומכך נובע שגודלו <math>\ q</math> חייב להיות חזקה של [[מספר ראשוני]] כלשהו. כאשר הא"ב בינארי (מכיל שני סימנים בלבד), למשל, מתקבל שדה עבור פעולות הכפל והחיבור הרגילות. בקודים לינאריים נהוג לציין את [[ממד (אלגברה לינארית)|ממד]] הקוד כמרחב וקטורי, ולא את מספר המילים שבקוד (שהוא q בחזקה הממד).
יתרונות הקודים הלינאריים על קודים רגילים רבים: קל לייצגם באמצעות [[בסיס (אלגברה)|בסיס]] של הקוד, וקיימות שיטות פשוטות לקידוד ופענוח קודים כאלה. (ראה בערך המורחב)
| 