3. Πολλαπλασιασμός των πιθανοτήτων ανεξάρτητων κοινών γεγονότων

4. Εύρεση του μέσου όρου για τις τιμές των τυχαίων ανεξάρτητων μεταβλητών

5. Η έννοια της υπό όρους πιθανότητας

6. Γενικός τύπος για την πιθανότητα να συμβούν γεγονότα

7. Γενικός τύπος για την πιθανότητα του αθροίσματος των γεγονότων

Διάλεξη 3. Η έννοια της εντροπίας

1. Η εντροπία ως μέτρο αβεβαιότητας

2. Ιδιότητες της εντροπίας

3. Εντροπία υπό όρους

Διάλεξη 4. Εντροπία και πληροφορίες

1. Ογκομετρική προσέγγιση για τη μέτρηση του όγκου των πληροφοριών

2. Προσέγγιση εντροπίας για τη μέτρηση του όγκου των πληροφοριών

Διάλεξη 5. Πληροφορίες και αλφάβητο

Διάλεξη 6. Δήλωση του προβλήματος κωδικοποίησης. Το πρώτο θεώρημα του Shannon.

Διάλεξη 7. Μέθοδοι κατασκευής δυαδικών κωδίκων. Αλφαβητική ανομοιόμορφη δυαδική κωδικοποίηση με σήματα ίσης διάρκειας. Κωδικοί προθέματος.

1. Δήλωση του προβλήματος βελτιστοποίησης της ανομοιόμορφης κωδικοποίησης

2. Ανομοιόμορφος κωδικός με οριοθέτη

3. Κωδικοί χωρίς διαχωριστικό. Κατάσταση Fano

4. Κωδικός προθέματος Shannon–Fano

5. Κωδικός προθέματος Huffman

Διάλεξη 8. Μέθοδοι κατασκευής δυαδικών κωδίκων. Αλλες επιλογές

1. Ομοιόμορφη αλφαβητική δυαδική κωδικοποίηση. Κωδικός byte

2. Διεθνή συστήματα κωδικοποίησης byte για δεδομένα κειμένου. Καθολικό σύστημα κωδικοποίησης δεδομένων κειμένου

3. Αλφαβητική κωδικοποίηση με άνιση διάρκεια στοιχειωδών σημάτων. κώδικας Μορς

4. Αποκλεισμός δυαδικής κωδικοποίησης

5. Κωδικοποίηση γραφικών δεδομένων

6. Κωδικοποίηση ηχητικών πληροφοριών

Διάλεξη 9. Αριθμητικά συστήματα. Αναπαράσταση αριθμών σε διαφορετικά συστήματα αριθμών. Μέρος 1

1. Αριθμητικά συστήματα

2. Σύστημα δεκαδικών αριθμών

3. Δυαδικό σύστημα αριθμών

4. Συστήματα αριθμών 8 και 16

5. Συστήματα μικτών αριθμών

6. Η έννοια της οικονομίας ενός συστήματος αριθμών

Διάλεξη 10. Αριθμητικά συστήματα. Αναπαράσταση αριθμών σε διαφορετικά συστήματα αριθμών. Μέρος 2ο.

1. Η εργασία μετατροπής ενός αριθμού από ένα σύστημα αριθμών σε άλλο

2. Μετατροπή q  p ακεραίων

3. Μετατροπή p  q ακεραίων

4. Μετατροπή p  q κλασματικών αριθμών

6. Μετατροπή αριθμών μεταξύ διψήφιων, 8ψήφιων και δεκαεξαδικών συστημάτων αριθμών

Διάλεξη 11. Κωδικοποίηση αριθμών σε υπολογιστή και λειτουργίες σε αυτούς

1. Κανονικοί αριθμοί

2. Μετατροπή ενός αριθμού από τη φυσική του μορφή στην κανονικοποιημένη του μορφή

3. Μετατροπή κανονικοποιημένων αριθμών

4. Κωδικοποίηση και επεξεργασία ανυπόγραφων ακεραίων

5. Κωδικοποίηση και επεξεργασία υπογεγραμμένων ακεραίων

6. Κωδικοποίηση και επεξεργασία πραγματικών αριθμών

Διάλεξη 12. Μετάδοση πληροφοριών μέσω γραμμών επικοινωνίας

1. Γενικό σχήμα μετάδοσης πληροφοριών σε γραμμή επικοινωνίας

2. Χαρακτηριστικά καναλιού επικοινωνίας

3. Επίδραση του θορύβου στη χωρητικότητα του καναλιού

Διάλεξη 13. Διασφάλιση της αξιοπιστίας της μεταφοράς πληροφοριών.

1. Δήλωση του προβλήματος της διασφάλισης της αξιοπιστίας μετάδοσης

2. Κωδικοί που εντοπίζουν ένα μόνο σφάλμα

3. Κωδικοί που διορθώνουν ένα μόνο λάθος

Διάλεξη 14. Μέθοδοι μετάδοσης πληροφοριών σε γραμμές επικοινωνίας υπολογιστή

1. Παράλληλη μεταφορά δεδομένων

2. Σειριακή μετάδοση δεδομένων

3. Επικοινωνία ηλεκτρονικών υπολογιστών μέσω τηλεφωνικών γραμμών

Διάλεξη 15. Ταξινόμηση δεδομένων. Αναπαράσταση δεδομένων στη μνήμη του υπολογιστή

1. Ταξινόμηση δεδομένων

2. Αναπαράσταση στοιχειωδών δεδομένων στη μνήμη RAM

Διάλεξη 16. Ταξινόμηση δομών δεδομένων

1. Ταξινόμηση και παραδείγματα δομών δεδομένων

2. Η έννοια της λογικής σημειογραφίας

Διάλεξη 17. Οργάνωση δομών δεδομένων στη μνήμη RAM και σε εξωτερικά μέσα

1. Οργάνωση δομών δεδομένων στη μνήμη RAM

2. Ιεραρχία δομών δεδομένων σε εξωτερικά μέσα

3. Χαρακτηριστικά των συσκευών αποθήκευσης

Ερωτήσεις ελέγχου

Βιβλιογραφία

3. Κωδικοί χωρίς διαχωριστικό. Κατάσταση Fano

