Encodage alphabétique binaire. Codage binaire alphabétique uniforme. Code d'octet
Lors de la transmission de messages via des lignes de communication, vous devez toujours utiliser l'un ou l'autre code, c'est-à-dire présenter un message sous la forme d'une série de signaux. Un exemple bien connu de code est le code Morse utilisé en télégraphie pour transmettre des messages verbaux. Grâce à cet alphabet, tout message est présenté comme une combinaison de signaux élémentaires : point, tiret, pause (espace entre les lettres), pause longue (espace entre les mots).
En général, le codage consiste à cartographier l’état d’un système physique en utilisant l’état d’un autre. Par exemple, lors d’une conversation téléphonique, les signaux audio sont codés sous forme d’ondes électromagnétiques puis décodés à nouveau pour devenir des signaux audio à l’autre bout de la ligne. Le cas de codage le plus simple est celui où les deux systèmes et (affiché et affichant) ont un nombre fini d'états possibles. C'est le cas lors de la transmission de messages écrits en lettres, par exemple lors de la télégraphie. Nous nous limiterons à considérer ce cas de codage le plus simple.
Supposons qu'il existe un système (par exemple, une lettre de l'alphabet russe) qui peut prendre au hasard l'un des États. Nous souhaitons l'afficher (l'encoder) à l'aide d'un autre système dont les états possibles sont . Si (le nombre d'états du système est inférieur au nombre d'états du système), alors chaque état du système ne peut pas être codé en utilisant un seul état du système. Dans de tels cas, un état du système doit être représenté à l’aide d’une certaine combinaison (séquence) d’états du système. Ainsi, en code Morse, les lettres sont affichées par diverses combinaisons de symboles élémentaires (point, tiret). La sélection de telles combinaisons et l'établissement d'une correspondance entre le message transmis et ces combinaisons est appelée « codage » au sens étroit du terme.
Les codes diffèrent par le nombre de symboles élémentaires (signaux) à partir desquels se forment les combinaisons, c'est-à-dire par le nombre d'états possibles du système. En code Morse, il existe quatre symboles élémentaires de ce type (point, tiret, pause courte, pause longue). La transmission du signal peut être effectuée dans Formes variées: éclairs lumineux, courants électriques de durées variables, signaux sonores, etc. Un code comportant deux symboles élémentaires (0 et 1) est dit binaire. Les codes binaires sont largement utilisés dans la pratique, en particulier lors de la saisie d'informations dans des ordinateurs numériques électroniques fonctionnant à l'aide du système de nombres binaires.
Le même message peut être codé de différentes manières. La question se pose des méthodes de codage optimales (les plus rentables). Il est naturel de considérer le code le plus rentable comme celui dans lequel le temps minimum est passé à transmettre des messages. Si le même temps est consacré à la transmission de chaque symbole élémentaire (par exemple 0 ou 1), alors le code optimal sera tel qu'il faudra quantité minimale symboles élémentaires.
Supposons qu'on nous confie une tâche : encoder les lettres de l'alphabet russe en code binaire pour que chaque lettre corresponde à une certaine combinaison de symboles élémentaires 0 et 1 et pour que le nombre moyen de ces symboles par lettre du texte soit minimal.
Regardons les 32 lettres de l'alphabet russe : a, b, c, d, d, f, g, z, i, j, k, l, m, n, o, p, r, s, t, u , f, x, ts, ch, sh, shch, b, y, b, e, yu, i plus l'espace entre les mots, que nous désignerons « – ». Si, comme il est d'usage en télégraphie, vous ne faites pas la distinction entre les lettres ъ et ь (cela n'entraîne pas de divergences), alors vous obtenez 32 lettres : a, b, c, d, d, f, g. h, je, j, k, l, m, n, o, p, r, s, t, u. f, x, c, h, w, chch, (b, b). s. euh, toi, je, "-".
La première chose qui me vient à l'esprit est, sans changer l'ordre des lettres, de les numéroter dans une rangée, en leur attribuant des numéros de 0 à 31, puis de convertir la numérotation en système de numérotation binaire. Un système binaire est un système dans lequel les unités de différents chiffres représentent différentes puissances de deux. Par exemple, le nombre décimal 12 est représenté par
et dans le système binaire, il s'écrira 1100.
Nombre décimal 25 -
Sera écrit en binaire comme 11001.
Chacun des nombres peut être représenté par un nombre binaire à cinq chiffres. On obtient alors le code suivant :
Dans ce code, exactement 5 caractères élémentaires sont consacrés à l'image de chaque lettre. La question se pose : ce code le plus simple est-il optimal et est-il possible de créer un autre code dans lequel il y aura, en moyenne, moins de symboles élémentaires par lettre ?
En effet, dans notre code, le même nombre de caractères élémentaires est consacré à l'image de chaque lettre - les « a », « e », « o » fréquents ou les « sch », « e », « f » rarement présents. -. De toute évidence, il serait plus raisonnable que les lettres fréquentes soient codées avec moins de caractères et les lettres moins fréquentes avec plus.
Pour composer un tel code, vous devez évidemment connaître la fréquence des lettres dans le texte russe. Ces fréquences sont données dans le tableau 18.8.1. Les lettres du tableau sont classées par ordre décroissant de fréquence.
Tableau 18.8.1.
À l'aide d'un tel tableau, vous pouvez créer le code le plus économique en fonction de considérations liées à la quantité d'informations. Bien évidemment, le code sera plus économique lorsque chaque symbole élémentaire véhicule le maximum d'informations. Considérons un symbole élémentaire (c'est-à-dire le signal qui le représente) comme un système physique avec deux états possibles : 0 et 1.
L'information que donne ce symbole est égale à l'entropie du système et est maximale dans le cas où les deux états sont également probables ; dans ce cas, le symbole élémentaire véhicule l'information 1 (deux unités). Par conséquent, la base d'un codage optimal sera l'exigence que les caractères élémentaires du texte codé apparaissent en moyenne aussi souvent.
Présentons ici une méthode pour construire un code qui satisfait à la condition énoncée ; Cette méthode est connue sous le nom de code de Shannon-Fano. Son idée est que les symboles codés (lettres ou combinaisons de lettres) sont divisés en deux groupes à peu près également probables : pour le premier groupe de symboles, 0 est placé à la première place de la combinaison (le premier caractère du nombre binaire représentant le symbole); pour le deuxième groupe - 1. Ensuite, chaque groupe est à nouveau divisé en deux sous-groupes à peu près également probables ; pour les symboles du premier sous-groupe, zéro est placé en deuxième place ; pour le deuxième sous-groupe - un, etc.
Démontrons le principe de construction du code de Shannon-Fano en utilisant le matériau de l'alphabet russe (tableau 18.8.1). Comptons les six premières lettres (de « - » à « t ») ; en résumant leurs probabilités (fréquences), nous obtenons 0,498 ; toutes les autres lettres (de « n » à « sf ») auront approximativement la même probabilité de 0,502. Les six premières lettres (de « - » à « t ») auront en premier lieu un 0 binaire. Les lettres restantes (de « n » à « f ») auront en premier lieu un un. Ensuite, nous divisons à nouveau le premier groupe en deux sous-groupes à peu près également probables : de « - » à « o » et de « e » à « t » ; pour toutes les lettres du premier sous-groupe, nous mettrons zéro en deuxième lieu, et du deuxième sous-groupe - un. Nous continuerons le processus jusqu'à ce qu'il reste exactement une lettre dans chaque division, qui sera codée avec un certain nombre binaire. Le mécanisme. pour construire le code est présenté dans le tableau 18.8.2, et le code lui-même est donné dans le tableau 18.8.3.
Tableau 18.8.2.
|
Signes binaires |
|||||||||
Tableau 18.8.3
|
Nombre binaire |
Nombre binaire |
Nombre binaire |
Nombre binaire |
||||
À l'aide du tableau 18.8.3, vous pouvez encoder et décoder n'importe quel message.
À titre d’exemple, écrivons l’expression « théorie de l’information » en code binaire.
01110100001101000110110110000
0110100011111111100110100
1100001011111110101100110
Notez qu'il n'est pas nécessaire de séparer les lettres les unes des autres par un signe spécial, puisque le décodage s'effectue sans ambiguïté même sans cela. Vous pouvez le vérifier en décodant la phrase suivante à l'aide du tableau 18.8.2 :
10011100110011001001111010000
1011100111001001101010000110101
010110000110110110
(« méthode de codage »).
Il faut cependant noter que toute erreur d'encodage (confusion aléatoire des caractères 0 et 1) avec un tel code est désastreuse, puisque décoder tout le texte suivant l'erreur devient impossible. Par conséquent, ce principe de codage ne peut être recommandé que dans les cas où les erreurs de codage et de transmission d'un message sont pratiquement éliminées.
Une question naturelle se pose : le code que nous avons compilé, en l’absence d’erreurs, est-il vraiment optimal ? Pour répondre à cette question, trouvons l'information moyenne par symbole élémentaire (0 ou 1) et comparons-la avec le maximum d'informations possible, qui est égal à une unité binaire. Pour ce faire, on trouve d'abord l'information moyenne contenue dans une lettre du texte transmis, soit l'entropie par lettre :
,
où est la probabilité que la lettre prenne un certain état (« - », o, e, a,..., f).
De la table 18.8.1 nous avons
(deux unités par lettre de texte).
A l'aide du tableau 18.8.2, on détermine le nombre moyen de symboles élémentaires par lettre
En divisant l'entropie par , on obtient l'information par symbole élémentaire
(deux unités).
Ainsi, l'information par caractère est très proche de sa limite supérieure de 1, et le code que nous avons choisi est très proche de celui optimal. En restant dans les limites du codage des lettres, on ne peut pas faire mieux.
Notez que dans le cas d'un codage de nombres de lettres simplement binaires, nous aurions une image de chaque lettre avec cinq caractères binaires et les informations pour un caractère seraient
(deux unités),
c'est-à-dire sensiblement moins qu'avec un codage de lettres optimal.
Il convient toutefois de noter que le codage « par lettre » n’est pas du tout économique. Le fait est qu’il existe toujours une dépendance entre les lettres adjacentes de tout texte significatif. Par exemple, après une voyelle en russe, il ne peut pas y avoir « ъ » ou « ь » ; « Je » ou « yu » ne peuvent pas apparaître après les sifflements ; après plusieurs consonnes d'affilée, la probabilité d'une voyelle augmente, etc.
Nous savons que lorsque des systèmes dépendants sont combinés, l’entropie totale est inférieure à la somme des entropies des systèmes individuels ; par conséquent, l'information véhiculée par un morceau de texte connecté est toujours inférieure à l'information par caractère multipliée par le nombre de caractères. Compte tenu de cette circonstance, un code plus économique peut être construit si vous ne codez pas chaque lettre individuellement, mais des « blocs » entiers de lettres. Par exemple, dans un texte russe, il est logique d'encoder entièrement certaines combinaisons de lettres fréquentes, telles que « tsya », « ayet », « nie », etc. Les blocs codés sont classés par ordre décroissant de fréquence, comme les lettres dans la table. 18.8.1, et le codage binaire s'effectue selon le même principe.
Dans certains cas, il s'avère raisonnable de coder non même des blocs de lettres, mais des morceaux de texte entiers et significatifs. Par exemple, pour soulager le télégraphe pendant les vacances, il convient d'encoder des textes standards entiers avec des nombres conventionnels, tels que :
"Félicitations pour la nouvelle année, je vous souhaite une bonne santé et du succès dans votre travail."
Sans nous attarder spécifiquement sur les méthodes de codage par blocs, nous nous limiterons à formuler le théorème de Shannon évoqué ici.
Soit une source d'information et un récepteur connectés par un canal de communication (Fig. 18.8.1).
La productivité de la source d'information est connue, c'est-à-dire le nombre moyen d'unités d'information binaires provenant de la source par unité de temps (numériquement elle est égale à l'entropie moyenne du message produit par les sources par unité de temps). Connaître en outre la capacité du canal, c'est-à-dire la quantité maximale d'informations (par exemple, les caractères binaires 0 ou 1) que le canal est capable de transmettre dans la même unité de temps. La question se pose : quelle doit être la capacité du canal pour qu'il « fasse » face à sa tâche, c'est-à-dire pour que les informations de la source au récepteur arrivent sans délai ?
La réponse à cette question est donnée par le premier théorème de Shannon. Formulons-le ici sans preuve.
1er théorème de Shannon
Si la capacité du canal de communication est supérieure à l'entropie de la source d'information par unité de temps
alors il est toujours possible de coder un message suffisamment long pour qu'il soit transmis par un canal de communication sans délai. Si au contraire
alors le transfert d'informations sans délai est impossible.
Capacité en bits du code binaire, Conversion des informations de la forme continue à la forme discrète, Universalité du codage binaire, Codes uniformes et non uniformes, Informatique 7e année Bosova, Informatique 7e année
1.5.1. Conversion d'informations d'une forme continue à une forme discrète
Pour résoudre ses problèmes, une personne doit souvent transformer des informations existantes d'une forme de représentation à une autre. Par exemple, lors de la lecture à haute voix, les informations sont converties d'une forme discrète (texte) à une forme continue (son). Au contraire, lors d’une dictée dans un cours de langue russe, l’information passe d’une forme continue (la voix du professeur) à une forme discrète (les notes des élèves).
Les informations présentées sous forme discrète sont beaucoup plus faciles à transmettre, à stocker ou à traiter automatiquement. Par conséquent, dans la technologie informatique, une grande attention est accordée aux méthodes de conversion des informations d'une forme continue à une forme discrète.
La discrétisation de l'information est le processus de conversion de l'information d'une forme continue de représentation à une forme discrète.
Examinons l'essence du processus d'échantillonnage d'informations à l'aide d'un exemple.
Les stations météorologiques disposent d'enregistreurs pour un enregistrement continu. pression atmosphérique. Le résultat de leur travail sont des barogrammes - des courbes montrant l'évolution de la pression sur de longues périodes de temps. L'une de ces courbes, tracée par l'appareil pendant sept heures d'observation, est représentée sur la Fig. 1.9.
Sur la base des informations obtenues, vous pouvez construire un tableau contenant les lectures de l'instrument au début des mesures et à la fin de chaque heure d'observation (Fig. 1.10). 
Le tableau obtenu ne donne pas une image complètement complète de l'évolution de la pression au cours de la période d'observation : par exemple, la valeur de pression la plus élevée survenue au cours de la quatrième heure d'observation n'est pas indiquée. Mais si vous totalisez les valeurs de pression observées toutes les demi-heures ou 15 minutes, le nouveau tableau donnera une image plus complète de l'évolution de la pression.
Ainsi, nous avons converti les informations présentées sous forme continue (barogramme, courbe) en forme discrète (tableau) avec une certaine perte de précision.
À l’avenir, vous vous familiariserez avec les manières de représenter discrètement des informations audio et graphiques.
En conséquence, un binaire à quatre bits vous permet d'obtenir 16 combinaisons de codes, un à cinq bits - 32, un à six bits - 64, etc. La longueur de la chaîne binaire - le nombre de caractères dans le code binaire - est appelé la profondeur de bits du code binaire.
Noter que:
4 = 2 * 2,
8 = 2 * 2 * 2,
16 = 2 * 2 * 2 * 2,
32 = 2 * 2 * 2 * 2 * 2 etc.
Ici, le nombre de combinaisons de codes est le produit d'un certain nombre de facteurs identiques égal à la profondeur de bits du code binaire.
Si le nombre de combinaisons de codes est désigné par la lettre N et que la profondeur de bits du code binaire est désignée par la lettre i, alors le motif identifié dans vue générale s'écrira ainsi :
N = 2 * 2 * ... * 2.
je facteurs
En mathématiques, ces produits s'écrivent sous la forme :
N = 2 je.
L'entrée 2 i se lit comme suit : « 2 à la i-ième puissance ».
Tâche. Le chef de la tribu Multi a demandé à son ministre de développer un binaire et de traduire tout une information important. Quelle taille de binaire sera requise si l'alphabet utilisé par la tribu Multi contient 16 caractères ? Notez toutes les combinaisons de codes.
Solution. Étant donné que l'alphabet multi-tribu est composé de 16 caractères, ils ont besoin de 16 combinaisons de codes. Dans ce cas, la longueur (profondeur en bits) du code binaire est déterminée à partir du rapport : 16 = 2 i. Donc i = 4.
Pour écrire toutes les combinaisons de codes de quatre 0 et 1, nous utilisons le diagramme de la Fig. 1.13 : 0000, 0001, 0010, 0011, 0100, 0101, 0110,0111,1000,1001,1010,1011,1100,1101,1110,1111.
1.5.3. La polyvalence du codage binaire
Au début de cette section, vous avez appris que, représenté sous forme continue, il peut être exprimé à l'aide de symboles dans un langage naturel ou formel. À leur tour, les caractères d'un alphabet arbitraire peuvent être convertis en binaire. Ainsi, à l'aide du code binaire, tous les langages naturels et formels, ainsi que les images et les sons, peuvent être représentés (Fig. 1.14). Cela signifie l'universalité du codage binaire.
Les codes binaires sont largement utilisés en technologie informatique, ne nécessitant que deux états d'un circuit électronique - "on" (cela correspond au chiffre 1) et "off" (cela correspond au chiffre 0).
La simplicité de mise en œuvre technique est le principal avantage du codage binaire. L’inconvénient du codage binaire est la grande longueur du code obtenu.
1.5.4. Codes uniformes et non uniformes
Il existe des codes uniformes et non uniformes. Les codes uniformes dans les combinaisons de codes contiennent le même nombre de symboles, les codes impairs contiennent un nombre différent.
Ci-dessus, nous avons examiné les codes binaires uniformes.
Un exemple de code non uniforme est le code Morse, dans lequel une séquence de signaux courts et longs est définie pour chaque lettre et chiffre. Ainsi, la lettre E correspond à un signal court (« point »), et la lettre Ш correspond à quatre signaux longs (quatre « tirets »). Inégal vous permet d'augmenter la vitesse de transmission des messages car les symboles apparaissant le plus fréquemment dans les informations transmises ont les combinaisons de codes les plus courtes.
Dans ce cas code binaire L'alphabet primaire est construit en chaînes d'égale longueur, c'est-à-dire Tous les signes sont associés à la même quantité d'informations JE ( A) = journal 2 N.Il n'est pas nécessaire de générer un terminateur, donc pour déterminer la longueur du code, vous pouvez utiliser la formule K(A,2) > journal 2 N. L'appareil récepteur compte simplement le nombre de signaux simples discutés à l'avance et interprète la chaîne (établit à quel signe elle correspond), en la corrélant avec la table de codes. Certes, avec tout cela, les échecs sont inacceptables, par exemple, manquer (non lire) le premier signal simple entraînera un décalage dans toute la séquence de code et son interprétation incorrecte ; Le problème est résolu par la synchronisation de la transmission ou par d'autres méthodes, qui seront abordées dans le chapitre. 5. En revanche, l'utilisation d'un code uniforme s'avère être l'un des moyens de contrôler l'exactitude de la transmission, puisque le fait de la réception d'un signal simple excessif ou, à l'inverse, la réception d'un code incomplet est immédiatement interprété comme une erreur.
Un exemple de codage alphabétique uniforme est le code télégraphique Baudot, qui a remplacé le code Morse. L'alphabet initial doit contenir moins de 32 caractères ; Alors K(A, 2) = journal 2 32 = 5, ceux. Chaque caractère de l'alphabet primaire contient 5 bits d'information et est codé par une chaîne de 5 caractères binaires. Condition N≤ 32 est bien entendu produit pour les langues basées sur l'alphabet latin ( T = 27 = 26 + « espace »), mais dans l'alphabet russe, il y a 34 lettres (avec un espace) - précisément pour cette raison, nous avons dû "compresser" l'alphabet (comme dans le code de Huffman) et combiner "e" et "e" en un seul caractère, également " b" et "b", visibles dans le tableau 3.1. Après une telle compression N= 32, mais il n'existe pas de codes libres pour les symboles de ponctuation, ils sont donc absents dans les télégrammes ou sont remplacés par des abréviations alphabétiques ; il ne s'agit pas d'une limitation notable puisque, comme indiqué ci-dessus, la redondance du langage permet de restituer simplement le contenu informatif du message. Redondance du code Baudot pour la langue russe Q(r,2) = 0,148, pour les Britanniques Q(e,2) = 0,239.
Un autre exemple fondamental pour nous d’utilisation d’un codage alphabétique uniforme est la représentation d’informations symboliques (signes) dans un ordinateur. Pour connaître la longueur du code, vous devez commencer par établir le nombre de caractères de l’alphabet primaire. L'alphabet informatique doit inclure :
- 26 x 2 = 52 lettres de l'alphabet latin (y compris les minuscules et les minuscules) ;
- 33 x 2 = 66 lettres de l'alphabet russe ;
- nombres 0...9 - total 10 ;
- signes d'opérations mathématiques, signes de ponctuation, caractères spéciaux ≈ 20.
Nous constatons que le nombre total de caractères N≈ 148. Nous pouvons maintenant estimer la longueur de la chaîne de codes : K(s, 2) ≥ log 2 148 ≥ 7,21. Puisque la longueur du code est exprimée sous forme d’entier, bien sûr K(s, 2) = 8. Cette méthode de codage particulière est adoptée dans les systèmes informatiques : à tout caractère se voit attribuer un code de 8 chiffres binaires (8 bits). Cette séquence est stockée et traitée comme une seule unité (c'est-à-dire pas d'accès à un seul bit)— pour cette raison, la capacité en bits des appareils informatiques créés pour stocker ou traiter des informations est un multiple de 8. La totalité des huit bits connectés est appelée b, et la représentation des signes de cette manière - codage d'octets.
B avec un bit peut être utilisé comme unité de mesure de la quantité d'informations contenues dans un message. Un b correspond à la quantité d'informations dans un caractère de l'alphabet avec leur répartition égale. Cette méthode de mesure de la quantité d'informations est également appelée grand. Qu'il y ait un certain message (séquence de caractères) ; estimer la quantité d'informations qu'il contient selon l'approche probabiliste précédemment considérée (en utilisant la formule de Shannon (2.17)) donne je ver, et que la plus grande mesure soit égale à jeà propos la relation entre ces quantités découle de (2.7) :
Plus précisément, b est adopté comme unité de mesure pour la quantité d'informations dans le Système international d'unités SI. 1b = 8 bits. Avec b, des unités dérivées plus grandes sont utilisées pour mesurer la quantité d'informations :
L'introduction de chaînes de 8 bits permet d'encoder 2 8 =256 caractères, ce qui dépasse celui estimé ci-dessus N et, comme suit, permet d'utiliser le reste de la table de codes pour représenter des caractères supplémentaires.
Mais il ne suffit pas de se mettre d’accord sur une certaine longueur de code. Il est clair que les méthodes de codage, c'est-à-dire options de comparaison pour les signes de l'alphabet primaire il existe de nombreuses chaînes de huit bits. C’est pourquoi une harmonisation des codes est nécessaire pour garantir la comparabilité des dispositifs techniques et garantir la capacité d’échange d’informations entre de nombreux consommateurs. Un accord similaire est conclu sous la forme normalisation des tables de codes.
La première norme internationale de ce type, utilisée sur de gros ordinateurs, était EBCDIC (code d'échange décimal codé binaire étendu) Les ordinateurs et les systèmes de télécommunications utilisent un code d'octet international ASCII (Code standard américain pour l'échange d'informations).
Il régule les codes de la première moitié de la table de codes (numéros de code de 0 à 127, c'est-à-dire que le 1er bit de tous les codes est 0). Cette partie comprend des codes pour les lettres anglaises minuscules et minuscules, les chiffres, les signes de ponctuation et les opérations mathématiques, ainsi que certains codes de contrôle (chiffres de 0 à 31) générés lors de l'utilisation du clavier. Ci-dessous quelques FSC-codes:
La deuxième partie de la table des codes - elle est considérée comme une extension de la table principale - couvre les codes allant de 128 jusqu'à 255 (1er bit de tous les codes 1). Il est utilisé pour représenter les symboles des alphabets d'État (par exemple, le russe), ainsi que les symboles pseudographiques. Il existe également des normes pour cette partie, par exemple pour les signes de la langue russe, ce sont KOI-8, KOI-7, etc.
Aussi bien dans le tableau principal que dans son extension, les codes des lettres et des chiffres correspondent à leur ordre dans le dictionnaire ( ceux. ordre alphabétique) - cela offre la possibilité d'automatiser le traitement du texte et de l'accélérer.
Actuellement, une autre norme internationale de cryptage est apparue et est de plus en plus utilisée : Unicode. Sa particularité est qu'il utilise un codage 16 bits, c'est-à-dire pour représenter chaque personnage est attribué 2 b. Cette longueur de code garantit que 65 536 caractères sont inclus dans l’alphabet principal. Ceci permet à son tour de créer et d’utiliser une table de codes unique pour tous les alphabets courants.
