Στη διπλωματική εργασία μελετήθηκε ο σχεδιασμός και η βελτιστοποίηση αρχιτεκτονικών αποκωδικοποιητων LDPC. Μελετήθηκε η δυνατότητα απλούστευσης του πολύπλοκου δικτύου διασύνδεσης των επεξεργαστικών στοιχείων της αρχιτεκτονικής που αποτελεί καθοριστικό παράγοντα της πολυπλοκότητας της υλοποίησης σε υλικό των αποκωδικοποιητών. Αναπτύχθηκε συστηματικός τρόπος αντιμετώπισης του προβλήματος αυτού, ανεξαρτήτως συγκεκριμένου κώδικα LDPC. / The design and optimization of LDPC decoders architecture was studied. An architecture with simplified interconnections and a systematic algorithm to derive it, regardless of the LDPC code, was proposed.

Ένα από τα βασικότερα τμήματα ενός συστήματος ψηφιακής μετάδοσης είναι η κωδικοποίηση καναλιού, η οποία στόχο έχει την ανίχνευση και διόρθωση των λαθών που εισάγονται στην πληροφορία μέσα στο κανάλι. Οι Bose, Chaudhuri και Hocquenghem (BCH) κώδικες είναι μία μεγάλη ομάδα ισχυρών κυκλικών κωδίκων διόρθωσης τυχαίων λαθών. Οι BCH κώδικες περιγράφονται με χρήση αλγεβρικών δομών που λέγονται πεπερασμένα πεδία. Για την κατανόηση των λειτουργιών κωδικοποίησης και αποκωδικοποίησης απαιτείται η προσεκτική μελέτη της άλγεβρας πεπερασμένων πεδίων και της αριθμητικής της. Οι BCH κώδικες χρησιμοποιούνται στο δορυφορικό πρότυπο DVB-S2, σε συνδυασμό με LDPC κώδικες. Στην παρούσα εργασία πραγματοποιήθηκε σχεδίαση και υλοποίηση κωδικοποιητών και αποκωδικοποιητών για κώδικες BCH(15,5,3) και BCH(16200,16008,12). Ο δεύτερος αποκωδικοποιητής σχεδιάστηκε με βάση της προδιαγραφές που θέτει το DVB-S2, και καλύπτει μία από τις περιπτώσεις κωδικοποίησης του συστήματος. Τέλος, αποδεικνύεται ότι με ελάχιστες μετατροπές ο ίδιος αποκωδικοποιητής μπορεί να καλύψει όλες τις περιπτώσεις διόρθωσης 12 λαθών ενός DVB-S2 συστήματος. / Channel coding is one of the most important parts of a digital transmission system, and it aims at the detection and correction of errors that might have occurred in a noisy channel. Bose, Chaudhuri and Hocquenghem (BCH) codes form a large class of powerful random error-correcting cyclic codes. BCH codes operate over algebraic structures called finite fields. Understanding the processes of encoding and decoding requires a careful study of finite field algebra and the associated arithmetic. DVB-S2 is a specification for satellite broadcasting that deploys BCH codes combined with LDPC codes. This thesis sets out to account for the design and implementation of encoders and decoders for the BCH(15,5,3) and BCH(16200,16008,12) codes. The BCH(16200,16008,12) encoder/decoder was designed according to the DVB-S2 standard. Proof is provided that the same encoder/decoder, with only some minor changes, can be used for all the 12 error-correcting codes used in DVB-S2.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη και ο σχεδιασμός VLSI επεξεργαστών για τη διόρθωση λαθών. Η κατηγορία των VLSI επεξεργαστών στην οποία εστιάζει η έρευνά μου είναι ο αποκωδικοποιητής Viterbi. Αρχικά, παρουσιάζεται η δομή του ψηφιακού τηλεπικοινωνιακού συστήματος και κάποιες βασικές έννοιες των κωδικών διόρθωσης λαθών. Έπειτα, αναλύονται οι Συνελικτικοί κωδικοποιητές, ανάμεσα στους οποίους περιλαμβάνεται ο Συνελικτικός κωδικοποιητής που χρησιμοποιείται στην εργασία μου και ο οποίος χρησιμοποιείται ευρέως στο πρότυπο Wifi 802.11a. Ακολούθως, γίνεται αναφορά στο κανάλι AWGN και στη διαμόρφωση BPSK. Ακόμα, παρουσιάζονται οι βασικές έννοιες του αλγόριθμου Viterbi, η λειτουργία του, η δομή του καθώς και οι εφαρμογές του. Στη συνέχεια, μελετώνται διάφορες αρχιτεκτονικές του αποκωδικοποιητή Viterbi σε VLSI. Με βάση τον τρόπο υλοποίησης αριθμητικών πράξεων, οι αρχιτεκτονικές που αναπτύσσονται είναι ο Radix-2 και ο Radix-4 Viterbi, ενώ με βάση τον τρόπο αποκωδικοποίησης αναπτύσσονται οι αρχιτεκτονικές του Viterbi για συνεχή αποκωδικοποίηση-εφαρμογές streaming και του Viterbi για αποκωδικοποίηση πακέτων των 20 bits. Επίσης, μελετάται η απόδοση των αρχιτεκτονικών αυτών με κριτήριο τη συχνότητα λαθών που πραγματοποιούνται (Bit Error Rate – BER) και αναλύεται η υλοποίηση των αρχιτεκτονικών αυτών στο αναπτυξιακό σύστημα Xilinx. Τέλος, προκύπτουν τα κατάλληλα συμπεράσματα. / The purpose of this diploma thesis is to study and implement VLSI processors for correcting errors. The category of VLSI processor which will focus in this work is the Viterbi decoder. Initially, the structure of the digital telecommunications system is presented along with some basic concepts of error correcting codes. Then we explain the theory behind convolutional encoders and we describe the convolutional encoder that is used in my work and is consistent in the Wifi 802.11a standard. Next we analyze briefly the AWGN channel and the BPSJ modulation. Also the basic concepts of the Viterbi algorithm, how it works, its structure and the different applications are given. For the practical part which is the main part of this project, is to study the different architectures of the Viterbi decoder in VLSI approach. The main architectures that were developed for the implementation arithmetic operations is Radix-2 and Radix-4 Viterbi, but in terms of decoding two more architectures were developed, Viterbi continuous decoding-streaming applications and Viterbi decoding for packets of 20 bits. Then, the performance of these architectures in terms of frequency of errors made (BER) was investigated and also the implementation of these architectures in the development system Xilinx was analyzed. At the end we give our conclusion regarding the results of the different simulations that we’ve done.