Έχοντας εξετάσει μία από τις παραλλαγές της δυαδικής ανομοιόμορφης κωδικοποίησης, ας προσπαθήσουμε να βρούμε μια απάντηση στην ακόλουθη ερώτηση: είναι δυνατή μια τέτοια κωδικοποίηση χωρίς τη χρήση οριοθέτων;

Η ουσία αυτού του προβλήματος είναι να βρεθεί μια επιλογή κωδικοποίησης μηνύματος στην οποία η επακόλουθη επιλογή κάθε μεμονωμένου χαρακτήρα από το μήνυμα (δηλαδή η αποκωδικοποίηση) αποδεικνύεται σαφής χωρίς ειδικούς δείκτες για τον διαχωρισμό χαρακτήρων.

Οι απλούστεροι και πιο συχνά χρησιμοποιούμενοι κωδικοί χωρίς διαχωριστικό είναι οι λεγόμενοι κωδικούς προθέματος , που πληρούν την ακόλουθη προϋπόθεση - Κατάσταση Fano:Ένα μήνυμα που κωδικοποιείται χρησιμοποιώντας έναν μη ομοιόμορφο κωδικό μπορεί να αποκωδικοποιηθεί ξεκάθαρα εάν κανένας από τους κωδικούς στο μήνυμα δεν ταιριάζει με το πρόθεμα * (αρχή) κάποιου άλλου μεγαλύτερου κώδικα.

Για παράδειγμα, εάν υπάρχει κωδικός 110, τότε οι κωδικοί 1, 11, 1101, 110101 κ.λπ. δεν μπορούν πλέον να χρησιμοποιηθούν.

Εάν η συνθήκη του Fano ικανοποιείται, τότε κατά την ανάγνωση (αποκωδικοποίηση, αποκρυπτογράφηση) ενός κωδικοποιημένου μηνύματος συγκρίνοντάς το με έναν πίνακα κωδικών, μπορείτε πάντα να υποδείξετε ακριβώς πού τελειώνει ένας κωδικός και ξεκινά ένας άλλος.

Παράδειγμα 1. Οι κωδικοί παρουσιάζονται στον πίνακα; 4, πρόθεμα; Οι κωδικοί που παρουσιάζονται στον πίνακα. Τα 4 δεν είναι πρόθεμα. Δείτε, για παράδειγμα, τους κωδικούς των γραμμάτων «O» και «E», «A» και «N», «S» και «M», «D» και «Ch».

Παράδειγμα 2. Υπάρχει ένας πίνακας κωδικών προθεμάτων (Πίνακας 6). Πρέπει να αποκωδικοποιήσετε το ακόλουθο μήνυμα κωδικοποιημένο χρησιμοποιώντας αυτόν τον πίνακα κωδικών:

00100010000111010101110000110

Τραπέζι 6. Πίνακας κωδικών προθεμάτων

Η αποκωδικοποίηση πραγματοποιείται επαναλαμβάνοντας κυκλικά τα ακόλουθα βήματα:

«Κόψτε» το σύμβολο που βρίσκεται στο αριστερό μέρος από το τρέχον μήνυμα, επισυνάψτε το στα δεξιά στην τρέχουσα κωδική λέξη.

συγκρίνετε το ρεύμα μια κωδική λέξημε πίνακα κωδικών? εάν δεν υπάρχει αντιστοιχία, επιστρέψτε στο βήμα 1.

Χρησιμοποιώντας τον πίνακα κωδικών, αντιστοιχίστε την τρέχουσα κωδική λέξη με έναν χαρακτήρα του κύριου αλφαβήτου.

Ελέγξτε εάν υπάρχουν άλλοι χαρακτήρες στο κωδικοποιημένο μήνυμα. αν ναι, τότε μεταβείτε στο σημείο 1.

Εφαρμογή αυτού του αλγορίθμουστο κωδικοποιημένο μήνυμα που προτείνεται παραπάνω δίνει:

00100010000111010101110000110

Έτσι, έχοντας ολοκληρώσει τη διαδικασία αποκωδικοποίησης, μπορείτε να λάβετε το μήνυμα: «μητέρα του σαπουνιού πλαίσιο."

Έτσι, η χρήση της κωδικοποίησης προθέματος επιτρέπει στο μήνυμα να είναι πιο σύντομο επειδή δεν υπάρχει ανάγκη μετάδοσης διαχωριστών χαρακτήρων.

Ωστόσο, η συνθήκη Fano δεν καθορίζει συγκεκριμένο τρόπο σχηματισμού κωδικού προθέματος, αφήνοντας το πεδίο για τη δραστηριότητα ανάπτυξης του καλύτερου δυνατού κωδικού προθέματος.

4. Κωδικός προθέματος Shannon–Fano

Ας εξετάσουμε την επιλογή κωδικοποίησης που προτάθηκε το 1948 - 1949. ανεξάρτητα από τους K. Shannon και R. Fano.

Ας εξετάσουμε το σχήμα κωδικοποίησης Shannon–Fano (πώς κατασκευάζεται) ως εξής: παράδειγμα .

Ας υπάρχει ένα πρωτεύον αλφάβητο που αποτελείται από έξι χαρακτήρες: , Οπου
. Έστω οι πιθανότητες εμφάνισης αυτών των ζωδίων σε μηνύματα ως εξής:
,
,
,
,
Και
. Ας τακτοποιήσουμε αυτά τα ζώδια στον πίνακα με φθίνουσα σειρά πιθανοτήτων.

Ας χωρίσουμε τα ζώδια σε δύο ομάδες έτσι ώστε τα αθροίσματα των πιθανοτήτων σε καθεμία από αυτές τις δύο ομάδες να είναι περίπου ίσα. Στην περίπτωση αυτή, η 1η ομάδα θα περιλαμβάνει Και , και τα υπόλοιπα - στη 2η ομάδα. Σημάδια Ας αντιστοιχίσουμε το πρώτο αριστερό ψηφίο των κωδικών τους στην πρώτη ομάδα ως «0» και ας είναι το πρώτο αριστερό ψηφίο των κωδικών συμβόλων της δεύτερης ομάδας «1».

