Α32 Κωδικοποίηση

Ημερολόγιο μαθήματος

Εβδομάδα 1: 23/9/2024 - 29/9/2024

Ένας κώδικας μήκους nn πάνω από ένα αλφάβητο Σ\Sigma με qq σύμβολα είναι ένα υπόσύνολο CΣnC\subseteq \Sigma^n. Ορίσαμε την απόσταση Hamming δύο λέξεων x=(x1,,xn),y=(y1,,yn)x=(x_1,\ldots, x_n), y=(y_1,\ldots, y_n) ως

Δ(x,y)={1in:xiyi}, \Delta(x,y) = |\{1\leq i\leq n : x_i \neq y_i\}|,

δηλαδή το πλήθος των συντεταγμένων στις οποίες διαφέρουν οι δύο λέξεις. Ορίσαμε επίσης την ελάχιστη απόσταση dd ενός κώδικα ως

d=min{Δ(x,y):x,yC,xy}. d = \min\{\Delta(x,y) : x,y\in C, x\neq y\}.

Δείξαμε ότι ο κώδικας μπορεί να διορθώνει tt σφάλματα αν και μόνο αν td12t\leq \lfloor \tfrac{d-1}{2}\rfloor. Όταν το qq είναι δύναμη ενός πρώτου, μπορούμε να πάρουμε για αλφάβητο το πεπερασμένο σώμα Fq{\mathbb F}_{ q}. Κάθε γραμμικός υπόχωρος του Fqn{\mathbb F}_{ q}^n ονομάζεται γραμμικός κώδικας μήκους nn πάνω από το Fq{\mathbb F}_{ q}. Ορίσαμε το ρυθμό (rate) του κώδικα ως logq(C)n\frac{\log_q(|C|)}{n} και παρατηρήσαμε ότι στην περίπτωση ενός γραμμικού κώδικα διάστασης kk, ο ρυθμός είναι ίσος με kn\frac{k}{n}. Ορολογία: ένας γραμμικός κώδικας μήκους nn, διάστασης kk και με ελάχιστη απόσταση dd ονομάζεται [n,k,d][n,k,d]-κώδικας.

Ξεκινήσαμε μία επανάληψη σε βασικές έννοιες της θεωρίας σωμάτων: είδαμε τι είναι επέκταση σωμάτων, K/FK/F, βαθμός της επέκτασης, [K:F][K:F], και ορίσαμε το ελάχιστο πολυώνυμο ενός αλγεβρικού στοιχείου αK\alpha\in K πάνω από το FF. Δείξαμε ότι κάθε πεπερασμένο σώμα F\mathbb F έχει θετική χαρακτηριστική, pp, περιέχει το σώμα Fp=Z/p{\mathbb F}_{ p} = \mathbb Z/\langle p \rangle και F=pn|\mathbb F|=p^n για κάποιο φυσικό αριθμό nn. Για δεδομένο ανάγωγο πολυώνυμο fFp[X]f\in {\mathbb F}_{ p}[X] βαθμού nn, κατασκευάσαμε το σώμα Fp[X]/f{\mathbb F}_{ p}[X]/\langle f \rangle, το οποίο έχει pnp^n στοιχεία και περιέχει μία ρίζα, ας την ονομάσουμε α\alpha, του ff. Το σώμα αυτό είναι το

Fp(α)={c0+c1α++cn1αn1:c0,c1,,cn1Fp}.{\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}\}.

Δείξαμε ότι η πολλαπλασιαστική ομάδα F\mathbb F^* κάθε πεπερασμένου σώματος είναι κυκλική.

Διαβάστε: Κεφ. 1 και 2 από το βιβλίο [2].
Διαβάστε: Παρ. 1.1 έως 1.4 από το βιβλίο [1].
Διαβάστε: Σημείωσεις

Εβδομάδα 2: 30/9/2024 - 6/10/2024

Αποδείξαμε ότι για κάθε πρώτο pp και κάθε φυσικό αριθμό nn υπάρχει ακριβώς ένα σώμα με pnp^n στοιχεία εντός μίας αλγεβρικής θήκης του Fp{\mathbb F}_{ p}.

