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

Εργασία 31. Ανομοιόμορφοι κωδικοί. Κατάσταση Fano

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

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

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

1) 00 2) 01 3) 0000 4) 101

5-85. Για την κωδικοποίηση μιας συγκεκριμένης ακολουθίας που αποτελείται από τα γράμματα U, CH, E, N, I και K, χρησιμοποιείται μη ομοιόμορφη δυαδική κωδικός προθέματος. Εδώ είναι ο κωδικός: U – 000, Ch – 001, E – 010, N – 100, I – 011, K – 11. Είναι δυνατόν να συντομεύσετε το μήκος της κωδικής λέξης για ένα από τα γράμματα έτσι ώστε ο κωδικός να εξακολουθεί να παραμένει πρόθεμα; Οι κωδικοί των υπόλοιπων γραμμάτων δεν πρέπει να αλλάξουν. Επιλέγω σωστή επιλογήαπάντηση.

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

1) η κωδική λέξη για το γράμμα Ε μπορεί να συντομευτεί σε 01

2) η κωδική λέξη για το γράμμα Κ μπορεί να μειωθεί σε 1

3) η κωδική λέξη για το γράμμα N μπορεί να μειωθεί σε 10

4) Αυτό είναι αδύνατο

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

5-74. Μηνύματα που περιέχουν μόνο 4 γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: E, H, O, T. Σε οποιοδήποτε μήνυμα, τα περισσότερα γράμματα είναι O, το επόμενο πιο κοινό γράμμα είναι το E, μετά το N. Το γράμμα T είναι λιγότερο κοινό από οποιοδήποτε άλλο . Για τη μετάδοση μηνυμάτων, πρέπει να χρησιμοποιήσετε έναν μη ομοιόμορφο δυαδικό κώδικα που το επιτρέπει ξεκάθαρη αποκωδικοποίηση; τα μηνύματα πρέπει να είναι όσο το δυνατόν πιο σύντομα. Ο κρυπτογράφος μπορεί να χρησιμοποιήσει έναν από τους κωδικούς που αναφέρονται παρακάτω. Ποιον κωδικό να επιλέξει;

1) E – 0, N – 1, O – 00, T – 11 2) O – 1, N – 0, E – 01, T – 10

3) E – 1, N – 01, O – 001, T – 000 4) O – 0, N – 10, E – 111, T – 110

5-105. Τα μηνύματα μεταδίδονται μέσω του καναλιού επικοινωνίας, καθένα από τα οποία περιέχει 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

5-102. Υπάρχουν 10 διαφορετικά γράμματα στο μήνυμα. Κατά τη μετάδοσή του, χρησιμοποιείται ένας ανομοιόμορφος δυαδικός κώδικας προθέματος. Οι κωδικοί των τριών γραμμάτων είναι γνωστοί: 11, 100, 101. Οι κωδικοί των υπόλοιπων επτά γραμμάτων έχουν το ίδιο μήκος. Ποιο είναι το ελάχιστο συνολικό μήκος και των 10 κωδικών λέξεων;

5-104. Το μήνυμα περιέχει 50 γράμματα A, 30 γράμματα B, 20 γράμματα C και 5 γράμματα G. Κατά τη μετάδοσή του, χρησιμοποιήθηκε ένας ανομοιόμορφος δυαδικός κωδικός προθέματος, ο οποίος κατέστησε δυνατή τη λήψη του ελάχιστου μήκους του κωδικοποιημένου μηνύματος. Πώς είναι σε bits;

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

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

9-1-23. Μετά τη μετατροπή ράστερ 256-χρωμάτων αρχείο γραφικώνστη μορφή 16 χρωμάτων το μέγεθός του μειώθηκε κατά 15 KB. Ποιο ήταν το μέγεθος αρχείο προέλευσηςσε KB;

9-1-25. Μετά τη μετατροπή του αρχείου γραφικών ράστερ, ο όγκος του μειώθηκε κατά 1,5 φορές. Πόσα χρώματα υπήρχαν στην παλέτα αρχικά, αν ελήφθη μετά τη μετατροπή εικόνα ράστερη ίδια ανάλυση σε μια παλέτα 16 χρωμάτων;

