קוד ליניארי

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

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

הגדרה

קוד ליניארי מאורך $n$, ומימד $k$ הוא תת-מרחב מממד $k$ של המרחב הווקטורי $\mathbb {F} _{q}^{n}$, כאשר $\mathbb {F} _{q}$ הוא השדה הסופי בן $q$ האיברים. קוד כזה מכונה גם קוד $\ [n,k]$ $q$-ארי, (עבור $q=2$, מכונה הקוד מכונה קוד בינארי, ועבור $q=3$, טרנארי) או במקרה שיש עניין לציין את מרחק הקוד $d$, קוד $[n,k,d]$.

תכונות

קוד $[n,k]$ ליניארי $C$ מכיל $q^{k}$ איברים, וניתן להצגה באמצעות בסיס בן $k$ איברים. מטריצה אשר שורותיה הן בסיס לקוד מכונה מטריצה יוצרת של הקוד.

לכל שתי מילות קוד שונות $\mathbf {x} ,\mathbf {y}$ מגדירים $\mathrm {d} (\mathbf {x} ,\mathbf {y} )=\mathrm {w} (\mathbf {x} -\mathbf {y} )$ (כאשר $\mathrm {d} (\cdot ,\cdot )$ מציין את מרחק המינג בין המילים, ו-$\mathrm {w} (\cdot )$ את משקל המילה - כלומר, מספר המקומות בהם היא שונה מאפס), ומרחק הקוד מוגדר להיות $d=\min _{\scriptstyle \mathbf {x} ,\mathbf {y} \in C \atop \scriptstyle \mathbf {x} \neq \mathbf {y} }\mathrm {d} (x,y)$. מכך ניתן להסיק שמרחק הקוד של קוד ליניארי שווה למשקל המינימלי של מילות הקוד השונות מאפס: $d=\min _{\mathbf {x} \in C\setminus \{\mathbf {0} \}}\mathrm {w} (\mathbf {x} )$.

ככל מרחב ליניארי, גם לקוד $C$ קיים משלים אורתוגונלי, המהווה גם קוד ליניארי, מסומן $C^{\perp }$ ונקרא הקוד הדואלי של $C$. בהינתן מטריצה יוצרת $G$ של $C$, מתקיים

$C^{\perp }=\left\{\mathbf {x} \in F^{n}:\forall \mathbf {c} \in C\;\mathbf {x} \mathbf {c} ^{\mathrm {T} }=0\right\}=\left\{\mathbf {x} \in F^{n}:\mathbf {x} G^{\mathrm {T} }=0\right\}$.

מטריצה יוצרת של קוד זה מכונה מטריצת בדיקת זוגיות של $C$, ומקיימת $GH^{T}=0$ כאשר $G$ היא מטריצה יוצרת של $C$, ו-$H$ היא מטריצת בדיקת זוגיות שלו. מכאן מקבלים כי

$\mathbf {c} \in C\iff H\mathbf {c} ^{\mathrm {T} }=\mathbf {0}$.

בשיטת הפענוח הסינדרומי נעשה שימוש במטריצה זו לפענוח $C$.

סימון מקובל

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

פענוח קודים ליניאריים

ראשי מחלקות

בהינתן קוד $[n,k]$ ליניארי $\ C$, ניתן לחלק את המרחב $\mathbb {F} _{q}^{n}$ למחלקות מהצורה $\mathbf {a} +C$ לכל $\mathbf {a} \in \mathbb {F} _{q}^{n}$. כלומר, לאוספי כל הווקטורים המתקבלים מהוספת וקטור כלשהו (לאו דווקא מילת קוד) לכל איברי $C$. המחלקות המתקבלות על ידי $C$ שוות כולן בגודלן לגודלו של $C$, דהיינו מכילות $q^{k}$ איברים כל אחת.

למחלקות הללו קיימים נציגים רבים. למעשה, כזכור מתורת החבורות, קיים שוויון $\mathbf {a} +C=\mathbf {b} +C$ בין שתי מחלקות אם ורק אם $\mathbf {a} -\mathbf {b} \in C$. על כן, שני וקטורים $\mathbf {a} ,\mathbf {b}$ שייכים לאותה המחלקה אם ורק אם ההפרש ביניהם הוא מילת קוד. לכן, כל אחד מאיברי מחלקה יכול לשמש נציג שלה. עם זאת, נבחר לכל מחלקה כנציג וקטור בעל משקל מינימלי במחלקה. את הנציגים שהתקבלו באופן זה נכנה ראשי המחלקות של $C$.

