Σχεδόν όλα τα σύγχρονα τηλεπικοινωνιακά συστήματα, τα οποία προορίζονται για μεταφορά ή αποθήκευση δεδομένων, έχουν υιοθετήσει κώδικες διόρθωσης λαθών για την αύξηση της αξιοπιστίας και τη μείωση της απαιτούμενης ισχύος εκπομπής. Μία αρκετά συχνά χρησιμοποιούμενη επιλογή είναι οι κώδικες Reed Solomon που έχουν την υψηλότερη δυνατή ελάχιστη απόσταση μεταξύ των κωδικών λέξεων για δεδομένη διορθωτική ικανότητα. Στην εργασία αυτή μελετήθηκαν οι ιδιότητες των κωδίκων αυτών, έγινε ανάλυση των διαφόρων αλγορίθμων αποκωδικοποίησης και ο σχεδιασμός σε FPGA των λειτουργιών κωδικοποίησης και αποκωδικοποίησης. Πιο συγκεκριμένα, έγινε εκτενής χρήση του συνθέσιμου μικρελεγκτή της Xilinx, του Picoblaze για τα δύο συστήματα που αφορούν τον κώδικα RS (255,239), υιοθετώντας μια παράλληλη αρχιτεκτονική για τον αποκωδικοποιητή, έχοντας ως στόχο μια οικονομική ως προς τους χρησιμοποιούμενους πόρους υλοποίηση. Η αρχιτεκτονική αυτή τροποποιήθηκε με σκοπό την επίτευξη υψηλότερης ταχύτητας λειτουργίας, αυξάνοντας το χρησιμοποιούμενο hardware. Ο σχεδιασμός υλοποιήθηκε σε ένα Virtex4 της Xilinx, χρησιμοποιώντας εργαλεία της Xilinx και διαπιστώθηκε η ορθή του λειτουργία χρησιμοποιώντας αντίστοιχα bit-accurate μοντέλα που αναπτύχθηκαν σε Matlab. / -

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

Η εργασία αυτή είχε ως σκοπό τη μελέτη της λειτουργίας των κωδικών LDPC, τη χρήση τους σε συστήματα μετάδοσης δεδομένων και την υλοποίησή τους σε κύκλωμα με επεξεργαστές ARM και FPGA. Ο στόχος ήταν να κατασκευαστεί ένα μοντέλο συνεχούς αποστολής και λήψης εικόνων μέσω μη αξιόπιστων μέσων. Αρχικά μελετήσαμε τα θεωρητικά θέματα που αφορούν τους κώδικες LDPC. Μετά ακολούθησε η προσομοίωση των διαδικασιών κωδικοποίησης, αποκωδικοποίησης και η μοντελοποίηση καναλιού. Η εφαρμογή των κωδίκων LDPC βασίστηκε στην προδιαγραφή ETSI EN 302 307. Αυτή η προδιαγραφή αφορά τις δορυφορικές επικοινωνίες και τυποποιεί τις αντίστοιχες εφαρμογές. Το επόμενο βήμα ήταν η υλοποίηση των λειτουργιών του κωδικοποιητή και του αποκωδικοποιητή LDPC. Τέλος, ελέγχθηκε η ορθή λειτουργία των εργασιών κωδικοποίησης και αποκωδικοποίησης και ελήφθησαν οι μετρήσεις σε σχέση με την απόδοση του υλικού. / This thesis was designed to study the function of the LDPC codes, their use in data transmission systems and their implementation in circuit with ARM processors and FPGA. The aim was to construct a model of continuous send and receive pictures via unreliable media (channels introduce errors). Initially we studied the theoretical issues surrounding the LDPC codes. After that we simulated the procedures of coding, decoding and channel modeling. The implementation of LDPC codes was based on the specification ETSI EN 302 307. This specification relates to satellite communications and standardizes the respective applications. The next step was the implementation of the functions of the LDPC encoder and decoder. Finally the proper functioning of coding and decoding operations was checked and measurements relative to the performance of the hardware were taken.

