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

Εργαστήριο 5:
IC's, Δυαδική Πρόσθεση

4 - 7 Νοεμβρίου 2002
Υπενθύμιση: Διαγωνισμός Προόδου: Σάββατο 16 Νοεμβρίου.

[Βιβλίο: Παράγραφοι 1.2 - 1.4 (σελίδες 5-13), και παράγραφος 4.3 (σελ. 148-154)].

Δυαδική Αρίθμηση:

Μία δυαδική λέξη αποτελούμενη από n bits μπορεί να αναπαραστήσει ένα από 2n διακριτά στοιχεία, με τη χρήση ενός κώδικα που να αντιστοιχίζει (αυθαίρετα) τον κάθε συνδυασμό των bits στο κάθε επιθυμητό στοιχείο. Με τον ίδιο αυτό τρόπο, οι δυαδικές λέξεις μπορούν να αναπαραστήσουν αριθμούς, αρκεί να επιλέξουμε τον επιθυμητό κώδικα. Γιά την αναπαράσταση των μη-αρνητικών ακεραίων (non-negative integers) (άλλως: "μη προσημασμένων ακεραίων" - unsigned integers) χρησιμοποιείται καθολικά η κωδικοποίηση του δυαδικού συστήματος μέτρησης που αποτελεί κατ' ευθείαν μεταφορά στη "βάση 2" των όσων ισχύουν στη "βάση 10", δηλαδή στο δεκαδικό σύστημα μέτρησης. Όπως ξέρουμε, ο δεκαδικός n-ψήφιος αριθμός "dn-1dn-2...d2d1d0", όπου τα "ψηφία" di (γιά i=0, 1, ..., n-1) είναι ακέραιοι αριθμοί μεταξύ του 0 και του 9, παριστάνει τον ακέραιο αριθμό:
dn-1·10n-1 + dn-2·10n-2 + ... + d2·102 + d1·101 + d0·100
Γιά παράδειγμα, ο συμβολισμός "14508", όταν ερμηνευτεί σαν δεκαδικός αριθμός, παριστάνει τον ακέραιο 1·104 + 4·103 + 5·102 + 0·101 + 8·100 = 10000 + 4000 + 500 + 8. Κατά εντελώς ανάλογο τρόπο, ο δυαδικός αριθμός μεγέθους n bits "bn-1bn-2...b2b1b0", όπου τα "bits" bi (γιά i=0, 1, ..., n-1) είναι ακέραιοι αριθμοί μεταξύ του 0 και του 1, παριστάνει τον αριθμό:
bn-1·2n-1 + bn-2·2n-2 + ... + b2·22 + b1·21 + b0·20
Γιά παράδειγμα, η οκτάμπιτη δυαδική λέξη "11010001", όταν ερμηνευτεί σαν (δυαδικός) αριθμός, παριστάνει τον ακέραιο 1·27 + 1·26 + 0·25 + 1·24 + 0·23 + 0·22 + 0·21 + 1·20 = 27 + 26 + 24 + 20 = 128 + 64 + 16 + 1 = 209 (δεκαδικό). Γενικότερα, ο n-ψήφιος αριθμός σε βάση H (όπου H είναι ένας ακέραιος μεγαλύτερος του 1) "hn-1hn-2...h2h1h0", όπου τα "ψηφία" hi (γιά i=0, 1, ..., n-1) είναι ακέραιοι αριθμοί μεταξύ του 0 και του H-1, παριστάνει τον αριθμό:
hn-1·Hn-1 + hn-2·Hn-2 + ... + h2·H2 + h1·H1 + h0·H0
Στην καθημερινή μας ζωή χρησιμοποιούμε δεκαδικούς αριθμούς, δηλαδή αριθμούς με βάση H=10. Η μέτρηση του χρόνου (60 δευτερόλεπτα, 60 λεπτά, 12 ή 24 ώρες), καθώς και ορισμένες Αγγλοσαξωνικές μονάδες (π.χ. ένα πόδι = 12 ίντσες), είναι κατάλοιπα ενός (παλαιοτέρου;) δωδεκαδικού συστήματος μέτρησης (βάση H=12). Τα ψηφιακά συστήματα λειτουργούν με δυαδικούς αριθμούς (βάση H=2).