Ας συνεχίσουμε να διαιρούμε κάθε μία από τις προκύπτουσες ομάδες σε υποομάδες σύμφωνα με το ίδιο σχήμα, δηλαδή, έτσι ώστε τα αθροίσματα των πιθανοτήτων σε κάθε βήμα και στις δύο υποομάδες της διαχωριστικής ομάδας να είναι όσο το δυνατόν πιο κοντά. Έτσι, θα λάβουμε τα ακόλουθα bits κωδικών χαρακτήρων ένα προς ένα . Θα αντιστοιχίσουμε αυτά τα επόμενα ψηφία στα δεξιά στα υπάρχοντα.

Ολόκληρη αυτή η διαδικασία μπορεί να απεικονιστεί σχηματικά στον Πίνακα 7.

Τραπέζι 7. Κατασκευή του κώδικα Shannon-Fano

Σημάδι		Κωδικοί αριθμοί

Μπορεί να φανεί ότι οι κατασκευασμένοι κωδικοί χαρακτήρων ικανοποιεί τη συνθήκη Fano, επομένως, αυτή η κωδικοποίηση είναι πρόθεμα.

Ας βρούμε το μέσο μήκος του κώδικα που προκύπτει χρησιμοποιώντας τον τύπο

,

Οπου – τον ​​αριθμό των bit (χαρακτήρων) στον κωδικό που αντιστοιχεί στο σύμβολο .

Από τον πίνακα είναι ξεκάθαρο ότι
,
,
.

Έτσι παίρνουμε:

Έτσι για να κωδικοποιήσουμε έναν χαρακτήρα πρωταρχικό αλφάβητο απαιτούσε κατά μέσο όρο 2,45 χαρακτήρες του δευτερεύοντος (δυαδικού) αλφαβήτου.

Ας προσδιορίσουμε τη μέση ποσότητα πληροφοριών ανά χαρακτήρα του κύριου αλφαβήτου ως πρώτη προσέγγιση (λαμβάνοντας υπόψη τη διαφορετική πιθανότητα εμφάνισης αυτών των χαρακτήρων στα μηνύματα). Ας εφαρμόσουμε τον τύπο του Shannon:

.

Ας βρούμε τον πλεονασμό του ληφθέντος δυάδικος κώδικας:

,

δηλαδή ο πλεονασμός είναι περίπου 2,5.

Ας μάθουμε αν ο κώδικας που προκύπτει είναι ο βέλτιστος. Υπάρχουν 6 μηδενικά στους κωδικούς που ελήφθησαν και 11 ένα. Έτσι, οι πιθανότητες εμφάνισης του 0 και του 1 απέχουν πολύ από το να είναι ίσες. Επομένως, ο κώδικας που προκύπτει δεν μπορεί να θεωρηθεί βέλτιστος.

Το μάθημα είναι αφιερωμένο στον τρόπο επίλυσης της εργασίας 5 της Ενιαίας Κρατικής Εξέτασης στην επιστήμη των υπολογιστών

Το 5ο θέμα χαρακτηρίζεται ως εργασίες βασικό επίπεδοπολυπλοκότητα, χρόνος εκτέλεσης - περίπου 2 λεπτά, μέγιστη βαθμολογία - 1

• Κωδικοποίηση- είναι η παρουσίαση πληροφοριών σε μορφή κατάλληλη για την αποθήκευση, μετάδοση και επεξεργασία τους. Ο κανόνας για τη μετατροπή πληροφοριών σε μια τέτοια αναπαράσταση ονομάζεται κώδικας.
• Η κωδικοποίηση γίνεται στολήΚαι άνισος:
• με ομοιόμορφη κωδικοποίηση, όλα τα σύμβολα αντιστοιχούν σε κωδικούς του ίδιου μήκους.
• στο ανομοιόμορφη κωδικοποίηση διαφορετικούς χαρακτήρεςαντιστοιχούν σε κωδικούς διαφορετικού μήκους, γεγονός που καθιστά δύσκολη την αποκωδικοποίηση.

Παράδειγμα:Ας κρυπτογραφήσουμε τα γράμματα A, B, C, D χρησιμοποιώντας δυαδική κωδικοποίησηενιαίος κωδικός και μετρήστε τον αριθμό των πιθανών μηνυμάτων:

Έτσι πήραμε ενιαίος κωδικός, επειδή το μήκος κάθε κωδικής λέξης είναι το ίδιο για όλους τους κωδικούς (2).

Κωδικοποίηση και αποκρυπτογράφηση μηνυμάτων

Αποκωδικοποίηση (αποκωδικοποίηση)- αυτή είναι η επαναφορά ενός μηνύματος από μια ακολουθία κωδικών.

Για να λύσετε προβλήματα με την αποκωδικοποίηση, πρέπει να γνωρίζετε την συνθήκη Fano:

Κατάσταση Fano:καμία κωδική λέξη δεν πρέπει να είναι η αρχή μιας άλλης κωδικής λέξης (που διασφαλίζει ότι τα μηνύματα αποκωδικοποιούνται ξεκάθαρα από την αρχή)

Κωδικός προθέματοςείναι ένας κώδικας στον οποίο καμία κωδική λέξη δεν συμπίπτει με την αρχή μιας άλλης κωδικής λέξης. Τα μηνύματα που χρησιμοποιούν αυτόν τον κωδικό αποκωδικοποιούνται χωρίς αμφιβολία.

Παρέχεται σαφής αποκωδικοποίηση:

Επίλυση 5 εργασιών Ενιαίας Κρατικής Εξέτασης

Ενιαία Κρατική Εξέταση 5.1:Για να κωδικοποιήσουμε τα γράμματα O, B, D, P, A, αποφασίσαμε να χρησιμοποιήσουμε τη δυαδική αναπαράσταση των αριθμών 0, 1, 2, 3 και 4, αντίστοιχα (με τη διατήρηση ενός ασήμαντου μηδενός στην περίπτωση ενός αναπαράσταση ψηφίων).

Κωδικοποιήστε την ακολουθία των γραμμάτων WATERFALL με αυτόν τον τρόπο και γράψτε το αποτέλεσμα σε οκταδικό κώδικα.

✍ Λύση:

• Ας μετατρέψουμε τους αριθμούς σε δυαδικούς κωδικούς και ας τους αντιστοιχίσουμε με τα γράμματά μας:

O -> 0 -> 00 V -> 1 -> 01 D -> 2 -> 10 P -> 3 -> 11 A -> 4 -> 100

Τώρα ας κωδικοποιήσουμε την ακολουθία των γραμμάτων από τη λέξη WATERFALL:

010010001110010

Ας χωρίσουμε το αποτέλεσμα σε ομάδες των τριών χαρακτήρων από δεξιά προς τα αριστερά για να τους μετατρέψουμε στο οκταδικό σύστημα αριθμών:

010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2

Αποτέλεσμα: 22162

Απόφαση Ενιαίας Κρατικής Εξέτασης αυτής της ανάθεσηςστην επιστήμη των υπολογιστών, βίντεο:

Ας εξετάσουμε μια άλλη ανάλυση 5 Εργασίες Ενιαίας Κρατικής Εξετάσεων:

Ενιαία Κρατική Εξέταση 5.2:Για 5 γράμματα Λατινικό αλφάβητοκαθορίζονται οι δυαδικοί κωδικοί τους (για μερικά γράμματα - από δύο bit, για μερικά - από τρία). Αυτοί οι κωδικοί παρουσιάζονται στον πίνακα:

ένα	σι	ντο	ρε	μι
000	110	01	001	10

Ποιο σύνολο γραμμάτων κωδικοποιείται από τη δυαδική συμβολοσειρά 1100000100110;

✍ Λύση:

• Αρχικά, ελέγχουμε τη συνθήκη Fano: καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Η συνθήκη είναι αληθής.

✎ 1η λύση:

• Σπάμε τον κωδικό από αριστερά προς τα δεξιά σύμφωνα με τα δεδομένα που παρουσιάζονται στον πίνακα. Τότε ας το μεταφράσουμε σε γράμματα:

110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ β α γ δ ε

Αποτέλεσμα:β α γ δ ε.

✎ 2η λύση:

110 000 01 001 10

Αποτέλεσμα:β α γ δ ε.

Επιπλέον, μπορείτε να παρακολουθήσετε ένα βίντεο της λύσης αυτής της εργασίας Ενιαίας Πολιτικής Εξέτασης στην επιστήμη των υπολογιστών:

Ας λύσουμε την παρακάτω 5η εργασία:

Εξέταση Ενιαίας Πολιτείας 5.3:
Για τη μετάδοση αριθμών μέσω ενός θορυβώδους καναλιού, χρησιμοποιείται ένας κωδικός ελέγχου ισοτιμίας. Κάθε ψηφίο γράφεται δυαδική αναπαράσταση, με τα αρχικά μηδενικά να προστίθενται σε μήκος 4, και το άθροισμα των στοιχείων του modulo 2 προστίθεται στην ακολουθία που προκύπτει (για παράδειγμα, αν μεταδώσουμε το 23, παίρνουμε την ακολουθία 0010100110).

Προσδιορίστε τον αριθμό που μεταδόθηκε μέσω του καναλιού με τη μορφή 01100010100100100110.

✍ Λύση:

• Ας σκεφτούμε παράδειγμααπό τη δήλωση προβλήματος:

Ήταν 23 10 Τώρα 0010100110 2

Πού είναι τα ψηφία του αρχικού αριθμού (τονίστε τα με κόκκινο):

0010 10011 0 (0010 - 2, 0011 - 3)

Προστέθηκε το πρώτο ψηφίο 1 μετά το δυαδικό δύο είναι έλεγχος ισοτιμίας (1 μονάδα in 0010 - σημαίνει περίεργο) 0 μετά το δυαδικό τριπλό είναι επίσης ένας έλεγχος περιττής ισοτιμίας (2 in 0011 , που σημαίνει ακόμη).

Με βάση την ανάλυση του παραδείγματος, λύνουμε το πρόβλημά μας ως εξής: αφού οι αριθμοί που «χρειαζόμαστε» σχηματίζονται από ομάδες 4 αριθμών η καθεμία συν έναν αριθμό για έλεγχο ισοτιμίας, θα χωρίσουμε το κωδικοποιημένο μήνυμα σε ομάδες των 5 και θα απορρίψουμε ο τελευταίος χαρακτήρας από κάθε ομάδα:

χωρίστε το σε 5s:

01100 01010 01001 00110

απορρίψτε τον τελευταίο χαρακτήρα από κάθε ομάδα:

0110 0101 0100 0011

Αποτέλεσμαμετάφραση σε μετρικό σύστημα:

0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3

Απάντηση: 6 5 4 3

Μπορείτε να παρακολουθήσετε ένα βίντεο της λύσης αυτής της εργασίας Ενιαίας Πολιτικής Εξετάσεων στην επιστήμη των υπολογιστών:

Εξέταση Ενιαίας Πολιτείας 5.4:
Για να κωδικοποιήσουν μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα K, L, M, N, αποφάσισαν να χρησιμοποιήσουν έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Η κωδική λέξη 0 χρησιμοποιήθηκε για το γράμμα Η και η κωδική λέξη 10 για το γράμμα Κ.

Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των τεσσάρων κωδικών λέξεων;

✍ Λύση:

✎ 1 επιλογή λύσηςμε βάση λογικά συμπεράσματα:

• Ας βρούμε τις συντομότερες δυνατές κωδικές λέξεις για όλα τα γράμματα.
• Κωδικές λέξεις 01 Και 00 δεν μπορεί να χρησιμοποιηθεί, αφού τότε παραβιάζεται η συνθήκη Fano (ξεκινούν από 0 και 0 - Αυτό Ν).
• Ας ξεκινήσουμε με διψήφιες κωδικές λέξεις. Ας πάρουμε το γράμμα μεγάλομια κωδική λέξη 11 . Τότε είναι αδύνατο να επιλέξετε μια κωδική λέξη για το τέταρτο γράμμα χωρίς να παραβιάσετε τη συνθήκη Fano (αν στη συνέχεια πάρετε 110 ή 111, τότε αρχίζουν με 11).
• Αυτό σημαίνει ότι πρέπει να χρησιμοποιούνται τριψήφιες κωδικές λέξεις. Ας κωδικοποιήσουμε τα γράμματα μεγάλοΚαι Μκωδικές λέξεις 110 Και 111 . Η συνθήκη Fano ικανοποιείται.

