Ημερολόγιο μαθήματος
δηλαδή το πλήθος των συντεταγμένων στις οποίες διαφέρουν οι δύο λέξεις. Ορίσαμε επίσης την ελάχιστη απόσταση ενός κώδικα ως
Δείξαμε ότι ο κώδικας μπορεί να διορθώνει σφάλματα αν και μόνο αν . Όταν το είναι δύναμη ενός πρώτου, μπορούμε να πάρουμε για αλφάβητο το πεπερασμένο σώμα . Κάθε γραμμικός υπόχωρος του ονομάζεται γραμμικός κώδικας μήκους πάνω από το . Ορίσαμε το ρυθμό (rate) του κώδικα ως και παρατηρήσαμε ότι στην περίπτωση ενός γραμμικού κώδικα διάστασης , ο ρυθμός είναι ίσος με . Ορολογία: ένας γραμμικός κώδικας μήκους , διάστασης και με ελάχιστη απόσταση ονομάζεται -κώδικας.
Ξεκινήσαμε μία επανάληψη σε βασικές έννοιες της θεωρίας σωμάτων: είδαμε τι είναι επέκταση σωμάτων, , βαθμός της επέκτασης, , και ορίσαμε το ελάχιστο πολυώνυμο ενός αλγεβρικού στοιχείου πάνω από το . Δείξαμε ότι κάθε πεπερασμένο σώμα έχει θετική χαρακτηριστική, , περιέχει το σώμα και για κάποιο φυσικό αριθμό . Για δεδομένο ανάγωγο πολυώνυμο βαθμού , κατασκευάσαμε το σώμα , το οποίο έχει στοιχεία και περιέχει μία ρίζα, ας την ονομάσουμε , του . Το σώμα αυτό είναι το
Δείξαμε ότι η πολλαπλασιαστική ομάδα κάθε πεπερασμένου σώματος είναι κυκλική.
Διαβάστε: Κεφ. 1 και 2 από το βιβλίο [2].
Διαβάστε: Παρ. 1.1 έως 1.4 από το βιβλίο [1].
Διαβάστε: Σημείωσεις
Ορίσαμε την έννοια του βάρους Hamming μίας λέξης ως το πλήθος των μη μηδενικών συντεταγμένων της:
Είδαμε ότι το βάρος Hamming είναι νόρμα στο χώρο και η αντίστοιχη μετρική είναι η απόσταση Hamming. Το ελάχιστο βάρος και η ελάχιστη απόσταση ενός κώδικα ορίζονται ως:
και
αντίστοιχα. Όταν ο είναι γραμμικός κώδικας, τότε .
Στο χώρο ορίσαμε το Ευκλείδειο εσωτερικό γινόμενο
Ο δϋικός χώρος του ορίζεται ως
Αν και, γενικά, οι χώροι και μπορεί να έχουν μη τετριμμένη τομή, ισχύουν τα παρακάτω:
,
.
Πίνακας βάσης (generator matrix) ενός -γραμμικού κώδικα είναι ένας πίνακας του οποίου οι γραμμές είναι βάση του .
Πίνακας ελέγχου (parity check matrix) ενός -γραμμικού κώδικα είναι ένας πίνακας του οποίου οι γραμμές είναι βάση του .
Δείξαμε ότι ένας γραμμικός κώδικας με πίνακα ελέγχου έχει ελάχιστη απόσταση αν και μόνο αν κάθε στήλες του είναι γραμμικώς ανεξάρτητες και υπάρχουν γραμμικώς εξαρτημένες στήλες του .
Είδαμε τη μέθοδο αποκωδικοποίησης με σύνδρομα.
Διαβάστε: Παρ. 2.1 έως και 2.3 από το βιβλίο [1].
Διαβάστε: Παρ. 4.1 έως και 4.4 από το βιβλίο [2].
Διαβάστε: Παρ. 4.5 έως 4.8 από το βιβλίο [2].
Ασκήσεις: Φυλλάδιο 0
Ασκήσεις: Φυλλάδιο 1 (Ημ. παράδοσης 9/10/2024)
όπου είναι ο όγκος (πλήθος σημείων) της μπάλας ακτίνας στο χώρο . Κάθε κώδικας που "πιάνει" το άνω φράγμα ονομάζεται τέλειος (perfect).
Ορίσαμε τους δυαδικούς κώδικες Hamming, , για , δείξαμε ότι έχουν παραμέτρους και συνεπώς είναι τέλειος. Είδαμε την αποκωδικοποίηση τους με σύνδρομα (και πώς δεν είναι απαραίτητο να καταγράψουμε τον πίνακα με τα σύνδρομα). Ορίσαμε τους κώδικες Hamming, , πάνω από το και δείξαμε ότι έχουν παραμέτρους , άρα είναι τέλειοι.
Είδαμε το Sphere Covering bound και το φράγμα των Gilbert-Varshamov.
Δείξαμε ότι κάθε κώδικας πάνω από ένα αλφάβητο με σύμβολα και παραμέτρους ικανοποιεί . Αυτό είναι το φράγμα του Singleton. Για γραμμικούς κώδικες με παραμέτρους το φράγμα γίνεται . Κάθε κώδικας ο οποίος έχει ελάχιστη απόσταση που "πιάνει" το φράγμα με ισότητα ονομάζεται MDS (Maximum Distance Separable).
Ορίσαμε τους γενικευμένους κώδικες Reed-Solomon, όπου , και τα είναι διακεκριμένα στοιχεία του , ως την εικόνα της γραμμικής απεικόνισης
και δείξαμε ότι έχουν παραμέτρους , δηλαδή είναι MDS.
Διαβάστε: Παρ. 5.2, 5.3.1 από το βιβλίο [2].
Διαβάστε: Παρ. 5.3.2, 5.4 από το βιβλίο [2].
Διαβάστε: Παρ. 5.2 από το βιβλίο [1].
Ασκήσεις: 2o Φυλλάδιο (Ημ. παράδοσης 21/10/2024)
είναι υπόχωρος του με διάσταση .
Αν , τότε , για και δείξαμε ότι για ισχύει
Για παίρνουμε , άρα . Εφαρμόζοντας το φράγμα αυτό στο δυϊκό κώδικα , ο οποίος είναι επίσης MDS, παίρνουμε .
Δείξαμε τα φράγματα του Plotkin και του Griesmer.
Διαβάστε: Σελ. 101-102 από το βιβλίο [4].
Διαβάστε: Παρ. 5.5 και 5.7 από το βιβλίο [2].
Ορίσαμε τους (γενικούς) κώδικες Reed-Muller ως κώδικες αποτίμησης πολυωνύμων. Ειδικότερα, ορίσαμε τους κώδικες ως την εικόνα της γραμμικής απεικόνισης
Είδαμε την κατασκευή της συνένωσης κωδίκων (concatenated codes).
Διαβάστε: Παρ. 6.1, 6.2 από το βιβλίο [2].
Διαβάστε: Παρ. 9.1 9.2, 9.3 από το βιβλίο [1].
Διαβάστε: Παρ. 6.3 (έως σελ. 123) από το βιβλίο [2].
Ασκήσεις: 3o Φυλλάδιο (Ημ. παράδοσης 4/11/2024)
όπου είναι ο χώρος των πολυωνύμων βαθμού πανω από το .
Έχουμε ήδη δει ότι ο είναι MDS και ότι ο δυϊκός κάθε MDS κώδικα είναι επίσης MDS. Δείξαμε ότι για τους GRS ισχύει κάτι περισσότερο: ο δυϊκός είναι επίσης GRS. Ειδικότερα, δείξαμε ότι , όπου το διάνυσμα μπορεί εύκολα να υπολογιστεί ως η βάση του μηδενόχωρου ενός πίνακα βάσης του . Αρχίσαμε να μελατάμε την αποκωδικοποίηση των GRS.
Διαβάστε: Παρ. 9.1 από το βιβλίο [2].
Είδαμε το σχήμα διαμοιρασμού μυστικών του Shamir (secret sharing scheme) και πώς αυτό μπορεί να διατυπωθεί ως πρόβλημα ereasure decoding κωδίκων Reed-Solomon.
Διαβάστε: Παρ. 6.1, 6.2, 6.3 από το βιβλίο [3].
Ασκήσεις: 4ο Φυλλάδιο (Ημ. παράδοσης 18/11/2024)
Διαβάστε: Παρ. 6.4 από το βιβλίο [3].