13-37. Κατά την εγγραφή στο σύστημα υπολογιστήΣε κάθε χρήστη εκδίδεται ένα αναγνωριστικό που αποτελείται από 8 χαρακτήρες, από τους οποίους ο πρώτος και ο τελευταίος είναι ένα από 18 γράμματα και τα υπόλοιπα είναι αριθμοί (επιτρέπονται 10 δεκαδικά ψηφία). Κάθε τέτοιο αναγνωριστικό σε πρόγραμμα υπολογιστήγράφεται με τον ελάχιστο δυνατό και τον ίδιο ακέραιο αριθμό byte (χρησιμοποιείται κωδικοποίηση χαρακτήρα προς χαρακτήρα· όλοι οι αριθμοί κωδικοποιούνται με τον ίδιο και ελάχιστο δυνατό αριθμό bit, όλα τα γράμματα κωδικοποιούνται επίσης με τον ίδιο και ελάχιστο δυνατό αριθμό bits). Προσδιορίστε την ποσότητα μνήμης σε byte που εκχωρείται από αυτό το πρόγραμμα για την εγγραφή 500 κωδικών πρόσβασης.

13-38. Κατά την εγγραφή στο μηχανογραφικό σύστημα που χρησιμοποιείται για την ομαδική Ολυμπιάδα, δίνεται σε κάθε μαθητή μοναδικό αναγνωριστικό– ένας ακέραιος από 1 έως 1000. Ο ίδιος και ελάχιστος δυνατός αριθμός bit χρησιμοποιείται για την αποθήκευση κάθε αναγνωριστικού. Το αναγνωριστικό ομάδας αποτελείται από διαδοχικά καταγεγραμμένα αναγνωριστικά μαθητών και 8 επιπλέον κομμάτια. Το σύστημα χρησιμοποιεί τον ίδιο και ελάχιστο αριθμό byte για την καταγραφή κάθε αναγνωριστικού εντολής. Όλες οι ομάδες έχουν ίσο αριθμό συμμετεχόντων. Πόσα μέλη υπάρχουν σε κάθε ομάδα εάν χρειάζονται 180 byte για να αποθηκεύσετε τα αναγνωριστικά των 20 ομάδων που συμμετέχουν;

13-50. Κατά την εγγραφή σε ένα σύστημα υπολογιστή, σε κάθε χρήστη δίνεται ένας κωδικός πρόσβασης που αποτελείται από 15 χαρακτήρες και περιέχει μόνο χαρακτήρες από το σύνολο των 12 χαρακτήρων: A, B, C, D, E, F, G, H, K, L, M, N. Στη βάση δεδομένων Τα δεδομένα για την αποθήκευση πληροφοριών για κάθε χρήστη έχουν τον ίδιο και ελάχιστο δυνατό ακέραιο αριθμό byte. Σε αυτή την περίπτωση, χρησιμοποιείται η κωδικοποίηση των κωδικών πρόσβασης ανά χαρακτήρα, όλοι οι χαρακτήρες κωδικοποιούνται με τον ίδιο και ελάχιστο δυνατό αριθμό bit. Εκτός από τον ίδιο τον κωδικό πρόσβασης, στο σύστημα αποθηκεύονται πρόσθετες πληροφορίες για κάθε χρήστη, για τον οποίο εκχωρείται ένας ακέραιος αριθμός byte. αυτός ο αριθμός είναι ο ίδιος για όλους τους χρήστες. Για την αποθήκευση πληροφοριών για 20 χρήστες, απαιτήθηκαν 300 byte. Πόσα byte διατίθενται για αποθήκευση Επιπλέον πληροφορίεςπερίπου ένας χρήστης; Στην απάντησή σας, σημειώστε μόνο έναν ακέραιο αριθμό - τον αριθμό των byte.

16-165. Εννοια αριθμητική έκφραση: 9 22 + 3 66 – 18 γραμμένο στο βασικό 3 αριθμητικό σύστημα Πόσα ψηφία «2» υπάρχουν σε αυτόν τον συμβολισμό;

Το μάθημα είναι αφιερωμένο στον τρόπο επίλυσης της εργασίας 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 και θα απορρίψουμε ο τελευταίος χαρακτήρας από κάθε ομάδα:

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

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 - ακατάλληλο ( αρχή του κωδικού B και D) 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

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

