קוד לינארי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

קוד לינארי הוא קוד, כלומר, אוסף של וקטורים מעל שדה סופי בן 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] לינארי מכיל \ q^k איברים, וניתן להצגה באמצעות בסיס בן \ k איברים. מטריצה אשר שורותיה הן בסיס לקוד מכונה מטריצה יוצרת של הקוד.

מאחר שלכל שתי מילות קוד שונות \ x,y מתקיים \ d(x,y)=w(x-y) (כאשר \ d מציין את מרחק המינג בין המילים, ו-w את "המשקל של המילה" - כלומר, מספר המקומות בהם היא שונה מאפס), ניתן להסיק שמרחק הקוד של קוד לינארי שווה למשקל המינימלי של מילות הקוד השונות מאפס.

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

סימון מקובל[עריכת קוד מקור | עריכה]

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

פענוח קודים לינאריים[עריכת קוד מקור | עריכה]

ראשי מחלקות[עריכת קוד מקור | עריכה]

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

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

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

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

פענוח סינדרומי[עריכת קוד מקור | עריכה]

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

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

\ xH^{T}=yH^{T} \iff (x-y)H^{T}=0 \iff x-y\isin C

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

דוגמאות לקודים לינאריים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

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