Στην εργασία αυτή μελετώνται τεχνικές διόρθωσης λαθών BCH κωδικοποίησης και η υλοποίηση τους με αρχιτεκτονικές VLSI. Στην αρχή γίνεται μία εισαγωγή στα Συστήματα Ψηφιακής Επικοινωνίας. Αυτή ακολουθείται από μία περιγραφή των μαθηματικών θεωρημάτων και ορισμών που χρησιμοποιούνται για την Διόρθωση Λαθών. Επίσης, παρουσιάζονται οι βασικές Τεχνικές Κωδικοποίησης, δίνοντας ιδιαίτερη έμφαση στην BCH Κωδικοποίηση. Στην συνέχεια παρουσιάζεται η πλατφόρμα εξομοίωσης στο MatLab, και οι συναρτήσεις που την υλοποιούν, για την μέτρηση BER διαφόρων BCH Κωδικών. Κάνοντας χρήση αυτής της πλατφόρμας γίνεται η σύγκριση μεταξύ non-binary και binary BCH Κωδίκων ίδιου code rate καθώς και non-binary BCH Κωδίκων διαφορετικών μηκών και code rate. Στο τελευταίο μέρος της εργασίας, προτείνεται μία γενική αρχιτεκτονική ενός non-binary BCH αποκωδικοποιητή. Βάσει αυτής της προτεινόμενης αρχιτεκτονικής περιγράφεται λεπτομερώς η υλοποίηση ενός αποκωδικοποιητή οκταδικού BCH Κώδικα μήκους 63 συμβόλων και διάστασης 48 συμβόλων με απόσταση σχεδίασης 4 συμβόλων. Τέλος, μετά την παρουσίαση των αποτελεσμάτων της υλοποίησης του συγκεκριμένου αποκωδικοποιητή σε FPGA πλατφόρμα ανάπτυξης, συνοψίζονται τα συμπεράσματα που προέκυψαν από την παραπάνω διαδικασία. / This dissertation refers to BCH error correction coding techniques and their implementation with VLSI architectures. At first, an introduction in the Digital Communications Systems takes place. This is followed by a description of mathematical theorems and definitions used for the error correction coding. In addition, basic coding techniques are presented emphasising in BCH Codes. The dissertation continues with the presentation of the MatLab simulation platform, as well as the functions that implement this, for the BER measurement of various BCH codes. Using this platform, a comparison is made between non binary and binary BCH codes of the same code rate as well as non binary BCH codes of different lengths and code rates. In the last part, a general architecture of a non binary BCH decoder is proposed. According to this architecture, an implementation of an octal BCH 63 symbols length, 48 symbol dimension and 4 symbols design distance code decoder, is described in depth. Finally, after the presentation of the implementation results of the described decoder in FPGA board, the conclusions that came up from the above procedure, are summarised.

Σήμερα, σε όλα σχεδόν τα τηλεπικοινωνιακά συστήματα τα οποία προορίζονται για αποστολή δεδομένων σε υψηλούς ρυθμούς, έχουν υιοθετηθεί κώδικες διόρθωσης λαθών για την αύξηση της αξιοπιστίας τους και τη μείωση της απαιτούμενης ισχύος εκπομπής τους. Οι κώδικες αυτοί δίνουν τη δυνατότητα ανίχνευσης και διόρθωσης των λαθών που μπορεί να δημιουργήσει το μέσο μετάδοσης (κανάλι) σε κάποιο τμήμα πληροφορίας που μεταφέρεται μέσω του τηλεπικοινωνιακού δικτύου. Μία κατηγορία τέτοιων κωδίκων, και μάλιστα με εξαιρετικές επιδόσεις, είναι η οικογένεια των 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. Αφού γίνει μια εισαγωγή στο σύστημα επικοινωνίας, στα πεπερασμένα σώματα και στη θεωρία κωδίκων, παρουσιάζονται αλγόριθμοι που υλοποιούν αποκωδικοποιητές περιορισμένης απόστασης, λίστας και 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.