Στην εργασία αυτή, μελετώνται διαφορετικοί αποκωδικοποιητές για κώδικες Reed-Solomon. Αφού γίνει μια εισαγωγή στο σύστημα επικοινωνίας, στα πεπερασμένα σώματα και στη θεωρία κωδίκων, παρουσιάζονται αλγόριθμοι που υλοποιούν αποκωδικοποιητές περιορισμένης απόστασης, λίστας και soft decoders. Συγκεκριμένα, μελετώνται κλασσικοί αποκωδικοποιητές, αποκωδικοποιητές βασισμένοι στον αλγόριθμο Guruswami-Sudan, και αποκωδικοποιητές βασισμένοι στον αλγόριθμο Koetter-Vardy. Η σύγκριση γίνεται ως προς τη διορθωτική ικανότητα και τη χρονική πολυπλοκότητα. Στα πλαίσια της εργασίας αυτής, σε συνέχεια της μελέτης υπαρχόντων αποκωδικοποιητών προτείνεται ένα είδος προσαρμοστικού αποκωδικοποιητή: φέρει την ίδια διορθωτική ικανότητα με έναν αποκωδικοποιητή λίστας, αλλά σε ορισμένες περιπτώσεις έχει ικανοποιητικά μικρότερη χρονική πολυπλοκότητα. Επίσης γίνεται μία ποιοτική διερεύνηση για το πότε πρέπει να προτιμάται ο προσαρμοστικός αποκωδικοποιητής. Προτείνονται δύο διαφορετικοί προσαρμοστικοί αποκωδικοποιητές. Η πρώτη εκδοχή, είναι μία διάταξη με δύο αποκωδικοποιητές. Αρχικά το ληφθέν διάνυσμα από το κανάλι, εισέρχεται ως είσοδος σε έναν κλασσικό αποκωδικοποιητή. Αν ο κλασσικός παρουσιάσει αδυναμία αποκωδικοποίησης, τότε επιχειρεί να διορθώσει το ίδιο διάνυσμα ένας αποκωδικοποιητής λίστας. Η δέυτερη εκδοχή, μοιάζει με την πρώτη, με τη διαφορά ότι ο δεύτερος αποκωδικοποιητής χρησιμοποιεί αποτελέσματα που έχουν ήδη υπολογιστεί από τον πρώτο, μειώνοντας έτσι την συνολική χρονική πολυπλοκότητα, σχετικά με την πρώτη εκδοχή. / In this thesis we study a family of linear block codes, the Reed-Solomon(RS) codes. RS codes are q-ary codes over some finite field GF(q). Therefore, they have strong burst-error correction capability, because they deal with groups of bits instead of single bits. Initially, we describe the employed communication system model, and introduce basic from finite field theory (construction and identities) and coding theory. After describing the RS encoding process, we describe different RS decoders (bounded distance decoder, list decoder and soft-input decoder). Specifically, in addition to traditional approaches, we focus on decoders based on Guruswami-Sudan and Koetter – Vardy algorithms. We compare them according to their complexity and performance, both in theory and experimentally. Furthermore, in this thesis, we propose an adaptive decoder, which has the same performance as a list decoder but in some cases it achieves much lower average time complexity. We present the experimental results, highlighting the cases where the adaptive decoder outperforms conventional decoders. The adaptive decoder comes in two different types. The first type is a system with two different decoders: the low complexity decoder attempts to decode a received vector and in case of decoding failure the subsequent decoder tries to decode the same received vector. The second type resembles the general organization of the above system; the second decoder re-uses intermediate results, previously computed by the first one.

