Number Systems

Από το βιβλίο ‘ΕΙΣΑΓΩΓΗ ΣΤΗΝ ΠΛΗΡΟΦΟΡΙΚΗ’ Β. Αναστασόπουλου – Α. Σκόδρα, Ελληνικά Γράµµατα, 2001

Κεφάλαιο 2 Αναπαράσταση των δεδοµένων στον Η/Υ Η πληροφορία αποτελεί ένα από τα συστατικά στοιχεία, ίσως το σηµαντικότερο, της σύγχρονης εποχής. Η ταχύτητα στη µετάδοσή της αλλά και στην επεξεργασία της είναι ζωτικής σηµασίας για τις περισσότερες ανθρώπινες δραστηριότητες. Στο κεφάλαιο αυτό θα εξετάσουµε τη µορφή των δεδοµένων που συνθέτουν την πληροφορία η οποία θα εισέλθει στον Η/Υ για επεξεργασία. Επισηµάνθηκε στο προηγούµενο κεφάλαιο ότι ο ψηφιακός Η/Υ χειρίζεται δυαδικούς αριθµούς. Στο κεφάλαιο αυτό θα µελετηθούν τα συστήµατα αρίθµησης και κυρίως το 'φυσικό' δυαδικό και η σχέση του µε το 'ανθρωποκεντρικό' δεκαδικό. Θα εξεταστούν επίσης όλες οι πράξεις στο δυαδικό σύστηµα αρίθµησης όπως αυτές εκτελούνται από τον Η/Υ και οι τρόποι µετατροπής των δεδοµένων από το ένα σύστηµα αρίθµησης στο άλλο. Στη συνέχεια του κεφαλαίου περιγράφεται ο τρόπος αναπαράστασης των αριθµών στο Η/Υ ανάλογα µε το µέγεθός τους καθώς επίσης και ο τρόπος κωδικοποίησής τους για αποθήκευση ή µετάδοση. Θα περιγραφούν επίσης διαδικασίες ελέγχου της ακρίβειας των δεδοµένων. Ο όγκος των δεδοµένων και ο χώρος µνήµης που καταλαµβάνουν στον Η/Υ είναι τελευταίο θέµα του κεφαλαίου.

Σχήµα 2.1. Η σηµασία της πληροφορίας για τον άνθρωπο ήταν ανέκαθεν πολύ σηµαντική ανεξάρτητα από τον τρόπο µετάδοσης ή επεξεργασίας της.

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

2.1. Τύποι δεδοµένων Η επεξεργασία των δεδοµένων είναι θέµα που αντιµετώπισε ο άνθρωπος από αρχαιοτάτων χρόνων είτε µε τους πρακτικούς τρόπους των Αιγυπτίων ή µε τους θεωρητικούς των Σουµερίων. Η όσο το δυνατόν ταχύτερη µετάδοσή τους ήταν επίσης ένα πρόβληµα που αντιµετωπίστηκε µε τη χρήση αγγελιαφόρων, περιστεριών, τυµπάνων ή ακόµη και καπνού (σχήµα 2.1). Τόσο στην επεξεργασία όσο και στη µετάδοση της πληροφορίας, παράµετροι όπως η ασφάλεια, η ακρίβεια αλλά και η κωδικοποίηση απασχόλησαν συνειδητά ή όχι τον άνθρωπο. Σε τελική ανάλυση, ανεξάρτητα από τον τρόπο µετάδοσης και επεξεργασίας το ενδιαφέρον εστιάστηκε στην ίδια την πληροφορία και το πόσο σηµαντική είναι για τον χρήστη-παραλήπτη. Οι τρόποι µετάδοσης και επεξεργασίας ακόµη και στις µέρες µας βελτιώνονται συνεχώς και µερικές φορές αλλάζουν ριζικά. Έµφαση εποµένως θα πρέπει να δοθεί κατ' αρχή στην οργάνωση της ίδιας της πληροφορίας και κατά δεύτερο λόγο στις διαδικασίες µετάδοσης και επεξεργασίας. Με άλλα λόγια η βελτίωση των διαδικασιών αυτών δεν µπορεί να είναι αυτοσκοπός, αλλά πρέπει να έχει πάντα στόχο τα ίδια τα δεδοµένα το περιεχόµενό τους και τη φυσική τους οργάνωση. Έτσι η µετάδοση µίας πολύ µεγάλης εικόνας µέσα από ένα κανάλι επικοινωνίας δεν πρέπει να πραγµατοποιηθεί όσο γρήγορο και να είναι το κανάλι, αν πρώτα δεν αναλύσουµε τα δεδοµένα της εικόνας και δεν συµπιέσουµε όσο το δυνατό περισσότερο την πληροφορία της. Από την άλλη, κατά την επεξεργασία και ανάλυση των φορολογικών στοιχείων των Ελλήνων πολιτών δεν πρέπει να δίνεται έµφαση µόνο στην ταχύτητα εξαγωγής των φόρων. Οι µέθοδοι επεξεργασίας των φορολογικών δεδοµένων θα πρέπει να είναι δοµηµένες έτσι ώστε να δίνεται έµφαση στα ίδια τα δεδοµένα και την οργάνωσή τους, µε σκοπό να µπορούν να δώσουν στατιστικά στοιχεία για τα οποία δεν έχουν προγραµµατιστεί από την αρχή. Οι διαδικασίες επεξεργασίας των δεδοµένων πρέπει να είναι δοµηµένες σύµφωνα µε την πληροφορία που αυτά µεταφέρουν και τη σηµασία τους για τον άνθρωπο (data oriented procedures). Πρέπει να σηµειώσουµε εδώ ότι οι έννοιες 'δεδοµένα' και 'πληροφορία' θα χρησιµοποιούνται ισοδύναµα παρότι διαφέρουν σηµαντικά(1). Γενικά η ίδια πληροφορία µπορεί να περιέχεται σε µεγαλύτερο ή µικρότερο όγκο δεδοµένων. Τα δεδοµένα που καλείται να επεξεργαστεί ο Η/Υ µπορούν να χωριστούν στα επόµενα τρία είδη.

32

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Αναλογικά ή συνεχή δεδοµένα. Πρόκειται για δεδοµένα που προκύπτουν από την µετατροπή φυσικών µεγεθών όπως θερµοκρασία, πίεση, ένταση φωτός σε ηλεκτρική τάση (σχήµα 2.2). Η τάση αυτή παίρνει συνεχείς τιµές πλάτους σε κάθε χρονική στιγµή όπως φαίνεται στο σχήµα 2.3α (αναλογικό σήµα). Για να µπορέσει ο Η/Υ να επεξεργαστεί ένα τέτοιο φυσικό µέγεθος αλλά και να το αποθηκεύσει πρέπει να το µετατρέψουµε σε αριθµούς. Έτσι λαµβάνουµε ισαπέχοντα στο χρόνο ή το χώρο δείγµατα της τάσης αυτής, όπως φαίνεται στο σχήµα 2.3.β και τα µετατρέπουµε στο δυαδικό σύστηµα µε το οποίο δουλεύει ο Η/Υ. Η διαδικασία αυτή ονοµάζεται µετατροπή αναλογικού σήµατος σε ψηφιακό (Analog to Digital Conversion - ADC) και είναι καθοριστική(2) για την περαιτέρω επεξεργασία του αρχικού αναλογικού µεγέθους από τον Η/Υ.

Σχήµα 2.2. Οι φωτογραφίες αποτελούν συνεχείς δισδιάστατες συναρτήσεις της αµαύρωσης του φιλµ που έχουν δηµιουργηθεί από µεταβολή της έντασης του φωτός επάνω του. Η φωτογραφία µε τη βοήθεια φωτοανιχνευτή θα µεταφερθεί στον Η/Υ σε κουκίδες (picture elements - pixels) που κάθε µία θα αντιστοιχεί ουσιαστικά σε έναν αριθµό ανάλογα µε την αµαύρωση του φιλµ.

∆ιακριτά δεδοµένα Πρόκειται για µετρήσιµα µεγέθη που προκύπτουν από στατιστικές ή άλλες µετρήσεις. Ένα τέτοιο παράδειγµα είναι όλες οι εξάδες του lotto που µετέχουν σε µία κλήρωση ή όλα τα φορολογικά δεδοµένα στο κέντρο επεξεργασίας του Υπουργείου Οικονοµικών (ΚΕΠΥΟ).

33

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

2 1 0 -1 -2

20

40

60 (α)

80

100

120

2 1 0 -1 -2

2

4

6

8

10

12

14

16

(β)

