Ανασκόπηση του κανόνα ολοκλήρωσης του gauss. Αναπαραστάσεις και εκτιμήσεις του υπολοίπου του. Τέλος περί της σύγκλισης του κανόνα ολοκλήρωσης. / A survey on gaussian quqdrature rules. Representation and estimates of its remainder. And about its convergence.

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

Σκοπός της παρούσης διατριβής είναι η ανάπτυξη ενός γρήγορου και ευέλικτου (παραµετρικού) αριθµητικού µοντέλου, µε βάση τα πεπερασµένα στοιχεία, για την πρόβλεψη των στρεβλώσεων ολοκληρωµένων κατασκευαστικών στοιχείων που συγκολλούνται µε Laser. Το µοντέλο που θα αναπτυχθεί θα αξιολογηθεί για την εκτίµηση των παραµέτρων συγκόλλησης, καθώς και για την πρόβλεψη της σειράς των ραφών συγκόλλησης πριν την παραγωγή του ολοκληρωµένου κατασκευαστικού στοιχείου, έτσι ώστε οι στρεβλώσεις να είναι οι ελάχιστες δυνατές. Η ανάπτυξη ενός αριθµητικού µοντέλου που θα επιτρέπει την ακριβή πρόβλεψη των στρεβλώσεων, απαιτεί να ληφθούν υπόψη κατά το δυνατόν µε πληρότητα και ακρίβεια οι παράµετροι της διεργασίας της συγκόλλησης και οι µηχανισµοί που λαµβάνουν χώρα κατά την συνολική διαδικασία. Έτσι ώστε, να επιτευχθεί µια ικανοποιητική προσοµοίωση της διεργασίας της συγκόλλησης. Εποµένως, το µοντέλο υπολογισµού των στρεβλώσεων πρέπει να περιέχει πληροφορίες ή να δηµιουργεί µε τη βοήθεια υπορουτινών δεδοµένα για σειρά ερωτηµάτων, όπως είναι ο τρόπος µε τον οποίο αποδίδεται η ενέργεια από την θερµική πηγή, πως και πόση από την ενέργεια αυτή χάνεται ή απορροφάται το υλικό, τι µηχανισµοί συγκόλλησης εµφανίζονται και πότε, πως επηρεάζονται οι θερµικές και µηχανικές ιδιότητες του υλικού µε τη θερµοκρασία και τι µετασχηµατισµοί φάσεων λαµβάνουν χώρα στην µικροδοµή του υλικού κατά την πλήρη διεργασία της συγκόλλησης. Στο σηµείο αυτό είναι απαραίτητο να διευκρινισθεί ότι στους στόχους της παρούσης διατριβής, δεν περιλαµβάνεται τόσο η παραγωγή νέας γνώσης για την ίδια την διεργασία της συγκόλλησης, όσο η ενσωµάτωση σε έναν ενιαίο κώδικα της σύγχρονης επιστηµονικής γνώσης για την διεργασία της συγκόλλησης. Στον γράφοντα δεν είναι γνωστή η ύπαρξη τέτοιων ολοκληρωµένων υπολογιστικών µοντέλων. Είναι εύλογο ότι ένα τέτοιο µοντέλο µη γραµµικής θερµικής-µηχανικής µεταβατικής ανάλυσης, το οποίο επιπλέον θα λαµβάνει υπόψη τους σχηµατισµούς φάσεων της µικροδοµής του υλικού που λαµβάνουν χώρα κατά την διεργασία της συγκόλλησης, αναµένεται να είναι πολύπλοκο και να απαιτεί µεγάλους χρόνους υπολογισµού. Με σκοπό την δηµιουργία ενός γρήγορου και ευέλικτου (παραµετρικού) µοντέλου, στόχος της εργασίας είναι η ανάπτυξη εναλλακτικών υπολογιστικών τεχνικών στον κώδικα των πεπερασµένων στοιχείων, για την ελαχιστοποίηση του χρόνου προσοµοίωσης της συγκόλλησης και του υπολογισµού των στρεβλώσεων πολύπλοκων ολοκληρωµένων εξαρτηµάτων. / -