Σχεδόν όλα τα σύγχρονα τηλεπικοινωνιακά συστήματα, τα οποία προορίζονται για αποστολή δεδομένων σε υψηλούς ρυθμούς, έχουν υιοθετήσει κώδικες διόρθωσης λαθών για την αύξηση της αξιοπιστίας και τη μείωση της απαιτούμενης ισχύος εκπομπής τους. Μια κατηγορία κωδίκων, και μάλιστα με εξαιρετικές επιδόσεις, είναι η οικογένεια των LPDC κωδίκων (Low-Density-Parity-Check codes). Οι κώδικες αυτοί είναι γραμμικοί block κώδικες με απόδοση πολύ κοντά στο όριο του Shannon. Επιπλέον, ο εύκολος παραλληλισμός της διαδικασίας αποκωδικοποίησής τους, τους καθιστά κατάλληλους για υλοποίηση σε υλικό. Στην παρούσα διπλωματική μελετούμε τα ιδιαίτερα χαρακτηριστικά και τις παραμέτρους των κωδίκων αυτών, ώστε να κατανοήσουμε την εκπληκτική διορθωτική ικανότητά τους. Στη συνέχεια, επιλέγουμε μια ειδική κατηγορία κωδίκων LDPC, της οποίας οι πίνακες ελέγχου ισοτιμίας έχουν δημιουργηθεί ώστε να διευκολύνουν την υλοποίησή τους, και προχωρούμε στο σχεδιασμό αυτής σε υλικό. Πιο συγκεκριμένα, υλοποιούμε σε VHDL έναν αποκωδικοποιητή σύμφωνα με τον rate ½ και block_lenght 576 bits πίνακα του προτύπου WiMax 802.16e, με στόχο κυρίως την επίτευξη πολύ υψηλού throughput. Στο χρονοπρογραμματισμό της μετάδοσης των μηνυμάτων μεταξύ των κόμβων του κυκλώματος χρησιμοποιούμε το two-phase scheduling και προτείνουμε δύο τροποποιήσεις αυτού για την επιτάχυνση της διαδικασίας αποκωδικοποίησης, οι οποίες καταλήγουν σε 24 και 50% βελτίωση του απαιτούμενου χρόνου μιας επανάληψης με μηδενική και σχετικά μικρή αύξηση της επιφάνειας ολοκλήρωσης αντίστοιχα. Ο όλος σχεδιασμός είναι πλήρως συνθέσιμος και η σωστή λειτουργία αυτού έχει επιβεβαιωθεί σε επίπεδο λογικής εξομοίωσης. Κατά τη διάρκεια σχεδιασμού, χρησιμοποιήθηκαν εργαλεία της Xilinx και MentorGraphics. / Αlmost all the modern telecommunication systems, which are designed for high data rate transmissions, have adopted error correction codes for improving the reliability and the required power of transmission. One special group of these codes, with extremely good performance, is the LDPC codes (Low-Density-Parity-Check codes). These codes are linear block codes with performance near to the theoretical Shannon limit. Furthermore, the inherent parallelism of the decoding procedure makes them suitable for implementation on hardware. In this thesis, we study the special characteristics of these codes in order to understand their astonishing correcting capability. Then, we choose a special category of these codes, whose parity check matrix are special designed to facilitate their implementation on hardware, and we design a high-throughput decoder. More specifically, we implement in VHDL an LDPC decoder according to the rate ½ and block_length 576 bits code of WiMax IEEE802.16e standard, with main purpose to achieve very high throughput. We use the two-phase scheduling at the message passing and we propose 2 modifications for reducing the required decoding time, which result in 25 and 50% improving of the required decoding time of one iteration with zero and little increasing in the decoder’s area respectively. Our design has been successfully simulated and synthesized. During the design process, we used Xiinx and MentorGraphics’s tools.

Αντικείμενο της διπλωματικής εργασίας αποτελεί η μελέτη και ανάλυση των μεθόδων διόρθωσης λαθών με χρήση κώδικα 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.

