{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1332868"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1332868","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΜΟΝΑΔΑΣ ΥΠΟΛΟΓΙΣΜΟΥ BUTTERFLY ΓΙΑ ΤΟΝ ΑΛΓΟΡΙΘΜΟ FFT","abstract":"Ο σκοπός της διπλωματικής εργασίας αυτής είναι η διερεύνηση της λειτουργίας της μονάδας υπολογισμού πεταλούδας, Butterfly Computation Unit (BCU), και η παρουσίαση δύο εναλλακτικών αρχιτεκτονικών για την υλοποίηση της μονάδας αυτής. Η μονάδα υπολογισμού Butterfly είναι η βασική μονάδα για την υλοποίηση μονάδων Fast Fourier Transform (FFT) για αποδεκατισμό στο πεδίο του χρόνου, η οποία χρησιμοποιείται ευρέως σε εφαρμογές Ψηφιακής Επεξεργασίας Σημάτων όπως η Ανάλυση Φάσματος σημάτων, η Συμπίεση Δεδομένων, η σχεδίαση φίλτρων, η λύση Μερικών Διαφορικών Εξισώσεων, ο Πολλαπλασιασμός Πολυωνύμων, και ο υπολογισμός Συνέλιξης. Σκοπός της παρούσας εργασίας είναι η διερεύνηση μίας συμβατικής υλοποίησης της μονάδας υπολογισμού πεταλούδας, αλλά και τριών εναλλακτικών μονάδων οι οποίες έχουν σχεδιαστεί με σκοπό την αποδοτικότερη υλοποίησή της. Συγκεκριμένα, προτείνεται η χρήση του αλγορίθμου του Gauss, για τον πολλαπλασιασμό δύο μιγαδικών αριθμών καθώς η πράξη αυτή περιέχει το μεγαλύτερο υπολογιστικό φόρτο στην μονάδα υπολογισμού πεταλούδας. Επίσης, προτείνεται η χρήση προ-κωδικοποιημένων πολλαπλασιαστών για την υλοποίηση της Μονάδας Μιγαδικού Πολλαπλασιασμού, με σκοπό την περαιτέρω βελτίωση της λειτουργίας της, σε αντιπαράθεση με την συμβατική της υλοποίηση, που κάνει χρήση πολλαπλασιαστών κωδικοποίησης Modified Booth. Οι παραπάνω μονάδες περιγράφηκαν με χρήση της γλώσσας περιγραφής υλικού Verilog, στην συνέχεια επαληθεύσαμε την ορθότητα λειτουργίας τους και συνθέσαμε τα κυκλώματα αυτά, με σκοπό να τα συγκρίνουμε ως προς την καθυστέρηση, την επιφάνεια που καταλαμβάνει το κύκλωμά τους, αλλά και την κατανάλωση ενέργειάς τους, με χρήση των εργαλείων σύνθεσης και προσομοίωσης της Synopsys. Τέλος, έγινε παρουσίαση των αποτελεσμάτων που προέκυψαν, καθώς και μία συγκριτική μελέτη τους για τα διάφορα μήκη λέξης εισόδου. Έτσι προέκυψαν τα απαραίτητα συμπεράσματα για την λειτουργία των διαφορετικών σχημάτων που υλοποιήθηκαν, καθώς, κάθε ένα από τα σχήματα που σχεδιάστηκαν, έδωσε αποτελέσματα που τα καθιστά κατάλληλα για διαφορετικές εφαρμογές, ανάλογα με το που εμφανίζουν την βέλτιστη συμπεριφορά τους.","abstract_html":"Ο σκοπός της διπλωματικής εργασίας αυτής είναι η διερεύνηση της λειτουργίας της μονάδας υπολογισμού πεταλούδας, Butterfly Computation Unit (BCU), και η παρουσίαση δύο εναλλακτικών αρχιτεκτονικών για την υλοποίηση της μονάδας αυτής. Η μονάδα υπολογισμού Butterfly είναι η βασική μονάδα για την υλοποίηση μονάδων Fast Fourier Transform (FFT) για αποδεκατισμό στο πεδίο του χρόνου, η οποία χρησιμοποιείται ευρέως σε εφαρμογές Ψηφιακής Επεξεργασίας Σημάτων όπως η Ανάλυση Φάσματος σημάτων, η Συμπίεση Δεδομένων, η σχεδίαση φίλτρων, η λύση Μερικών Διαφορικών Εξισώσεων, ο Πολλαπλασιασμός Πολυωνύμων, και ο υπολογισμός Συνέλιξης. Σκοπός της παρούσας εργασίας είναι η διερεύνηση μίας συμβατικής υλοποίησης της μονάδας υπολογισμού πεταλούδας, αλλά και τριών εναλλακτικών μονάδων οι οποίες έχουν σχεδιαστεί με σκοπό την αποδοτικότερη υλοποίησή της. Συγκεκριμένα, προτείνεται η χρήση του αλγορίθμου του Gauss, για τον πολλαπλασιασμό δύο μιγαδικών αριθμών καθώς η πράξη αυτή περιέχει το μεγαλύτερο υπολογιστικό φόρτο στην μονάδα υπολογισμού πεταλούδας. Επίσης, προτείνεται η χρήση προ-κωδικοποιημένων πολλαπλασιαστών για την υλοποίηση της Μονάδας Μιγαδικού Πολλαπλασιασμού, με σκοπό την περαιτέρω βελτίωση της λειτουργίας της, σε αντιπαράθεση με την συμβατική της υλοποίηση, που κάνει χρήση πολλαπλασιαστών κωδικοποίησης Modified Booth. Οι παραπάνω μονάδες περιγράφηκαν με χρήση της γλώσσας περιγραφής υλικού Verilog, στην συνέχεια επαληθεύσαμε την ορθότητα λειτουργίας τους και συνθέσαμε τα κυκλώματα αυτά, με σκοπό να τα συγκρίνουμε ως προς την καθυστέρηση, την επιφάνεια που καταλαμβάνει το κύκλωμά τους, αλλά και την κατανάλωση ενέργειάς τους, με χρήση των εργαλείων σύνθεσης και προσομοίωσης της Synopsys. Τέλος, έγινε παρουσίαση των αποτελεσμάτων που προέκυψαν, καθώς και μία συγκριτική μελέτη τους για τα διάφορα μήκη λέξης εισόδου. Έτσι προέκυψαν τα απαραίτητα συμπεράσματα για την λειτουργία των διαφορετικών σχημάτων που υλοποιήθηκαν, καθώς, κάθε ένα από τα σχήματα που σχεδιάστηκαν, έδωσε αποτελέσματα που τα καθιστά κατάλληλα για διαφορετικές εφαρμογές, ανάλογα με το που εμφανίζουν την βέλτιστη συμπεριφορά τους.","abstract_has_math":false,"creators":["Ντούσκας Φώτιος","Ntouskas Fotios"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-11-19T05:27:45Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1332868"],"render_values":[{"text":"uoadl:1332868","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1332868","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1332868","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1332868","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Ντούσκας Φώτιος","Ntouskas Fotios"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1332868","https://pergamos.lib.uoa.gr/uoa/dl/object/1332868"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ο σκοπός της διπλωματικής εργασίας αυτής είναι η διερεύνηση της λειτουργίας της μονάδας υπολογισμού πεταλούδας, Butterfly Computation Unit (BCU), και η παρουσίαση δύο εναλλακτικών αρχιτεκτονικών για την υλοποίηση της μονάδας αυτής. Η μονάδα υπολογισμού Butterfly είναι η βασική μονάδα για την υλοποίηση μονάδων Fast Fourier Transform (FFT) για αποδεκατισμό στο πεδίο του χρόνου, η οποία χρησιμοποιείται ευρέως σε εφαρμογές Ψηφιακής Επεξεργασίας Σημάτων όπως η Ανάλυση Φάσματος σημάτων, η Συμπίεση Δεδομένων, η σχεδίαση φίλτρων, η λύση Μερικών Διαφορικών Εξισώσεων, ο Πολλαπλασιασμός Πολυωνύμων, και ο υπολογισμός Συνέλιξης. Σκοπός της παρούσας εργασίας είναι η διερεύνηση μίας συμβατικής υλοποίησης της μονάδας υπολογισμού πεταλούδας, αλλά και τριών εναλλακτικών μονάδων οι οποίες έχουν σχεδιαστεί με σκοπό την αποδοτικότερη υλοποίησή της. Συγκεκριμένα, προτείνεται η χρήση του αλγορίθμου του Gauss, για τον πολλαπλασιασμό δύο μιγαδικών αριθμών καθώς η πράξη αυτή περιέχει το μεγαλύτερο υπολογιστικό φόρτο στην μονάδα υπολογισμού πεταλούδας. Επίσης, προτείνεται η χρήση προ-κωδικοποιημένων πολλαπλασιαστών για την υλοποίηση της Μονάδας Μιγαδικού Πολλαπλασιασμού, με σκοπό την περαιτέρω βελτίωση της λειτουργίας της, σε αντιπαράθεση με την συμβατική της υλοποίηση, που κάνει χρήση πολλαπλασιαστών κωδικοποίησης Modified Booth. Οι παραπάνω μονάδες περιγράφηκαν με χρήση της γλώσσας περιγραφής υλικού Verilog, στην συνέχεια επαληθεύσαμε την ορθότητα λειτουργίας τους και συνθέσαμε τα κυκλώματα αυτά, με σκοπό να τα συγκρίνουμε ως προς την καθυστέρηση, την επιφάνεια που καταλαμβάνει το κύκλωμά τους, αλλά και την κατανάλωση ενέργειάς τους, με χρήση των εργαλείων σύνθεσης και προσομοίωσης της Synopsys. Τέλος, έγινε παρουσίαση των αποτελεσμάτων που προέκυψαν, καθώς και μία συγκριτική μελέτη τους για τα διάφορα μήκη λέξης εισόδου. Έτσι προέκυψαν τα απαραίτητα συμπεράσματα για την λειτουργία των διαφορετικών σχημάτων που υλοποιήθηκαν, καθώς, κάθε ένα από τα σχήματα που σχεδιάστηκαν, έδωσε αποτελέσματα που τα καθιστά κατάλληλα για διαφορετικές εφαρμογές, ανάλογα με το που εμφανίζουν την βέλτιστη συμπεριφορά τους.","The scope of the thesis is the exploration of the Butterfly Computation Unit, and the introduction of two alternative architectures for the implementation of the said unit. The Butterfly Computation Unit is the most essential unit for the implementation of the algorithm of the Fast Fourier Transform, for Decimation in Time, that is used widely in applications for Digital Signals Processing like Spectral Analysis, Data Compression, and in solving Partial Differential equations, Filtering algorithms, Polynomial Multiplication and Convolution. The purpose of this thesis is the exploration of a conventional implementation of the Butterfly Computation Unit, but also three more alternative schemes that have been designed in order to be more efficient than the conventional one. Specifically, we propose the use of the Gauss algorithm for multiplying two complex numbers as this operation contains the largest computational effort in the Butterfly Computation Unit. Also, we proposed the use of pre-encoded multipliers to implement the complex number multiplication unit, in order to further improve its functioning, in juxtaposition with the conventional implementation, which uses Modified Booth multipliers. The units described above have been implemented, using Verilog hardware description language, next, their functionality has been behaviorally verified and we synthesized the circuits in order to experimentally compare them in delay, area and power consumption, using the Synopsys tools. Lastly, we presented the results that arose, and we also presented a comparative study for various input bit-widths. This way, we reached the necessary conclusions for the operation of the different proposed schemes that we designed and implemented, and according to the findings each proposed scheme showed its advantages, depending on the application that they are targeted for, where they appear to perform optimally."]},{"key":"dc:title","label":"Title","values":["ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΜΟΝΑΔΑΣ ΥΠΟΛΟΓΙΣΜΟΥ BUTTERFLY ΓΙΑ ΤΟΝ ΑΛΓΟΡΙΘΜΟ FFT"]}]}],"canonical_facts":{"dc:creator":["Ντούσκας Φώτιος","Ntouskas Fotios"],"dc:date":["2017"],"dc:description":["Ο σκοπός της διπλωματικής εργασίας αυτής είναι η διερεύνηση της λειτουργίας της μονάδας υπολογισμού πεταλούδας, Butterfly Computation Unit (BCU), και η παρουσίαση δύο εναλλακτικών αρχιτεκτονικών για την υλοποίηση της μονάδας αυτής. Η μονάδα υπολογισμού Butterfly είναι η βασική μονάδα για την υλοποίηση μονάδων Fast Fourier Transform (FFT) για αποδεκατισμό στο πεδίο του χρόνου, η οποία χρησιμοποιείται ευρέως σε εφαρμογές Ψηφιακής Επεξεργασίας Σημάτων όπως η Ανάλυση Φάσματος σημάτων, η Συμπίεση Δεδομένων, η σχεδίαση φίλτρων, η λύση Μερικών Διαφορικών Εξισώσεων, ο Πολλαπλασιασμός Πολυωνύμων, και ο υπολογισμός Συνέλιξης. Σκοπός της παρούσας εργασίας είναι η διερεύνηση μίας συμβατικής υλοποίησης της μονάδας υπολογισμού πεταλούδας, αλλά και τριών εναλλακτικών μονάδων οι οποίες έχουν σχεδιαστεί με σκοπό την αποδοτικότερη υλοποίησή της. Συγκεκριμένα, προτείνεται η χρήση του αλγορίθμου του Gauss, για τον πολλαπλασιασμό δύο μιγαδικών αριθμών καθώς η πράξη αυτή περιέχει το μεγαλύτερο υπολογιστικό φόρτο στην μονάδα υπολογισμού πεταλούδας. Επίσης, προτείνεται η χρήση προ-κωδικοποιημένων πολλαπλασιαστών για την υλοποίηση της Μονάδας Μιγαδικού Πολλαπλασιασμού, με σκοπό την περαιτέρω βελτίωση της λειτουργίας της, σε αντιπαράθεση με την συμβατική της υλοποίηση, που κάνει χρήση πολλαπλασιαστών κωδικοποίησης Modified Booth. Οι παραπάνω μονάδες περιγράφηκαν με χρήση της γλώσσας περιγραφής υλικού Verilog, στην συνέχεια επαληθεύσαμε την ορθότητα λειτουργίας τους και συνθέσαμε τα κυκλώματα αυτά, με σκοπό να τα συγκρίνουμε ως προς την καθυστέρηση, την επιφάνεια που καταλαμβάνει το κύκλωμά τους, αλλά και την κατανάλωση ενέργειάς τους, με χρήση των εργαλείων σύνθεσης και προσομοίωσης της Synopsys. Τέλος, έγινε παρουσίαση των αποτελεσμάτων που προέκυψαν, καθώς και μία συγκριτική μελέτη τους για τα διάφορα μήκη λέξης εισόδου. Έτσι προέκυψαν τα απαραίτητα συμπεράσματα για την λειτουργία των διαφορετικών σχημάτων που υλοποιήθηκαν, καθώς, κάθε ένα από τα σχήματα που σχεδιάστηκαν, έδωσε αποτελέσματα που τα καθιστά κατάλληλα για διαφορετικές εφαρμογές, ανάλογα με το που εμφανίζουν την βέλτιστη συμπεριφορά τους.","The scope of the thesis is the exploration of the Butterfly Computation Unit, and the introduction of two alternative architectures for the implementation of the said unit. The Butterfly Computation Unit is the most essential unit for the implementation of the algorithm of the Fast Fourier Transform, for Decimation in Time, that is used widely in applications for Digital Signals Processing like Spectral Analysis, Data Compression, and in solving Partial Differential equations, Filtering algorithms, Polynomial Multiplication and Convolution. The purpose of this thesis is the exploration of a conventional implementation of the Butterfly Computation Unit, but also three more alternative schemes that have been designed in order to be more efficient than the conventional one. Specifically, we propose the use of the Gauss algorithm for multiplying two complex numbers as this operation contains the largest computational effort in the Butterfly Computation Unit. Also, we proposed the use of pre-encoded multipliers to implement the complex number multiplication unit, in order to further improve its functioning, in juxtaposition with the conventional implementation, which uses Modified Booth multipliers. The units described above have been implemented, using Verilog hardware description language, next, their functionality has been behaviorally verified and we synthesized the circuits in order to experimentally compare them in delay, area and power consumption, using the Synopsys tools. Lastly, we presented the results that arose, and we also presented a comparative study for various input bit-widths. This way, we reached the necessary conclusions for the operation of the different proposed schemes that we designed and implemented, and according to the findings each proposed scheme showed its advantages, depending on the application that they are targeted for, where they appear to perform optimally."],"dc:identifier":["uoadl:1332868","https://pergamos.lib.uoa.gr/uoa/dl/object/1332868"],"dc:language":["Ελληνικά","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΜΟΝΑΔΑΣ ΥΠΟΛΟΓΙΣΜΟΥ BUTTERFLY ΓΙΑ ΤΟΝ ΑΛΓΟΡΙΘΜΟ FFT"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:27:45Z"}