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. Code préfixe– il s’agit d’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, le mot de code 1 a été utilisé, pour la lettre B, le mot de code 011 a été utilisé. 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 celui avec le plus petit valeur numérique.

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 chiffres décimaux sont autorisés). 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 ?

Bonjour! Je m'appelle Alexander Georgievich et je suis un tuteur professionnel à Moscou en informatique et en programmation. Avez-vous rencontré un problème lié au codage et ne savez-vous pas quel algorithme permet de le résoudre ? Vous devez de toute urgence vous rencontrerEtat de Fano, et inscrivez-vous également à des cours particuliers avec moi. Dans mes cours, je me concentre sur la résolution d'exercices thématiques simples et complexes.

Quelle est la signification de la condition directe de Fano ?

Etat de Fano du nom de son créateur, le scientifique italo-américain Robert Fano. La condition est nécessaire dans la théorie du codage lors de la construction d’un code à terminaison automatique. Compte tenu de la terminologie différente, un tel code est appelé code préfixe.

Cette condition peut être formulée ainsi : « aucun mot de code ne peut servir de début à un autre mot de code».

D'un point de vue mathématique, la condition peut être formulée comme suit : « si le code contient le motB, puis pour toute chaîne non videLe mot C BC n'existe pas dans le code».

Quelle est la signification de la condition de Fano inversée ?

Il existe également une règle de Fano inverse dont la formulation est la suivante : « aucun mot de code ne peut servir de terminaison à un autre mot de code».

D'un point de vue mathématique, la condition inverse peut être formulée ainsi : « si le code contient le mot B, alors pour toute chaîne non vide C le mot CB n'existe pas dans le code».

Application pratique de la condition de Fano

Considérons numéros de téléphone V téléphonie traditionnelle. Si le numéro « 102 » existe déjà, alors le numéro « 1029876 » ne sera tout simplement pas émis. Si les trois premiers chiffres sont composés, le PBX cesse de reconnaître et d'accepter tous les autres chiffres, se connectant à l'abonné par le numéro 102. Cependant, cette règle n'est pas valable pour les opérateurs communications mobiles. Cela est dû au fait que pour composer un numéro, vous devez appuyer sur la touche correspondante, qui est principalement la touche avec l'image verte. combiné. Pour cette raison, les numéros « 102 », « 1020 » et « 1029876 » peuvent exister et être attribués à des destinataires différents.

Condition problématique :étant donné une séquence composée des lettres « A », « B », « C », « D » et « E ». Pour coder la séquence donnée, un code binaire non uniforme est utilisé, avec lequel il est possible d'effectuer un décodage sans ambiguïté.

Question: Est-il possible que l'un des symboles raccourcisse la longueur du mot de code de manière à préserver la possibilité d'un décodage sans ambiguïté ? Dans ce cas, les codes des symboles restants doivent rester inchangés.

Solution: afin de préserver la possibilité de décodage, il suffit de respecter le direct ou le reverseConditions de Fano. Effectuons une vérification séquentielle des options 1, 3 et 4. Si aucune des options ne convient, la bonne réponse sera l'option 2 (pas possible).

Option 1. Code : A - 00, B - 01, C - 011, D - 101 et E - 111. Direct Etat de Fano non exécuté : le code du caractère « B » coïncide avec le début du code du caractère « C ». La règle de Fano inverse ne tient pas : le code du caractère « B » coïncide avec la fin du code du caractère « D ». L'option ne convient pas.

Option 3. Code : A - 00, B - 010, C - 01, D - 101 et E - 111. Direct Etat de Fano non exécuté : le code du caractère « C » coïncide avec le début du code du caractère « B ». La condition inverse n'est pas non plus satisfaite : le code du caractère « C » coïncide avec la fin du code du caractère « D ». L'option ne convient pas.

Option 4. Code : A - 00, B - 010, C - 011, D - 01 et E - 111. Direct Etat de Fano non exécuté : le code du caractère « D » coïncide avec le début du code des caractères « B » et « C ». Cependant, la règle inverse de Fano est observée : le code du caractère « D » ne coïncide pas avec la fin du code de tous les autres caractères. Pour cette raison, l’option est appropriée.

Après avoir vérifié les options pour résoudre le problème de respect des règles directes et inverses Etat de Fano, il a été constaté que l'option 4 est correcte.

Répondre: 4

Et maintenant, je vous propose de vous familiariser avec la solution multimédia au problème qui a été proposée dans la version démo de l'examen d'État unifié en informatique et TIC. D'ailleurs, cette tâche fait référence au type de problèmes résolus en utilisant Conditions de Fano.

