 שנה"ל תשע"ז | |||||||||||||||||||||||||
 |
 |
||||||||||||||||||||||||
|
מבוא לקודים לתיקון שגיאות
Introduction to Error Correction Codes |
0512-4163-01 | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| הנדסה | תואר ראשון - חשמל ואלקטרוניקה | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
ש"ס: 4.0
סילבוס מקוצר
שעות: 4 ש"ס
משקל: 3.5
דרישות קדם: תקשורת ספרתית (במקביל)
צופני בלוק, לינאריות, מטריצה יוצרת, מטריצת בדיקה. פענוח שגיאות ומחיקות. חסם Hamming, חסם Singleton, רדיוס כסוי, צופני Reed-Muller, חסם Griesmer, צופן Hamming. שקילות מונומית. צופן מכפלה, משקלי Hamming מוכללים. חסם Singleton מעל אלפבית כללי, צופני MDS, שקילות. צופן ציקלי, שזור צופנים, המפענח של Meggitt ומלכוד שגיאות. פעולות חשוב בשדות סופיים. צופני BCH, צופני Reed-Solomon, שרשור צופנים, חסם BCH, פולינום מיקום השגיאה ומפענח PGZ, פענוח מהיר של BCH.
Course description
Credit Points: 3.5
Prerequisites: Digital Communications (Concurrent)
Block codes, linearity, generator matrix, check matrix. Errors and erasures decoding. Hamming bound, Singleton bound, covering radius, Reed-Muller codes, Griesmer bound, Hamming codes. Monomial equivalence. Product codes, generalized Hamming weight. Singleton bound over a general alphabet, MDS codes, equivalence. Cyclic codes, interleaved codes, the Meggitt decoder and error trapping. Computation in finite fields. BCH codes, Reed-Solomon codes, concatenation, BCH boud, error location polynomial and the PGZ decoder, fast decoders for BCH codes.
Week 1: Model of communication system. Models of errors. Codes. Encoding and decoding. Hamming distance. Minimum distance of codes. Maximum likelihood and minimum distance decoding. Error-correcting capability.
Week 2: Hamming bound on the minimum distance. Perfect codes. Linear codes. Generator matrix. Parity-check matrix. Finding the minimum distance from parity-check matrix.
Week 3: Standard array. Cosets. Syndrome decoding.
Week 4: Repetition codes. Parity-check codes. Hamming codes. Simplex codes. Reed-Muller codes. Golay codes. Operations on codes – shortening, lengthening, puncturing. Bounds on codes’ parameters (Plotkin bound, Singleton bound, Griesmer bound).
Week 5: Dual codes. Distance distributions. The Mac-Williams threorem. Computation of decoding and detection error probabilities.
Week 6: Cyclic codes. Generator polynomial. Check polynomial. Encoding using registers with feedback. Meggit’s decoder.
Week 7: Introduction to groups and finite fields. Implementation of operations in fields.
Week 8: Hamming codes in the cyclic form. Two-error correcting BCH codes.
Week 9: BCH and Reed-Solomon codes.
Week 10: Decoding BCH codes using Peterson-Gorenstein-Zierler algorithm.
Week 11: Decoding BCH codes using Berlekamp-Welch algorithm.
Week 12: Decoding Reed-Solomon codes.
Week 13: Product codes. Concatenated codes. Reed-Muller codes.
Week 14: Low-density parity check codes.