Σχεδιασμός Συστημάτων Ειδικού Σκοπού — Φεβρουάριος 2021¶
Μεταγραφή από το κείμενο του
FR.pdf, με έλεγχο της εικόνας της σελίδας. Η υπογραφή του διδάσκοντα δεν μεταγράφεται.
FR.pdf¶
Σχεδιασμός Συστημάτων Ειδικού Σκοπού Υπολογιστικά Συστήματα Ανοχής Ελαττωμάτων Εξέταση 5/2/2021 Διάρκεια εξέτασης : 120 + 20΄
Θέμα 1 (3,0 μονάδες)¶
Δίδεται η ακόλουθη υλοποίηση της F(A,B,C,D) :
[Σχήμα: κύκλωμα από πύλες NAND. Εισόδοι A, B σε πύλη με έξοδο E. Η E διακλαδώνεται σε L (προς πύλη με είσοδο D, έξοδος J), σε H (προς πύλη με έξοδο K) και σε G (προς πύλη με είσοδο C, έξοδος M). Η πύλη με είσοδο H και M έχει έξοδο K. Οι J και K οδηγούν την πύλη εξόδου με έξοδο F.]
A. Ποιος είναι ο αριθμός των απλών σφαλμάτων μόνιμης τιμής αυτού του κυκλώματος? (0,5 μονάδες)
B. Δώστε όλα τα πιθανά διανύσματα ελέγχου για καθένα από τα σφάλματα :
(α) Γραμμή H μόνιμα στο 1 (H s-a-1), (0,5 μονάδες)
(β) Γραμμή D μόνιμα στο 0 (D s-a-0), και (0,7 μονάδες)
(γ) Γραμμή K μόνιμα στο 0 (K s-a-0) (0,9 μονάδες)
Γ. Συμπτύξτε τα διανύσματα του υποερωτήματος (B.) σε ένα ελάχιστο σύνολο που να ανιχνεύει και τα 3 παραπάνω σφάλματα. (0,4 μονάδες)
Θέμα 2 (1,8 μονάδες)¶
- Κατασκευάστε τον διαχωρίσιμο κώδικα υπολοίπου ως προς 7 καθώς και τον διαχωρίσιμο κώδικα αντιθέτου υπολοίπου ως προς 3 για τους αριθμούς 0 έως 9. (0,9 μονάδες)
- Δώστε τις αναπαραστάσεις με δυαδικά ψηφία των ίδιων αριθμών σε αριθμητικό σύστημα υπολοίπων (RNS) με βάση {3, 4, 7}. (0,9 μονάδες)
Θέμα 3 (3,2 μονάδες)¶
Έστω κυκλικός κώδικας με γεννήτορα πολυώνυμο το \(G(X) = x^3 + x + 1\) και η κωδικοποιημένη σε μη διαχωρίσιμη μορφή λέξη : \(V(X)\) = msb → 1 1 1 0 0 0 1 0 ← lsb
Ζητούνται :
A. το κύκλωμα κωδικοποίησης για το δεδομένο G(X) (0,6 μονάδες)
B. το κύκλωμα αποκωδικοποίησης (0,6 μονάδες)
Γ. ο έλεγχος της ορθότητας της κωδικοποιημένης λέξης V(X) με :
- διαίρεση πολυωνύμων (0,6 μονάδες)
- εκτέλεση από το υλικό που σχεδιάσατε στο υποερώτημα (B.) (0,7 μονάδες)
Δ. η διαχωρίσιμη μορφή για την κωδικοποίηση της πληροφορίας \(D(X) = x^4 + x^3 + 1\). (0,7 μονάδες)
Θέμα 4 (2,0 μονάδες)¶
Πόσα αντίγραφα (modules) με σφάλματα μπορείτε να ανεχτείτε υιοθετώντας κάποια από τις παρακάτω τεχνικές :
- 5MR ?
- TMR με 2 αναπληρωματικά (spare) modules ? (O συνολικός αριθμός modules –λειτουργικά και αναπληρωματικά– είναι 5).
- Αυτοκάθαρσης (self – purging) με 5 modules ?
Εξηγήστε σύντομα (1 παράγραφο των 3 προτάσεων μέγιστο για) κάθε απάντησή σας επικεντρώνοντας στα υπέρ και τα κατά της κάθε τεχνικής.
Καλή επιτυχία
[Παραλείπεται: υπογραφή διδάσκοντα]
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2021-02.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):FR_feb_2021.pdf,orca-image-1905240536.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: λύση σε έξι σελίδες (FR_feb_2021.pdf), χωρίς ταυτοποιημένη πηγή (προέλευση άγνωστη)
Προσοχή
Θέμα 1 Β(α): η αιτιολόγηση «Θέτω H = 0 ⇒ A = B = 1 ⇒ L = 0, G = 0» δεν συνάδει με το σχήμα όπως περιγράφεται (η E διακλαδώνεται σε L και G, και η H προέρχεται από την E)· για A = B = 1 η E και άρα η H θα ήταν 1. Έλεγξε με το πρωτότυπο. Η μεταγραφή της λύσης έχει μερική αναγνωσιμότητα· τα σχήματα περιγράφονται μόνο ως «[Σχήμα: …]» και δεν ελέγχθηκαν από το πρωτότυπο.
Λύσεις — 2021-02¶
Λύση των Θεμάτων 1–4 της εξέτασης 5/2/2021, μεταγραφή με όραση· η αναγνωσιμότητα είναι μερική.
FR_feb_2021.pdf¶
Δίνεται το ακόλουθο κύκλωμα:
[Σχήμα: Λογικό κύκλωμα με εισόδους A, B σε πύλη AND με έξοδο E. Η E διακλαδώνεται σε L και G. Είσοδοι C και L σε πύλη NAND με έξοδο J. Είσοδοι G και C σε πύλη NAND με έξοδο M. Είσοδος H (από E) και M σε πύλη NAND με έξοδο K. Πύλη με εισόδους J, K και έξοδο F.]
Α. # απλών σφαλμάτων μόνιμης τιμής
\(12 \times 2 = 24\)
Β. Δώστε όλα τα πιθανά test sets για καθένα από τα παρακάτω:
α) H s-a-1
1) Θέτω \(H = 0 \Rightarrow A = B = 1 \Rightarrow L = 0, G = 0\)
2) Θέλω \(F = \bar{H}\)
\(K = \bar{H}\) και \(J = 1\)
\(M = 1\)
3) \(M = 1 \Rightarrow C = X\)
\(J = 1 \Rightarrow D = X\)
Άρα
| ABCD | G | G H s-a-1 |
| :---: | :---: | :---: |
| 1 1 X X | 0 | 1 |
β) D s-a-0
1) Θέτω \(D = 1\)
2) Θέλω \(F = D\)
\(J = \bar{D}\) και \(K = 1\)
3) \(J = \bar{D} \rightarrow L = 1 \rightarrow A = 1, B = 0\) ή \(A = 0, B = 0\) ή \(A = 0, B = 1\)
\(K = 1 \rightarrow M = 0 \Rightarrow C = 1\)
| ABCD | G | G D s-a-0 |
|---|---|---|
| 0 0 1 1 | 1 | 0 |
| 0 1 1 1 | 1 | 0 |
| 1 0 1 1 | 1 | 0 |
γ) K s-a-0 \(\rightarrow F = \bar{K} \rightarrow J = 1 \rightarrow D = 0\) ή \(D = 1\) και \(L = 0\)
\(K = 1 \rightarrow H = 0\) ή \(M = 0\)
| ABCD |
|---|
| X X 0 0 |
| 1 1 X X |
(Γ) Συμπτύξτε το Β σε ένα test set
\(\left. \begin{array}{l} 1 1 X X \text{ ελέγχει 1, 3} \\ 0 0 1 1 \text{ ελέγχει 2} \end{array} \right\} \begin{array}{l} ABCD \\ 1 1 0 0 \\ 0 0 1 1 \end{array}\)
Θέμα 2
• Κατασκευάστε τον διαχωρίσιμο κώδικα υπολοίπου ως προς 7 και τον διαχωρίσιμο αντίθετου υπολοίπου ως προς 3 για τους αριθμούς 0-9.
ως προς 7 \(\leadsto\) mod 7 \(\leadsto\) μέχρι 6 υπόλοιπο \(\rightarrow\) άρα χρειάζομαι 3 bits check bits.
reverse mod 3 \(\leadsto\) μέχρι 2 υπόλοιπο, 2 bits.
| Data | check mod 7 | reverse mod 3 |
|---|---|---|
| 0 0 0 0 | 0 0 0 | 1 1 |
| 0 0 0 1 | 0 0 1 | 1 0 |
| 0 0 1 0 | 0 1 0 | 0 1 |
| 0 0 1 1 | 0 1 1 | 1 1 |
| 0 1 0 0 | 1 0 0 | 1 0 |
| 0 1 0 1 | 1 0 1 | 0 1 |
| 0 1 1 0 | 1 1 0 | 1 1 |
| 0 1 1 1 | 0 0 0 | 1 0 |
| 1 0 0 0 | 0 0 1 | 0 1 |
| 1 0 0 1 | 0 1 0 | 1 1 |
RNS {3, 4, 7}
1 \(\rightarrow (1, 1, 1) \quad 01, 01, 001\)
2 \(\rightarrow (2, 2, 2) \quad 10, 10, 010\)
3 \(\rightarrow (0, 3, 3) \quad 00, 11, 011\)
4 \(\rightarrow (1, 0, 4) \quad 01, 00, 100\)
5 \(\rightarrow (2, 1, 5) \quad 10, 01, 101\)
6 \(\rightarrow (0, 2, 6) \quad 00, 10, 110\)
7 \(\rightarrow (1, 3, 0) \quad 01, 11, 000\)
8 \(\rightarrow (2, 0, 1) \quad 10, 00, 001\)
9 \(\rightarrow (0, 1, 2) \quad 00, 01, 010\)
Θέμα 3
\(G(x) = x^3 + x + 1 = x(x^2 + 1) + 1\)
\(V(x) = 1 1 1 0 0 0 1 0\)
Α) κύκλωμα κωδικοποίησης
[Σχήμα: κύκλωμα κωδικοποίησης με shift registers / flip-flops και πύλες XOR]
Β) κύκλωμα αποκωδικοποίησης
\(V(x) = G(x) D(x)\)
\(V(x) = D(x) \cdot x(x^2 + 1) + D(x)\)
\(D(x) = D(x) \cdot x(x^2 + 1) + V(x)\)
[Σχήμα: κύκλωμα αποκωδικοποίησης με flip-flops και πύλες XOR]
γ) Έλεγχος ορθότητας με διαίρεση πολ.
\(\begin{array}{l|l}
x^7 + x^6 + x^5 + x & x^3 + x + 1 \\
\cline{2-2}
x^7 + x^5 + x^4 & x^4 + x^3 + 1 \\
\hline
x^6 + x^4 + x & \\
x^6 + x^4 + x^3 & \\
\hline
x^3 + x & \\
x^3 + x + 1 & \\
\hline
1 &
\end{array}\)
\(\Rightarrow\) Λάθος \(R \neq 0\)
| T | FF1 | FF2 | FF3 | V(x) | D(x) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 2 | 1 | 0 | 0 | 0 | 1 |
| 3 | 1 | 1 | 0 | 0 | 1 |
| 4 | 1 | 1 | 1 | 0 | 0 |
| 5 | 0 | 1 | 1 | 1 | 0 |
| 6 | 0 | 0 | 1 | 1 | 0 |
| 7 | 0 | 0 | 0 | 1 | 1 |
| 8 | 1 | 0 | 0 |
\(\rightarrow\) Λάθος
δ) Διαχωρίσιμη μορφή
\(x^3 D(x) = x^7 + x^6 + x^3\)
\(\begin{array}{l|l}
x^7 + x^6 + x^3 & x^3 + x + 1 \\
\cline{2-2}
x^7 + x^5 + x^4 & x^4 + x^3 + x^2 + 1 \\
\hline
x^6 + x^5 + x^4 + x^3 & \\
x^6 + x^4 + x^3 & \\
\hline
x^5 & \\
x^5 + x^3 + x^2 & \\
\hline
x^3 + x^2 & \\
x^3 + x + 1 & \\
\hline
x^2 + x + 1 &
\end{array}\)
\(R(x) = x^2 + x + 1 = 1 1 1\)
Άρα η διαχωρίσιμη μορφή \(R(x) + x^3 D(x) = 1 1 0 0 1 \vdots 1 1 1\)
Πόσα modules με σφάλματα μπορείτε να ανιχνεύσετε στις παρακάτω περιπτώσεις:
• 5MR \(\rightarrow\) Έως 2 faulty modules
• TMR w. 2 spares \(\rightarrow\) 3 faulty αν όμως να μην χαλάσουν ταυτόχρονα. Αν και 2 modules χαλάσουν ταυτόχρονα θα έχουμε πάντα λάθος αποτέλεσμα
• Self-purging 5 modules: Μέχρι 3 faulty modules.
5MR: Έχω single POF (voter) και υπάρχει σοβαρή μεγάλη χρονική καθυστέρηση και κόστος σε υλικό. Είναι η πιο φτηνή υλοποίηση από τις επιλογές.
TMR + spares: Ακριβή υλοποίηση, σε περίπτωση 2 faulty modules ταυτόχρονα παίρνω μόνιμα λάθος τιμή άρα ανεπανόρθωτη.
Self-purging: Ακριβή υλοποίηση, πιο γρήγορη.