Λογική Σχεδίαση — Σεπτέμβριος 2023¶
Μεταγραφή από τις φωτογραφίες sel1.png, sel2.png και sel3.png της εξεταστικής Σεπτεμβρίου 2023.
sel1.png¶
Λογική Σχεδίαση — Εξεταστική Σεπτεμβρίου 2023 Διάρκεια εξέτασης: 140 λεπτά. Ελάχιστη Παραμονή: 90 λεπτά Οι απαντήσεις σας να δοθούν πάνω στις κόλλες των θεμάτων.
Ονοματεπώνυμο: Μάθημα: ΑΜ: Έτος σπουδών:
Θέμα 1 (1.5 μονάδες) Δίνεται η συνάρτηση F(Z, X, Y, E) = Σ(1, 2, 5, 6, 8, 14) που έχει αδιάφορη έξοδο για τους ελαχιστόρους 0, 4, 7 και 10. Να την απλοποιήσετε χρησιμοποιώντας χάρτη Karnaugh (συμπληρώστε τον πίνακα που σας δίνεται). Να γράψετε το τελικό αποτέλεσμα στο πλαίσιο κάτω από τον πίνακα. Να σχεδιάσετε την F με τον ελάχιστο αριθμό πυλών 2 εισόδων. Για κάθε σήμα έχετε διαθέσιμη και την ορθή και την ανάστροφη μορφή.
[Σχήμα: Χάρτης Karnaugh 4x4 με γραμμές ZX (00, 01, 11, 10) και στήλες YE (00, 01, 11, 10), και κενό ορθογώνιο πλαίσιο από κάτω]
Θέμα 2 (2 μονάδες) Δίνεται το κύκλωμα της παρακάτω εικόνας. Να συμπληρώσετε τον πίνακα.
[Σχήμα: Συνδυαστικό λογικό κύκλωμα με εισόδους b, c, a. Το c και b εισέρχονται σε πύλη XOR, η έξοδος της οποίας και το a εισέρχονται σε πύλη NOR με έξοδο F. Το c αντιστρέφεται με πύλη NOT και εισέρχεται σε πύλη AND μαζί με το a. Η έξοδος της AND και το a εισέρχονται σε πύλη XOR με έξοδο G.]
| a | c | b | G | F |
|---|---|---|---|---|
| 1 | 1 | |||
| 1 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 0 | |
| 1 | 0 | 0 |
sel2.png¶
Θέμα 3 (2 μονάδες) Να υλοποιήσετε την F (A, B, C, D) του παρακάτω λογικού διαγράμματος με: (1) έναν αποκωδικοποιητή και μία λογική πύλη 2 εισόδων, και (2) έναν πολυπλέκτη 4 → 1, έναν πολυπλέκτη 2 → 1 και έναν αντιστροφέα.
[Σχήμα: Λογικό διάγραμμα με δύο πύλες 2 εισόδων (μία με εισόδους A, B και μία με εισόδους C, D) των οποίων οι έξοδοι οδηγούνται σε τρίτη πύλη 2 εισόδων με έξοδο F. Ο τύπος της πύλης με εισόδους C, D είναι [δυσανάγνωστο] (φαίνεται XOR), ενώ η πύλη με εισόδους A, B και η τελική πύλη φαίνονται OR.]
Θέμα 4 (2.5 μονάδες) 1) Αναπτύξτε το κατά Mealy διάγραμμα μετάβασης καταστάσεων μιας μηχανής καταστάσεων η οποία να αναγνωρίζει αν μια ακολουθία εισόδου περιέχει ένα ‘1’ μετά τριάδες από ‘0’ και μετά ένα ‘1’. Κάθε φορά που αναγνωρίζεται η ακολουθία στην είσοδο, η έξοδος γίνεται U και σε κάθε άλλη περίπτωση η έξοδος είναι ‘X’. Για παράδειγμα η μηχανή πρέπει να αναγνωρίζει τις ακολουθίες 10001, 10000001, 10000000001, 100010001 αλλά όχι τις 101, 1001, 100001 και 1000001. (1.5 μονάδες)
sel3.png¶
2) Σχεδιάστε την έξοδο της μηχανής καταστάσεων του προηγούμενου ερωτήματος όταν δέχεται σαν είσοδο το σήμα INP. Η μηχανή καταστάσεων χρησιμοποιεί θετικά ακμοπυροδότητα D flip-flop. (1.0 μονάδα)
[Σχήμα: Κυματομορφές χρονισμού CLK (παλμοί ρολογιού) και INP (ακολουθία εισόδου) και γραμμή OUT με αρχική ακαθόριστη κατάσταση XX]
Θέμα 5 (2.5 μονάδες) 1) Θέλουμε να αντικαταστήσουμε ένα παράλληλο πολλαπλασιαστή AxB με μια ROM. Το A ∈ [0, 256] και B ∈ [0, 44]. Υπολογίστε ποιο είναι το μέγεθος της ROM που θα χρειαστεί σε kBytes. Υπολογίστε αναλυτικά τον αριθμό θέσεων και δυαδικά ψηφία ανά θέση. (1.0 μονάδα)
2) Δίνεται μια ROM με την ακόλουθη διασύνδεση που υλοποιεί την πράξη \(Z = X \cdot 2 + \lfloor Y/2 \rfloor\), όπου X και Y φυσικοί αριθμοί των 4-bit. Δώστε τα περιεχόμενα της μνήμης στις αντίστοιχες διευθύνσεις συμπληρώνοντας τον πίνακα. Εξηγείστε συνοπτικά πως συμπληρώσατε την πρώτη και τελευταία γραμμή του πίνακα. (1.5 μονάδες)
(Πρόχειρο)
[Σχήμα: ROM με διευθύνσεις X[0]->A0, Y[0]->A1, X[1]->A2, Y[1]->A3, X[2]->A4, Y[2]->A5, X[3]->A6, Y[3]->A7 και εξόδους D0->Z[0], D1->Z[1], D2->Z[2], D3->Z[3], D4->Z[4], D5->Z[5]]
| Διεύθυνση | Περιεχόμενο (σε δεκαεξαδικό) |
|---|---|
| \(01_{16}\) | |
| \(02_{16}\) | |
| \(03_{16}\) | |
| \(04_{16}\) | |
| \(BA_{16}\) | |
| \(BB_{16}\) | |
| \(CA_{16}\) | |
| \(CB_{16}\) | |
| \(E3_{16}\) | |
| \(EA_{16}\) | |
| \(EC_{16}\) | |
| \(FF_{16}\) |
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2023-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Σειρά μεταβλητών \(Z X Y E\) (\(Z\) MSB). Ελαχιστόροι 1,2,5,6,8,14, αδιάφοροι (d) 0,4,7,10.
Χάρτης (γραμμές \(ZX\) = 00,01,11,10 · στήλες \(YE\) = 00,01,11,10):
| ZX \ YE | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | d | 1 | 0 | 1 |
| 01 | d | 1 | d | 1 |
| 11 | 0 | 0 | 0 | 1 |
| 10 | 1 | 0 | 0 | d |
Πρώτοι συνεπαγόμενοι (με χρήση των d): \(X'E'\) (κελιά 0,2,8,10), \(YE'\) (ελαχ. 2,6,10,14) και \(Z'Y'\) (ελαχ. 0,1,4,5). Επιλέγονται και οι τρεις (χρειάζονται όλοι: το 8 μόνο από \(X'E'\), το 14 μόνο από \(YE'\), το 1 και το 5 μόνο από \(Z'Y'\)). Η επιλογή επαληθεύτηκε με πρόγραμμα (η ελάχιστη κάλυψη είναι μοναδική).
Υλοποίηση με πύλες 2 εισόδων (διαθέσιμες και οι δύο πολικότητες): 4 πύλες: \(g_1 = X' + Y\) (OR), \(g_2 = g_1\cdot E'\) (AND), \(g_3 = Z'\cdot Y'\) (AND), \(F = g_2 + g_3\) (OR). Δεν απέδειξα ότι 4 είναι το ελάχιστο (έλεγξα μόνο δέντρα χωρίς επαναχρησιμοποίηση μεταβλητής και βρέθηκε ότι 3 πύλες δεν αρκούν σε αυτή τη μορφή).
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Από το κύκλωμα: \(F = \overline{(c\oplus b) + a}\), \(G = a \oplus (c'a)\). Απλοποίηση: αν \(a=0\) τότε \(G=0\)· αν \(a=1\) τότε \(G = 1\oplus c' = c\). Άρα \(G = a\,c\).
Πλήρης πίνακας (υπολογίστηκε με πρόγραμμα):
| a | c | b | G | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |
Συμπλήρωση των γραμμών του θέματος: - 2η γραμμή (\(c=1,b=0\), \(G=0,F=0\)): \(G=0\) με \(c=1\) απαιτεί \(a=0\). a = 0 (επαληθεύεται \(F=0\)). - 3η γραμμή (\(a=1,b=1\), \(G=1\)): \(G=ac\) ⇒ \(c=1\). c = 1, και \(F=0\) ✓. - 4η γραμμή (\(a=1,c=0,b=0\)): G = 0, F = 0. - 1η γραμμή (\(G=1,F=1\)): αδύνατο με αυτό το κύκλωμα (\(G=1\) απαιτεί \(a=1\), οπότε \(F=0\)). Πιθανό λάθος μεταγραφής ή εκφώνησης· δεν δίνω τιμές.
Θέμα 3¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στην εικόνα sel2.png το λογικό διάγραμμα διακρίνεται καθαρά:
- Η άνω πύλη είναι πύλη OR 2 εισόδων με εισόδους \(A, B\), άρα έξοδο \(A + B\).
- Η κάτω πύλη είναι πύλη XOR 2 εισόδων (διακρίνεται καθαρά η διπλή καμπύλη γραμμή εισόδου) με εισόδους \(C, D\), άρα έξοδο \(C \oplus D\).
- Η τελική πύλη είναι πύλη OR 2 εισόδων, άρα η συνάρτηση εξόδου είναι:
$\(F(A, B, C, D) = (A + B) + (C \oplus D) = A + B + C \oplus D\)$
(1) Υλοποίηση με έναν αποκωδικοποιητή και μία λογική πύλη 2 εισόδων¶
Η συνάρτηση \(F\) είναι 0 μόνο όταν \(A = 0\), \(B = 0\) και \(C \oplus D = 0\). Για \(C \oplus D = 0\) έχουμε \((C, D) = (0, 0)\) ή \((C, D) = (1, 1)\). Συνεπώς, οι μοναδικοί ελαχιστόροι για τους οποίους \(F = 0\) είναι: - \(m_0 = A'B'C'D' = (0, 0, 0, 0)_2\) - \(m_3 = A'B'CD = (0, 0, 1, 1)_2\) Σε όλους τους υπόλοιπους 14 ελαχιστόρους η \(F\) ισούται με 1: \(F = \sum m(1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) = \prod M(0, 3)\).
- Χρησιμοποιούμε έναν αποκωδικοποιητή 4-σε-16 με εισόδους επιλογής \(A, B, C, D\) (όπου \(A\) το MSB).
- Αν ο αποκωδικοποιητής έχει ενεργές στο 1 (active-high) εξόδους: Εφόσον \(F = \overline{m_0 + m_3}\), συνδέουμε τις εξόδους \(m_0\) και \(m_3\) του αποκωδικοποιητή σε μία πύλη NOR 2 εισόδων, η έξοδος της οποίας δίνει την \(F\).
- Αν ο αποκωδικοποιητής έχει ενεργές στο 0 (active-low) εξόδους \(\overline{m_i}\): Εφόσον \(F = \overline{m_0 \cdot m_3}' = \overline{m_0} \cdot \overline{m_3}\), συνδέουμε τις εξόδους \(\overline{m_0}\) και \(\overline{m_3}\) σε μία πύλη AND 2 εισόδων, η έξοδος της οποίας δίνει την \(F\).
(2) Υλοποίηση με έναν πολυπλέκτη 4 → 1, έναν πολυπλέκτη 2 → 1 και έναν αντιστροφέα¶
- Χρησιμοποιούμε τον πολυπλέκτη 4 → 1 με γραμμές επιλογής τις μεταβλητές \(A, B\) (με \(S_1 = A, S_0 = B\)):
- Όταν \(AB = 01\) (\(I_1\)), \(A+B = 1 \implies F = 1\). Συνδέουμε \(I_1 = 1\) (λογικό '1' / Vcc).
- Όταν \(AB = 10\) (\(I_2\)), \(A+B = 1 \implies F = 1\). Συνδέουμε \(I_2 = 1\) (λογικό '1' / Vcc).
- Όταν \(AB = 11\) (\(I_3\)), \(A+B = 1 \implies F = 1\). Συνδέουμε \(I_3 = 1\) (λογικό '1' / Vcc).
- Όταν \(AB = 00\) (\(I_0\)), \(A+B = 0 \implies F = C \oplus D\).
- Για να παράγουμε τη συνάρτηση \(C \oplus D\) στην είσοδο \(I_0\), χρησιμοποιούμε τον πολυπλέκτη 2 → 1 και τον αντιστροφέα:
- Ορίζουμε γραμμή επιλογής του 2 → 1 πολυπλέκτη τη μεταβλητή \(C\) (\(S = C\)).
- Όταν \(C = 0\): \(C \oplus D = 0 \oplus D = D\). Συνδέουμε την είσοδο \(D_0 = D\).
- Όταν \(C = 1\): \(C \oplus D = 1 \oplus D = D'\). Χρησιμοποιούμε τον αντιστροφέα στην είσοδο \(D\) ώστε να οδηγήσουμε το \(D'\) στην είσοδο \(D_1\).
- Η έξοδος του πολυπλέκτη 2 → 1 είναι \(C' \cdot D + C \cdot D' = C \oplus D\), την οποία συνδέουμε απευθείας στην είσοδο δεδομένων \(I_0\) του πολυπλέκτη 4 → 1.
Θέμα 4¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στην εικόνα sel3.png διακρίνεται καθαρά το χρονικό διάγραμμα του Ερωτήματος 2:
- Υπάρχουν 14 κύκλοι ρολογιού CLK με θετικές ακμές ακμοπυροδότησης.
- Το σήμα εισόδου INP είναι σταθερό σε κάθε περίοδο ρολογιού και λαμβάνει κατά σειρά τις τιμές:
- Κύκλος 1: \(1\)
- Κύκλος 2: \(0\)
- Κύκλος 3: \(0\)
- Κύκλος 4: \(0\)
- Κύκλος 5: \(1\)
- Κύκλος 6: \(0\)
- Κύκλος 7: \(0\)
- Κύκλος 8: \(0\)
- Κύκλος 9: \(0\)
- Κύκλος 10: \(0\)
- Κύκλος 11: \(0\)
- Κύκλος 12: \(1\)
- Κύκλος 13: \(0\)
- Κύκλος 14: \(0\)
Η μηχανή Mealy του Ερωτήματος 1 αναγνωρίζει ένα '1', ακολουθούμενο από τριάδες μηδενικών (\(3k\) μηδενικά με \(k \ge 1\)), ακολουθούμενο από '1'.
- Στους κύκλους 1–5 εισέρχεται η ακολουθία \(10001\) (\(3\) μηδενικά). Στον κύκλο 5 εισέρχεται '1' μετά από ακριβώς 3 μηδενικά, άρα αναγνωρίζεται η ακολουθία και η έξοδος γίνεται U.
- Στους κύκλους 5–12 εισέρχεται η ακολουθία \(10000001\) (\(6 = 2 \times 3\) μηδενικά). Στον κύκλο 12 εισέρχεται '1' μετά από 6 μηδενικά, άρα αναγνωρίζεται ξανά η ακολουθία και η έξοδος γίνεται U.
- Σε όλους τους υπόλοιπους κύκλους η έξοδος είναι X.
Η έξοδος OUT για κάθε έναν από τους 14 κύκλους ρολογιού είναι αναλυτικά:
- Κύκλος 1 (INP = 1): OUT = X
- Κύκλος 2 (INP = 0): OUT = X
- Κύκλος 3 (INP = 0): OUT = X
- Κύκλος 4 (INP = 0): OUT = X
- Κύκλος 5 (INP = 1): OUT = U (αναγνώριση \(10001\))
- Κύκλος 6 (INP = 0): OUT = X
- Κύκλος 7 (INP = 0): OUT = X
- Κύκλος 8 (INP = 0): OUT = X
- Κύκλος 9 (INP = 0): OUT = X
- Κύκλος 10 (INP = 0): OUT = X
- Κύκλος 11 (INP = 0): OUT = X
- Κύκλος 12 (INP = 1): OUT = U (αναγνώριση \(10000001\))
- Κύκλος 13 (INP = 0): OUT = X
- Κύκλος 14 (INP = 0): OUT = X
Η κυματομορφή της εξόδου OUT παραμένει στο επίπεδο X συνεχώς, εκτός από τον 5ο και τον 12ο κύκλο όπου μεταβαίνει στο επίπεδο U.
Θέμα 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
1. \(A\in[0,256]\): 257 τιμές ⇒ 9 bit. \(B\in[0,44]\): 45 τιμές ⇒ 6 bit. Διεύθυνση 15 bit ⇒ \(2^{15}=32768\) θέσεις. Μέγιστο γινόμενο \(256\cdot44=11264\), και \(2^{13}<11264<2^{14}\) ⇒ 14 bit ανά θέση. Μέγεθος \(32768\cdot14=458752\) bit \(=57344\) bytes = 56 kBytes. (Αν χρησιμοποιούνταν μόνο οι έγκυρες \(257\cdot45=11565\) θέσεις, θα χρειαζόταν λιγότερη μνήμη, αλλά η κανονική διευθυνσιοδότηση δίνει 56 kB.)
2. Η διεύθυνση είναι \(A_7..A_0=Y_3X_3Y_2X_2Y_1X_1Y_0X_0\) (A0=X0, A1=Y0, A2=X1, …). Το \(Z=2X+\lfloor Y/2\rfloor\) είναι 6 bit (μέγιστο \(30+7=37\)). Για κάθε διεύθυνση αποκωδικοποιούμε \(X\) (bit στις άρτιες θέσεις) και \(Y\) (στις περιττές).
| Διεύθυνση | X | Y | Περιεχόμενο |
|---|---|---|---|
| 01 | 1 | 0 | 02 |
| 02 | 0 | 1 | 00 |
| 03 | 1 | 1 | 02 |
| 04 | 2 | 0 | 04 |
| BA | 4 | 15 | 0F |
| BB | 5 | 15 | 11 |
| CA | 8 | 11 | 15 |
| CB | 9 | 11 | 17 |
| E3 | 9 | 13 | 18 |
| EA | 8 | 15 | 17 |
| EC | 10 | 14 | 1B |
| FF | 15 | 15 | 25 |
Πρώτη γραμμή: \(01_{16}=0000\,0001\) ⇒ \(A_0=1\) ⇒ \(X_0=1\), όλα τα άλλα 0 ⇒ \(X=1,Y=0\) ⇒ \(Z=2\). Τελευταία γραμμή: \(FF\) ⇒ \(X=Y=15\) ⇒ \(Z=30+7=37=25_{16}\).