Οι κώδικες LDPC ανήκουν στην κατηγορία των block κωδικών. Πρόκειται για κώδικες ελέγχου σφαλμάτων μετάδοσης και πιο συγκεκριμένα για κώδικες διόρθωσης σφαλμάτων. Αν και η εφεύρεσή τους (από τον Gallager) τοποθετείται χρονικά στις αρχές της δεκαετίας του 60, μόλις τα τελευταία χρόνια κατάφεραν να κεντρίσουν το έντονο ενδιαφέρον της επιστημονικής-ερευνητικής κοινότητας για τις αξιόλογες επιδόσεις τους. Πρόκειται για κώδικες ελέγχου ισοτιμίας με κυριότερο χαρακτηριστικό τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check) από τον οποίο και πήραν το όνομά τους. Δεδομένου ότι η κωδικοποίηση των συγκεκριμένων κωδικών είναι σχετικά απλή, η αποκωδικοποίηση τους είναι εκείνη η οποία καθορίζει σε μεγάλο βαθμό τα χαρακτηριστικά του κώδικα που μας ενδιαφέρουν, όπως είναι η ικανότητα διόρθωσης σφαλμάτων μετάδοσης (επίδοση) και η καταναλισκόμενη ισχύς. Για το λόγο αυτό έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Παρόλο που οι ανεπτυγμένοι αλγόριθμοι και οι διάφορες εκδοχές τους δεν είναι λίγοι, δεν έχει ακόμα καταστεί εφικτό να αναλυθεί θεωρητικά η επίδοσή τους. Στην παρούσα εργασία παρατίθενται οι κυριότεροι αλγόριθμοι αποκωδικοποίησης κωδικών LDPC, που έχουν αναπτυχθεί μέχρι σήμερα. Οι αλγόριθμοι αυτοί υλοποιούνται και συγκρίνονται βάσει των αποτελεσμάτων εξομοιώσεων. Ο πιο αποδοτικός από αυτούς είναι ο αποκαλούμενος αλγόριθμος log Sum-Product και στηρίζει σε μεγάλο βαθμό την επίδοσή του σε μία αρκετά πολύπλοκή συνάρτηση, την Φ(x). Η υλοποίηση της τελευταίας σε υλικό επιβάλλει την πεπερασμένη ακρίβεια αναπαράστασής της, δηλαδή τον κβαντισμό της. Το σφάλμα κβαντισμού που εισάγεται από την διαδικασία αυτή θέτει ένα όριο στην επίδοση του αλγορίθμου. Η μελέτη που έγινε στα πλαίσια της εργασίας οδήγησε στον προσδιορισμό δύο μηχανισμών εισαγωγής σφάλματος κβαντισμού στον αλγόριθμο log Sum-Product και στη θεωρητική έκφραση της πιθανότητας εμφάνισης κάθε μηχανισμού κατά την πρώτη επανάληψη του αλγορίθμου. Μελετήθηκε επίσης ο τρόπος με τον οποίο το εισαγόμενο σφάλμα κβαντισμού επιδρά στην απόφαση του αλγορίθμου στο τέλος της κάθε επανάληψης και αναπτύχθηκε ένα θεωρητικό μοντέλο αυτού του μηχανισμού. Το θεωρητικό μοντέλο δίνει την πιθανότητα αλλαγής απόφασης του αλγορίθμου λόγω του σφάλματος κβαντισμού της συνάρτησης Φ(x), χωρίς όμως να είναι ακόμα πλήρες αφού βασίζεται και σε πειραματικά δεδομένα. Η ολοκλήρωση του μοντέλου, ώστε να είναι πλήρως θεωρητικό, θα μπορούσε να αποτελέσει αντικείμενο μελλοντικής έρευνας, καθώς θα επιτρέψει τον προσδιορισμό του περιορισμού της επίδοσης του αλγορίθμου για συγκεκριμένο σχήμα κβαντισμού της συνάρτησης, αποφεύγοντας χρονοβόρες εξομοιώσεις. / Low-Density Parity-Check (LDPC) codes belong to the category of Linear Block Codes. They are error detection and correction codes. Although LDPC codes have been proposed by R. Gallager since 1962, they were scarcely considered in the 35 years that followed. Only in the end-90's they were rediscovered due to their decoding performance that approaches Shannon limit. As their name indicates they are parity check codes whose parity check matrix is sparse. Since the encoding process is simple, the decoding procedure determines the performance and the consumed power of the decoder. For this reason several iterative decoding algorithms have been developed. However theoretical determination of their performance has not yet been feasible. This work presents the most important iterative decoding algorithms for LDPC codes, that have been developed to date. These algorithms are implemented in matlab and their performance is studied through simulation. The most powerful among them, namely Log Sum-Product, uses a very nonlinear function called Φ(x). Hardware implementation of this function enforces finite accuracy, due to finite word length representation. The roundoff error that this procedure imposes, impacts the decoding performance by means of two mechanisms. Both mechanisms are analyzed and a theoretical expression for each mechanism activation probability, at the end of the first iteration of the algorithm, is developed. The impact of the roundoff error on the decisions taken by the log Sum-Product decoding algorithm at the end of each iteration is also studied. The mechanism by means of which roundoff alters the decisions of a finite word length implementation of the algorithm compared to the infinite precision case, is analyzed and a corresponding theoretical model is developed. The proposed model computes the probability of changing decisions due to finite word length representation of Φ(x), but it is not yet complete, since the determination of the corresponding parameters is achieved through experimental results. Further research focuses on the completion of the theoretical model, since it can lead to a tool that computes the expected degradation of the decoding performance for a particular implementation of the decoder, without the need of time-consuming simulations.

