Σήμερα, σε όλα σχεδόν τα τηλεπικοινωνιακά συστήματα τα οποία προορίζονται για αποστολή δεδομένων σε υψηλούς ρυθμούς, έχουν υιοθετηθεί κώδικες διόρθωσης λαθών για την αύξηση της αξιοπιστίας τους και τη μείωση της απαιτούμενης ισχύος εκπομπής τους. Οι κώδικες αυτοί δίνουν τη δυνατότητα ανίχνευσης και διόρθωσης των λαθών που μπορεί να δημιουργήσει το μέσο μετάδοσης (κανάλι) σε κάποιο τμήμα πληροφορίας που μεταφέρεται μέσω του τηλεπικοινωνιακού δικτύου. Μία κατηγορία τέτοιων κωδίκων, και μάλιστα με εξαιρετικές επιδόσεις, είναι η οικογένεια των LDPC (Low Density Parity Check) κωδίκων. Πρόκειται για γραμμικούς μπλοκ κώδικες, με απόδοση πολύ κοντά στο όριο Shannon. Στην παρούσα διπλωματική μελετώνται οι κώδικες LDPC και σχετικές αρχιτεκτονικές υλικού. Oι κώδικες LDPC χρησιμοποιούνται όλο και περισσότερο σε εφαρμογές που απαιτούν αξιόπιστη και υψηλής απόδοσης μετάδοση, υπό την παρουσία ισχυρού θορύβου. Η κατασκευή τους στηρίζεται στη χρήση πινάκων ελέγχου ισοτιμίας χαμηλής πυκνότητας, ενώ η αποκωδικοποίηση εκτελείται με τη χρήση επαναληπτικών αλγορίθμων. Σε υψηλά επίπεδα θορύβου παρουσιάζουν πολύ καλή διορθωτική ικανότητα, αλλά υστερούν σε χαμηλότερα επίπεδα θορύβου, όπου υποφέρουν από το φαινόμενο του error floor. Στη συγκεκριμένη εργασία μελετάται εκτενώς μία αλγεβρική μέθοδος για την κατασκευή regular LDPC κωδίκων που βασίζεται σε κώδικες Reed-Solomon με δύο σύμβολα πληροφορίας. Η μέθοδος αυτή μας επιτρέπει την κατασκευή ενός πίνακα ελέγχου ισοτιμίας Η για τον κώδικα LDPC, όπου το διάγραμμα Tanner που του αντιστοιχεί δεν περιέχει κύκλους μήκους 4 (ελάχιστο μήκος κύκλου 6). Οι κύκλοι μικρού μήκους στο διάγραμμα Tanner «εγκλωβίζουν» τον αποκωδικοποιητή σε καταστάσεις που δεν μπορεί να ανιχνεύσει και να διορθώσει τα λάθη που δημιουργήθηκαν στη μετάδοση. Έτσι χρησιμοποιώντας την παραπάνω μέθοδο μπορούμε να κατασκευάσουμε απλούς σε δομή κώδικες, που σε συνδυασμό με τους επαναληπτικούς αλγορίθμους αποκωδικοποίησης οδηγούν σε αποκωδικοποιητές με εξαιρετικές διορθωτικές ικανότητες και εμφάνιση error floor σε πολύ χαμηλές τιμές του BER. Ακόμα, αυτού του τύπου οι πίνακες ισοτιμίας επιβάλλουν μία συγκεκριμένη δομή για το γεννήτορα πίνακα G που χρησιμοποιείται για την κωδικοποίηση. Για το λόγο αυτό μελετάται επίσης ο τρόπος για να κατασκευάσουμε ένα συστηματικό πίνακα G, ο οποίος απλουστεύει κατά πολύ τη διαδικασία της κωδικοποίησης. Όλες οι παραπάνω διαδικασίες εφαρμόζονται για την κατασκευή του κώδικα (2048,1723) RS-LDPC. Πρόκειται για έναν κώδικα ρυθμού 0,84 που χρησιμοποιείται από το πρότυπο 802.3an της IEEE για το 10GBASE-T Ethernet και παρουσιάζει ιδιαίτερο ενδιαφέρον λόγω των επιδόσεών του. Για τον κώδικα αυτό προτείνεται σχεδίαση για τον κωδικοποιητή και τον αποκωδικοποιητή καθώς και για όλα τα εξωτερικά κυκλώματα που απαιτούνται ώστε να δημιουργηθεί ένα ολοκληρωμένο σύστημα αποστολής, λήψης και διόρθωσης δεδομένων. Έχοντας όλο το υπόβαθρο για την κατασκευή ενός RS-LDPC συστήματος κωδικοποίησης-αποκωδικοποίησης, υλοποιήσαμε τη σχεδίαση του συστήματος σε κώδικα VHDL ενώ εκτελέστηκαν οι απαραίτητες εξομοιώσεις (Modelsim). Στη συνέχεια εκτελέστηκαν οι διαδικασίες της σύνθεσης (εργαλείο XST του Xilinx ISE) και της πλήρους υλοποίησης σε fpga (Virtex 5 XC5VLX330T-1FF1738), δίνοντας μας έτσι τη δυνατότητα διεξαγωγής ταχύτατων εξομοιώσεων ειδικά σε χαμηλά επίπεδα θορύβου σε σχέση με τις αντίστοιχες υλοποιήσεις σε λογισμικό (MATLAB). Πραγματοποιώντας πειράματα στο υλικό παρατηρούμε τη διορθωτική ικανότητα του αλγορίθμου αποκωδικοποίησης και συγκρίνουμε τα αποτελέσματα με αυτά των υλοποιήσεων σε λογισμικό. Επίσης μελετάται ο τρόπος μεταβολής της διορθωτικής ικανότητας του αλγορίθμου ανάλογα με τον αριθμό των επαναλήψεων που εκτελεί. Τέλος, πήραμε κάποιες μετρήσεις για το throughput του αποκωδικοποιητή, ώστε σε περίπτωση που θέλουμε να πετύχουμε ένα συγκεκριμένο ρυθμό επεξεργασίας δεδομένων να μπορούμε να υπολογίσουμε τον αριθμό των αποκωδικοποιητών που θα χρειαστούμε. / Nowadays, almost every telecommunication system that aims to achieve high transmission rates has adopted error correction codes in order to increase its reliability while decreasing the required power of transmission. The information signal is transmitted over a communication channel with the presence of noise. Error correction codes allow systems to detect and correct errors that occurred to the information signal due to the noise. LDPC (Low Density Parity Check) codes compose a large family of error correcting linear block codes with great performance, close to the Shannon limit. In this thesis we analyze LDPC codes and the corresponding hardware designs. LDPC codes are used in applications that require reliable and highly efficient transmission under high levels of noise. Any LDPC code is fully defined by a sparse parity-check-matrix and all of them use iterative belief propagation techniques for the decoding process. In general, LDPC codes perform very well in high levels of noise, but in very low levels they suffer from “error floor” effect. First we present a thorough analysis of an algebraic method for constructing regular LDPC codes based on Reed-Solomon codes with two information symbols. This construction method results in a class of LDPC codes which are free of cycles of length 4 in their Tanner graphs (so the girth of their Tanner graphs is at least 6). The existence of circles with length 4 in the Tanner graph “traps” the decoder in states that it cannot detect and correct any error occuring in the transmitted codeword. So by using the previous constructing method we can create simply structured codes which, combined with iterative decoding algorithms, may provide decoders with great performance and error floor at very low levels of BER. Furthermore, this type of decoders requires that the generator matrix G used for the encoding process of the system must have specific structural properties. For this reason we are going to study the way of constructing a proper systematic generator matrix which also simplifies the decoding process. All the previous stages are carried out in order to construct the (2048, 1723) RS-LDPC code. This code was adopted in 802.3an IEEE standard for the 10GBASE-T and is of high interest due to its remarkable efficiency. For this code we demonstrate a specific implementation for the encoder, decoder and all the additional components required in order to design a complete transmitter-receiver system, coupled with error correction capabilities. We utilize the above mentioned background so as to implement our design in VHDL code and run the proper simulations (Modelsim tool). Later on we synthesized (XST tool, Xilinx ISE) and implemented our design on an fpga board (Virtex 5 XC5VLX330T-1FF1738). This enabled us to accomplish rapid simulation times, especially under low level of noise in contrast to the corresponding software implementations (MATLAB). We evaluate the error correction capability of the decoding algorithm by running experiments in hardware and we compare these results with software implementations. Moreover we observe how the effectiveness of the decoding algorithm is affected by its number of iterations. Finally, we measure the decoder throughput so that in case we want to achieve a specific decoding rate we are able to estimate the required number of decoders for this rate.

