הרצאה 1 - 21.10.15

• מנהלות
• מוטיבציה לעיסוק בקודים לתיקון שגיאה
• משפט שאנון לגבי המקרה חסר הרעש, כלומר דחיסה
• הוכחה בעזרת עצי האופמן
• משפט שאנון לגבי המקרה המורעש - BSCp
• הוכחה בשיטה הסתברותית

הרצאה 2 - 28.10.15

• המינג
• הקודים עם d=1,d=2
• קודים לינאריים, מטריצות יוצרות וParity Check Matrix
• בנייה של הקוד עם d=3 בעזרת הקשר בין d ל PCM
• חסם הכדורים של המינג
• חסם הסינגלטון
• הוכחה שאי אפשר להשיג את חסם הסינגלטון מעל השדה בן 2 האיברים
• תזכורת: שדות, מציין של שדה, ...

הרצאה 3 - 4.11.15

• קודי ריד סולומון
• דוגמת שימוש לריד סולומון
• קודי ריד מולר מעל שדה כללי - אם l<q ואם l>q.
• קודי ריד מולר עבור השדה בן 2 האיברים
• קודי הדמרד
• משפט (חסם) גילברט ורשנוב
• הוכחה של גילברט
• הוכחה של ורשמוב
• דיאגרמה (אנחנו בקורס שימושי, אחרי הכל)

הרצאה 4 - 11.11.15

• הבנייה של ווזנקראפט
• פעולות על קודים:
• הוספת ביט זוגיות
• ניקוב, כל קוד מתקבל מניקוב קוד הדמרד
• מכפלת קודים (direct product)
• הרכבת קודים (concatenation) , דוגמאות להרכבות שימושיות

הרצאה 4.5 - 25.11.15
הייתה טעות באינדקסציה של השיעורים.
הוספתי את השיעור החסר כאן, בתור שיעור 4.5. סליחה על אי הנוחות.

• תיקון טעויות ומחיקות בקודי ריד-סולומון
• הכללה של האלגוריתם עבור קודים שאינם בהכרח ריד סולומון

הרצאה 5 - 2.12.15

• קוד ריד-סלומון המורכב
• פענוח הקוד
• פענוח שמחזיר רשימה

סיכום הרצאה 5

• אלגוריתמים הקשורים לפענוח שמחזיר רשימה
• חסמים נוספים על קודים:
• חסם פלוטקין ומסקנות
• חסם ג'ונסון

• רדוקציה מקושי ב-worst case לקושי ממוצע (worst case to average case reduction)
• תיקון מקומי של קוד אדמר
• תיקון מקומי של קוד ריד-מולר מאחוז טעויות קטן
• תיקון מקומי של קוד ריד-מוךר מאחוז קבוע של טעויות
• תיאור אלגוריתם לפענוח רשימה מקומי (local list-decoding) לקודי ריד-מולר

• אלגוריתם לפענוח רשימה מקומי (local list-decoding) לקודי ריד-מולר
• חזרה על הוכחת חסם גונסון והוכחת חסם Elias-Bassalygo

• גרפים דו-צדדיים מרחיבים
• קשר בין מטריצת בדיקת זוגיות דלילה לגרפים דו״צ עם דרגות חסומות
• אלגוריתם שרץ בזמן ליניארי לתיקון אחוז קבוע של טעויות בקוד שגרף בדיקת הזוגיות שלו הוא מרחיב ומדרגה חסומה
• כיצד לתקן יותר טעויות ע״י אלגוריתם belief propagation

• קודים עם זמן לינארי של קידוד ופענוח

• סיבוכיות של קוד לינארי
• פרוטוקול קריפטוגרפי שמשתמש בקושי של פענוח קוד לינארי
• חלוקת סוד