Σχήµα 2.3. Το συνεχές σήµα (α) που αντιστοιχεί στις µεταβολές φυσικού µεγέθους, για να περάσει στον υπολογιστή πρέπει να δηγµατοληπτηθεί σε ίσες αποστάσεις (β) και τα δείγµατα να µετατραπούν σε δυαδικούς αριθµούς. ∆εδοµένα που δηµιουργούνται από τον υπολογιστή Οι Η/Υ είναι σε θέση να παράγουν τυχαίους αριθµούς για προσοµοίωση συστηµάτων, αλλά και αριθµούς µε συγκεκριµένη σχέση µεταξύ τους, που περιγράφουν διαδικασίες ή φυσικά φαινόµενα. Είναι επίσης δυνατόν να δηµιουργήσουµε γραφήµατα ή συναρτήσεις. Μία τέτοια ηµιτονική κυµατοµορφή φαίνεται στο σχήµα 2.4 και έχει δηµιουργηθεί από το ακόλουθο πρόγραµµα της γλώσσας προγραµµατισµού FORTRAN. * program sinewave real phi,a,pi pi=3.14159 do phi=0, 4*pi, pi/5 a=sin(phi) print*,a enddo stop end

34

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Με την εκτέλεση του προγράµµατος λαµβάνουµε τις παρακάτω τιµές που χρονικά ισαπέχουν. .00000 .00000 -.00001 .00001

.58778 -.58778 .58778 -.58778

.95106 -.95106 .95105 -.95105

.95106 -.95106 .95106 -.95106

.58779 -.58779 .58779 -.58779

-.00001

Οι τιµές αυτές µε τη βοήθεια κατάλληλου λογισµικού µπορούν να αποδοθούν σε καρτεσιανό σύστηµα συντεταγµένων όπως φαίνεται στο σχήµα 2.4.

1 0.5 0 -0.5 -1 0

5

10

15

20

Σχήµα 2.4. Ηµιτονική κυµατοµορφή που δηµιουργείται από πρόγραµµα υπολογιστή Οι τρεις κατηγορίες δεδοµένων που περιγράψαµε αντιστοιχούν σε διαφορετικά µεγέθη που γενικά η ακρίβειά τους ποικίλει. Έτσι στον ψηφιακό Η/Υ έχουµε την δυνατότητα να χρησιµοποιούµε ακέραιους ή πραγµατικούς αριθµούς µε µικρή ή µεγάλη ακρίβεια και µέγεθος. Επίσης µπορούµε να χρησιµοποιούµε και πιο σύνθετα είδη αριθµών όπως µιγαδικούς, ή αριθµούς που εκφράζουν κάποιου είδους συντεταγµένες ή τύπους δεδοµένων που έχουν οριστεί από τον χρήστη. Στον ψηφιακό Η/Υ κάθε είδος δεδοµένων κωδικοποιείται τελικά στο δυαδικό σύστηµα (0 ή 1). Με τη βοήθεια του transistor ως διακοπτικού στοιχείου, ο ψηφιακός Η/Υ επεξεργάζεται τα δυαδικά δεδοµένα. Με το transistor δοµούνται οι βασικές πύλες λογικής που δίνονται στο σχήµα 2.5.α και εξετάζονται λεπτοµερώς στο επόµενο κεφάλαιο. Από τις πύλες φτιάχνονται όλα τα ψηφιακά κυκλώµατα. Σε αντίθεση, οι αναλογικοί ηλεκτρονικοί υπολογιστές, που δεν χρησιµοποιούνται πλέον, είχαν ως δοµικό στοιχείο τον τελεστικό ενισχυτή (σχήµα 2.5.β). Οι ψηφιακοί υπολογιστές και γενικά τα ψηφιακά κυκλώµατα πλεονεκτούν έναντι των αναλογικών στα ακόλουθα σηµεία: • Έχουν την δυνατότητα µνήµης. • Έχουν µεγάλη ακρίβεια στην αναπαράσταση των διαφόρων µεγεθών. 35

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

• Τροποποιείται εύκολα η διαδικασία που εκτελείται.

• ∆εν είναι ευαίσθητα στη θερµοκρασία και το χρόνο. Βασικές λογικές πύλες

Τελεστικός Ενισχυτής

AND

υ2

υο =Α(υ2-υ1)

υ1

OR NOT

α.

β.

Σχήµα 2.5. Οι βασικές πύλες λογικής αποτελούν δοµικά στοιχεία για τους ψηφιακούς υπολογιστές, ενώ ο τελεστικός ενισχυτής τη στοιχειώδη µονάδα του αναλογικού υπολογιστή.

2.2. Συστήµατα αρίθµησης Το δεκαδικό Ο άνθρωπος χρησιµοποιεί το δεκαδικό σύστηµα αρίθµησης γιατί αυτό είναι πιο κοντά στη φύση του. (Από µικρός µαθαίνει να χρησιµοποιεί τα δάκτυλα για την απαρίθµηση αντικειµένων). Το σύστηµα αυτό το απαρτίζουν συνολικά δέκα ψηφία, δηλαδή από το 0 µέχρι και το 9. Ένας οποιοσδήποτε θετικός πραγµατικός αριθµός x του δεκαδικού συστήµατος (DEC, decimal) συµβολίζεται ως:

αn-1 αn-2 .... α1α0 . α-1α-2 .... α-m

(1)

όπου αn-1, αn-2.α0, α-1, α-m ψηφία του δεκαδικού συστήµατος µε τιµές [0, 9]. Ο αριθµός αυτός αποτελείται συνολικά από n+m ψηφία του δεκαδικού συστήµατος. Είναι προφανές στην προκειµένη περίπτωση ότι η αξία του αριθµού x υπολογίζεται ως:

x = αn-1 !10n-1 + αn-2 !10n-2 +...+ α1 !101 + α0 !100 + α-1 !10-1 +...+ α-m !10-m (2α) ή

x=

n −1

∑ α 10 i

i =− m

36

i

(2β)

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Τυχαίας βάσης Άπειρα συστήµατα αρίθµησης µπορούν να χρησιµοποιηθούν. Ως βάση ενός συστήµατος αρίθµησης ορίζεται το πλήθος των διαφορετικών ψηφίων που χρησιµοποιούνται για τη δηµιουργία του. Εάν b είναι η βάση ενός τέτοιου συστήµατος, όπου b ≥ 2, τότε τα ψηφία αi , i = -m, ...., n-1 του συστήµατος αυτού θα παίρνουν τιµές από 0 έως b-1, δηλαδή b τιµές συνολικά. Ένας οποιοσδήποτε θετικός αριθµός του συστήµατος1 αυτού (x)b θα γράφεται ως:

αn-1 αn-2 .... α1α0 , α-1α-2 .... α-m

(3)

και η αντίστοιχη αξία του (στο δεκαδικό σύστηµα το οποίο και καταλαβαίνουµε) υπολογίζεται από τη σχέση:

(x)b = αn-1 !bn-1 + αn-2 !bn-2 +...+ α1 !b1 + α0 !b0 + α-1 !b-1 +...+ α-m !b-m ( x )b =

ή

n −1

∑α b

i

i

(4α) (4β).

i =− m

Το δυαδικό Το απλούστερο σύστηµα αρίθµησης που µπορεί να υπάρξει είναι το δυαδικό (binary) που έχει βάση b=2 και µε ψηφία το 0 και το 1. Τα ψηφία αυτά ονοµάζονται δυαδικά (binary digits) ή bits. Ένα bit αντιπροσωπεύει την ελάχιστη πληροφορία που µπορεί να µεταφέρει ένας αριθµός. Ένας δυαδικός αριθµός των 8 bits ονοµάζεται byte (π.χ. 0110 1101), ενώ ένας των 16 bits καλείται word. Το πρώτο από αριστερά δυαδικό ψηφίο ενός αριθµού είναι το πιο σηµαντικό (Most Significant Bit - MSB) γιατί σύµφωνα µε την (4) έχει την µεγαλύτερη αξία. Αντίθετα το τελευταίο δεξιά ψηφίο καλείται LSB (Least Significant Bit). Η όλη λειτουργία των ψηφιακών ηλεκτρονικών υπολογιστών στηρίζεται στο δυαδικό σύστηµα αρίθµησης. Ο λόγος είναι απλός. Είναι πολύ πιο εύκολο για ένα ηλεκτρονικό κύκλωµα να αναγνωρίσει δύο διαφορετικές καταστάσεις: • διακόπτης ανοικτός ή κλειστός • υλικό µαγνητισµένο ή µη • ύπαρξη φωτός ή µη • πρόταση αληθής ή ψευδής 1