Σε μία εποχή όπου η ψηφιοποίηση δεδομένων έχει αυξηθεί ραγδαία η ανάγκη για τη βέλτιστη μετάδοσή τους είναι απαραίτητη. Από τα πλέον σημαντικά μέρη των προτύπων μετάδοσης είναι η κωδικοποίηση του καναλιού μέσω ειδικών αλγορίθμων ώστε να επιτευχθεί η εύρεση και διόρθωση τυχών λαθών. Οι κώδικες Bose, Chaudhuri και Hocquenghem (BCH) είναι τέτοιου είδους κώδικες που χρησιμοποιούνται ευρέως σε εφαρμογές όπως τα CD, DVD, σκληροί δίσκοι, δίσκοι στερεάς κατάστασης (SSD) και το πρότυπο δορυφορικής μετάδοσης τηλεόρασης υψηλής ανάλυσης (HDTV), DVB-S2. Στην παρούσα διπλωματική εργασία σχεδιάστηκε και υλοποιήθηκε κωδικοποιητής και αποκωδικοποιητής BCH για τις 11 περιπτώσεις κανονικού πλαισίου που προσφέρει το πρότυπο DVB-S2. Κύριος στόχος ήταν η όσο το δυνατόν καλύτερη υλοποίηση με γνώμονα το μέγεθος, με τη χρήση κοινών κυκλωμάτων και για τις 11 περιπτώσεις. Αποτέλεσμα αυτής της βελτιστοποίησης μεγέθους, ήταν κάποιες τεχνικές βελτιστοποίησης της ταχύτητας αποκωδικοποίησης, όπως το shortening, να μη χρησιμοποιηθούν καθώς θα είχαν ως αποτέλεσμα την αύξηση της επιφάνειας μερών του αποκωδικοποιητή κατά περίπου 11 φορές. Καθώς σκοπός της διπλωματικής ήταν η μελέτη της απόδοσης των κωδίκων BCH, μελετήθηκε ο ρυθμός λαθών σε διάφορες τιμές της αναλογίας ενέργειας – θορύβου (Eb / N0 ), αφού πρώτα υλοποιήθηκε σε FPGA. / The amount of digital information is growing rapidly the recent decades, making transmission optimization one of the top priorities in digital information systems. One of the main parts of every transmission standard is channel encoding, with the use of algorithms aimed at finding and correcting errors (Forward Error Correction – FEC). Such codes are Bose, Chaudhuri and Hocquenghem (BCH) code, which are widely used in applications like CDs, DVDs, Hard Drives, Solid State Drives (SSDs) and DVB-S2, a satellite transmission standard mostly used for High Definition Television (HDTV). This thesis sets out to account for the design and implementation of a BCH encoder and decoder for all 11 different code rates proposed by the DVB-S2 standard for normal frames. The design was area optimized in order for all 11 code rate encoders and decoders to work on the same FPGA. This lead to some optimization techniques being unused. Even though the codes are shortened, no shortening algorithms which aim at clock cycle optimization were used. Were they used, would lead parts of the decoder to be almost 11 times larger. The main goal of the thesis is to analyze the performance of the codes, so the error rate was measured under different values of the energy to noise ratio (Eb/ N0 ).

