Τα τελευταία χρόνια ο όγκος των δεδομένων που διακινείται μέσω δικτυακών συστημάτων είναι συνεχώς αυξανόμενος με την επιτακτική ανάγκη για αξιόπιστη επικοινωνία. Παρόλο που η εξέλιξη της τεχνολογίας επιτρέπει μεγαλύτερη ανοχή σε παρεμβολές στο τηλεπικοινωνιακό κανάλι, ο υψηλότερος ρυθμός δεδομένων προκαλεί παραμορφώσεις στο σήμα και κάνει το τηλεπικοινωνιακό σύστημα πιο επιρρεπές στον θόρυβο. Παράδειγμα τέτοιων συστημάτων αποτελούν εφαρμογές ασύρματων δικτύων όπως τα συστήματα κινητής τηλεφωνίας, οι δορυφορικές επικοινωνίες, ασύρματα τοπικά δίκτυα WiFi καθώς και ενσύρματων επικοινωνιών (ενσύρματα Modem). Η παρούσα διπλωματική επικεντρώνεται στα πρότυπα 802.11 που αφορούν ασύρματα τοπικά δίκτυα και πιο συγκεκριμένα στο πρόσφατο 802.11ac ώστε να τεθούν συγκεκριμένα κριτήρια απόδοσης. Αφενός γίνεται σχεδιασμός και υλοποίηση ενός αποκωδικοποιητή σύμφωνου με το πρότυπο λαμβάνοντας υπόψη περιορισμούς χρονισμού αλλά και επιφάνειας και επαλήθευση αυτών μέσω τεχνολογιών FPGA και ASIC. Αφετέρου μελετώνται διαφορετικές αρχιτεκτονικές υλοποίησης του αλγορίθμου (πχ high radix) και εξετάζονται τα πιθανά σχεδιαστικά trade-off. Εξετάζονται μέθοδοι αύξησης του throughput αλλά και θέματα απόδοσης που αφορούν την ικανότητα διόρθωσης λαθών. / In recent years the volume of data handled by network systems is growing with the need for reliable communication . Although the evolution of technology allows greater tolerance to interference in the telecommunication channel , higher data rate causes distortion to the signal and makes the telecommunication system more susceptible to noise. Examples of such systems are applications of wireless networks such as cellular systems , satellite communications , wireless local area networks WiFi and wired communications ( wired Modem). This thesis focuses on the 802.11 standards regarding wireless LANs and in particular in recent 802.11ac to put specific performance criteria. First is design and implementation of a decoder conforming to the model taking into account timing and surface constraints and verification technologies through FPGA and ASIC. Secondly, different architectures of the algorithm ( eg high radix) are studied and the possible design trade-off is examined. Methods of increasing the throughput and performance issues relating to error correction capability are examined.

