Décodage sans ambiguïté de la condition Fano. Un décodage sans ambiguïté est fourni. Encodage et décryptage des messages
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 préfixé, 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éterminer s'ils ont la propriété de décodabilité sans ambiguïté codes suivants: UN) {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. Les codes de préfixe sont parfois appelés 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.
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. Tableau d'encodage. Volume d'information du texte. Codage binaire dans un ordinateur. Codage des informations textuelles. Table de codes étendue. Symbole. Unique code binaire. 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 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. La lettre du 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 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 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 ?
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.
À l'aide de la table de codes, faites correspondre le mot de code actuel avec un caractère 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.
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 celui avec le plus petit valeur numérique. 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 celui ayant la valeur numérique la plus faible.
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
Noir et blanc image tramée encodé 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é. 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
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 bonne option.
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, 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 ?
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
Les messages contenant seulement 4 lettres P, R, S, T sont transmis sur un canal de communication en utilisant un code binaire uniforme. Chaque lettre a son propre mot de code, et la propriété suivante est satisfaite pour un ensemble de mots de code : deux mots quelconques du groupe. ensemble diffèrent d’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
Dans les tests de préparation à l'examen d'État unifié en informatique, il y a des problèmes d'utilisation de la condition de Fano. Je n'ai trouvé aucun élément dans les manuels. Allons sur Wikipédia.
Condition de Fano (condition anglaise de Fano, en l'honneur de Robert Fano) - en théorie du codage condition nécessaire construire un code auto-terminable (dans une autre terminologie, code préfixe). La formulation habituelle de cette condition ressemble à ceci :
Aucun mot de code ne peut être le début d’un autre mot de code.
Formulation plus « mathématique » :
Si le code inclut le mot a, alors pour toute chaîne non vide b, le mot ab n'existe pas dans le code.
L'algorithme de Shannon-Fano est l'un des premiers algorithmes de compression, formulé pour la première fois par les scientifiques américains Shannon et Robert Fano. Cette méthode la compression est très similaire à l’algorithme de Huffman, apparu plusieurs années plus tard. L'algorithme utilise des codes longueur variable: un caractère fréquent est codé avec un code de longueur plus courte, un caractère rare est codé avec un code de plus grande longueur. Les codes Shannon-Fano sont préfixés, c'est-à-dire qu'aucun mot de code n'est un préfixe d'un autre. Cette propriété vous permet de décoder de manière unique n’importe quelle séquence de mots de passe.
Les bases
Le codage Shannon-Fano est un algorithme de codage hétérogène à préfixe. Fait référence aux méthodes de compression probabilistes (plus précisément aux méthodes de modélisation de contexte d'ordre zéro). Comme l'algorithme de Huffman, l'algorithme de Shannon-Fano utilise la redondance des messages contenue dans la distribution de fréquences non uniforme des symboles de son alphabet (primaire), c'est-à-dire qu'il remplace les codes par des codes plus nombreux. personnages fréquents des séquences binaires courtes et des codes de caractères plus rares - des séquences binaires plus longues.
L'algorithme a été développé indépendamment par Shannon (publication " Théorie mathématique communications", 1948) et, plus tard, Fano (publié sous forme de rapport technique).
1. Notions de base
Encoder un texte signifie l’associer à un autre texte. Le codage est utilisé dans la transmission de données - afin de crypter le texte d'étrangers, pour rendre la transmission de données plus fiable, car le canal de données ne peut transmettre que ensemble limité caractères (par exemple - seulement deux caractères, 0 et 1) et pour d'autres raisons.
Lors du codage, l'alphabet dans lequel sont écrits les textes sources (alphabet source) et l'alphabet dans lequel les textes codés (codes) sont écrits sont déterminés à l'avance ; cet alphabet est appelé alphabet de code ; Un alphabet binaire est souvent utilisé comme alphabet codé, composé de deux caractères (bits) 0 et 1. Les mots de l'alphabet binaire sont parfois appelés séquences de bits.
2. Codage lettre par lettre
La méthode de codage la plus simple est la lettre par lettre. Avec le codage lettre par lettre, chaque caractère de l'alphabet d'origine est associé à un mot de code - un mot de l'alphabet de code. Parfois, au lieu de « mot de code de lettre », ils disent simplement « code de lettre ». Lors de l'encodage du texte lettre par lettre, les codes de tous les caractères sont écrits dans une rangée, sans délimiteurs.
Exemple 1. L'alphabet original est l'alphabet des lettres russes, minuscules et lettres majuscules ne diffèrent pas. La taille de l'alphabet est de 33 caractères.
Alphabet codé - alphabet chiffres décimaux. La taille de l'alphabet est de 10 caractères.
Le codage lettre par lettre est utilisé selon règle suivante: une lettre est codée par son numéro dans l'alphabet : le code de la lettre A est 1 ; lettres I – 33, etc.
Le code du mot ABBA est alors 1221.
Attention : La séquence 1221 peut signifier non seulement ABBA, mais aussi KU (K est la 12ème lettre de l'alphabet et U est la 21ème lettre). On dit d'un tel code qu'il ne permet PAS un décodage sans ambiguïté
Exemple 2. Les alphabets d'origine et de code sont les mêmes que dans l'exemple 1. Chaque lettre est également codée avec son propre numéro dans l'alphabet, MAIS le numéro est toujours écrit sur deux chiffres : 0 est ajouté à l'enregistrement des nombres à un chiffre à gauche Par exemple, le code A est 01, le code B est 02, etc.
Dans ce cas, le code texte ABBA sera 01020201. Et ce code ne peut être déchiffré que d'une seule manière. Pour le décrypter, il suffit de le décomposer texte de code 01020201 pour deux : 01 02 02 01 et pour chaque deux, déterminez la lettre qui lui correspond.
Cette méthode de codage est appelée uniforme. Un codage uniforme permet toujours un décodage sans ambiguïté.
Dans la suite, seul le codage lettre par lettre est pris en compte.
3. Encodage inégal
Le codage uniforme est pratique pour le décodage. Cependant, des codes non uniformes sont également souvent utilisés, c'est-à-dire codes avec différentes longueurs de mots de passe. Ceci est utile lorsque texte source différentes lettres apparaissent avec des fréquences différentes. Ensuite, les caractères fréquents doivent être codés avec des mots plus courts et les caractères rares avec des mots plus longs. L'exemple 1 montre clairement que (contrairement aux codes uniformes !) tous les codes non uniformes ne permettent pas un décodage sans ambiguïté.
Il existe une condition simple sous laquelle un code non uniforme permet un décodage sans ambiguïté.
Un code est appelé préfixe s’il ne contient pas un seul mot de code qui serait le début (en termes scientifiques, un préfixe) d’un autre mot de code.
Mais je veux démontrer comment ce processus peut être automatisé.
je mettrai la vidéo sur Internet
Je vais donner un exemple de préparation à l'examen d'État unifié en informatique (entreprise 1C - matériel du Centre de formation certifiée) :
Pour coder une certaine séquence composée des lettres C, T, P, O, K et A, un code binaire non uniforme est utilisé qui satisfait à la condition de Fano et permet donc de décoder de manière unique la séquence binaire résultante. Voici le code : S - 000, T - 001, P - 010, O - 100, K - 011, A - 11. Est-il possible de raccourcir la longueur du mot de code pour l'une des lettres afin que le code reste satisfait la condition de Fano ? Les codes des lettres restantes ne doivent pas changer.
Choisissez la bonne réponse.
Réponses possibles :
1) pour la lettre P - 01
2) pour la lettre O - 10
3) pour la lettre A - 1
4) c'est impossible
La bonne option est 2
Solution:
L'option 1) ne convient pas - la condition de Fano sera violée pour les lettres P et K
L'option 2) convient - le mot 10 n'est pas le début des mots de code pour d'autres lettres
L'option 3) ne convient pas - la condition de Fano sera violée pour les lettres A et O
L'option 4) ne convient pas - voir l'option 2)
Voyons maintenant ce que le programme produira pour la solution automatisée de tels problèmes et le contrôle des connaissances.
La tâche ne précise pas la fréquence ou la probabilité d'apparition des lettres, donc dans le programme nous la prendrons égale à 0,01 pour toutes les lettres.
Probabilités :
0.01, 0.01, 0.01, 0.01, 0.01, 0.01
Valeurs:
C, T, P, O, K, A
Résultat:
C 000
T001
P01
Ô 100
K 101
Un 11
Il ressort clairement de la solution qu’il peut y avoir plusieurs solutions possibles, mais elles satisfont toutes à la condition de Fano.
Je crois que programmes similaires sera utile pour surveiller les connaissances, et l'inclusion d'une telle fonction dans un langage de programmation renforcera les capacités du langage, j'inclus donc cette fonction dans le langage SmartMath. Le programme lui-même détermine le nombre de symboles à analyser, les trie en fonction de la fréquence et attribue des codes selon la condition Fano. L’avantage de l’automatisation de la génération de code lorsque la condition de Fano est remplie est que vous pouvez créer rapidement des solutions pour n’importe quelle séquence.
Voir lien.