Ας εξετάσουμε έναν άλλο πίνακα κωδικών: A B C D D 000 01 10 011 100 Εδώ η συνθήκη Fano δεν ικανοποιείται, αφού ο κωδικός του γράμματος B (01) είναι η αρχή του κωδικού του γράμματος G (011) και ο κωδικός του γράμματος Το D (100) αρχίζει με τον κωδικό του γράμματος B ( 10). Ωστόσο, μπορεί να σημειωθεί ότι η «αντίστροφη» συνθήκη Fano ικανοποιείται: κανένας κωδικός δεν είναι το τέλος ενός άλλου κώδικα (ένας τέτοιος κωδικός ονομάζεται postfix). Επομένως, το κωδικοποιημένο μήνυμα μπορεί να αποκωδικοποιηθεί αναμφίβολα από το τέλος. Για παράδειγμα, σκεφτείτε την αλυσίδα 011000110110. Τελευταίο γράμμασε αυτό το μήνυμα μπορεί να υπάρχει μόνο B (κωδικός 10): B 0110001101 10 Το δεύτερο γράμμα από το τέλος είναι B (κωδικός 01): B B 01100011 01 10 και ούτω καθεξής: B D G B B 01 100 011 01 10.

Διαφάνεια 26από την παρουσίαση "Μέθοδοι κωδικοποίησης πληροφοριών". Το μέγεθος του αρχείου με την παρουσίαση είναι 734 KB.

Κατεβάστε την παρουσίαση

Μέθοδοι κωδικοποίησης

περίληψη άλλων παρουσιάσεων

"Δυαδική κωδικοποίηση" - Αριθμοί. Δυαδική κωδικοποίηση πληροφορίες κειμένου. Πίνακας κωδικοποίησης. Ο όγκος πληροφοριών του κειμένου. Δυαδική κωδικοποίηση σε υπολογιστή. Κωδικοποίηση πληροφοριών κειμένου. Εκτεταμένος πίνακας κωδικών. Σύμβολο. Μοναδικός δυαδικός κώδικας. Γράμμα του λατινικού αλφαβήτου. Χρησιμοποιώντας το δυαδικό σύστημα. Υπολογιστές.

"Κωδικοποίηση πληροφοριών σε δυαδικό κώδικα" - Ορισμός. Αριθμητικά συστήματα. Δυαδικό σύστημαΥπολογισμός. Κωδικοποίηση. Κωδικοποίηση πληροφοριών. Δώστε παραδείγματα κωδικοποίησης. Μετρικό σύστημαΥπολογισμός. Η έννοια του αριθμού. Η σημασία ενός αριθμού εξαρτάται από τη θέση του. Αλφάβητο. Γλώσσες. ρωμαϊκός σύστημα μη θέσης. Δυαδική κωδικοποίηση. Τι είναι κρυπτογραφημένο εδώ;

«Μέθοδοι κωδικοποίησης» - Αριθμός στήλης. Γράμμα κείμενο πηγής. Κωδικοποίηση πληροφοριών. Μέθοδοι κωδικοποίησης πληροφοριών. Αποκωδικοποιήστε τις πληροφορίες. Μεταδιδόμενες πληροφορίες. Στον κόσμο των κωδικών. Αυτόματη κωδικοποίηση. Μέθοδος συντεταγμένων. Πλεονεκτήματα και μειονεκτήματα. Ποικιλία κωδικών. Αγόρι. Τι μπορείτε να καλέσετε σημειωματάριοαπό την άποψη της αποθήκευσης πληροφοριών. Κωδικοποιημένο κείμενο. Φορέας πληροφοριών. Λέξεις-κλειδιά. Λύσε το παζλ.

"Μέθοδοι κωδικοποίησης πληροφοριών" - Στη μνήμη του υπολογιστή, οι πληροφορίες παρουσιάζονται σε δυαδικό κώδικα. Κωδικοποίηση και αποκωδικοποίηση. Μπορείτε να κωδικοποιήσετε πληροφορίες. Μέθοδοι κωδικοποίησης πληροφοριών. Ας δημιουργήσουμε έναν απλό πίνακα κωδικών. Για να μάθετε την κρυπτογραφημένη λέξη, πάρτε μόνο τις πρώτες συλλαβές. Τι διάβασε ο Λομ στις σημαίες του επερχόμενου σκαρί. Σκαρφίζομαι δικός μου τρόποςκωδικοποίηση γραμμάτων του ρωσικού αλφαβήτου. Καθήκοντα. Κρυπτογραφημένες πληροφορίες. εφευρέθηκε ο Λουί Μπράιγ ιδιαίτερο τρόποπαρουσίαση πληροφοριών.