(Ν)1 + (Κ)2 + (L)3 + (Μ)3 = 9

✎ Επιλογή 2:

(N) -> 0 -> 1 χαρακτήρας (K) -> 10 -> 2 χαρακτήρες (L) -> 110 -> 3 χαρακτήρες (M) -> 111 -> 3 χαρακτήρες

Το συνολικό μήκος και των τεσσάρων κωδικών λέξεων είναι:

(Ν)1 + (Κ)2 + (L)3 + (Μ)3 = 9

Απάντηση: 9

Unified State Exam in Informatics 5 task 2017 FIPI option 2 (επιμέλεια Krylov S.S., Churkina T.E.):

Τα μηνύματα που περιέχουν μόνο 4 γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, C, D. Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που επιτρέπει τη σαφή αποκωδικοποίηση. Για τα γράμματα A, B, C χρησιμοποιούνται οι ακόλουθες κωδικές λέξεις: A: 101010, B: 011011, C: 01000.

Г, στο οποίο ο κωδικός θα επιτρέπει σαφή αποκωδικοποίηση. το μικρότεροαριθμητική αξία.

✍ Λύση:

• Οι μικρότεροι κωδικοί θα μπορούσαν να μοιάζουν 0 Και 1 (μονοψήφιο). Αλλά αυτό δεν θα ικανοποιούσε τη συνθήκη Fano ( ΕΝΑξεκινά με ένα - 101010 , σιξεκινά από το μηδέν - 011011 ).
• Ο επόμενος μικρότερος κωδικός θα ήταν μια λέξη δύο γραμμάτων 00 . Εφόσον δεν είναι πρόθεμα καμίας από τις παρουσιαζόμενες κωδικές λέξεις, τότε G = 00.

Αποτέλεσμα: 00

Unified State Examination in Informatics 5 task 2017 FIPI option 16 (επιμέλεια Krylov S.S., Churkina T.E.):

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D και D, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα, ο οποίος μας επιτρέπει να αποκωδικοποιήσουμε ξεκάθαρα τη δυαδική ακολουθία που εμφανίζεται στην πλευρά λήψης του καναλιού επικοινωνίας. Ο κωδικός που χρησιμοποιήθηκε ήταν: A - 01, B - 00, C - 11, D - 100.

Υποδείξτε με ποια κωδική λέξη πρέπει να κωδικοποιείται το γράμμα D. Μήκοςαυτή η κωδική λέξη πρέπει να είναι ελάχιστααπό όλα τα δυνατά. Ο κωδικός πρέπει να ικανοποιεί το ακίνητο ξεκάθαρη αποκωδικοποίηση. Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με τη χαμηλότερη αριθμητική τιμή.

✍ Λύση:

Αποτέλεσμα: 101

Μια πιο λεπτομερής ανάλυση του μαθήματος μπορείτε να δείτε στο βίντεο της Ενιαίας Κρατικής Εξέτασης στην Επιστήμη Υπολογιστών 2017:

Unified State Examination in Informatics 5 task 2017 FIPI option 17 (Krylov S.S., Churkina T.E.):

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D, D και E, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα, ο οποίος μας επιτρέπει να αποκωδικοποιήσουμε ξεκάθαρα τη δυαδική ακολουθία που εμφανίζεται στην πλευρά λήψης του καναλιού επικοινωνίας . Ο κωδικός που χρησιμοποιήθηκε ήταν: A - 0, B - 111, C - 11001, D - 11000, D - 10.

Υποδείξτε με ποια κωδική λέξη πρέπει να κωδικοποιείται το γράμμα Ε.Το μήκος αυτής της κωδικής λέξης πρέπει να είναι το συντομότερο δυνατό. Ο κωδικός πρέπει να ικανοποιεί την ιδιότητα της ξεκάθαρης αποκωδικοποίησης. Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με τη χαμηλότερη αριθμητική τιμή.

✍ Λύση:

1 - ακατάλληλο (όλα τα γράμματα εκτός από το Α ξεκινούν με 1) 10 - ακατάλληλο (αντιστοιχεί στον κωδικό D) 11 - ακατάλληλο (η αρχή των κωδικών B, C και D) 100 - ακατάλληλο (κωδικός D - 10 - είναι το αρχή αυτού του κωδικού) 101 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 110 - ακατάλληλο (η αρχή του κωδικού Β και Δ) 111 - ακατάλληλο (αντιστοιχεί στον κωδικό Β) 1000 - ακατάλληλο ( κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1001 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1010 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1011 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1100 - ακατάλληλο (αρχή κωδικού Β και Δ) 1101 - κατάλληλο

Αποτέλεσμα: 1101

Περισσότερο λεπτομερής λύσηΑυτή η εργασία παρουσιάζεται στο εκπαιδευτικό βίντεο:

Εργασία 5. Έκδοση επίδειξης του Unified State Exam 2018 Computer Science (FIPI):

Τα κρυπτογραφημένα μηνύματα που περιέχουν μόνο δέκα γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, E, I, K, L, R, S, T, U. Χρησιμοποιείται ένας ανομοιόμορφος δυαδικός κώδικας για μετάδοση. Οι κωδικές λέξεις χρησιμοποιούνται για εννέα γράμματα.

Καθορίστε τη συντομότερη κωδική λέξη για το γράμμα σι, σύμφωνα με την οποία ο κωδικός θα ικανοποιεί την συνθήκη Fano.Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με το μικρότεροαριθμητική αξία.

✍ Λύση:

Αποτέλεσμα: 1100

Για μια λεπτομερή λύση σε αυτήν την 5η εργασία από την έκδοση επίδειξης του Unified State Exam 2018, δείτε το βίντεο:

Εργασία 5_9. Πρότυπες επιλογές εξετάσεων 2017. Επιλογή 4 (Krylov S.S., Churkina T.E.):

Τα κρυπτογραφημένα μηνύματα που περιέχουν μόνο τέσσερα γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, C, D. Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που επιτρέπει τη σαφή αποκωδικοποίηση. Για τα γράμματα ΕΝΑ, σι, ΣΕχρησιμοποιημένες κωδικές λέξεις:

A: 00011 B: 111 C: 1010

Καθορίστε τη συντομότερη κωδική λέξη για το γράμμα σολ, στο οποίο ο κώδικας θα επιτρέπει τη σαφή αποκωδικοποίηση.Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με το μικρότεροαριθμητική αξία.

✍ Λύση:

Αποτέλεσμα: 00

Εργασία 5_10. Επιλογή προπόνησης Νο. 3 από 10/01/2018 (FIPI):

Τα μηνύματα που περιέχουν μόνο γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: Α, Ε, Δ, Κ, Μ, Ρ; Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που ικανοποιεί τη συνθήκη Fano. Οι ακόλουθοι κωδικοί είναι γνωστό ότι χρησιμοποιούνται:

E – 000 D – 10 K – 111

Καθορίστε το μικρότερο δυνατό μήκος κωδικοποιημένου μηνύματος DEDMAKAR.
Στην απάντησή σας, γράψτε έναν αριθμό - τον αριθμό των bit.

✍ Λύση:

D E D M A K A R 10.000 10.001 01.111 01.110

Ας μετρήσουμε τον αριθμό των ψηφίων στον τελικό κωδικό και πάρουμε 20 .

Αποτέλεσμα: 20

Δείτε τη λύση στην εργασία:

Έκδοση επίδειξης του Unified State Exam 2019 – εργασία No. 5

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D, D, E, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα Α χρησιμοποιήθηκε η κωδική λέξη 0. για το γράμμα Β – κωδική λέξη 10. Ποιο είναι το μικρότερο δυνατό άθροισμα των μηκών των κωδικών λέξεων για τα γράμματα Β, Δ, Δ, Ε;

Σημείωση. Η συνθήκη Fano σημαίνει ότι καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Αυτό καθιστά δυνατή την ξεκάθαρη αποκρυπτογράφηση κρυπτογραφημένων μηνυμάτων.

Λύση:

Απάντηση:

Έκδοση επίδειξης του Unified State Exam 2018 – εργασία No. 5

Τα κρυπτογραφημένα μηνύματα που περιέχουν μόνο δέκα γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, E, I, K, L, R, S, T, U. Χρησιμοποιείται ένας ανομοιόμορφος δυαδικός κώδικας για μετάδοση. Οι κωδικές λέξεις χρησιμοποιούνται για εννέα γράμματα.

Υποδείξτε τη συντομότερη κωδική λέξη για το γράμμα Β έτσι ώστε ο κωδικός να ικανοποιεί τη συνθήκη Fano. Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με τη χαμηλότερη αριθμητική τιμή. Σημείωση. Η συνθήκη Fano σημαίνει ότι καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Αυτό καθιστά δυνατή την ξεκάθαρη αποκρυπτογράφηση κρυπτογραφημένων μηνυμάτων.

Λύση:

Απάντηση: 1100

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D, D, E, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα Α χρησιμοποιήθηκε η κωδική λέξη 0. για το γράμμα Β – κωδική λέξη 10. Ποιο είναι το μικρότερο δυνατό άθροισμα των μηκών και των έξι κωδικών λέξεων;
Σημείωση. Η συνθήκη Fano σημαίνει ότι καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Αυτό καθιστά δυνατή την ξεκάθαρη αποκρυπτογράφηση κρυπτογραφημένων μηνυμάτων.

Έκδοση επίδειξης του Unified State Exam 2017 - εργασία No. 5

Λύση:

Για να βρούμε κωδικές λέξεις θα χρησιμοποιήσουμε αυτόν τον πίνακα.

Εάν οι κωδικοί των υπόλοιπων γραμμάτων αρχίζουν με 0, ο κωδικός του γράμματος A=0 θα είναι η αρχή των κωδικών τους, επομένως αυτή η επιλογή δεν είναι κατάλληλη. Εάν ο κωδικός B = 10, οι κωδικοί των γραμμάτων B, D, D, E ξεκινούν με 11. Για να πάρετε 4 διαφορετικούς κωδικούς, πρέπει να χρησιμοποιήσετε κωδικούς που αποτελούνται από 4 χαρακτήρες (1111, 1110, 1101, 1100).

0	1
	1
	1		0
	1	0	1	0

A - 0 (1 χαρακτήρας)
B - 10 (2 χαρακτήρες)
B - 1100 (4 χαρακτήρες)
G - 1101 (4 χαρακτήρες)
D - 1110 (4 χαρακτήρες)
E - 1111 (4 χαρακτήρες)

1+2+4+4+4+4 = 19

Απάντηση: 19

Έκδοση επίδειξης του Unified State Exam 2016 – εργασία No. 5

Μηνύματα που περιέχουν μόνο τέσσερα γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: P, O, S, T. Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που επιτρέπει τη σαφή αποκωδικοποίηση. Για τα γράμματα T, O, P χρησιμοποιούνται οι ακόλουθες κωδικές λέξεις: T: 111, O: 0, P: 100.

Καθορίστε τη συντομότερη κωδική λέξη για το γράμμα C, στην οποία ο κωδικός θα επιτρέπει σαφή αποκωδικοποίηση. Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με τη χαμηλότερη αριθμητική τιμή.

Λύση:

Για να βρούμε κωδικές λέξεις θα χρησιμοποιήσουμε αυτό το σχήμα.

Αν οι κωδικοί των υπόλοιπων γραμμάτων αρχίζουν με 0 , κωδικός γράμματος ΣΧΕΤΙΚΑ ΜΕ=0 θα είναι η αρχή των κωδικών τους, επομένως αυτή η επιλογή δεν είναι κατάλληλη. Από τον κωδικό γράμματος Π=100 και τον κωδικό γράμματος Τ =111 , μετά το γράμμα ΜΕδεν μπορεί να ξεκινήσει ή να τελειώσει με αυτούς τους αριθμούς.

Απάντηση: 101

Για την κωδικοποίηση ενός μηνύματος που αποτελείται μόνο από τα γράμματα A, B, C και D, χρησιμοποιείται ένας δυαδικός κώδικας άνισου μήκους:

Εάν κωδικοποιήσετε την ακολουθία χαρακτήρων GAVBGV με αυτόν τον τρόπο και γράψετε το αποτέλεσμα δεκαεξαδικός κώδικας, τότε θα αποδειχθεί:

1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16

Λύση:

GAVBGV = 0110001011011010

0110	0010	1101	1010
6	2	ρε	ΕΝΑ

Απάντηση: 4

Μαύρο και άσπρο εικόνα ράστερκωδικοποιημένη γραμμή προς γραμμή, ξεκινώντας από τα αριστερά πάνω γωνιάκαι τελειώνει στην κάτω δεξιά γωνία. Κατά την κωδικοποίηση, το 1 αντιπροσωπεύει το μαύρο και το 0 το λευκό.

Για συμπαγή, το αποτέλεσμα ήταν γραμμένο οκταδικό σύστημαΥπολογισμός Επιλέγω σωστή καταχώρησηκώδικας.

1) 57414 2) 53414 3) 53412 4) 53012