Οι μονάδες επεξεργασίας δεδομένων αποτελούν τις βασικές δομικές μονάδες όλων των μικροεπεξεργαστών. Κάποια από τα κυκλώματα αυτής της κατηγορίας υλοποιούν τις βασικές αριθμητικές πράξεις πάνω σε δεδομένα τόσο σταθερής όσο και κινητής υποδιαστολής, ενώ κάποια άλλα αναλαμβάνουν την αναδιοργάνωση των δεδομένων αυτών για την επιτάχυνση του υπολογισμού. Σε επεξεργαστές ειδικού σκοπού, όπως οι επεξεργαστές πολυμέσων και γραφικών, οι μονάδες επεξεργασίας δεδομένων καταλαμβάνουν περισσότερο από το 30% του ολοκληρωμένου και η αποτελεσματική σχεδίαση τους έχει άμεσο αντίκτυπο στην απόδοση ολόκληρου του συστήματος. Στο μέλλον, αναμένεται πως ακόμα και οι επεξεργαστές γενικού σκοπού, θα είναι εξοπλισμένοι από εξειδικευμένους επιταχυντές, οι οποίοι θα εκτελούν απ’ ευθείας σε υλικό σύνθετους αλγορίθμους με μεγάλες υπολογιστικές απαιτήσεις. Η βάση όλων των προτεινόμενων λύσεων σ’ αυτή τη διατριβή είναι η αναλυτική εύρεση ενός εγγενώς απλούστερου αλγορίθμου, ο οποίος θα επιτρέπει την αποτελεσματική υλοποίηση των αντίστοιχων κυκλωμάτων ανεξάρτητα από την τεχνολογία που θα χρησιμοποιηθεί και από τους επιπλέον περιορισμούς που τυχόν θα επιβληθούν στο μέλλον κατά την κατασκευή των κυκλωμάτων αυτών. Η ανάλυση και τα πειραματικά αποτελέσματα που συλλέξαμε βασίζονται τόσο σε υλοποιήσεις σε επίπεδο τρανζίστορ, που είναι η κύρια μέχρι τώρα πρακτική σχεδίασης των μικροεπεξεργαστών υψηλών επιδόσεων, όσο και σε πλήρως αυτοματοποιημένες υλοποιήσεις. Φυσικά, στη δεύτερη περίπτωση η απόδοση των κυκλωμάτων επιβαρύνεται, τόσο σε καθυστέρηση όσο και σε ενέργεια, εξαιτίας των περιορισμών των αυτοματοποιημένων εργαλείων και την αναγκαστική χρήση των προσχεδιασμένων βιβλιοθηκών βασικών πυλών. Η μελέτη που πραγματοποιήσαμε στοχεύει στην πλήρη εξερεύνηση του χώρου λύσεων των κυκλωμάτων αυτών. Η ανάλυση της συμπεριφοράς τους πραγματοποιήθηκε χρησιμοποιώντας τις βέλτιστες καμπύλες της ενέργειας ως προς την καθυστέρηση, οι οποίες αποτελούν τον πιο έγκυρο τρόπο περιγραφής της απόδοσης ενός κυκλώματος. Τα κυκλώματα που παρουσιάζονται ανήκουν σε τρεις βασικές κατηγορίες. Στην πρώτη ανήκουν οι αθροιστές παράλληλου προθέματος, που χρησιμοποιούν τα κρατούμενα του Ling για την υλοποίηση της δυαδικής πρόσθεσης. Τα κρατούμενα που προτάθηκαν από τον Ling αποτελούν απλοποιημένες μορφές των κλασικών σχέσεων πρόβλεψης κρατουμένου και χρησιμοποιούνται αυτή τη στιγμή στην πλειοψηφία των εμπορικών επεξεργαστών. Το νέο κύκλωμα, που προτείναμε, αποτελεί ουσιαστικά τη γενίκευση των σχέσεων αυτών, επιτρέποντας την υλοποίηση τους με απλοποιημένες δομές παράλληλου προθέματος, με αποτέλεσμα τη μείωση τόσο της καθυστέρησης όσο και της απαιτούμενης ενέργειας. Η νέα τεχνική οδηγεί σε γρηγορότερα κυκλώματα ανεξάρτητα από τη λογική οικογένεια που θα χρησιμοποιηθεί (στατική ή δυναμική CMOS λογική) και το δένδρο παράλληλου προθέματος που θα επιλεγεί. Η δεύτερη κατηγορία αναφέρεται σε κυκλώματα αναδιάταξης των δεδομένων που είναι αποθηκευμένα μέσα στους καταχωρητές του επεξεργαστή. Η αποδοτική αναδιάταξη των δεδομένων καταλήγει να είναι σε πολλούς αλγορίθμους (κρυπτογραφία, ψηφιακή επεξεργασία σήματος, πολυμέσα) τόσο αναγκαία όσο και η γρήγορη υλοποίηση των βασικών αριθμητικών πράξεων, αλλά και η ταχεία επικοινωνία με τη μνήμη. H προσπάθεια μας εστιάστηκε στην αποδοτική υλοποίηση μιας γενικής εντολής αναδιάταξης δεδομένων, στοχεύοντας σε όσο το δυνατόν ταχύτερες υλοποιήσεις. Όλες οι εκδοχές που προτείναμε στηρίζονται σε μια νέα μορφή δικτύων ταξινόμησης, η οποία μας επιτρέπει να παρέχουμε λύσεις που είναι σημαντικά πιο αποδοτικές σε σχέση με τις ήδη υπάρχουσες. Τα κυκλώματα που προτείνουμε κατασκευάζονται με τη χρήση ενός μόνο κελιού υπολογισμού (διαφορετικό για κάθε δίκτυο ταξινόμησης) και διατηρούν μια πλήρως κανονική δομή. Το στοιχείο αυτό, συμβάλλει, πέρα από τη βελτίωση της απόδοσης, στην αποτελεσματικότερη χωροθέτηση του κυκλώματος και στη μείωση των αρνητικών επιδράσεων των γραμμών διασύνδεσης. Η τελευταία κατηγορία κυκλωμάτων αναφέρεται σε κυκλώματα που χρησιμοποιούνται για την υλοποίηση της πρόσθεσης αριθμών κινητής υποδιαστολής. Τα κυκλώματα που προτείνουμε χρησιμοποιούνται στα πιο κρίσιμα στάδια, από πλευράς καθυστέρησης, του υπολογισμού του αθροίσματος και αφορούν στην πρόσθεση των μεγεθών και στην κανονικοποίηση του αποτελέσματος. Αρχικά, περιγράφουμε μια εναλλακτική προσέγγιση για την υλοποίηση των αθροιστών μεγέθους των αριθμών κινητής υποδιαστολής. Οι νέες μονάδες εκμεταλλεύονται την αναπαράσταση συμπληρώματος ως προς ένα και τις γρήγορες μονάδες υπολογισμού του κρατουμένου, που βασίζονται στην τεχνική παράλληλου προθέματος. Προτείνουμε μια ενοποιημένη μεθοδολογία για το πως μπορούμε να παράγουμε δομές παράλληλου προθέματος ανεξάρτητα από το μέγεθος της λέξης εισόδου, ενώ καταφέρνουμε να ενώσουμε για πρώτη φορά τις απλοποιημένες σχέσεις κρατουμένου του Ling με την πρόσθεση αριθμών που ακολουθούν την αναπαράσταση συμπληρώματος ως προς ένα. Στη συνέχεια, περιγράφεται ένας νέος απλός τρόπος για την υλοποίηση της πρόβλεψης και της μέτρησης των προπορευόμενων μηδενικών που εμφανίζονται στα αποτελέσματα των πράξεων αριθμών κινητής υποδιαστολής. Με τη χρήση των νέων κυκλωμάτων η κανονικοποίηση του αποτελέσματος μπορεί να πραγματοποιηθεί σε λιγότερο χρόνο και με σημαντικά μικρότερη ενέργεια. / Data processing units (or simply datapath) constitute a major part of all microprocessors. They take over the execution of all arithmetic operations either of fixed point or floating-point data, while they are also responsible for the execution of the needed data rearrangements in order to speed up the computation. In application-specific processors used for media and graphics applications, datapath circuits occupy more than one third of the processor’s core area and their efficient design directly affects the energy-delay behavior of the whole circuit. In the near future, it is expected that even general-purpose processors will be equipped we specialized accelerators that will execute directly in hardware complex algorithms with large computational demands. The basis of all circuits presented in this thesis is the derivation of an inherently simpler algorithm that would allow their efficient implementation irrespective the technology used and the constraints that would be imposed in the future, concerning the reliable and more predictable circuit fabrication in very deep submicron technologies. Our analysis relies on full-custom transistor-level designs that is the most common technique employed in high-performance microprocessor design. The performance of some of the presented circuits has also been investigated using an automated design flow. It is expected that, in these cases, the performance of the presented circuits will be aggravated due to the limitations imposed by the design automation tools and the available standard cell library. In this study, we aim at fully exploring the design space of our circuits. For this reason, we derived an optimal energy-delay curve for each one of the examined circuits in order to analyze its behavior. An energy-delay curve is the most reliable metric for presenting the performance of a circuit and allows the designer to perform a fair comparison among various design alternatives and circuit topologies. The new circuits presented in this thesis belong to three categories. In the first class, we find the parallel prefix adders that adopt the carries proposed by Ling. These carries are a simplified form of the classic carry lookahead equations and they are used at the moment in the majority of commercial high-speed microprocessors. The newly proposed circuits are based on a transformation of the Ling carries that leads to more efficient parallel prefix structures, which are better suited for Ling-carry computation. This new technique offers faster implementations irrespective the logic family used (either static or dynamic CMOS) and the prefix structure selected for the implementation. The second class refers to circuits that rearrange the data stored inside one or more of the processor’s registers. Efficient data rearrangement ends up being, in many cases, such as cryptography, digital signal processing, and multimedia applications, as essential as the fast implementation of basic arithmetic operations and the high bandwidth processor-memory communication. Our effort has focused on the efficient implementation of one of the most versatile permutation instruction, aiming to the reduction of the delay of the corresponding circuit. The design of the proposed permutation units is put under a common framework and their functionality resembles that of sorting networks. All the presented variants are designed using a single processing element (different for each sorting network) and have a very regular structure. This fact significantly contributes to the delay reduction because of the regular placement of the circuits’ cells that also alleviates the interconnect delay overhead. The last class of circuits is used for the implementation of high-speed floating-point units. The proposed circuits participate in two of the most time critical parts of any floating-point adder that is the significand (or fraction) adder and the result normalization unit. At first, we describe an alternative implementation of the significant adder that employs the one’s complement representation in order to reduce the delay of the circuit. The proposed parallel-prefix structures are derived using a general design methodology that leads to efficient designs irrespective the wordlength of the input operands. Also, we managed for the first time to produce simplified parallel-prefix carry computation units for the case of one’s complement addition that rely on the definition of Ling carries. Secondly, we describe a simple and practical algorithm for counting the number of leading zeros that may appear in the result of floating-point addition. New circuits are also presented that simplify the design of the corresponding leading zero anticipation logic. Using the proposed structures, normalization can be performed with less delay and significantly reduced power dissipation compared to already known implementations.