Information bit selection in polar coding for the binary symmetric channelInformation bit selection in polar coding for the binary symmetric channelΕπιλογή bit πληροφορίας σε πολική κωδικοποίηση για το συμμετρικό δυαδικό κανάλι Διπλωματική Εργασία Diploma Work 2018-04-202018enPolar codes is a new scheme of channel coding, which is the first provably capacity-achieving coding scheme for a wide class of channels, the binary discrete memoryless channels. At the same time, they use low complexity encoding and decoding algorithms, which makes them attractive for a wide range of use-cases. These algorithms scale as O(NlogN), where N is the blocklength of the code. Polar codes exploit channel polarization, a very common phenomenon which arises when one takes N independent copies of a channel and transforms them into another set of N channels. Under channel polarization, the channels are converted to a set of extremal (either perfect or completely noisy) channels, called bit-channels. In the presence of channel polarization, the information vector is sent through the perfect bit-channels, while a fixed vector of arbitrary bits is sent through the useless bit-channels. A problem which arises is the determination of which bit-channels are perfect and which are useless. This problem, called the “construction of polar codes” among researchers, has been addressed successfully and efficiently only for the binary erasure channel (BEC). The non-universality property of polar codes complicates their construction, because the behaviour of a bit-channel may be perfect for one physical channel but noisy for another. The adoption of polar codes in 5G NR strengthens the demand for a fast and adaptive construction scheme. This thesis attempts to design an efficient algorithm for the construction of polar codes for the binary symmetric channel (BSC), taking advantage of proved universal partial orders among the bit-channels and state-of-the-art algorithms which approximate efficiently upper and lower bounds of the probability of error of the bit-channels. The simulation results show a marginal time-running difference over the explicit use of the approximation algorithms, which can be used computationally for a more accurate construction.Οι πολικοί κώδικες (polar codes) είναι μια σύγχρονη μέθοδος κωδικοποίησης καναλιού, η πρώτη μέθοδος που αποδεδειγμένα επιτυγχάνει την χωρητικότητα του καναλιού για μια μεγάλη κατηγορία καναλιών, τα δυαδικά διακριτά κανάλια χωρίς μνήμη. Την ίδια στιγμή, χρησιμοποιούν αλγορίθμους κωδικοποίησης και αποκωδικοποίησης χαμηλής πολυπλοκότητας, κάτι που τους κάνει ελκυστικούς για πολλές χρήσεις. Οι αλγόριθμοι αυτοί έχουν πολυπλοκότητα της τάξης O(NlogN), όπου N είναι το μήκος μπλοκ του κώδικα. Οι πολικοί κώδικες αξιοποιούν ένα φαινόμενο που λέγεται πόλωση καναλιού (channel polarization), ένα σύνηθες φαινόμενο που προκύπτει όταν μετασχηματίζουμε N ανεξάρτητα αντίγραφα ενός καναλιού σε ένα άλλο σύνολο από N κανάλια. Τα κανάλια πολώνονται, με την έννοια ότι μετατρέπονται σε ένα σύνολο από ακραία κανάλια (είτε τέλεια είτε εντελώς θορυβώδη), τα οποία ονομάζουμε bit-channels. Υπό την παρουσία της πόλωσης του καναλιού, η πληροφορία αποστέλλεται μέσα από τα τέλεια bit-channels, ενώ μέσα από τα άχρηστα bit-channels αποστέλλεται μια αυθαίρετη στατική ακολουθία από bits. Ένα πρόβλημα που προκύπτει είναι η εξακρίβωση των bit-channels που είναι τέλεια και αυτών που είναι άχρηστα. Αυτό το πρόβλημα, που από τους ερευνητές ονομάζεται “κατασκευή των πολικών κωδίκων”, έχει επιλυθεί με γρήγορο τρόπο μόνο για το δυαδικό κανάλι διαγραφής (BEC). Το γεγονός ότι τα bit-channels των πολικών κωδίκων δεν έχουν ενιαία συμπεριφορά για όλα τα φυσικά κανάλια στα οποία κατασκευάζεται ο πολικός κώδικας, περιπλέκει το πρόβλημα διότι ένα bit-channels μπορεί να είναι τέλειο για ένα πολικό κώδικα αλλά θορυβώδες για έναν άλλον. Η αξιοποίηση των πολικών κωδίκων στο 5G NR ενισχύει την ανάγκη για έναν γρήγορο και ευπροσάρμοστο αλγόριθμο κατασκευής. Αυτή η διπλωματική εργασία προσπαθεί να σχεδιάσει έναν αποδοτικό αλγόριθμο για την κατασκευή των πολικών κωδίκων για το δυαδικό συμμετρικό κανάλι (BSC), αξιοποιώντας κάποιες μερικές διατάξεις (partial orders) μεταξύ των bit-channels που έχουν αποδειχθεί ότι ισχύουν για όλους τους πολικούς κώδικες και κάποιους σύγχρονους αλγορίθμους που εκτιμούν αποδοτικά άνω και κάτω όρια της πιθανότητας σφάλματος των bit-channels. Τα αποτελέσματα των προσομοιώσεων δείχνουν μια σημαντική διαφορά στην ταχύτητα του προτεινόμενου αλγορίθμου από την αποκλειστική χρήση των προσεγγιστικών αλγορίθμων, τέτοια ώστε ο χρόνος που εξοικονομείται να μπορεί να αξιοποιηθεί υπολογιστικά για μια πιο ακριβή κατασκευή του κώδικα.http://creativecommons.org/licenses/by-nc-sa/4.0/Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών ΥπολογιστώνBountrogiannis_Konstantinos_Dip_2018.pdfChania [Greece]Library of TUC2018-04-20application/pdf748.5 kBfree Bountrogiannis Konstantinos Μπουντρογιαννης Κωνσταντινος Karystinos Georgios Καρυστινος Γεωργιος Liavas Athanasios Λιαβας Αθανασιος Bletsas Aggelos Μπλετσας Αγγελος Πολυτεχνείο Κρήτης Technical University of Crete Πολικοί κώδικες Polar codes Channel polarization Κωδικοποίηση καναλιού Channel coding Construction algorithms Συμμετρικό δυαδικό κανάλι Binary symmetric channel