«Μέθοδοι κωδικοποίησης πληροφοριών» - Δυαδική κωδικοποίηση σε υπολογιστή. Ποσότητα πληροφοριών. Οπτικός τηλέγραφος Shapp. Κατάσταση Fano. Τι κώδικα να χρησιμοποιήσετε. Μήνυμα ελήφθη. "Ναι ή όχι". Ο πρώτος τηλέγραφος. Μέθοδοι κωδικοποίησης πληροφοριών. Πληροφορίες καταγραφής. Γιατί δυαδική κωδικοποίηση. Σημαίες σημάτων. Κωδικοποίηση. Κωδικοποίηση και αποκωδικοποίηση. Κωδικοποίηση πληροφοριών. Επιλογή της μεθόδου κωδικοποίησης. Τύποι πληροφοριών. Πόσες επιλογές;

Γειά σου! Ονομάζομαι Alexander Georgievich και είμαι επαγγελματίας δάσκαλος στη Μόσχα στην επιστήμη των υπολογιστών και στον προγραμματισμό. Έχετε συναντήσει κάποιο πρόβλημα που σχετίζεται με την κωδικοποίηση και έχετε μπερδευτεί σχετικά με τον αλγόριθμο για την επίλυσή του; Πρέπει επειγόντως να συναντηθείτεΚατάσταση Fanoκαι εγγραφείτε για ιδιαίτερα μαθήματα μαζί μου. Στα μαθήματά μου επικεντρώνομαι στην επίλυση θεματικών απλών και σύνθετων ασκήσεων.

Ποιο είναι το νόημα της άμεσης συνθήκης του Φάνου;

Κατάσταση Fanoπήρε το όνομά του από τον δημιουργό του, τον Ιταλοαμερικανό επιστήμονα Robert Fano. Η συνθήκη είναι απαραίτητη στη θεωρία κωδικοποίησης κατά την κατασκευή ενός αυτοτερματιζόμενου κώδικα. Δεδομένης της διαφορετικής ορολογίας, ένας τέτοιος κωδικός ονομάζεται κωδικός προθέματος.

Αυτή η συνθήκη μπορεί να διατυπωθεί ως εξής: « καμία κωδική λέξη δεν μπορεί να λειτουργήσει ως αρχή οποιασδήποτε άλλης κωδικής λέξης».

Από μαθηματική άποψη, η συνθήκη μπορεί να διατυπωθεί ως εξής: εάν ο κωδικός περιέχει τη λέξηB, μετά για οποιαδήποτε μη κενή συμβολοσειράΗ λέξη C BC δεν υπάρχει στον κώδικα».

Τι σημαίνει η αντίστροφη συνθήκη Fano;

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

Από μαθηματική άποψη, η αντίστροφη συνθήκη μπορεί να διατυπωθεί ως εξής: εάν ο κωδικός περιέχει τη λέξη B, τότε για οποιαδήποτε μη κενή συμβολοσειρά C η λέξη CB δεν υπάρχει στον κωδικό».

Πρακτική εφαρμογή της συνθήκης Fano

Ας σκεφτούμε τηλεφωνικοί αριθμοί V παραδοσιακή τηλεφωνία. Εάν ο αριθμός "102" υπάρχει ήδη, τότε ο αριθμός "1029876" απλά δεν θα εκδοθεί. Εάν καλέσετε τα τρία πρώτα ψηφία, το PBX σταματά να αναγνωρίζει και να δέχεται όλα τα άλλα ψηφία, συνδέοντας τον συνδρομητή με τον αριθμό 102. Ωστόσο, αυτός ο κανόνας δεν ισχύει για τους χειριστές κινητές επικοινωνίες. Αυτό οφείλεται στο γεγονός ότι για να καλέσετε έναν αριθμό πρέπει να πατήσετε το αντίστοιχο πλήκτρο, το οποίο είναι κυρίως το πλήκτρο με την πράσινη εικόνα Ακουστικό. Για το λόγο αυτό, οι αριθμοί «102», «1020» και «1029876» μπορούν να υπάρχουν και να εκχωρηθούν σε διαφορετικούς παραλήπτες.