Η διόρθωση λαθών με κώδικες LDPC είναι μεγάλου ενδιαφέροντος σε σημαντικές νέες τηλεπικοινωνιακές εφαρμογές, όπως δορυφορικό Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) και IEEE 802.16 (WiMAX). Οι κώδικες LDPC ανήκουν στην κατηγορία των γραμμικών μπλοκ κωδικών. Πρόκειται για κώδικες ελέγχου και διόρθωσης σφαλμάτων μετάδοσης, με κυριότερο χαρακτηριστικό τους τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check), από τον οποίο και πήραν το όνομά τους. Η αποκωδικοποίηση γίνεται μέσω μιας επαναληπτικής διαδικασίας ανταλλαγής πληροφορίας μεταξύ δύο τύπων επεξεργαστικών μονάδων. Η υλοποίηση σε υλικό των LDPC αποκωδικοποιητών αποτελεί ένα ραγδαία εξελισσόμενο πεδίο για τη σύγχρονη επιστημονική έρευνα. Σκοπός της παρούσας διπλωματικής εργασίας υπήρξε ο σχεδιασμός, η υλοποίηση και η βελτιστοποίηση αρχιτεκτονικών αποκωδικοποιητών VLSI για κώδικες LDPC. Έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Μελετήθηκαν αρχιτεκτονικές βασισμένες σε δύο αλγόριθμους, τον log Sum-Product και τον Min-Sum. Ο πρώτος είναι θεωρητικά βέλτιστος, αλλά ο Min-Sum είναι αρκετά απλούστερος και έχει μεγαλύτερο πρακτικό ενδιαφέρον στα πλαίσια μιας ρεαλιστικής εφαρμογής. Συγκεκριμένα, αναπτύχθηκαν δύο αλγόριθμοι αποκωδικοποίησης, οι οποίοι χρησιμοποιούν ως δομικά στοιχεία, τους δύο προαναφερθέντες αλγορίθμους και τη φιλοσοφία του layered decoding. Η μελέτη μας επικεντρώθηκε σε κώδικες, η δομή των πινάκων ελέγχου ισοτιμίας των οποίων, προσφέρεται για υλοποίηση. Για αυτό το λόγο, χρησιμοποιήσαμε κώδικες του προτύπου WiMax 802.16e. Η συνεισφορά της παρούσας εργασίας έγκειται στο σχεδιασμό και την υλοποίηση αποδοτικών αρχιτεκτονικών σε επίπεδο επιφάνειας και ταχύτητας αποκωδικοποίησης (Mbps), καθώς και η διερεύνηση του σχετικού σχεδιαστικού χώρου, χρησιμοποιώντας ως σχεδιαστικές παραμέτρους, τον αλγόριθμο αποκωδικοποίησης, τη χρονοδρομολόγηση των πράξεων, το βαθμό παραλληλίας της αρχιτεκτονικής, το βάθος του pipelining και την αριθμητική αναπαράσταση των δεδομένων. Επιπλέον, είναι σημαντικό να αναφέρουμε πως, στα πλαίσια της σχεδίασης του LDPC αποκωδικοποιητή και με τη βοήθεια του εργαλείου Matlab, αναπτύχθηκαν παραμετρικά scripts για την παραγωγή του VHDL κώδικα. Οι δύο βασικές παράμετροι που χρησιμοποιήθηκαν ήταν το πλήθος των επεξεργαστικών μονάδων και το μήκος λέξης των δεδομένων. Τα scripts αυτά αποτέλεσαν ένα πολύ χρήσιμο εργαλείο κατά τη διαδικασία ανάπτυξης και βελτιστοποίησης της αρχιτεκτονικής, δίνοντας μας τη δυνατότητα να παράγουμε με αυτοματοποιημένο και γρήγορο τρόπο τον VHDL κώδικα, για τις επιμέρους μονάδες του αποκωδικοποιητή. Η υλοποίηση ενός μοντέλου αποκωδικοποιητή σε υλικό, μας δίνει τη δυνατότητα να διεξάγουμε ταχύτατες εξομοιώσεις, σε σχέση με αντίστοιχες υλοποιήσεις σε λογισμικό (π.χ. σε Matlab περιβάλλον). Διαθέτουμε, έτσι, ένα ισχυρό εργαλείο για τη μελέτη της επίδοσης διαφόρων ρεαλιστικών υλοποιήσεων αποκωδικοποιητών. Κατά τη διάρκεια της υλοποίησης, αξιοποιήθηκε αναπτυξιακό σύστημα βασισμένο σε virtex-4 fpga. / LDPC (low-density parity-check) codes are widely applied for error correction, in the development of highly efficient modern digital communication systems, as satellite Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) and IEEE 802.16 (WiMax). LDPC codes are linear block codes, characterized by a sparse parity-check matrix. They are error detection and correction codes. The most typical decoding procedure is the message passing algorithm that implements the iterative exchange of node-generated messages between two types of processing units, called check and variable nodes. Hardware implementation of an LDPC decoder is a fast growing field for contemporary scientific research. This work presents the results of the design, implementation and optimization of a VLSI decoder for LDPC codes. Several iterative decoding algorithms have been developed. At this work we present architectures based on the log Sum-Product (Log-SP) and Min-Sum algorithm. Log-SP is theoretically optimal; however Min-Sum is substantially simpler and reduces the hardware complexity. Two alternative decoding algorithms have been developed, that use these two algorithms for the check-node LLR update, and the philosophy of layered decoding for the exchange of messages. Our study focused on WiMax 801.16e LDPC codes, whose form, based on permuted identity matrices, is suitable for a hardware realization. The contribution of this work lays within the design and implementation of area and decoding throughput efficient architectures, as well a detailed investigation of design space, using decoding algorithm, message exchange scheduling, pipelining and quantization schemes as design parameters. Furthermore, important to mention is, -the development of parametric Matlab scripts, in order to achieve easy and automated structural VHDL code production. The two key parameters are the number of the processing units and the data length. A hardware realization of a LDPC decoder, gives us a simulation tool that is much faster than corresponding software implementations (for example, a matlab implementation). During the implementation procedure, development board based in virtex-4 fpga has been used.

