ΗΥ-120: Ψηφιακή Σχεδίαση
Φθινόπωρο 2002		 Τμ. Επ. Υπολογιστών
Πανεπιστήμιο Κρήτης

Εργαστήριο 6:
Προσημασμένοι Ακέραιοι, Προσθαφαιρέτες, Flip-Flops τύπου RS

18 - 21 Νοεμβρίου 2002

[Βιβλίο: Παράγραφοι 1.5 - 1.6 (σελίδες 13-22), παράγρ. 5.2 χωρίς πρόβλ. κρατ. (σελ. 194-198),
και παράγρ. 6.2 χωρίς JK και T (σελ. 255-261)].

Πολλαπλασιασμός, Διαίρεση, και Υπόλοιπο με δυνάμεις του 2:

Όπως στο δεκαδικό σύστημα ο πολλαπλασιασμός επί 10, 100, κλπ. είναι πολύ απλός, έτσι και στο δυαδικό ο πολλαπλασιασμός επί δύναμη του 2 αντιστοιχεί σε απλή αριστερή ολίσθηση με γέμισμα μηδενικών από δεξιά. Όντως, αν B είναι ο δυαδικός αριθμός bn-1bn-2...b2b1b0 με n bits, όπως είχαμε δεί στο προηγούμενο μάθημα, τότε το γινόμενό του επί 2k είναι:
B·2k = bn-1·2(n-1)+k + bn-2·2(n-2)+k + ... + b2·22+k + b1·21+k + b0·20+k
= bn-1·2n+k-1 + bn-2·2n+k-2 + ... + b1·2k+1 + b0·2k + 0·2k-1 + 0·2k-2 + ...+ 0·21 + 0·20
Βάσει της τελευταίας αυτής ισότητας, ο αριθμός B·2k άναπαρίσταται στο δυαδικό με n+k bits τα οποία είναι: τα n bits του αριθμού B "ολισθημένα" αριστερά κατά k θέσεις (δηλαδή με τη σημαντικότητα καθενός αυξημένη κατά k θέσεις), ακολουθούμενα από k μηδενικά. Γιά παράδειγμα, ο αριθμός 45 (δεκαδικό) = 101101 (δυαδικό), πολλαπλασιαζόμενος επί 16 = 24 δίνει 45x16 = 720 (δεκαδικό), το οποίο στο δυαδικό είναι: 1011010000. Στο δεκαεξαδικό, ο πρώτος αριθμός (45) είναι ο 2D, και το γινόμενό του επί 16 (επί "10" στο δεκαεξαδικό) είναι: 2D0.

Κατ' αντίστοιχο τρόπο, η διαίρεση διά δύναμη του 2 αντιστοιχεί σε δεξιά ολίσθηση· τα λιγότερο σημαντικά bits του αριθμού, που "εκδιώκονται" από τη δεξιά άκρη του, αποτελούν το υπόλοιπο της διαίρεσης. Γιά τον παραπάνω αριθμό B, η διαίρεσή του διά 2k δίνει:

B / 2k = (bn-1·2(n-1)-k + bn-2·2(n-2)-k + ... + bk+1·21 + bk·20) + (bk-1·2k-1 + ... + b1·21 + b0·20) / 2k
Ο πρώτος όρος του παραπάνω αθροίσματος είναι ακέραιος αριθμός, ενώ ο δεύτερος είναι κλασματικός, μικρότερος της μονάδας ή μηδεν, δεδομένου ότι ο αριθμητής (bk-1·2k-1 + ... + b1·21 + b0·20) είναι ένας δυαδικός αριθμός με k bits, άρα πάντα μικρότερος του 2k. Κατά συνέπεια, ο πρώτος όρος (τα αριστερά n-k bits του αρχικού αριθμού) είναι το ακέραιο πηλίκο της διαίρεσης, ενώ ο αριθμητής του δευτέρου όρου (τα δεξιά k bits του αρχικού αριθμού) είναι το υπόλοιπο της (ακέραιας) διαίρεσης. Γιά παράδειγμα, ο αριθμός 205 (δεκαδικό) = 11001101 (δυαδικό), διαρούμενος διά 8 = 23 δίνει πηλίκο 25 (δεκαδικό) = 11001 (δυαδικό), και υπόλοιπο 5 (δεκαδικό) = 101 (δυαδικό). Στο οκταδικό, ο διαιρετέος είναι 315, ο διαιρέτης είναι 10, το πηλίκο είναι 31 (=3x8+1=25 στο δεκαδικό), και το υπόλοιπο είναι 5.

Μιά συνηθισμένη εφαρμογή στους υπολογιστές είναι όταν μιά μεγάλη μνήμη, π.χ. 256 Mbytes, κατασκευάζεται από κάμποσες --π.χ. δεκαέξι (16)-- μικρότερες, μεγέθους δύναμης του 2 η καθεμία --εδώ μεγέθους 16 MBytes = 16,777,216 Bytes καθεμία. Εάν μας ζητηθεί να προσπελάσουμε το Byte με διεύθυνση 167,772,560, σε ποιάν από τις 16 μικρότερες μνήμες βρίσκεται αυτό και τι διεύθυνση μέσα σε αυτήν έχει; Γιά να βρούμε σε ποιά μνήμη θα το αναζητήσουμε, πρέπει να διαιρέσουμε τη διεύθυνση 167,772,560 διά το μέγεθος 16,777,216 των επιμέρους μνημών, που σ' αυτήν την περίπτωση μας δίνει 10 (δεκαδικό) (πρόκειται γιά την 11η μνήμη, αφού οι επιμέρους μνήμες αριθμούνται 0, 1, 2, ..., 15)· το υπόλοιπο της διαίρεσης, 400 (δεκαδικό), μας δίνει την επιθυμητή διεύθυνση μέσα στην επιμέρους μνήμη. Η ζητούμενη διεύθυνση είναι 167,772,560 (δεκαδικό) = A,00,01,90 (δεκαεξαδικό) = 1010,00000000,00000001,10010000 (δυαδικό - 28 bits). Το μέγεθος της κάθε επιμέρους μνήμης (διαιρέτης) είναι 16 M = 224, άρα το ζητούμενο Byte βρίσκεται στη θέση 00...0110010000 (υπόλοιπο διαίρεσης, δηλαδή δεξιά 24 bits της διεύθυνσης) της μνήμης υπ' αριθμόν 1010 (πηλίκο διαίρεσης, δηλαδή αριστερά 28-24 = 4 bits της διεύθυνσης)· μετατρέποντας στο δεκαδικό, βλέπουμε ότι όντως πρόκειται γιά τη θέση 256+128+16 = 400 της μνήμης υπ' αριθμόν 8+2 = 10.

