קוד ליניארי

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

הגדרה

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

תכונות

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

סימון מקובל

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

ראשי מחלקות

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