Η διπλωματική εργασία επικεντρώνεται στη μελέτη της κωδικοποίησης για κώδικες LDPC. Στα πλαίσιά της, θα μελετηθούν τα προβλήματα και η πολυπλοκότητα κωδικοποίησης συναρτήσει του μήκους της κωδικής λέξης. Έμφαση θα δοθεί σε εφαρμογές με μεγάλο μήκος κωδικής λέξης όπως εκείνες που χρησιμοποιούνται σε νέες τηλεπικοινωνιακές εφαρμογές, όπως δορυφορικό Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) και IEEE 802.16(WiMAX). Σε τέτοιες εφαρμογές όπου η κωδική λέξη μπορεί να έχει μήκος αρκετά μεγαλύτερο των 1000 bits, η πολυπλοκότητα κωδικοποίησης είναι σημαντική. Αυτό συμβαίνει διότι απαιτούνται μεγάλες σε μέγεθος μνήμες για την αποθήκευση του Πίνακα Έλεγχου Ισοτιμίας (Parity-check Matrix H), πολύ μεγάλη χρονική επεξεργαστική πολυπλοκότητα O(n^2) αλλά και πολλά επεξεργαστικά στοιχεία τάξης Ο(n^2). Ο σκοπός λοιπόν είναι να μελετηθούν οι αλγόριθμοι κωδικοποίησης και να μελετηθεί πώς μπορεί να αξιοποιηθεί η αραιότητα του Πίνακα Έλεγχου Ισοτιμίας έτσι ώστε να επιτευχθεί κατά το δυνατόν γραμμική πολυπλοκότητα O(n) κωδικοποίησης. Στη συνέχεια, αφού αναπτυχθεί η κατάλληλη μέθοδος κωδικοποίησης, θα ακολουθήσει η μελέτη και ο σχεδιασμός μίας βέλτιστης VLSI αρχιτεκτονικής για την υλοποίηση σε υλικό του LDPC κωδικοποιητή, ώστε να ικανοποιεί και άλλα πρακτικά κριτήρια, με έμφαση στη μείωση της καθυστέρησης και της απαιτούμενης επιφάνειας. Θα αναπτυχθεί επίσης μια κατάλληλη αρχιτεκτονική για διάφορους βαθμούς παραλληλίας του κωδικοποιητή. / An LDPC code is a linear block code specified by a very sparse parity check matrix (PCM). LDPC codes are usually represented by a bi-partite graph in which a variable node corresponds to a ’coded bit’ or a PCM column, and a check node corresponds to a parity check equation or a PCM row. There is an edge between each pair of nodes if there is a ’one’ in the corresponding PCM entry. In a general analysis an (n, k) LDPC code has k information bits and n coded bits with code rate r = k/n. An important issue in the implementation of LDPC-code based forward error correction systems is the encoding of LDPC codes. Generally, LDPC codes cannot have the simple encoding structures based on of shift registers as in the case of convolutional, turbo codes, or cyclic block codes. However, general LDPC codes do not fall in this category. Except QC-cyclic LDPC codes, most efficient LDPC codes, especially irregular LDPC codes are hard to encode with the idea of shift registers. A straightforward way is to derive a systematic generator matrix from a PCM, and then to encode LDPC code systematically with the generator matrix. This can work for every LDPC code in theory, but practically it is a very bad idea because it has high complexity, as the generator matrix derived from parity-check matrix is not sparse contrasted to the PCM. Generator matrix can be very dense matrix. The objective is to utilize the sparseness to achieve LDPC encoding in linear time. This Master’s thesis presents a flexible encoder architecture using QC-cyclic LDPC codes and efficient two-step encoding algorithm in order to achieve linear time encoding. The particular approach considers several VLSI design issues of LDPC encoder. In particular efficient approaches are presented for reducing memory requirements, for reducing hardware complexity, and increasing the speed and throughput of LDPC encoding. The proposed structure is also generic and scalable, supporting multiple configurations, in terms of bits per symbol and code rate. A generic scalable processing unit is also presented. It supports LDPC codes that define parity check matrix as a combination of identity matrix, shifted identity matrix and all-zero matrix (QC-cyclic LDPC codes). The particular LDPC encoder architecture is synthesized and experimental results are reported.