Η ενσωμάτωση των κωδίκων Turbo σε ένα ευρύ φάσμα εφαρμογών λόγω της εκπληκτικής αποδόσεώς τους που προσεγγίζει το θεμελιώδες όριο του Shannon, απαιτεί αποδοτικές αρχιτεκτονικές και υλοποιήσεις υψηλού ρυθμού διεκπεραίωσης και χαμηλής κατανάλωσης ενέργειας όσον αφορά την εξαιρετικά πολύπλοκη και χρονοβόρα επαναληπτική αποκωδικοποίησή τους. Η παρούσα διδακτορική διατριβή μελετά την χρήση της τεχνολογίας Πυριτίου-Γερμανίου (SiGe) BiCMOS σε αναλογικές αρχιτεκτονικές για την υλοποίηση αποκωδικοποιητών Turbo υψηλού ρυθμού διεκπεραίωσης και όσο το δυνατόν χαμηλής κατανάλωσης ισχύος. Η σχεδίαση βάσει των διπολικών τρανζίστορ ετεροεπαφής προσδίδει ιδιαίτερα υψηλή ταχύτητα στην απόκριση του αναλογικού συστήματος σε αντίθεση με τα συμβατικά διπολικά τρανζίστορ ή με τα τρανζίστορ πεδίου MOS, τα οποία λειτουργούν στην περιοχή υποκατωφλίου για τη διατήρηση της διαγραμμικής αρχής. Στα πλαίσια της διατριβής αυτής παρουσιάζεται μια γενική μεθοδολογία χρησιμοποιώντας τους γράφους παραγόντων για την προδιαγραφή συστημάτων ελέγχου λαθών. Έπειτα, πραγματοποιείται η σύζευξη της επιτευχθείσας προδιαγραφής με την κυκλωματική συμπεριφορά των τοπολογιών λαμβάνοντας υπ’ όψιν φυσικά τα χαρακτηριστικά της τεχνολογίας SiGe BiCMOS και καταλήγουμε στην αποδοτική σχεδίαση και ολοκλήρωση αποκωδικοποιητών διόρθωσης λαθών υψηλής ταχύτητας. Χρήσιμα συμπεράσματα, για την υιοθέτηση της προτεινόμενης μεθοδολογίας και τη χρήση της τεχνολογίας Πυριτίου-Γερμανίου, αναφέρονται με την παρουσίαση της πρώτης επιτυχούς υλοποίησης σε τεχνολογία 0.35μm AMS SiGe BiCMOS ενός αναλογικού Trellis αποκωδικοποιητή και των εξομοιωτικών αποτελεσμάτων του αντίστοιχου αποκωδικοποιητή Turbo, ο οποίος ενσωματώνει τον παραπάνω Trellis αποκωδικοποιητή. / The incorporation of Turbo codes into a wide range of applications due to their amazing performance close to the fundamental Shannon limit, demands efficient architectures and implementations of high-throughput and low energy consumption in the case of the extremely complex and time consuming procedure of iterative decoding. The present dissertation studies the use of SiGe BiCMOS technology in analog architectures for the implementation of high-throughput and moderate power consumption Turbo decoders. The design is based on Heterojunction Bipolar Transistors and leads to a significant increment of the analog system’s speed in contrast to the designs based on conventional bipolar transistors or MOS transistor, which operate in the subthreshold region in order to conform to the translinear principle. A generic methodology, using factor-graphs for the specification procedure of error control systems, is also presented. Furthermore, we map the derived specification onto the appropriate acircuit topology taking into account the characteristics of the SiGe BiCMOS technology. Finally, the methodology leads to an efficient design and consistent integration of high-speed analog decoders. We report useful conclusions for the adoption of the proposed methodology, and the use of Silicon-Germanium technology by presenting the first successful implementation of an analog Trellis decoder, and the simulation results of the relevant Turbo decoder in a 0.35μm AMS SiGe BiCMOS technology.