Επίσης, στην επιστήμη υπολογιστών χρησιμοποιούμε οκταδικούς (octal) αριθμούς (βάση H=8) και δεκαεξαδικούς (hexadecimal) αριθμούς (βάση H=16), επειδή η μετατροπή ανάμεσα σε αυτούς και τους δυαδικούς αριθμούς είναι απλούστατη, και, απ' την άλλη μεριά, οι οκταδικοί και δεκαεξαδικοί αριθμοί έχουν πολύ λιγότερα ψηφία από τους δυαδικούς, κι έτσι τους γράφει και τους διαβάζει πολύ ευκολότερα ο άνθρωπος. Οι οκταδικοί αριθμοί χρησιμοποιούν 8 ψηφία: τα ψηφία 0, 1, 2, 3, 4, 5, 6, και 7. Οι δεκαεξαδικοί αριθμοί χρησιμοποιούν 16 ψηφία: τα ψηφία 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, και F. Έτσι, οι πρώτοι 65 αριθμοί στο δεκαδικό (decimal), δυαδικό (binary), οκταδικό (octal), και δεκαεξαδικό (hex) είναι οι εξής:

    Dec  Binary  Oct Hex   |   Dec  Binary  Oct Hex   |   Dec  Binary  Oct Hex
    00   000000  00  00    |   16   010000  20  10    |   32   100000  40  20
    01   000001  01  01    |   17   010001  21  11    |   33   100001  41  21
    02   000010  02  02    |   18   010010  22  12    |   34   100010  42  22
    03   000011  03  03    |   19   010011  23  13    |   ...   ...   ... ...
    04   000100  04  04    |   20   010100  24  14    |   38   100110  46  26
    05   000101  05  05    |   21   010101  25  15    |   39   100111  47  27
    06   000110  06  06    |   22   010110  26  16    |   40   101000  50  28
    07   000111  07  07    |   23   010111  27  17    |   41   101001  51  29
    08   001000  10  08    |   24   011000  30  18    |   42   101010  52  2A
    09   001001  11  09    |   25   011001  31  19    |   ...   ...   ... ...
    10   001010  12  0A    |   26   011010  32  1A    |   46   101110  56  2E
    11   001011  13  0B    |   27   011011  33  1B    |   47   101111  57  2F
    12   001100  14  0C    |   28   011100  34  1C    |   48   110000  60  30
    13   001101  15  0D    |   29   011101  35  1D    |   ...   ...   ... ...
    14   001110  16  0E    |   30   011110  36  1E    |   62   111110  76  3E
    15   001111  17  0F    |   31   011111  37  1F    |   63   111111  77  3F 
                                                      |   64  1000000 100  40 
Η μετατροπή αριθμού μεταξύ δυαδικού, οκταδικού, και δεκαεξαδικού είναι εντελώς τετριμένη, βάσει της εξής παρατήρησης: Επειδή η βάση H = 8 = 23, κάθε ψηφίο ενός οκταδικού αριθμού αντιστοιχεί ακριβώς σε μιά τριάδα από bits του ίδιου αριθμού γραμμένου στο δυαδικό, ξεκινώντας από δεξιά. Ομοίως, επειδή η βάση H = 16 = 24, κάθε ψηφίο ενός δεκαεξαδικού αριθμού αντιστοιχεί ακριβώς σε μιά τετράδα από bits του ίδιου αριθμού γραμμένου στο δυαδικό, ξεκινώντας πάλι από δεξιά.

Η μετατροπή αριθμού από το δυαδικό στο δεκαδικό μπορεί να γίνει όπως στο παράδειγμα στην αρχή της παραγράφου, προσθέτοντας δηλαδή τις δυνάμεις του 2 που αντιστοιχούν στους άσσους του αριθμού. Τέλος, η μετατροπή αριθμού από το δεκαδικό στο δυαδικό μπορεί να γίνει βάσει της παρατήρησης ότι αν ένας αριθμός είναι μονός τότε το δεξιότερο bit του στο δυαδικό (το "λιγότερο σημαντικό" bit - least significant bit - LSB) θα είναι άσσος, ενώ αν ο αριθμός είναι ζυγός τότε το LS bit του είναι μηδέν. Πράγματι, αν ο αριθμός A είναι, όπως παραπάνω, ο bn-1bn-2...b2b1b0, τότε διαιρώντας τον A διά 2 έχουμε:

A/2 = bn-1·2n-2 + bn-2·2n-3 + ... + b2·21 + b1·20 + ( b0 / 2 )
Έτσι διαπιστώνουμε ότι το ακέραιο πηλίκο της διαίρεσης του A διά 2 είναι ο δυαδικός αριθμός bn-1bn-2...b2b1, ενώ το υπόλοιπο της διαίρεσης είναι το bit b0. Με αυτόν τον τρόπο βρίσκουμε το λιγότερο σημαντικό (LS) bit του A στο δυαδικό. Συνεχίζοντας με τον ίδιο τρόπο, διαιρώντας το προηγούμενο ακέραιο πηλίκο διά 2, βρίσκουμε το επόμενο bit, b1, κ.ο.κ.

Άσκηση 5.1: Μετατροπές Βάσης Αριθμών

[Άσκηση στο χαρτί· παράδοση μέσα στην αναφορά του εργαστηρίου].
(α) Θεωρήστε δεκαεξάμπιτους (16-bit) μη προσημασμένους (unsigned) αριθμούς. Πόσα ψηφία θα έχουν αυτοί όταν εκφραστούν στο δεκαεξαδικό; Γιατί; Πόσα ψηφία στο οκταδικό; Γιατί; Στο οκταδικό, το αριστερότερό τους ψηφίο (περισσότερο σημαντικό - most significant - MS) τι μπορεί να είναι μόνο; Γιατί;
(β) Μετατρέψτε τους δεκαδικούς αριθμούς 9485 και 23592 σε δεκαεξάμπιτους δυαδικούς αριθμούς, δείχνοντας και τις ενδιάμεσες πράξεις που κάνετε. Στη συνέχεια, επαληθεύστε τις μετατροπές αυτές, βρίσκοντας από τους δυαδικούς αριθμούς τους δεκαδικούς στους οποίους αυτοί αντιστοιχούν. Τέλος, γράψτε τους δύο δεκαεξάμπιτους δυαδικούς αριθμούς που βρήκατε στο οκταδικό και στο δεκαεξαδικό, δείχνοντας καθαρά από που προκύπτει το κάθε ψηφίο του κάθε οκταδικού και δεκαεξαδικού αριθμού.
(γ) Θεωρήστε τον εξαψήφιο δεκαεξαδικό αριθμό 8F2B7C. Πόσα bits έχει; Γιατί; Γράψτε τον στο δυαδικό και στη συνέχεια στο οκταδικό.

Πρόσθεση Δυαδικών Αριθμών: Αλγόριθμος "Κρατουμένου"

Έστω ότι θέλουμε να προσθέσουμε τους δυαδικούς αριθμούς, μεγέθους n bits ο καθένας, A = an-1an-2...a2a1a0 και B = bn-1bn-2...b2b1b0. Προφανώς, από μαθηματική άποψη, το άθροισμά τους είναι:
A + B = (an-1+bn-1)·2n-1 + (an-2+bn-2)·2n-2 + ... + (a2+b2)·22 + (a1+b1)·21 + (a0+b0)·20
Το πρόβλημα είναι ότι αυτή η μαθηματική απεικόνιση δεν μας δίνει με άμεσο τρόπο τη δυαδική αναπαράσταση του αθροίσματος, διότι οι συντελεστές (ai+bi) των δυνάμεων του 2 (γιά i=0, 1, ..., n-1) δεν είναι ακέραιοι αριθμοί μεταξύ του 0 και του 1, όπως πρέπει γιά τη δυαδική αναπαράσταση, αλλά είναι ακέραιοι αριθμοί μεταξύ του 0 και του 2, δηλαδή μπορούν να έχουν τρείς διαφορετικές τιμές ο καθένας.