Σε αυτή την εργασία μελετάμε τους αλγορίθμους που χρησιμοποιούνται στην αποκωδικοποίηση των LDPC, με έμφαση στους κώδικες του προτύπου 802.11n. Αντιμετωπίζουμε τις δυσκολίες που αντιμετωπίζουν στην υλοποίηση στο υλικό, κυρίως στην εκτέλεση αριθμητικών πράξεων, και προτείνουμε πρακτικές λύσεις. Χρησιμοποιώντας τα αποτελέσματα εκτενών εξομοιώσεων, καταλήγουμε στις βέλτιστες παραμέτρους που θα έχουν οι προτεινόμενες υλοποιήσεις. / In this thesis, we study the LDPC decoding algorithms, with emphasis on the 802.11n standard codes. We tackle the hardware implementation difficulties, especially those related to arithmetic computations, and propose practical solutions. Leveraging the results of extensive simulations, we find the optimal parameters of the proposed implementations.

Στη σύγχρονη εποχή η ανάγκη για αξιοπιστία των δεδομένων στις νέες τηλεπικοινωνιακές εφαρμογές έχει οδηγήσει στη ανάπτυξη και βελτιστοποίηση των λεγόμενων κωδικών διόρθωσης λαθών. Πρόκειται για συστήματα που έχουν την δυνατότητα ανίχνευσης και διόρθωσης λαθών που εισέρχονται σε τμήμα της πληροφορίας που μεταφέρεται μέσω τηλεπικοινωνιακών κυρίως δικτύων λόγω του θορύβου από το περιβάλλον και πιο συγκεκριμένα από το κανάλι μετάδοσης. Υπάρχουν αρκετές κατηγορίες από τέτοιους κώδικες διόρθωσης ανάλογα της δομής και της φύσης των αλγορίθμων που χρησιμοποιούν. Οι δύο κυριότερες κατηγορίες είναι οι συνελικτικοί κώδικες και οι γραμμικοί μπλοκ κώδικες με τους οποίους θα ασχοληθούμε.Οι δύο κώδικες που θα χρησιμοποιηθούν στα πλαίσια αυτής της εργασίας είναι οι κώδικες LDPC και οι BCH. Ανήκουν και οι δυο στους γραμμικούς μπλοκ κώδικες. Σκοπός της παρούσας διπλωματικής εργασίας αποτελεί αρχικά ο σχεδιασμός και η υλοποίηση ενός παραμετρικού συστήματος κωδικοποίησης και αποκωδικοποίησης για δυαδικούς BCH κώδικες διαφόρων μεγεθών. Εκτός της παραμετροποίησης έμφαση δόθηκε στην χαμηλή πολυπλοκότητα του συστήματος, στον υψηλό ρυθμό επεξεργασίας και στην δυνατότητα χρήσης shortening. Σε δεύτερη φάση πραγματοποιήθηκε σύνδεση μεταξύ, του παραπάνω κώδικα BCH, με έναν έτοιμο κώδικα LDPC και ένα κανάλι λευκού προσθετικού θορύβου (AWGN) που σχεδιάστηκαν στα πλαίσια άλλων διπλωματικών εργασιών με τελικό αποτέλεσμα την μελέτη της συμπεριφοράς του συνολικού συστήματος σε θέματα διόρθωσης λαθών και πιο συγκεκριμένα στην μείωση του φαινομένου του error-floor που παρατηρείται στον LDPC κώδικα. Επιπλέον μελετήθηκε η απαίτηση του συστήματος σε πόρους καθώς και ο ρυθμός επεξεργασίας που επιτυγχάνεται. Οι κύριες παράμετροι του κώδικα BCH που μπορούν να μεταβληθούν είναι το μέγεθος της κωδικής λέξης και η διορθωτική ικανότητα που επιτυγχάνεται. / -