Για λόγους σαφήνειας οι αριθµοί συµβολίζονται µέσα στις παρενθέσεις, ενώ έξω από αυτές γράφεται η βάση του συστήµατος αρίθµησης, π.χ. ο αριθµός x του δυαδικού συστήµατος συµβολίζεται

37

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

• αποτέλεσµα σωστό ή λάθος. Για τον λόγο αυτό το δυαδικό σύστηµα µπορεί να θεωρηθεί ως σύστηµα αρίθµησης προσαρµοσµένο περισσότερο στη φύση σε σχέση µε το δεκαδικό που το έχει συνηθίσει πιο πολύ ο άνθρωπος. Ένας οποιοσδήποτε θετικός αριθµός του δυαδικού συστήµατος θα έχει την µορφή της σχέσεως (3), όπου αi ∈ [0,1] και η αντίστοιχη αξία του θα υπολογίζεται από τις σχέσεις (4). Παράδειγµα: Ο αριθµός (101.01)2 του δυαδικού συστήµατος αντιστοιχεί στον 1!22 + 0!21 + 1!20 + 0!2-1 + 1!2-2 = 4 + 0 + 1 + 0 + 0.25 = 5.25 του δεκαδικού συστήµατος. Αξίζει να σηµειωθεί ότι το πλήθος των δυαδικών ψηφίων ενός αριθµού µας δείχνει και

τον

µέγιστο

αριθµό

του

δεκαδικού

συστήµατος

που

µπορούµε

να

αντιπροσωπεύσουµε. Συγκεκριµένα, µε 4 δυαδικά ψηφία µπορούµε να έχουµε 16 δυνατούς συνδυασµούς και έτσι να καλύψουµε τους πρώτους 16 αριθµούς στο δυαδικό σύστηµα, δηλαδή από το 0 µέχρι και το 15.

Το δεκαεξαδικό Ένα άλλο σύστηµα αρίθµησης το οποίο χρησιµοποιείται εκτεταµένα στους Η/Υ είναι το δεκαεξαδικό (HEX, hexadecimal). Υπάρχει η δυνατότητα άµεσης µετατροπής (στην πραγµατικότητα πρόκειται για άµεση απεικόνιση, όπως θα δούµε στη συνέχεια) από το σύστηµα αυτό στο δυαδικό και αντίστροφα. Στο δεκαεξαδικό σύστηµα αρίθµησης η βάση είναι το 16 (b=16) και τα ψηφία αi , i = -m, ...., n-1 παίρνουν τιµές από 0 µέχρι και 15. Επειδή όµως δεν είναι δυνατόν ψηφία (για λόγους σαφήνειας) του δεκαεξαδικού συστήµατος να αποτελούνται από δύο αριθµούς (π.χ. πώς µπορούµε να ξεχωρίσουµε αν ο αριθµός 15 του δεκαεξαδικού αντιστοιχεί σε ψηφία αυτού ή σε δύο ξεχωριστά ψηφία, το 1 και το 5;), τα ψηφία από το 10 µέχρι το 15 συµβολίζονται µε τα γράµµατα του λατινικού αλφαβήτου Α µέχρι F, όπως δείχνεται στον πίνακα 2.1. Με δύο δεκαεξαδικά ψηφία, µπορούµε να αναπαραστήσουµε όλους τους δεκαδικούς αριθµούς από το 0 ως το 255 (0 ως FF=15×161+15×160=255). ∆ηλαδή όλους τους αριθµούς που µπορούν να παρασταθούν στο δυαδικό σύστηµα µε 8 δυαδικά ψηφία ή 1 byte. Αυτός είναι εξάλλου και ο κύριος λόγος της χρήσης του δεκαεξαδικού συστήµατος στην αναπαράσταση της δυαδικής πληροφορίας στους ψηφιακούς ηλεκτρονικούς υπολογιστές.

ως (x)2.

38

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

ΠΙΝΑΚΑΣ 2.1: Αντιστοιχία δυαδικού, δεκαδικού και δεκαεξαδικού. ∆υαδικό (BIN)

∆εκαδικό (DEC)

∆εκαεξαδικό (HEX)

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 1 2 3 4 5 6 7 8 9 A Β C D E F

2.3. Μετατροπές από σύστηµα σε σύστηµα Στην παράγραφο αυτή θα ασχοληθούµε µε την µετατροπή ενός θετικού αριθµού από το ένα σύστηµα αρίθµησης στο άλλο. Επειδή το δεκαδικό σύστηµα είναι αυτό που αντιλαµβανόµαστε καλύτερα, ενώ το δυαδικό είναι το σύστηµα που χρησιµοποιείται στα ψηφιακά κυκλώµατα, θα εξετάσουµε πρώτα αυτά τα δύο.

Μετατροπές µεταξύ δυαδικού και δεκαδικού Μετατροπή δυαδικού σε δεκαδικό Αυτή είναι η πλέον απλή περίπτωση και η µετατροπή γίνεται µε χρήση της σχέσης (4), όπως παρουσιάστηκε και στο παράδειγµα της προηγούµενης παραγράφου. Μετατροπή δεκαδικού σε δυαδικό

39

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

α. Ακέραιοι αριθµοί

Για την µετατροπή ενός θετικού ακεραίου αριθµού του δεκαδικού συστήµατος στο δυαδικό, διαιρούµε διαδοχικά τον αριθµό καθώς και όλα τα πηλίκα που προκύπτουν διά 2, µέχρις ότου το πηλίκο να µηδενισθεί. Ο αντίστοιχος δυαδικός είναι εκείνος που προκύπτει αν γράψουµε τα υπόλοιπα που προέκυψαν σε αντίστροφη σειρά. Παράδειγµα: (25)10 = (?????)2. 25 2 1 12 2

LSB

0 6

2

0

3

2

1

1

2

1

0

MSB

Άρα (25)10 = (11001)2 .

β. Μη ακέραιοι µικρότεροι της µονάδας

Για την µετατροπή ενός θετικού µη ακεραίου µικρότερου της µονάδας αριθµού του δεκαδικού συστήµατος στο δυαδικό σύστηµα, πολλαπλασιάζουµε διαδοχικά επί 2 τον αριθµό καθώς και όλα τα γινόµενα που προκύπτουν (αγνοώντας τα ακέραια µέρη των γινοµένων) µέχρις ότου το αποτέλεσµα γίνει µηδέν ή πετύχουµε την επιθυµητή ακρίβεια. Ο αντίστοιχος δυαδικός προκύπτει από τα ακέραια µέρη των γινοµένων γραµµένων µε την σειρά που εµφανίζονται. Παράδειγµα: (0.625)10 = (???)2. 0.625

0.25

0.5

x

2

x 2

1.250

0.50

1.0

1

0

1

x 2

MSB Συνεπώς (0.625)10 = (.101)2.

40

LSB

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Παράδειγµα: (0.14)10 = (????)2. 0.140

.28

0.56

0.12

0.24

0.48

0.96

0.92

x 2x 2

x 2

x 2

x 2

x 2

x 2

x 2

........

0.28

0.56

1.12

0.24

0.48

0.96

1.92

1.84

0

0

1

0

0

1

1

0

Στην περίπτωση αυτή παρατηρούµε ότι η διαδικασία δεν σταµατά από µόνη της αλλά µπορεί να συνεχισθεί µέχρις ότου επιτύχουµε την επιθυµητή προσέγγιση. Έτσι µε ακρίβεια οκτώ δυαδικών ψηφίων ο αριθµός γράφεται (0.14)10≅ (.00100011)2≅(0.137)10. γ. Μη ακέραιοι µεγαλύτεροι της µονάδας

Στην περίπτωση αυτή µετατρέπουµε χωριστά το ακέραιο και το µη ακέραιο µέρος του αριθµού σύµφωνα µε αυτά που αναφέρθηκαν στις (α), (β). Παράδειγµα: (3.14)10 = (??????)2. • Μετατροπή του ακέραιου µέρους 3 2 1 1

2

1

0

(3)10 = (11)2.

• Μετατροπή του µη ακέραιου µέρους 0.14 x 2 0.28

0

0.28

.......

x 2 0.56

0

(0.14)10 = (.0010)2. Άρα, τελικά ο αριθµός του δεκαδικού συστήµατος (3.14)10 γράφεται στο δυαδικό ως (11.0010)2.

Σηµείωση