Λύση:

1	0	1	0	1
1	1	0	0	0
0	1	0	1	0

101	011	100	001	010
5	3	4	1	2

Απάντηση: 3

Για τη μετάδοση αριθμών μέσω ενός θορυβώδους καναλιού, χρησιμοποιείται ένας κωδικός ελέγχου ισοτιμίας. Κάθε ψηφίο του γράφεται σε δυαδική αναπαράσταση, με μηδενικά που προστίθενται στο μήκος 4 και το άθροισμα των στοιχείων του modulo 2 προστίθεται στην ακολουθία που προκύπτει (για παράδειγμα, αν μεταδώσουμε το 23, παίρνουμε την ακολουθία 0010100110). Προσδιορίστε ποιος αριθμός μεταδόθηκε μέσω του καναλιού με τη μορφή 01100010100100100110;

1) 6543 2) 62926 3) 62612 4) 3456

Λύση:

01100010100100100110

01100	01010	01001	00110
6	5	4	3

Απάντηση: 1

Για την κωδικοποίηση των γραμμάτων O, L, A, Z, K χρησιμοποιούνται δυαδικοί κωδικοί των αριθμών 0, 1, 2, 3 και 4 αντίστοιχα (με διατήρηση ενός ασήμαντου μηδενός στην περίπτωση μονοψήφιας παράστασης). Εάν κωδικοποιήσετε την ακολουθία χαρακτήρων BARRIER με αυτόν τον τρόπο και γράψετε το αποτέλεσμα σε δεκαεξαδικό κώδικα, θα λάβετε:

1) 4531253 2) 9876 3) E832 4) 238E

Λύση:

ΣΧΕΤΙΚΑ ΜΕ	μεγάλο	ΕΝΑ	Ζ	ΠΡΟΣ ΤΗΝ
0=00	1=01	2=10	3=11	4=100

ΦΡΑΓΜΑ = 1110100000110010

1110	1000	0011	0010
μι	8	3	2

Απάντηση: 3

Για να μεταδώσουν ένα μήνυμα μέσω ενός καναλιού επικοινωνίας που αποτελείται μόνο από τα γράμματα A, B, C, D, αποφάσισαν να χρησιμοποιήσουν έναν κωδικό ανομοιόμορφου μήκους: A=00, B=11, C=100. Πώς πρέπει να κωδικοποιηθεί το γράμμα G έτσι ώστε το μήκος του κωδικού να είναι ελάχιστο και το κωδικοποιημένο μήνυμα να μπορεί να χωριστεί ξεκάθαρα σε γράμματα;

1) 010 2) 0 3) 01 4) 011

Λύση:

Α=00, Β=11, Γ=100, Δ=?

Απάντηση: 3

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D και D, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα, ο οποίος μας επιτρέπει να αποκωδικοποιήσουμε ξεκάθαρα τη δυαδική ακολουθία που εμφανίζεται στην πλευρά λήψης του καναλιού επικοινωνίας. Για τα γράμματα A, B, C και D χρησιμοποιήθηκαν οι ακόλουθες κωδικές λέξεις: A - 111, B - 110, C - 101, D - 100.

Υποδείξτε ποια κωδική λέξη από αυτές που αναφέρονται παρακάτω μπορεί να χρησιμοποιηθεί για την κωδικοποίηση του γράμματος D.

Ο κωδικός πρέπει να ικανοποιεί την ιδιότητα της ξεκάθαρης αποκωδικοποίησης. Εάν μπορούν να χρησιμοποιηθούν περισσότερες από μία κωδικές λέξεις, εισαγάγετε τη συντομότερη.

1) 1 2) 0 3) 01 4) 10

Λύση:

A - 111, B - 110, C - 101, D - 100, D - ?

Απάντηση: 2

Μηνύματα που περιέχουν μόνο 4 γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, C, D. Για την κωδικοποίηση των γραμμάτων A, B, C, χρησιμοποιούνται κωδικές λέξεις 5 bit: A - 10110, B - 11000, C - 00101. Για αυτό το σύνολο κωδικών οι λέξεις έχουν την ακόλουθη ιδιότητα: οποιεσδήποτε δύο λέξεις από το σύνολο διαφέρουν σε τουλάχιστον τρεις θέσεις. Αυτή η ιδιότητα είναι σημαντική για την αποκρυπτογράφηση μηνυμάτων παρουσία παρεμβολών. Ποια από τις παρακάτω κωδικές λέξεις μπορεί να χρησιμοποιηθεί για το γράμμα G έτσι ώστε η καθορισμένη ιδιότητα να ισχύει και για τις τέσσερις κωδικές λέξεις;

1) 01110 2) 01011 3) 10001 4) καμία από τις παραπάνω λέξεις δεν είναι κατάλληλη

Λύση:

1) 01 110: A - 10 110 - δεν διαφέρουν σε τουλάχιστον τρεις θέσεις

2) 01011: A - 101 10, B - 1 1000, C - 0010 1 - διαφέρουν σε τουλάχιστον τρεις θέσεις

Απάντηση: 2

Ένας κώδικας 5 bit χρησιμοποιείται για τη μετάδοση δεδομένων μέσω ενός καναλιού επικοινωνίας. Το μήνυμα περιέχει μόνο τα γράμματα A, B και C, τα οποία κωδικοποιούνται με τις ακόλουθες κωδικές λέξεις:

A - 10001, B - 01101, C - 10110.