Vous avez encore des questions ?

Si après avoir lu cette publication vous avez encore des questions, des malentendus ou si vous souhaitez consolider le matériel que vous avez couvert solutions pratiques, puis appelez et inscrivez-vous avec moi à des cours particuliers d'informatique et de TIC.

Tâche n°5

Lors de l'exécution de cette tâche, vous devez connaître la condition de Fano,Code de Huffman

Quelle est la signification de la condition directe de Fano ?

Etat de Fano du nom de son créateur, le scientifique italo-américain Robert Fano. La condition est nécessaire dans la théorie du codage lors de la construction d’un code à terminaison automatique. Compte tenu de la terminologie différente, un tel code est appelé code préfixe.

Cette condition peut être formulée ainsi : «aucun mot de code ne peut servir de début à un autre mot de code ».

D'un point de vue mathématique, la condition peut être formulée comme suit : «si le code contient le mot B, alors pour toute ligne C non vide le mot BC n'existe pas dans le code ».

Quelle est la signification de la condition de Fano inversée ?

Il existe également une règle de Fano inverse dont la formulation est la suivante : «aucun mot de code ne peut servir de terminaison à un autre mot de code ».

D'un point de vue mathématique, la condition inverse peut être formulée ainsi : «si le code contient le mot B, alors pour toute chaîne non vide C le mot CB n'existe pas dans le code ».

Condition problématique : étant donné une séquence composée des lettres « A », « B », « C », « D » et « E ». Pour coder la séquence donnée, un code binaire non uniforme est utilisé, avec lequel il est possible d'effectuer un décodage sans ambiguïté.

Lettre

Équivalent binaire

010

011

101

111

Question : Est-il possible que l'un des symboles raccourcisse la longueur du mot de code de manière à préserver la possibilité d'un décodage sans ambiguïté ? Dans ce cas, les codes des symboles restants doivent rester inchangés.

Numéro d'option

Répondre

B–01

Pas possible

C–01

J–01

Solution : afin de préserver la possibilité de décodage, il suffit de respecter le direct ou le reverseConditions de Fano . Effectuons une vérification séquentielle des options 1, 3 et 4. Si aucune des options ne convient, la bonne réponse sera l'option 2 (pas possible).

Option 1. Code : A - 00, B - 01, C - 011, D - 101 et E - 111. DirectEtat de Fano non exécuté : le code du caractère « B » coïncide avec le début du code du caractère « C ». La règle de Fano inverse ne tient pas : le code du caractère « B » coïncide avec la fin du code du caractère « D ». L'option ne convient pas.

Option 3. Code : A - 00, B - 010, C - 01, D - 101 et E - 111. DirectEtat de Fano non exécuté : le code du caractère « C » coïncide avec le début du code du caractère « B ». La condition inverse n'est pas non plus satisfaite : le code du caractère « C » coïncide avec la fin du code du caractère « D ». L'option ne convient pas.

Option 4. Code : A - 00, B - 010, C - 011, D - 01 et E - 111. DirectEtat de Fano non exécuté : le code du caractère « D » coïncide avec le début du code des caractères « B » et « C ». Cependant, la règle inverse de Fano est observée : le code du caractère « D » ne coïncide pas avec la fin du code de tous les autres caractères. Pour cette raison, l’option est appropriée.

Après avoir vérifié les options pour résoudre le problème de respect des règles directes et inversesEtat de Fano , il a été constaté que l'option 4 est correcte.

Répondre : 4

Code de Huffman

L'idée derrière le codage de Huffman est basée sur la fréquence d'apparition d'un caractère dans une séquence. Le symbole qui apparaît le plus souvent dans la séquence reçoit un nouveau très petit code, et le symbole qui apparaît le moins souvent reçoit au contraire un très petit code. code long. En effet, nous voulons nous assurer que lorsque nous aurons traité toutes les entrées, les caractères les plus courants occuperont le moins d'espace (et moins que dans l'original), et les plus rares occuperont le plus d'espace. (mais comme ils sont rares, ce n'est pas grave).

№ 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). Si vous encodez la séquence de lettres CASCADE de cette manière et notez le résultat code octal, alors ça ira

1) 22162

2) 1020342

3) 2131453

4) 34017

Explication.

Vous devez d’abord présenter les données dans la condition numérique dans code binaire:

100