41

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Θα πρέπει να τονισθεί στο σηµείο αυτό ότι το σηµείο της υποδιαστολής δεν υπάρχει στο δυαδικό σύστηµα. Απλώς προσδιορίζεται νοητά η θέση του και λαµβάνεται υπόψη στις οποιεσδήποτε πράξεις εκτελεσθούν. Έτσι, όταν πρόκειται για ακέραιο δυαδικό αριθµό, θεωρείται πως η υποδιαστολή βρίσκεται αµέσως µετά (δεξιά από) τα bits του αριθµού (σχ. 2.6.α). Αν πρόκειται για µη ακέραιο µικρότερο της µονάδας αριθµό χωρίς πρόσηµο, τότε η θέση της υποδιαστολής είναι πριν (αριστερά από) τα bits του αριθµού (σχ. 2.6.β). Αν ο αριθµός έχει πρόσηµο (όπως θα δούµε στη συνέχεια), τότε το σηµείο της υποδιαστολής θα βρίσκεται νοητά, αµέσως µετά το bit του προσήµου (σχ. 2.6.γ). Τώρα ίσως αναρωτηθείτε τι γίνεται στην περίπτωση που ο αριθµός αποτελείται από ακέραιο και µη ακέραιο µέρος. Θεωρητικά αντιπροσωπεύεται στο παράδειγµα της περίπτωσης (γ) προηγουµένως και έχει όπως φαίνεται στο σχήµα 2.6.δ. Στην πράξη όµως, θα δούµε πως οι αριθµοί που χρησιµοποιούνται είναι είτε ακέραιοι, είτε µη ακέραιοι µικρότεροι της µονάδας. Ακέραιος

(α)

.

Μη ακέραιος

.

.

Μη ακέραιος µε πρόσηµο

Ακέραιο

(β)

(γ)

.

Μη ακέραιο

(δ)

Σχήµα 2.6. Η θέση της υποδιαστολής στα διάφορα είδη των δυαδικών αριθµών.

Μετατροπή µεταξύ δυαδικού και δεκαεξαδικού Η µετατροπή από το δυαδικό σύστηµα στο δεκαεξαδικό είναι άµεση και δεν απαιτεί οποιεσδήποτε πράξεις. Άλλωστε αυτός είναι ο λόγος για τον οποίο εισήχθη η χρήση του δεκαεξαδικού και δεν παραµείναµε στα δύο πρώτα συστήµατα, δηλαδή στο δεκαδικό που είναι "κοντά" στον άνθρωπο και στο δυαδικό που είναι "κοντά" στη µηχανή (υπολογιστή). Μετατροπή δυαδικού σε δεκαεξαδικό Για την µετατροπή ενός αριθµού από το δυαδικό στο δεκαεξαδικό, χωρίζουµε τον δυαδικό από τα δεξιά προς τα αριστερά σε οµάδες των τεσσάρων bits, και σε κάθε µία από αυτές αντιστοιχούµε το δεκαεξαδικό ψηφίο σύµφωνα µε τον πίνακα 2.1.

42

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Παράδειγµα: (1011010101)2 =(???)16. 10 1101 0101 2

D

5

Άρα (1011010101)2 = (2D5)16. Μετατροπή δεκαεξαδικού σε δυαδικό Η περίπτωση αυτή είναι η αντίστροφη της προηγούµενης, δηλαδή σε κάθε δεκαεξαδικό ψηφίο αντιστοιχούµε τα 4 δυαδικά ψηφία σύµφωνα µε τον πίνακα 2.1. Παράδειγµα: (2D5)16 = (?)2. 2 6 474 8 0010

D 6 474 8 1101

5 6 474 8 0101

Άρα (2D5)16 = (001011010101)2. Παράδειγµα: (37)16 = (?)2. 3 6 474 8 0011

7 6 474 8 0111

Άρα (37)16 = (00110111)2.

Μετατροπές µεταξύ δεκαδικού και δεκαεξαδικού Η περίπτωση αυτή παρουσιάζεται σπάνια κατά την ενασχόλησή µας µε τους υπολογιστές. Αναφέρεται όµως εδώ, για να δειχτεί η οµοιότητα των διαδικασιών µετατροπής µεταξύ των διαφόρων συστηµάτων αρίθµησης. Μετατροπή δεκαεξαδικού σε δεκαδικό Η µετατροπή δεκαεξαδικού σε δεκαδικό γίνεται µε την βοήθεια της σχέσης (4). Παράδειγµα: (2D5)16 = (?)10. (2D5)16 = 2!162 + 13!161 + 5!160 = 512 + 208 + 5 = (725)10. Μετατροπή δεκαδικού σε δεκαεξαδικό Η διαδικασία για την µετατροπή ενός DEC σε HEX, είναι αντίστοιχη εκείνης της µετατροπής δεκαδικού σε δυαδικό, και γίνεται µε διαδοχικές διαιρέσεις των πηλίκων διά 16.

Παράδειγµα: (725)10 = (?)16. 43

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

725 16 5 45 16 13 2 16 LSΒ

2 0

ΜSΒ

Άρα (725)10 = (2D5)16.

2.4. Πράξεις στο δυαδικό Οι πράξεις στο δυαδικό σύστηµα αρίθµησης γίνονται µε τον ίδιο τρόπο όπως και στο δεκαδικό σύστηµα. Η στοιχειώδης πρόσθεση µεταξύ δυαδικών ψηφίων έχει ως εξής: 0+0=0 1+0=1 0+1=1 1 + 1 = 0 και 1 κρατούµενο για ανώτερη τάξη. Οι πράξεις αυτές υλοποιούνται από το κύκλωµα του ηµιαθροιστή (σχήµα 2.7) που θα δούµε αναλυτικά στο επόµενο κεφάλαιο. Κύκλωµα Ηµιαθροιστή Α Β

S =άθροισµα

C = κρατούµενο

Σχήµα 2.7. Το κύκλωµα του ηµιαθροιστή που υλοποιεί την απλή πρόσθεση δύο δυαδικών ψηφίων, και που αποτελείται από λογικές πύλες. Ας δούµε µερικά παραδείγµατα πράξεων στο δυαδικό σύστηµα αρίθµησης, πριν προχωρήσουµε σε πιο αναλυτική µελέτη ορισµένων από αυτές.

Πρόσθεση:

1 1 1

(21)10

( 10101 )2

+ ( 7)10

+ ( 111)2

(28)10

(11100)2

κρατούµενα

Παρατηρούµε ότι τα κρατούµενα που δηµιουργούνται κατά την πρόσθεση δύο bits προστίθενται στα αµέσως µεγαλύτερης σηµαντικότητας bits. ∆ηλαδή λάβαµε υπόψη

44

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

µας ότι 1 + 1 = (2)10 ή 0 και 1 το κρατούµενο στο δυαδικό και ότι 1 + 1 + 1 = (3)10 ή 1 και 1 το κρατούµενο στο δυαδικό. 1 1 1

(21)10

( 10101 )2

- ( 7)10

- (00111)2

(14)10

(01110)2

Αφαίρεση:

∆ανεικά κρατούµενα

Όπως ίσως διαπιστώσατε στη διαδικασία αφαίρεσης χρειάστηκε να δανειστούµε κάποιες µονάδες, τις οποίες και "επιστρέψαµε" (προσθέτοντας αυτές στον αφαιρετέο) κατά τον υπολογισµό του αµέσως µεγαλύτερης σηµαντικότητας bit. Έτσι για τον υπολογισµό (0)2 - (1)2 χρειάστηκε να δανειστούµε 1 και έτσι ο µειωτέος να γίνει (10)2 (1)2 = (2)10 - (1)10 = 1. Τη µονάδα που δανειστήκαµε την προσθέτουµε στον αµέσως µεγαλύτερης σηµαντικότητας αφαιρετέο, δηλ. (1)10 + (1)10 = (2)10 και το αποτέλεσµα το αφαιρούµε από το 1. Όµως επειδή και πάλι η πράξη αυτή δεν µπορεί να γίνει, δανειζόµαστε µία µονάδα οπότε ο µειωτέος γίνεται (11)2 = (3)10, και συνεπώς (3)10 (2)10 = 1. Παρατηρούµε πως η διαδικασία της αφαίρεσης στο δυαδικό σύστηµα, που µόλις αναπτύχθηκε, είναι πολύ επίπονη και η πιθανότητα λάθους µεγάλη. Τα πράγµατα περιπλέκονται ακόµη περισσότερο αν το αποτέλεσµα της αφαίρεσης είναι αρνητικός αριθµός. Η όλη αυτή διαδικασία απλουστεύεται σηµαντικά µε την εισαγωγή των προσηµασµένων αριθµών, όπως θα δούµε παρακάτω, οπότε αντί για αφαίρεση κάνουµε πρόσθεση των αντιθέτων.

