Brevet FR2918825A1 — publié le 20090116

Procédé codant séquentiellement sur plusieurs caractères ou plusieurs octets une information fragmentée, indépendamment de l'information pré-existante I- Introduction. La fiabilité de la lecture d'une information codée sous forme d'une suite de caractères dépend essentiellement des qualités du support et de l'écriture. En pratique ces dernières ne sont pas toujours optimisées et entraînent des défauts et des erreurs de reconnaissance des caractères. Plusieurs procédés sont utilisés pour accroître la fiabilité de lecture. Le plus courant consiste à ajouter une information complémentaire, élaborée à partir de l'information source, qui permet de corriger certaines erreurs de lecture. Plus cette information complémentaire est importante plus il est possible de corriger de caractères. Cette information complémentaire étant issue de l'information à fiabiliser ou source, constitue une forme de redondance dont la quantité correspond à un pourcentage de l'information source. II- L'existant. L'information redondante s'ajoute par principe à l'information source, l'ensemble source et redondance occupe plus de place que la source et dépend du pourcentage de redondance, lequel varie généralement de 5 à 30%. L'ensemble représente alors de 1,05 à 1,3 fois la surface de la source. Cette accroissement peut se manifester directement, par exemple, quand on ajoute une clé de n caractères à un texte de m caractères (soit m + n caractères au total). Il se manifeste différemment dans le cas des codes 2D, par exemple, où la redondance est répartie sur l'ensemble de la surface du code. Dans ce dernier cas, la surface prise par l'ensemble, source et code, varie par bonds en fonction du pourcentage de redondance et de la taille de la source. III- Nouveauté. Certaines structures de caractères sur support physique et d'octets en machine peuvent coder individuellement plusieurs variables. Ils permettent de coder à la fois une valeur intrinsèque et des informations de contrôle de la structure ou des paramètres supplémentaires comme la taille des caractères. La nouveauté du présent procédé est de répartir, en plus de leur représentation individuelle intrinsèque, une information supplémentaire répartie individuellement sur au moins un groupe de caractères ou d'octets préexistants. Cette information supplémentaire est souvent une redondance de l'information portée par ces caractères ou ces octets. Ainsi, la totalité de la redondance de l'information générale est supportée par les caractères eux-mêmes sans nécessiter d'en rajouter d'autres. Ceci présente l'avantage de ne pas augmenter la surface du texte ou fichier sources pour les taux usuels de redondance. La répartition de cette information supplémentaire exige un découpage particulier de sa représentation au niveau du groupe de caractères ou du groupe d'octets, lesquels gagnent à être marqués et hiérarchisés pour faciliter leur repérage et leur exploitation. Ce procédé s'applique particulièrement bien aux caractères Alphacodes DoteM (du même auteur)..50 IV- Description du procédé. Pour expliquer le présent procédé à partir d'un cas concret, nous prendrons le procédé Dotent (Brevet n 01 02889) et modifierons les caractères pour y incruster en surcharge un pourcentage de redondance extrait de l'information portée par l'ensemble de ces caractères. Il convient d'inserrer l'information redondante élaborée à partir d'une partie ou de la totalité de l'ensemble du message et de la coder au moins par demi octet au niveau de chaque caractère. Autrement dit, chaque caractère possède plusieurs dots (équivalent bits) porteurs d'éléments de la redondance globale en plus de sa valeur intrinsèque. Dans ce cas concret les caractères possédent 2 colonnes ou plus. Chaque type correspond à un nombre donné de colonnes constitutives et présente des propriétés particulières détaillées ci-aprés. Remarques : correspondancedirecte dots-bits. Tous les caractères 2 colonnes ou plus, possèdent leur dual en informatique sous forme de groupes d'octets en nombre égal à celui des colonnes. Les propriétés des uns sont directement transposables aux autres ; autrement dit, ce qui est valable pour des caractères à 2 ou 3 colonnes l'est aussi pour leur dual ou groupes de 2 ou 3 octets en machine, d'où la correspondance directe caractères papier octets machine, sachant que toute colonne de dots correspond de fait à un octet en machine ou sur réseaux comme illustré figures 8 pour les colonnes de dots et 9 pour les octets de bits. Par ailleurs, ce qui est valable pour une information de redondance, l'est pour toute information dont le volume est égale ou supérieur à la moitié d'un groupe de caractères ou d'octets donné. Les caractères porteurs d'information complémentaire sont de 2 types : les caractères marqués et ordonnés ou hiérarchisés et les caractères courants non hiérarchisés. IV-1 Caractères à 2 colonnes sans hiérarchie -Figure 1- Pour tous les caractères non hiérarchisés l'en-tête A est noire et constante. Elle constitue une ligne noire de l'épaisseur d'un dot quand les caractères sont juxtaposés formant une seule composante connexe par rangée de caractères pour faciliter sa détection. Par principe le nombre de dots par colonne est variable. Nous présentons ici des colonnes de 10 dots qui s'appliquent particulièrement au présent procédé. La valeur intrinsèque qu'ils peuvent coder va de 0 à 255 . Dans le cas des caractères sans hiérarchie, l'en-tête est invariable. Nous verrons qu'elle sert à coder les niveaux de hiérarchie quand ils existent en plus de la détection du sens des caractères et de la ligne d'écriture. La Figure 1 représente 2 caractères jointifs de 2 colonnes. Les dots noirs et blancs sont invariants. Les autres varient suivant le caractère représenté. Par caractère, chaque seconde colonne (2) code en binaire sur 8 dots (ou bits) une valeur parmi 256, de 2 (i), 21 (j), 22 (k), .. jusqu'à 2' (q). Le premier dot (B) de la première colonne (1) code la parité des 16 dots ou bits des 2 colonnes. Il est noir (ou = 1) de façon que le nombre des dots noirs variables des 2 colonnes, y compris le dot de parité lui-même, soit pair. Les dots représentant un contrôle de parité possèdent une étoile. Le second (C) indique s'il s'agit d'un caractère, dot noir, ou d'une balise (tag possédant un sens) dot blanc. Le troisième (D) précise si le caractère est à 2 colonnes (noir) ou plus (blanc). Les quatre dots E, F, G et H supportent un demi octet de redondance globale, le E correpondant au plus faible poids et le H au plus fort. Cette première colonne supporte l'essentiel voire la totalité de l'information supplémentaire(redondante). Nous obtenons une redondance de 4 bits pour les 8 bits de l'octet, soit un pourcentage de 50%, rarement atteint avec les autres codes 2D qui plafonne généralement à 30%. Remarque : Il est utile dans certains cas d'augmenter l'extension du codage de la valeur donc de réduire à 3 ou 2 dots la représentation de la redondance, ainsi par exemple G et H codent 28 et 29 et F et H codent la redondance dont le pourcentage tombe à 25 %. IV-2 - Caractères à 3 colonnes sans hiérarchie -Figure 2- : La valeur intrinsèque qu'ils peuvent coder va de 256 à 4096 . La Figure 2 représente 2 caractères jointifs de 3 colonnes. Les dots noirs et blancs sont invariants. Les autres varient suivant le caractère représenté. Les 2 premières colonnes et l'en-tête A sont indentiques à celles du caractère à 2 colonnes. Le premier dot R de la troisième colonne code sa propre parité de sorte que le nombre de dots noirs variables soit toujours pair. Le dot suivant S précise si cette colonne représente une variable indépendante ou si elle constitue l'extension de la seconde colonne Le dot T indique que cette 31 le colonne est la dernière (noir) ou pas (caractère à 3 colonnes ou plus). Les 2 dots suivants U, V codent l'extension de la redondance globale de la colonne 1 et les 4 derniers dots W.,X,Y,Z codent l'extension de la valeur du caractère c'est-à-dire respectivement : 28 , 29 ,210 , 211 20 IV- 3 - La figure 3 représente 2 caractères à 4 colonnes sans hiérarchie. En règle générale, les colonnes supérieures à la troisième, ici la quatrième, sont de même structure que la troisième. Les caractères ou balises de cette taille codent de 0 à 65535 . Chaque taille 25 supplémentaire multiplie la valeur maximale par 16 (5 col - 1 048 575 etc..). Remarque : Comme la capacité de codage de la valeur intrinsèque du caractère, la capacité de codage de la redondance dépend du nombre de colonnes de la structure des caractères. La structure 2 colonnes a une capacité de 4 dots (ou bits) soit 1 demi octet par caractère. 30 La structure 3 colonnes a une capacité de 4 (colt) + 2 (col3) = 6 dots par caractère. Si n est le nombre de colonnes par caractère on a : Nombre de dots disponibles par caractères pour redondance (par exemple) = 4 +2(n-2). Nombre de dots disponibles par caractère pour coder Unicode (par exempl) = 8+4(n-2), soit le double de la précédente. 35 - Si l'on s'en tient à ne coder qu'un demi octet de redondance sur la première colonne de chaque caractère, on obtient pour le calcul du pourcentage de redondance par type de structure avec n = nombre de colonnes par caractère, plus le codage d'un demi octet par caractère sur 2 caractères consécutifs: ^ Par caractère 2 colonnes, 40 o la capacité de codage redondance = 1/2 octet, o la capacitéde codage valeur (type unicode) = 1 octet, o soit le pourcentagede redondance = 50 % ^ Par caractère 3 colonnes, o la capacité de codage redondance = 1/2 octet, 45 o la capacitéde codage valeur ( type unicode) = 1,5 octet, o soit le pourcentagede redondance = 33 % ^ Par caractère 4 colonnes, o la capacité de codage redondance = 1/2 octet, o la capacitéde codage valeur (type unicode) = 2 octets, 50 o soit le pourcentagede redondance = 2 5 %. Si l'on utilise, en plus de la 1' colonne, la capacité de codage supplémentaire de 2 dots sur chaque colonne après le seconde ( si elles existent) on peut maintenir le pourcentage maximal de redondance à 50% pour toutes les tailles de caractères et de balises. IV- 4 - Caractères avec hiérarchie( marqués et ordonnés). De ce qui précède on constate qu'il n'est pas possible d'intégrer un octet (8 dots ou 8 bits suivant le cas) de redondance par caractère. L'information supplémentaire à coder étant une suite d'octets, il est nécessaire de fragmenter ces octets notamment par moitié pour qu'ils soient incrustés par bloc de 4 + 2(n-2) dots par caractère si n = le nombre de colonnes par caractère. Il est apparu intéressant d'affecter plusieurs niveaux hiérarchiques (ou rangs) aux caractères hôtes afin de repérer les débuts et fins d'octet et reconstruire l'information fragmentée de manière plus sûre qu'une suite continue et de dots (ou d'octets) non repérés. Pour se faire la partie supérieure A des caractères est modifiée comme illustrées figures 4, 5 et 6 suivant que la structure est à 2, 3 ou 4 colonnes. Notons que le nombre de colonnes n'est pas limitatif. Pour toutes les structures, le premier dot de la première colonne est noir afin de faciliter la détection et le cadrage. Sur une suite de tels caractères on observe un crénelage de 1 dot noir entre 3 blancs. Pour la structure à n=3 colonnes, le caractère de rang 1 possède une en-tête A composée de 1 noir et n-1 = 2 blancs ; le second affiche une en-tête de 2 noirs et n-2=1 blanc. Toutefois, le résultat du calcul de la redondance s'exprime généralement en octets (8 bits), il faut donc 2 caractères successifs de 2 colonnes pour coder un octet de redondance (à raison d'un demi octet de redondance par caractère). C'est dire que le poucentage de redondance ne peut dépasser 50% sans ajouter de caractères supplémentaires. Par contre il peut être inférieur. Pour les caractères qui ne supporteraient pas de redondance, les dots E, F, G, H seraient tous nuls (blancs). Si n est le nombre de colonnes de la structure et p le rang du caractère dans la hiérarchie, l'en-tête d'un caractère peut se définir par une suite de dots noirs et blancs comme suit : Nombre de dots noirs = p et nombre de dots blancs = n - p. On arrive à une hiérarchie à : Qui se construit, par exemple, comme suit : Pour les caractères à 2 colonnes de la figure 4 ^ une en-tête du caractère de rang 1 noir-blanc et ^ une en-tête du caractère de rang 2 noir-noir. Pour les caractères à 3 colonnes de la figure 5 ^ une en-tête du caractère de rang 1 est noir-blanc-blanc et ^ une en-tête du caractère de rang 2 est noir-noir- blanc et ^ une en-tête du caractère de rang 3 est noir-noir-noir. Pour les caractères à 4 colonnes de la figure 6 ^ une en-tête du caractère de rang 1 est noir-blanc-blanc-blanc et ^ une en-tête du caractère de rang 2 est noir-noir-blanc-blanc et ^ une en-tête du caractère de rang 3 est noir-noir-noir-blanc et ^ une en-tête du caractère de rang 4 est noir-noir-noir-noir. Et ainsi de suite suivant le nombre de colonnes des caractères ou balises. ^ 2 niveaux pour les caractères 2 colonnes, ^ 3 niveaux pour les 3 colonnes, donc ^ n niveaux pour n colonnes... Remarque : Les pieds de colonnes, figures 1, 2, 3, 4, 5 et 6 limitent la partie inférieure des colonnes. Elles permettent de détecter et d'identifier la première colonne de chaque caractère et confirmer le type de caractère 2 ou 3 ou 4 ... colonnes grâce à la forme du crénelage des caractères juxtaposés. V- Sens de codage de l'information de redondance. La suite des octets représentant un calcul d'information redondante, (comme le reed salomon ou CRC ou de type Turbocodes etc.. ) peut être codée de demi octet en demi octet, c'est-à-dire caractère par caractère, de gauche à droite comme l'écriture latine usuelle. Toutefois, afin d'accroître les possibilités de correction de l'écriture en cas d'altération d'une des extrémités, les demi octets de redondance gagnent à être écrits de droite à gauche à l'opposé des octets d'information source. En effet, suivant le type de calcul de la redondance il peut être intéressant de croiser début de texte et fin de redondance et vice versa pour conserver le maximum d'information en cas d'altération de l'écriture. Remarque : Les contrôles CRC qui sont généralement de quelques octets peuvent être placés en plusieurs endroits séquentiellement dans un texte (grâce à l'emploi de balises) ou par exemple, tous les 30 caractères, de façon à sécuriser la lecture en cas de défauts aléatoires d'impression. Ainsi, des CRC de 5 octets pourront prendre place dans 10 caractères support par exemple. Ce dispositif peut être généralisé et faire que tous les 12 caractères on code le résultat d'un CRC de 6 octets calculés sur les 12 caractères support et ainsi de suite. VI- Adaptation du logiciel d'application de redondance. Normalement les polices de caractères sont enregistrées selon des format standards (comme .ppt . vfp .v1c...etc.) qui sont exploités directement par les éditeurs de textes (ou traitements de textes). Dans ce cas chaque caractère a une structure pré-établie qui est interprétée par les logiciels standards de visualisation ou d'impression. Le présent procédé utilise au départ les mêmes opérations, mais avant la visualisation et surtout l'impression, il convient de calculer l'information de redondance et de l'injecter au sein des différents caractères. Cela revient à recalculer les nouvelles valeurs de chaque caractères qui correspondront à la nouvelle structure de chaque caractère pour représenter à la fois la valeur d'origine (type Unicodes) plus la partie de la redondance qui lui est affectée. Ce logiciel peut être automatiquement appelé avant l'impression et éventuellement la visualisation de façon transparente pour l'utilisateur. VII- Conclusion. -Figure 7- Concernant l'information de redondance, le procédé permet la juxtaposition de 3 niveaux de redondance qui sont imbriqués pour plus d'efficacité : 2 niveaux internes et un externe. Les deux niveaux internes se divisent en : ^ Un niveau individuel avec le dot de contrôle de parité des colonnes (P figure 7) et ^ Le niveau de redondance générale codée sur les caractères selon le procédé lui- même où le codage de la redondance générale s'effectue principalement sur la première colonne des caractères (R1 figure 7). Un niveau externe qui consiste en : ^ Un groupe de caractères ajouté, par exemple, à une extrémité du texte source comme un CRC I( R2 figure 7) . L'ensemble peut être amélioré avec l'utilisation de balises ( figure 7) pour indiquer le début B1 , la fin B3 et la zone de redondance CRC B2 par exemple. Suite de la conclusion : il s'agit d'un procédé de codage intégrant une information supplémentaire au sein de caractères, de symboles graphiques sous forme d'un ou de plusieurs groupements de dots caractérisé en ce que ces groupements s'ajoutent à ceux codant la valeur intrinsèque du caractère sans les altérer et en ce que les caractères support sont marqués graphiquement de façon à les différencier et les ordonner. Dans ce procédé de codage les caractères sont marqués au moyen du dessin de leur en-tête qui varie en fonction de la structure du caractère pour différentier autant de rangs que de colonnes constitutives. Le marquage hiérarchisé est assuré par l'en-tête pour lesquelles toutes les premières colonnes ont un dot noir. Le caractère de premier rang a une en-tête avec 1 seul dot noir ; le caractère de second rang a une en-tête dont les 2 premiers dots sont noirs et les autres blancs quand ils existent. Le caractère de rang 3 possède 3 dots noirs consécutifs, les autres sont blancs s'ils existent et ainsi de suite. L'information supplémentaire incrustée dans les caractères est issue d'un calcul de redondance et le sens d'incrustation de cette information d'un caractère à l'autre soit, de préférence, dans le sens inverse de celui du codage de l'information intrinsèque source du calcul de redondance. Ce procédé de codage permet à un groupement de caractères de présenter plusieurs niveaux de redondance : - un au sein des caractères eux-mêmes que sont les contrôles de parité des colonnes, - un second avec la redondance incrustée au moins dans une colonne des caractères et, - un niveau externe qui consiste en un groupe de caractères comme un CRC ajouté, de préférence, à une extrémité du groupement d'origine. Ainsi, en dehors de l'en-tête, la structure de la colonne dé- côntrole ou de l'octet équivalent est composé de préférence: -de dot (ou bit) représentant la parité des 2 premières colonnes, - d'un dot (ou bit) représentant le type : balise ou caractère, - d'un dot (ou bit) précisant si le caractère est à 2 colonnes ou plus, - d'au moins 4 dots (ou bits) pour coder l'information supplémentaire dont la redondance. En effet, en dehors de l'en-tête, la structure de la colonne de contrôle ou de l'octet octet équivalent est composé de préférence: - de dot (ou bit) représentant la parité des 2 premières colonnes, - d'un dot (ou bit) représentant le type : balise ou caractère, - d'un dot (ou bit) précisant si le caractère est à 2 colonnes ou plus, - d'au moins 2 dots (ou bits) pour coder l'information supplémentaire dont la redondance. - d'au plus 2 dots (ou bits) pour coder l'extension de la valeur intrinsèque. Précisons que les bits des octets en machine ou sur réseaux sont identiques (1= noir et 0= blanc) aux dots des colonnes dépouillées des en-têtes et pieds de colonne (figures 8 et 9). Revendications 1. Procédé de codage intégrant une information supplémentaire au sein de caractères ou de symboles graphiques caractérisé en ce que : Premièrement, cette information est ajoutée au codage de la valeur intrinsèque du caractère ou du symbole à l'aide de dots restés libres de toute information, et deuxièmement les caractères ou les symboles ainsi complétés sont marqués à l'aide d'autres dots libres de façon à les différencier et à les ordonner. 2. Procédé de codage selon la revendication 1 caractérisé en ce que le rang des caractères ou des symboles est précisé par le dessin de leur en-tête pour différentier autant de 15 rangs que de colonnes constitutives de la façon suivante : le caractère ou le symbole de premier rang a une en-tête avec 1 seul dot noir ; le caractère ou le symbole de second rang a une en-tête dont les 2 premiers dots sont noirs et les autres blancs quand ils existent, le caractère ou le symbole de rang 3 possède 3 dots noirs consécutifs, les autres sont 20 blancs s'ils existent et ainsi de suite. 3. Procédé de codage selon les revendications 1 et 2 caractérisé en ce que l'information supplémentaire incrustée dans les caractères ou les symboles est issue d'un calcul de redondance et que le sens d'incrustation de cette information d'un caractère ou d'un 25 symbole à l'autre soit, de préférence, dans le sens inverse de celui du codage de l'information intrinsèque source du calcul de redondance. 4. Procédé de codage selon les revendications précédentes caractérisé en ce qu'en dehors de l'en-tête, la structure de la colonne comportant le contrôle de la structure du 30 symbole ou du caractère ou de l'octet correspondant en machine soit composé : - d'un dot (ou bit) représentant le type : balise ou caractère, - de dot (ou bit) représentant la parité des 2 premières colonnes, - d'un dot (ou bit) précisant si le caractère est à 2 colonnes ou plus, - d'au moins 4 dots (ou bits) pour coder l'information supplémentaire dont la 35 redondance. 5. Procédé de codage selon les revendications précédentes caractérisé en ce qu'en dehors de l'en-tête, la structure de la colonne comportant le contrôle de la structure du caractère ou de l'octet correspondant soit composé : 40 - de dot (ou bit) représentant la parité des 2 premières colonnes, - d'un dot (ou bit) représentant le type : balise ou caractère, - d'un dot (ou bit) précisant si le caractère est à 2 colonnes ou plus, -d'au moins 2 dots (ou bits) pour coder l'information supplémentaire dont la redondance. 45 - d'au plus 2 dots (ou bits) pour coder l'extension de la valeur intrinsèque. 6. Procédé de codage selon les revendications précédentes caractérisé en ce que les bits des octets en machine ou sur réseaux sont identiques (1= noir et 0= blanc) aux dots des colonnes dépouillées des en-têtes et pieds de colonne. 50