Encodez ensuite la séquence de lettres : CASCADE - 010010001110010. Divisons maintenant cette représentation en triplets de droite à gauche et convertissons l'ensemble de nombres résultant en code décimal, puis en octal (la représentation octale est la même que la décimale lorsqu'elle est divisée par triples)

010 010 001 110 010 - 22162.

№ 2. Pour transmettre un message sur un canal de communication composé uniquement de caractères A, B, C et D, un codage caractère par caractère est utilisé : A-00, B-11, B-010, D-011. Le message est transmis via le canal de communication : VBGAGV. Encodez le message avec ce code. Reçu nombre binaire convertir en hexadécimal.

1) CBDADC

2) 511110

3) 5B1A

4)A1B5

Explication.

Codons la séquence de lettres : VBGAGV - 0101101100011010. Divisons maintenant cette représentation en quatre de droite à gauche et convertissons l'ensemble de nombres résultant d'abord en code décimal, puis en hexadécimal :

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

La bonne réponse est indiquée au numéro 3

№ 3. Pour coder un message composé uniquement des lettres A, B, C et D, un code binaire de longueur impaire est utilisé :

010

011

Si vous encodez la séquence de caractères VGAGBV de cette manière et notez le résultat, vous obtenez :

1) CDADBC

2)A7C4

3) 412710

4) 4С7А

Explication.

Codons la séquence de lettres : VGAGBV - 0100110001111010. Divisons maintenant cette représentation en quatre de droite à gauche et convertissons l'ensemble de nombres résultant d'abord en code décimal, puis en hexadécimal :

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

La bonne réponse est indiquée au numéro 4.

№ 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

Explication.

Code de première ligne : 10101.

Code de deuxième ligne : 11000.

Code de troisième ligne : 01010.

Écrivons les codes dans l'ordre sur une seule ligne : 101011100001010. Divisons maintenant cette représentation en triplets de droite à gauche et convertissons l'ensemble de nombres résultant en code décimal ( représentation octale coïncide avec le nombre décimal lorsqu'il est divisé en triplets).

101 011 100 001 010 - 53412.

№ 5. Pour 5 lettres alphabet latin leurs codes binaires sont spécifiés (pour certaines lettres - à partir de deux bits, pour certaines - à partir de trois). Ces codes sont présentés dans le tableau :

000

110

001

Déterminez quel ensemble de lettres est codé par la chaîne binaire 1100000100110

1)baade

2) méchant

3)bacde

4) backdb

Explication.

On voit que la condition de Fano est satisfaite : aucun mot de code n’est le début d’un autre mot de code, on peut donc définitivement décoder le message depuis le début.

Divisons le code de gauche à droite en fonction des données du tableau et traduisons-le en lettres :

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

La bonne réponse est indiquée au numéro 3.

№ 6. 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éterminer quel numéro a été transmis sur le canal sous la forme 01100010100100100110 ?

1) 6543

2) 62926

3) 62612

4) 3456

Explication.

L'exemple montre que 2 caractères sont codés avec 10 chiffres binaires (bits), 5 bits sont alloués pour chaque chiffre. La condition dit que chaque chiffre est écrit dans un code de 4 caractères, ce qui signifie que le cinquième chiffre peut être omis.

Décomposons-le notation binaire en groupes de 5 caractères : 01100 01010 01001 00110. Nous supprimons le dernier chiffre de chaque cinq et le convertissons en notation décimale :

0110 0101 0100 0011 - 6 5 4 3.

La bonne réponse est indiquée sous le numéro 1.

№ 7. Les messages contenant seulement 4 lettres sont transmis sur le canal de communication - P, O, R, T. Pour coder les lettres, des mots de code de 5 bits sont utilisés :

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

Cet ensemble de mots de passe a la propriété suivante :deux mots quelconques d'un ensemble diffèrent dans au moins trois positions.

Cette propriété est importante pour décrypter les messages en présence d'interférences (en supposant que bits transmis peut être déformé, mais ne disparaît pas). Un message codé est considéré comme reçu correctement si sa longueur est un multiple de 5 et si chaque quint ne diffère d'un mot de code que par une position au maximum ; dans ce cas, on pense que le cinq code la lettre correspondante. Par exemple, si le cinq 00000 est reçu, alors on considère que la lettre P a été transmise.

Parmi les messages ci-dessous, retrouvez celui qui a été correctement reçu et indiquez son décodage (les espaces n'ont pas d'importance).

11011 11100 00011 11000 01110

00111 11100 11110 11000 00000

1) INONDATION

2) ROTOR

3) HACHE