Η εργασία αφορά ένα ειδικό είδος κωδικοποίησης εντοπισμού και διόρθωσης λαθών, την κωδικοποίση Reed-Solomon. Οι κώδικες αυτού του είδους χρησιμοποιούνται σε τηλεπικοινωνιακές εφαρμογές (ενσύρματη τηλεφωνία, ψηφιακή τηλεόραση, ευρυζωνικές ασύρματες επικοινωνίες) και σε συστήματα ψηφιακής αποθήκευσης (οπτικοί, μαγνητικοί δίσκοι). Η κωδικοποίηση Reed-Solomon βασίζεται σε μία ειδική κατηγορία αριθμητικών πεδίων τα πεδία Galois (Galois Field). Στα πλαίσια της εργασίας πραγματοποιήθηκε μελέτη των ιδιοτήτων των πεδίων Galois. και σχεδιάστηκε κωδικοποιητής-αποκωδικοποιητής για κώδικες Reed Solomon. Η σχεδίαση υλοποιήθηκε σε υλικό (hardware) σε γλώσσα Verilog HDL. Η σύνθεση των κυκλωμάτων πραγματοποιήθηκε με τεχνολογία Πεδίων Προγραμματιζόμενων Πινάκων Πυλών (τεχνολογία FPGA) και τεχνολογία Ολοκληρωμένων Κυκλωμάτων Ειδικού Σκοπού (τεχνολογία ASIC). Ακολουθήθηκε η μεθοδολογία σχεδιασμού Μονάδων Διανοητικής Ιδιοκτησίας για ολοκληρωμένα κυκλώματα (IP core), σύμφωνα με την οποία η σχεδίαση είναι ανεξάρτητη της πλατφόμας υλοποίησης και μπορεί να υλοποιηθεί με καθόλου ή ελάχιστες αλλαγές σε διαφορετικές τεχνολογίες. Η έννοια των IP core βρίσκει ιδιαίτερη εφαρμογή σε Συστήματα σε Ολοκληρωμένα Κυκλώματα (System on Chip). / The present work is about a specific group of error detection and correction codes, the Reed-Solomon codes. Such codes are used in telecommunications applications (wire telephony, digital television, broadband wireless communications) and digital storage systems (optical, magnetic disks). The Reed Solomon codes are based on a specific category of numerical fields, called Galois Fields. The Work consists of the study of the properties of Galois fields and of the design of an codec for Reed Solomon codes. The design was implemented in hardware with the use of Verilog HDL language. The synthesis of the circuit targets Field programmable Gate Array (FPGA) and Applications Specific Integrated Circuit (ASIC) technologies. The design methodology for Intellectual Property Units for integrated circuits (IP cores) was used. According to that methodology the design is platform independent and consequently the implementation can be achieved with minimal or no changes in different technologies. The IP cores model is widely applied in Systems on Integrated Circuits (System on Chips).