Σε αυτή τη διπλωματική εργασία υλοποιήθηκε ένας LDPC αποκωδικοποιητής που χρησιμοποιεί τις βασικές αρχές της turbo αποκωδικοποίησης, εισάγοντας στα χαρακτηριστικά της αποκωδικοποίησης του το διάγραμμα trellis. O maximum a posteriori probability (MAP) αλγόριθμος χρησιμοποιείται σαν μια γέφυρα μεταξύ των LDPC και Turbo κωδικών. Οι LDPC κώδικες αντιμετωπίζονται ως μια αλυσιδωτή σύνδεση n υπέρ κωδικών, όπου ο κάθε υπέρ κώδικας έχει πλέον μια πιο απλή δομή trellis ώστε ο MAP αλγόριθμος να μπορεί να εφαρμοστεί. / In this thesis an LDPC decoder is implemented using the principles of turbo decoding, introducing the characteristics of the decoding of the trellis diagram . The maximum a posteriori probability (MAP) algorithm is used as a bridge between the LDPC and Turbo codes. The LDPC codes are treated as concatenated n supercodes, where each code has a simple trellis structure so that the MAP algorithm can be implemented.

Σε αυτήν την διπλωματική εργασία ασχοληθήκαμε με την υλοποίηση των κριτηρίων έγκυρου τερματισμού του Turbo αποκωδικοποιητή σε συσκευή FPGA. Στο πρώτο κεφάλαιο παρουσιάζουμε το θεωρητικό υπόβαθρο που περιλαμβάνει βασικές έννοιες των ψηφιακών επικοινωνιών και την μαθηματική υποστήριξη του turbo κώδικα. Στο δεύτερο κεφάλαιο παρουσιάζονται τα αποτελέσματα της εξομοίωσης του κώδικα. Στο τρίτο κεφάλαιο παρουσιάζεται αρχιτεκτονική του κυκλώματος που υλοποιεί τον turbo κώδικα τόσο από την πλευρά του κωδικοποιητή όσο και από την πλευρά του αποκωδικοποιητή. Εν συνεχεία, στο κεφάλαιο 4 παρουσιάζεται το προτεινόμενο κριτήριο τερματισμού μαζί με την δική του υλοποίηση καθώς και την υλοποίηση τριών άλλων κριτηρίων. Στο τέλος παρουσιάζουμε τα συμπερασματά μας και τις μετρήσεις μας. / In this thesis we studied the implementation of the termination criteria of the turbo decoder as well as its implementation on the hardware. In the first chapter an introduction to fundamental concepts of digital communication as well as their mathimatical expression. In the second chapter the results of the simulation of the code are presented. In the third chapter the architecture of the turbo encoder and decoder are presented. In the fourth chapter a new termination criterion is presented with the implementation of tree other criteria. Finally we present our conclusions and our measurements.