פענוח באמצעות ראשי מחלקות מתבסס על האבחנה שאם נשלחה מילת קוד $\mathbf {x}$ והתקבלה תחתיה מילה $\mathbf {y}$, וקטור השגיאה $\mathbf {v} =\mathbf {x} -\mathbf {y}$ (במקרה הבינארי, למשל, מדובר בווקטור אשר מכיל 1 במקומות בהם התקבלו השגיאות בתקשורת) שייך לאותה המחלקה לה שייכת המילה $\mathbf {y}$. משקל וקטור השגיאה שווה למספר השגיאות שהתקבלו בתקשורת. לכן, אם אנחנו מעוניינים בתיקון שגיאות לפי שיטת השכן הקרוב ביותר, יהיה עלינו להניח וקטור שגיאה ממשקל מינימלי, ולכן שווקטור השגיאה הוא אחד מראשי המחלקה לה שייך $\mathbf {y}$. לאחר שקבענו את וקטור השגיאה $\mathbf {v}$, הפענוח יתרחש באמצעות הוספת וקטור השגיאה המשוער $\mathbf {v}$ לווקטור שהתקבל $\mathbf {y}$, ותתקבל באופן זה מילת הקוד המקורית.

ניתן להעיר ששיטה זו אינה חד משמעית תמיד, ובקוד בעל מרחק קוד של $d=2t$, תיתכן מחלקה אשר תכיל שני ראשי מחלקות אפשריים בעלי משקל $t$, אשר הבחירה ביניהם תעשה שרירותית. ביישומים בהם לא מעוניינים בבחירה שרירותית, ניתן להשתמש בשיטת פענוח לא שלם לפיה מבוצע פענוח אך ורק כאשר משקל ראש המחלקה שנמצא קטן מ-$t$.

פענוח סינדרומי

קושי אחד נותר בשיטה שתוארה לעיל - בהתקבל מילה $\mathbf {y}$, כיצד ניתן למצוא את ראש המחלקה לה היא שייכת בצורה יעילה? חיפוש סדרתי בין כל המילים האפשריות ידרוש זמן מעריכי באורך $\mathbf {y}$, ולכן אינו סביר.

שימוש במטריצת בדיקת הזוגיות $H$ של הקוד פותר בעיה זו. ראשית, נגדיר את $\mathbf {y} H^{T}$ כסינדרום של $\mathbf {y}$. השיטה המכונה פענוח סינדרומי מתבססת על כך שלשתי מילים קיים אותו סינדרום אם ורק אם הן שייכות לאותה המחלקה:

$\mathbf {x} H^{T}=\mathbf {y} H^{T}\iff (\mathbf {x} -\mathbf {y} )H^{T}=0\iff \mathbf {x} -\mathbf {y} \in C$

לכן, באמצעות שמירת רשימה של ראשי מחלקות והסינדרומים המתאימים להן, ניתן למצוא את ראש המחלקה המתאים לכל מילה $\mathbf {y}$ באמצעות חישוב הסינדרום המתאים לה, ומציאתו ברשימת הסינדרומים.

דוגמאות לקודים ליניאריים

מספר דוגמאות בולטות לקודים ליניאריים הן:

• קוד החזרה מאורך נתון (קוד המכיל רצפי אפסים ואחדים מאורך נתון המסמנים שני מסרים בלבד)
• סיבית זוגיות (קוד כל המילים ממשקל זוגי)
• בדיקת יתירות מחזורית (CRC)
• קודי המינג
• קודי גולֶה (Golay) - הבינארי והטרנארי
• קוד ריד-סולומון
• קודי BCH
• קודי ריד-מולר
• קודי גופה
• קוד פולינומי

ראו גם

• קוד מעגלי - קוד אשר נוסף על היותו ליניארי, סגור גם תחת הזזה מעגלית של מילות הקוד.

קישורים חיצוניים

• קוד ליניארי, באתר MathWorld (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33141383קוד ליניארי