4) aucun des messages n'a été reçu correctement

Explication.

La longueur des deux messages est un multiple de cinq.

En analysant le premier message « 11011 11100 00011 11000 01110 », nous arrivons à la conclusion qu'il a été mal reçu, puisqu'il n'y a pas de mot qui diffère du mot « 01110 » dans une seule position.

Regardons le deuxième message. Étant donné que chaque cinq ne diffère d'un certain mot de code que par une seule position, il ne peut être déchiffré que par « AX ».

№ 8. 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-10010, B-11111, C-00101.

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 00100 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, alors on considère qu'une erreur s'est produite (cela est indiqué par "x").

Message reçu 10000 10101 11001 10111. Décodez ce message - sélectionnez l'option correcte.

1) AVBB

2) xxxx

3) ABxB

4) AhhB

Explication.

Nous décodons chaque mot du message. Le premier mot : 10000 ne diffère de la lettre A que sur une seule position. Le deuxième mot : 10101 ne diffère de la lettre B que sur une seule position. Troisième mot : 11001 diffère de n’importe quelle lettre sur plus d’une position. Le quatrième mot : 10111 ne diffère de la lettre B que sur une seule position.

Réponse : ABxB.

№ 9. 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

Explication.

Pour qu'un message écrit à l'aide d'un code de longueur inégale soit décodé sans ambiguïté, il est nécessaire qu'aucun code ne soit le début d'un autre code (plus long). Regardons les options pour la lettre D, en commençant par la plus courte.

1) D=1 : la lettre code D est le début de tous les codes lettres présentés, cette option n'est donc pas adaptée.

2) D=0 : le code de la lettre D n'est pas le début d'un autre code, cette option convient donc.

3) D=01 : le code de la lettre D n'est pas le début d'un autre code, cette option convient donc.

4) D=10 : le code de la lettre D est le début des codes des lettres B et G, cette option n'est donc pas adaptée.

Ainsi, deux options conviennent : 0 et 01. 0 est plus court que 01.

№ 10. Les messages contenant seulement 4 lettres sont transmis sur le canal de communication :

E, N, 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 les autres.

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−11, E−101, T−100

Explication.

Choisissons les codes pour lesquels la condition de Fano est satisfaite. Ce sont les codes 3 et 4.

Pour que le message soit le plus court possible, il faut que plus une lettre apparaît souvent, plus son code est court.

Par conséquent, la réponse est 4, puisque la lettre O est la lettre la plus courante et que l’option 4 utilise un caractère pour la coder.

№ 11. Pour coder une certaine séquence composée des lettres K, L, M, N, nous avons décidé d'utiliser un code binaire non uniforme qui satisfait à la condition de Fano. Pour la lettre H, le mot de code 0 a été utilisé, pour la lettre K, le mot de code 110 a été utilisé. Quelle est la longueur totale la plus courte possible des quatre mots de code ?

1) 7

2) 8

3) 9

4) 10

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.

Explication.

Trouvons pour les deux symboles restants la représentation la plus courte qui satisfait la condition de Fano. Le mot de code 1 ne peut pas être utilisé car cela violerait la condition de Fano. Parmi les mots de code à deux chiffres, le mot 10 peut être utilisé, mais les mots 11 et 01 ne peuvent pas être utilisés. Avec cette construction de codes, il est impossible de sélectionner un mot de code à deux chiffres pour le quatrième symbole. Nous utilisons donc un mot à trois chiffres, à savoir 111.

Ainsi, la longueur totale la plus courte possible des quatre mots de code sera 1 + 3 + 2 + 3 = 9.

La bonne réponse est indiquée au numéro 3.

№12. Les messages sont transmis via le canal de communication, dont chacun contient 16 lettres A, 8 lettres B, 4 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:0, B:10, C:110, D:111

2) A:0, B:10, C:01, D:11

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

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

Explication.

2 et 3 ne conviennent pas, car ils contiennent des paires de codes dont l'un est le début de l'autre.

La longueur des messages lors de l'utilisation du premier code sera égale à .

La longueur des messages lors de l'utilisation du quatrième code sera égale à .

L’utilisation du premier code entraîne des messages plus courts, c’est donc celui-ci qui doit être utilisé.

3. Multiplication des probabilités d'événements conjoints indépendants

4. Trouver la moyenne des valeurs de variables indépendantes aléatoires

5. Le concept de probabilité conditionnelle

6. Formule générale pour la probabilité que des événements se produisent

7. Formule générale pour la probabilité de la somme des événements