Αντικείμενο της διπλωματικής εργασίας αποτελεί η μελέτη και ανάλυση των μεθόδων διόρθωσης λαθών με χρήση κώδικα BCH που μπορούν να εφαρμοστούν σε συστήματα αποθήκευσης πληροφορίας τεχνολογίας PCM (Phase-Change Memory). Η τεχνολογία PCM αποτελεί μία νέα τεχνολογία που υπόσχεται υψηλές χωρητικότητες, χαμηλή κατανάλωση ισχύος και μπορεί να εφαρμοστεί είτε σε συσκευές αποθήκευσης σταθερής κατάστασης (Solid State Drives) είτε σε μνήμες τυχαίας προσπέλασης (Random-Access Memories), παρέχοντας μία εναλλακτική πρόταση έναντι μνημών τεχνολογίας flash και DRAM. Ένα από τα μειονεκτήματα της τεχνολογίας PCM είναι η ανθεκτικότητα εγγραφής (write endurance), η οποία μπορεί να βελτιωθεί με τη χρήση μεθόδων διόρθωσης λαθών που θα παρατείνουν τον χρόνο ζωής της συσκευής όταν, λόγω της φυσικής φθοράς του μέσου, αρχίσουν να υπάρχουν σφάλματα στα αποθηκευμένα δεδομένα. Για την εφαρμογή της διόρθωσης λαθών μπορούν να χρησιμοποιηθούν κώδικες BCH, οι οποίοι αποτελούν μια κλάση ισχυρών κυκλικών κωδίκων διόρθωσης τυχαίων λαθών, και κατασκευάζονται με χρήση της άλγεβρας πεπερασμένων πεδίων. Οι κώδικες BCH είναι ιδανικοί για διόρθωση λαθών σε συσκευές αποθήκευσης πληροφορίας όπου η κατανομή των λαθών είναι τυχαία. Αρκετοί αλγόριθμοι έχουν προταθεί για τις λειτουργίες αποδοτικής κωδικοποίησης και αποκωδικοποίησης κωδίκων BCH. Στην παρούσα εργασία μελετήθηκαν λύσεις που μπορούν να υλοποιηθούν με παράλληλες αρχιτεκτονικές, ενώ ειδικότερα για την λειτουργία αποκωδικοποίησης έγινε χρήση ενός παράλληλου αλγορίθμου που δεν χρειάζεται αντιστροφείς πεπερασμένου πεδίου για την επίλυση των εξισώσεων των συνδρόμων, επιτυγχάνοντας υψηλές συχνότητες λειτουργίας. Για την κατανόηση των λειτουργιών κωδικοποίησης και αποκωδικοποίησης απαιτείται η προσεκτική μελέτη της άλγεβρας πεπερασμένων πεδίων και της αριθμητικής της. Οι κώδικες BCH προσφέρουν πλεονεκτήματα όπως χαμηλή πολυπλοκότητα και ύπαρξη αποδοτικών μονάδων υλοποίησης σε υλικό. Στην παρούσα εργασία σχεδιάστηκαν ένας παράλληλος κωδικοποιητής και ένας παράλληλος αποκωδικοποιητής για τον κώδικα BCH(728,688). Τα δύο συστήματα υλοποιήθηκαν ως περιφερειακά σε ενσωματωμένο σύστημα βασισμένο σε επεξεργαστή MicroBlaze, με έμφαση σε μια καλή σχέση μεταξύ της συχνότητας λειτουργίας και των απαιτήσεων σε επιφάνεια υλικού και κατανάλωση ισχύος. Για την υλοποίηση χρησιμοποιήθηκε συσκευή FPGA σειράς Virtex-6. / The objective of this thesis is the study and analysis of BCH error-correction methods that can be applied on PCM (Phase-Change Memory) storage devices. PCM is a new technology that promises high capacities, low power consumption and can be applied either on Solid State Drives or on Random Access Memories, providing an alternative to flash and DRAM memories. However, PCM suffers from limited write endurance, which can be increased using error-correction schemes that will extend the lifetime of the device when, due to medium wear-out, errors start to appear in the written data. Thus, BCH codes (powerful cyclic random multiple error-correcting codes) can be employed. BCH codes are ideal for ECC (Error-Correction Coding) in storage devices, due to their fault model which is random noise. Several algorithms have been proposed for the efficient coding and decoding BCH codes. In the present thesis parallel implementations where studied. For the decoding process in particular, a parallel algorithm was used that does not require finite field inverter units to solve the syndrome equations, achieving high operation frequencies. For the understanding of BCH coding and decoding processes, basic knowledge of the finite field algebra and arithmetic is required. BCH codes offer advantages such as low complexity and efficient hardware implementations. In the present thesis a parallel BCH(728,688) encoder and a parallel BCH(728,688) decoder were designed. The above systems were implemented as peripherals on an MicroBlaze-based embedded system, with emphasis on an optimal tradeoff between area and power consumption. A Virtex-6 FPGA device was used for the final stages of the implementation.