Το έργο:δίνεται μια ακολουθία που αποτελείται από τα γράμματα «Α», «Β», «Γ», «Δ» και «Ε». Για την κωδικοποίηση της δεδομένης ακολουθίας, χρησιμοποιείται ένας μη ομοιόμορφος δυαδικός κώδικας, με τον οποίο είναι δυνατή η διεξαγωγή σαφούς αποκωδικοποίησης.

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

Λύση: για να διατηρηθεί η δυνατότητα αποκωδικοποίησης, αρκεί η συμμόρφωση με απευθείας ή αντίστροφηΣυνθήκες Fano. Ας πραγματοποιήσουμε έναν διαδοχικό έλεγχο των επιλογών 1, 3 και 4. Εάν καμία από τις επιλογές δεν είναι κατάλληλη, η σωστή απάντηση θα είναι η επιλογή 2 (δεν είναι δυνατή).

Επιλογή 1. Κωδικός: A - 00, B - 01, C - 011, D - 101 και E - 111. Απευθείας Κατάσταση Fanoδεν εκτελείται: ο κωδικός του χαρακτήρα "B" συμπίπτει με την αρχή του κωδικού του χαρακτήρα "C". Ο αντίστροφος κανόνας Fano δεν ισχύει: ο κωδικός του χαρακτήρα "B" συμπίπτει με το τέλος του κωδικού του χαρακτήρα "D". Η επιλογή δεν είναι κατάλληλη.

Επιλογή 3. Κωδικός: A - 00, B - 010, C - 01, D - 101, και E - 111. Απευθείας Κατάσταση Fanoδεν εκτελείται: ο κωδικός του χαρακτήρα "C" συμπίπτει με την αρχή του κωδικού του χαρακτήρα "B". Η αντίστροφη συνθήκη επίσης δεν ικανοποιείται: ο κωδικός του χαρακτήρα "C" συμπίπτει με το τέλος του κωδικού του χαρακτήρα "D". Η επιλογή δεν είναι κατάλληλη.

Επιλογή 4. Κωδικός: A - 00, B - 010, C - 011, D - 01 και E - 111. Απευθείας Κατάσταση Fanoδεν εκτελείται: ο κωδικός του χαρακτήρα "D" συμπίπτει με την αρχή του κωδικού των χαρακτήρων "B" και "C". Ωστόσο, τηρείται ο αντίστροφος κανόνας Fano: ο κωδικός του χαρακτήρα "D" δεν συμπίπτει με το τέλος του κωδικού όλων των άλλων χαρακτήρων. Για το λόγο αυτό, η επιλογή είναι κατάλληλη.

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

Απάντηση: 4

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

Έχετε ακόμα ερωτήσεις;

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

Εργασία Νο. 5

Όταν εκτελείτε αυτήν την εργασία, πρέπει να γνωρίζετε την συνθήκη Fano,Κωδικός Huffman

Ποιο είναι το νόημα της άμεσης συνθήκης του Φάνου;

Κατάσταση Fano πήρε το όνομά του από τον δημιουργό του, τον Ιταλοαμερικανό επιστήμονα Robert Fano. Η συνθήκη είναι απαραίτητη στη θεωρία κωδικοποίησης κατά την κατασκευή ενός αυτοτερματιζόμενου κώδικα. Δεδομένης της διαφορετικής ορολογίας, ένας τέτοιος κωδικός ονομάζεται κωδικός προθέματος.

Αυτή η συνθήκη μπορεί να διατυπωθεί ως εξής: «καμία κωδική λέξη δεν μπορεί να λειτουργήσει ως αρχή οποιασδήποτε άλλης κωδικής λέξης ».

Από μαθηματική άποψη, η συνθήκη μπορεί να διατυπωθεί ως εξής:εάν ο κωδικός περιέχει τη λέξη B, τότε για οποιαδήποτε μη κενή γραμμή C η λέξη BC δεν υπάρχει στον κωδικό ».

Τι σημαίνει η αντίστροφη συνθήκη Fano;

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

Από μαθηματική άποψη, η αντίστροφη συνθήκη μπορεί να διατυπωθεί ως εξής:εάν ο κωδικός περιέχει τη λέξη B, τότε για οποιαδήποτε μη κενή συμβολοσειρά C η λέξη CB δεν υπάρχει στον κωδικό ».