Στο πρώτο μέρος της παρούσας Διπλωματικής Εργασίας εισάγονται οι βασικές έννοιες της Θεωρίας Κωδικοποίησης και των Τηλεπικοινωνιακών Συστημάτων. Για τη διόρθωση λαθών στην περίπτωση της μετάδοσης μέσω ενός θορυβώδους καναλιού εφαρμόζεται κωδικοποίηση καναλιού με Γραμμικούς Μπλοκ Κώδικες, και πιο συγκεκριμένα Κώδικες Χαμηλής Πυκνότητας Ελέγχου Ισοτιμίας (Low-Density Parity-Check Codes, LDPC). Ορίζεται η μαθηματική περιγραφή των κωδίκων αυτών και διατυπώνονται σχετικοί ορισμοί και θεωρήματα. Επίσης, διατυπώνεται το κριτήριο Μέγιστης Πιθανοφάνειας, στο οποίο βασίζεται η ανάπτυξη του αντίστοιχου αποκωδικοποιητή. Το δεύτερο μέρος περιλαμβάνει την εξομοίωση του αποκωδικοποιητή Μέγιστης Πιθανοφάνειας στο λογισμικό και την υλοποίησή του σε FPGA, στις περιπτώσεις όπου χρησιμοποιούνται Soft ή Hard είσοδοι στον αποκωδικοποιητή. Ακόμη, παρουσιάζεται η Αρχιτεκτονική του αποκωδικοποιητή και η Μεθοδολογία Σχεδίασής του. Παρουσιάζονται βελτιώσεις στη σχεδίαση του αποκωδικοποιητή που οδηγούν σε μείωση της απαιτούμενης επιφάνειας στο υλικό. Τα αποτελέσματα που προκύπτουν από τις μετρήσεις των δύο υλοποιήσεων συγκρίνονται με την περίπτωση αποκωδικοποιητή βασισμένο σε επαναλήψεις και εξάγονται τα διαγράμματα ρυθμού σφαλμάτων bit και τα αντίστοιχα συμπεράσματα. / In the first part of this thesis, the basic principles of Coding Theory and Communication Systems are introduced. In order to correct errors in the case of transmission through a noisy channel, channel coding with Linear Block Codes is applied, and more specifically Low-Density Parity-Check (LDPC) codes. The mathematical description of such codes is defined and useful definitions and theorems are specified. In addition, the Maximum Likelihood (ML) criterion is specified, on which the development of the relevant decoder is based. The second part consists of the simulation of the ML decoder in software and its hardware implementation on FPGA, in the cases where either Soft or Hard information is used as the decoder's input. Furthermore, the decoder's Architecture and the Design Methodology used are presented. Improvements concerning the implementation of the decoder are introduced, which lead to a reduction in the required area on chip. The experimental results of the two implementations are compared to the case of the iterative decoder and the Bit Error Rate plots are produced, as well as the appropriate conclusions.