Η παρούσα διπλωματική εργασία έγινε στα πλαίσια του Προγράμματος Μεταπτυχιακών Σπουδών Ηλεκτρονικής και Υπολογιστών, στο Τμήμα Φυσικής του Πανεπιστημίου Πατρών. Αντικείμενό της αποτελεί η μελέτη του φυσικού επιπέδου συστημάτων κινητής τηλεφωνίας τρίτης γενιάς και η εξομοίωση χαρακτηριστικού καναλιού του φυσικού επιπέδου σύμφωνα με την παγκόσμια προτυποποίηση 3GPP. Στο πρώτο κεφάλαιο γίνεται ιστορική ανασκόπηση των συστημάτων προηγούμενων γενεών. Αναφέρονται βασικά προβλήματα που πρέπει να αντιμετωπίσει ένα τηλεπικοινωνιακό σύστημα καθώς και η βασική δομή των κυψελοειδών συστημάτων. Γίνεται εισαγωγή στα συστήματα τρίτης γενιάς ως προς τις απαιτήσεις, τις υπηρεσίες που προσφέρουν, την προτυποποίηση και την αρχιτεκτονική τους. Στο δεύτερο κεφάλαιο μελετώνται οι τρόποι πολλαπλής πρόσβασης με ιδιαίτερη έμφαση στην προσπέλαση με διαίρεση κωδικών. Αναλύονται τα συστήματα διάχυσης φάσματος. Γίνεται εκτενής αναφορά και υλοποίηση προγραμμάτων για τις ψευδοτυχαίες ακολουθίες και τις ακολουθίες Gold. Στο τρίτο κεφάλαιο μελετάται η δομή δικτύων επικοινωνίας κατά το μοντέλο OSI. Αναφέρονται τα επίπεδα των τηλεπικοινωνιακών συστημάτων με διεξοδική μελέτη του φυσικού επιπέδου και στις διεπαφές που χρησιμοποιεί για επικοινωνία καθώς και στις υπηρεσίες που προσφέρει. Αναλύεται η δομή όλων των φυσικών καναλιών και εξομοιώνεται η διαδικασία ενθυλάκωσης του καναλιού PRACH. Στο τέταρτο κεφάλαιο αναλύονται οι κώδικες διάχυσης των φυσικών καναλιών ανερχόμενης ζεύξης καθώς και η διαδικασία διάχυσης τους. Δημιουργούνται προγράμματα που παράγουν αυτούς τους κώδικες και γίνεται εξομοίωση της διάχυσης και της αποδιάχυσης του PRACH καναλιού. Στο πέμπτο κεφάλαιο αναφέρεται η διαδικασία κωδικοποίησης πηγής και μελετάται η PSK διαμόρφωση και αποδιαμόρφωση που χρησιμοποιούν τα συστήματα τρίτης γενιάς. Υλοποιούνται προγράμματα που εξομοιώνουν τη συνολική διαδικασία σε ενθόρυβο κανάλι AWGN μελετώντας την επίδραση του θορύβου σε μεταδιδόμενο σήμα. Όλες οι εξομοιώσεις υλοποιήθηκαν με το πρόγραμμα Matlab 7.1. / This master thesis is a part of the post-graduate course of the Physics department of the University of Patras, on Electronics and Computers. Its main objective is the study of the physical layer of 3rd generation telecommunication systems and the simulation of a particular channel, in accordance to 3GPP specifications. In the first chapter we review telecommunication systems of previous generations. We also refer to major problems that need to be dealt with and also the basic structure of cellular networks. 3rd generation telecommunication systems, their requirements, offered services, standardisation and architecture are all introduced. In the second chapter we study multiple access methods, emphasising CDMA methods. Moreover, spread spectrum systems are analysed. Finally we refer to pseudorandom and Gold sequences. Programs are created which generate these sequences. In the third chapter we look into the structure of communication networks according to the OSI model. The layers of telecommunication systems are mentioned, laying emphasis on the physical layer, the interfaces used for communication as well as the offered services. We report all physical channels and we simulate the encapsulation of the PRACH channel. In the fourth chapter we analyse the spreading and scrambling codes referring to the uplink channels. Next we point out the code allocation process. Programs are created which generate these spreading and scrambling codes and we finally simulate the spreading and de-spreading process of the PRACH channel. In the fifth chapter we outline the source coding process using PCM, and we study PSK modulation and demodulation which are used by 3rd generation telecommunication systems. We create programs that simulate the whole procedure in a noisy channel, and we study the effect of AWGN. The programs were created and the simulations were run using Matlab version 7.1.