Γιά να βρούμε το άθροισμα σε μορφή δυαδικής αναπαράστασης πρέπει να ακολουθήσουμε μιά διαδικασία ("αλγόριθμο"!) ανάλογη της πρόσθεση με "κρατούμενο" (carry) του δημοτικού σχολείου. Ξεκινάμε από τη λιγότερο σημαντική (LS) θέση (θέση 0), (a0+b0). Εάν το άθροισμα αυτό είναι 0 ή 1, τότε το ονομάζουμε s0, και αυτό αποτελεί το λιγότερο σημαντικό (LS) bit του αθροίσματος. Εάν όμως a0+b0 = 2, τότε εκφράζουμε το 2 στο δυαδικό (10), και επομένως θέτουμε s0 = 0 (αφού το άθροισμα είναι ζυγός αριθμός), και θυμόμαστε ότι μας έχει "περισσέψει" μιά ποσότητα 2·20 (όταν μας προέκυψε στη θέση 0) = 1·21 (όταν τη μεταφέρουμε στη θέση 1), την οποία και "κρατάμε" γιά να τη μεταφέρουμε στη θέση 1, ονομάζοντας την c1 (κρατούμενο - carry).

Συνεχίζοντας με τη θέση 1, πρέπει να προσθέσουμε τα bits a1 και b1 των δύο αριθμών, καθώς και το κρατούμενο c1 που προέκυψε από τη θέση 0. Καθένας από αυτούς τους τρείς αριθμούς είναι 0 ή 1 (το κρατούμενο μπορεί να ήταν "2" στη θέση 0, αλλά όταν μεταφέρθηκε στη θέση 1 έγινε το μισό ("1"), διότι η θέση 1 έχει διπλάσια "σημαντικότητα" (δύναμη του 2) από τη θέση 0). Αθροίζοντας αυτούς τους 3 αριθμούς, που καθένας τους είναι 0 ή 1, προκύπτει ένας αριθμός μεταξύ 0 και 3. Αν το άθροισμα αυτό είναι 0 ή 1, τότε το ονομάζουμε s1, και αυτό αποτελεί το bit του αθροίσματος στη θέση 1. Εάν όμως a1+b1+c1 είναι 2 ή 3, τότε το εκφράζουμε στο δυαδικό σαν έναν αριθμό των 2 bits (2 bits αρκούν!), ονομάζουμε s1 το δεξιό και c2 το αριστερό από αυτά τα 2 bits, και θυμόμαστε ότι μας έχει "περισσέψει" μιά ποσότητα 2c2·21 (όταν μας προέκυψε στη θέση 1) = c2·22 (όταν τη μεταφέρουμε στη θέση 2), την οποία και "κρατάμε" γιά να τη μεταφέρουμε στη θέση 2.

Από κει και πέρα, η διαδικασία (αλγόριθμος) της πρόσθεσης προχωρεί με τον ίδιο τρόπο. Η παρατήρηση-κλειδί ("αναλλοίωτη συνθήκη" - invariant property) είναι ότι το "κρατούμενο εισόδου" ci στη θέση i είναι πάντα 0 ή 1. Την ιδιότητα αυτή την αποδείξαμε στη θέση i=1, και την αποδεικνύουμε στη συνέχεια επαγωγικά, από τη θέση i γιά τη θέση i+1: αφού το άθροισμα (ai+bi+ci) είναι άθροισμα τριών αριθμών που καθένας τους είναι 0 ή 1, τότε το άθροισμα αυτό θα είναι μεταξύ 0 και 3, άρα μπορεί να εκφραστεί με μοναδικό τρόπο σαν δυαδικός αριθμός των 2 bits, ci+1·2i+1 + si·2i, όπου οι αριθμοί ci+1 και si είναι μεταξύ 0 και 1. Ο.Ε.Δ.

8-bit adder, consisting of a chain of eight 1-bit adders

Ο Ψηφιακός Αθροιστής:

Η διαδικασία πρόσθεσης που διατυπώσαμε παραπάνω μεταφράζεται άμεσα σε ψηφιακό κύκλωμα όπως φαίνεται δίπλα. Το παράδειγμα στο σχήμα αφορά την πρόσθεση δύο οκτάμπιτων δυαδικών αριθμών, A και B. Κάθε ορθογώνιο κουτί παριστά ένα κύκλωμα πρόσθεσης γιά μία θέση των bits. Το δεξιό (LS) κύκλωμα είναι απλούστερο από τα άλλα, διότι έχει να προσθέσει μόνο δύο εισόδους (του ενός bit καθεμία)· αυτό λέγεται "ημιαθροιστής" (half-adder, "HA"). Το άθροισμα που υπολογίζει το εκφράζει σαν δύο bits: το bit s0 που έχει τον ίδιο βαθμό σημαντικότητας με τις εισόδους (θέση 0), και το bit c1 που έχει βαθμό σημαντικότητας κατά 1 μεγαλύτερο αυτού των εισόδων. Τα υπόλοιπα 7 κυκλώματα είανι κάπως πολυπλοκότερα: πρέπει να προσθέσουν τρείς εισόδους (του ενός bit καθεμία) το καθένα· αυτά λέγονται "πλήρεις αθροιστές" (full-adders, "FA"). Ο ρόλος ενός τέτοιου κυκλώματος είναι να μετράει πόσοι άσσοι υπάρχουν στις τρείς εισόδους του --άρα μοιάζει με το κύκλωμα του πειράματος 3.3-- και να εκφράζει αυτό τον αριθμό στο δυαδικό, με 2 bits, τα ci+1 και si. Το κρατούμενο εξόδου του κάθε αθροιστή είναι είσοδος στον επόμενο προς τα "αριστερά" (προς MS) αθροιστή. Στην αριστερότερη (MS) θέση, το κρατούμενο εξόδου πρέπει να θεωρηθεί ότι αποτελεί το επόμενο σε σημαντικότητα bit του αθροίσματος, αφού το άθροισμα δύο οκτάμπιτων αριθμών (από 0 έως 255 καθένας) ενδέχεται να απαιτεί 9 bits γιά να παρασταθεί (άθροισμα από 0 έως 510).

Ο οκτάμπιτος αθροιστής που σχεδιάσαμε παραπάνω είναι ένα συνδυαστικό κύκλωμα, διότι οι έξοδοί του, S, εξαρτώνται μόνο από τις παρούσες τιμές των εισόδων του, A και B, δηλαδή δεν έχει μνήμη. Όταν συνθέταμε συνδυαστικά κυκλώματα είχαμε δεί τη μέθοδο του χάρτη Karnaugh, με την οποία το κύκλωμα εκφράζονταν σαν το λογικό Ή κάμποσων όρων που ο καθένας τους ήταν το λογικό ΚΑΙ εισόδων ή συμπληρωμάτων τους. Ακολουθόντας τη μέθοδο αυτή μπορεί κανείς να φτιάξει το ένα από τα κουτιά του σχήματος --περίπου έτσι είχαμε ξεκινήσει και στο πείραμα 3.3. Όμως, αν προσπαθήσουμε να εφαρμόσουμε τη μέθοδο αυτή σε ολόκληρο τον (π.χ. οκτάμπιτο) αθροιστή, (i) ο χάρτης Karnaugh θα είναι τεραστίων διαστάσεων (216 τετράγωνα!), και (ii) το κύκλωμα που θα προέκυπτε θα ήταν εξωπραγματικά τεράστιο. Αντ' αυτού, το κύκλωμα που σχεδιάσαμε εδώ, στο παραπάνω σχήμα, είναι πολύ διαφορετικό: αποτελείται από πολλά υποκυκλώματα (ένα γιά κάθε θέση bit), όπου η έξοδος του ενός είναι είσοδος στο άλλο (κρατούμενα), δηλαδή πρόκειται γιά μιάν αλυσίδα πολλών κυκλωμάτων αντί γιά μόλις δύο επίπεδα πυλών (ΚΑΙ - Ή) που δίνει ο χάρτης Karnaugh. Το πλεονέκτημα της νέας μεθόδου είναι η τεράστια απλοποίηση του κυκλώματος. Το μειονέκτημα είναι η μεγαλύτερη καθυστέρηση: γιά να προκύψουν τα τελευταία 2 bits του αθροίσματος, s7 και s8, πρέπει πρώτα να τελειώσουν τη δουλειά τους, "σειριακά" ο ένας μετά τον άλλον, όλοι οι επιμέρους αθροιστές (ενός bit καθένας), από τη δεξιά μέχρι την αριστερή άκρη. Pin-out of 7408 (AND), 7432 (OR), 7486 (XOR), & Test Ckt