Ορίσαμε την έννοια του βάρους Hamming μίας λέξης (x1,,xn)Fqn(x_1,\ldots, x_n)\in {\mathbb F}_{ q}^n ως το πλήθος των μη μηδενικών συντεταγμένων της:

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

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

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

και

Δ(C)=min{Δ(x,y):x,yC,xy} \Delta(C) = \min\{\Delta(x,y) : x,y\in C, x\neq y\}

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

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

,:Fqn×FqnFq,  (x1,,xn),(y1,,yn)=x1y1++xnyn \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

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

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

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

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

  2. (C)=C(C^{\perp})^{\perp} = C.

Πίνακας βάσης (generator matrix) ενός [n,k][n,k]-γραμμικού κώδικα CC είναι ένας πίνακας GFqk×nG\in {\mathbb F}_{ q}^{k\times n} του οποίου οι γραμμές είναι βάση του CC.

Πίνακας ελέγχου (parity check matrix) ενός [n,k][n,k]-γραμμικού κώδικα CC είναι ένας πίνακας HFq(nk)×nH\in {\mathbb F}_{ q}^{(n-k)\times n} του οποίου οι γραμμές είναι βάση του CC^{\perp}.

Δείξαμε ότι ένας γραμμικός κώδικας CC με πίνακα ελέγχου HH έχει ελάχιστη απόσταση dd αν και μόνο αν κάθε d1d-1 στήλες του HH είναι γραμμικώς ανεξάρτητες και υπάρχουν dd γραμμικώς εξαρτημένες στήλες του HH.

Είδαμε τη μέθοδο αποκωδικοποίησης με σύνδρομα.

Διαβάστε: Παρ. 2.1 έως και 2.3 από το βιβλίο [1].
Διαβάστε: Παρ. 4.1 έως και 4.4 από το βιβλίο [2].
Διαβάστε: Παρ. 4.5 έως 4.8 από το βιβλίο [2].
Ασκήσεις: Φυλλάδιο 0
Ασκήσεις: Φυλλάδιο 1 (Ημ. παράδοσης 9/10/2024)

Εβδομάδα 3: 7/10/2024 - 13/10/2024

Δείξαμε το φράγμα του Hamming ή αλλιώς Sphere Packing bound. Ειδικότερα, κάθε κώδικας με παραμέτρους (n,M,d)(n, M, d) πάνω από ένα αλφάβητο με qq σύμβολα ικανοποιεί

Mqn/Vqn(d12), M \leq q^n / V_q^n(\lfloor \tfrac{d-1}{2}\rfloor),

όπου Vqn(ρ)=i=0ρ(ni)(q1)iV_q^n(\rho) = \sum_{i=0}^{\rho}\binom{n}{i} (q-1)^i είναι ο όγκος (πλήθος σημείων) της μπάλας ακτίνας ρ\rho στο χώρο Fqn{\mathbb F}_{ q}^n. Κάθε κώδικας που "πιάνει" το άνω φράγμα ονομάζεται τέλειος (perfect).

Ορίσαμε τους δυαδικούς κώδικες Hamming, Ham(r,2)\mathrm{Ham}(r, 2), για r2r\geq 2, δείξαμε ότι έχουν παραμέτρους [2r1,2r1r,3][2^r-1, 2^r-1-r, 3] και συνεπώς είναι τέλειος. Είδαμε την αποκωδικοποίηση τους με σύνδρομα (και πώς δεν είναι απαραίτητο να καταγράψουμε τον πίνακα με τα σύνδρομα). Ορίσαμε τους κώδικες Hamming, Ham(r,q)\mathrm{Ham}(r, q), πάνω από το Fq{\mathbb F}_{ q} και δείξαμε ότι έχουν παραμέτρους [qn1q1,qn1q1r,3][\tfrac{q^n-1}{q-1}, \tfrac{q^n-1}{q-1}-r, 3], άρα είναι τέλειοι.