Το έργο: δίνεται μια ακολουθία που αποτελείται από τα γράμματα «Α», «Β», «Γ», «Δ» και «Ε». Για την κωδικοποίηση της δεδομένης ακολουθίας, χρησιμοποιείται ένας μη ομοιόμορφος δυαδικός κώδικας, με τον οποίο είναι δυνατή η διεξαγωγή σαφούς αποκωδικοποίησης.

Γράμμα

Δυαδικό ισοδύναμο

010

011

101

111

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

Αριθμός επιλογής

Απάντηση

Β–01

Δεν φαίνεται δυνατό

C–01

D–01

Λύση : για να διατηρηθεί η δυνατότητα αποκωδικοποίησης, αρκεί η συμμόρφωση με απευθείας ή αντίστροφηΣυνθήκες Fano . Ας πραγματοποιήσουμε έναν διαδοχικό έλεγχο των επιλογών 1, 3 και 4. Εάν καμία από τις επιλογές δεν είναι κατάλληλη, η σωστή απάντηση θα είναι η επιλογή 2 (δεν είναι δυνατή).

Επιλογή 1. Κωδικός: A - 00, B - 01, C - 011, D - 101 και E - 111. ΑπευθείαςΚατάσταση Fano δεν εκτελείται: ο κωδικός του χαρακτήρα "B" συμπίπτει με την αρχή του κωδικού του χαρακτήρα "C". Ο αντίστροφος κανόνας Fano δεν ισχύει: ο κωδικός του χαρακτήρα "B" συμπίπτει με το τέλος του κωδικού του χαρακτήρα "D". Η επιλογή δεν είναι κατάλληλη.

Επιλογή 3. Κωδικός: A - 00, B - 010, C - 01, D - 101, και E - 111. ΑπευθείαςΚατάσταση Fano δεν εκτελείται: ο κωδικός του χαρακτήρα "C" συμπίπτει με την αρχή του κωδικού του χαρακτήρα "B". Η αντίστροφη συνθήκη επίσης δεν ικανοποιείται: ο κωδικός του χαρακτήρα "C" συμπίπτει με το τέλος του κωδικού του χαρακτήρα "D". Η επιλογή δεν είναι κατάλληλη.

Επιλογή 4. Κωδικός: A - 00, B - 010, C - 011, D - 01 και E - 111. ΑπευθείαςΚατάσταση Fano δεν εκτελείται: ο κωδικός του χαρακτήρα "D" συμπίπτει με την αρχή του κωδικού των χαρακτήρων "B" και "C". Ωστόσο, τηρείται ο αντίστροφος κανόνας Fano: ο κωδικός του χαρακτήρα "D" δεν συμπίπτει με το τέλος του κωδικού όλων των άλλων χαρακτήρων. Για το λόγο αυτό, η επιλογή είναι κατάλληλη.

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

Απάντηση : 4

Κωδικός Huffman

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

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

1) 22162

2) 1020342

3) 2131453

4) 34017

Εξήγηση.

Πρώτα πρέπει να αναπαραστήσετε τα δεδομένα στην αριθμητική συνθήκη σε δυαδικό κώδικα:

100

Στη συνέχεια, κωδικοποιήστε την ακολουθία των γραμμάτων: WATERFALL - 010010001110010. Τώρα ας διαιρέσουμε αυτήν την παράσταση σε τρίδυμα από τα δεξιά προς τα αριστερά και ας μετατρέψουμε το σύνολο αριθμών που προκύπτει σε δεκαδικός κωδικός, μετά σε οκταδική (οκταδική αναπαράσταση είναι ίδια με τη δεκαδική όταν χωρίζεται με τριπλάσια)

010 010 001 110 010 - 22162.

№ 2. Για τη μετάδοση ενός μηνύματος μέσω ενός καναλιού επικοινωνίας που αποτελείται μόνο από χαρακτήρες A, B, C και D, χρησιμοποιείται κωδικοποίηση χαρακτήρα προς χαρακτήρα: A-00, B-11, B-010, D-011. Το μήνυμα μεταδίδεται μέσω του καναλιού επικοινωνίας: VBGAGV. Κωδικοποιήστε το μήνυμα με αυτόν τον κωδικό. Ελήφθη δυάδικος αριθμόςμετατροπή σε δεκαεξαδικό.