Άσκηση 5.2: Δυαδική Πρόσθεση

[Άσκηση στο χαρτί· παράδοση με την αναφορά του εργαστηρίου].
Προσθέστε στο δυαδικό, με τον παραπάνω αλγόριθμο πρόσθεσης με κρατούμενα, τους δύο δεκαεξάμπιτους δυαδικούς αριθμούς που βρήκατε στην άσκηση 5.1(β) όταν μετατρέψατε τους δεκαδικούς αριθμούς 9485 και 23592 στο δυαδικό. Στη συνέχεια, μετατρέψτε το δυαδικό άθροισμα που βρήκατε στο δεκαδικό, και επαληθεύστε ότι αυτό ισούται με 9485+23592.

Πείραμα 5.3: Chips Λογικών Πυλών

Στα σημερινά πειράματα θα χρησιμοποιήσουμε τρία "κλασσικά" chips της παλιάς οικογένειας "TTL" (διαφορετική τεχνολογιά από την CMOS) --ή συμβατά τους σε CMOS-- που περιέχουν από 4 πύλες των 2 εισόδων καθεμία, όπως φαίνεται στο σχήμα δεξιά. Το chip "7408" περιέχει 4 πύλες ΚΑΙ· αυτά που έχουμε στο εργαστήριο γράφουν επάνω "M74HC08B1" και περισσοτερες πληροφορίες γι' αυτά μπορείτε να βρείτε στο http://eu.st.com/stonline/books/pdf/docs/1885.pdf. Το chip "7432" περιέχει 4 πύλες Ή· αυτά που έχουμε στο εργαστήριο γράφουν επάνω "SN74LS32N" και περισσοτερες πληροφορίες γι' αυτά μπορείτε να βρείτε στο http://www.onsemi.com/pub/Collateral/SN74LS32-D.PDF. Τέλος, το chip "7486" περιέχει 4 πύλες Αποκλειστικού-Ή (XOR)· τα chips στο εργαστήριο μας γράφουν επάνω "T74LS86B1" και είναι παρόμοια με αυτά που περιγράφονται στο http://www.fairchildsemi.com/ds/DM/DM74LS86.pdf.

Στο εργαστήριο, ελέγξτε τη σωστή λειτουργία των πυλών αυτών, δίνοντας σε καθεμιά τους όλους τους δυνατούς συνδυασμούς τιμών εισόδων και παρατηρώντας την έξοδό τους γιά να δείτε αν παίρνει τη σωστή τιμή κάθε φορά. Μπορείτε να δίνετε τιμές στις εισόδους είτε με διακόπτες SPDT (μισός DPDT) όπως στο πείραμα 4.3, είτε με απλούς διακόπτες κουμπιού (SPST) όπως φαίνεται στο σχήμα εδώ, αρκεί να υπάρχει και η αντίσταση που φαίνεται γιά να δίνει στην έξοδο την "άλλη" τιμή όταν ο διακόπτης είναι ανοικτός (δεν κάνει επαφή). [Κανονικά, στην οικογένεια TTL, το κύκλωμα αυτό χρησιμοποιείται με το διακόπτη γειωμένο, και μιάν αντίσταση από 1 έως 4.7 KΩ προς τη θετική τροφοδοσία, λόγω των ασύμμετρων ρευμάτων εισόδου στις 2 καταστάσεις· εμείς, γιά να διατηρήσουμε τη θετική πολικότητα του διακόπτη όπως και στο παρελθόν, μπορούμε να χρησιμοποιήσουμε την παραλλαγή που φαίνεται, με κόστος τη μεγαλύτερη κατανάλωση ισχύος]. Συνδέστε από μιάν ενδεικτική LED στον κάθε διακόπτη, γιά να βλέπετε τις τιμές εισόδου, και συνδέστε π.χ. την LED "probe" σε κάθε έξοδο που θέλετε να παρακολουθήσετε. Μπορείτε να ελέγξετε όλες τις πύλες, τη μία μετά την άλλη, μετακινώντας μόνο τα 3 καλώδια που φαίνονται με διακεκομένη γραμμή από τη μία πύλη στην άλλη. Μην ξεχνάτε να κάνετε πολύ προσεκτικά τις σωστές συνδέσεις τροφοδοσίας (γείωση, VDD), διότι κινδυνεύετε να κάψετε τα chips αν αυτές λείπουν ή είναι λανθασμένες.

