Αυτή η εργασία αφορά έναν αλγόριθμο διόρθωσης λαθών, που χρησιμοποιείται όταν μια δυαδική είσοδος περνάει από κανάλι μαζί με εξωτερικό θόρυβο. Τα τηλεπικοινωνιακά συστήματα αποτελούν το θεμέλιο λίθο του σύγχρονου πολιτισμού, άρα η αξιοπιστία τους είναι ύψιστης σημασίας. Συγκεκριμένα ασχολούμαστε με τους συνελικτικούς κώδικες ελέγχου ισοτιμίας με αραιούς πίνακες (convolutional LDPC). Αυτοί πρωτίστως κωδικοποιούν το περιεχόμενο του καναλιού μέσω συνέλιξης της εισόδου με μια αραιή μήτρα ισοτιμίας. Αφού το σήμα περάσει από ένα θορυβώδες κανάλι, τελούν μια ανάλογη αποκωδικοποίηση χρησιμοποιώντας την ίδια μήτρα με την κωδικοποίηση και το διάνυσμα που παράγεται από αυτή για να μαντέψουν την αρχική είσοδο. Όσον αφορά την υλοποίηση του αλγόριθμου , θα τον προσομοιώσουμε πρώτα στο περιβάλλον του Matlab για να πειραματιστούμε με διαφορετικές παραμέτρους και δεδομένα και να δούμε την ακρίβεια του αποτελέσματος. Ύστερα, θα προσομοιώσουμε τον αλγόριθμο και σε γλώσσα VHDL, μέσω της οποίας μπορούμε να το μετατρέψουμε σε ολοκληρωμένο κύκλωμα FPGA.
Αυτή η εργασία αφορά έναν αλγόριθμο διόρθωσης λαθών, που χρησιμοποιείται όταν μια δυαδική είσοδος περνάει από κανάλι μαζί με εξωτερικό θόρυβο. Τα τηλεπικοινωνιακά συστήματα αποτελούν το θεμέλιο λίθο του σύγχρονου πολιτισμού, άρα η αξιοπιστία τους είναι ύψιστης σημασίας. Συγκεκριμένα ασχολούμαστε με τους συνελικτικούς κώδικες ελέγχου ισοτιμίας με αραιούς πίνακες (convolutional LDPC). Αυτοί πρωτίστως κωδικοποιούν το περιεχόμενο του καναλιού μέσω συνέλιξης της εισόδου με μια αραιή μήτρα ισοτιμίας. Αφού το σήμα περάσει από ένα θορυβώδες κανάλι, τελούν μια ανάλογη αποκωδικοποίηση χρησιμοποιώντας την ίδια μήτρα με την κωδικοποίηση και το διάνυσμα που παράγεται από αυτή για να μαντέψουν την αρχική είσοδο. Όσον αφορά την υλοποίηση του αλγόριθμου , θα τον προσομοιώσουμε πρώτα στο περιβάλλον του Matlab για να πειραματιστούμε με διαφορετικές παραμέτρους και δεδομένα και να δούμε την ακρίβεια του αποτελέσματος. Ύστερα, θα προσομοιώσουμε τον αλγόριθμο και σε γλώσσα VHDL, μέσω της οποίας μπορούμε να το μετατρέψουμε σε ολοκληρωμένο κύκλωμα FPGA.
Η διόρθωση λαθών με κώδικες LDPC είναι μεγάλου ενδιαφέροντος σε σημαντικές νέες τηλεπικοινωνιακές εφαρμογές, όπως δορυφορικό Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) και IEEE 802.16 (WiMAX). Οι κώδικες LDPC ανήκουν στην κατηγορία των γραμμικών μπλοκ κωδικών. Πρόκειται για κώδικες ελέγχου και διόρθωσης σφαλμάτων μετάδοσης, με κυριότερο χαρακτηριστικό τους τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check), από τον οποίο και πήραν το όνομά τους. Η αποκωδικοποίηση γίνεται μέσω μιας επαναληπτικής διαδικασίας ανταλλαγής πληροφορίας μεταξύ δύο τύπων επεξεργαστικών μονάδων. Η υλοποίηση σε υλικό των LDPC αποκωδικοποιητών αποτελεί ένα ραγδαία εξελισσόμενο πεδίο για τη σύγχρονη επιστημονική έρευνα. Σκοπός της παρούσας διπλωματικής εργασίας υπήρξε ο σχεδιασμός, η υλοποίηση και η βελτιστοποίηση αρχιτεκτονικών αποκωδικοποιητών VLSI για κώδικες LDPC. Έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Μελετήθηκαν αρχιτεκτονικές βασισμένες σε δύο αλγόριθμους, τον log Sum-Product και τον Min-Sum. Ο πρώτος είναι θεωρητικά βέλτιστος, αλλά ο Min-Sum είναι αρκετά απλούστερος και έχει μεγαλύτερο πρακτικό ενδιαφέρον στα πλαίσια μιας ρεαλιστικής εφαρμογής. Συγκεκριμένα, αναπτύχθηκαν δύο αλγόριθμοι αποκωδικοποίησης, οι οποίοι χρησιμοποιούν ως δομικά στοιχεία, τους δύο προαναφερθέντες αλγορίθμους και τη φιλοσοφία του layered decoding. Η μελέτη μας επικεντρώθηκε σε κώδικες, η δομή των πινάκων ελέγχου ισοτιμίας των οποίων, προσφέρεται για υλοποίηση. Για αυτό το λόγο, χρησιμοποιήσαμε κώδικες του προτύπου WiMax 802.16e. Η συνεισφορά της παρούσας εργασίας έγκειται στο σχεδιασμό και την υλοποίηση αποδοτικών αρχιτεκτονικών σε επίπεδο επιφάνειας και ταχύτητας αποκωδικοποίησης (Mbps), καθώς και η διερεύνηση του σχετικού σχεδιαστικού χώρου, χρησιμοποιώντας ως σχεδιαστικές παραμέτρους, τον αλγόριθμο αποκωδικοποίησης, τη χρονοδρομολόγηση των πράξεων, το βαθμό παραλληλίας της αρχιτεκτονικής, το βάθος του pipelining και την αριθμητική αναπαράσταση των δεδομένων. Επιπλέον, είναι σημαντικό να αναφέρουμε πως, στα πλαίσια της σχεδίασης του LDPC αποκωδικοποιητή και με τη βοήθεια του εργαλείου Matlab, αναπτύχθηκαν παραμετρικά scripts για την παραγωγή του VHDL κώδικα. Οι δύο βασικές παράμετροι που χρησιμοποιήθηκαν ήταν το πλήθος των επεξεργαστικών μονάδων και το μήκος λέξης των δεδομένων. Τα scripts αυτά αποτέλεσαν ένα πολύ χρήσιμο εργαλείο κατά τη διαδικασία ανάπτυξης και βελτιστοποίησης της αρχιτεκτονικής, δίνοντας μας τη δυνατότητα να παράγουμε με αυτοματοποιημένο και γρήγορο τρόπο τον VHDL κώδικα, για τις επιμέρους μονάδες του αποκωδικοποιητή. Η υλοποίηση ενός μοντέλου αποκωδικοποιητή σε υλικό, μας δίνει τη δυνατότητα να διεξάγουμε ταχύτατες εξομοιώσεις, σε σχέση με αντίστοιχες υλοποιήσεις σε λογισμικό (π.χ. σε Matlab περιβάλλον). Διαθέτουμε, έτσι, ένα ισχυρό εργαλείο για τη μελέτη της επίδοσης διαφόρων ρεαλιστικών υλοποιήσεων αποκωδικοποιητών. Κατά τη διάρκεια της υλοποίησης, αξιοποιήθηκε αναπτυξιακό σύστημα βασισμένο σε virtex-4 fpga.
Οι κώδικες LDPC ανήκουν στην κατηγορία των block κωδικών. Πρόκειται για κώδικες ελέγχου σφαλμάτων μετάδοσης και πιο συγκεκριμένα για κώδικες διόρθωσης σφαλμάτων. Αν και η εφεύρεσή τους (από τον Gallager) τοποθετείται χρονικά στις αρχές της δεκαετίας του 60, μόλις τα τελευταία χρόνια κατάφεραν να κεντρίσουν το έντονο ενδιαφέρον της επιστημονικής-ερευνητικής κοινότητας για τις αξιόλογες επιδόσεις τους. Πρόκειται για κώδικες ελέγχου ισοτιμίας με κυριότερο χαρακτηριστικό τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check) από τον οποίο και πήραν το όνομά τους. Δεδομένου ότι η κωδικοποίηση των συγκεκριμένων κωδικών είναι σχετικά απλή, η αποκωδικοποίηση τους είναι εκείνη η οποία καθορίζει σε μεγάλο βαθμό τα χαρακτηριστικά του κώδικα που μας ενδιαφέρουν, όπως είναι η ικανότητα διόρθωσης σφαλμάτων μετάδοσης (επίδοση) και η καταναλισκόμενη ισχύς. Για το λόγο αυτό έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Παρόλο που οι ανεπτυγμένοι αλγόριθμοι και οι διάφορες εκδοχές τους δεν είναι λίγοι, δεν έχει ακόμα καταστεί εφικτό να αναλυθεί θεωρητικά η επίδοσή τους. Στην παρούσα εργασία παρατίθενται οι κυριότεροι αλγόριθμοι αποκωδικοποίησης κωδικών LDPC, που έχουν αναπτυχθεί μέχρι σήμερα. Οι αλγόριθμοι αυτοί υλοποιούνται και συγκρίνονται βάσει των αποτελεσμάτων εξομοιώσεων. Ο πιο αποδοτικός από αυτούς είναι ο αποκαλούμενος αλγόριθμος log Sum-Product και στηρίζει σε μεγάλο βαθμό την επίδοσή του σε μία αρκετά πολύπλοκή συνάρτηση, την Φ(x). Η υλοποίηση της τελευταίας σε υλικό επιβάλλει την πεπερασμένη ακρίβεια αναπαράστασής της, δηλαδή τον κβαντισμό της. Το σφάλμα κβαντισμού που εισάγεται από την διαδικασία αυτή θέτει ένα όριο στην επίδοση του αλγορίθμου. Η μελέτη που έγινε στα πλαίσια της εργασίας οδήγησε στον προσδιορισμό δύο μηχανισμών εισαγωγής σφάλματος κβαντισμού στον αλγόριθμο log Sum-Product και στη θεωρητική έκφραση της πιθανότητας εμφάνισης κάθε μηχανισμού κατά την πρώτη επανάληψη του αλγορίθμου. Μελετήθηκε επίσης ο τρόπος με τον οποίο το εισαγόμενο σφάλμα κβαντισμού επιδρά στην απόφαση του αλγορίθμου στο τέλος της κάθε επανάληψης και αναπτύχθηκε ένα θεωρητικό μοντέλο αυτού του μηχανισμού. Το θεωρητικό μοντέλο δίνει την πιθανότητα αλλαγής απόφασης του αλγορίθμου λόγω του σφάλματος κβαντισμού της συνάρτησης Φ(x), χωρίς όμως να είναι ακόμα πλήρες αφού βασίζεται και σε πειραματικά δεδομένα. Η ολοκλήρωση του μοντέλου, ώστε να είναι πλήρως θεωρητικό, θα μπορούσε να αποτελέσει αντικείμενο μελλοντικής έρευνας, καθώς θα επιτρέψει τον προσδιορισμό του περιορισμού της επίδοσης του αλγορίθμου για συγκεκριμένο σχήμα κβαντισμού της συνάρτησης, αποφεύγοντας χρονοβόρες εξομοιώσεις.
Η παρούσα διπλωματική εργασία αφορά την ανάπτυξη βιβλιοθήκης συναρτήσεων για κβαντικό υπολογισμό και τη δημιουργία γραφικού περιβάλλοντος το οποίο χρησιμοποιεί τη συγκεκριμένη βιβλιοθήκη. Αρχικά μελετήθηκαν: πρώτον, οι βασικές έννοιες που διέπουν τους κβαντικούς υπολογιστές και δεύτερον, η χρήση και οι δυνατότητες της γλώσσας python. Εν συνέχεια, ύστερα από εμβάθυνση στα ανωτέρω πεδία πραγματοποιήθηκε η συγγραφή της κβαντικής βιβλιοθήκης καθώς και η δημιουργία του γραφικού περιβάλλοντος που χρησιμοποιεί τη κβαντική αυτή βιβλιοθήκη. Επίσης δημιουργήθηκε και μία γραφική διεπαφή για την παρουσίαση των γραφικών παραστάσεων που παρουσιάζουν τα αποτελέσματα του κβαντικού υπολογισμού. Η ανάπτυξη του προγράμματος πραγματοποιήθηκε σε γλώσσα Python.
Οι κώδικες LDPC είναι κώδικες διόρθωσης σφαλμάτων που παρέχουν επιδόσεις ρυθμού μετάδοσης πληροφορίας κοντά στη χωρητικότητα του καναλιού και προτάθηκαν για πρώτη φορά από τον Gallager στις αρχές της δεκαετίας του 60. Ωστόσο, μέχρι τα μέσα της δεκαετίας του 90, παρέμειναν στο περιθώριο καθώς η υλοποίηση των αποκωδικοποιητών τους σε υλικό δεν ήταν δυνατή μέχρι τότε. Χαρακτηρίζονται από έναν αραιό πίνακα ελέγχου ισοτιμίας ο οποίος καθορίζει το κύκλωμα και κατά συνέπεια την πολυπλοκότητα του αποκωδικοποιητή. Στην παρούσα εργασία παρουσιάζονται οι κυριότεροι LDPC αλγόριθμοι αποκωδικοποίησης που έχουν αναπτυχθεί μέχρι σήμερα. Ακόμη, έγιναν συγκρίσεις μεταξύ τους για τους κώδικες του προτύπου IEEE 802.11ac σε απλές συνθήκες μετάδοσης και του προτύπου IEEE 802.11ah για όλες τις πιθανές συνθήκες μετάδοσης. Σκοπός αυτής της χαρτογράφησης ήταν η εύρεση της βέλτιστης επιλογής αλγορίθμου ανάλογα με τις εκάστοτε συνθήκες. Μετά από μελέτη των αλγορίθμων, διαπιστώθηκε μια έντονη μείωση της απόδοσης ορισμένων αποκωδικοποιητών όταν υπόκεινται σε puncturing, μια διαδικασία επεξεργασίας που έχει ως σκοπό την αύξηση του πραγματικού ρυθμού του κώδικα. Στην συνέχεια έγινε διερεύνηση της συμπεριφοράς των συγκεκριμένων αλγορίθμων και προτάθηκαν προσεγγίσεις ώστε να βελτιωθούν οι επιδόσεις τους σε επίπεδο ρυθμού σφαλμάτων. Τέλος, σχεδιάστηκε ένα από τα προτεινόμενα συστήματα αποκωδικοποίησης punctured κωδίκων σε γλώσσα υλικού και υλοποιήθηκε με την βοήθεια εργαλείων σχεδίασης. Χρησιμοποιήθηκαν διάφορες μέθοδοι σχεδίασης με σκοπό να μειωθεί η συνολική απαιτούμενη επιφάνεια υλικού της αρχιτεκτονικής και να αυξηθεί το throughput της σχεδίασης.
H διπλωματική εργασία αποτελεί μια βιβλιογραφική ανασκόπηση της θεωρίας και των εφαρμογών στην περιοχή της Κρυπτογραφίας Πλεγμάτων (Lattice Cryptography). Ένας μακροπρόθεσμος στόχος στην Κρυπτογραφία Δημοσίου Κλειδιού, για τη μετάβαση από τις υφιστάμενες και δοκιμασμένες μεθόδους σε προτάσεις για τις μελλοντικές γενιές επεξεργαστών (quantum-safe cryptography), είναι η αντικατάσταση των πρωταρχικών δομικών κρυπτογραφικών στοιχείων (cryptographic primitives). Προϋπόθεση για την επίτευξη αυτού του στόχου είναι η εύρεση εναλλακτικών οι οποίες στηρίζονται σε μαθηματικό υπόβαθρο (provable security) και επιπλέον ικανοποιούν τις τεχνικές απαιτήσεις για πρακτική ασφάλεια (security levels) και αποδοτική υλοποίηση (efficiency properties). H Κρυπτογραφία Πλεγμάτων έχει αναδειχθεί τις τελευταίες δεκαετίες σε μια ερευνητική περιοχή που συγκεντρώνει μεγάλο ενδιαφέρον τόσο για τον πλούτο των θεωρητικών κατασκευών όσο και για τις πιο πρόσφατες επιτυχίες στις προτάσεις υλοποίησης αποδοτικών αλγορίθμων. Στο Κεφάλαιο 1 δίνεται η μαθηματική περιγραφή και οι βασικοί αλγόριθμοι για τα υπολογιστικά προβλήματα πλεγμάτων που αξιοποιούνται στην κρυπτογραφία. Στο Κεφάλαιο 2 παρουσιάζονται οι τεχνικές κατασκευής πρωταρχικών κρυπτογραφικών στοιχείων οι οποίες βασίζονται στα προβλήματα Learning With Errors (LWE) και Short Integer Solution (SIS) με αναγωγή σε προβλήματα πλεγμάτων. Καταγράφονται, επίσης, τα κλασικά συστήματα κρυπτογράφησης και ψηφιακών υπογραφών τα οποία έχουν μελετηθεί στον ακαδημαϊκό χώρο. Στο Κεφάλαιο 3 γίνεται αναφορά στις πρόσφατες προσπάθειες προτυποποίησης και σε ορισμένα σύγχρονα κρυπτογραφικά σχήματα που έχουν υλοποιηθεί. Το μεγάλο εύρος στο ακαδημαϊκό πεδίο της έρευνας καθιστά δύσκολη την εξαντλητική συγκριτική ανάλυση και πολλές πρακτικές λεπτομέρειες δεν έχουν διευκρινιστεί ακόμα. H βιομηχανία τελικά θα υιοθετήσει μόνο τις ολοκληρωμένες κρυπτογραφικές προτάσεις που έχουν διερευνηθεί και προτυποποιηθεί από την ερευνητική κοινότητα. Η συστηματική θεμελίωση και αξιολόγηση των υποσχόμενων νέων τεχνικών κρυπτογράφησης πρέπει να προηγηθεί της έρευνας και κατασκευής νέων επεξεργαστών, οι οποίοι θα επιβάλλουν ριζική αναθεώρηση της δημόσιας Κρυπτογραφίας. Στο άμεσο μέλλον αναμένεται να συγκεντρωθούν και να παρουσιαστούν σαφέστερα οι επικρατέστερες εναλλακτικές προκειμένου να καθοριστούν συγκεκριμένες κατευθύνσεις εξειδίκευσης της έρευνας · είναι βέβαιο ότι οι κατασκευές της σύγχρονης Κρυπτογραφίας Πλεγμάτων θα έχουν θέση ανάμεσα σε αυτές.
Οι κώδικες LDPC ανήκουν στην κατηγορία των block κωδίκων. Πρόκειται για κώδικες ελέγχου σφαλμάτων μετάδοσης και πιο συγκεκριμένα για κώδικες διόρθωσης σφαλμάτων. Αν και αναπτύχθηκαν από τον Gallager στις αρχές της δεκαετίας του 60, μόλις τα τελευταία χρόνια έχουν καταφέρει να κεντρίσουν το ενδιαφέρον της επιστημονικής και ερευνητικής κοινότητας λόγω και της ραγδαίας ανάπτυξης στο κομμάτι της αρχιτεκτονικής υλικού που επιτρέπει την πιο εύκολη υλοποίησή τους παρά την μεγάλη υπολογιστή τους πολυπλοκότητα. Είναι κώδικες ελέγχου ισοτιμίας με κυριότερο χαρακτηριστικό τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check) από τον οποίο πήραν και το όνομά τους. Δεδομένου ότι η κωδικοποίηση των συγκεκριμένων κωδίκων είναι σχετικά απλή, η αποκωδικοποίησή τους είναι εκείνη που καθορίζει σε μεγάλο βαθμό τα χαρακτηριστικά του κώδικα που μας ενδιαφέρουν, όπως η ικανότητα διόρθωσης σφαλμάτων μετάδοσης (επίδοση). Για αυτό το λόγο έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Στην παρούσα διπλωματική εργασία μελετήθηκε η υλοποίηση του LDPC αποκωδικοποιητή της matlab με χρήση ενός κβαντιστή που είναι βασισμένος στην μέθοδο του Information Bottleneck και συγκεκριμένα στον τροποποιημένο Sequential Information Bottleneck που ανέπτυξαν οι Jan Lewandowsky και Gerhard Bauch. Μελετήθηκε η απόδοση του αποκωδικοποιητή για πέντε διαφορετικούς πίνακες ελέγχου ισοτιμίας για 5 και 10 επαναλήψεις του αποκωδικοποιητή και ελέγχθηκε η απόδοσή του σε σύγκριση με την υλοποίηση με έναν γραμμικό κβαντιστή με ίδια αλλά και περισσότερα bit κβάντισης, σύμφωνα με τα πειραματικά δεδομένα της υλοποίησης. Τέλος, εξετάστηκε η υλοποίηση του κβαντιστή σε αρχιτεκτονικές υλικού.