Στη σύγχρονη εποχή η ανάγκη για αξιοπιστία των δεδομένων στις νέες τηλεπικοινωνιακές εφαρμογές έχει οδηγήσει στη ανάπτυξη και βελτιστοποίηση των λεγόμενων κωδικών διόρθωσης λαθών. Πρόκειται για συστήματα που έχουν την δυνατότητα ανίχνευσης και διόρθωσης λαθών που εισέρχονται σε τμήμα της πληροφορίας που μεταφέρεται μέσω τηλεπικοινωνιακών κυρίως δικτύων λόγω του θορύβου από το περιβάλλον και πιο συγκεκριμένα από το κανάλι μετάδοσης. Υπάρχουν αρκετές κατηγορίες από τέτοιους κώδικες διόρθωσης ανάλογα της δομής και της φύσης των αλγορίθμων που χρησιμοποιούν. Οι δύο κυριότερες κατηγορίες είναι οι συνελικτικοί κώδικες και οι γραμμικοί μπλοκ κώδικες με τους οποίους θα ασχοληθούμε.Οι δύο κώδικες που θα χρησιμοποιηθούν στα πλαίσια αυτής της εργασίας είναι οι κώδικες LDPC και οι BCH. Ανήκουν και οι δυο στους γραμμικούς μπλοκ κώδικες. Σκοπός της παρούσας διπλωματικής εργασίας αποτελεί αρχικά ο σχεδιασμός και η υλοποίηση ενός παραμετρικού συστήματος κωδικοποίησης και αποκωδικοποίησης για δυαδικούς BCH κώδικες διαφόρων μεγεθών. Εκτός της παραμετροποίησης έμφαση δόθηκε στην χαμηλή πολυπλοκότητα του συστήματος, στον υψηλό ρυθμό επεξεργασίας και στην δυνατότητα χρήσης shortening. Σε δεύτερη φάση πραγματοποιήθηκε σύνδεση μεταξύ, του παραπάνω κώδικα BCH, με έναν έτοιμο κώδικα LDPC και ένα κανάλι λευκού προσθετικού θορύβου (AWGN) που σχεδιάστηκαν στα πλαίσια άλλων διπλωματικών εργασιών με τελικό αποτέλεσμα την μελέτη της συμπεριφοράς του συνολικού συστήματος σε θέματα διόρθωσης λαθών και πιο συγκεκριμένα στην μείωση του φαινομένου του error-floor που παρατηρείται στον LDPC κώδικα. Επιπλέον μελετήθηκε η απαίτηση του συστήματος σε πόρους καθώς και ο ρυθμός επεξεργασίας που επιτυγχάνεται. Οι κύριες παράμετροι του κώδικα BCH που μπορούν να μεταβληθούν είναι το μέγεθος της κωδικής λέξης και η διορθωτική ικανότητα που επιτυγχάνεται. / -

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