(6)10

Πολλαπλασιασµός:

x (5)10 (30)10

(110)2 x (101)2 110 000 110 (11110)2

Παρατηρούµε ότι ο πολλαπλασιασµός δύο θετικών δυαδικών αριθµών γίνεται µε διαδοχικές ολισθήσεις αριστερά και προσθέσεις, όπως και στην περίπτωση του

45

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

δεκαδικού συστήµατος. Η διαίρεση δύο δυαδικών αριθµών γίνεται µε διαδοχικές ολισθήσεις δεξιά και αφαιρέσεις. Σηµείωση: Σηµειώνεται πως ολίσθηση ενός αριθµού αριστερά ή δεξιά κατά µία θέση συνεπάγεται πολλαπλασιασµό ή διαίρεση αυτού επί 2 ή διά 2 αντίστοιχα.

2.5. ∆υαδικοί αριθµοί µε πρόσηµο Το αποτέλεσµα της αφαίρεσης δύο θετικών δυαδικών αριθµών θα µπορούσε να ήταν αρνητικό αν ο µειωτέος ήταν µικρότερος από τον αφαιρετέο. Συνεπώς υπάρχει η ανάγκη ορισµού θετικών και αρνητικών δυαδικών αριθµών. Για να το πετύχουµε αυτό κάνουµε την εξής σύµβαση: Κάθε θετικός αριθµός θα έχει ως MSB το 0 και κάθε αρνητικός αριθµός θα έχει ως MSB το 1. Υπάρχουν τρεις διαφορετικοί τρόποι για τον συµβολισµό (παράσταση) των προσηµασµένων αριθµών, οι εξής: (i) Προσηµασµένου µέτρου (signed magnitude), (ii) Συµπληρώµατος ως προς 1 (1's complement), (iii) Συµπληρώµατος ως προς 2 (2's complement). Η µορφή συµπληρώµατος ως προς 2 είναι εκείνη που χρησιµοποιείται στους υπολογιστές. Θα αναφέρουµε όµως και τις τρεις παραστάσεις για να γίνουν κατανοητά τα πλεονεκτήµατα καθεµιάς.

Προσηµασµένου µέτρου Σύµφωνα µε αυτή την µορφή συµβολισµού, το πρώτο bit από αριστερά είναι το bit του προσήµου (0 για +, 1 για -) και τα υπόλοιπα bits υποδηλώνουν το µέγεθος του αριθµού. Ο συµβολισµός αυτός είναι ο πλέον βολικός για εµάς, αλλά δύσχρηστος για µια µηχανή, µια που πρέπει να λαµβάνουµε πρώτα το πρόσηµο υπόψη µας πριν κάνουµε µια πράξη. Σύµφωνα µε αυτή την µορφή παράστασης ο αριθµός (+3)10 θα γράφεται στο δυαδικό ως (011)2 µε ακρίβεια τριών bits ή (0011)2 µε ακρίβεια τεσσάρων bits, ενώ ο αριθµός (-3)10 θα γράφεται ως (1011)2 µε ακρίβεια τεσσάρων bits. (Βλ. πίνακα 2.2).

46

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Πίνακας 2.2 Παράδειγµα προσηµασµένων αριθµών των 4-bits. Παράσταση των ακεραίων αριθµών -8 έως +7 στο δυαδικό µε ακρίβεια 4 δυαδικών ψηφίων Signed Magnitude

1's Complement

2's Complement

+7

0111

0111

0111

+6

0110

0110

0110

+5

0101

0101

0101

+4

0100

0100

0100

+3

0011

0011

0011

+2

0010

0010

0010

+1

0001

0001

0001

0

 0000  1000 

 0000  1111 

0000

-1

1001

1110

1111

-2

1010

1101

1110

-3

1011

1100

1101

-4

1100

1011

1100

-5

1101

1010

1011

-6

1110

1001

1010

-7 -8

1111 -

1000 -

1001 1000

Συµπλήρωµα ως προς 1 Οι θετικοί αριθµοί έχουν την µορφή προσηµασµένου µέτρου. Οι αρνητικοί προκύπτουν από τους αντίστοιχους θετικούς µε αντιστροφή των δυαδικών ψηφίων από 0 σε 1 και από 1 σε 0. Παράδειγµα ο (+3)10 γράφεται ως (0011)2, ενώ ο (-3)10 ως (1100)2 (βλ. Πίνακα 2.2). Η πρόσθεση στο σύστηµα αυτό γίνεται κανονικά όπως αναφέρθηκε στην προηγούµενη παράγραφο. Η αφαίρεση γίνεται µε πρόσθεση του αντιθέτου (του συµπληρώµατος ως προς 1) του αφαιρετέου. Αν προκύψει κρατούµενο το προσθέτουµε

47

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

στο αποτέλεσµα που µόλις βρήκαµε. Το κρατούµενο αυτό ονοµάζεται τελικό (end around carry). Παράδειγµα: (7)10 - (5)10 = (7)10 + (-5)10 = (+2)10 (0111)2 - (0101)2 = (0111)2 + (1010)2 = (0010)2 0111 + 1010 Τελικό κρατούµενο

1 0001 +

1 0010

Παράδειγµα: (5)10 - (7)10 = (5)10 + (-7)10 = (-2)10 (0101)2 - (0111)2 = (0101)2 + (1000)2 = (1101)2 0101 + 1000 1101 Εδώ δεν υπάρχει τελικό κρατούµενο. Το αποτέλεσµα είναι σωστό και συµβολίζει τον αριθµό (-2)10 σε συµπλήρωµα ως προς 1. Αυτό µπορεί να επιβεβαιωθεί είτε µέσω του πίνακα 2.2, είτε αντιστρέφοντας τα ψηφία του αποτελέσµατος, οπότε προκύπτει το (0010)2, δηλαδή το (+2)10.

Συµπλήρωµα ως προς 2 Οι θετικοί αριθµοί έχουν την γνωστή πλέον µορφή προσηµασµένου µέτρου. Οι αρνητικοί προκύπτουν από τους αντίστοιχους σε συµπλήρωµα ως προς 1 προσθέτοντας µία µονάδα. Η πρόσθεση στο σύστηµα αυτό γίνεται κατά τα γνωστά. Η αφαίρεση γίνεται µε πρόσθεση του αντιθέτου (του συµπληρώµατος ως προς 2) του αφαιρετέου. Αν από αυτή την πρόσθεση προκύψει κρατούµενο, αυτό αγνοείται!

48

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Παράδειγµα: (7)10 - (5)10 = (7)10 + (-5)10 = (+2)10 =

(+5)10

(0101)2

ως 1  → (-5)10 Συµπ.

(1010)2 +

ως 2 (-5)10 Συµπ.  →

1 (1011)2

Άρα η πρόσθεση του (-5)10 στο (+7)10 δίνει: 0111 + 1011 αγνοείται

10010

Παράδειγµα: (5)10 - (7)10 = (5)10 + (-7)10 = (-2)10 (+7)10

=

(0111)2

ως 1  → (-7)10 Συµπ.

(1000)2 +

ως 2  → (-7)10 Συµπ.

1 (1001)2

Και τελικά προσθέτουµε το (-7)10 στο (+5)10 και έχουµε το τελικό αποτέλεσµα: 0101 + 1001 1110 Προσοχή:

ως 2 Συµπ.  →

(-2)10

Για να κάνετε σωστά τις πράξεις να φροντίσετε οι αριθµοί σας να έχουν το ίδιο πλήθος δυαδικών ψηφίων λαµβάνοντας πάντοτε υπόψη και το πρόσηµο!

Παράδειγµα: Να υπολογισθεί η διαφορά Α-Β όπου Α = (37)10, Β = (4)10. πρόσηµο

Βήµα 1ο:

Α = (+37)10 = (0100101)2 Β = ( 4)10 =

(100)2

Βήµα 2ο:

Β = (+4)10 = (0000100)2

Βήµα 3ο:

-Β = (-4)10 = (1111100)2 σε συµπλήρωµα ως προς 2

Βήµα 4ο:

Α - Β = Α + (-Β) = 0100101 + 1111100 αγνοείται

10100001 = (33)10.

49

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Σηµείωση 1η: Ένας δυαδικός αριθµός (Χ)2 = αn-1 αn-2 .... α1α0.α-1 ... α-m, όπου αi, i

= -m, ... , n-1 (µε αn-1 το bit προσήµου) σε µορφή συµπληρώµατος ως προς 2, µετατρέπεται σε δεκαδικό µε βάση τη σχέση:

(Χ)10 = -αn-1!2n-1 +

n−2

∑α 2

i

i

(5)

i =− m

Σηµείωση 2η: Ένας εποπτικός τρόπος για την εύρεση του συµπληρώµατος ως προς 2 ενός δυαδικού αριθµού είναι ο ακόλουθος: αρχίζοντας από δεξιά (δηλ. από το LSB του αριθµού) ξαναγράφουµε κάθε bit όπως έχει, µέχρι και της πρώτης µονάδας που θα συναντήσουµε, ενώ τα υπόλοιπα bits τα αντιστρέφουµε. Παραδείγµατα: α) Ο αριθµός (-2)10 προκύπτει από τον (+2)10 ως εξής: 00 Αντιστροφή

11

10 Αντιγραφή

10

β) Ο αριθµός (-76)10 προκύπτει από τον (+76)10 ως εξής: 01001 Αντιστροφή

10110

100 Αντιγραφή

100

Σηµείωση 3η: Τα πλεονεκτήµατα του συµπληρώµατος ως προς 2 έναντι των άλλων δύο µορφών αναπαράστασης των αριθµών είναι τα εξής (βλ. πίνακα 2.2): α) υπάρχει µόνο ένας τρόπος παράστασης του µηδενός, β) υπάρχει παράσταση για το -2n, όπου n το πλήθος των δεκαδικών ψηφίων, γ) η αφαίρεση γίνεται µε απλή πρόσθεση των αριθµών αδιαφορώντας για το τελικό κρατούµενο.

2.6. Συµπληρώµατα αριθµών: Μιά γενικότερη µατιά Συµπληρώµατα (complements) µπορούν να υπάρξουν όχι µόνο για αριθµούς του δυαδικού συστήµατος αλλά και για οποιοδήποτε άλλο σύστηµα αρίθµησης µε βάση b. Σε κάθε περίπτωση υπάρχουν δύο ειδών συµπληρώµατα, δηλαδή ως προς b-1 και ως προς b. Το συµπλήρωµα ως προς b-1 ενός αριθµού Χ µε Ν ψηφία ισούται µε (bN-1)-X,

50

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

ενώ το συµπλήρωµα ως προς b του ίδιου αριθµού ισούται µε bΝ-X. ∆ηλαδή, το συµπλήρωµα ως προς b προκύπτει από το συµπλήρωµα ως προς b-1 µε πρόσθεση µιας µονάδας. Ας εξετάσουµε την περίπτωση των δεκαδικών αριθµών (b=10) και ας δούµε πώς θα µπορούσαµε να κάνουµε αφαίρεση, προσθέτοντας το συµπλήρωµα ως προς 9 του αφαιρετέου. Ας υπολογίσουµε ως παράδειγµα πόσα χρόνια πέρασαν από την στιγµή που πρωτοπαρουσιάστηκε ο πρώτος προσωπικός Η/Υ (Personal Computer, PC) το 1981. Με άλλα λόγια, ας υπολογίσουµε την διαφορά 1998-1981. Το συµπλήρωµα ως προς 9 του 1981 (αφαιρετέου) προκύπτει µε αφαίρεση αυτού από τον τετραψήφιο αριθµό 9999 = 104-1 και ισούται µε 8018. Άρα 1998 - 1981 = 1998 + 8018. 1998 + 8018 Τελικό κρατούµενο

1 0016 +

1 0017

Παρατηρούµε ότι το τελικό κρατούµενο που προέκυψε προστέθηκε στο άθροισµα ώστε να πάρουµε το σωστό αποτέλεσµα που είναι 17 χρόνια. Γίνεται φανερό πως, όπως και στην αντίστοιχη περίπτωση του δυαδικού συστήµατος, αν χρησιµοποιούσαµε το συµπλήρωµα ως προς 10 το αποτέλεσµα θα ήταν σωστό και δεν θα χρειαζόταν η πρόσθεση του τελικού κρατουµένου.

2.7. Παραστάσεις αριθµών στον υπολογιστή Οι αριθµοί παριστάνονται (αντιπροσωπεύονται) στους υπολογιστές είτε ως αριθµοί σταθερής υποδιαστολής (fixed-point), είτε ως αριθµοί κινητής υποδιαστολής (floatingpoint). Όλοι οι αριθµοί όπως τους γνωρίσαµε στις προηγούµενες παραγράφους είναι σε παράσταση σταθερής υποδιαστολής. Όταν η υποδιαστολή βρίσκεται στο δεξιό άκρο του αριθµού τότε έχουµε ακέραιους αριθµούς.

Ακέραιοι αριθµοί Οι ακέραιοι αριθµοί διακρίνονται ανάλογα µε το πλήθος των bytes σε περιορισµένης ακρίβειας (1 byte ή 8 bits και δυναµική περιοχή από -128 ως 127), σε απλής ακρίβειας (2 bytes ή 16 bits και δυναµική περιοχή από -32768 ως 32767) και σε διπλής ακρίβειας (4 bytes ή 32 bits και δυναµική περιοχή από -2147438648 ως 2147438647). Το

51

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

πλεονέκτηµα αυτού του τύπου αριθµών είναι η ταχύτητα εκτέλεσης των πράξεων, ενώ το µειονέκτηµά του έναντι των αριθµών κινητής υποδιαστολής είναι η περιορισµένη δυναµική περιοχή (περιορισµένο πλήθος αριθµών για προκαθορισµένο µήκος λέξης) και τα συνεπαγόµενα προβλήµατα υπερχείλισης (overflow). Σηµείωση: Όταν το αποτέλεσµα µιας πράξης είναι µεγαλύτερο ή µικρότερο από την µέγιστη ή ελάχιστη τιµή που µπορεί να αναπαρασταθεί σε συγκεκριµένο µήκος λέξης τότε έχουµε το φαινόµενο της υπερχείλισης (overflow) ή υποχείλισης (underflow). Παράδειγµα υπερχείλισης:

01001001 + 01101100 10110101

Παρατηρούµε πως η πρόσθεση δύο θετικών αριθµών έδωσε ως αποτέλεσµα αρνητικό αριθµό. Παράδειγµα υποχείλισης: α) ∆ιαίρεση µικρού αριθµού: 00000001 : 2 = 00000000. β) Πρόσθεση µικρού αριθµού σε πολύ µεγάλο: 0.2!10-30 + 0.7!1031 = 0.7!1031. Πρέπει να τονίσουµε ότι έχει µεγάλη σηµασία ο τύπος των αριθµών που θα επιλέξουµε για τα µεγέθη µας στον Η/Υ. Αυτό κατ΄ αρχή θα εξαρτηθεί από τα ίδια τα µεγέθη και τη δυναµική τους περιοχή (ελάχιστη και µέγιστη τιµή). Όµως, η απαιτούµενη µνήµη (πλήθος bytes) και η ταχύτητα εκτέλεσης των πράξεων επίσης θα επηρεάσουν στην επιλογή τους.

Αριθµοί Σταθερής Υποδιαστολής (Fixed-point Numbers) Σε µορφή σταθερής υποδιαστολής αντιπροσωπεύονται συνήθως οι ακέραιοι αριθµοί (βλ. Σχ. 2.6.α). Ένας ακέραιος αριθµός µε n bits (συµπεριλαµβανοµένου του bit του προσήµου) θα βρίσκεται στην περιοχή -2n-1 µέχρι +2n-1 -1. Για παράδειγµα, από τον Πίνακα 2.2 παρατηρούµε πως για n=4 οι αριθµοί κυµαίνονται στην περιοχή [-8,+7]. Θυµίζουµε πως για ακέραιους αριθµούς σταθερής υποδιαστολής η θέση της υποδιαστολής βρίσκεται νοητά αµέσως µετά (δεξιά) από το LSB του αριθµού. Αν ο αριθµός είναι µη-ακέραιος µικρότερος της µονάδας, τότε η υποδιαστολή τοποθετείται νοητά µεταξύ του πρώτου bit (δηλαδή του bit προσήµου) και του δεύτερου bit (βλ. Σχ.

52

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

2.6.γ.). Ένας τέτοιος αριθµός, πλήθους n δυαδικών ψηφίων, θα βρίσκεται στην περιοχή [-1, 1-2-n]. Μπορούµε να παρατηρήσουµε πως ο µικρότερος αριθµός σε συµπλήρωµα 1000 0 , ενώ ο µεγαλύτερος δυαδικός αριθµός είναι ο 1 0111 1 . ως προς 2 είναι ο 1 42.... 43 42.... 4 3 n bits

n bits

