Ημερολόγιο μαθήματος
Ένας κώδικας μήκους \(n\newcommand{\wt}{\mathrm{wt}} \newcommand{\an}[1]{\langle #1 \rangle}\) πάνω από ένα αλφάβητο \(\Sigma\) με \(q\) σύμβολα είναι ένα υπόσύνολο \(C\subseteq \Sigma^n\). Ορίσαμε την απόσταση Hamming δύο λέξεων \(x=(x_1,\ldots, x_n), y=(y_1,\ldots, y_n)\) ως \[ \Delta(x,y) = |\{1\leq i\leq n : x_i \neq y_i\}|, \] δηλαδή το πλήθος των συντεταγμένων στις οποίες διαφέρουν οι δύο λέξεις. Ορίσαμε επίσης την ελάχιστη απόσταση \(d\) ενός κώδικα ως \[ d = \min\{\Delta(x,y) : x,y\in C, x\neq y\}.\] Δείξαμε ότι ο κώδικας μπορεί να διορθώνει \(t\) σφάλματα αν και μόνο αν \(t\leq \lfloor \tfrac{d-1}{2}\rfloor\). Όταν το \(q\) είναι δύναμη ενός πρώτου, μπορούμε να2 πάρουμε για αλφάβητο το πεπερασμένο σώμα \(\mathbb{F}_{q}\). Κάθε γραμμικός υπόχωρος του \(\mathbb{F}_{q}^n\) ονομάζεται γραμμικός κώδικας μήκους \(n\) πάνω από το \(\mathbb{F}_{q}\). Ορίσαμε το ρυθμό (rate) του κώδικα ως \(\frac{\log_q(|C|)}{n}\) και παρατηρήσαμε ότι στην περίπτωση ενός γραμμικού κώδικα διάστασης \(k\), ο ρυθμός είναι ίσος με \(\frac{k}{n}\). Ορολογία: ένας γραμμικός κώδικας μήκους \(n\), διάστασης \(k\) και με ελάχιστη απόσταση \(d\) ονομάζεται \([n,k,d]\)-κώδικας.
Ξεκινήσαμε μία επανάληψη σε βασικές έννοιες της θεωρίας σωμάτων: είδαμε τι είναι επέκταση σωμάτων, \(K/F\), βαθμός της επέκτασης, \([K:F]\), και ορίσαμε το ελάχιστο πολυώνυμο ενός αλγεβρικού στοιχείου \(\alpha\in K\) πάνω από το \(F\). Δείξαμε ότι κάθε πεπερασμένο σώμα \(\mathbb{F}\) έχει θετική χαρακτηριστική, \(p\), περιέχει το σώμα \(\mathbb{F}_{p} = \mathbb{Z}/\langle p\rangle\) και \(|\mathbb{F}|=p^n\) για κάποιο φυσικό αριθμό \(n\). Για δεδομένο ανάγωγο πολυώνυμο \(f\in \mathbb{F}_{p}[X]\) βαθμού \(n\), κατασκευάσαμε το σώμα \(\mathbb{F}_{p}[X]/\langle f\rangle\), το οποίο έχει \(p^n\) στοιχεία και περιέχει μία ρίζα, ας την ονομάσουμε \(\alpha\), του \(f\). Το σώμα αυτό είναι το \[\mathbb{F}_{p}(\alpha) = \{c_0+c_1\alpha+\cdots + c_{n-1}\alpha^{n-1} : c_0,c_1,\ldots, c_{n-1}\in \mathbb{F}_{p}\}.\] Δείξαμε ότι η πολλαπλασιαστική ομάδα \(\mathbb{F}^*\) κάθε πεπερασμένου σώματος είναι κυκλική.
Διαβάστε: Κεφ. 1 και 2 από το βιβλίο [2].Διαβάστε: Παρ. 1.1 έως 1.4 από το βιβλίο [1].
Διαβάστε: Σημείωσεις
Αποδείξαμε ότι για κάθε πρώτο \(p\) και κάθε φυσικό αριθμό \(n\) υπάρχει ακριβώς ένα σώμα με \(p^n\) στοιχεία εντός μίας αλγεβρικής θήκης του \(\mathbb{F}_{p}\).
Ορίσαμε την έννοια του βάρους Hamming μίας λέξης \((x_1,\ldots, x_n)\in \mathbb{F}_{q}^n\) ως το πλήθος των μη μηδενικών συντεταγμένων της: \[ \wt(x_1,\ldots, x_n) = |\{1\leq i\leq n : x_i \neq 0\}|. \]
Είδαμε ότι το βάρος Hamming είναι νόρμα στο χώρο \(\mathbb{F}_{q}^n\) και η αντίστοιχη μετρική \(\Delta(x, y) = \wt(x-y)\) είναι η απόσταση Hamming. Το ελάχιστο βάρος και η ελάχιστη απόσταση ενός κώδικα ορίζονται ως: \[ \wt(C) = \min\{\wt(c) : c\in C, c\neq 0\} \] και \[ \Delta(C) = \min\{\Delta(x,y) : x,y\in C, x\neq y\}\] αντίστοιχα. Όταν ο \(C\) είναι γραμμικός κώδικας, τότε \(\wt(C) = \Delta(C)\).
Στο χώρο \(\mathbb{F}_{q}^n\) ορίσαμε το Ευκλείδειο εσωτερικό γινόμενο
\[ \an{\cdot, \cdot} : \mathbb{F}_{q}^n\times \mathbb{F}_{q}^n \longrightarrow \mathbb{F}_{q},\ \ \an{(x_1,\ldots,x_n), (y_1,\ldots, y_n)} = x_1y_1+\cdots + x_n y_n \]
Ο δϋικός χώρος του \(C\) ορίζεται ως \[ C^{\perp} = \{ u\in \mathbb{F}_{q}^n : \forall c\in C, \an{c,u} = 0\}.\] Αν και, γενικά, οι χώροι \(C\) και \(C^{\perp}\) μπορεί να έχουν μη τετριμμένη τομή, ισχύουν τα παρακάτω:
- \(\dim C + \dim C^{\perp} = n\),
- \((C^{\perp})^{\perp} = C\).
Πίνακας βάσης (generator matrix) ενός \([n,k]\)-γραμμικού κώδικα \(C\) είναι ένας πίνακας \(G\in \mathbb{F}_{q}^{k\times n}\) του οποίου οι γραμμές είναι βάση του \(C\).
Πίνακας ελέγχου (parity check matrix) ενός \([n,k]\)-γραμμικού κώδικα \(C\) είναι ένας πίνακας \(H\in \mathbb{F}_{q}^{(n-k)\times n}\) του οποίου οι γραμμές είναι βάση του \(C^{\perp}\).
Δείξαμε ότι ένας γραμμικός κώδικας \(C\) με πίνακα ελέγχου \(H\) έχει ελάχιστη απόσταση \(d\) αν και μόνο αν κάθε \(d-1\) στήλες του \(H\) είναι γραμμικώς ανεξάρτητες και υπάρχουν \(d\) γραμμικώς εξαρτημένες στήλες του \(H\).
Είδαμε τη μέθοδο αποκωδικοποίησης με σύνδρομα.
Διαβάστε: Παρ. 2.1 έως και 2.3 από το βιβλίο [1].Διαβάστε: Παρ. 4.1 έως και 4.4 από το βιβλίο [2].
Διαβάστε: Παρ. 4.5 έως 4.8 από το βιβλίο [2].
Ασκήσεις: 0o Φυλλάδιο
Ασκήσεις: 1o Φυλλάδιο (Ημ. παράδοσης 9/10/2024)
Δείξαμε το φράγμα του Hamming ή αλλιώς Sphere Packing bound. Ειδικότερα, κάθε κώδικας με παραμέτρους \((n, M, d)\) πάνω από ένα αλφάβητο με \(q\) σύμβολα ικανοποιεί \[ M \leq q^n / V_q^n(\lfloor \tfrac{d-1}{2}\rfloor), \] όπου \(V_q^n(\rho) = \sum_{i=0}^{\rho}\binom{n}{i} (q-1)^i\) είναι ο όγκος (πλήθος σημείων) της μπάλας ακτίνας \(\rho\) στο χώρο \(\mathbb{F}_{q}^n\). Κάθε κώδικας που "πιάνει" το άνω φράγμα ονομάζεται τέλειος (perfect).
Ορίσαμε τους δυαδικούς κώδικες Hamming, \(\mathrm{Ham}(r, 2)\), για \(r\geq 2\), δείξαμε ότι έχουν παραμέτρους \([2^r-1, 2^r-1-r, 3]\) και συνεπώς είναι τέλειος. Είδαμε την αποκωδικοποίηση τους με σύνδρομα (και πώς δεν είναι απαραίτητο να καταγράψουμε τον πίνακα με τα σύνδρομα). Ορίσαμε τους κώδικες Hamming, \(\mathrm{Ham}(r, q)\), πάνω από το \(\mathbb{F}_{q}\) και δείξαμε ότι έχουν παραμέτρους \([\tfrac{q^n-1}{q-1}, \tfrac{q^n-1}{q-1}-r, 3]\), άρα είναι τέλειοι.
Είδαμε το Sphere Covering bound και το φράγμα των Gilbert-Varshamov.
Δείξαμε ότι κάθε κώδικας πάνω από ένα αλφάβητο με \(q\) σύμβολα και παραμέτρους \((n, M, d)\) ικανοποιεί \(M\leq q^{n-d+1}\). Αυτό είναι το φράγμα του Singleton. Για γραμμικούς κώδικες με παραμέτρους \([n,k,d]\) το φράγμα γίνεται \(d \leq n-k+1\). Κάθε κώδικας ο οποίος έχει ελάχιστη απόσταση που "πιάνει" το φράγμα με ισότητα ονομάζεται MDS (Maximum Distance Separable).
Ορίσαμε τους γενικευμένους κώδικες Reed-Solomon, \(\mathrm{GRS}_k({\mathbf{a}})\) όπου \({\mathbf{a}} = (a_1,\ldots, a_n)\), και τα \(a_i\) είναι διακεκριμένα στοιχεία του \(\mathbb{F}_{q}\), ως την εικόνα της γραμμικής απεικόνισης
\[ \mathrm{ev} : \mathbb{F}_{q}[X]_{< k} \longrightarrow \mathbb{F}_{q}^n,\ \ \ f \mapsto (f(a_1),\ldots, f(a_n)) \\ \]
και δείξαμε ότι έχουν παραμέτρους \([n, k, n-k+1]\), δηλαδή είναι MDS.
Διαβάστε: Παρ. 5.2, 5.3.1 από το βιβλίο [2].Διαβάστε: Παρ. 5.3.2, 5.4 από το βιβλίο [2].
Διαβάστε: Παρ. 5.2 από το βιβλίο [1].
Ασκήσεις: 2o Φυλλάδιο (Ημ. παράδοσης 21/10/2024)
Μελετήσαμε του MDS κώδικες. Ειδικότερα, δείξαμε ότι αν \(C\) είναι ένας κώδικας με παραμέτρους \([n, k, n-k+1]\) πάνω από το \(\mathbb{F}_{q}\) και επιλέξουμε ένα υποσύνολο \(S\subseteq \{1,\ldots, n\}\) με \(|S|=d'\geq d = n-k+1\), τότε το σύνολο \[ C_{S} = \{(c_1,\ldots,c_n)\in C : \forall i\not\in S\ \ c_i = 0\} \] είναι υπόχωρος του \(C\) με διάσταση \(d'-d+1\).
Αν \(A_i = |\{c\in C : \wt(c) = i\}|\), τότε \(A_0 = 1\), \(A_i = 0\) για \(1\leq i\leq d-1\) και δείξαμε ότι για \(d\leq i \leq n\) ισχύει \[ A_i = \binom{n}{i}(q-1) \sum_{j=0}^{i-d}(-1)^j \binom{i-1}{j} q^{i-j-d}.\] Για \(i=d+1\) παίρνουμε \(A_{d+1} = \binom{n}{d+1}(q-1)(q-d) \geq 0\), άρα \(q\geq d = n-k+1\). Εφαρμόζοντας το φράγμα αυτό στο δυϊκό κώδικα \(C^{\perp}\), ο οποίος είναι επίσης MDS, παίρνουμε \(q\geq k+1\).
Δείξαμε τα φράγματα του Plotkin και του Griesmer.
Διαβάστε: Σελ. 101-102 από το βιβλίο [4].Διαβάστε: Παρ. 5.5 και 5.7 από το βιβλίο [2].
Είδαμε κάποιες βασικές κατασκευές νέων κωδίκων από δεδομένους κώδικες. Είδαμε την κατασκευή του ευθέως αθροίσματος και την κατασκευή \((u, u+v)\). Ως ειδική περίπτωση της τελευταίας κατασκευής, είδαμε την κατασκευή των κωδίκων Reed-Muller πρώτης τάξης πάνω από το \(\mathbb{F}_{2}\) και υπολογίσαμε τις παραμέτρους τους.
Ορίσαμε τους (γενικούς) κώδικες Reed-Muller ως κώδικες αποτίμησης πολυωνύμων. Ειδικότερα, ορίσαμε τους κώδικες \(\mathrm{RM}(q,m,r)\) ως την εικόνα της γραμμικής απεικόνισης \[ \begin{eqnarray*} \mathrm{ev} : \mathbb{F}_{q}[X_1,\ldots, X_m]_{\leq r} &\longrightarrow& \mathbb{F}_{q}^{q^m} \\ f(X_1,\ldots,X_m) &\mapsto& (f(t_1),\ldots, f(t_{q^m})) \end{eqnarray*} \] όπου \(t_1,\ldots, t_{q^m}\) είναι τα σημεία του \(\mathbb{F}_{q}^m\). Μελετήσαμε τη διάσταση και την ελάχιστη απόσταση τους.
Είδαμε την κατασκευή της συνένωσης κωδίκων (concatenated codes).
Διαβάστε: Παρ. 6.1, 6.2 από το βιβλίο [2].Διαβάστε: Παρ. 9.1 9.2, 9.3 από το βιβλίο [1].
Διαβάστε: Παρ. 6.3 (έως σελ. 123) από το βιβλίο [2].
Ασκήσεις: 3o Φυλλάδιο (Ημ. παράδοσης 4/11/2024)
Αρχίσαμε τη συστηματική μελέτη των Γενικευμένων Κωδίκων Reed-Solomon (GRS). Για να ορίσουμε ένα (γενικευμένο) κώωδικα Reed-Solomon πάνω από το σώμα \(\mathbb{F}_{q}\) μήκους \(n\) και διάστασης \(k\), χρειαζόμαστε ένα διάνυσμα \(\alpha = (a_1,\ldots,a_n)\in (\mathbb{F}_{q}^*)^n\), με \(a_i\neq a_j\) για \(i\neq j\) και ένα διάνυσμα \(v = (v_1\ldots,v_n)\in (\mathbb{F}_{q}^*)^n\) (τα \(v_i\) μπορούν να μην είναι διακεκριμένα). Ο κώδικας \(\mathrm{GRS}_{k}(\alpha, v)\) ορίζεται ως η εικόνα της γραμμικής απεικόνισης \[ \mathrm{ev} : \mathbb{F}_{q}[X]_{< k}\ \ \longrightarrow\ \ \mathbb{F}_{q}^n, \ \ \ \mathrm{ev}(f) = (v_1 f(a_1),\ldots, v_n f(a_n)), \] όπου \(\mathbb{F}_{q}[X]_{< k}\) είναι ο χώρος των πολυωνύμων βαθμού \(< k\) πανω από το \(\mathbb{F}_{q}\).
Έχουμε ήδη δει ότι ο \(\mathrm{GRS}_{k}(\alpha, v)\) είναι MDS και ότι ο δυϊκός κάθε MDS κώδικα είναι επίσης MDS. Δείξαμε ότι για τους GRS ισχύει κάτι περισσότερο: ο δυϊκός είναι επίσης GRS. Ειδικότερα, δείξαμε ότι \(\mathrm{GRS}_{k}(\alpha, v)^{\perp} = \mathrm{GRS}_{n-k}(\alpha, v')\), όπου το διάνυσμα \(v'\) μπορεί εύκολα να υπολογιστεί ως η βάση του μηδενόχωρου ενός πίνακα βάσης του \(\mathrm{GRS}_{n-1}(\alpha, v)\). Αρχίσαμε να μελατάμε την αποκωδικοποίηση των GRS.
Διαβάστε: Παρ. 9.1 από το βιβλίο [2].
Είδαμε μία βασική μέθοδο αποκωδικοποίησης των GRS.
Είδαμε το σχήμα διαμοιρασμού μυστικών του Shamir (secret sharing scheme) και πώς αυτό μπορεί να διατυπωθεί ως πρόβλημα ereasure decoding κωδίκων Reed-Solomon.
Διαβάστε: Παρ. 6.1, 6.2, 6.3 από το βιβλίο [3].Ασκήσεις: 4ο Φυλλάδιο (Ημ. παράδοσης 18/11/2024)
Είδαμε πώς μπορούμε να κάνουμε αποκωδικοποίηση των GRS με τη βοήθεια του Ευκλείδειου αλγόριθμου.
Διαβάστε: Παρ. 6.4 από το βιβλίο [3].
Λύσαμε τις ασκήσεις των φυλλαδίων 2 και 3.
Είδαμε τους κώδικες Goppa και πώς χρησιμοποιούνται στο κρυπτοσύστημα του McEliece.
Διαβάστε: Παρ. 9.3 από το βιβλίο [2].Ασκήσεις: 5ο Φυλλάδιο (Ημ. παράδοσης 9/12/2024)
Αρχίσαμε να μελετάμε κυκλικούς κώδικες. Ένας γραμμικός κώδικας \(C\) ονομάζεται κυκλικός αν \((c_0,c_1,\ldots,c_{n-1})\in C\ \Rightarrow\ (c_{n-1},c_0,\ldots,c_{n-2})\in C\). Δείξαμε ότι κάτω από τον ισομορφισμό \[ \pi : \mathbb{F}_{q}^n \longrightarrow \mathbb{F}_{q}[X]/\an{X^n-1},\ \ (c_0,c_1,\ldots,c_{n-1}) \mapsto \overline{c_0+c_1X+\cdots+c_{n-1}X^{n-1}} \] ένας κυκλικός κώδικας \(C\) αντιστοιχεί σε ένα ιδεώδες \(\pi(C)\) του δακτυλίου \(R=\mathbb{F}_{q}[X]/\an{X^n-1}\). Συμβολίσαμε \(x = \overline{X}\) και γράφουμε τα στοιχεία του \(R\) ως πολυώνυμα στο \(x\), με δεδομένη τη σχέση \(x^n=1\).
Δείξαμε ότι κάθε ιδεώδες \(J\) του \(R\) είναι κύριο. Αν το \(J\) είναι μη μηδενικό και \(g(X)\) είναι ελάχιστου βαθμού, τέτοιο ώστε \(g(x)\in J\), τότε το \(J = \an{g(x)}\). Αν επιλέξουμε το \(g(X)\) μονικό, τότε είναι μοναδικό και ονομάζεται ο γεννήτορας του \(J\). Δείξαμε επίσης, ότι αυτό το \(g(X)\) διαιρεί το \(X^n-1\). Καταλήξαμε στο πόρισμα ότι οι κυκλικοί κώδικες μήκους \(n\) πάνω από το \(\mathbb{F}_{q}\) είναι σε ένα-προς-ένα αντιστοιχία με τους διαιρέτες του πολυωνύμου \(X^n-1\).
Αρχίσαμε να μελατάμε την παραγοντοποίηση του \(X^n-1\) πάνω από το \(\mathbb{F}_{q}\). Αν \((n, q) = p^{\nu}\), τότε \[ X^n - 1 = (X^m - 1)^{p^{\nu}}\] όπου \(n = p^{\nu} m\) και \((m, q) = 1\) και έτσι αρκεί να μελετήσουμε την περίπτωση όπου \((n,q)=1\). Τότε \[ Χ^n-1 = \prod_{d|n} \Psi_d(X) \] όπου το \(d\)-οστό κυκλοτομικό πολυώνυμο \(\Psi_d(X)\) παραγοντοποιείται \[ \Psi_d(X) = \prod_{(j,d)=1} (X-\zeta_d^j)\] και \(\zeta_d\) είναι μία πρωταρχική \(d\)-οστή ρίζα της μονάδας. Δείξαμε ότι \(\Psi_d(X) \in \mathbb{F}_{q}[X]\).
Διαβάστε: Παρ. 7.1, 7.2, 7.3 από το βιβλίο [2].
Δείξαμε ότι κάθε κυκλοτομικό πολυώνυμο \(\Psi_k(X)\in \mathbb{F}_{q}[X]\) αναλύεται σε γινόμενο \(r=\phi(k)/\mathrm{ord}_k(q)\) αναγώγων βαθμού \(\mathrm{ord}_k(q)\) το καθένα.
Ορίσαμε τους primitive BCH κώδικες, μήκους \(q^m-1\) πάνω από το \(\mathbb{F}_{q}\), δείξαμε ένα φράγμα για την διάσταση τους και δείξαμε ότι η ελάχιστη απόσταση τους είναι τουλάχιστον όση και η απόσταση σχεδίασης (αυτό είναι γνωστό ως BCH bound).
Ορίσαμε την ομάδα των χαρακτήρων μίας πεπερασμένης αβελιανής ομάδας \(G\), την οποία ονομάσαμε δυϊκή της \(G\) και συμβολίσαμε \(\widehat{G}\). Είδαμε τις ομάδες \(\widehat{\mathbb{F}_{q}}\) όταν \(q\) είναι δύναμη πρώτου και την \(\widehat{\mathbb{F}_{q}^n}\).
Ορίσαμε τον διακριτό μετασχηματισμό Fourier και υπολογίσαμε το μετασχηματισμό της χαρακτηριστικής συνάρτησης ενός υπόχωρου \(C\leq \mathbb{F}_{q}^n\).
Ολοκληρώσαμε την απόδειξη των εξισώσεων MacWilliams.
Διαβάστε: Παρ. 8.1.1, 8.1.2 από το βιβλίο [2].Ασκήσεις: 6ο Φυλλάδιο