Η προστασία των πνευματικών δικαιωμάτων και η απόδειξη γνησιότητας του κατόχου, επομένως και η πιστοποίηση της αυθεντικότητας των ψηφιακών αντικειμένων είναι ένα πολύ καυτό ζήτημα και για την επίλυσή του επιστρατεύονται μέθοδοι απόκρυψης πληροφορίας και τεχνικές υδατογράφησης. Εκτός από τη φιλοσοφική αντιμετώπιση του θέματος, προτείνονται μια μέθοδος απόκρυψης πληροφορίας και δύο τεχνικές υδατογράφησης, με σκοπό την προστασία των πνευματικών δικαιωμάτων και την πιστοποίηση της αυθεντικότητας των ψηφιακών αντικειμένων. Η μέθοδος απόκρυψης πληροφορίας δανείζεται έννοιες από την κρυπτογραφία εισάγοντας σε μεγάλες εικόνες ένα δύσκολο στιγμιότυπο, δηλαδή έναν τρία χρωματίσιμο γράφο. Ο γράφος μαζί με το χρωματισμό του αποτελεί το κλειδί. Για να μην αποκαλυφθεί όλος ο χρωματισμός του γράφου σε μια πιθανή διαμάχη, εφαρμόζεται το πρωτόκολλο των διαντιδραστικών αποδείξεων μηδενικής γνώσης (ZKIP) για δύσκολα υπολογιστικά προβλήματα. Η διαδικασία της ένθεσης γίνεται με χρήση του μετασχηματισμού wavelets, παρέχοντας καλή ποιότητα των παραγόμενων εικόνων και ανθεκτικότητα σε περιπτώσεις επιθέσεων. Οι δύο τεχνικές υδατογράφησης εφαρμόζονται στο χωρικό πεδίο και στο πεδίο συχνοτήτων, αντίστοιχα. Η τεχνική που εφαρμόστηκε στο χωρικό πεδίο εκμεταλλεύεται τυχόν ομοιότητες του υδατογραφήματος με τις αρχικές εικόνες για να επιλεγούν οι θέσεις ένθεσης. Αντίθετα στην τεχνική υδατογράφησης που εφαρμόστηκε στο πεδίο συχνοτήτων γίνεται χρήση του μετασχηματισμού wavelet. Σε όλες τις τεχνικές παρατηρήθηκαν ικανοποιητικά αποτελέσματα μετά την ένθεση της εισαγόμενης πληροφορίας έτσι ώστε να μη είναι οπτικά αντιληπτή. Επίσης εξετάστηκε και η ανθεκτικότητα της εισαγόμενης πληροφορίας στις εικόνες ύστερα από πιθανές επιθέσεις και επιβεβαιώθηκε ότι επιζεί ένα αρκετά μεγάλο ποσοστό της εισαγόμενης πληροφορίας, γεγονός που καταξιώνει τις προτεινόμενες μεθόδους. / The copyright protection and the authentication is a very hot topic and for its solution are called up data hiding methods and watermarking techniques. Αpart from the philosophical confrontation of the subject, there are proposed a data hiding method and two watermarking techniques that aim to copyright protect and the authenticate digital objects. The data hiding technique combines concepts from cryptography and it can be applied to large images by inserting a hard instance, i.e. a 3-colorable graph. The graph itself with its coloring compose the key. In order not to reveal all its coloring in a possible conflict, the Zero Knowledge Interactive Proof Protocol (ZKIP) is applied. The insertion process has been done using wavelets transformation, offering good quality of the produced images and robustness against possible attacks. The two watermarking techniques are applied in spatial domain and in frequency domain, respectively. The technique that was applied in spatial domain is exploiting any similarity between the watermark and the initial images so that to select at best the insertion positions. On the contrary, in the watermarking technique that is applied in the frequency domain, wavelets transformation has been used and the watermark was inserted in the differential coefficients of the image, in order to be imperceptible. To all the above techniques, it has been observed sufficient results after the insertion of the redundant information, so that it turned to be visible imperceptibly. Moreover, the robustness of the redundant information was each time after possible attacks examined, and it was confirmed that a rather big percentage of the redundant information is survived, making more reliable the proposed techniques.

