Ch2

Συνδυαστικα Λογικα Κυκλωματα Combinational Logic Circuits • Λογικες Πυλες • Βoolean Algebra • Aπλοποιηση – με Boolean Algebra και K-MAPS

• Yλοποιηση Kυκλωματων – ΝΑΝD, NOR – Two-level – XOR

Συνδυαστικα Λογικα Κυκλωματα • Ψηφιακα συστηματα επεξεργαζονται δυαδικες πληροφοριες • Συχνα αποτελουνται απο ολοκληρωμενα κυκλωματα (integrated ccts) περιεχουν 100δες εκτακομυρια xtrs και πολλα μετρα μηκος συρμα (πολυ μικρο πλατος: nm! τριχα/10000) – Τransistors και συρματα σιλικονης

• Βασικα κυκλωματα ενος ψηφιακου συστηματος μπορουν να περιγραφουν με Λογικες Πυλες (Logic Gates: Gates ΑΝD, OR,

Συνδυαστικα Λογικα Κυκλωματα • Αφαιρετικοτητα: δεν χρειαζεται γνωση ηλεκτρονικων ιδιοτητων πυλων για περιγραφη/σχεδιασμο ψηφιακων συστηματων, μονο λογικες ιδιοτητες • Μια πυλη εκτελει μια πραξη στα εισαγομενα για να παραξει ενα εξαγομενο. Το εξαγομενο χρησιμοποιηται στην εισοδο καποιας πυλης. Πυλη

Πυλη

Βοοlean Algrebra • Mαθηματικη Θεωρια Λογικης (1850s) • Χρησιμοποιηται για – περιγραφη δυαδικων λογικων κυκλωματων με μαθηματικες εκφρασεις – επεξεργασια εκφρασεων – αναλυση και σχεδιασμο

Δυαδικη Λογικη • Δυαδικες μεταβλητες παιρνουν δυο διακριτες τιμες: 0 και 1 • Μεταβλητες συμβολιζονται με Α,Β,C,..,Z • 3 Bασικοι Λογικοι Τελεστες ΑΝD Z=X.Y ή Z=XY OR Z=X+Υ NOT Ζ=Χ, Z = X’ (αρνηση, συμπληρωμα) • Διαφορες δυαδικης λογικης και αριθμητικης...

Oρισμοι Τελεστων AND 0 .0 = 0 0 .1 = 0 1 .0 = 0 1 .1 = 1

OR 0+0=0 0+1=1 1+0=1 1+1=1

NOT 0=1 1=0

Πινακας Αληθειας (Τruth Table) • Περιλαμβανει ολους τους συνδυασμους τιμων σε μια εκφραση και την αντιστοιχη τιμη της εκφρασης • n εισοδους, n στηλες και 2n σειρες. Καθε σειρα ενα μοναδικο δυαδικο συνδυασμο (0 .. 2n-1)

Λογικες Πυλες (Logic Gates) • Λογικες Πυλες: ηλεκτρονικα κυκλωματα με ενα ή περισοτερα σηματα εισοδου και ενα σημα εξοδου. • Τα σηματα ειναι σε ηλεκτρικη μορφη (ταση) με μια απο δυο τιμες • Oι τιμες αντιπροσωπευουν πεδια τασης, πχ – high ή 1: 3 με 5V – low ή 0: -0.5 με 2V

• Πρεπει να συμπεριφερονται συμφωνα με τον πινακα αληθεια τους

Λογικες Πυλες (Logic Gates) • Γραφικα συμβολα βασικων λογικων πυλων:

• Χρονικο Διαγραμμα Y:ταση(τιμη) Χ:χρονος

AND και OR πυλες με περισσοτερες απο 2 εισοδους

Βοοlean Συναρτησεις (Functions) • F = X + Y ’Z ονομα οροι συναρτησης συναρ. • F ειναι 1 oταν ο ορος Χ=1 ή ο oρος Υ’Ζ=1. Το Υ’Ζ=1 οταν το Υ’=1 (Υ=0) και Ζ=1

Βοοlean Συναρτησεις (Functions) • Mια Βοοlean συναρτηση αποτελειται απο μια δυαδικη μεταβλητη (που δεικνυει την συναρτηση), το συμβολο =, και μια εκφραση που μπορει να αποτελειται απο δυαδικες μεταβλητες, 0, 1, (,) και λογικες πραξεις • Η εκφραση οριζει την σχεση μεταξυ δυαδικων μεταβλητων. • Η συναρτηση για συγκεκριμενες τιμες των μεταβλητων παιρνει τιμη 1 ή 0

Βοοlean Συναρτησεις και Πινακες Αληθειας • Μια συναρτηση μπορει να οριστει επισης με πινακα αληθειας, πχ F = X + Y’Z – 3 μεταβλητες εισοδου, 23=8 σειρες – coverage: 1 literal 4, 2 literal 2, 3 literal 1

Βοοlean Συναρτησεις και Λογικα(Συνδυαστικα)Κυκλωματα • F= X + Y’Z

Βοοlean Συναρτησεις • Μια συναρτηση μπορει να περιγραφει με πινακα αληθειας μονο με ενα μοναδικο τροπο • Σε αλγεβρικη μορφη (και σε κυκλωμα) μπορει να εκφραστει η ιδια συναρτηση με διαφορους τροπους • Ποιος ειναι ο καλυτερος τροπος; – μικροτερος αριθμο πυλων και εισοδων σε πυλες

• Πως επιτυγχανεται; – Αλγεβρικη επεξ, Κ-ΜΑP,Q-M, οχι παντοτε εφικτο

Βασικες Ταυτοτητες της Αλγεβρας Βοοle

Αντιμεταθεση, προσεταιρισμος;;;, καταμερ;;;

Δυϊσμος (Duality) • Iδιοτητα αλγεβρας Boole: οταν μια σχεση ισχυει, ισχυει και η dual της • Το dual μιας σχεσης το παιρνουμε με να αλλαξουμε το πιο κατωAND ↔OR, 0↔1 • Προσοχη δεν λεει (και δεν ισχυει) οτι η σχεση και το dual της ειναι ισα

Βασικες Ιδιοτητες • Σχεσεις ισχυουν και οταν μια μεταβλητη αντικατασταθει απο μια εκφραση, πχ – Χ + 1 = 1, εαν το Χ = ΑΒ + C, τοτε ΑΒ+ C + 1 = 1 – (Χ+Υ) (Χ+Ζ) = Χ + ΥΖ, εαν το X=A, Y=B, Ζ = CD, τοτε (Α+Β)(Α+CD)=A + BCD

DeMorgan’s Theorem • Υπολογισμος συμπληρωματος μιας εκφρασης

Προσοχη στη σειρα αποτιμησης

DeMorgan’s Theorem • Ισχυει για πολλαπλες μεταβλητες • X1+X2+…+Xn = X1 X2 … Xn • X1X2…Xn = X1 + X2 + …+Xn

Προτεραιοτητα Τελεστων • () • NOT – αν υπολογιζεται το συμπληρωμα μιας εκφρασης πρεπει να αποτιμηθει και μετα να υπολογιστει το συμπληρωμα της

• ΑΝD • ΟR • Ιδια προτεραιοτητα: αριστερα προς δεξια

Αλγεβρικος Χειρισμος (και Απλοποιηση)

Aπολοποιηση • F = Χ’ΥΖ + Χ’ΥΖ’ + ΧΖ = X’Y (Z+Z’) + XZ = X’Y (1) + XZ = X’Y + XZ

Eπαληθευση

Στοχοι Απλοποιησης • Kαθε ορος σε μια boolean εκφραση απαιτει μια πυλη και καθε μεταβλητη σε ενα ορο (συμπληρωμενη ή οχι) καθοριζει μια εισοδο στην πυλη (literal) • Στοχος της απλοποιησης ειναι να μειωθουν oι οροι(terms) ή/και τα literals • Aλγεβρικη απλοποιηση μπορει να πετυχει την πιο απλοποιημενη εκφραση. Δεν υπαρχει συγκεκριμενη διαδικασια (trial and error!)

Παραδειγματα • • • • • •

Χ+ΧΥ ΧΥ+ΧΥ’ Χ+Χ’Υ Χ(Χ+Υ) (Χ+Υ)(Χ+Υ’) Χ(Χ’+Υ)

Προσοχη: Δυϊσμος

Consensus Theorem (Θεωρια της Ομοφωνιας) • ΧΥ + Χ’Ζ+ΥΖ = ΧΥ + Χ’Ζ • ΧΥ + Χ’Ζ + (Χ+Χ’) ΥΖ = • οταν ΥΖ=1 τοτε η το ΧΥ=1 ή το Χ’Ζ=1 • Dual: (X+Y)(X’+Z)(Y+Z) = (X+Y)(X’+Z) • (A+B)(A’+C)=

Συμπληρωμα μιας Συναρτησης • F’ απο το F – πινακα αληθειας: εναλλαγη 1 και 0 – εκφραση: • DeMorgan’s Theorem • Demorgan και Δυισμος – ΑΝD↔OR, 0↔1και συμπληρωσε καθε literal – πριν τις αλλαγες προσθεσε παρενθεσεις για καθε ορο

• F = X’YZ’+X’Y’Z • G= X(Y’Z’+YZ)

Προτυπες Μορφες • Οροι με γινομενα/products(anded literals) και αθροισματα/sums(ored literals) – ΧΥΖ’ – Χ΄+Υ+Ζ

• Tυποποιηση • Ελαχιστοροι και Μεγιστοροι

Eλαχιστοροι(minterms) • Minterm:γινομενο με ολες τις μεταβλητες • 2n ελαχιστοροι οταν εχουμε n μεταβλητες – πχ με 3 μεταβλητες Χ,Υ,Ζ: 8 ελαχιστοροι

Mεγιστοροι (Μaxterms) • Maxterm: αθροισμα με ολες τις μεταβλητες • 2n μεγιστοροι οταν εχουμε n μεταβλητες – πχ με 3 μεταβλητες Χ,Υ,Ζ: 8 μεγιστοροι

Ελαχιστοροι/Μεγιστοροι • mj = Mj, mj = Mj • πχ – m3=X’YZ – M3= (X’YZ)’ = X+Y’+Z’

Εκφραση απο πινακα αληθειας • Το αθροισμα ολων των minterms που η συναρτηση παιρνει τιμη 1(sum of minterms)

• F=X’YZ’+X’YZ+XY’Z+XYZ=m2+m3+m5+m7 • F(X,Y,Z) = Σm(2,3,5,7)

Συμπληρωμα Εκφρασης • Εαν F = Σm(2,3,5,7) - μορφη αθροισμα γινομ. • τοτε F’=Σm(0,1,4,6) • και F=ΠΜ(0,1,4,6) - μορφη γινομενο αθροισμ.

Θυμασται... • οποιαδηποτε εκφραση μπορει να μετατραπει σε προτυπη μορφη μεσο του πινακα αληθεια της • μια λογικη εκφραση με n μοναδικες μεταβλητες εχει 2n ελαχιστορους • μια συναρτηση μπορει να εκφραστει σαν αθροισμα ελαχιστορων (γινομενο μεγιστορων) • μια συναρτηση που περιεχει ολους τους ελαχιστορους ειναι ιση με την τιμη 1

Παραδειγμα • Εκφραστε την πιο κατω συναρτηση με αθροισμα ελαχιστορων E =Y’+X’Z’

• E(X,Y,Z)=Σm(0,1,2,4,5)

Προτυπη Μορφη:Sum of Products • Απλοποιημενη εκφραση απο sum-of-minterms • F =Σm(2,3,5,7) =X’YZ’+X’YZ+XY’Z+XYZ (SOM) =X’Y + XZ (SOP)

Υλοποιηση SOP με 2-levels • F = Y’ + X’YZ’+XY

Εκφρασεις οχι σε μορφη SOP • Mπορουν να μετατραπουν με αλγεβρικους χειρισμους ή μεσο πινακα αληθειας και απλοπ.

• Ποια ειναι η καλυτερη επιλογη;;;; – 3-levels ή 2-levels

Προτυπη Μορφη POS • F = X(Y’+Z)(X+Y+Z’)

Aπλοποιηση με πινακες Κarnaugh Maps ή K-maps • Γραφικη μεθοδος απλοποιησης – καθε κελι ενας ελαχιστορος – αναγνωριση ‘‘μορφων’’ σε ενα πινακα και απλοπ. – απλοποιηση παραγει εκφραση σε SOP(POS) μορφη που μπορει να υλοποιηθει με 2-levels – συγκεκριμενη διαδικασια που παραγει την βελτιστη(οχι απαραιτητα μοναδικη) απλοποιηση – Απλοποιηση: ελαχιστους ορους και literals

• Αποτελεσματικη για μεχρι και 4 μεταβλητες

Κ-Μaps με 2 μεταβλητες

m1+m2+m3

K-maps με 3 μεταβλητες Σειρα!

– Οι τιμες δυο γειτονικων (οριζοντια/καθετα) ελαχιστορων διαφερουν μονο σε ενα bit position (πχ 100-101) – covered row/columns (1 literal σε 4 minterms, 2 σε δυο minterms και 3 σε ενα)

Βασικη Ιδεα Κ-maps • Oριζοντια ή/και καθετα γειτονικοι ελαχιστοροι μπορουν να απλοποιηθουν γιατι περιεχουν literals σε συμπληρωμενη και μη συμπληρωμενη μορφη (αυτα τα literals μπορουν να απλοποιηθουν) – πχ m5+m7 = XY’Z+XYZ = XZ (Y’+Y) = XZ – ή m0+m1+m2+m3=X’Y’Z’+X’Y’Z+X’YZ’+X’YZ = X’(Y’Z’+Y’Z+YZ’+YZ) = X’

Βασικη Ιδεα Κ-maps • • • •

ενα κελλι:1 minterm δυο κελλια: ορο με 2 literals τεσσερα κελλια: ορο με1 literal οκτω κελλια:

Παραδειγμα: Σm(2,3,4,5)

Παραδειγμα: Σm(2,3,4,5) • 1 στα κελια με ελαχιστορους της συναρτησης • καθορισμος του ελαχιστου αριθμου ορθογωνιων (με 1,2,4,8,… κελια) που περιλαμβανουν ολους τους ελαχιστορους • καθε ορθογωνιο αντιστοιχει σε ενα (απλοποιημενο) γινομενο. το γινομενο αποτελειται απο τα ελαχιστα literals που περιλαμβανουν το ορθογωνιο

Κριτηριο Γειτονοτητας • Οχι αναγκαστικα διπλα στο Κ-map, απλος να διαφερουν οι αντιστοιχοι ελαχιστοροι σε ενα bit position, πχ Σm(0,2,4,6)

Σm(0,1,2,3,6,7)

Δυο βελτιστες λυσεις: Σm(1,3,4,5,6)

• F = X’Z+XZ’+XY’ ή F = X’Z+XZ’+Y’Z

Εκφραση σε SOP μορφη F(Χ,Υ,Ζ)= X’Z+X’Y+XY’Z+YZ

Εκφραση σε SOP μορφη F(Χ,Υ,Ζ)= X’Z+X’Y+XY’Z+YZ • Ελαχιστοροι…

• F = Z+X’Y

K-maps με 4 μεταβλητες

K-maps με 4 μεταβλητες • Ιδια μεθοδος οπως με με 3 μεταβλητες – – – – –

ενα κελλι: ελαχιστορος με 4 literals δυο κελλια: ορος με 3 literals τεσσερα κελια: ορος με 2 literals οκτω κελλια: ορος με 1 literal δεκαεξι κελλια: συναρτηση με παντοτε τιμη 1

• Κριτηριο Γειτονοτητας: ελαχιστοροι διαφερουν σε ενα bit position

F(W,X,Y,Z) = X’Z’

F(W,X,Y,Z) = X’Z’

F(W,X,Y,Z)= Σm(0,1,2,4,5,6,8,9,12,13,14)

F(W,X,Y,Z)= Σm(0,1,2,4,5,6,8,9,12,13,14)

• F=

F=A’B’C’+B’CD’+AB’C’+A’BCD’

F=A’B’C’+B’CD’+AB’C’+A’BCD’

• F=

Συστηματικη Επεξεργασια Πινακων • Prime Implicant (PI): oρθογωνιο με το μεγιστο δυνατο μεγεθος σε ενα K-MAP που δεν περιλαμβανεται σε πιο μεγαλο ορθογωνιο • Essential Prime Implicant (EPI): PI που περιεχει ελαχιστορο δεν που περιλαμβανεται σε αλλο PI

F(A,B,C,D)=Σm(1,3,4,5,6,7,12,14)

• PI:

,EPI:

, F=

Essential και nonEssential PI Σm(0,5,10,11,12,13,15)

• PI: , EPI: , F=

Eπιλογη για nonEPI • Eπελεξε ΕPI • Eπελεξε nonEPI που δεν εχουν overlap • Eπελεξε nonEPI που εχουν overlap (τυχαια)

nonEPI επιλογη Σm(0,1,2,4,5,10,11,13,15)

• PI: , EPI: , F=

F(A,B,C,D)=Σm(0,1,2,5,8,9,10) F σε POS

• F’ = , F = (dual και συμπληρωμα literals)

Aπολοποιηση με POS • F’: απλοποιηση 0 στο Κ-Μap - μορφη SOP • συμπληρωμα F’ - μορφη POS • Oταν εχουμε ενα απο F’pos, Fpos, F’sop, Fsop μπορουμε να παραξουμε τα αλλα

Συνθηκες Αδιαφοριας (don’t-care conditions) • Συγκεκριμενοι συνδυασμοι τιμων εισοδου που δεν συμβαινουν ή οταν συμβουν δεν μας ενδιαφερει τι θα συμβει στην εξοδο – πχ BCD 4 σηματα εισοδου μα μονο 10 απο τους 16 συνδυασμους συμβαινουν

• Δεικνυονται με X στα K-maps, και μπορουν να υποθεσουμε πως ειναι 0 ή 1 (don’t care minterms δεν χρειαζεται να απλοποιηθουν)

F(A,B,C,D)=Σm(1,3,7,11,15) d(A,B,C,D)=Σm(0,2,5) • Απλοποιηση με don’t cares

• Δυο λυσεις οχι ισες!

Βασικες Πυλες για Υλοποιηση Ψηφιακων Συστηματων

Βασικες Πυλες για Υλοποιηση Ψηφιακων Συστηματων

Universal Πυλη: ΝΑND

Αλλα συμβολα για NAND πυλες

2-level υλοποιηση SOP εκφρασεων με NAND πυλες • F=AB+CD

F(X,Y,Z)=Σm(1,2,3,4,5,7)

Διαδικασια Σχεδιασμου με NAND • Απλοποιημενη εκφραση σε SOP μορφη • ΝΑΝD πυλη για καθε ορο με τουλαχιστο δυο literals (1st level) • ΝΑΝD ή ΝΟΤ-ΟR πυλη με εισοδο τις εξοδους απο το 1st level • oροι με ενα literal χρειαζονται NOT πυλη στο 1st level

Μultilevel ΝΑΝD κυκλωματα

Διαδικασια για Multilelevel NAND κυκλωματα • ΑΝD με ΝΑΝD (and-not) • OR με NAND (not-or) • για καθε μονο bubble σε μια γραμμη insert ΝΟΤ πυλη ή συμπληρωσε το σημα εισοδου

Universal πυλες:ΝΟR

Αλλα συμβολα για NΟR πυλες

Yλοποιηση συναρτησεων σε POS μορφη

• Multilevel: παρομοια με NAND

Πυλη ΧΟR • X⊕Y = XY’+X’Y Χ Υ

X⊕Y

Ex-OR Tαυτοτητες • • • • •

X⊕0 = X X⊕1 = X’ X⊕Χ = 0 X⊕Χ’ = 1 X⊕Y’ = X⊕Y X’⊕Y = X⊕Y X⊕Y = Υ⊕Χ (X⊕Υ)⊕Ζ = Χ⊕(Υ⊕Ζ)

ΧΟR υλοποιηση με πυλες NAND

ΧΝΟR • X⊕Y = XY+X’Y’

Odd Function (XOR με >2 inputs) • X⊕Y⊕Z = (XY’+X’Y)Z’+ (X’Y’+XY)Z = XY’Z’+X’YZ’+ X’Y’Z+XYZ • μονός αριθμος σηματων εισοδου με τιμη 1

Parity bit • Πχ για ενα μυνημα με 3 bits (ΧΥΖ) με even parity: P = X⊕Υ⊕Ζ (στο σημειο αποστολης) • Στο σημειο παραληψης: C = P⊕X⊕Υ⊕Ζ εαν το C ειναι 1 λαθος!

Ολοκληρωμενα Κυκλωματα • Ιntegrated Circuits – – – –

σημερα: απο transistors και συρματα σιλικονης περιεχεται σε ενα πλαστικο ή κεραμικο πακεττο. διασυνδεση με pins (10s-1000s) καθε ΙC μοναδικο κωδικα

• Eπιπεδα Ολοκληρωσης – SSI ~10,MSI ~100,LSI ~1000,VLSI 104-108

• Λογικες “Οικογενειες”: • RTL,DTL,TTL,ECL,MOS,CMOS,BiCMOS,GaAs

Xαρακτηρηστικα (ηλεκτρονικες ιδιοτητες) – FanΟut: ποσες inputs μπορει να ξεκινουν απο ενα output – Kαταναλωση ισχυος – Χρονος Μεταδοσης (propagation delay) tαλλαγη στο input - tαλλαγη στο output

Θετικη και Αρνητικη Λογικη

• Υποθετουμε θετικη λογικη

Περιληψη • • • • • •

Δυαδικη Λογικη και Πυλες Boolean Algebra Προτυπες Μορφες Απλοποιηση με Πινακες Πυλες ΝΑΝD,NOR και XOR Επιπεδα ολοκληρωσης