Le code répond-il à la condition fano ? Nous nous préparons à l'examen d'État unifié en informatique. Etat Fano. Application pratique de la condition de Fano
Considérons une autre table de codes : A B C D D 000 01 10 011 100 Ici la condition de Fano n'est pas satisfaite, puisque le code de la lettre B (01) est le début du code de la lettre G (011), et le code de la lettre D (100) commence par le code de la lettre B ( 10). Cependant, on peut noter que la condition de Fano « inverse » est satisfaite : aucun code n'est la fin d'un autre code (un tel code est appelé suffixe). Par conséquent, le message codé peut être décodé sans ambiguïté depuis la fin. Par exemple, considérons la chaîne 011000110110. Dernière lettre dans ce message il ne peut y avoir que B (code 10) : B 0110001101 10 La deuxième lettre à partir de la fin est B (code 01) : B B 01100011 01 10 et ainsi de suite : B D G B B 01 100 011 01 10.
Diapositive 26 de la présentation "Méthodes de codage des informations".Télécharger la présentation
Méthodes de codagerésumé d'autres présentations "Codage binaire" - Nombres. Codage binaire informations textuelles . Tableau d'encodage. Volume d'information du texte. Codage binaire dans un ordinateur. Codage des informations textuelles. Table de codes étendue. Symbole. Code binaire unique. Lettre alphabet latin
. Utiliser le système binaire. Ordinateurs. « Encodage des informations en code binaire » - Définition. Systèmes numériques. Système binaire Compte. Codage. Encodage des informations. Donnez des exemples de codage. Système de nombres décimaux. La signification du nombre. La signification d'un nombre dépend de sa position. Alphabet. Langues. romain système non positionnel
. Codage binaire. Qu'est-ce qui est crypté ici ? « Méthodes de codage » - Numéro de colonne. Lettre texte source . Encodage des informations. Méthodes de codage des informations. Décodez les informations. Informations transmises . Dans le monde des codes. Codage automatique. Méthode de coordonnées. Avantages et inconvénients. Variété de codes. Garçon. Comment peux-tu appeler carnet de notes du point de vue du stockage de l'information. Texte codé. Support d'informations. Mots-clés
« Méthodes de codage des informations » - Dans la mémoire de l'ordinateur, les informations sont présentées sous forme de code binaire. Encodage et décodage. Vous pouvez coder des informations. Méthodes de codage des informations. Créons une simple table de codes. Pour connaître le mot crypté, ne prenez que les premières syllabes. Ce que Lom a lu sur les drapeaux de la goélette venant en sens inverse. Trouver propre façon lettres de codage de l'alphabet russe. Missions. Informations cryptées. Louis Braille a inventé manière spéciale présentation des informations.
« Méthodes de codage de l'information » - Codage binaire dans un ordinateur. Quantité d'informations. Télégraphe optique Shapp. Etat Fano. Quel code utiliser. Message reçu. "Oui" ou "Non". Le premier télégraphe. Méthodes de codage des informations. Enregistrement des informations. Pourquoi un codage binaire ? Drapeaux de signalisation. Codage. Encodage et décodage. Encodage des informations. Sélection de la méthode d'encodage. Types d'informations. Combien d'options ?
La leçon est consacrée à la façon de résoudre la tâche 5 de l'examen d'État unifié en informatique
Le 5ème sujet est caractérisé par des tâches niveau de base difficulté, temps d'exécution – environ 2 minutes, score maximum – 1
- Codage- est la présentation d'informations sous une forme pratique pour leur stockage, leur transmission et leur traitement. La règle pour convertir les informations en une telle représentation s'appelle code.
- Le codage se produit uniforme Et inégal:
- avec un codage uniforme, tous les symboles correspondent à des codes de même longueur ;
- à codage inégal différents personnages correspondent à des codes de longueurs différentes, ce qui rend le décodage difficile.
Exemple: Chiffrons les lettres A, B, C, D en utilisant codage binaire code uniforme et comptez le nombre de messages possibles :
Nous avons donc code uniforme, parce que la longueur de chaque mot de passe est la même pour tous les codes (2).
Encodage et décryptage des messages
Décodage (décodage)- c'est la restauration d'un message à partir d'une séquence de codes.
Pour résoudre les problèmes de décodage, vous devez connaître la condition de Fano :
Etat Fano : aucun mot de code ne doit pas être le début d'un autre mot de passe (ce qui garantit que les messages sont décodés sans ambiguïté depuis le début)
Code préfixe est un code dans lequel aucun mot de code ne coïncide avec le début d'un autre mot de code. Les messages utilisant ce code sont décodés sans ambiguïté.
Un décodage sans ambiguïté est fourni :
Résoudre 5 tâches d'examen d'État unifié
Examen d'État unifié 5.1 : Pour coder les lettres O, B, D, P, A, nous avons décidé d'utiliser la représentation binaire des nombres 0, 1, 2, 3 et 4, respectivement (avec conservation d'un zéro insignifiant dans le cas d'un simple- représentation numérique).
Encodez ainsi la séquence de lettres CASCADE et écrivez le résultat en code octal.
✍Solution :
- Convertissons les nombres en codes binaires et associons-les à nos lettres :
Résultat: 22162
Décision relative à l'examen d'État unifié de cette mission en informatique, vidéo :
Considérons une autre analyse 5 Travaux d'examen d'État unifié:
Examen d'État unifié 5.2 : Pour 5 lettres de l'alphabet latin, leurs codes binaires sont précisés (pour certaines lettres - à partir de deux bits, pour certaines - à partir de trois). Ces codes sont présentés dans le tableau :
| un | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
Quel ensemble de lettres est codé par la chaîne binaire 1100000100110 ?
✍Solution :
- Tout d’abord, nous vérifions la condition de Fano : aucun mot de code n’est le début d’un autre mot de code. La condition est vraie.
- On casse le code de gauche à droite selon les données présentées dans le tableau. Traduisons-le ensuite en lettres :
✎ 1ère solution :
Résultat: b a c d e.
✎ 2ème solution :
110
000 01
001 10
Résultat: b a c d e.
De plus, vous pouvez regarder une vidéo de la solution à ce devoir d'examen d'État unifié en informatique :
Résolvons la 5ème tâche suivante :
Examen d'État unifié 5.3 :
Pour transmettre des numéros sur un canal bruyant, un code de contrôle de parité est utilisé. Chaque chiffre est écrit en représentation binaire, avec des zéros non significatifs ajoutés à une longueur de 4, et la somme de ses éléments modulo 2 est ajoutée à la séquence résultante (par exemple, si nous transmettons 23, nous obtenons la séquence 0010100110).
Déterminez quel numéro a été transmis sur le canal sous la forme 01100010100100100110.
✍Solution :
- Considérons exemple de l'énoncé du problème :
Répondre: 6 5 4 3
Vous pouvez regarder une vidéo de la solution à ce devoir d'examen d'État unifié en informatique :
Examen d'État unifié 5.4 :
Pour coder une certaine séquence composée des lettres K, L, M, N, ils ont décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Le mot de code 0 a été utilisé pour la lettre H et le mot de code 10 pour la lettre K.
Quelle est la longueur totale la plus courte possible des quatre mots de code ?
✍Solution :
✎ 1 solution possible basé sur des conclusions logiques :
- Trouvons les mots de passe les plus courts possibles pour toutes les lettres.
- Mots de code 01 Et 00 ne peut pas être utilisé, car alors la condition de Fano est violée (ils partent de 0, et 0 - Ce N).
- Commençons par des mots de passe à deux chiffres. Prenons pour la lettre L mot de code 11 . Ensuite, il est impossible de sélectionner un mot de code pour la quatrième lettre sans violer la condition de Fano (si vous prenez ensuite 110 ou 111, alors ils commencent par 11).
- Cela signifie que des mots de code à trois chiffres doivent être utilisés. Encodons les lettres L Et M mots de code 110 Et 111 . La condition de Fano est satisfaite.
✎ Option 2:
(N) -> 0 -> 1 caractère (K) -> 10 -> 2 caractères (L) -> 110 -> 3 caractères (M) -> 111 -> 3 caractères Répondre: 9
Examen d'État unifié en informatique 5 tâche 2017 FIPI option 2 (édité par Krylov S.S., Churkina T.E.) :
Les messages contenant seulement 4 lettres sont transmis via le canal de communication : A, B, C, D ; Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres A, B, C, les mots de code suivants sont utilisés : A : 101010, B : 011011, C : 01000.
Г, auquel le code permettra un décodage sans ambiguïté. le plus petitvaleur numérique.
✍Solution :
- Les plus petits codes pourraient ressembler à 0 Et 1 (un seul chiffre). Mais cela ne satisferait pas la condition de Fano ( UN commence par un - 101010 , B commence à zéro - 011011 ).
- Le prochain plus petit code serait un mot de deux lettres 00 . Puisqu'il ne s'agit d'un préfixe d'aucun des mots de passe présentés, alors G = 00.
Résultat: 00
Examen d'État unifié en informatique 5 tâche 2017 FIPI option 16 (édité par Krylov S.S., Churkina T.E.) :
Pour coder une certaine séquence composée des lettres A, B, C, D et D, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. Le code utilisé était : A - 01, B - 00, C - 11, D - 100.
Indiquez avec quel mot de code la lettre D doit être codée. Longueur ce mot de code doit être moins de tous les possibles. Le code doit satisfaire la propriété décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez le code avec la valeur numérique la plus basse.
✍Solution :
Résultat: 101
Une analyse plus détaillée de la leçon peut être vue dans la vidéo de l'examen d'État unifié en informatique 2017 :
Examen d'État unifié en informatique 5 tâche 2017 FIPI option 17 (Krylov S.S., Churkina T.E.) :
Pour coder une certaine séquence composée des lettres A, B, C, D, D et E, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. . Le code utilisé était : A - 0, B - 111, C - 11001, D - 11000, D - 10.
Indiquez avec quel mot de code la lettre E doit être codée. La longueur de ce mot de code doit être la plus courte possible. Le code doit satisfaire à la propriété de décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez le code avec la valeur numérique la plus basse.
✍Solution :
1 - ne convient pas (toutes les lettres sauf A commencent par 1) 10 - ne convient pas (correspond au code D) 11 - ne convient pas (le début des codes B, C et D) 100 - ne convient pas (le code D - 10 - est le début de ce code) 101 - ne convient pas (le code D - 10 - est le début de ce code) 110 - ne convient pas (le début des codes B et D) 111 - ne convient pas (correspond au code B) 1000 - ne convient pas ( le code D - 10 - est le début de ce code) 1001 - ne convient pas (le code D - 10 - est le début de ce code) 1010 - ne convient pas (le code D - 10 - est le début de ce code) 1011 - ne convient pas (le code D - 10 - est le début de ce code) 1100 - ne convient pas (début des codes B et D) 1101 - convient
Résultat: 1101
Plus solution détaillée Cette tâche est présentée dans le didacticiel vidéo :
Tâche 5. Version démo de l'examen d'État unifié 2018 en informatique (FIPI) :
Des messages cryptés contenant seulement dix lettres sont transmis sur le canal de communication : A, B, E, I, K, L, R, S, T, U. Un code binaire impair est utilisé pour la transmission. Les mots de code sont utilisés pour neuf lettres. 
Spécifiez le mot de code le plus court pour la lettre B, sous lequel le code satisfera la condition de Fano. S'il existe plusieurs de ces codes, indiquez le code avec le plus petit valeur numérique.
✍Solution :
Résultat: 1100
Pour une solution détaillée à cette 5ème tâche de la version démo de l'examen d'État unifié 2018, regardez la vidéo :
Tâche 5_9. Options d'examen modèle 2017. Option 4 (Krylov S.S., Churkina T.E.) :
Des messages cryptés contenant seulement quatre lettres sont transmis sur le canal de communication : A, B, C, D ; Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres UN, B, DANS mots de code utilisés :
A : 00011 B : 111 C : 1010
Spécifiez le mot de code le plus court pour la lettre G, dans lequel le code permettra un décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez le code avec le plus petit valeur numérique.
✍Solution :
Résultat: 00
Tâche 5_10. Option de formation n°3 du 10/01/2018 (FIPI) :
Les messages contenant uniquement des lettres sont transmis sur le canal de communication : A, E, D, K, M, R; Pour la transmission, un code binaire satisfaisant la condition de Fano est utilisé. Connu pour être utilisé codes suivants:
E – 000 D – 10 K – 111
Spécifiez la longueur de message codé la plus courte possible DEDMAKAR.
Dans votre réponse, écrivez un nombre – le nombre de bits.
✍Solution :
D E D M A K A R 10 000 10 001 01 111 01 110
Résultat: 20
Voir la solution à la tâche :
Tâche 31. Codes inégaux. Etat de Fano
5-54. Pour coder une certaine séquence composée des lettres A, B, C, D et D, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. Pour les lettres A, B, C et D, les mots de code suivants ont été utilisés : A - 001, B - 010, C - 000, D - 011.
Indiquez quel mot de code parmi ceux répertoriés ci-dessous peut être utilisé pour coder la lettre D.
Le code doit satisfaire à la propriété de décodage sans ambiguïté. Si plusieurs mots de passe peuvent être utilisés, saisissez le plus court.
1) 00 2) 01 3) 0000 4) 101
5-85. Pour coder une certaine séquence composée des lettres U, CH, E, N, I et K, un code de préfixe binaire impair est utilisé. Voici le code : U – 000, Ch – 001, E – 010, N – 100, I – 011, K – 11. Est-il possible de raccourcir la longueur du mot de code pour l'une des lettres afin que le code reste reste un préfixe ? Les codes des lettres restantes ne doivent pas changer. Sélectionner bonne option répondre.
Note. Un code préfixe est un code dans lequel aucun mot de code n’est le début d’un autre ; De tels codes permettent de décoder sans ambiguïté la séquence binaire résultante.
1) le mot de code de la lettre E peut être raccourci à 01
2) le mot de code de la lettre K peut être réduit à 1
3) le mot de code pour la lettre N peut être réduit à 10
4) c'est impossible
5-94. Pour coder une certaine séquence composée des lettres A, B, C, D, ils ont décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Pour la lettre A, nous avons utilisé le mot de code 1, pour la lettre B, nous avons utilisé le mot de code 011. Quelle est la longueur totale la plus courte possible des quatre mots de code ?
5-74. Les messages contenant seulement 4 lettres sont transmis sur le canal de communication : E, H, O, T. Dans tout message, la plupart des lettres sont O, la lettre suivante la plus courante est E, puis N. La lettre T est moins courante que toute autre. . Pour transmettre des messages, vous devez utiliser un code binaire non uniforme qui permet un décodage sans ambiguïté ; les messages doivent être aussi courts que possible. Le cryptographe peut utiliser l’un des codes listés ci-dessous. Quel code choisir ?
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. Les messages sont transmis via le canal de communication, dont chacun contient 15 lettres A, 10 lettres B, 6 lettres C et 4 lettres G (il n'y a pas d'autres lettres dans les messages). Chaque lettre est codée sous forme de séquence binaire. Lors du choix du code, deux exigences ont été prises en compte :
a) aucun mot de code n'est le début d'un autre (cela est nécessaire pour que le code permette un décodage sans ambiguïté) ;
b) la longueur totale du message codé doit être aussi courte que possible.
Quel code parmi les suivants devriez-vous choisir pour coder les lettres A, B, C et D ?
1) A:1, B:01, C:001, D:111
2) A:1, B:01, C:10, D:111
3) A:00, B:01, C:10, D:11
4) A:100, B:101, C:11, D:0
5-102. Il y a 10 lettres différentes dans le message. Lors de sa transmission, un code de préfixe binaire impair est utilisé. Les codes de trois lettres sont connus : 11, 100, 101. Les codes des sept lettres restantes sont de même longueur. Quelle est la longueur totale minimale des 10 mots de passe ?
5-104. Le message contient 50 lettres A, 30 lettres B, 20 lettres C et 5 lettres G. Lors de sa transmission, un code préfixe binaire impair a été utilisé, ce qui a permis d'obtenir la longueur minimale du message codé. Comment ça se passe en morceaux ?
Les messages contenant seulement cinq lettres sont transmis sur le canal de communication : A, B, C, D, E. Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres A, B, C, les mots de code suivants sont utilisés : A – 111, B – 0, C – 100.
Spécifiez le mot de code le plus court pour la lettre D, auquel le code permettra un décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez le code avec la valeur numérique la plus basse.
9-1-23. Après avoir converti le raster 256 couleurs fichier graphique au format 16 couleurs, sa taille a été réduite de 15 Ko. Quelle était la taille fichier source en Ko ?
9-1-25. Après avoir converti le fichier graphique raster, son volume a diminué de 1,5 fois. Combien de couleurs y avait-il initialement dans la palette, si après conversion elle a été obtenue image tramée la même résolution dans une palette de 16 couleurs ?
13-37. Lors de votre inscription à système informatique Chaque utilisateur reçoit un identifiant composé de 8 caractères, dont le premier et le dernier sont l'une des 18 lettres, et le reste sont des chiffres (10 sont autorisés chiffres décimaux). Chacun de ces identifiants dans programme informatique est écrit avec le minimum possible et le même nombre entier d'octets (le codage caractère par caractère est utilisé ; tous les nombres sont codés avec le même nombre minimum de bits possible, toutes les lettres sont également codées avec le même nombre minimum possible de bits. bits). Déterminez la quantité de mémoire en octets allouée par ce programme pour enregistrer 500 mots de passe.
13-38. Lors de son inscription dans le système informatique utilisé pour l'Olympiade par équipe, chaque élève se voit remettre identifiant unique– un nombre entier de 1 à 1000. Le même nombre minimum possible de bits est utilisé pour stocker chaque identifiant. L'ID d'équipe se compose d'ID d'étudiant enregistrés séquentiellement et de 8 bits supplémentaires. Le système utilise le même nombre minimal d'octets pour enregistrer chaque ID de commande. Toutes les équipes ont un nombre égal de participants. Combien y a-t-il de membres dans chaque équipe s'il faut 180 octets pour stocker les identifiants des 20 équipes participantes ?
13-50. Lors de son inscription dans un système informatique, chaque utilisateur reçoit un mot de passe composé de 15 caractères et contenant uniquement les caractères du jeu de 12 caractères : A, B, C, D, E, F, G, H, K, L, M, N. Dans la base de données Les données permettant de stocker des informations sur chaque utilisateur se voient attribuer le même nombre entier d'octets minimum possible. Dans ce cas, le codage caractère par caractère des mots de passe est utilisé, tous les caractères sont codés avec le même nombre de bits minimum possible. En plus du mot de passe lui-même, des informations supplémentaires sont stockées dans le système pour chaque utilisateur, pour lesquelles un nombre entier d'octets est alloué ; ce numéro est le même pour tous les utilisateurs. Pour stocker des informations sur 20 utilisateurs, 300 octets étaient nécessaires. Combien d'octets sont alloués au stockage Informations Complémentairesà propos d'un utilisateur ? Dans votre réponse, notez uniquement un nombre entier - le nombre d'octets.
16-165. Signification expression arithmétique: 9 22 + 3 66 – 18 écrit dans le système numérique base 3 Combien y a-t-il de chiffres « 2 » dans cette notation ?
La question se pose naturellement : existe-t-il des codes non uniformes pour lesquels le décodage est toujours unique ? Oui, ils existent.
Robert Fano formulé ce qui suit état suffisant que le code a un décodage sans ambiguïté : aucun mot de code n'est le début d'un autre mot de code. Si cette condition est remplie, il n'y aura aucun problème de décodage.
Laisser Un 1, Un 2 Et Un 3- les mots au-dessus d'un alphabet sont tels que Un 1=Un 2 Un 3, c'est Un 1 obtenu de Un 2 simplement en y ajoutant un mot Un 3(mots Un 2 ou Un 3 il peut s'agir de caractères uniques). Nommons le mot Un 2, qui est la partie initiale du mot Un 1, préfixe mots Un 1. Par exemple, pour le mot 11101101 les préfixes seront des mots 1110110 , 111011 , 11101 , 1110 , 111 , 11 , 1 .
Alors la condition de Fano pour les codes peut être formulée comme suit :
Aucun mot de code n'est le préfixe d'un autre mot de code.
Les codes qui satisfont à la condition de Fano sont appelés préfixe. Ainsi, si le code est préfixé, cela permet un décodage sans ambiguïté.
Par exemple, un code composé de mots de code {0, 10, 11} , est un préfixe et la séquence de codes suivante 01001101110 peut être décomposé en mots de code de la seule manière : 0 10 0 11 0 11 10 .
Un code composé de mots de code {0, 10, 11, 100} , n'est pas préfixé et ne permet pas un décodage sans ambiguïté. En effet, une même séquence peut être divisée en mots de code de différentes manières: 0 10 0 11 0 11 10 ou 0 100 11 0 11 10 .
Il est important de noter que la condition de Fano n’est qu’une condition suffisante pour un décodage sans ambiguïté des codes, mais n’est pas une condition nécessaire.
Par exemple, un code simple composé de seulement deux mots de code {1, 10} , n'est évidemment pas un préfixe, mais il donne un décodage sans ambiguïté de toute séquence de code obtenue par codage avec ce code. En effet, dans une telle séquence, deux zéros ne peuvent pas apparaître côte à côte. Et puis nous remplaçons chaque zéro par une unité devant lui par l'image inverse du deuxième mot de code, et tous les autres par l'image inverse du premier mot, ce sera un décodage sans ambiguïté.
Il y en a d'autres, moins codes simples, ayant la même propriété. Par exemple, code {01,10,011} n'est pas non plus un préfixe, mais a un décodage sans ambiguïté (essayez de le prouver vous-même).
Comment peut-on déterminer si un code est décodable de manière unique si la condition de Fano n'est pas satisfaite pour celui-ci ? Vous pouvez utiliser la méthode suivante.
Laisse le mot Un 2 est préfixe mots Un 1. Alors Un 1=Un 2 Un 3, Où Un 3 un mot, la dernière partie d'un mot Un 1. Appelons Un suffixe 3 quelques mots Un 1 Et Un 2, dont l'un est un préfixe de l'autre, et la paire elle-même Un 1 Et Un 2 appelons préfixe.
Considérons toutes les paires de préfixes de mots de code dans un code donné et construisons à partir d'elles l'ensemble de tous les suffixes. Ensuite, nous considérerons toutes les paires de mots préfixes, dont l'un est un mot de code et l'autre est un suffixe, et nous construirons des suffixes pour eux, en élargissant l'ensemble des suffixes. Continuons ce processus jusqu'à ce que de nouveaux suffixes cessent d'apparaître. Un code est décodable de manière unique si et seulement si aucun suffixe ne correspond à un mot de code.
Par exemple, pour le code {01,10,011} il y aura beaucoup de suffixes {1,0,11} . Pas un seul suffixe ici ne correspond à un mot de code, on peut donc affirmer que ce code est décodable de manière unique.
Tâche 1. Déterminez si les codes suivants ont la propriété de décodabilité unique : a) {110, 11, 100, 00, 10} b) {100, 001, 101, 1101, 11011} .
Les séquences de décodage obtenues avec des codes sans préfixe nécessitent une analyse plus complexe que pour les codes avec préfixe. Codes de préfixe parfois appelé instantané(instantanément décodables), puisque pour eux, lors de la lecture d'une séquence de code, la fin du mot de code est reconnue immédiatement après avoir atteint le symbole final du mot. C'est l'avantage des codes préfixes.
Version de démonstration de l'examen d'État unifié 2019 – tâche n°5
Pour coder une certaine séquence composée des lettres A, B, C, D, D, E, nous avons décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Pour la lettre A, le mot de code 0 a été utilisé ; pour la lettre B – mot de code 10. Quelle est la plus petite somme possible des longueurs des mots de code pour les lettres B, D, D, E ?
Note. La condition de Fano signifie qu’aucun mot de code n’est le début d’un autre mot de code. Cela permet de décrypter sans ambiguïté les messages cryptés.
Solution:
Répondre:
Version de démonstration de l'examen d'État unifié 2018 – tâche n°5
Des messages cryptés contenant seulement dix lettres sont transmis sur le canal de communication : A, B, E, I, K, L, R, S, T, U. Un code binaire impair est utilisé pour la transmission. Les mots de code sont utilisés pour neuf lettres.
Indiquez le mot de code le plus court pour la lettre B tel que le code satisfasse à la condition de Fano. S'il existe plusieurs de ces codes, indiquez le code avec la valeur numérique la plus basse. Note. La condition de Fano signifie qu’aucun mot de code n’est le début d’un autre mot de code. Cela permet de décrypter sans ambiguïté les messages cryptés.
Solution:
Réponse : 1100
Pour coder une certaine séquence composée des lettres A, B, C, D, D, E, nous avons décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Pour la lettre A, le mot de code 0 a été utilisé ; pour la lettre B – mot de code 10. Quelle est la plus petite somme possible des longueurs des six mots de code ?
Note. La condition de Fano signifie qu’aucun mot de code n’est le début d’un autre mot de code. Cela permet de décrypter sans ambiguïté les messages cryptés.
Version de démonstration de l'examen d'État unifié 2017 - tâche n°5
Solution:
Pour trouver des mots de code, nous utiliserons ce tableau.
Si les codes des lettres restantes commencent par 0, le code de la lettre A=0 sera le début de leurs codes, cette option n'est donc pas adaptée. Si le code B = 10, les codes des lettres B, D, D, E commencent par 11. Pour en avoir 4 différents codes, vous devez utiliser des codes composés de 4 caractères (1111, 1110, 1101, 1100).
| 0 | 1 | ||||
| 1 | |||||
| 1 | 0 | ||||
| 1 | 0 | 1 | 0 | ||
A - 0 (1 caractère)
B - 10 (2 caractères)
B - 1100 (4 caractères)
G-1101 (4 caractères)
D - 1110 (4 caractères)
E-1111 (4 caractères)
1+2+4+4+4+4 = 19
Réponse : 19
Version de démonstration de l'examen d'État unifié 2016 – tâche n°5
Les messages contenant seulement quatre lettres sont transmis via le canal de communication : P, O, S, T ; Pour la transmission, un code binaire est utilisé qui permet un décodage sans ambiguïté. Pour les lettres T, O, P, les mots de code suivants sont utilisés : T : 111, O : 0, P : 100.
Spécifiez le mot de code le plus court pour la lettre C, auquel le code permettra un décodage sans ambiguïté. S'il existe plusieurs de ces codes, indiquez le code avec la valeur numérique la plus basse.
Solution:
Pour trouver des mots de code, nous utiliserons ce schéma.
Si les codes des lettres restantes commencent par 0 , code lettre À PROPOS=0 sera le début de leurs codes, cette option ne convient donc pas. Depuis la lettre code P.=100 , et le code de la lettre T =111 , puis la lettre AVEC ne peut pas commencer ni se terminer par ces chiffres.
Réponse : 101
Pour coder un message composé uniquement des lettres A, B, C et D, un code binaire de longueur impaire est utilisé :
Si vous codez ainsi la séquence de caractères GAVBGV et écrivez le résultat dans code hexadécimal, alors il s'avérera :
1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16
Solution:
GAVBGV = 0110001011011010
| 0110 | 0010 | 1101 | 1010 |
| 6 | 2 | D | UN |
Réponse : 4
Une image raster en noir et blanc est codée ligne par ligne, en commençant par la gauche coin supérieur et se terminant dans le coin inférieur droit. Lors de l'encodage, 1 représente le noir et 0 représente le blanc.
Pour des raisons de compacité, le résultat a été écrit en système octal Compte. Sélectionner entrée correcte code.
1) 57414 2) 53414 3) 53412 4) 53012
Solution:
| 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 |
Réponse : 3
Pour transmettre des numéros sur un canal bruyant, un code de contrôle de parité est utilisé. Chacun de ses chiffres est écrit en représentation binaire, avec des zéros non significatifs ajoutés sur une longueur de 4, et la somme de ses éléments modulo 2 est ajoutée à la séquence résultante (par exemple, si nous transmettons 23, nous obtenons la séquence 0010100110). Déterminer quel numéro a été transmis sur le canal sous la forme 01100010100100100110 ?
1) 6543 2) 62926 3) 62612 4) 3456
Solution:
01100010100100100110
| 01100 | 01010 | 01001 | 00110 |
| 6 | 5 | 4 | 3 |
Réponse : 1
Pour coder les lettres O, L, A, Z, K, des codes binaires de nombres 0, 1, 2, 3 et 4 sont utilisés respectivement (avec la préservation d'un zéro insignifiant dans le cas d'une représentation à un chiffre). Si vous encodez ainsi la séquence de caractères BARRIER et écrivez le résultat en code hexadécimal, vous obtiendrez :
1) 4531253 2) 9876 3) E832 4) 238E
Solution:
| À PROPOS | L | UN | Z | À |
| 0=00 | 1=01 | 2=10 | 3=11 | 4=100 |
BARRIÈRE = 1110100000110010
| 1110 | 1000 | 0011 | 0010 |
| E | 8 | 3 | 2 |
Réponse : 3
Pour transmettre un message sur un canal de communication composé uniquement des lettres A, B, C, D, ils ont décidé d'utiliser un code de longueur inégale : A=00, B=11, C=100. Comment la lettre G doit-elle être codée pour que la longueur du code soit minimale et que le message codé puisse être divisé sans ambiguïté en lettres ?
1) 010 2) 0 3) 01 4) 011
Solution:
A=00, B=11, C=100, D=?
Réponse : 3
Pour coder une certaine séquence composée des lettres A, B, C, D et D, nous avons décidé d'utiliser un code binaire non uniforme, qui nous permet de décoder sans ambiguïté la séquence binaire apparaissant du côté réception du canal de communication. Pour les lettres A, B, C et D, les mots de code suivants ont été utilisés : A - 111, B - 110, C - 101, D - 100.
Indiquez quel mot de code parmi ceux répertoriés ci-dessous peut être utilisé pour coder la lettre D.
Le code doit satisfaire à la propriété de décodage sans ambiguïté. Si plusieurs mots de passe peuvent être utilisés, saisissez le plus court.
1) 1 2) 0 3) 01 4) 10
Solution:
A-111, B-110, C-101, D-100, D-?
Réponse : 2
Les messages contenant seulement 4 lettres sont transmis sur le canal de communication : A, B, C, D. Pour coder les lettres A, B, C, des mots de code de 5 bits sont utilisés : A - 10110, B - 11000, C - 00101. Pour cet ensemble de codes, les mots ont la propriété suivante : deux mots quelconques de l'ensemble diffèrent sur au moins trois positions. Cette propriété est importante pour décrypter les messages en présence d'interférences. Lequel des mots de code suivants peut être utilisé pour la lettre G afin que la propriété spécifiée soit valable pour les quatre mots de code ?
1) 01110 2) 01011 3) 10001 4) aucun des mots ci-dessus ne convient
Solution:
1) 01 110 : A - 10 110 - ne diffèrent pas sur au moins trois positions
2) 01011 : A - 101 10, B - 1 1000, C - 0010 1 - diffèrent sur au moins trois positions
Réponse : 2
Un code à 5 bits est utilisé pour transmettre des données sur un canal de communication. Le message contient uniquement les lettres A, B et C, qui sont codées avec les mots de code suivants :
A-10001, B-01101, C-10110.
Il peut y avoir des interférences pendant la transmission. Vous pouvez néanmoins tenter de corriger certaines erreurs. Deux d'entre eux trois codes les mots diffèrent les uns des autres dans au moins trois positions. Par conséquent, si une erreur s’est produite dans au plus une position lors de la transmission d’un mot, il est alors possible de deviner quelle lettre a été transmise. (Ils disent que « le code corrige une erreur. ») Par exemple, si le mot de code 01111 est reçu, on considère que la lettre B a été transmise (la différence avec le mot de code pour B n'est que dans une position ; pour. d'autres mots de code, il y a plus de différences.) Si le mot de code reçu Si le mot diffère des mots de code pour les lettres A, B, C dans plus d'une position, on considère qu'une erreur s'est produite (elle est indiquée par ' x').
Message reçu 00110 11101 11000 11001. Décodez ce message - sélectionnez l'option correcte.
1) VBxx 2) VBVA 3) xxxx 4) VBxA
Solution:
| 00110 | 11101 | 11000 | 11001 |
| B=1 0110 | B=0 1101 | x | A=10 001 |
Réponse : 4
Pour coder une certaine séquence composée des lettres A, B, C, D et D, un code binaire non uniforme est utilisé, ce qui permet de décoder sans ambiguïté la séquence binaire résultante. Voici le code : A – 1 ; B-0100 ; B-000 ; G-011 ; D – 0101. Il est nécessaire de réduire la longueur du mot de code pour l'une des lettres afin que le code puisse toujours être décodé sans ambiguïté. Les codes des lettres restantes ne doivent pas changer. Lequel de les méthodes ci-dessus est-ce que cela peut être fait ?
1) pour la lettre G – 11 2) pour la lettre B – 00 3) pour la lettre G – 01 4) c'est impossible
Solution:
Réponse : 2
Pour coder une certaine séquence composée des lettres A, B, C, D, ils ont décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Pour la lettre A, nous avons utilisé le mot de code 1, pour la lettre B, nous avons utilisé le mot de code 011. Quelle est la longueur totale la plus courte possible des quatre mots de code ?
1) 7 2) 8 3) 9 4) 10
Solution:
A-1, B-011, B-00, G-010
Réponse : 9
Les messages sont transmis via le canal de communication, dont chacun contient 15 lettres A, 10 lettres B, 6 lettres C et 4 lettres G (il n'y a pas d'autres lettres dans les messages). Chaque lettre est codée sous forme de séquence binaire. Lors du choix du code, deux exigences ont été prises en compte :
a) aucun mot de code n'est le début d'un autre (cela est nécessaire pour que le code permette un décodage sans ambiguïté) ;
b) la longueur totale du message codé doit être aussi courte que possible.
Quel code parmi les suivants devriez-vous choisir pour coder les lettres A, B, C et D ?
1) A:1, B:01, C:001, D:111
2) A:1, B:01, C:10, D:111
3) A:00, B:01, C:10, D:11
4) A:100, B:101, C:11, D:0
Solution:
Aucun des deux mots de code n’est le début d’un autre : UN c'est le début G dans les 1ère et 2ème options.
La longueur totale du message codé doit être aussi courte que possible.
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
Réponse : 3
Par le canal de communication en utilisant l'uniforme code binaire des messages contenant seulement 4 lettres P, R, S, T sont transmis. Chaque lettre a son propre mot de code, et pour un ensemble de mots de code, la propriété suivante est satisfaite : deux mots quelconques de l'ensemble diffèrent sur au moins trois positions. Cette propriété est importante pour décrypter les messages en présence d'interférences. Pour coder les lettres P, P, C, des mots de code de 5 bits sont utilisés : P : 01111, P : 00001, C : 11000. Le code de 5 bits pour la lettre T commence par 1 et se termine par 0. Déterminez le mot de code pour la lettre T.
Solution:
S: 1 1000
Tél. : 1 011 0 (T commence par 1 et se termine par 0)
S et T : 2 lettres sont identiques, cela signifie que les 3 lettres restantes doivent être différentes.
Répondre: 1 0110