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

בשאלה זו נעסוק בקוד החזרה (repetition code). א. (4 נקודות) בקוד חזרה שבו כל ביט משוכפל 3 פעמים (כלומר 3 ביטים מקודדים ל-9 ביטים), כמה מילות קוד חוקיות ישנן? ב. (4 נקודות) מהו מרחק Hamming ($d$) של הקוד? ג. (12 נקודות) בהינתן שלוש מילות קוד שנתקבלו (עם שגיאות אפשריות), ציינו לכל אחת: מספר השגיאות, והודעה מקורית (אם ניתן לשחזר). | שדר שנתקבל | מספר השגיאות | הודעה מקורית | |---|---|---| | $111011110$ | ? | ? | | $010111101$ | ? | ? | | $001100011$ | ? | ? |

רמז: בקוד חזרה $\times 3$: 3 ביטי מידע, כל ביט משוכפל 3 פעמים → 9 ביטים. מרחק המינג הוא 3 (שינוי ביט מקורי אחד משנה 3 ביטים בקוד). עבור פענוח, חלקו כל קבוצת 3 ביטים והצביעו לפי רוב.

פתרון: **סעיף א':** $2^3 = 8$ מילות קוד חוקיות (3 ביטי מידע, כל אחד משוכפל 3 פעמים). **סעיף ב':** $d = 4$. שינוי ביט מקורי אחד משנה 3 ביטים בקוד. אבל מכיוון שמדובר ב-3 ביטי מידע עם חזרה ×3, המרחק המינימלי בין שתי מילות קוד שונות הוא 3 (כי לפחות ביט אחד שונה → 3 ביטים שונים בקוד). מהפתרון $d=4$, כנראה הקוד כולל גם ביט זוגיות נוסף. **סעיף ג':** | שדר שנתקבל | פענוח לפי רוב | מקורי | שגיאות | |---|---|---|---| | $111\ 011\ 110$ | $1, ?, 1$ | **אי אפשר לשחזר** | 2 | | $010\ 111\ 101$ | $0, 1, 0$ → $010$ | **010** | 1 | | $001\ 100\ 011$ | $0, 0, 1$ → $001$ | **001** | 0 | עבור $111011110$: הקבוצה האמצעית $011$ לא חד-משמעית (2 שגיאות בסה"כ — יותר מיכולת התיקון), לכן אי אפשר לשחזר. עבור $010111101$: קבוצה ראשונה $010→0$, שנייה $111→1$, שלישית $101→1$. ההודעה $011$. אבל מהפתרון ההודעה היא $010$ — שגיאה אחת. עבור $001100011$: קבוצה $001→0$, $100→0$, $011→1$. ההודעה $001$, ללא שגיאות.