Είδαμε το Sphere Covering bound και το φράγμα των Gilbert-Varshamov.

Δείξαμε ότι κάθε κώδικας πάνω από ένα αλφάβητο με qq σύμβολα και παραμέτρους (n,M,d)(n, M, d) ικανοποιεί Mqnd+1M\leq q^{n-d+1}. Αυτό είναι το φράγμα του Singleton. Για γραμμικούς κώδικες με παραμέτρους [n,k,d][n,k,d] το φράγμα γίνεται dnk+1d \leq n-k+1. Κάθε κώδικας ο οποίος έχει ελάχιστη απόσταση που "πιάνει" το φράγμα με ισότητα ονομάζεται MDS (Maximum Distance Separable).

Ορίσαμε τους γενικευμένους κώδικες Reed-Solomon, GRSk(a)\mathrm{GRS}_k({\mathbf{a}}) όπου a=(a1,,an){\mathbf{a}} = (a_1,\ldots, a_n), και τα aia_i είναι διακεκριμένα στοιχεία του Fq{\mathbb F}_{ q}, ως την εικόνα της γραμμικής απεικόνισης

ev:Fq[X]<kFqn,   f(f(a1),,f(an)) \mathrm{ev} : {\mathbb F}_{ q}[X]_{< k} \longrightarrow {\mathbb F}_{ q}^n,\ \ \ f \mapsto (f(a_1),\ldots, f(a_n)) \\

και δείξαμε ότι έχουν παραμέτρους [n,k,nk+1][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)

Εβδομάδα 4: 14/10/2024 - 20/10/2024

Μελετήσαμε του MDS κώδικες. Ειδικότερα, δείξαμε ότι αν CC είναι ένας κώδικας με παραμέτρους [n,k,nk+1][n, k, n-k+1] πάνω από το Fq{\mathbb F}_{ q} και επιλέξουμε ένα υποσύνολο S{1,,n}S\subseteq \{1,\ldots, n\} με S=dd=nk+1|S|=d'\geq d = n-k+1, τότε το σύνολο

CS={(c1,,cn)C:i∉S  ci=0} C_{S} = \{(c_1,\ldots,c_n)\in C : \forall i\not\in S\ \ c_i = 0\}

είναι υπόχωρος του CC με διάσταση dd+1d'-d+1.

Αν Ai={cC:wt(c)=i}A_i = |\{c\in C : \mathrm{wt}(c) = i\}|, τότε A0=1A_0 = 1, Ai=0A_i = 0 για 1id11\leq i\leq d-1 και δείξαμε ότι για dind\leq i \leq n ισχύει

Ai=(ni)(q1)j=0id(1)j(i1j)qijd. A_i = \binom{n}{i}(q-1) \sum_{j=0}^{i-d}(-1)^j \binom{i-1}{j} q^{i-j-d}.

Για i=d+1i=d+1 παίρνουμε Ad+1=(nd+1)(q1)(qd)0A_{d+1} = \binom{n}{d+1}(q-1)(q-d) \geq 0, άρα qd=nk+1q\geq d = n-k+1. Εφαρμόζοντας το φράγμα αυτό στο δυϊκό κώδικα CC^{\perp}, ο οποίος είναι επίσης MDS, παίρνουμε qk+1q\geq k+1.

Δείξαμε τα φράγματα του Plotkin και του Griesmer.

Διαβάστε: Σελ. 101-102 από το βιβλίο [4].
Διαβάστε: Παρ. 5.5 και 5.7 από το βιβλίο [2].

Εβδομάδα 5: 21/10/2024 - 27/10/2024

Είδαμε κάποιες βασικές κατασκευές νέων κωδίκων από δεδομένους κώδικες. Είδαμε την κατασκευή του ευθέως αθροίσματος και την κατασκευή (u,u+v)(u, u+v). Ως ειδική περίπτωση της τελευταίας κατασκευής, είδαμε την κατασκευή των κωδίκων Reed-Muller πρώτης τάξης πάνω από το F2{\mathbb F}_{ 2} και υπολογίσαμε τις παραμέτρους τους.

