ΑΛΓΟΡΙΘΜΟΙ ΣΥΜΠΙΕΣΗΣ ΜΟΝΟΔΙΑΣΤΑΤΩΝ ΗΜΙΠΕΡΙΟΔΙΚΩΝ ΒΙΟΙΑΤΡΙΚΩΝ ΣΗΜΑΤΩΝ ΚΑΙ ΜΕΘΟΔΟΙ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗΣ ΤΟΥΣ

Abstract

Η ΔΙΑΤΡΙΒΗ ΠΑΡΟΥΣΙΑΖΕΙ ΜΙΑ ΝΕΑ ΟΙΚΟΓΕΝΕΙΑ ΑΛΓΟΡΙΘΜΩΝ ΣΥΜΠΙΕΣΗΣ (CPBC), Η ΟΠΟΙΑ ΣΧΕΔΙΑΣΤΗΚΕ ΩΣΤΕ ΝΑ ΕΚΜΕΤΑΛΛΕΥΕΤΑΙ ΤΗΝ ΠΕΡΙΤΤΗ ΠΛΗΡΟΦΟΡΙΑ ΤΩΝ ΜΟΝΟΔΙΑΣΤΑΤΩΝ ΗΜΙΠΕΡΙΟΔΙΚΩΝ ΒΙΟΙΑΤΡΙΚΩΝ ΣΗΜΑΤΩΝ Η ΟΠΟΙΑ ΠΗΓΑΖΕΙ ΑΠΟ ΤΗΝ ΚΥΚΛΙΚΗ ΦΥΣΗ ΤΗΣ ΔΙΕΡΓΑΣΙΑΣ ΠΟΥ ΤΑ ΠΑΡΑΓΕΙ. Η ΒΑΣΙΚΗ ΙΔΕΑ ΕΙΝΑΙ ΟΤΙ ΜΙΑ ΔΕΞΑΜΕΝΗ ΠΡΟΗΓΟΥΜΕΝΩΝ ΚΥΚΛΩΝ ΤΟΥ ΣΗΜΑΤΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙ ΓΙΑ ΝΑ ΠΕΡΙΓΡΑΦΕΙ ΜΕΣΩ ΚΑΤΑΛΛΗΛΟΥ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΥ, ΤΟΥΣ ΜΕΛΛΟΝΤΙΚΟΥΣ ΚΥΚΛΟΥΣ. ΓΙΑ ΤΟ ΣΚΟΠΟ ΑΥΤΟ ΠΑΡΟΥΣΙΑΖΕΤΑΙ ΜΙΑ ΝΕΑ ΜΕΘΟΔΟΣ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟΥ ΠΟΥ ΕΠΙΤΡΕΠΕΙ ΟΧΙ ΜΟΝΟ ΤΗ ΣΥΓΚΡΙΣΗ ΤΩΝ ΚΥΚΛΩΝ ΑΛΛΑ ΚΑΙ ΤΗΝ ΑΝΤΙΚΑΤΑΣΤΑΣΗ ΤΟΥΣ ΑΠΟ ΑΛΛΟΥΣ. ΜΕ ΒΑΣΗ ΤΟ ΣΚΕΛΕΤΟ ΤΗΣ ΟΙΚΟΓΕΝΕΙΑΣ CPBC ΑΝΑΠΤΥΧΘΗΚΑΝ ΔΥΟ ΜΕΘΟΔΟΙ ΣΥΜΠΙΕΣΗΣ ΓΙΑ ΤΟ ΗΛΕΚΤΡΟΚΑΡΔΙΟΓΡΑΦΗΜΑ ΚΑΙ ΤΟ ΣΗΜΑ ΤΗΣ ΠΙΕΣΗΣ ΑΙΜΑΤΟΣ. ΟΙ ΕΠΙΔΟΣΕΙΣ ΤΩΝ ΔΥΟ ΑΥΤΩΝ ΑΛΓΟΡΙΘΜΩΝ ΟΙ ΟΠΟΙΕΣ ΞΕΠΕΡΝΟΥΝ ΠΡΟΗΓΟΥΜΕΝΕΣΜΕΘΟΔΟΥΣ, ΕΞΕΤΑΣΤΗΚΑΝ ΣΤΑΤΙΣΤΙΚΑ ΚΑΙ ΘΕΩΡΗΤΙΚΑ, ΚΑΙ ΕΞΗΧΘΗΣΑΝ ΣΥΜΠΕΡΑΣΜΑΤΑ ΓΙΑ ΤΙΣ ΒΕΛΤΙΣΤΕΣ ΠΑΡΑΜΕΤΡΟΥΣ ΛΕΙΤΟΥΡΓΙΑΣ ΤΟΥΣ. ΓΙΑ ΤΗΝ ΠΑΡΑΛΛΗΛΟΠΟΙΗΣΗ ΤΩΝ ΑΛΓΟΡΙΘΜΩΝ CPBC, ΜΕΛΕΤΗΘΗΚΕ ΤΟ ΠΡΟΒΛΗΜΑ ΤΗΣ ΒΕΛΤΙΣΤΗΣ ΚΑΤΑΝΟΜΗΣ ΔΙΑΙΡΟΥΜΕΝΟΥ ΥΠΟΛΟΓΙΣΤΙΚΟΥ ΦΟΡΤΟΥ ΣΤΟΥΣ ΚΟΜΒΟΥΣ ΤΥΧΑΙΟΥ ΔΕΝΔΡΟΥ ΕΠΕΞΕΡΓΑΣΤΩΝ. ΤΟ ΜΑΘΗΜΑΤΙΚΟ ΜΟΝΤΕΛΟ ΠΟΥ ΠΑΡΟΥΣΙΑΖΕΤΑΙ ΕΠΙΤΡΕΠΕΙ ΤΗΝ ΕΞΑΓΩΓΗ ΤΗΣ ΒΕΛΤΙΣΤΗΣ ΑΚΟΛΟΥΘΙΑΣ ΕΝΕΡΓΕΙΩΝΚΑΤΑΝΟΜΗΣ ΚΑΙ ΣΥΓΚΟΜΙΔΗΣ ΠΟΥ ΑΠΑΙΤΕΙΤΑΙ, ΚΑΘΩΣ ΚΑΙ ΤΟΝ ΥΠΟΛΟΓΙΣΜΟ ΤΗΣ ΛΥΣΗΣ ΣΕ ΧΡΟΝΟ 0(N*P), ΟΠΟΥ P ΕΙΝΑΙ ΤΟ ΠΛΗΘΟΣ ΤΩΝ ΚΟΜΒΩΝ ΤΟΥ ΔΕΝΔΡΟΥ ΚΑΙ N Ο ΜΕΓΙΣΤΟΣΒΑΘΜΟΣ ΤΟΥΣ. Η ΒΑΣΙΚΗ ΣΥΝΕΙΣΦΟΡΑ ΤΗΣ ΔΙΑΤΡΙΒΗΣ ΕΙΝΑΙ ΟΤΙ (Α) ΣΥΝΥΠΟΛΟΓΙΖΕΤΑΙ ΤΟΣΟ ΤΟ ΚΟΣΤΟΣ ΤΗΣ ΚΑΤΑΝΟΜΗΣ ΟΣΟ ΚΑΙ ΤΗΣ ΣΥΓΚΟΜΙΔΗΣ ΤΩΝ ΑΠΟΤΕΛΕΣΜΑΤΩΝ, ΚΑΙ (Β)ΕΞΕΤΑΖΟΝΤΑΙ ΤΥΧΑΙΑ ΔΕΝΔΡΑ ΕΠΕΞΕΡΓΑΣΤΩΝ.