Οι αντίστοιχες τιµές τους στο δεκαδικό υπολογίζονται µε βάση τη σχέση (5).

Αριθµοί Κινητής Υποδιαστολής (Floating-Point Numbers) Ένας δυαδικός αριθµός Χ σε µορφή κινητής υποδιαστολής παριστάνεται ως γινόµενο δύο προσηµασµένων αριθµών, του µεγέθους (mantissa) Μ και του εκθέτη (exponent) Ε: Χ = Μ!2Ε

(6)

Ο εκθέτης καθορίζει το εύρος της περιοχής των αριθµών που µπορούν να αντιπροσωπευθούν, ενώ το µέγεθος την ακρίβεια (accuracy) των αριθµών. Για παράδειγµα, εάν ο εκθέτης και το µέγεθος παριστάνονται αντίστοιχα µε 8 και 16 bits, η περιοχή των αριθµών κινητής υποδιαστολής που µπορούν να αντιπροσωπευθούν κυµαίνεται µεταξύ 0.5!2-128 έως 1-(2-15)!2128. Οι πραγµατικοί αριθµοί παριστάνονται ως αριθµοί κινητής υποδιαστολής. Ένας πραγµατικός αριθµός απλής ακρίβειας παριστάνεται µε 4 bytes όπως στο σχήµα 2.8, και η δυναµική περιοχή κυµαίνεται µεταξύ 3.4!10-38 έως 3.4!1038. Στον αριθµό αυτό 8 bits χρησιµοποιούνται για τον εκθέτη και 24 για το µέγεθος. Πραγµατικός αριθµός απλής ακρίβειας (4 bytes)

Ε=Εκθέτης 7 bits

Μ = Mantissa ή Μέγεθος 23 bits

Πρόσηµο Σχήµα 2.8. Παράσταση πραγµατικού αριθµού απλής ακρίβειας στον Η/Υ. Η παράσταση αυτή ισοδυναµεί σε ακρίβεια 7 δεκαδικών ψηφίων. Για ένα πραγµατικό αριθµό διπλής ακρίβειας αφιερώνονται 8 bytes. Στην αναπαράσταση αυτή χρησιµοποιούνται 11 bits για τον εκθέτη και 53 bits για το µέγεθος. Τέλος στους πραγµατικούς υψηλής ακρίβειας χρησιµοποιούνται 10 bytes (80 bits) συνολικά. Από αυτά τα 15 bits αφιερώνονται στον εκθέτη και τα υπόλοιπα 65 στο µέγεθος. Οι

53

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

τελευταίοι αυτοί αριθµοί στηρίζονται από την γλώσσα προγραµµατισµού C++ και τον επεξεργαστή Pentium. Στον Πίνακα 2.3. δίνονται αναλυτικά τα χαρακτηριστικά των παραπάνω πραγµατικών αριθµών κινητής υποδιαστολής. Πίνακας 2.3 Είδη πραγµατικών αριθµών κινητής υποδιαστολής και τα χαρακτηριστικά τους. Τύπος

bytes

δυναµική περιοχή

Ακρίβεια

float ή real

4

3.4×10-38 ως 3.4×1038

7

double ή real*8

8

1.7×10-308 ως 1.7×10308

15

long double

10

3.4×10-4932 ως 3.4×104932

19

Γίνεται κατανοητό ότι η αριθµητική κινητής υποδιαστολής υπερτερεί εκείνης της σταθερής υποδιαστολής από άποψη δυναµικής περιοχής, υστερεί όµως από άποψη πολυπλοκότητας και ταχύτητας υπολογισµών. Ως παράδειγµα αναφέρεται η περίπτωση του πολλαπλασιασµού δύο αριθµών κινητής υποδιαστολής όπου πρέπει να πολλαπλασιασθούν τα µεγέθη των αριθµών και να προστεθούν οι εκθέτες για να υπολογισθεί το τελικό γινόµενο. Συνήθως υπάρχουν ξεχωριστές µονάδες για την εκτέλεση των υπολογισµών σε αριθµούς κινητής υποδιαστολής (FPU, Floating Point Units). Αυτές οι µονάδες µπορεί να βρίσκονται εκτός της κύριας µονάδας επεξεργασίας ως ξεχωριστοί συν-επεξεργαστές (µαθηµατικοί συνεπεξεργαστές) ή να είναι ενσωµατωµένες σε αυτή.

2.8. Κώδικες Μέχρι τώρα είδαµε τον τρόπο µε τον οποίο αναπαριστούµε τα διάφορα είδη των αριθµών σε δυαδική µορφή, δηλαδή σε µορφή επεξεργάσιµη από τον υπολογιστή. Όµως ο υπολογιστής θα πρέπει να είναι σε θέση να επεξεργαστεί και άλλου είδους δεδοµένων εκτός από αριθµητικά. Για παράδειγµα αλφαβητικά δεδοµένα, όπως ένα κατάλογο ονοµάτων τα οποία πρέπει να ταξινοµήσουµε. Βλέπουµε λοιπόν πως υπάρχει ανάγκη αντιστοίχισης/κωδικοποίησης των γραµµάτων µε ειδικά σύµβολα.

54

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Κώδικας ASCII Για την κωδικοποίηση λοιπόν των γραµµάτων του αλφαβήτου, αλλά και των διαφόρων συµβόλων, καθιερώθηκε ο κώδικας ASCII (American Standard Code for Information Interchange) (βλ. Παράρτηµα Α). Ο κώδικας αυτός αποτελείται από 7 bits και κατά συνέπεια µπορούν να αντιστοιχηθούν 27=128 διαφορετικά σύµβολα. Για παράδειγµα στο γράµµα b αντιστοιχεί η ακολουθία των δυαδικών ψηφίων 1100010, ενώ στο γράµµα c η ακολουθία των ψηφίων 1100011. Επειδή όµως τα 7 bits δεν ήταν αρκετά για την κωδικοποίηση όλων των διαφορετικών συµβόλων που υπάρχουν (π.χ. ελληνικό αλφάβητο, κεφαλαία και πεζά, τονούµενα και µη), γι' αυτό ο κώδικας αυτός επεκτάθηκε σε 8 bits (8-bit ASCII, extended ASCII). Άλλοι κώδικες που θα πρέπει να αναφερθούν είναι εκείνοι για την αναπαράσταση των αριθµών (όπως BCD, excess-3, Gray), καθώς και οι κώδικες για τον έλεγχο ή και την διόρθωση λαθών (parity, Hamming).

Κώδικας BCD Κατά τον κώδικα BCD (Binary Coded Decimal) κάθε ψηφίο ενός αριθµού του δεκαδικού συστήµατος κωδικοποιείται ξεχωριστά ως δυαδικός. Έτσι ο αριθµός (127)10 κωδικοποιείται κατά BCD ως 0001 0010 0111 (η αντίστοιχη δυαδική αναπαράσταση του αριθµού είναι 1111111). Παλαιότερα συστήµατα υπολογιστών είχαν ειδικές µονάδες για την εκτέλεση πράξεων σε BCD αριθµούς.

Έλεγχος ισοτιµίας Τέλος, για την ανίχνευση λάθους κατά την µετάδοση ή και την αποθήκευση δυαδικών δεδοµένων, χρησιµοποιείται ευρύτατα ο έλεγχος ισοτιµίας (parity checking). Σύµφωνα µε αυτόν, για κάθε δυαδική λέξη µήκους n που αποστέλλεται ή αποθηκεύεται, δηµιουργείται ένα επιπλέον bit, το bit ισοτιµίας, µε τέτοιο τρόπο ώστε το συνολικό πλήθος των µονάδων να είναι άρτιο ή περιττό, ανάλογα µε το αν έχει επιλεγεί άρτια ή περιττή ισοτιµία. Το επιπλέον αυτό bit γίνεται µέρος της νέας λέξης που δηµιουργείται, αυξάνοντας έτσι το συνολικό µήκος της κάθε λέξης σε n+1 bits. Κατά την λήψη ή την ανάγνωση της λέξης ελέγχεται αν το συνολικό πλήθος των µονάδων είναι άρτιο ή περιττό. Με τον τρόπο αυτό διαπιστώνεται αν υπήρξε λάθος σε κάποιο bit (δηλαδή από 0 να έγινε 1 ή το αντίστροφο). Το πιθανό λάθος ανιχνεύεται µόνο, χωρίς

55

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