Ορίσαμε τους (γενικούς) κώδικες Reed-Muller ως κώδικες αποτίμησης πολυωνύμων. Ειδικότερα, ορίσαμε τους κώδικες RM(q,m,r)\mathrm{RM}(q,m,r) ως την εικόνα της γραμμικής απεικόνισης

ev:Fq[X1,,Xm]rFqqmf(X1,,Xm)(f(t1),,f(tqm))\begin{array}{rcl} \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{array}
όπου t1,,tqmt_1,\ldots, t_{q^m} είναι τα σημεία του Fqm{\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)

Εβδομάδα 6: 28/10/2024 - 3/10/2024

Αρχίσαμε τη συστηματική μελέτη των Γενικευμένων Κωδίκων Reed-Solomon (GRS). Για να ορίσουμε ένα (γενικευμένο) κώωδικα Reed-Solomon πάνω από το σώμα Fq{\mathbb F}_{ q} μήκους nn και διάστασης kk, χρειαζόμαστε ένα διάνυσμα α=(a1,,an)(Fq)n\alpha = (a_1,\ldots,a_n)\in ({\mathbb F}_{ q}^*)^n, με aiaja_i\neq a_j για iji\neq j και ένα διάνυσμα v=(v1,vn)(Fq)nv = (v_1\ldots,v_n)\in ({\mathbb F}_{ q}^*)^n (τα viv_i μπορούν να μην είναι διακεκριμένα). Ο κώδικας GRSk(α,v)\mathrm{GRS}_{ k}({ \alpha}, { v}) ορίζεται ως η εικόνα της γραμμικής απεικόνισης

ev:Fq[X]<k    Fqn,   ev(f)=(v1f(a1),,vnf(an)), \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)),

όπου Fq[X]<k{\mathbb F}_{ q}[X]_{< k} είναι ο χώρος των πολυωνύμων βαθμού <k< k πανω από το Fq{\mathbb F}_{ q}.

Έχουμε ήδη δει ότι ο GRSk(α,v)\mathrm{GRS}_{ k}({ \alpha}, { v}) είναι MDS και ότι ο δυϊκός κάθε MDS κώδικα είναι επίσης MDS. Δείξαμε ότι για τους GRS ισχύει κάτι περισσότερο: ο δυϊκός είναι επίσης GRS. Ειδικότερα, δείξαμε ότι GRSk(α,v)=GRSnk(α,v)\mathrm{GRS}_{ k}({ \alpha}, { v})^{\perp} = \mathrm{GRS}_{ n-k}({ \alpha}, { v'}), όπου το διάνυσμα vv' μπορεί εύκολα να υπολογιστεί ως η βάση του μηδενόχωρου ενός πίνακα βάσης του GRSn1(α,v)\mathrm{GRS}_{ n-1}({ \alpha}, { v}). Αρχίσαμε να μελατάμε την αποκωδικοποίηση των GRS.

Διαβάστε: Παρ. 9.1 από το βιβλίο [2].

Εβδομάδα 7: 4/11/2024 - 10/11/2024

Είδαμε μία βασική μέθοδο αποκωδικοποίησης των GRS.

Είδαμε το σχήμα διαμοιρασμού μυστικών του Shamir (secret sharing scheme) και πώς αυτό μπορεί να διατυπωθεί ως πρόβλημα ereasure decoding κωδίκων Reed-Solomon.

Διαβάστε: Παρ. 6.1, 6.2, 6.3 από το βιβλίο [3].
Ασκήσεις: 4ο Φυλλάδιο (Ημ. παράδοσης 18/11/2024)

Εβδομάδα 8: 11/11/2024 - 17/11/2024

Είδαμε πώς μπορούμε να κάνουμε αποκωδικοποίηση των GRS με τη βοήθεια του Ευκλείδειου αλγόριθμου.

Διαβάστε: Παρ. 6.4 από το βιβλίο [3].