Half-Adder from XOR & AND; Full-Adder from Half-Adder & OR

Πείραμα 5.4: Ημιαθροιστής (Half-Adder)

Ονομάσαμε ημιαθροιστή (half-adder, HA) το κύκλωμα που προσθέτει 2 bits, ai και bi, και εκφράζει το άθροισμά τους σε μορφή ενός δυαδικού αριθμού 2 bits, ci+1si. Πρίν φτάσετε στο εργαστήριο, κατασκευάστε τον πίνακα αληθείας αυτού του κυκλώματος, και αποδείξτε μ' αυτόν ότι ο ημιαθροιστής μπορεί να υλοποιηθεί όπως φαίνεται στο σχήμα δεξιά. Στη συνέχεια, σχεδιάστε ένα chip 7408 και ένα 7486, και δείξτε τις συνδέσεις που πρέπει να γίνουν σ' αυτά προκειμένου να υλοποιήστε έναν ημιαθροιστή· δείξτε πού θα συνδέσετε τις δύο πηγές εισόδων σας, και οδηγήστε την έξοδο ci+1 στη LED.6 και την έξοδο si στη LED.7. Στο εργαστήριο, κατασκευάστε το κύκλωμα αυτό, και ελέγξτε τη σωστή λειτουργία του.

Πείραμα 5.5: Πλήρης Αθροιστής (Full-Adder)

Ονομάσαμε πλήρη αθροιστή (full-adder, FA) το κύκλωμα που προσθέτει 3 bits, ai, bi, και ci, και εκφράζει το άθροισμά τους σε μορφή ενός δυαδικού αριθμού 2 bits, ci+1si. Το κύκλωμα αυτό μπορεί να κατασκευαστεί χρησιμοποιώντας ημιαθροιστές όπως δείχνει το παραπάνω σχήμα, δεδομένου ότι γιά να προσθέσω τρείς αριθμούς αρκεί να προσθέσω τους δύο πρώτους, και στο άθροισμά τους να προσθέσω τον τρίτο. Κανονικά, πρέπει επίσης να προσθέσω και τα κρατούμενα. Όμως, μπορεί κανείς εύκολα να αποδείξει ότι το πολύ ένας από τους δύο ημιαθροιστές του σχήματος μπορεί να βγάζει κρατούμενο 1, κάθε φορά· άρα, αντί γιά κύκλωμα πρόσθεσης των δύο επιμέρους κρατουμένων, αρκεί να χρησιμοποιηθεί μιά πύλη Ή.

Πρίν φτάσετε στο εργαστήριο: (i) γράψτε την απόδειξη της παραπάνω ιδιότητας· (ii) κατασκευάστε τον πίνακα αληθείας του πλήρη αθροιστή βάσει των προδιαγραφών του· (iii) κατασκευάστε τον πίνακα αληθείας του κυκλώματος με τους δύο ημιαθροιστές και την πύλη Ή που φαίνεται στο παραπάνω σχήμα, συγκρίνετέ τον με το (ii), και αποδείξτε έτσι ότι το κύκλωμα αυτό υλοποιεί όντως έναν πλήρη αθροιστή· και (iv) σχεδιάστε ένα chip 7408, ένα 7486, και ένα 7432, και δείξτε τις συνδέσεις που πρέπει να γίνουν σ' αυτά προκειμένου να υλοποιήστε έναν πλήρη αθροιστή σύμφωνα με το παραπάνω σχήμα· δείξτε και τις συνδέσεις εισόδων και εξόδων, όπως πρίν. Στο εργαστήριο, κατασκευάστε το κύκλωμα αυτό, και ελέγξτε τη σωστή λειτουργία του.