Συστροφή (wrap-around) Αναπαράστασης Αριθμών με n bits:

Μία άλλη εφαρμογή της παραπάνω παρατήρησης σχετικά με το υπόλοιπο της διαίρεσης διά δύναμη του 2 είναι η ερμηνεία των αριθμητικών πράξεων με πεπερασμένο πλήθος bits. Ας φανταστούμε ότι οι ακέραιοι αριθμοί των μαθηματικών έχουν πάρα πολλά bits --όσα χρειάζονται γιά το μέγεθός τους-- αλλά εμείς κάνουμε πράξεις μ' έναν υπολογιστή που έχει πεπερασμένο πλήθος bits, έστω n bits, και γι' αυτό κρατάμε μόνο τα n λιγότερο σημαντικά (δεξιά) bits του "μαθηματικού" αριθμού. Έτσι, όταν προσθέτουμε αριθμούς μ' έναν αθροιστή μεγέθους n bits, αγνοούμε (πετάμε) το κρατούμενο που βγαίνει από την αριστερή άκρη (MSB), διότι δεν έχουμε πού να το αποθηκεύσουμε. Επομένως, αν A είναι το πραγματικό (μαθηματικό) αποτέλεσμα της πράξης μας, ο υπολογιστής μας τελικά θα κρατήσει μόνο το υπόλοιπο της διαίρεσης του A διά 2n (που συνήθως συμβολίζεται: A mod 2n). The number axis wrapping around 4-bit numbers

Εάν σε αυτό τον υπολογιστή, με το πεπερασμένο πλήθος των n bits, αρχίσω να μετρώ από το 0 προς τα πάνω, όταν φτάσω στον αριθμό 2n-1, ο επόμενος αριθμός θα φανεί σαν να είναι πάλι ο 0, και μετά θα συνεχίσω να μετράω πάλι από την αρχή, 1, 10, 11, 100, κλπ. Το φαινόμενο αυτό είναι σαν να έχω ένα τροχό με περίμετρο 2n και με χαραγμένους επάνω του τους 2n υπάρχοντες συνδυασμούς των n bits, δεξιόστροφα από το 00...000 μέχρι το 11...111, και να τυλίγω επάνω σε αυτόν τον τροχό τον άξονα των αριθμών, όπως φαίνεται στο σχήμα δίπλα γιά n=4 bits. Έστω ότι ξεκινάμε το τύλιγμα έτσι ώστε ο ακέραιος αριθμός 0 να συμπέσει με τον δυαδικό κώδικα 00...000. Τότε, οι 2n κώδικες του τροχού θα συμπέσουν με τους ακεραίους αριθμούς από 0 έως 2n-1, όπως ακριβώς καθορίζει ο γνωστός μας από το εργαστήριο 5 κώδικας δυαδικής αναπαράστασης των μη προσημασμένων ακεραίων αριθμών. Όταν όμως εξαντλούνται οι υπάρχοντες συνδυασμοί των n bits, οι περαιτέρω αριθμοί (π.χ. 16, 17,... στο σχήμα) έχουν "τυλιχτεί" πάνω στους ίδιους κώδικες, 000, 001, κλπ, ξανά από την αρχή. Αν λοιπόν μιά πρόσθεση δώσει αποτέλεσμα από 2n και πάνω, το αποτέλεσμα αυτό, στον υπολογιστή με τα n bits, θα μοιάζει σαν ένας μικρότερος αριθμός --αυτός που προκύπτει από το "τύλιγμα". Το φαινόμενο αυτό ονομάζεται "wrap around" --περιτύλιγμα, περιέλιξη, ή συστροφή-- των ακεραίων αριθμών γύρω από τον "τροχό" των πεπερασμένων συνδυασμών που έχει τη δυνατότητα να παραστήσει ο υπολογιστής.

Εάν τώρα θεωρήσουμε και τους αρνητικούς αριθμούς, στον ίδιο άξονα των αριθμών τον συνεστραμμένο γύρω από τον τροχό, όπως φαίνεται στο σχήμα, τότε αποκτάμε μιά μέθοδο --έναν κώδικα-- αναπαράστασης και αρνητικών αριθμών. Ο κώδικας αυτός, που ονομάζεται "συμπλήρωμα ως προς 2", χρησιμοποιείται σήμερα σε όλους τους υπολογιστές γιά την αναπαράσταση "προσημασμένων ακεραίων" (signed integers), και έχει πολύ σημαντικά πλεονεκτήματα απλότητας έναντι άλλων, εναλλακτικών κωδίκων. Όντως, στην καθημερινή μας ζωή, παριστάνουμε τους προσημασμένους ακεραίους διαφορετικά, με το πρόσημο και την απόλυτη τιμή τους (sign-magnitude representation). Η κατεύθυνση αύξησης της απόλυτης τιμής, όμως, είναι άλλοτε δεξιόστροφα (θετικοί αριθμοί) και άλλοτε αριστερόστροφα (αρνητικοί αριθμοί), πάνω στον συνεστραμμένο άξονα των αριθμών. Αυτή η αλλαγή φοράς αύξησης έχει σαν συνέπεια, όταν προσθέτουμε προσημασμένους ακεραίους στην καθημερινή μας ζωή, άλλοτε να πρέπει να κάνουμε πρόσθεση κι άλλοτε αφαίρεση των απολύτων τιμών τους, και μάλιστα πριν από την αφαίρεση να πρέπει να συγκρίνουμε τις δύο απόλυτες τιμές γιά να βρούμε ποιά είναι η μικρότερη και να αφαιρέσουμε αυτήν από την άλλη.