να είναι δυνατόν να εντοπισθεί η θέση του bit που άλλαξε. Είναι φανερό πως µε τον τρόπο αυτό µπορούµε να ελέγξουµε µόνο περιττό πλήθος λαθών. Παράδειγµα άρτιας ισοτιµίας Το πλήθος των ψηφίων ‘1’, τόσο στο byte που µεταφέρεται όσο και στο ψηφίο 0010 1100 1 " bit ισοτιµίας

ισοτιµίας, πρέπει να είναι άρτιο. Παράδειγµα περιττής ισοτιµίας

Το πλήθος των ψηφίων ‘1’, τόσο στο byte που µεταφέρεται όσο και στο ψηφίο 0010 1100 0 " bit ισοτιµίας

ισοτιµίας, πρέπει να είναι περιττό.

2.9. Έλεγχος του όγκου των δεδοµένων Το πλήθος των bytes που χρειάζονται για να αντιπροσωπευτεί κάποια πληροφορία είναι καθοριστικό τόσο για την ταχύτητα µετάδοσης της πληροφορίας αυτής όσο και για την επεξεργασία και αποθήκευσή της στον Η/Υ. Τα bytes της πληροφορίας είναι οργανωµένα σε σύνολα που καλούνται αρχεία (files). Κάθε αρχείο έχει το δικό του µέγεθος σε bytes. Κάθε 1024 bytes (210) µας κάνουν 1 Kbyte, ενώ 1024 Kbytes µας δίνουν 1 Mbyte. Τα αρχεία που περιέχουν πληροφορία κειµένου είναι συνήθως µικρά σε µέγεθος (µερικά

Kbytes).

αντιπροσωπεύεται

Αυτό µε

1

συµβαίνει byte

διότι

(κώδικας

κάθε ASCII)

χαρακτήρας ενώ

µερικά

του

κειµένου

ακόµη

bytes

χρησιµοποιούνται για την µορφοποίηση του κειµένου. Αρχεία που περιέχουν πληροφορία σχετική µε γραφικά ή στοιχεία πληθυσµών είναι αρκετά µεγαλύτερα (µερικές εκατοντάδες Kbytes). Τέλος, αρχεία εγχρώµων εικόνων (βλέπε σχήµα 2.9) µπορεί να είναι αρκετά Mbytes. Πρέπει να επισηµάνουµε ότι ειδικοί αλγόριθµοι µπορούν να συµπιέσουν σηµαντικά τον όγκο των αρχείων, ανάλογα µε το περιεχόµενό τους.

56

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

1.8K

64K (256×256)

16K

8K

1.2M (600×350)

Σχήµα 2.9. Ο υπολογισµός του µεγέθους µιας εικόνας σε bytes και το ποσό της πληροφορίας που περιέχει ποικίλει. Η εικόνα της γάτας έχει πολύ λίγη πληροφορία (µόνο το όριο της σκιάς). Αντίθετα η µαστογραφική εικόνα έχει 64 Κbytes, ενώ το "ατελιέ του ζωγράφου" του Gustav Courbet 1.2 Mbytes.

Βιβλιογραφία. 1. 'Introduction to Communication Systems', Ferrel G. Stremler, Third Edition, 1990, Addison Wesley. 2. 'Ανάλυση και επεξεργασία ψηφιακών σηµάτων', Β. Αναστασόπουλος, 1998. 3. Θ. ∆εληγιάννης, "Ηλεκτρονικά Ψηφιακά Κυκλώµατα", Εκδόσεις Πανεπιστηµίου Πατρών, 1994 4. Α. Σκόδρας, "Ολοκληρωµένα κυκλώµατα TTL - MOS", Σηµειώσεις Πανεπιστηµίου Πατρών, 1997. 5. Μ.Μ. Mano: "Ψηφιακή σχεδίαση", 2η έκδοση, Εκδόσεις Παπασωτηρίου, 1992.

57

Κεφάλαιο 2

Αναπαράσταση δεδοµένων στον Η/Υ

Προβλήµατα - Ερωτήσεις 1.

Σε ποιες κατηγορίες διακρίνουµε τα διάφορα είδη δεδοµένων που καλείται να επεξεργαστεί ο Η/Υ;

2.

Τι γίνεται στη διαδικασία µετατροπής αναλογικού σήµατος σε ψηφιακό;

3.

Ποια είναι τα δοµικά στοιχεία των ψηφιακών Η/Υ;

4.

Σε τι πλεονεκτούν οι ψηφιακοί Η/Υ των αναλογικών;

5.

Γιατί το δυαδικό σύστηµα είναι συνδεδεµένο µε τους ψηφιακούς Η/Υ;

6.

Ποιός είναι ο λόγος που το δεκαεξαδικό σύστηµα αρίθµησης χρησιµοποιείται συχνά στους Η/Υ για απεικόνιση της πληροφορίας;

7.

Τι είναι βάση ενός συστήµατος αρίθµησης; Ποιος είναι ο γενικός τύπος µετατροπής ενός αριθµού από ένα τυχαίο σύστηµα αρίθµησης στο δεκαδικό;

8.

Να γίνει η µετατροπή των παρακάτω δυαδικών αριθµών στο δεκαδικό 1000101

011001

0101 110011

Ποιο είναι το MSB και ποιο το LSB στους αριθµούς αυτούς, και τι αξία έχουν. 9. Να γίνει η µετατροπή των παρακάτω δυαδικών αριθµών στο δεκαδικό 100.001

1.000101

1011.01010101…

10. Ένας δυαδικός αριθµός των 3 bytes πόσο µεγάλο (ακέραιο) αριθµό µπορεί να εκπροσωπήσει; 11. Να µετατραπούν οι παρακάτω δεκαδικοί αριθµοί σε δυαδικούς 2.35

345

569

13

0.3333333...

12. Να µετατραπούν οι παρακάτω δεκαεξαδικοί αριθµοί σε δυαδικούς 68FA 125

12

35BD

Ποιό είναι το πλέον σηµαντικό ψηφίο και τι αξία έχει σε κάθε έναν από αυτούς; 13. Να µετατραπούν οι παρακάτω δυαδικοί αριθµοί σε δεκαεξαδικούς 011000011010

1101100101101001 0101001

14. Να γίνουν οι προσθέσεις και αφαιρέσεις των παρακάτω δυαδικών 10011+011

1001+110001

110011-1101 11111-1011

11111+1 10001-111001

15. Να γίνουν οι αφαιρέσεις της προηγούµενης άσκησης µε βάση το συµπλήρωµα ως προς δύο. 16. Να γίνουν οι πράξεις µεταξύ των δυαδικών 10001×101

58

1101×11101 11101×110

Κεφάλαιο 2

10001:101

Αναπαράσταση δεδοµένων στον Η/Υ

1101:11101

11101:110

17. Πως θα παρασταθεί ο επόµενος αριθµός πιο σωστά σε παράσταση κινητής υποδιαστολής; 2356000000000000000000 18. Πως αναπαρίσταται στο Η/Υ αριθµός κινητής υποδιαστολής απλής ακρίβειας; Πόσο µεγάλος (ή πόσο µικρός) µπορεί να είναι ο αριθµός αυτός; Να εξηγήσετε την απάντησή σας. 19. Τι είναι το φαινόµενο της υπερχείλισης; Να αναφέρετε παράδειγµα; 20. Τι είναι το φαινόµενο της υποχείλισης; Να αναφέρετε παραδείγµατα. 21. Τι είναι ο κώδικας ASCII; 22. Τι είναι ο κώδικας BCD; 23. Τι είναι ο έλεγχος ισοτιµίας; Να βρεθεί σε περίπτωση περιττής ισοτιµίας, το bit ισοτιµίας για τους επόµενους δυαδικούς αριθµούς. 01100011

00110010

00011110

10101011

24. Πόσο µεγάλο είναι το Kbyte; Πόσο το Mbyte και πόσο το Gbyte; 25. Σήµα ήχου διάρκειας 2 λεπτών, δειγµατοληπτείται µε ρυθµό 44100 δείγµατα/sec και τα ψηφιοποιηµένα δείγµατα αποθηκεύονται στον Η/Υ. Αν κάθε δείγµα χρειάζεται 16 bits για να αναπαρασταθεί στο δυαδικό σύστηµα, πόσα Kbytes θα καταλάβει το σήµα στον σκληρό δίσκο του υπολογιστή; 26. Μία έγχρωµη εικόνα έχει διαστάσεις 1024×1024 pixels. Αν κάθε pixel χρειάζεται τρία bytes για να αναπαρασταθεί ψηφιακά στον Η/Υ (ένα για κάθε ένα χρώµα από τα κόκκινο, πράσινο και µπλε - RGB) πόσο χώρο θα καταλάβει η εικόνα στον σκληρό δίσκο;

59