Άσκηση 5.6: Ταχύτητα Δυαδικής Πρόσθεσης

[Άσκηση στο χαρτί· παράδοση μέσα στην αναφορά του εργαστηρίου].
Θεωρήστε ότι η κάθε λογική πύλη έχει καθυστέρηση 100 ps, δηλαδή η έξοδός της παίρνει τη σωστή καινούργια τιμή 100 ps μετά την αλλαγή μιάς εισόδου σε μιά νέα "σωστή" τιμή. Στην πράξη, η καθυστέρηση μιάς πύλης κυμαίνεται σε μιά ευρεία περιοχή τιμών, εξαρτώμενη από πολλούς παράγοντες· πάντως, η τιμή που υποθέτουμε, 100 ps = 0.1 ns - ένα δέκατο του δισεκατομμυριοστού του δευτερολέπτου, είναι αντιπροσωπευτική του τι συμβαίνει μέσα σ' ένα σύγχρονο (2002) επεξεργαστή με ρολόϊ κοντά στο GHz --ας πούμε με ρολόϊ στην περιοχή 600 MHz έως 1 GHz. Προσοχή: η τιμή που υποθέτουμε είναι πολύ μικρότερη από την καθυστέρηση των πυλών των chips 7408, 7432, και 7486, πρώτ' απ' όλα επειδή εκείνες οι καθυστερήσεις αφορούν σήματα που είναι έξω από το chip, ενώ εδώ μιλάμε γιά σήματα μέσα στο ίδιο chip, και δεύτερον επειδή εδώ υποθέτουμε πιό σύγχρονη τεχνολογία κατασκευής.
Υπενθύμιση: τα υποπολλαπλάσια της μονάδας είναι: m (milli - χιλιοστό - 10-3μ (micro - εκατομμυριοστό - 10-6n (nano - δισεκατομμυριοστό - 10-9p (pico - τρισεκατομμυριοστό - 10-12f (femto - τετράκις εκατομμυριοστό - 10-15a (atto - πεντάκις εκατομμυριοστό - 10-18
(α) Πόσες πύλες μεσολαβούν από την είσοδο κρατουμένου του πλήρη αθροιστή του πειράματος 5.5 μέχρι την έξοδο κρατουμένου του; Πολλαπλασιάστε τον αριθμό αυτό επί 100 ps γιά να βρείτε κατά προσέγγιση την καθυστέρηση ενός bit της πρόσθεσης.
(β) Θεωρήστε έναν αθροιστή λέξεων των 64 bits, όπως αυτοί που υπάρχουν στους σύγχρονους 64-μπιτους επεξεργαστές. Τι καθυστέρηση θα είχε ένας τέτοιος αθροιστής αν ήταν κατασκευασμένος από μιάν αλυσίδα 64 πλήρων αθροιστών σαν αυτούς του (α), όπως έδειχνε το σχήμα της σελίδας 3; Γιά απλότητα, θεωρήστε ότι ο ημιαθροιστής του δεξιού bit έχει κι αυτός την ίδια καθυστέρηση.
(γ) Αν η περίοδος του ρολογιού του επεξεργαστή ήταν περίπου ίση με την καθυστέρηση του αθροιστή (όπως συχνά είναι), τι συχνότητα ρολογιού θα είχε αυτός ο επεξεργαστής; Πώς συγκρίνεται αυτή με τις συχνότητες ρολογιών των σύγχρονων επεξεργαστών; [Ευτυχώς, υπάρχουν τρόποι να γίνονται πολύ γρηγορότερα οι προσθέσεις, γι' αυτό και οι επεξεργαστές είναι τόσο γρήγοροι όσο είναι!...]


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