Conférence 3. Le concept d'entropie

1. L'entropie comme mesure de l'incertitude

2. Propriétés de l'entropie

3. Entropie conditionnelle

Conférence 4. Entropie et information

1. Approche volumétrique pour mesurer la quantité d'informations

2. Approche entropique pour mesurer la quantité d'informations

Conférence 5. Informations et alphabet

Cours 6. Énoncé du problème de codage. Premier théorème de Shannon.

Cours 7. Méthodes de construction de codes binaires. Codage binaire alphabétique non uniforme avec des signaux d'égale durée. Codes de préfixe.

1. Énoncé du problème d'optimisation du codage non uniforme

2. Code inégal avec délimiteur

3. Codes sans séparateur. Etat de Fano

4. Code de préfixe Shannon-Fano

5. Code de préfixe Huffman

Cours 8. Méthodes de construction de codes binaires. Autres options

1. Codage binaire alphabétique uniforme. Code d'octet

2. Systèmes internationaux de codage d'octets pour les données textuelles. Système universel de codage de données textuelles

3. Codage alphabétique à durée inégale des signaux élémentaires. Code Morse

4. Bloquer le codage binaire

5. Encodage des données graphiques

6. Encodage des informations audio

Conférence 9. Systèmes numériques. Représentation des nombres dans différents systèmes numériques. Partie 1

1. Systèmes numériques

2. Système de nombres décimaux

3. Système de numérotation binaire

4. Systèmes de numérotation 8 et 16-aires

5. Systèmes de numérotation mixtes

6. Le concept d'économie d'un système numérique

Conférence 10. Systèmes numériques. Représentation des nombres dans différents systèmes numériques. Partie 2.

1. La tâche de convertir un nombre d'un système numérique à un autre

2. Conversion des entiers q  p

3. Conversion d'entiers p  q

4. Conversion de nombres fractionnaires p  q

6. Conversion de nombres entre les systèmes numériques à 2 chiffres, 8 chiffres et hexadécimaux

Cours 11. Codage des nombres dans un ordinateur et opérations sur ceux-ci

1. Nombres normalisés

2. Conversion d'un nombre de sa forme naturelle à sa forme normalisée

3. Conversion de nombres normalisés

4. Encodage et traitement des entiers non signés

5. Encodage et traitement des entiers signés

6. Codage et traitement des nombres réels

Conférence 12. Transmission d'informations sur les lignes de communication

1. Schéma général de transmission d'informations dans une ligne de communication

2. Caractéristiques des canaux de communication

3. Effet du bruit sur la capacité des canaux

Cours 13. Assurer la fiabilité du transfert d'informations.

1. Énoncé du problème de la garantie de la fiabilité de la transmission

2. Codes qui détectent une seule erreur

3. Des codes qui corrigent une seule erreur

Cours 14. Méthodes de transmission d'informations dans les lignes de communication informatique

1. Transfert de données parallèle

2. Transmission de données en série

3. Communication des ordinateurs via les lignes téléphoniques

Cours 15. Classification des données. Représentation des données dans la mémoire de l'ordinateur

1. Classement des données

2. Représentation des données élémentaires en RAM

Cours 16. Classification des structures de données

1. Classification et exemples de structures de données

2. Le concept de notation logique

Cours 17. Organisation des structures de données en RAM et sur supports externes

1. Organisation des structures de données en RAM

2. Hiérarchie des structures de données sur supports externes

3. Caractéristiques des périphériques de stockage

Questions de sécurité

Références

3. Codes sans séparateur. Etat de Fano

Après avoir examiné l'une des options de codage binaire non uniforme, essayons de trouver une réponse à la question suivante : un tel codage est-il possible sans l'utilisation de délimiteurs ?

L'essence de ce problème est de trouver une option de codage de message dans laquelle la sélection ultérieure de chaque caractère individuel du message (c'est-à-dire le décodage) s'avère sans ambiguïté sans indicateurs spéciaux pour séparer les caractères.

Les codes sans séparateur les plus simples et les plus couramment utilisés sont ce qu'on appelle codes de préfixe, qui satisfont à la condition suivante – Etat de Fano:Un message codé à l'aide d'un code non uniforme peut être décodé sans ambiguïté si aucun des codes du message ne correspond au préfixe. * (le début de) un autre code plus long.

Par exemple, s'il existe un code 110, alors les codes 1, 11, 1101, 110101, etc. ne peuvent plus être utilisés.