Το έτος 1987 στο Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών του Πανεπιστήμιου Πατρών και συγκεκριμένα στο Εργαστήριο Ηλεκτρομηχανικής Μετατροπής Ενέργειας του Τμήματος Ηλεκτρολόγων Μηχανικών, στα πλαίσια εκπαιδευτικών και ερευνητικών σκοπών, εγκαταστάθηκε ένα πλήρες αυτοματοποιημένο σύστημα παράγωγης και παροχής ηλεκτρικών τάσεων. Σκοπός του συστήματος ήταν η παροχή 10 διαφορετικών τύπων τάσεων σε 15 συγκεκριμένες θέσεις εργασίας στο χώρου του Εργαστηρίου. Το σύστημα ήταν πλήρως αυτοματοποιημένο, καθώς χρησιμοποιήθηκε προγραμματιζόμενος λογικός ελεγκτής (PLC) που ήταν επιφορτισμένος με τον έλεγχο, την εποπτεία και τη διαχείριση του Συστήματος. Επίσης υπήρχε προσωπικός Η/Υ άμεσα συνδεδεμένος στο σύστημα, μέσω του όποιου ο διαχειριστής του μπορούσε να παρακολουθεί, να διαχειρίζεται και να διανέμει τον κάθε τύπο από τις προσφερόμενες παροχές. Το σύστημα με την πάροδο του χρόνου εμφάνισε βασικά λειτουργικά προβλήματα, με αποτέλεσμα να μειωθεί δραστικά ο αριθμός των παρεχόμενων τύπων τάσεων, αλλά και η ικανότητα διαχείρισης και διανομής αυτών που παρέχονταν. Πιο συγκεκριμένα, το τμήμα τoυ προγραμματιζόμενoυ λογικού ελεγκτή (PLC) και του συνδεδεμένου Η/Υ του συστήματος ουσιαστικά και πρακτικά είχε τεθεί πλέον πλήρως εκτός λειτουργίας. Στόχος και σκοπός της παρούσας εργασίας ήταν η λύση των προβλημάτων του προαναφερθέντος συστήματος με τελικό αποτέλεσμα την κανονική και ομαλή λειτουργία του. Η λύση που προτείνεται είναι η υλοποίηση και η ενσωμάτωση ενός σύγχρονου δικτύου αυτοματισμού με τη χρήση σύγχρονων PLC (επιλέχθηκε η εταιρεία OMRON) καθώς και η ενσωμάτωση ενός συστήματος εποπτικού και διαχειριστικού ελέγχου, λογισμικό τύπου SCADΑ της ίδιας εταιρείας. Αναλύονται διεξοδικά τόσο ο τρόπος παραγωγής των τάσεων με τα αντίστοιχα κυκλώματα ισχύος όσο και ο τρόπος διανομής και διαχείρισης αυτών με τα αντίστοιχα κυκλώματα αυτοματισμού. Εμπεριέχονται εκτενείς αναφορές στα σύγχρονα PLC, στον τρόπο λειτουργίας και προγραμματισμού τους καθώς και ο τρόπος με τον οποίο είναι δυνατό να ενσωματωθούν και να λειτουργήσουν πλήρως στο υπάρχον σύστημα. Γίνεται μια εισαγωγή στα σύγχρονα συστήματα διαχείρισης και εποπτικού ελέγχου (SCADA) ώστε να μπορεί ο κάθε αναγνώστης, χωρίς να χρειάζονται υψηλού επιπέδου γνώσεις, να κατανοήσει τη χρησιμότητα και τη λειτουργία τους και μελετείται ο τρόπος με τον οποίο θα υλοποιηθεί το παραπάνω δίκτυο αυτοματισμού με τη χρήση των PLC και με την παρουσία του εποπτικού συστήματος SCADA. Γίνεται πλήρης αναφορά σε έναν πολύ βασικό τομέα του Ηλεκτρολόγου Μηχανικού στη σύγχρονη εποχή: τον υπολογισμό κόστους προμήθειας, εγκατάστασης και κατασκευής όλων των στοιχείων του εγχειρήματος και μελετούνται όλες οι παράλληλες επιλογές για την καλύτερη δυνατή λειτουργία του και την περαιτέρω ανάπτυξη και βελτίωση του. / The year 1987 in the Department of Electrical and Computer Engineering University of Patras and specifically in Electromechanical Energy Conversion Laboratory Department of Electrical Engineering, in educational and research purposes, installed a complete automated system for producing and providing electrical voltages. This system was able to provide 10 different types of voltages in 15 stations in the area of Laboratory. The system was fully automated, used a Programmable Logic Controller (PLC), which was responsible for monitoring, supervision and management system. Also there was a PC directly connected to the system, through which the administrator can monitor, manage and distribute each type of voltage. The system through the walking time showed major operational problems. As a result, the number of the types of voltages and the ability to manage and distribute those provided reduced drastically. Specifically, the part of programmable logic controller (PLC) and the connected computer system effectively and practically has run out of order. The purpose of this work was the solution of problems of the system and ultimately with final result the normal and smooth operation. The solution proposed is the implementation and integration of a modern network automation using modern PLC (the company chosen is OMRON) and the incorporation of a supervisory control and data acquisition application and (SCADA) software of the same company. Analyzed in detail both the production voltages with the respective power circuits and the method of distribution and management of the automation circuits. Contained extensive references to contemporary PLC, in operations and programming, and how it is possible to integrate and operate fully in the existing system. There is an introduction to SCADA to enable each reader without the need for high-level knowledge to understand the utility and operation, and considering how we implement the above automation network using a PLC and SCADA application. We mention a very important area of Electrical Engineering in the modern era: counting the cost of supply, installation and construction of all elements of the project and consider all parallel options for optimal operation and further development and improvement.