Ενδέχεται να υπάρχουν παρεμβολές κατά τη μετάδοση. Ωστόσο, μπορείτε να προσπαθήσετε να διορθώσετε ορισμένα λάθη. Οποιαδήποτε δύο από αυτά τρεις κωδικοίοι λέξεις διαφέρουν μεταξύ τους σε τουλάχιστον τρεις θέσεις. Επομένως, εάν προέκυψε ένα σφάλμα το πολύ σε μία θέση κατά τη μετάδοση μιας λέξης, τότε μπορεί να γίνει μια ενημερωμένη εικασία σχετικά με το γράμμα που μεταδόθηκε. (Λένε ότι "ο κωδικός διορθώνει ένα σφάλμα.") Για παράδειγμα, εάν ληφθεί η κωδική λέξη 01111, θεωρείται ότι μεταδόθηκε το γράμμα Β (Η διαφορά από την κωδική λέξη για το Β είναι μόνο σε μία θέση άλλες κωδικές λέξεις υπάρχουν περισσότερες διαφορές.) Εάν η ληφθείσα κωδική λέξη Εάν η λέξη διαφέρει από τις κωδικές λέξεις για τα γράμματα A, B, C σε περισσότερες από μία θέσεις, θεωρείται ότι έχει συμβεί σφάλμα (συμβολίζεται με " Χ').

Λήφθηκε μήνυμα 00110 11101 11000 11001. Αποκωδικοποιήστε αυτό το μήνυμα - επιλέξτε τη σωστή επιλογή.

1) VBxx 2) VBVA 3) xxxx 4) VBxA

Λύση:

00110	11101	11000	11001
B=1 0110	B=0 1101	Χ	A=10 001

Απάντηση: 4

Για την κωδικοποίηση μιας συγκεκριμένης ακολουθίας που αποτελείται από τα γράμματα A, B, C, D και D, χρησιμοποιείται ένας μη ομοιόμορφος δυαδικός κώδικας, ο οποίος καθιστά δυνατή την αναμφισβήτητη αποκωδικοποίηση της προκύπτουσας δυαδικής ακολουθίας. Εδώ είναι ο κωδικός: A – 1; B – 0100; B – 000; G – 011; D – 0101. Απαιτείται η μείωση του μήκους της κωδικής λέξης για ένα από τα γράμματα, έτσι ώστε ο κωδικός να μπορεί να αποκωδικοποιηθεί αναμφίβολα. Οι κωδικοί των υπόλοιπων γραμμάτων δεν πρέπει να αλλάξουν. Ποιο από τις παραπάνω μεθόδουςΜπορεί να γίνει;

1) για το γράμμα G – 11 2) για το γράμμα B – 00 3) για το γράμμα G – 01 4) αυτό είναι αδύνατο

Λύση:

Απάντηση: 2

Για να κωδικοποιήσουν μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D, αποφάσισαν να χρησιμοποιήσουν έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα Α χρησιμοποιήθηκε η κωδική λέξη 1, για το γράμμα Β χρησιμοποιήθηκε η κωδική λέξη 011. Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των τεσσάρων κωδικών λέξεων;

1) 7 2) 8 3) 9 4) 10

Λύση:

A-1, B-011, B-00, G-010

Απάντηση: 9

Τα μηνύματα μεταδίδονται μέσω του καναλιού επικοινωνίας, καθένα από τα οποία περιέχει 15 γράμματα A, 10 γράμματα B, 6 γράμματα C και 4 γράμματα G (δεν υπάρχουν άλλα γράμματα στα μηνύματα). Κάθε γράμμα κωδικοποιείται ως δυαδική ακολουθία. Κατά την επιλογή του κωδικού, ελήφθησαν υπόψη δύο απαιτήσεις:

α) καμία κωδική λέξη δεν είναι η αρχή μιας άλλης (αυτό είναι απαραίτητο για να επιτρέπει ο κώδικας ξεκάθαρη αποκωδικοποίηση).

β) το συνολικό μήκος του κωδικοποιημένου μηνύματος πρέπει να είναι όσο το δυνατόν μικρότερο.

Ποιον κώδικα από τους παρακάτω θα πρέπει να επιλέξετε για να κωδικοποιήσετε τα γράμματα A, B, C και D;

1) A:1, B:01, C:001, D:111

2) Α:1, Β:01, Γ:10, Δ:111

3) A:00, B:01, C:10, D:11

4) Α:100, Β:101, Γ:11, Δ:0

Λύση:

Καμία κωδική λέξη δεν είναι η αρχή μιας άλλης: ΕΝΑείναι η αρχή σολστην 1η και 2η επιλογή.

Το συνολικό μήκος του κωδικοποιημένου μηνύματος πρέπει να είναι όσο το δυνατόν μικρότερο.

3) A:00 (15), B:01 (10), C:10 (6), D:11 (4)

2.15+2.10+2.6+2.4 = 70

4) A:100 (15), B:101 (10), C:11 (6), D:0 (4)

3.15+3.10+2.6_1.4 = 61

Απάντηση: 3

Μηνύματα που περιέχουν μόνο 4 γράμματα P, R, S, T μεταδίδονται μέσω ενός καναλιού επικοινωνίας χρησιμοποιώντας έναν ομοιόμορφο δυαδικό κώδικα, και η ακόλουθη ιδιότητα ικανοποιείται για ένα σύνολο κωδικών λέξεων: οποιεσδήποτε δύο λέξεις από το. σετ διαφέρουν κατά τουλάχιστον τρεις θέσεις. Αυτή η ιδιότητα είναι σημαντική για την αποκρυπτογράφηση μηνυμάτων παρουσία παρεμβολών. Για την κωδικοποίηση των γραμμάτων P, P, C, χρησιμοποιούνται κωδικές λέξεις 5 bit: P: 01111, P: 00001, C: 11000. Ο κωδικός 5 bit για το γράμμα T ξεκινά με 1 και τελειώνει σε 0. Προσδιορίστε την κωδική λέξη για το γράμμα Τ.

Λύση:

S: 1 1000

Τ: 1 011 0 (Το T αρχίζει με 1 και τελειώνει με 0)

S και T: 2 γράμματα είναι ίδια, αυτό σημαίνει ότι τα υπόλοιπα 3 γράμματα πρέπει να είναι διαφορετικά.

Απάντηση: 1 0110