Η διπλωματική εργασία επικεντρώνεται στην αποκωδικοποίηση με τη χρήση LDPC κωδικών. Στα πλαίσιά της, θα μελετηθεί και θα αξιολογηθεί η κωδικοποίηση και η αποκωδικοποίηση LDPC, με συνδυασμένα κριτήρια παρεχόμενης ποιότητας (κριτήρια BER σε διάφορες συνθήκες μετάδοσης) και πολυπλοκότητας υλοποίησης σε υλικό. Μέσω εξομοίωσης, θα εξεταστεί κατά πόσο επηρεάζεται η απόδοση των αποκωδικοποιητών από την αναπαράσταση πεπερασμένου μήκους λέξης, η οποία χρησιμοποιείται για την υλοποίηση της αρχιτεκτονικής τους σε υλικό. Αφού αποφασιστεί το μήκος λέξης, ώστε η απόδοση του αποκωδικοποιητή να προσσεγγίζει τη θεωρητική, θα ακολουθήσει η μελέτη και ο σχεδιασμός της αρχιτεκτονικής του αποκωδικοποιητή, ώστε να ικανοποιεί και άλλα πρακτικά κριτήρια, με έμφαση στην χαμηλή κατανάλωση ενέργειας. Η καινοτομία της διπλωματικής έγκειται στην παρουσίαση ενός νέου κριτηρίου για τον τερματισμό των επαναλήψεων σε αποκωδικοποιητές LDPC. Το προτεινόμενο κριτήριο είναι κατάλληλο για υλοποίηση σε υλικό, και όπως προκύπτει τελικά, μπορεί να αποφέρει σημαντική μείωση στην κατανάλωση ενέργειας των αποκωδικοποιητών. Το κριτήριο ελέγχει αν υπάρχουν «κύκλοι» στην ακολουθία των soft words κατά την αποκωδικοποίηση. Οι «κύκλοι» αυτοί προκύπτουν σε κάποιες περιπτώσεις χαμηλού λόγου σήματος προς θόρυβο, όπου ο αποκωδικοποιητής δε μπορεί να καταλήξει σε αποτέλεσμα, κάτι το οποίο οδηγεί σε ανόφελη κατανάλωση ενέργειας, αφού δε βελτιώνεται το bit error rate, ενώ ο αποκωδικοποιητής συνεχίζει να λειτουργεί. Η προτεινόμενη αρχιτεκτονική τερματίζει τη διαδικασία της αποκωδικοποίησης σε περίπτωση που υπάρχει «κύκλος», επιτρέποντας σημαντική μείωση της κατανάλωσης ενέργειας, η οποία συνοδεύεται από πολύ μικρή μείωση στην απόδοση του αποκωδικοποιητή. Το προτεινόμενο κριτήριο μπορεί να εφαρμοστεί σε οποιαδήποτε υπάρχουσα αρχιτεκτονική για LDPC αποκωδικοποιητές. Συγκεκριμένα, στη διπλωματική αυτή, μελετώνται τα αποτελέσματα της εφαρμογής του κριτηρίου στις Hardware-Sharing και Parallel αρχιτεκτονικές. / This thesis introduces a novel criterion for the termination of iterations in iterative LDPC Code decoders. The proposed criterion is amenable for VLSI implementation, and it is here shown that it can enhance previously reported LDPC Code decoder architectures substantially, by reducing the corresponding power dissipation. The concept of the proposed criterion is the detection of cycles in the sequences of soft words. The soft-word cycles occur in some cases of low signal-to-noise ratios and indicate that the decoder is unable to decide on a codeword, which in turn results in unnecessary power consumption due to iterations that do not improve the bit error rate. The proposed architecture terminates the decoding process when a soft-word occurs, allowing for substantial power savings at a minimal performance penalty. The proposed criterion is applied to Hardware-Sharing and Parallel Decoder architectures.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη και ο σχεδιασμός VLSI επεξεργαστών για τη διόρθωση λαθών. Η κατηγορία των VLSI επεξεργαστών στην οποία εστιάζει η έρευνά μου είναι ο αποκωδικοποιητής Viterbi. Αρχικά, παρουσιάζεται η δομή του ψηφιακού τηλεπικοινωνιακού συστήματος και κάποιες βασικές έννοιες των κωδικών διόρθωσης λαθών. Έπειτα, αναλύονται οι Συνελικτικοί κωδικοποιητές, ανάμεσα στους οποίους περιλαμβάνεται ο Συνελικτικός κωδικοποιητής που χρησιμοποιείται στην εργασία μου και ο οποίος χρησιμοποιείται ευρέως στο πρότυπο Wifi 802.11a. Ακολούθως, γίνεται αναφορά στο κανάλι AWGN και στη διαμόρφωση BPSK. Ακόμα, παρουσιάζονται οι βασικές έννοιες του αλγόριθμου Viterbi, η λειτουργία του, η δομή του καθώς και οι εφαρμογές του. Στη συνέχεια, μελετώνται διάφορες αρχιτεκτονικές του αποκωδικοποιητή Viterbi σε VLSI. Με βάση τον τρόπο υλοποίησης αριθμητικών πράξεων, οι αρχιτεκτονικές που αναπτύσσονται είναι ο Radix-2 και ο Radix-4 Viterbi, ενώ με βάση τον τρόπο αποκωδικοποίησης αναπτύσσονται οι αρχιτεκτονικές του Viterbi για συνεχή αποκωδικοποίηση-εφαρμογές streaming και του Viterbi για αποκωδικοποίηση πακέτων των 20 bits. Επίσης, μελετάται η απόδοση των αρχιτεκτονικών αυτών με κριτήριο τη συχνότητα λαθών που πραγματοποιούνται (Bit Error Rate – BER) και αναλύεται η υλοποίηση των αρχιτεκτονικών αυτών στο αναπτυξιακό σύστημα Xilinx. Τέλος, προκύπτουν τα κατάλληλα συμπεράσματα. / The purpose of this diploma thesis is to study and implement VLSI processors for correcting errors. The category of VLSI processor which will focus in this work is the Viterbi decoder. Initially, the structure of the digital telecommunications system is presented along with some basic concepts of error correcting codes. Then we explain the theory behind convolutional encoders and we describe the convolutional encoder that is used in my work and is consistent in the Wifi 802.11a standard. Next we analyze briefly the AWGN channel and the BPSJ modulation. Also the basic concepts of the Viterbi algorithm, how it works, its structure and the different applications are given. For the practical part which is the main part of this project, is to study the different architectures of the Viterbi decoder in VLSI approach. The main architectures that were developed for the implementation arithmetic operations is Radix-2 and Radix-4 Viterbi, but in terms of decoding two more architectures were developed, Viterbi continuous decoding-streaming applications and Viterbi decoding for packets of 20 bits. Then, the performance of these architectures in terms of frequency of errors made (BER) was investigated and also the implementation of these architectures in the development system Xilinx was analyzed. At the end we give our conclusion regarding the results of the different simulations that we’ve done.