Στο πλαίσιο αυτής της διατριβής μελετάται η επίδοση συστημάτων διαφορισμού MIMO σε γενικευμένα κανάλια διαλείψεων. Αρχικά, εξετάζεται η επίδοση των OSTBC σε περιβάλλοντα διαλείψεων Hoyt. Αποδεικνύεται ότι, στην περίπτωση τέτοιων συστημάτων, ο σηματοθορυβικός λόγος (signal to noise ratio, SNR) εκφράζεται ως μία τετραγωνική μορφή κανονικών τυχαίων μεταβλητών και γίνεται χρήση της συνάρτησης πυκνότητας πιθανότητας και της αθροιστικής συνάρτησης κατανομής αυτής της μορφής για τον υπολογισμό των μετρικών επίδοσης. Επιπλέον, μελετάται η σύγκλιση των σειρών που χρησιμοποιούνται για τον υπολογισμό των δύο αυτών συναρτήσεων και κατασκευάζονται νέα άνω φράγματα για το σφάλμα αποκοπής των σειρών. Τα φράγματα αυτά είναι σαφώς πιο αυστηρά από τα ήδη γνωστά από τη βιβλιογραφία. Στη συνέχεια, εισάγεται ένα γενικευμένο μοντέλο διαλείψεων για την ανάλυση επίδοσης των OSTBC και των δεκτών MRC και υπολογίζονται όλες οι μετρικές επίδοσης των δύο συστημάτων για το συγκεκριμένο μοντέλο διαλείψεων. Το μοντέλο αυτό περιλαμβάνει ως ειδικές περιπτώσεις τα πλέον διαδεδομένα μοντέλα καναλιών διαλείψεων, ενώ επιπλέον, επιτρέπει την ανάλυση επίδοσης σε μικτά περιβάλλοντα διαλείψεων όπου τα πολλαπλά κανάλια μπορούν να ακολουθούν διαφορετικές κατανομές. Στη συνέχεια, μελετάται η επίδοση συστημάτων συνεργατικού διαφορισμού με χρήση αναμεταδοτών ανίχνευσης και προώθησης (Detect and Forward, DaF) σε περιβάλλοντα διαλείψεων Rayleigh. Εξετάζονται τρεις διαφορετικοί δέκτες και υπολογίζεται η πιθανότητα σφάλματος ανά bit γι' αυτούς. Τέλος προτείνεται ένας νέος δέκτης για συνεργατικά συστήματα DaF και αποδεικνύεται η ανωτερότητά του σε σύγκριση με τους υπόλοιπους μελετώμενους δέκτες. Όλα τα θεωρητικά αποτελέσματα που παρουσιάζονται στο πλαίσιο της διατριβής συγκρίνονται με αποτελέσματα προσομοιώσεων Monte Carlo που αποδεικνύουν την ορθότητα της ανάλυσης. / This thesis studies the performance of MIMO diversity systems in generalized fading channels. First, we examine the performance of OSTBC in Hoyt fading channels. It is proven that, for this fading model, and when an OSTBC is employed, the signal-to-noise ratio (SNR) of the OSTBC can be expressed as a quadratic form in normal random variables. Therefore, the performance analysis for OSTBC over Hoyt fading channels is performed using the PDF and the CDF of such quadratic forms. In the statistical literature, these functions are expressed in terms of infinite series. The convergence of the series is thoroughly studied and new expressions for the truncation error bound of these series are proposed. The proposed bounds are much tighter than the bounds that can be found in the literature. The expressions for the PDF and the CDF are then used for the performance analysis of OSTBC over Hoyt fading and several performance metrics are calculated. Then, a generalized fading model for the performance analysis of OSTBC and MRC is proposed and the theoretical performance analysis of both MRC and OSTBC is carried out. The main advantage of this model is the fact that it includes as special cases most of the widely used fading models. Furthermore, the performance of cooperative diversity systems employing Detect and Forward (DaF) relays is studied for Rayleigh fading channels. More specifically, three low complexity detection algorithms for these channels are examined and closed-form expressions of the bit error probability (BEP) for these receivers are derived. Finally, a new low complexity receiver for cooperative systems with DaF relays is proposed. Using Monte Carlo Simulations it is shown that this receiver outperforms the three receivers that have been studied. For the systems studied in the thesis, the performance analysis results that have been derived theoretically are compared with Monte Carlo simulations that prove the validity of the analysis.