Συντάχθηκε 12-01-2018 14:25
από Sofia Malandraki
Email συντάκτη: sofiamalandraki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος ΗΜΜΥ.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΜΑΓΔΑΣ ΑΜΙΡΙΔΗ
με θέμα
Τεχνικές Κατασκευής και Αποκωδικοποίησης Πολικών Κωδίκων
Polar-code Construction and Decoding Techniques
Δευτέρα 15 Ιανουαρίου 2018, 9 π.μ.
Αίθουσα 137.Π39, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Γεώργιος Καρυστινός (επιβλέπων)
Αναπληρωτής Καθηγητής Άγγελος Μπλέτσας
Καθηγητής Αθανάσιος Λιάβας
Περίληψη
Οι πολικοί κώδικες, που πρόσφατα εφευρέθηκαν από τον Arikan, είναι οι πρώτοι κώδικες που αποδεδειγμένα επιτυγχάνουν την χωρητικότητα για οποιοδήποτε συμμετρικό κανάλι δυαδικής εισόδου, διακριτό και χωρίς μνήμη με χαμηλή πολυπλοκότητα κωδικοποίησης και αποκωδικοποίησης. Η διπλωματική αυτή εργασία διερευνά την πρακτική υλοποίηση πολικών κωδικών ώστε να είναι αποδοτικοί από πλευράς πολυπλοκότητας και performance για το δυαδικό κανάλι διαγραφής (BEC) και το δυαδικό συμμετρικό κανάλι (BSC). Η ρητή κατασκευή των πολικών κώδικων βασίζεται σε ένα χαρακτηριστικό που ονομάζεται πόλωση καναλιού, το οποίο περιλαμβάνει τη δημιουργία N ακραίων (τέλειων ή εντελώς θορυβώδων) καναλιών από Ν ανεξάρτητες χρήσεις του ίδιου βασικού καναλιού. Τα bits πληροφορίας στέλνονται μέσω των αθόρυβων καναλιών, ενώ στα θορυβώδη αποδίδονται fixed δυαδικά ψηφία, που ονομάζονται frozen bits. Ο σχεδιασμός των κώδικων για το BEC βασίζεται σε αναδρομικες σχέσεις που παρουσιάζονται στο αρχικό paper του Arikan, ενώ για το BSC προτείνουμε έναν ευρετικό και αποδοτικό αλγόριθμο και τον συγκρίνουμε με τη μέθοδο της αναδρομικής εκτίμησης των παραμέτρων Bhattacharyya των bit καναλιών. Η κωδικοποίηση υλοποιείται χρησιμοποιώντας μια αναδρομική δομή πεταλούδας με πολυπλοκότητα O (N logN), όπου N είναι το μήκος του μπλοκ του κώδικα. Δύο κύριοι αποκωδικοποιητές χαμηλής πολυπλοκότητας συγκρίνονται ως προς το ποσοστό σφάλματος δυαδικών ψηφίων: o successive cancellation decoder, που προτάθηκε από τον Arikan με πολυπλοκότητα Ο (N logN), με ευαισθησία στη διάδοση σφάλματος και μέτρια απόδοση σφάλματος bit σε μικρά ή μέτρια μήκη κώδικα, και o list decoder, ο οποίος προτάθηκε από τους Tal και Vardy, με πολυπλοκότητα O (LN logN) όπου L είναι το μέγεθος της λίστας.
Abstract
Polar codes, recently invented by Arikan, are the first provably capacity achieving codes for any binary input symmetric discrete memoryless channel with low encoding and decoding complexity. This thesis explores the practical implementation of polar codes which are complexity efficient and perform well for binary erasure channel (BEC) and binary symmetric channel (BSC). The explicit code construction is based on a characteristic called channel polarization which involves generating N extremal (perfect or completely noisy) channels from N independent uses of the same base channel. Information bits are sent over the noiseless channels while pilot bits, called frozen bits, are assigned to the noisy ones. Code design for BEC is based on the recursive relations presented in the original paper whereas for BSC we propose a heuristic and efficient algorithm and compare it to the method of recursive estimation of Bhattacharyya parameters of bit-channels. The encoding is implemented using a recursive butterfly structure with O(N logN) complexity, where N is the block length of the code. Two main low complexity decoders are compared in terms of bit error rate: successive cancellation decoder proposed by Arikan having complexity O(N logN) with susceptibility to error propagation and mediocre bit error rate performance at small or moderate code lengths and list decoder, proposed by Tal and Vardy, with complexity O(LN logN) where L is the list size.