Αντ' αυτού, οι υπολογιστές ακολουθούν τον πολύ απλούστερο τρόπο που πηγάζει από την παραπάνω μέθοδο της "συστροφής": επειδή η (αλγεβρική) αύξηση μιάς τιμής --είτε θετικής είτε αρνητικής-- αντιστοιχεί πάντα σε δεξιόστροφη κίνηση πάνω στον τροχό, προκύπτει ότι αρκεί πάντα να κάνουμε πρόσθεση και μόνο, ανεξαρτήτως του αν προσθέτουμε θετικούς ή αρνητικούς αριθμούς! Η άλλη βασική παρατήρηση είναι ότι η (αλγεβρική) ελάττωση μιάς τιμής, δηλαδή η πρόσθεση ενός αρνητικού αριθμού --π.χ. του (-1)-- που αντιστοιχεί σε αριστερόστροφη κίνηση πάνω στον τροχό --π.χ. κατά 22.5 μοίρες εδώ-- μπορεί να προκύψει ισοδύναμα και σαν πρόσθεση ενός "μεγάλου" θετικού αριθμού --του 15 στο εδώ παράδειγμα, που αντιστοιχεί σε δεξιόστροφη κίνηση κατά 360-22.5 = 337.5 μοίρες. Αν λοιπόν κωδικοποιήσουμε το -1 με τον ίδιο κώδικα όπως και το 15, Negative number representation using wrap-around τότε η πρόσθεση αυτού του κώδικα με έναν τετράμπιτο αθροιστή θα φέρνει το ίδιο αποτέλεσμα όπως η πρόσθεση του -1.

Κώδικας Συμπληρώματος ως προς 2 Προσημασμένων Ακεραίων:

Σ' έναν υπολογιστή που λειτουργεί με λέξεις των n bits καθεμία, η συστροφή των ακεραίων αριθμών προκαλεί την επανεμφάνιση της ίδιας αναπαράστασης κάθε φορά που προχωρούμε κατά 2n προς τα πάνω ή προς τα κάτω. Στο σχήμα δεξιά φαίνεται ένα παράδειγμα γιά έναν οκτάμπιτο υπολογιστή. Ο κώδικας 11111111, ερμηνευόμενος σαν μη προσημασμένος ακέραιος (unsigned integer), παριστά τον αριθμό 255 (δεκαδικό)· όμως, ο ίδιος κώδικας επανεμφανίζεται 256 θέσεις πιό πάνω, στο 255+256 = 511, όπως και 256 θέσεις πιό κάτω, στο 255-256 = -1. Η παρατήρηση αυτή είναι η βάση της δημιουργίας του κώδικα αναπαράστασης των προσημασμένων ακεραίων.