Si la condition de Fano est satisfaite, alors lors de la lecture (décodage, déchiffrement) d'un message codé en le comparant avec une table de codes, vous pouvez toujours indiquer exactement où se termine un code et où commence un autre.

Exemple 1. Les codes sont-ils présentés dans le tableau ? 4, préfixe ? Les codes présentés dans le tableau. 4 ne sont pas des préfixes. Voir par exemple les codes des lettres « O » et « E », « A » et « N », « S » et « M », « D » et « Ch ».

Exemple 2. Il existe un tableau de codes de préfixe (tableau 6). Vous devez décoder le message suivant codé à l'aide de cette table de codes donnée :

00100010000111010101110000110

Tableau 6. Tableau des codes de préfixe

Le décodage s'effectue en répétant cycliquement les étapes suivantes :

« Coupez » le symbole le plus à gauche du message actuel, attachez-le à droite au mot de code de travail (actuel) ;

comparer le mot de code actuel avec la table de codes ; s’il n’y a pas de correspondance, revenez à l’étape 1.

Utilisation de la table de codes pour le courant mot de code faire correspondre le symbole de l'alphabet primaire ;

Vérifiez s'il y a encore des caractères dans le message codé ; si oui, passez à l'étape 1.

Application de cet algorithme au message codé suggéré ci-dessus donne :

00100010000111010101110000110

Ainsi, après avoir terminé la procédure de décodage jusqu'au bout, vous pouvez recevoir le message : « mère de savon cadre."

Ainsi, l'utilisation du codage par préfixe permet au message d'être plus court car il n'est pas nécessaire de transmettre des séparateurs de caractères.

Cependant, la condition de Fano ne spécifie pas de manière spécifique de former un code de préfixe, laissant le champ libre à l'activité de développement du meilleur code de préfixe possible.

4. Code de préfixe Shannon-Fano

Considérons l'option de codage proposée en 1948-1949. indépendamment par K. Shannon et R. Fano.

Considérons le schéma de codage Shannon – Fano (comment il est construit) comme suit : exemple .

Soit un alphabet primaire composé de six caractères : , Où
. Soit les probabilités d'apparition de ces signes dans les messages :
,
,
,
,
Et
. Classons ces signes dans le tableau par ordre décroissant de probabilités.

Divisons les signes en deux groupes afin que les sommes de probabilités dans chacun de ces deux groupes soient approximativement égales. Dans ce cas, le 1er groupe comprendra Et , et le reste - dans le 2ème groupe. Signes Attribuons le premier chiffre gauche de leurs codes au premier groupe comme « 0 », et que le premier chiffre gauche des codes de symboles du deuxième groupe soit « 1 ».

Continuons à diviser chacun des groupes résultants en sous-groupes selon le même schéma, c'est-à-dire de manière à ce que les sommes de probabilités à chaque étape dans les deux sous-groupes du groupe de division soient aussi proches que possible. Ainsi, nous recevrons les bits de codes de caractères suivants un par un . Nous attribuerons ces prochains chiffres à droite à ceux existants.

L’ensemble de cette procédure peut être schématiquement représenté dans le tableau 7.

Tableau 7. Construction du code de Shannon-Fano

Signe		Chiffres du code

On peut voir que les codes de caractères construits satisfaire la condition de Fano, par conséquent, un tel codage est un préfixe.

Trouvons la longueur moyenne du code résultant en utilisant la formule

,

Où – le nombre de bits (caractères) dans le code correspondant au symbole .

D'après le tableau, il ressort clairement que
,
,
.

On obtient ainsi :

Donc pour encoder un caractère alphabet primaire nécessitait une moyenne de 2,45 caractères de l’alphabet secondaire (binaire).

Déterminons la quantité moyenne d'informations par caractère de l'alphabet primaire en première approximation (en tenant compte des probabilités différentes d'apparition de ces caractères dans les messages). Appliquons la formule de Shannon :

.

Trouvons la redondance du code binaire résultant :

,

c'est-à-dire que la redondance est d'environ 2,5.

Voyons si le code résultant est optimal. Il y a 6 zéros dans les codes reçus et 11 uns. Ainsi, les probabilités d’apparition de 0 et 1 sont loin d’être égales. Le code résultant ne peut donc pas être considéré comme optimal.

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".

La taille de l'archive avec la présentation est de 734 Ko.

Télécharger la présentation

Méthodes de codage

ré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 de l'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 décimal Compte. 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 en termes de stockage d’informations. Texte codé. Support d'informations. Mots-clés

. Résolvez l'énigme. « 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

« 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 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 ?