Ένας κώδικας μήκους $n$ πάνω από ένα αλφάβητο $\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$ είναι δύναμη ενός πρώτου, μπορούμε να πάρουμε για αλφάβητο το πεπερασμένο σώμα ${\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$ ως το πλήθος των μη μηδενικών συντεταγμένων της:

$\mathrm{wt}(x_1,\ldots, x_n) = |\{1\leq i\leq n : x_i \neq 0\}|.$

Είδαμε ότι το βάρος Hamming είναι νόρμα στο χώρο ${\mathbb F}_{ q}^n$ και η αντίστοιχη μετρική $\Delta(x, y) = \mathrm{wt}(x-y)$ είναι η απόσταση Hamming. Το ελάχιστο βάρος και η ελάχιστη απόσταση ενός κώδικα ορίζονται ως:

$\mathrm{wt}(C) = \min\{\mathrm{wt}(c) : c\in C, c\neq 0\}$

και

$\Delta(C) = \min\{\Delta(x,y) : x,y\in C, x\neq y\}$

αντίστοιχα. Όταν ο $C$ είναι γραμμικός κώδικας, τότε $\mathrm{wt}(C) = \Delta(C)$.

Στο χώρο ${\mathbb F}_{ q}^n$ ορίσαμε το Ευκλείδειο εσωτερικό γινόμενο

$\langle \cdot, \cdot \rangle : {\mathbb F}_{ q}^n\times {\mathbb F}_{ q}^n \longrightarrow {\mathbb F}_{ q},\ \ \langle (x_1,\ldots,x_n), (y_1,\ldots, y_n) \rangle = x_1y_1+\cdots + x_n y_n$

Ο δϋικός χώρος του $C$ ορίζεται ως

$C^{\perp} = \{ u\in {\mathbb F}_{ q}^n : \forall c\in C, \langle c,u \rangle = 0\}.$

Αν και, γενικά, οι χώροι $C$ και $C^{\perp}$ μπορεί να έχουν μη τετριμμένη τομή, ισχύουν τα παρακάτω:

1. $\dim C + \dim C^{\perp} = n$,

2. $(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].
Ασκήσεις: Φυλλάδιο 0
Ασκήσεις: Φυλλάδιο 1 (Ημ. παράδοσης 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 : \mathrm{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)$ ως την εικόνα της γραμμικής απεικόνισης

όπου $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]/\langle X^n-1 \rangle,\ \ (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]/\langle X^n-1 \rangle$. Συμβολίσαμε $x = \overline{X}$ και γράφουμε τα στοιχεία του $R$ ως πολυώνυμα στο $x$, με δεδομένη τη σχέση $x^n=1$.

Δείξαμε ότι κάθε ιδεώδες $J$ του $R$ είναι κύριο. Αν το $J$ είναι μη μηδενικό και $g(X)$ είναι ελάχιστου βαθμού, τέτοιο ώστε $g(x)\in J$, τότε το $J = \langle g(x) \rangle$. Αν επιλέξουμε το $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ο Φυλλάδιο

Λύσαμε τις ασκήσεις των φυλλαδίων 4 και 5.