Σχεδιασμός Συστημάτων Ειδικού Σκοπού — Φεβρουάριος 2011¶
Μεταγραφή της φωτογραφίας
2011.jpg(εκτύπωση εξεταστικής κόλλας).
2011.jpg¶
Σχεδιασμός Συστημάτων Ειδικού Σκοπού Εξετάσεις Φεβρουαρίου 2011
Διάρκεια Εξέτασης : 150′
Θέμα 1
Ποιος είναι ο ελάχιστος αριθμός δυαδικών ψηφίων ελέγχου (check bits) που πρέπει να προστεθούν σε μήνυμα μήκους \(k\) δυαδικών ψηφίων ώστε να υπάρχει η δυνατότητα διόρθωσης ενός ή δύο απλών λαθών; Αποδείξτε τον ισχυρισμό σας. Πόση είναι η επιβάρυνση που προκαλεί ο κώδικας όταν \(k = 7\); (2,5 μονάδες)
Θέμα 2
Σχεδιάστε με όση λεπτομέρεια κρίνετε απαραίτητη έναν προσθετή 8 δυαδικών ψηφίων χρησιμοποιώντας τη τεχνική RESWO. Υπολογίστε την επιβάρυνση σε υλικό που απαιτεί η υιοθέτηση αυτής της τεχνικής θεωρώντας ότι κάθε πολυπλέκτης από δύο δυαδικά ψηφία σε ένα απαιτεί υλικό ίσο με το 1% του προσθετή, η αποθήκευση ενός δυαδικού ψηφίου απαιτεί 2% του υλικού του προσθετή και η σύγκριση δύο δυαδικών ψηφίων απαιτεί 1% του υλικού του προσθετή. Τέλος, εντοπίστε τυχόν απλά λάθη στην RESWO δομή τα οποία ΔΕΝ ανιχνεύονται και προτείνετε βελτιώσεις / αλλαγές. (2,5 μονάδες)
Θέμα 3
Για την κωδικοποίηση σε κυκλικό κώδικα και με δεδομένο το γεννήτορα πολυώνυμο \(G(X) = x^5 + x^2 + 1\),
- Σχεδιάστε :
- το κύκλωμα κωδικοποίησης και
- το κύκλωμα αποκωδικοποίησης.
- Δείξτε την κωδικοποίηση για την πληροφορία που παριστάνεται από το πολυώνυμο \(x^3 + 1\) ακολουθώντας :
- πολ/σμό πολυωνύμων και
- την εκτέλεση από το υλικό που σχεδιάσατε.
- Δώστε τη μορφή της κωδικοποιημένης πληροφορίας σε διαχωρίσιμη μορφή και
- Ελέγξτε την ορθότητα της πληροφορίας : MSB → 10011001 ← LSB.
(3,0 μονάδες)
Θέμα 4
Σε ένα RNS με βάση τα υπόλοιπα \(\{13, 11, 7, 5, 2\}\) ποιο είναι το εύρος της αναπαράστασης; Πώς αναπαρίστανται στο σύστημα αυτό οι \(137_{10}\) και \(26_{10}\) με δυαδικά ψηφία; Δείξτε τη διαδικασία πρόσθεσής τους. Πώς μπορείτε να αυξήσετε τις ικανότητες ανίχνευσης λαθών σε αυτό το σύστημα με το ελάχιστο δυνατό κόστος; Δώστε αναλυτικά τις νέες αναπαραστάσεις και δείξτε την νέα διαδικασία πρόσθεσης.
(2,0 μονάδες)
Καλή επιτυχία
[όνομα και υπογραφή διδάσκοντα παραλείφθηκαν]
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2011-02¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια
Ερμηνεύω αρχικά την απαίτηση ως τη συνήθη SEC-DED: διόρθωση ενός απλού λάθους και ανίχνευση δύο απλών λαθών. Αν χρησιμοποιηθούν \(r\) συνολικά ψηφία ελέγχου, τότε \(n=k+r\) και απαιτείται [ 2^{r-1}\ge k+r. ] Πράγματι, τα \(r-1\) ψηφία δίνουν \(2^{r-1}\) συνδρομές Hamming· χρειάζονται μη μηδενικές και διακριτές συνδρομές για τις \(n=k+r\) θέσεις, ενώ το επιπλέον bit συνολικής ισοτιμίας διακρίνει τα δύο λάθη από τα ένα. Για \(k=7\): [ r=4:\quad 2^{3}=8<7+4=11, ] [ r=5:\quad 2^{4}=16\ge 7+5=12. ] Άρα ελάχιστος αριθμός check bits είναι \(r=5\), με κωδική λέξη μήκους \(n=12\). Η επιβάρυνση είναι [ \frac{r}{k}=\frac{5}{7}\approx71.4\%, ] ή ως προς το συνολικό μήκος \(\frac{5}{12}\approx41.7\%\).
Αν το ζητούμενο ερμηνευθεί κατά γράμμα ως διόρθωση έως δύο απλών λαθών, τότε απαιτείται \(d_{\min}\ge5\) και ισχύει το φράγμα σφαιρικής κάλυψης [ 2^r\ge \sum_{i=0}^{2}\binom{k+r}{i}. ] Για \(k=7\), \(r=6\) δίνει \(64<92\), ενώ \(r=7\) δίνει \(128\ge106\), άρα \(r=7\) (π.χ. με κώδικα \([14,7,5]\)), με επιβάρυνση \(100\%\). Αν χρησιμοποιηθεί ο γνωστός BCH \([15,7,5]\), τότε \(r=8\) και η επιβάρυνση είναι \(8/7\approx114.3\%\).
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια
Έστω 8-bit προσθετής \(S=A+B\), κόστους \(100\%\). Στο RESWO γίνονται δύο φάσεις.
-
Υπολογίζεται το κανονικό άθροισμα [ S^{(1)}=(A+B)\bmod 2^8 ] και αποθηκεύεται σε καταχωρητή 8 bits.
-
Γίνεται επανυπολογισμός με ολισθημένους τελεστές: [ A^{(2)}=A\ll1=[A_6A_5\cdots A_0\,0],\qquad B^{(2)}=B\ll1=[B_6B_5\cdots B_0\,0], ] υπολογίζεται \(S^{(2)}=A^{(2)}+B^{(2)}\), ολισθαίνεται δεξιά κατά μία θέση και συγκρίνεται με το \(S^{(1)}\). Η επιλογή κανονικών/ολισθημένων bit γίνεται με 2-to-1 πολυπλέκτες: 8 για το \(A\), 8 για το \(B\), δηλαδή 16 πολυπλέκτες. Χρειάζονται επίσης καταχωρητές 8 bits για κάθε τελεστή και 8 bits για το πρώτο άθροισμα, δηλαδή \(8+8+8=24\) bits αποθήκευσης. Η σύγκριση των 8 bits απαιτεί 8 bit-συγκριτές.
Επιβάρυνση: [ \text{MUX}:16\cdot1\%=16\%, ] [ \text{Αποθήκευση}:24\cdot2\%=48\%, ] [ \text{Σύγκριση}:8\cdot1\%=8\%. ] Συνολική επιβάρυνση: [ 16\%+48\%+8\%=72\%. ] Δηλαδή ο νέος προσθετής κοστίζει \(172\%\) του αρχικού. Αν οι καταχωρητές εισόδου \(A,B\) θεωρηθούν ήδη υπάρχοντες, η πρόσθετη επιβάρυνση είναι \(16\%+16\%+8\%=40\%\).
Απλά λάθη που δεν ανιχνεύονται: - Με απλή αριστερή ολίσθηση 8 bits χάνονται το πιο σημαντικό bit του αθροίσματος και το carry-out· άρα μόνιμο σφάλμα στο MSB ή στο carry μπορεί να μην ελεγχθεί. - Σφάλματα στους πολυπλέκτες, στους καταχωρητές, στη λογική ολίσθησης και στον συγκριτή δεν καλύπτονται από την τεχνική, αφού το RESWO ελέγχει μόνο τον προσθετή. - Σφάλματα που επιδρούν ταυτόσημα και στις δύο εκτελέσεις μπορεί να μην αλλάξουν τη σύγκριση.
Βελτιώσεις: χρήση \(9\)-bit προσθετή ή διατήρηση/έλεγχος του carry-out, κυκλική ολίσθηση ή ισοτιμία για το MSB, self-checking/διπλασιασμός της λογικής ελέγχου και εναλλαγή διαφορετικών ολισθήσεων μεταξύ των δύο εκτελέσεων.
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: μέτρια
Έχουμε [ G(X)=X^5+X^2+1,\qquad r=5, ] και πληροφορία [ M(X)=X^3+1. ]
Κωδικοποίηση με πολλαπλασιασμό πολυωνύμων (μη συστηματική)¶
[ C_{\rm ns}(X)=M(X)G(X) =(X^3+1)(X^5+X^2+1). ] Υπολογίζοντας modulo 2, [ C_{\rm ns}(X)=X^8+X^3+X^2+1. ] Σε δυαδικά ψηφία, από MSB προς LSB: [ 100001101. ]
Κυκλωμα κωδικοποίησης¶
Χρησιμοποιείται συστηματικός κωδικοποιητής με καταχωρητή 5 θέσεων \(q_4q_3q_2q_1q_0\), ο οποίος εκτελεί διαίρεση με το \(G(X)\). Με \(t=q_4\) και εισερχόμενο bit \(d\): [ q_4^+=q_3,\quad q_3^+=q_2,\quad q_2^+=q_1\oplus t,\quad q_1^+=q_0,\quad q_0^+=d\oplus t. ] Τα bits πληροφορίας εισέρχονται από το MSB προς το LSB, δηλαδή \(1,0,0,1\), και στη συνέχεια εισάγονται πέντε μηδενικά για τον υπολογισμό του υπολοίπου. Η ακολουθία καταστάσεων \(q_4q_3q_2q_1q_0\) είναι: [ 00000\to00001\to00010\to00100\to01001 \to10010\to00001\to00010\to00100\to01000. ] Άρα το υπόλοιπο είναι [ R(X)=X^3, ] ή ως check bits \(q_4q_3q_2q_1q_0=01000\).
Συστηματική/διαχωρίσιμη μορφή¶
[ X^5M(X)=X^8+X^5. ] Εκτελώντας διαίρεση: [ X^8+X^5=X^3(X^5+X^2+1)+X^3. ] Άρα [ C_{\rm sys}(X)=X^5M(X)+R(X)=X^8+X^5+X^3. ] Η συστηματική κωδική λέξη είναι [ \underbrace{1001}{\text{πληροφορία}}\;\underbrace{01000}, ] δηλαδή [ C_{\rm sys}=100101000. ]}
Κυκλωμα αποκωδικοποίησης¶
Χρησιμοποιείται το ίδιο κύκλωμα διαίρεσης με το \(G(X)\). Τα λαμβανόμενα bits εισέρχονται από το MSB προς το LSB. Μετά από όλες τις ολισθήσεις, ο καταχωρητής \(q_4q_3q_2q_1q_0\) περιέχει το σύνδρομο [ S(X)=R_{\rm rec}(X)\bmod G(X). ] Αν \(S(X)=0\), η λέξη είναι δεκτή· αν \(S(X)\ne0\), ανιχνεύεται λάθος. Για διόρθωση ενός λάθους, το σύνδρομο συγκρίνεται με πίνακα συνδρόμων \(X^i\bmod G(X)\) και διορθώνεται η αντίστοιχη θέση.
Έλεγχος της ακολουθίας \(10011001\)¶
Με MSB προς LSB: [ R_{\rm rec}(X)=X^7+X^4+X^3+1. ] Διαιρώντας με \(G(X)\): [ X^7+X^4+X^3+1=X^2G(X)+(X^3+X^2+1). ] Άρα [ S(X)=X^3+X^2+1\ne0, ] οπότε η λέξη δεν είναι έγκυρη κωδική λέξη. Επειδή [ X^8\bmod G(X)=X^3+X^2+1, ] αν ερμηνευθεί ως (31,26) Hamming και υποτεθεί ένα μόνο λάθος, το σφάλμα βρίσκεται στη θέση \(X^8\)· η διορθωμένη λέξη είναι \(X^8+X^7+X^4+X^3+1\), δηλαδή \(110011001\) (με μηδενικά υψηλότερης τάξης αν πρόκειται για 31-bit κώδικα). Σημειώνεται ότι η δοθείσα ακολουθία έχει μήκος 8, ενώ η συστηματική κωδική λέξη του \(X^3+1\) είναι 9 bits.
Θέμα 4¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Οι βάσεις είναι [ {m_{13},m_{11},m_7,m_5,m_2}={13,11,7,5,2}. ] Το εύρος αναπαράστασης είναι [ M=13\cdot11\cdot7\cdot5\cdot2=10010. ] Άρα αναπαρίστανται οι ακέραιοι \(0,\ldots,10009\) (ή προσημασμένα περίπου \(\pm5005\)).
Αναπαράσταση του \(137_{10}\)¶
[ 137\bmod13=7,\quad 137\bmod11=5,\quad 137\bmod7=4,\quad 137\bmod5=2,\quad 137\bmod2=1. ] Άρα [ 137_{10}=(7,5,4,2,1){13,11,7,5,2}. ] Με πλάτη \(4,4,3,3,1\) bits: [ 137=0111\,|\,0101\,|\,100\,|\,010\,|\,1. ]
Αναπαράσταση του \(26_{10}\)¶
[ 26\bmod13=0,\quad 26\bmod11=4,\quad 26\bmod7=5,\quad 26\bmod5=1,\quad 26\bmod2=0. ] Άρα [ 26_{10}=(0,4,5,1,0), ] δηλαδή [ 26_{10}=0000\,|\,0100\,|\,101\,|\,001\,|\,0. ]
Πρόσθεση¶
Η πρόσθεση στο RNS γίνεται ψηφίο προς ψηφίο modulo τη βάση: [ (7,5,4,2,1)+(0,4,5,1,0) =(7,9,2,3,1). ] Πράγματι \(137+26=163\) και [ 163\bmod13=7,\quad 163\bmod11=9,\quad 163\bmod7=2,\quad 163\bmod5=3,\quad 163\bmod2=1. ] Άρα [ 163_{10}=(7,9,2,3,1), ] ή [ 163_{10}=0111\,|\,1001\,|\,010\,|\,011\,|\,1. ]
Αύξηση ικανότητας ανίχνευσης λαθών με ελάχιστο κόστος¶
Για να ανιχνεύονται αξιόπιστα όλα τα απλά λάθη σε ένα υπόλοιπο, προστίθεται ένα redundant modulus \(m_r\) μεγαλύτερο από όλες τις υπάρχουσες βάσεις. Ο μικρότερος πρώτος μεγαλύτερος του \(13\) είναι [ m_r=17. ] Χρειάζονται \(\lceil\log_2 17\rceil=5\) bits επιπλέον. Το πληροφοριακό εύρος παραμένει \(M=10010\), ενώ το εκτεταμένο γινόμενο για έλεγχο είναι \(10010\cdot17=170170\).
Νέα υπόλοιπα: [ 137\bmod17=1,\qquad 26\bmod17=9,\qquad 163\bmod17=10. ] Έτσι: [ 137_{10}=(7,5,4,2,1,1), ] [ 26_{10}=(0,4,5,1,0,9). ] Σε δυαδικά ψηφία: [ 137_{10}=0111\,|\,0101\,|\,100\,|\,010\,|\,1\,|\,00001, ] [ 26_{10}=0000\,|\,0100\,|\,101\,|\,001\,|\,0\,|\,01001. ] Η νέα πρόσθεση γίνεται ως [ (7,5,4,2,1,1)+(0,4,5,1,0,9) =(7,9,2,3,1,10), ] δηλαδή [ 163_{10}=0111\,|\,1001\,|\,010\,|\,011\,|\,1\,|\,01010. ] Ο redundant όρος \(10\bmod17\) χρησιμοποιείται ως έλεγχος συμβατότητας· αν το προκύπτον redundant υπόλοιπο διαφέρει από το αναμενόμενο, εντοπίζεται λάθος. Αν ζητείται απλώς η ελάχιστη δυνατή πρόσθετη υλολογία χωρίς εγγύηση ανίχνευσης όλων των απλών λαθών, θα μπορούσε να προστεθεί \(m_r=3\) (2 bits), αλλά τότε η ανίχνευση δεν είναι πλήρης για όλες τις βάσεις.