IN THIS THESIS, A NOVEL FAMILY OF COMPRESSION ALGORITHMS (CPBC) IS PRESENTED, WHICH IS DESIGNED TO EXPLOIT THE REDUNDANCY OF 1-DIMENSIONAL SEMI-PERIODICAL BIOMEDICAL SIGNALS RESULTING FROM THE CYCLIC NATURE OF THE UNDERLYING PHYSICAL PROCESS. THE BASIC IDEA IS THAT A POOL OF PAST-SEEN CYCLES IS MAINTAINED AND SOTHAT CYCLES TO BE ENCODED CAN BE STORED AS TRANSFORMED VERSIONS OF THE ONES RESIDING IN THE POOL. A CYCLE TRANSFORMATION METHOD IS INTRODUCED IN ORDER TO RENDER THE PATTERN MATCHING PROCESS PRACTICAL AND TO ENABLE CYCLE SUBSTITUTION. BASED ON THE PRINCIPLES OF THE ALGORITHMIC FAMILY AND THIS TRANSFORMATION METHOD, TWO ALGORITHMS TARGETING THE ELECTROCARDIOGRAM AND THE BLOOD PRESSURE SIGNAL RESPECTIVELY, ARE IMPLEMENTED AND TESTED THOROUGHLY. THE PERFORMANCE OF THESE IMPLEMENTATIONS IS EXAMINED THEORETICALLY AND DEDUCTIONS ABOUT THE OPTIMAL POOL SETTINGS ARE MADE. IN ORDER TO ADDRESS THE PROBLEM OF PARALLELIZING THE CPBC ALGORITHMS, THE PROBLEM OF OPTIMALLY DISTRIBUTING A DIVISIBLE LOAD TO THE NODES OF AN ARBITRARY PROCESSOR TREE WAS ALSO TACKLED. THE RIGOROUS MATHEMATICAL FOUNDATION PRESENTED, ALLOWS THE DERIVATION OF THE SEQUENCE OF OPERATIONS THAT IS NECESSARY TO OBTAIN THE MINIMUM PROCESSING TIME ALONG WITH CLOSED-FORM EXPRESSIONS THAT YIELD THE SOLUTION IN TIME 0(N*P), WHERE P IS THE NUMBEROF TREE NODES AND N THEIR MAXIMUM DEGREE. THE MAIN CONTRIBUTIONS OF THIS WORKARE: (A) BOTH LOAD DISTRIBUTION AND RESULT COLLECTION OVERHEADS ARE CONSIDERED THUS PROVIDING BETTER RESOURCE UTILIZATION, AND (B) ARBITRARY PROCESSOR TREES ARE EXAMINED.