שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2015 - קידוד

נגדיר קוד זוגיות דו-מימדי "חסר פינה": עבור 9 ביטים של מידע $D_1, \ldots, D_9$, נוסיף לכל שורה ביט זוגיות ($R_1, R_2, R_3$) ולכל עמודה ביט זוגיות ($C_1, C_2, C_3$). בניגוד לקוד שנלמד בכיתה, כאן אין ביט זוגיות בפינה הימנית התחתונה. המבנה: | $D_1$ | $D_2$ | $D_3$ | $R_1$ | | $D_4$ | $D_5$ | $D_6$ | $R_2$ | | $D_7$ | $D_8$ | $D_9$ | $R_3$ | | $C_1$ | $C_2$ | $C_3$ | -- | מילת קוד מתוארת ע"י $D_1 D_2 D_3 \ldots D_9 R_1 R_2 R_3 C_1 C_2 C_3$, כלומר 15 ביטים. קוד נקרא קוד $(n,k,d)$ אם $n$ הוא מספר הביטים במילת קוד, $k$ הוא מספר ביטי המידע, ו-$d$ הוא המרחק המינימלי בין שתי מילות קוד. א. קבעו מהם $n, k, d$. לקביעת המרחק המינימלי, ניתן להסתמך על הטענה: בקוד זה יש מילת קוד שמרחקה ממילת האפס הוא $d$. הראו מילת קוד במרחק מינימלי ממילת האפס. ב. הראו מילת קוד במרחק מקסימלי ממילת האפס. ג. התשדורת הבאה התקבלה לאחר מעבר בערוץ תקשורת רועש: `0 0 0 0 0 0 0 1 0 0 0 1 0 0 0` האם היא נמצאת במרחק 1 ממילת קוד כלשהי? הוכיחו. ד. תהי $A \subseteq \{0,1\}^{15}$ קבוצת כל המילים שנמצאות במרחק הקטן או שווה ל-2 ממילת קוד כלשהי. האם הקבוצה $A$ כוללת את כל המילים ב-$\{0,1\}^{15}$? הסבירו.

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

פתרון: **א.** $n=15$, $k=9$, $d=3$. מילת קוד במרחק מינימלי ממילת האפס: נציב $D_1=1$ ושאר ביטי המידע 0. אז $R_1=1$ (זוגיות שורה ראשונה) ו-$C_1=1$ (זוגיות עמודה ראשונה). סה"כ 3 ביטים דולקים, מרחק 3 ממילת האפס. מילת הקוד: `1 0 0 0 0 0 0 0 0 1 0 0 1 0 0` לא ניתן ליצור מילת קוד חוקית עם פחות מ-3 ביטים דולקים (מלבד מילת האפס): שינוי ביט מידע אחד דורש שינוי ביט זוגיות שורה + ביט זוגיות עמודה = 3 שינויים. ושינוי של ביט זוגיות בלבד יפר את תנאי הזוגיות. **ב.** מילת קוד במרחק מקסימלי: נציב את כל 9 ביטי המידע כ-1. אז כל ביטי הזוגיות של השורות הם 1 (3 ביטים בשורה = אי-זוגי) וכל ביטי הזוגיות של העמודות הם 1 (3 ביטים בעמודה = אי-זוגי). סה"כ 15 ביטים דולקים. מילת הקוד: `1 1 1 1 1 1 1 1 1 1 1 1 1 1 1` **ג.** התשדורת: `0 0 0 0 0 0 0 1 0 0 0 1 0 0 0` כלומר $D_8=1$, $R_3=1$ ושאר הביטים 0. נבדוק: אם זו מילת קוד חוקית — שורה 3: $D_7+D_8+D_9 = 0+1+0 = 1$ (אי-זוגי), $R_3=1$ ✓. שורות 1,2: תקינות (כל 0). עמודה 2: $D_2+D_5+D_8 = 0+0+1 = 1$, $C_2=0$ ✗. לכן התשדורת אינה מילת קוד. האם במרחק 1? צריך למצוא מילת קוד שנבדלת בביט אחד. אם נשנה $C_2$ ל-1: נקבל שעמודה 2 תקינה, אבל שורה 4 (שורת העמודות) תהיה $0+1+0=1$ — אין ביט זוגיות לשורה זו ("חסר פינה") אז אין בעיה. נבדוק: $D_8=1, R_3=1, C_2=1$. שורה 3: $0+1+0=1$, $R_3=1$ ✓. עמודה 2: $0+0+1=1$, $C_2=1$ ✓. עמודות 1,3: ✓. שורות 1,2: ✓. כן, התשדורת במרחק 1 ממילת הקוד `0 0 0 0 0 0 0 1 0 0 0 1 0 1 0`. **ד.** לא. מספר מילות הקוד הוא $2^9 = 512$. כדור ברדיוס 2 סביב כל מילת קוד מכיל $\binom{15}{0} + \binom{15}{1} + \binom{15}{2} = 1 + 15 + 105 = 121$ מילים. גם אם הכדורים אינם חופפים, סה"כ $512 \times 121 = 61{,}952 < 2^{15} = 32{,}768$. למעשה $512 \times 121 = 61{,}952 > 32{,}768$, אז לפי ספירה לא ניתן לשלול. אבל ניתן להראות ישירות: ניקח את המילה שבה רק $R_1=1$ (שאר 0). זו לא מילת קוד (שורה 1 עם כל $D_i=0$ ו-$R_1=1$ מפרה זוגיות). כדי להגיע למילת קוד צריך לשנות $R_1$ (מרחק 1) או לשנות ביט מידע בשורה 1 + ביט עמודה מתאים (מרחק 2) — אבל שינוי ביט מידע + עמודה = שורה מתוקנת אך צריך גם $R_1$. למעשה $d=3$ אומר שהקוד מתקן שגיאה אחת בלבד, ומרחק 2 ממילת קוד מובטח רק אם $d \geq 5$. מכיוון ש-$d=3$, כדורים ברדיוס 2 עלולים לחפוף ויש מילים שלא מכוסות.