1) CBDADC

2) 511110

3) 5Β1Α

4) A1B5

Εξήγηση.

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

0101 1011 0001 1010 - 5 11 1 10 - 5В1А.

Η σωστή απάντηση αναφέρεται στον αριθμό 3

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

010

011

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

1) CDADBC

2) A7C4

3) 412710

4) 4С7А

Εξήγηση.

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

0100 1100 0111 1010 - 4 12 7 10 - 4С7А.

Η σωστή απάντηση αναγράφεται στον αριθμό 4.

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

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

1) 57414

2) 53414

3) 53412

4) 53012

Εξήγηση.

Κωδικός πρώτης γραμμής: 10101.

Κωδικός δεύτερης γραμμής: 11000.

Κωδικός τρίτης γραμμής: 01010.

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

101 011 100 001 010 - 53412.

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

000

110

001

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

1) baade

2) badde

3) μπάκντε

4) bacdb

Εξήγηση.

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

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

110 000 01 001 10 - b a c d e.

Η σωστή απάντηση αναγράφεται στον αριθμό 3.

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

1) 6543

2) 62926

3) 62612

4) 3456

Εξήγηση.

Το παράδειγμα δείχνει ότι 2 χαρακτήρες κωδικοποιούνται με 10 δυαδικά ψηφία (bit), εκχωρούνται 5 bit για κάθε ψηφίο. Η συνθήκη λέει ότι κάθε ψηφίο είναι γραμμένο σε έναν κωδικό μήκους 4 χαρακτήρων, πράγμα που σημαίνει ότι το πέμπτο ψηφίο μπορεί να παραλειφθεί.

Ας το αναλύσουμε δυαδική σημειογραφίασε ομάδες των 5 χαρακτήρων: 01100 01010 01001 00110. Απορρίπτουμε το τελευταίο ψηφίο σε κάθε πέντε και το μετατρέπουμε σε δεκαδικό συμβολισμό:

0110 0101 0100 0011 - 6 5 4 3.

Η σωστή απάντηση αναφέρεται στον αριθμό 1.

№ 7. Τα μηνύματα που περιέχουν μόνο 4 γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας - P, O, R, T. Για την κωδικοποίηση γραμμάτων, χρησιμοποιούνται κωδικές λέξεις 5 bit:

P - 11111, O - 11000, P - 00100, T - 00011.

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

Αυτή η ιδιότητα είναι σημαντική για την αποκρυπτογράφηση μηνυμάτων παρουσία παρεμβολών (υποθέτοντας ότι μεταδιδόμενα bitsμπορεί να παραμορφωθεί, αλλά να μην εξαφανιστεί). Ένα κωδικοποιημένο μήνυμα θεωρείται ότι λήφθηκε σωστά εάν το μήκος του είναι πολλαπλάσιο του 5 και κάθε πεντάδα διαφέρει από κάποια κωδική λέξη σε όχι περισσότερες από μία θέσεις. Σε αυτή την περίπτωση, πιστεύεται ότι το πέντε κωδικοποιεί το αντίστοιχο γράμμα. Για παράδειγμα, εάν ληφθεί το πέντε 00000, τότε θεωρείται ότι μεταδόθηκε το γράμμα P.

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

11011 11100 00011 11000 01110

00111 11100 11110 11000 00000

1) ΠΛΗΜΜΥΡΑ

2) ROTOR

3) ΑΞΙ

4) κανένα από τα μηνύματα δεν ελήφθη σωστά

Εξήγηση.

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

Αναλύοντας το πρώτο μήνυμα «11011 11100 00011 11000 01110», καταλήγουμε στο συμπέρασμα ότι λήφθηκε λάθος, αφού δεν υπάρχει λέξη που να διαφέρει από τη λέξη «01110» σε μία μόνο θέση.

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

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

A - 10010, B - 11111, C - 00101.

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

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

1) AVBB

2) xxxx

3) ABxB

4) AhhB

Εξήγηση.