Σήμερα οι απαιτήσεις τόσο σε όγκο πληροφορίας προς μετάδοση όσο και της αξιόπιστης μετάδοσης και προστασίας της πληροφορίας είναι ιδιαίτερα υψηλές. Καθοριστικό ρόλο σε αυτό παίζει το αντικείμενο της Αναγνώρισης και Διόρθωσης Λαθών με τους κώδικες διόρθωσης λαθών που βρίσκονται σε κάθε πλευρά της καθημερινής και όχι μόνο ζωής οι οποίοι προστατεύουν από την αλλοίωση των δεδομένων και χρησιμοποιούνται για παράδειγμα σε συσκευές αποθήκευσης, κινητή τηλεφωνία, ασύρματα δίκτυα και επεκτείνονται μέχρι και στην δορυφορική επικοινωνία. Οι κώδικες LDPC είναι μια τέτοια κατηγορία κωδίκων με ποικίλες εφαρμογές και συγκαταλέγονται ανάμεσα στους καλύτερους του πεδίου της Αναγνώρισης και Διόρθωσης Λαθών. Όμως για να προστατευθεί το αναλλοίωτο της πληροφορίας είναι απαραίτητη η αξιόπιστη και επιτυχής αποκωδικοποίηση μετά τη λήψη των δεδομένων. Το πρόβλημα στην επαναληπτική αποκωδικοποίηση κωδίκων LDPC εμφανίζεται όταν έχουμε κύκλους στον πίνακα ελέγχου ισοτιμίας και στο γράφημα Tanner και εμφανίζονται κάποιες δομές που ονομάζονται trapping sets, οι οποίες οδηγούν σε διαφορετική από την αναμενόμενη συμπεριφορά της καμπύλης που δίνει το ρυθμό σφάλματος ανά bit. Σε αυτές τις περιπτώσεις η καμπύλη εμφανίζει από ένα σημείο και μετά διαφορετική κλίση από την αναμενόμενη και επηρεάζεται το κατώτατο σφάλμα το οποίο τώρα είναι υψηλότερο. Η μέθοδος που ακολουθήθηκε στη παρούσα εργασία ήταν για την μελέτη των χαρακτηριστικών κωδίκων μέσω της καταμέτρησης των trapping sets. / Today our requirements for reliable transmission of huge amounts of information are very high. The objective of Error Identification and Correction plays an important role in this effort with the use of error correction codes which are present in every aspect of everyday life and beyond for keeping information unchanged. Such examples of their use are storage devices, mobile communication, wireless networks and even satellite communication. LDPC codes are such a category of error correction codes, have many applications and constitute of some of the greatest codes of the field of Error Identification and Correction. But in order to achieve unchanged information after transmission, it is essential that decoding problems which appear must be resolved. The problem with iterative decoding of LDPC codes appears when cycles exist inside the parity check matrix and the Tanner graph and as a result some other structures appear, which are called trapping sets. These trapping sets are responsible for the deviation of the bearing of the graph of bit error rate and error floor. In these cases the graph has a suddenly change in gradient. So the error floor is much higher now. The method used here was the study of characteristics of some codes from counting the trapping sets.

Στο πρώτο μέρος της παρούσας Διπλωματικής Εργασίας εισάγονται οι βασικές έννοιες της Θεωρίας Κωδικοποίησης και των Τηλεπικοινωνιακών Συστημάτων. Για τη διόρθωση λαθών στην περίπτωση της μετάδοσης μέσω ενός θορυβώδους καναλιού εφαρμόζεται κωδικοποίηση καναλιού με Γραμμικούς Μπλοκ Κώδικες, και πιο συγκεκριμένα Κώδικες Χαμηλής Πυκνότητας Ελέγχου Ισοτιμίας (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.