Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Information bit selection in polar coding for the binary symmetric channel

Bountrogiannis Konstantinos

Simple record


URIhttp://purl.tuc.gr/dl/dias/26D4B8E1-C83C-4407-A172-BE3EEC02F2B1-
Identifierhttps://doi.org/10.26233/heallink.tuc.74152-
Languageen-
Extent56 pagesen
TitleInformation bit selection in polar coding for the binary symmetric channelen
TitleΕπιλογή bit πληροφορίας σε πολική κωδικοποίηση για το συμμετρικό δυαδικό κανάλιel
CreatorBountrogiannis Konstantinosen
CreatorΜπουντρογιαννης Κωνσταντινοςel
Contributor [Thesis Supervisor]Karystinos Georgiosen
Contributor [Thesis Supervisor]Καρυστινος Γεωργιοςel
Contributor [Committee Member]Liavas Athanasiosen
Contributor [Committee Member]Λιαβας Αθανασιοςel
Contributor [Committee Member]Bletsas Aggelosen
Contributor [Committee Member]Μπλετσας Αγγελοςel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Content SummaryPolar 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.en
Content SummaryΟι πολικοί κώδικες (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. Τα αποτελέσματα των προσομοιώσεων δείχνουν μια σημαντική διαφορά στην ταχύτητα του προτεινόμενου αλγορίθμου από την αποκλειστική χρήση των προσεγγιστικών αλγορίθμων, τέτοια ώστε ο χρόνος που εξοικονομείται να μπορεί να αξιοποιηθεί υπολογιστικά για μια πιο ακριβή κατασκευή του κώδικα.el
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by-nc-sa/4.0/en
Date of Item2018-04-20-
Date of Publication2018-
SubjectΠολικοί κώδικεςel
SubjectPolar codesen
SubjectChannel polarizationen
SubjectΚωδικοποίηση καναλιούel
SubjectChannel codingen
SubjectConstruction algorithmsen
SubjectΣυμμετρικό δυαδικό κανάλι el
SubjectBinary symmetric channelen
Bibliographic CitationKonstantinos Bountrogiannis, "Information bit selection in polar coding for the binary symmetric channel", Diploma Work, School of Electronic Computer Engineering, Technical University of Crete, Chania, Greece, 2018el
Bibliographic CitationΚωνσταντίνος Μπουντρογιάννης, "Επιλογή bit πληροφορίας σε πολική κωδικοποίηση για το συμμετρικό δυαδικό κανάλι", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2018el

Available Files

Services

Statistics