Αποκωδικοποιούμε κάθε λέξη του μηνύματος. Η πρώτη λέξη: 10000 διαφέρει από το γράμμα Α σε μία μόνο θέση. Η δεύτερη λέξη: 10101 διαφέρει από το γράμμα Β μόνο σε μία θέση. Τρίτη λέξη: Το 11001 διαφέρει από οποιοδήποτε γράμμα σε περισσότερες από μία θέσεις. Η τέταρτη λέξη: 10111 διαφέρει από το γράμμα Β μόνο σε μία θέση.

Απάντηση: ABxB.

№ 9. Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα 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

Εξήγηση.

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

1) D=1: ο κωδικός γράμματος D είναι η αρχή όλων των κωδικών γραμμάτων που παρουσιάζονται, επομένως αυτή η επιλογή δεν είναι κατάλληλη.

2) D=0: ο κωδικός για το γράμμα D δεν είναι η αρχή ενός άλλου κωδικού, επομένως αυτή η επιλογή είναι κατάλληλη.

3) D=01: ο κωδικός για το γράμμα D δεν είναι η αρχή ενός άλλου κωδικού, επομένως αυτή η επιλογή είναι κατάλληλη.

4) D=10: ο κωδικός για το γράμμα D είναι η αρχή των κωδικών για τα γράμματα B και G, επομένως, αυτή η επιλογή δεν είναι κατάλληλη.

Έτσι, δύο επιλογές είναι κατάλληλες: 0 και 01. Το 0 είναι μικρότερο από το 01.

№ 10. Τα μηνύματα που περιέχουν μόνο 4 γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας:

Ε, Ν, Ο, Τ.

Σε οποιοδήποτε μήνυμα, τα περισσότερα γράμματα είναι O, το επόμενο πιο κοινό γράμμα είναι το E, μετά το N. Το γράμμα T είναι λιγότερο κοινό από οποιοδήποτε άλλο.

Για τη μετάδοση μηνυμάτων, πρέπει να χρησιμοποιήσετε έναν μη ομοιόμορφο δυαδικό κώδικα που επιτρέπει τη σαφή αποκωδικοποίηση. τα μηνύματα πρέπει να είναι όσο το δυνατόν πιο σύντομα. Ο κρυπτογράφος μπορεί να χρησιμοποιήσει έναν από τους κωδικούς που αναφέρονται παρακάτω. Ποιον κωδικό να επιλέξει;

1) E−0, N−1, O−00, T−11

2) O−1, N−0, E−01, T−10

3) E−1, N−01, O−001, T−000

4) O−0, N−11, E−101, T−100

Εξήγηση.

Ας επιλέξουμε κωδικούς για τους οποίους η συνθήκη Fano ικανοποιείται. Αυτοί είναι οι κωδικοί 3 και 4.

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

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

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

1) 7

2) 8

3) 9

4) 10

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

Εξήγηση.

Ας βρούμε για τα υπόλοιπα δύο σύμβολα τη συντομότερη παράσταση που ικανοποιεί τη συνθήκη Fano. Η κωδική λέξη 1 δεν μπορεί να χρησιμοποιηθεί, καθώς αυτό θα παραβίαζε τη συνθήκη Fano. Από τις διψήφιες κωδικές λέξεις, η λέξη 10 μπορεί να χρησιμοποιηθεί, αλλά οι λέξεις 11 και 01 δεν μπορούν να χρησιμοποιηθούν. Με αυτήν την κατασκευή κωδικών, είναι αδύνατο να επιλέξετε μια διψήφια κωδική λέξη για το τέταρτο σύμβολο. Επομένως, χρησιμοποιούμε μια τριψήφια λέξη, δηλαδή 111.

Έτσι, το μικρότερο δυνατό συνολικό μήκος και των τεσσάρων κωδικών λέξεων θα είναι 1 + 3 + 2 + 3 = 9.

Η σωστή απάντηση αναγράφεται στον αριθμό 3.

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

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

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

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

1) Α:0, Β:10, Γ:110, Δ:111

2) Α:0, Β:10, Γ:01, Δ:11

3) A:1, B:01, C:011, D:001

4) Α:00, Β:01, Γ:10, Δ:11

Εξήγηση.

Τα 2 και 3 δεν είναι κατάλληλα, αφού περιέχουν ζεύγη κωδικών, εκ των οποίων ο ένας είναι η αρχή του άλλου.

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

Το μήκος των μηνυμάτων κατά τη χρήση του τέταρτου κωδικού θα είναι ίσο με .

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