Ο κώδικας "συμπληρώματος ως προς 2" (2's Complement) που χρησιμοποιείται σήμερα στους υπολογιστές γιά την αναπαράσταση προσημασμένων ακεραίων (signed integers), κωδικοποιεί τον αρνητικό αριθμό A, όπου A μεταξύ -2n-1 και -1, με τον κώδικα μη προσημασμένου του ακεραίου A + 2n. Έτσι, στο σχήμα δεξιά, ο αριθμός -2 κωδικοποιείται όπως ο -2 + 2n = 256 - 2 = 254, δηλαδή 11111110. Ομοίως, ο -3 κωδικοποιείται όπως ο 253, ο -4 όπως ο 252, ο -5 κωδικοποιείται 11111011, σαν τον 251, κ.ο.κ. Βλέπουμε ότι οι κώδικες των αρνητικών αριθμών αυξάνουν προς την ίδια κατεύθυνση προς την οποία αυξάνουν και οι κώδικες των θετικών αριθμών. Τους θετικούς αριθμούς από 0 έως 2n-1-1, ο κώδικας συμπληρώματος ως προς 2 τους παριστά πανοποιότυπα όπως και ο κώδικας των μη προσημασμένων ακεραίων.

Σ' έναν οκτάμπιτο υπολογιστή όπως του παραπάνω παραδείγματος, έχουμε τη δυνατότητα να κωδικοποιήσουμε μονοσήμαντα μέχρι 256 διαφορετικούς ακεραίους αριθμούς· οι υπόλοιποι αριθμοί, που "δεν χωράνε" σε 8 bits, θα απεικονίζονται μέσω συστροφής σε κάποιον από τους "βασικούς" αριθμούς. Από τους άπειρους ακεραίους που υπάρχουν, ποιούς 256 θα διαλέξουμε σαν τους "βασικούς" ακεραίους, που θα χρησιμοποιούμε και θα κωδικοποιούμε μονοσήμαντα; Η απάντηση εξαρτάται από τον κώδικα που επιλέγουμε. Είδαμε στο εργαστήριο 5 ότι ο κώδικας 8 bits των μη προσημασμένων ακεραίων παριστάνει τους αριθμούς από το 0 ώς το 255· γενικότερα, με n bits, ο κώδικας αυτός παριστάνει τους ακεραίους από το 0 έως και το 2n-1. Αντ' αυτού, ο κώδικας συμπληρώματος ως προς 2 επιλέγουμε να παριστά μονοσήμαντα, με 8 bits, τους ακεραίους από -128 έως και +127 με 8 bits· γενικότερα, με n bits, ο κώδικας αυτός παριστάνει τους ακεραίους από τον -2n-1 έως και τον +2n-1-1. Τις περιοχές αυτές τις βλέπουμε σημειωμένες στο σχήμα δεξιά με αγκύλες. Όπως βλέπουμε, η περιοχή αναπαράστασης του κώδικα των προσημασμένων ακεραίων είναι σχεδόν συμμετρική γύρω από το μηδέν, και έχει επιλεγεί ούτως ώστε το αριστερό (MS) bit του κώδικα να είναι 1 γιά όλους τους αρνητικούς αριθμούς και μόνο, και να είναι 0 γιά όλους τους μη αρνητικούς αριθμούς και μόνο, δηλαδή γιά τον αριθμό μηδέν και όλους τους θετικούς αριθμούς. Unsigned n-bit adder, adding signed integers

Πρόσθεση Προσημασμένων Ακεραίων σε Συμπλήρωμα ως προς 2:

Θεωρήστε έναν υπολογιστή με λέξεις των n bits, και έναν αθροιστή μη προσημασμένων ακεραίων σαν αυτόν που είδαμε στο εργαστήριο 5, του οποίου όμως αγνοούμε το κρατούμενο εξόδου, κρατάμε δηλαδή μόνο το άθροισμα mod 2n, δηλαδή μόνο τα n LS bits. Θα αποδείξουμε ότι εάν στις δύο εισόδους αυτού του αθροιστή τροφοδοτήσουμε τους κώδικες συμπληρώματος-2 δύο προσημασμένων ακεραίων, As και Bs, μεταξύ -2n-1 και +2n-1-1 ο καθένας, και εάν το (προσημασμένο) άθροισμα των δύο ακεραίων βρίσκεται επίσης στην περιοχή μεταξύ -2n-1 και +2n-1-1, τότε στην έξοδο του παραπάνω αθροιστή θα εμφανιστεί ο κώδικας συμπληρώματος-2 του (προσημασμένου) αυτού αθροίσματος. Με άλλα λόγια, ο αθροιστής μη προσημασμένων ακεραίων, όπως τον ξέρουμε, είναι επίσης και αθροιστής προσημασμένων αριθμών, όταν αυτοί παρίστανται με κώδικα συμπληρώματος-2.

Γιά την απόδειξη θα χρησιμοποιήσουμε, όπως φαίνεται στο παραπάνω σχήμα, τους ακεραίους Au και Bu, που αποτελούν την ερμηνεία των As και Bs ως μη προσημασμένων αριθμών· δηλαδή, όπως ξέρουμε, Au = As + 2n όταν As<0, αλλοιώς Au = As --και ομοίως γιά τον Bu. Ο αθροιστής μη προσημασμένων υπολογίζει το Su = (Au+Bu) mod 2n, το οποίο στη συνέχεια ερμηνεύουμε σαν τον προσημασμένο αριθμό Ss, δηλ. Ss = Su όταν Su<2n-1, αλλοιώς Ss = Su - 2n. Η βασική ιδέα της απόδειξης είναι η εξής: αφού ο Au είναι είτε As είτε As + 2n, και ο Bu είναι είτε Bs είτε Bs + 2n, τότε το άθροισμα (Au+Bu) θα είναι: As+Bs+P, όπου P = είτε 0, είτε 2n, είτε 2n+1. Επομένως, αφού το άθροισμα Su υπολογίζεται mod 2n, ο όρος P θα φεύγει, και θα μας μένει το άθροισμα As+Bs. Γιά μιά πλήρη απόδειξη, πρέπει να εξετάσουμε προσεκτικά τις περιοχές τιμών των προσθετέων και του αθροίσματος, όπως θα κάνουμε τώρα, χωριστά γιά τις τέσσερεις περιπτώσεις: Signed integer addition, usign 2's complement repres.

(α) Θετικός συν Θετικό:
Όταν οι δύο προσθετέοι, As και Bs, είναι θετικοί ή μηδέν και δεν ξεπερνούν τον αριθμό +2n-1-1, τότε Au = As και Bu = Bs, άρα και Au+Bu = As+Bs. Η υπόθεση του θεωρήματός μας είναι ότι το άθροισμα As+Bs μπορεί να παρασταθεί με n bits σε μορφή συμπληρώματος 2, άρα το As+Bs δεν ξεπερνά το +2n-1-1. Κατά συνέπεια, και το S = Au+Bu δεν ξεπερνά το 2n-1-1, επομένως Su = S <2n-1. Σε αυτήν την περιοχή, όμως, Ss = Su, άρα Ss = S = Au+Bu = As+Bs [ΟΕΔ].

(β) Θετικός συν Αρνητκό, με Άθροισμα Θετικό ή Μηδέν:
Έστω ότι As = +A και Bs = -B, όπου A και B είναι θετικοί που δεν ξεπερνούν το +2n-1-1, και ο A είναι μεγαλύτερος ή ίσος του B, όπως φαίνεται στο σχήμα (πρώτοι δύο άξονες). Επειδή As>0, έχουμε Au=As=A· απ' την άλλη μεριά, Bs<0, άρα Bu = Bs+2n = 2n-B. Ο μη προσημασμένος αθροιστής υπολογίζει το άθροισμα S = A + (2n - B) = 2n + (A-B), το οποίο όμως είναι μεγαλύτερο ή ίσο του 2n, επειδή ο A είναι μεγαλύτερος ή ίσος του B. Άρα, Su = S mod 2n = (2n + (A-B)) mod 2n = A - B. Επειδή Su=A-B δεν ξεπερνά το +2n-1-1, θα είναι Ss = Su· επομένως, Ss = A-B = As+Bs [ΟΕΔ].

(γ) Θετικός συν Αρνητκό, με Άθροισμα Αρνητικό:
Έστω ότι As = -A και Bs = +B, όπου A θετικός, B θετικός ή μηδέν, A>B, ο A δεν ξεπερνά το 2n-1, και ο B δεν ξεπερνά το 2n-1-1. Σε αυτή την περίπτωση, έχουμε: Au = As+2n = 2n-A, και Bu=Bs=B, όπως φαίνεται στο σχήμα, στη μετάβαση από τον πρώτο στον τρίτο άξονα των αριθμών. Ο μη προσημασμένος αθροιστής υπολογίζει το άθροισμα S = (2n - A) + B = 2n - (A-B)· επειδή A>B, το άθροισμα αυτό είναι μικρότερο του 2n, άρα ο αθροιστής το βγάζει αυτούσιο: Su = S = 2n - (A-B). Επειδή ο A δεν ξεπερνά το 2n-1, το ίδιο ισχύει και γιά τον (A-B)· επομένως, ο Su είναι μεγαλύτερος ή ίσος του 2n-1. Ένας τέτοιος μη προσημασμένος αριθμός, ερμηνευόμενος σε κωδικοποίηση συμπληρώματος-2, θα ερμηνευτεί σαν ο αρνητικός αριθμός Ss = Su - 2n = (2n-(A-B)) - 2n = -A + B = As + Bs [ΟΕΔ].

(δ) Αρνητκός συν Αρνητκό:
Έστω ότι As = -A και Bs = -B, όπου A και B είναι θετικοί που δεν ξεπερνούν, ούτε αυτοί ούτε το άθροισμά τους, τον αριθμό 2n-1. Τότε: Au = As+2n = 2n-A, και Bu = Bs+2n = 2n-B, όπως φαίνεται στο δεξιό άξονα του σχήματος. Ο μη προσημασμένος αθροιστής υπολογίζει το άθροισμα S = (2n-A) + (2n-B) = 2n+1 - (A+B), το οποίο όμως είναι μεταξύ 2n+1-2n-1 = 2n+2n-1 και 2n+1-1. Άρα, επειδή ο αθροιστής βγάζει μόνο n bits, θα βγάλει τελικά: Su = S mod 2n = (2n+1 - (A+B)) mod 2n = 2n - (A+B), το οποίο είναι μεταξύ 2n-1 και 2n-1. Σε αυτήν την περιοχή τιμών, Ss = Su - 2n = (2n - (A+B)) - 2n = -A-B = As + Bs [ΟΕΔ]. 1's Complement of a word, and its sum with the original word

Εύρεση του Αντιθέτου ενός Αριθμού:

Διαπιστώσαμε ότι μπορούμε να προσθέτουμε προσημασμένους ακεραίους σε μορφή συμπληρώματος ως προς 2 χρησιμοποιώντας τον ίδιο αθροιστή μη προσημασμένων ακεραίων που ήδη είχαμε. Προκειμένου, τώρα, να κάνουμε και αφαιρέσεις, το μόνο που χρειαζόμαστε είναι μιά μέθοδος να βρίσκουμε τον αντίθετο αριθμό, -B, ενός δοθέντα αριθμού B. Όταν αποκτήσουμε μιά τέτοια μέθοδο, θα μπορούμε να κάνουμε την αφαίρεση A-B μέσω της πρόσθεσης A+(-B). Τη ζητούμενη μέθοδο μας τη δίνει η παρατήρηση του σχήματος δεξιά: Έστω B ένας μη προσημασμένος ακέραιος με n bits, και έστω B' ο μη προσημασμένος ακέραιος που προκύπτει από τον B αντιστρέφοντας το κάθε bit του. Τον αριθμό B' τον λέμε και "συμπλήρωμα του B ως προς 1" (1's complement), επειδή κάθε νέο bit είναι 1 μείον το παλαιό bit. Εύκολα βλέπει κανείς ότι το μη προσημασμένο άθροισμα των B + B' ισούται πάντα με 2n-1, αφού είναι ο δυαδικός αριθμός με όλο άσσους: η πρόσθεση ενός bit 0 με ένα bit 1, χωρίς κρατούμενο εισόδου, δίνει πάντα άθροισμα 1 και κρατούμενο 0.

Έστω τώρα ότι μας δίνουν τον παραπάνω κώδικα B, λέγοντάς μας ότι αυτός παριστά έναν προσημασμένο αριθμό σε μορφή συμπληρώματος ως προς 2, και μας ζητούν την αναπαράσταση συμπληρώματος-2 του αντίθετου αριθμού. Θα δείξουμε ότι αυτή είναι πάντα το μη προσημασμένο άθροισμα B'+1, εκτός από την περίπτωση που ο κώδικας που μας έδωσαν είναι ο B=100...00, που παριστάνει τον -2n-1, του οποίου ο αντίθετος δεν εκφράζεται με n bits. Διακρίνουμε δύο περιπτώσεις:

(α) Έστω ότι ο κώδικας B που μας έδωσαν είναι στην περιοχή 0 έως και 2n-1-1· άρα, ειδωμένος σαν προσημασμένος αριθμός σε συμπλήρωμα-2, παριστά πάλι τον αριθμό B. Ζητάμε την αναπαράσταση συμπληρώματος-2 του αρνητικού αριθμού (-B). Ξέρουμε ότι αυτή θα είναι η μη προσημασμένη αναπαράσταση του αριθμού (2n-B). Σύμφωνα με τα παραπάνω, B+B' = 2n-1, άρα 2n-B = B' + 1. Επομένως, η ζητούμενη αναπαράσταση συμπληρώματος-2 του αρνητικού αριθμού (-B) είναι το μη προσημασμένο άθροισμα B' + 1.

(β) Έστω ότι ο κώδικας B που μας έδωσαν είναι στην περιοχή 2n-1+1 έως 2n-1. Ειδωμένος σαν προσημασμένος αριθμός σε συμπλήρωμα-2, ο κώδικας αυτός παριστά τον αρνητικό αριθμό (B-2n), ο οποίος είναι στην περιοχή -(2n-1-1) έως -1. Ζητάμε την αναπαράσταση συμπληρώματος-2 του θετικού αριθμού -(B-2n) = 2n-B, ο οποίος είναι στην περιοχή 1 έως 2n-1-1· άρα, η ζητούμενη αναπαράσταση ταυτίζεται με την μη προσημασμένη αναπαράσταση του ίδιου αριθμού, 2n-B. Σύμφωνα με τα παραπάνω, B+B' = 2n-1, άρα 2n-B = B' + 1. Επομένως, και πάλι, η ζητούμενη αναπαράσταση συμπληρώματος-2 του θετικού αριθμού -(B-2n) είναι το μη προσημασμένο άθροισμα B' + 1, όπου B' είναι το συμπλήρωμα ώς προς 1 του κώδικα που μας έδωσαν αρχικά.

Άσκηση 6.1: Αρνητικοί Αριθμοί και Αφαιρέσεις

[Κάντε την πριν το εργαστήριο και παραδώστε την με την αναφορά σας.]
(α) Χρησιμοποιήστε τις παραστάσεις συμπληρώματος-2 του σχήματος της σελίδας 2, γιά να κάνετε τις παρακάτω προσθέσεις μέσω του γνωστού αλγόριθμου μη προσημασμένης πρόσθεσης, με 8 bits και αγνοώντας το κρατούμενο εξόδου, και επιβεβαιώστε στο δεκαδικό ότι το αποτέλεσμα είναι σωστό: 15+(-3), 2+(-5), (-1)+(-1), (-4)+(-1), (-127)+126.
(β) Χρησιμοποιήστε τις παραστάσεις συμπληρώματος-2 του σχήματος της σελίδας 2, και την παραπάνω μέθοδο εύρεσης του αντίθετου ενός αριθμού, γιά να βρείτε τα εξής αντίθετα, και επιβεβαιώστε την ορθότητα του αποτελέσματος: -(127), -(126), -(4), -(3), -(1), -(0) -(-1), -(-2), -(-4), -(-5), -(-126), και -(-127). Signed Adder/Subtracter made of adder, mux, and inverters

Προσθαφαιρέτες:

Στους υπολογιστές συνήθως βρίσκει κανείς "προσθαφαιρέτες" (adder/subtracter) ακεραίων, κυκλώματα δηλαδή που μπορούν να κάνουν είτε προσθεση είτε αφαίρεση. Το κύκλωμα αυτό κατασκευάζεται πολύ εύκολα και με χαμηλό κόστος, με βάση έναν αθροιστή μη προσημασμένων ακεραίων σαν αυτόν που είδαμε στο εργαστήριο 5, όπως δείχνει το σχήμα δεξιά. Ο αθροιστής φαίνεται στο κάτω μέρος του σχήματος: το σύμβολό του είναι ένα τραπέζιο με μιά εσοχή, έτσι που να θυμίζει ότι παίρνει δύο λέξεις δεδομένων, τις συνδυάζει, και βγάζει μία λέξη-απάντηση· μέσα στο τραπέζιο γράφεται το σύμβολο "+" γιά να ξεχωρίζουμε αυτόν τον αθροιστή από άλλα κυκλώματα που κάνουν (και) άλλες πράξεις πάνω στις δύο εισόδους τους. Το κύκλωμα έχει δύο εισόδους δεδομένων, A και B, μία είσοδο ελέγχου, add'/sub, και μία έξοδο δεδομένων, S. Συνήθως τα δεδομένα είναι προσημασμένοι αριθμοί, αλλά μπορεί να χρησιμοποιηθεί και με μη προσημασμένους.

Η είσοδος A δίδεται στον αθροιστή ως έχει· η είσοδος B, όμως, φτάνει στον αθροιστή με μία από δύο διαφορετικές μορφές, σύμφωνα με το τι επιλέγει ένας πολυπλέκτης 2-σε-1: είτε αυτούσια η λέξη B, είτε το συμπλήρωμά της ως προς 1, B'. Ο βασικός αθροιστής μπορεί να έχει ένα κρατούμενο εισόδου, Cin· όταν κάναμε πρόσθεση το κρατούμενο αυτό εισόδου ήταν πάντα 0, και γι' αυτό μπορούσαμε να το αγνοήσουμε χρησιμοποιώντας έναν ημιαθροιστή γιά τα δεξιά (LS) bits, όμως εδώ θα το χρειαστούμε αυτό το κρατούμενο εισόδου, (άρα χρειαζόμαστε πλήρεις αθροιστές στις θέσεις όλων των bits --και του LS). Γιά να κάνει το κύκλωμα πρόσθεση, S = A+B, θέτουμε την είσοδο ελέγχου add'/sub = 0· αυτό κάνει τη δεύτερη είσοδο του αθροιστή να ισούται με B, και το κρατούμενο εισόδου να είναι 0, όπως ακριβώς δηλαδή πρέπει γιά να γίνει η πρόσθεση A+B. Γιά να κάνει το κύκλωμα αφαίρεση, S = A-B, θέτουμε την είσοδο ελέγχου add'/sub = 1· αυτό κάνει τη δεύτερη είσοδο του αθροιστή να είναι το συμπλήρωμα B', και το κρατούμενο εισόδου να είναι 1. Δεδομένου ότι το κρατούμενο εισόδου έχει την ίδια σημαντικότητα, 20 με τα δεξιά (LS) bits των αριθμών εισόδου, A0 και B0, στα οποία και προστίθεται, το να ισούται το κρατούμενο εισόδου αυτό με 1 ισοδυναμεί με το να προστίθεται ο αριθμός 1 μαζί με τους δύο προσθετέους, A και B'. Επομένως, η έξοδος S = A + B' + 1· ξέρουμε όμως, απ' όσα είπαμε παραπάνω περί αντιθέτων των αριθμών, ότι B'+1 = -B, άρα η έξοδος S = A + (B'+1) = A + (-B) = A - B. Το όνομα του σήματος ελέγχου, add'/sub, είναι κατάλληλα γραμμένο ώστε να μας θυμίζει ότι όταν αυτό είναι αληθές (1) το κύκλωμα κάνει "sub" (αφαίρεση), ενώ όταν αυτό είναι ψευδές (0), δηλαδή add' ψευδές άρα add αληθές, τότε το κύκλωμα κάνει "add" (πρόσθεση). 7483 chip: 4-bit binary adder

Πείραμα 6.2: Τετράμπιτος Αθροιστής

ΠΡΟΣΟΧΗ!: το chip αυτού του πειράματος έχει τα pins τροφοδοσίας σε παράξενη, μη συμβατική θέση. Συνδέστε τα πολύ προσεκτικά, αλλοιώς θα κάψετε το chip, προκαλώντας έξοδα και αδυναμία εκτέλεσης του πειράματος από συναδέλφους σας!
Στο πείραμα αυτό θα χρησιμοποιήσετε το chip "7483" (της οικογένειας TTL) το οποίο είναι ένας τετράμπιτος δυαδικός αθροιστής: περιέχει 4 πλήρεις αθροιστές (του ενός bit καθένας), με τα κρατούμενά τους συνδεδεμένα σε μιάν αλυσίδα. Τα chips που θα βρείτε στο εργαστήριο γράφουν επάνω "T74LS83AB1", και λεπτομερείς πληροφορίες γιά έναν ισοδύναμο τύπο chip μπορείτε να βρείτε π.χ. στο: http://www.fairchildsemi.com/ds/DM/DM74LS83A.pdf . Συνδέστε έναν μεταγωγό διακόπτη στην είσοδο κρατουμένου του αθροιστή, και 5 LED's στις εξόδους του, όπως στο σχήμα. Γιά να τροφοδοτήσετε τις εισόδους δεδομένων, επειδή αυτές είναι πολλές και η σύνδεσή τους σε διακόπτες είναι προβληματική, σας προτείνεται να πάρετε ένα σύρμα από την καθεμία τους και να το φέρετε στις οριζόντιες γραμμές τροφοδοσίας του breadboard. Τα bits Ai και Bi πάνω στο chip βρίσκονται σε ημιτυχαίες, ανακατωμένες θέσεις· όταν τα φέρετε στις γραμμές τροφοδοσίας του breadboard, φροντίστε να τα φέρετε τακτικά, με τη σειρά από MS προς LS, χωριστά τα Α και χωριστά τα B, όπως στο σχήμα. Γιά να αλλάξετε τους αριθμούς εισόδου και να πειραματιστείτε με διάφορες τιμές, μετακινείτε τα επιθυμητά σύρματα πάνω ή κάτω, προσέχοντας να μην τα στραβώνετε και να τα εισάγετε ίσια στις τρύπες. Πριν φτάσετε στο εργαστήριο, συμπληρώστε τον παρακάτω πίνακα: 
     Ain   Bin Cin Au+Bu+Cin  S(5b)  As+Bs+Cin  S(4)  Bin' =Bs'  As-Bs'=S(4)
    0010  0011  1  2+3+1 = 6  00110  2+3+1 = 6  0110  1100 = -4  2-(-4) = 6
    0010  1011  1  2+11+1=14  01110  2-5+1 =-2  1110  0100 = +4  2-(+4) =-2
    1110  1111  1
{{επόμενες γραμμές}}:
όπου οι {{επόμενες γραμμές}} είναι: 1111 + 1111, 0101 + 1110, 0101 + 0001, 0101 + 0000, και όλες με Cin=1. Στον πίνακα αυτόν, Ain, Bin, και Cin είναι οι δυαδικές είσοδοι του αθροιστή· Au+Bu+Cin είναι η ερμηνία των εισόδων και της αναμενόμενης εξόδου σύμφωνα με τον κώδικα μη προσημασμένων αριθμών· S(5b) είναι η αναμενόμενη πεντάμπιτη έξοδος του αθροιστή (άθροισμα μη προσημασμένων εισόδων), και πρέπει να συμφωνεί με την προηγούμενη στήλη· As+Bs+Cin είναι η ερμηνεία των εισόδων και της αναμενόμενης εξόδου σύμφωνα με τον κώδικα συμπληρώματος-2 προσημασμένων αριθμών· S(4) είναι η αναμενόμενη τετράμπιτη έξοδος του αθροιστή (άθροισμα προσημασμένων εισόδων), και πρέπει να συμφωνεί με την προηγούμενη στήλη· Bin' είναι το συμπλήρωμα ως προς 1 της εισόδου Bin --ας θεωρήσουμε από δω και πέρα ότι αυτό ήταν η αρχική είσοδος ενός αφαιρέτη, πριν ένας αντιστροφέας δώσει το Bin στον αθροιστή, και Bs' είναι η ερμηνεία αυτού του Bin' σαν προσημασμένου αριθμού· As-Bs'=S(4) είναι η ερμηνεία της πράξης του (φανταστικού) αφαιρέτη, και πρέπει να συμφωνεί με τη στήλη S(4). Στο εργαστήριο, επαληθεύστε πειραματικά τις εξόδους S(5b) και S(4) του πίνακα. Μην χαλάστε το κύκλωμά σας όταν τελειώσετε: θα το χρειαστείτε στο πείραμα 6.3. 7483 + 7486: adder + XOR's yield 4-bit adder/subtracter

Πείραμα 6.3: Προσθαφαιρέτης με XOR

Ο προσθαφαιρέτης που είδαμε στη σελίδα 5 παραπάνω μπορεί εναλλακτικά να υλοποιηθεί με πύλες αποκλειστικού-Ή (XOR), όπως φαίνεται στο σχήμα δίπλα, αντί αντιστροφέων και πολυπλέκτη. Ο λόγος είναι ότι οι πύλες XOR δίνουν στην έξοδό τους την πρώτη είσοδο όταν η δεύτερη είσοδος είναι 0, ενώ δίνουν στην έξοδό τους το συμπλήρωμα της πρώτης εισόδου τους όταν η δεύτερη είσοδος είναι 1. Φτιάξτε έναν τετράμπιτο προσθαφαιρέτη, χρησιμοποιώντας τον αθροιστή του προηγουμένου πειράματος 6.2 και ένα chip πυλών XOR (7486) όπως αυτό του πειράματος 5.3· γιά διευκόλυνσή σας, το pin-out του επαναλαμβάνεται στο σχήμα δίπλα. Πριν φτάσετε στο εργαστήριο, κάντε το σχεδιάγραμμα συνδεσμολογίας που δείχνει ποιά συγκεκριμένα pins ποιού chip πρέπει να συνδέσετε πού. Στο εργαστήριο, κατασκευάστε τον προσθαφαιρέτη, και δώστε του τις εισόδους Bin' του πίνακα του παραπάνω πειράματος 6.2, με το σήμα add'/sub = 1, ούτως ώστε να διαπιστώσετε πως αυτές οι αφαιρέσεις γίνονται σωστά. Μετά, γυρίστε το σήμα add'/sub στο 0 (πρόσθεση), και κάντε κάμποσες προσθέσεις γιά να διαπιστώσετε τη σωστή λειτουργία --π.χ. κάντε τις προσθέσεις των δύο πρώτων στηλών του παραπάνω πίνακα, χωρίς κρατούμενο εισόδου αυτή τη φορά.

Πείραμα 6.4: Flip-Flop τύπου RS

Στο πείραμα 2.5 είχαμε δεί ότι τα κυκλώματα με θετική ανάδραση έχουν συνήθως δύο σταθερές καταστάσεις, κι έτσι χρησιμοποιούνται σαν μνήμες· το βασικό τέτοιο κύκλωμα λέγεται flip-flop. Είχαμε δεί τότε ένα flip-flop φτιαγμένο με ηλεκτρονόμους. Εδώ θα δούμε ένα όμοιο flip-flop, "τύπου RS", φτιαγμένο με πύλες. Το σχήμα (a) δείχνει τη βασική ιδέα της θετικής ανάδρασης: η πολικότητα της ανάδρασης δεν έχει αντιστροφή. Το κύκλωμα αυτό ναι μεν είναι flip-flop, πλην όμως δεν έχει είσοδο, άρα δυνατότητα εγγραφής. Το κύκλωμα (b) διατηρεί τη θετική πολικότητα της ανάδρασης, και εισάγει εισόδους S (set - θέση) και R' (reset - επαναφορά, μηδένιση). Όταν S=1, η έξοδος Q τίθεται σε κατάσταση 1, ανεξαρτήτως της προηγούμενής της κατάστασης. Positive feedback; RS flip-flop; 2 x NOR implementation Όταν R'=0 (και S=0), η έξοδος Q επαναφέρεται στην κατάσταση 0, πάλι ανεξαρτήτως της προηγούμενής της κατάστασης. Στην τεχνολογιά CMOS, οι πύλες AND και OR δεν υπάρχουν, και πρέπει να συντεθούν από NAND/NOR· μπορούμε να κερδίσουμε σε κατασκευαστική απλότητα μετατρέποντας το κύκλωμα (b) στο κύκλωμα (c), εισάγοντας δύο αντιστροφές στο βρόχο ανάδρασης. Η μία αντιστροφή προσάπτεται στην έξοδο της πύλης OR, μετατρέποντας την έτσι σε πύλη NOR, η δε άλλη αντιστροφή προσάπτεται στις εισόδους της πύλης AND (αλλάζοντας και την πολικότητα του σήματος R' σε R), μετατρέποντας την έτσι και αυτήν σε πύλη NOR (κανόνας DeMorgan). Ξανασχεδιάζοντας το κύκλωμα (c) με ισοδύναμη τοπολογιά και σύμβολα, παίρνουμε το "κλασσικό" κύκλωμα του flip-flop τύπου RS με πύλες NOR που φάινεται στο σχήμα (d)· εξ' ίσου κλασσικό είναι και το δυϊκό του με πύλες NAND.

Κατασκευάστε το flip-flop τύπου RS του σχήματος (d) στο εργαστήριο. Χρησιμοποιήστε ένα chip "7402" (της οικογένειας TTL) το οποίο περιέχει 4 πύλες NOR των δύο εισόδων όπως φαίνεται στο σχήμα (e). Τα chips που θα βρείτε στο εργαστήριο γράφουν επάνω "SN74LS02N", και λεπτομερείς πληροφορίες γι' αυτά μπορείτε να βρείτε στο: http://www.onsemi.com/pub/Collateral/SN74LS02-D.PDF . Συνδέστε στις εξόδους του flip-flop δύο LED's. Διαπιστώστε ότι το κύκλωμα έχει μνήμη, αφού διατηρεί την κατάστασή του (μία από τις δύο δυνατές) όταν R=S=0. Γράψτε Q=1 στο flip-flop, πατώντας στιγμιαία το διακόπτη S. Γράψτε Q=0 στο flip-flop, πατώντας στιγμιαία το διακόπτη R. Οι δύο έξοδοι, Q και Q', είναι η μία το συμπλήρωμα της άλλης όταν δεν είναι ταυτόχρονα ενεργοποιημένες και οι δύο είσοδοι εγγραφής, R και S. Όταν πατήστε και τους δύο διακόπτες, R και S, τι συμβαίνει; Όταν τους αφήστε, σε ποιά κατάσταση μένει το flip-flop; Μπορείτε να τους αφήστε "ταυτόχρονα";

Up to the Home Page of CS-120
 		 © copyright University of Crete, Greece.
Last updated: 12 Nov. 2002, by M. Katevenis.