BOUTITON, Sophie (7 rue Lande d'Abas, Cesson Sévigné, F-35510, FR)
LE GUELVOUIT, Gaëtan (7 rue Lande d'Abas, Cesson Sévigné, F-35510, FR)
BOUTITON, Sophie (7 rue Lande d'Abas, Cesson Sévigné, F-35510, FR)
| Revendications 1. Procédé de codage d'une séquence d'ensembles marqués de données (CT) en fonction d'une séquence de symboles d'entrée (Id), ladite séquence de données (CT) comprenant au moins un ensemble marqué de données (C(i)) obtenu (1 10) pour chaque symbole d'entrée (ld(i)), le procédé étant caractérisé en ce que chacun desdits ensembles marqués de données (C(i)) obtenus comprend une pluralité d'occurrences d'un symbole de marquage (M(i)) sélectionné (1 1 1) en fonction dudit symbole d'entrée (ld(i)). 2. Procédé de codage selon la revendication 1 , caractérisé en ce que, pour chaque symbole d'entrée (ld(i)), le symbole de marquage (M(i)) sélectionné est différent du symbole de marquage (M(i-1 )) sélectionné pour le symbole d'entrée précédent (ld(i-1 )). 3. Procédé de codage selon la revendication 2, caractérisé en ce que, pour chaque symbole d'entrée (ld(i)), la sélection du symbole de marquage (M(i)) se fait en fonction du symbole de marquage (M(i-1 )) sélectionné pour le symbole d'entrée précédent (ld(i-1 )) et de la transition, dans un treillis de codage, d'un état de départ (E(i-1 )) vers un état d'arrivée (E(i)) différent de l'état de départ (E(i-1 )). 4. Procédé de codage selon la revendication 3, dans lequel la transition d'un état de départ (E(i-1 )) vers un état d'arrivée (E(i)) se fait selon la formule suivante : E(i) = nr E(i - 1 ) + ld(i) modulo e , où nr est le nombre de symboles possibles pour le symbole d'entrée, et e est un nombre pair d'états possibles dans le treillis de codage, avec les conditions suivantes ; E(0) = 0 si i = 0 E(i) = nr si E(i - 1 ) = 0 et ld(i) = 0 E(i) = 0 pour E(i - 1 ) = e - 1 et ld(i) = e - 1 + nr modulo e 5. Procédé de codage selon l'une des revendications 1 à 4, caractérisé en ce que, pour chaque symbole d'entrée (ld(i)), l'ensemble marqué de données (C(i)) est obtenu par sélection (1 13') d'un ensemble parmi une pluralité d'ensembles marqués de données enregistrés (105) préalablement en fonction du symbole de marquage (M(i)) sélectionné. 6. Procédé de codage selon l'une des revendications 1 à 5, caractérisé en ce que, pour chaque symbole d'entrée (ld(i)), une séquence intermédiaire (CT(Î)) est constituée à partir de la séquence intermédiaire (Cr(i- 1 )) obtenue pour le symbole d'entrée précédent (ld(i-1 )) à laquelle est ajoutée l'ensemble de données (C(i)) sélectionné pour ledit symbole d'entrée (ld(i)), la séquence d'ensemble de données marqués (CT) correspondant à la séquence intermédiaire (Ci(k)) obtenue pour le dernier symbole d'entrée (ld(k)). 7. Procédé de décodage d'une séquence (CT) d'ensembles marqués de données (C(i)) pour retrouver une séquence de symboles d'entrée (Id), chacun desdits ensembles marqués de données (C(i)) comprenant une pluralité d'occurrences d'un symbole de marquage (M(i)), le procédé de décodage utilisant un treillis de décodage dans lequel, pour chaque état initial de décodage (E(j'-1 )), il existe au moins une transition vers un état suivant de décodage (E(j')) identique à l'état initial (E(j'-1 )) associée à la répétition du symbole de marquage, le procédé comprenant, pour chaque symbole de marquage (M(j)) détecté dans la séquence d'ensembles marqués de données, la vérification (210) que le symbole de marquage (M(j)) correspond à une transition dans le treillis de décodage et la détermination (230) du symbole d'entrée (ld(i)) associé à cette transition si ladite transition n'a pas lieu entre deux états identiques (220). 8. Procédé de décodage d'une séquence (CT) d'ensembles marqués de données selon la revendication 7, caractérisé en ce qu'il comporte en outre, si le symbole de marquage (M(j)) détecté (210) ne correspond à aucune transition parlant d'un premier état de décodage (E(j')), la vérification (240) successive que chaque symbole de marquage détecté suivant correspond à une transition du treillis de décodage jusqu'à trouver un symbole de marquage (M(j+I)) correspondant à une transition partant d'un deuxième état de décodage (E(j'+I')), et la sélection (250) d'au moins un symbole d'entrée correspondant au meilleur chemin allant dudit premier état de décodage (E(j')) au deuxième état de décodage (E(j'+I')). 9. Procédé de décodage d'une séquence d'ensembles de données marqués (CT) selon la revendication 8, caractérisé en ce que l'algorithme de Viterbi est utilisé pour sélectionner (250) ledit au moins un symbole d'entrée. 10. Dispositif de codage (320) d'une séquence d'ensembles marqués de données (CT) en fonction d'une séquence de symboles d'entrée (Id), caractérisé en ce qu'il comporte des moyens de codage (321 ,323) adaptés pour mettre en œuvre les étapes du procédé de codage selon les revendications 1 à 6. 1 1 . Dispositif de décodage (360) d'une séquence d'ensembles marqués de données (CT), caractérisé en ce qu'il comporte des moyens de décodage (363) adaptés pour mettre en œuvre les étapes du procédé de décodage selon l'une des revendications 7 à 9. 12. Système de transmission (300) d'une séquence d'ensembles marqués de données (CT) comprenant une unité de transmission (310) et une unité de réception (340). caractérisé en ce que l'unité de transmission comprend un dispositif de codage (320) selon la revendication 10 et en ce que l'unité de réception comprend un dispositif de décodage (360) selon la revendication 1 1 . 13. Produit de programme d'ordinateur enregistré sur un support de mémorisation pour exécution par un dispositif de codage et apte à mettre en œuvre les étapes du procédé de codage selon l'une des revendications 1 à 6. 14. Produit de programme d'ordinateur enregistré sur un support de mémorisation pour exécution par un dispositif de décodage et apte à mettre en œuvre les étapes du procédé de décodage selon l'une des revendications 7 à |
L'invention concerne le domaine du codage et du décodage avec correction d'erreur adapté au marquage de données numériques, en particulier dans le cadre du tatouage multimédia transactionnel par bloc.
Dans le domaine de la transmission de données numériques, le marquage d'ensembles de données à transmettre est répandu. Un tel marquage, également appelé couramment tatouage multimédia, consiste à insérer une marque dans un document multimédia contenant par exemple du son, des images ou des vidéos. Une telle marque doit être invisible et correspondre à un message spécifique.
L'une des principales utilisations de cette technologie de tatouage est la protection d'un document grâce au marquage dit « transactionnel » : l'identifiant du destinataire du document est inséré par tatouage avant sa transmission. Cela permet de retrouver l'origine de la fuite s'il y a redistribution illégale du document.
De façon classique, l'insertion d'une telle marque se fait en modifiant le contenu de base du document, c'est-à-dire les pixels quand on marque des images ou des vidéos, ou les échantillons quand on marque des signaux sonores. Le document marqué est ensuite compressé, par exemple au format JPEG pour des images ou MPEG pour les vidéos, en vue de sa transmission et/ou de son archivage.
Le tatouage se fait donc habituellement avant l'étape de compression des documents à marquer. Il existe certes quelques techniques de tatouage qui peuvent marquer directement des contenus compressés, mais elles ne fonctionnent que sur un format de compression donné et sont limitées en termes de performance. Pour des documents volumineux comme des fichiers de sons et de vidéos, la phase de compression est très gourmande en temps. Dans les scénarios de distribution de documents où le temps de transmission doit être le plus court possible, cette contrainte de temps constitue un frein à la mise en place du tatouage transactionnel. En effet, lorsqu'un client télécharge un film sur une plateforme de vidéo « à la demande », il n'est pas possible de laisser ce client attendre une heure supplémentaire pour permettre la compression du film.
Afin de remédier à ce problème, une technique dite de « tatouage par bloc » a été développée. Cette technique permet de faire du tatouage transactionnel sans avoir besoin de compression post-tatouage. L'article "VIDEO-DNA ; LARGE-SCALE SERVER-SIDE WATERMARKING" de Ivan Kopilovic et al. décrit une telle technique de tatouage par bloc.
Ce type de technique de tatouage par bloc est illustré sur les figures 1A à 1 C. Comme illustré sur la première figure 1 A, le document F à tatouer est d'abord préparé en produisant un nombre n de versions tatouées F, avec des marques distinctes. Ces n versions tatouées Fi sont ensuite compressées afin d'obtenir un nombre n de fichiers C, distincts, tatoués et compressés.
Ainsi, dans l'exemple présent de la figure 1A, avec n = 4, quatre versions F A - F D respectivement tatouées par une marque A, B, C et D sont produites. Ces quatre versions tatouées sont ensuite compressées, afin d'obtenir respectivement les quatre fichiers distincts tatoués et compressés C A , Ce, Ce et C D .
Lors d'une transaction avec un client, le tatouage final se fait alors en deux phases, comme illustré sur la figure 1 B.
Dans une première phase, l'identifiant du client, dans l'exemple présent « user23 », est codé en une séquence de symboles uniques, ces symboles appartenant à un ensemble des marques possibles, l'ensemble {A, B, C, D} dans l'exemple présent. Ensuite, dans un deuxième temps, un programme de sélection construit un fichier CT en sélectionnant des blocs dans les fichiers CA à CD en fonction de la séquence de symboles définie lors de la première phase.
Cette phase de tatouage est extrêmement rapide car il s'agit de simples manipulations de fichiers.
Lorsque l'on désire retrouver ultérieurement l'identifiant du client à partir du fichier CT, le procédé de décodage illustré à la figure 1 C peut être employé. La lecture de la marque globale depuis le fichier ainsi marqué se fait en lisant la marque contenue dans chaque bloc pour former une séquence de symboles. La séquence de symboles ainsi obtenue est ensuite décodée pour redonner l'identifiant du client.
Ce type de tatouage par bloc, bien que représentant une avancée, souffre toutefois de certains problèmes. En effet, le document marqué est susceptible de subir de multiples modifications telles qu'un changement de format de compression, des conversions ou des traitements divers. De telles modifications peuvent détériorer la bonne lecture des marques et donc compromettre le décodage de l'identifiant. Une fonction de décodage permettant de corriger les erreurs spécifiques à la technique de tatouage par bloc est donc nécessaire.
Trois types d'erreur sont possibles avec un tel procédé de tatouage par bloc :
a) si une des marques est mal interprétée, un des symboles de la séquence est remplacé par un autre et l'on parle d'erreur de substitution. Ceci arrive, par exemple, quand on lit une séquence A D B A D A B A C a la place de la séquence A D B Ç D A B A C.
Ce type d'erreur de substitution peut être corrigé par des codes correcteurs classiques, comme ceux prévus pour le codage canal.
b) si une des marques ne peut être lue, il y a alors erreur par effacement et il manque un symbole dans la séquence. Ceci arrive, par exemple, quand on lit une séquence A D C D A B A C au lieu de lire la même séquence A D B C D A B A 0. c) si la taille des blocs est changée, par exemple en changeant de format de compression, une marque peut être lue en plusieurs exemplaires, ce qui ajoute des symboles supplémentaires dans la séquence. Ceci se traduit alors, par exemple, par la lecture d'une séquence A D B B C D A B A C au lieu de la même séquence A D B C D A B A C.
Les deux derniers types d'erreur ne peuvent pas être corrigés avec un code correcteur classique. Il n'existe pas, à notre connaissance, de code correcteur adapté à la problématique du tatouage par bloc et pouvant corriger aussi bien les substitutions que les effacements ou les duplications de symboles, ces trois types d'erreurs pouvant d'ailleurs être combinés. Il serait également souhaitable qu'un tel code soit aussi insensible aux décalages de symboles.
La présente invention a pour objet de remédier aux inconvénients précités en proposant un procédé de codage permettant de corriger aussi bien les substitutions que les effacements ou les duplications de symboles. Le procédé de codage proposé est par ailleurs insensible aux décalages de symboles.
Elle propose à cet effet un procédé de codage d'une séquence d'ensembles marqués de données en fonction d'une séquence de symboles d'entrée, ladite séquence de données comprenant au moins un ensemble marqué de données obtenu pour chaque symbole d'entrée, dans lequel chacun desdits ensembles marqués de données obtenus comprend une pluralité d'occurrences d'un symbole de marquage sélectionné en fonction dudit symbole d ' entrée. Avec un tel procédé de codage, une erreur d'effacement d'un des symboles de marquage peut être détectée lors du décodage de la séquence d'ensembles marqués de données.
De façon avantageuse, pour chaque symbole d'entrée, le symbole de marquage sélectionné est différent du symbole de marquage sélectionné pour le symbole d'entrée précédent. Ceci permet de détecter plus facilement une erreur de duplication d'un des symboles de marquage. En particulier, pour chaque symbole d'entrée, la sélection du symbole de marquage se fait en fonction du symbole de marquage sélectionné pour le symbole d'entrée précédent et de la transition, dans un treillis de codage, d'un état de départ vers un état d'arrivée différent de l'état de départ.
Dans un mode de réalisation avantageux, la transition d'un état de départ vers un état d'arrivée se fait selon la formule :
E(i) = n r E(i - 1 ) + ld(i) modulo e
où n r est le nombre de symboles possibles pour le symbole d'entrée, et e est un nombre pair d'états possibles dans le treillis de codage, avec les conditions suivantes :
E(0) = 0 si i = 0
E(i) = n r si E(i - 1 ) = 0 et ld(i) = 0
E(i) = 0 pour E(i - 1 ) = e - 1 et ld(i) = e - 1 + n r modulo e
Avec la formule et les conditions suivantes, le treillis de codage employé garantit qu'il ne puisse y avoir aucune transition, pour chaque symbole d'entrée, entre deux états identiques dans le treillis de codage.
Dans un mode de réalisation avantageux, pour chaque symbole d'entrée, l'ensemble de données marqué est obtenu par sélection d'un ensemble parmi une pluralité d'ensemble de données marquées enregistrées préalablement en fonction du symbole de marquage sélectionné. Il est ainsi possible d'accélérer le processus de génération de la séquence d'ensemble marqués de données après réception de la séquence de symboles d'entrée, ce qui est particulièrement avantageux dans le contexte d'un codage transactionnel.
Avantageusement, pour chaque symbole d'entrée, une séquence intermédiaire est constituée à partir de la séquence intermédiaire obtenue pour le symbole d'entrée précédent à laquelle est ajoutée l'ensemble de données sélectionné pour ledit symbole d'entrée, la séquence d'ensembles marqués de données correspondant à la séquence intermédiaire obtenue pour le dernier symbole d'entrée. Ceci permet une mémorisation progressive de la séquence d'ensembles marqués de données. La présente invention vise aussi un procédé de décodage d'une séquence d'ensembles marqués de données pour retrouver une séquence de symboles d'entrée, chacun desdits ensembles marqués de données comprenant une pluralité d'occurrences d'un symbole de marquage, le procédé de décodage utilisant un treillis de décodage dans lequel, pour chaque état initial de décodage, il existe au moins une transition vers un état suivant de décodage identique à l'état initial de décodage associée à la répétition du symbole de marquage, le procédé comprenant, pour chaque symbole de marquage détecté dans la séquence d'ensembles marqués de données, la vérification que le symbole de marquage correspond à une transition dans le treillis de décodage et la détermination du symbole d'entrée associé à cette transition si ladite transition n'a pas lieu entre deux états identiques.
Un tel procédé de décodage permet de décoder la séquence d'ensembles marqués en différenciant les répétitions de symbole de marquage, afin de pouvoir détecter et corriger les erreurs d'effacement.
Avantageusement, le procédé de décodage comporte en outre, si le symbole de marquage détecté ne correspond à aucune transition partant d'un premier état de décodage, la vérification successive que chaque symbole de marquage détecté suivant correspond à une transition du treillis de décodage jusqu'à trouver un symbole de marquage correspondant à une transition partant d'un deuxième état de décodage, et la sélection d'au moins un symbole d'entrée correspondant au meilleur chemin allant dudit premier état de décodage au deuxième état de décodage. Il est alors possible de retrouver la séquence correcte de symboles d'entrée en cas d'erreur de substitution, d'effacement ou de répétition.
Dans un mode de réalisation préféré, l'algorithme de Viterbi est utilisé pour sélectionner ledit au moins un symbole d'entrée. Cet algorithme est particulièrement efficace pour retrouver une séquence correcte dans un treillis de décodage.
La présente invention vise par ailleurs un dispositif de codage d'une séquence d'ensembles marqués de données en fonction d'une séquence de symboles d'entrée comportant des moyens de codage adaptés pour effectuer les étapes du procédé de codage selon la présente invention.
La présente invention vise également un dispositif de décodage d'une séquence d'ensembles marqués de données comportant des moyens de décodage adaptés pour effectuer les étapes du procédé de décodage selon la présente invention.
La présente invention vise par ailleurs un système de transmission d'un ensemble de données comprenant une entité d'émission et une entité de réception, lesquelles comportent respectivement un dispositif de codage et un dispositif de décodage ci-dessus.
L'invention a aussi pour objet un programme d'ordinateur comprenant des instructions de code de programme pour l'exécution des étapes respectivement du procédé de codage et du procédé de décodage ci-dessus lorsque ledit programme est exécuté sur un ordinateur.
Les procédés de codage et de décodage ainsi que les dispositifs mettant en œuvre ces procédé, objets de l'invention, seront mieux compris à la lecture de la description et à l'observation des dessins ci-après dans lesquels, outre les figures 1A à 1 C relatives à l'art antérieur :
- la figure 2A illustre les étapes d'un procédé de codage 100 selon un premier mode de réalisation de la présente invention ;
- la figure 2B illustre les étapes d'un procédé de codage 100' selon un autre mode de réalisation de la présente invention adapté au marquage transactionnel ;
- la figure 2C illustre les étapes d'un procédé de codage 100" selon un autre mode de réalisation de la présente invention également adapté au marquage transactionnel ;
- la figure 2D illustre une étape du treillis de codage utilisé par le procédé de codage selon la présente invention ; - la figure 2E illustre l'encodage d'une séquence de symboles d'entrée au moyen du treillis de codage utilisé par le procédé de codage selon la présente invention ;
- la figure 3A illustre les étapes d'un procédé de décodage 200 selon la présente invention ;
- la figure 3B illustre une étape du treillis de décodage utilisé par le procédé de décodage selon la présente invention ;
- la figure 3C illustre le décodage d'une séquence d'ensembles marqués de données au moyen du treillis de décodage utilisé par le procédé de codage selon la présente invention ; et
- la figure 4 illustre un système de transmission 300 comprenant des dispositifs de codage et de décodage aptes à mettre en œuvre les procédés de codage et de décodage selon la présente invention.
On se réfère tout d'abord à la figure 2A sur laquelle sont illustrées les étapes d'un procédé 100 de codage selon un premier mode de réalisation de la présente invention.
Dans ce procédé 100, le codage va se dérouler en fonction d'une séquence Id de symboles d'entrée, composée de k symboles d'entrée successifs ld(1 ), Id(k).
Une telle séquence de symboles d'entrée peut être, par exemple, un identifiant attribué à un client souhaitant télécharger un film dans un système de vidéo à la demande. Les symboles peuvent être sous forme binaire, c'est-à-dire des bits 0 ou 1 , auquel cas une telle séquence Id est un identifiant de type 01 101001 ...
Pour chaque symbole d'entrée ld(i) considéré, une transition sera faite dans un treillis de codage, lequel présente un nombre e d'états possibles, d'un premier état vers un deuxième état en fonction de ce symbole ld(i). Par définition et commodité, l'état de départ E(0) est égal à 0.
Si la séquence de symboles d'entrée Id est composée de k symboles ld(i). le procédé consiste à obtenir, lors d'une étape 1 10 d'obtention appliquée pour chaque symbole d'entrée ld(i) associé une valeur i allant de 1 à k, au moins un ensemble marqué de données C(i) comprenant un nombre p d'occurrences d'un symbole de marquage M(i), choisi parmi n symboles de marquage possibles, c'est-à-dire dans un ensemble de symboles de marquage {Mi , M n }.
Le fait d'insérer un nombre p, supérieur ou égal à deux, d'occurrences d'un symbole de marquage M(i) dans chaque ensemble marqué de données C(i) va renforcer le code par rapport à une erreur d'effacement en permettant une détection plus facile de celle-ci, comme démontré plus loin.
Cette étape d'obtention 1 10 d'au moins un ensemble de données C(i) pour chaque symbole d'entrée ld(i) est ainsi répétée pour chaque valeur de i allant de 1 à k, comme illustrée par la boucle récursive comprenant l'étape de vérification 130 de la valeur de i et l'étape d'incrémentation 140 de cette valeur i si celle-ci n'a pas encore atteint la valeur k, c'est-à-dire s'il reste des symboles d'entrée ld(i) à coder.
Une séquence d'ensemble de données marquées CT est obtenue au final par concaténation des ensembles de données marqués C(i) sélectionnés au cours des itérations successives de l'étape d'obtention 1 10.
Dans un mode de réalisation, cette concaténation peut être progressive, par exemple au moyen d'une étape 120 d'ajout progressif, pour chaque identifiant ld(i) donné, de l'ensemble de données marqués C(i) obtenu à l'étape 1 10 aux ensembles précédemment sélectionnés C(1 ), C(i-1 ).
Avec ce mode de réalisation, on obtient pour chaque symbole d'entrée ld(i) une séquence intermédiaire C T (i) correspondant à la concaténation des ensembles C(1 ) à C(i) obtenus lors des étapes 1 10 afférentes aux symboles ld(1 ) à ld(i). La séquence finale CT est obtenue à la fin de la dernière occurrence de la boucle récursive pour le dernier symbole d'entrée ld(k).
Dans un autre mode de réalisation, la concaténation peut être réalisée une fois tous les ensembles de données marqués C(i) obtenus, lors d'une seule étape globale 120' de concaténation de tous les ensembles de données marqués C(i) obtenus lors des différentes itérations de l'étape 1 10 pour les symboles d'entrée ld(1 ), Id(k). Ce mode de réalisation nécessite donc la mémorisation de tous les ensembles de données marqués C(i) jusqu'à l'étape 120' de concaténation.
L'étape d'obtention 1 10 de l'ensemble marqué de données C(i) peut être décomposée en une première sous-étape 1 1 1 de sélection d'un symbole de marquage M(i) dans l'ensemble {M-i , M n } suivie d'une deuxième sous-étape 1 13 d'obtention d'un ensemble de données C(i) comprenant un certain nombre p d'occurrences du symbole de marquage M(i) sélectionné.
Dans un mode de réalisation, l'étape 1 13 d'obtention de l'ensemble de données C(i) peut consister en une étape de marquage à la volée d'un ensemble de données non marqué au moyen du symbole de marquage M(i) sélectionné avec une période L/p où L est la longueur temporelle de l'ensemble de données non marqué et p est le nombre d'occurrences à insérer.
Ce mode de réalisation, tout en apportant une certaine flexibilité, impose d'effectuer ce marquage durant la boucle récursive du procédé de la figure 2A, ce qui peut engendrer une augmentation du temps de calcul de la séquence C T .
Un autre mode de réalisation de la présente invention, illustré à la figure 2B, permet d'optimiser le temps de calcul du marquage en ce sens qu'une étape préliminaire 105 de préparation des ensembles de données marquées est incluse avant les étapes illustrées à la figure 2A, sur la base de ce qui est décrit à la figure 1A.
Cette étape préliminaire 105 comprend une étape de génération 105i consistant à générer, à partir d'un ensemble de données initial C, un nombre n de versions Ci . .... C n de cet ensemble initial correspondant respectivement à chacun des symboles de marquage possibles M-i , M n . Pour chaque symbole de marquage possible M,, cette opération est réalisée en insérant un nombre p d'occurrences du symbole de marquage M, dans l'ensemble initial.
Dans un mode de réalisation particulier, les n versions Ci , C n de l ' ensemble initial C peuvent être compressées lors d'une étape de compression 105 2 . Ce mode de réalisation est particulièrement adapté au contexte du tatouage transactionnel par bloc dans la mesure où l'étape de compression, nécessitant un temps de calcul significatif, étant déjà effectuée préliminairement, les étapes 1 10 à 140 peuvent se dérouler sans compression et la séquence CT peut être générée suffisamment rapidement pour une transaction, par exemple du type vidéo à la demande.
Par ailleurs, lorsque les ensembles de données marqués C, ont déjà été préparés lors d'une étape de marquage préliminaire 105, dans le cadre d'un tatouage par bloc par exemple, l'étape d'obtention 1 10 de l'ensemble de données marqué C(i) peut consister en une étape de sélection 1 13' directement effectuée au niveau des ensembles de données C, en fonction du symbole d'entrée ld(i) sans passer par une étape préalable 1 1 1 ' de sélection d'un symbole de marquage M(i).
Il est cependant également possible de passer par une telle étape préalable 1 1 1 ' de sélection d'un symbole de marquage (i), pour chaque symbole d'entrée ld(i), auquel cas l'étape de sélection 1 13' de l'ensemble de données marqué C(i) consiste alors à sélectionner un ensemble marqué parmi les ensembles marqués préparés Ci, ..., C n en fonction du symbole de marquage M(î) sélectionné, par exemple au moyen d'une table de correspondance.
Les autres étapes 120, 120', 130 et 140 du procédé illustré à la figure 2B sont similaires aux étapes du procédé illustré à la figure 2A.
Que ce soit dans le mode de réalisation de la figure 2A ou de dans celui de la figure 2B, l'étape 1 1 1 de sélection du symbole de marquage M(i) se déroule en fonction du symbole d'entrée ld(i) et les ensembles marqués C(i) de données sont directement sélectionnés lors des étapes 1 10 successives.
Une autre mode de réalisation du procédé de codage est illustré à la figure 2C, dans lequel seule l'étape 1 1 1 de sélection des symboles de marquages M(i) a lieu, pour chaque symbole d'entrée ld(i), et dans lequel une étape d'obtention globale 120" de la séquence Cj a lieu une fois tous les symboles de marquage M(i) sélectionnés. De préférence, le procédé 100" de la figure 2C comporte également une étape de préparation des ensembles marqués C(i) afin que l'étape d'obtention globale 120" consiste en une simple et rapide manipulation de fichiers, ce qui est particulièrement avantageux dans le cadre du tatouage transactionnel par blocs.
Dans la présente invention, le treillis de codage est organisé de sorte à ce qu'il n'y ait pas de transition possible entre un état de codage E(i-1 ) et le même état de codage E(i). Autrement dit, l'état de codage E(i), à un instant i, doit être différent de l'état de codage E(i-1 ) à un instant i-1 précédent.
Une telle opération permet de réserver la transition entre états identiques à la détection de la répétition des symboles de marquage, lorsque l'on utilise un treillis de décodage correspondant à ce treillis de codage, et donc de ne pas être influencé en décodage par la répétition des symboles de marquage.
Pour ce faire, un treillis de codage basé sur la formule générale suivante peut être utilisé :
(1 ) E(i) = n r * E(i-1 ) + b modulo e où n r est le nombre de symboles possibles pour chaque symbole d'entrée, b est le symbole d'entrée considéré et e est un nombre pair d'états possibles dans le treillis de codage. On impose, par convention, de commencer le codage par l'état 0, c'est-à-dire E(0) = 0.
Avec une telle formule (1 ), il est apparent que si E(i-1 ) vaut zéro et le symbole d'entrée b reçu vaut également zéro, on retrouvera un état E(i) égal à zéro. Pour éviter cela, la condition suivante est imposée :
(2) E(i) = n, si E(i-1 ) = 0 et b = 0.
De même, avec la formule (1 ), il est apparent que si E(i-1 ) vaut e-1 et que b vaut e-1 +nr, E(i) vaudra également e-1 . Pour éviter cela, une autre condition suivante est imposée ;
(3) E(i) = 0 si E(i-1 ) = e-1 et b = e-1 +nr modulo e Ainsi, avec la formule (1 ) agrémentée des conditions (2) et (3), il est possible d'obtenir un treillis de codage où l'état de codage change nécessairement entre chaque transition.
Une représentation par treillis de codage telle qu'illustrée à la figure 2D permet de mieux comprendre l'invention et en particulier la façon dont se déroule la sélection des symboles de marquage M(i).
Sur cette figure 2D est en effet illustrée une étape dans un treillis de codage selon la présente invention, dans le cas où il y a huit états de codage possible (e = 8) et où les symboles d'entrée sont de forme binaire, i.e. où les symboles d'entrée sont des bits prenant la valeur 0 ou 1 . Cette étape illustre toutes les transitions d'état de codage possibles entre un instant i-1 et un instant i, c'est-à-dire toutes les transitions d'un état de codage E(i-1 ) à un état de codage E(i).
Dans ce contexte particulier, la formule (1 ) devient la formule (4) suivante : (4) E(i) = 2 * E(i-1 ) + b modulo 8 où b est la valeur d'un bit d'entrée considéré à l'instant i.
Ainsi, en partant d'un état de codage E(i-1 ) = 1 , la transition se fera vers un état E(i) = 2 si le bit d'entrée vaut 0, ou E(i) = 3 si le bit d'entrée vaut 1 ,
Similairement, en partant d'un état de codage E(i-1 ) = 2, la transition se fera vers un état E(i) = 4 si le bit d'entrée vaut 0, ou E(i) = 5 si le bit d'entrée vaut 1 .
Enfin, par exemple, en partant d'un état de codage E(i-1 ) = 4, la transition se fera vers un état E(i) = 8 modulo 8, soit 0 si le bit d'entrée vaut 0, ou E(i) = 9 modulo 8, soit 1 si le bit d'entrée vaut 1 .
Comme vu précédemment, afin de s'assurer que le treillis de codage soit construit de sorte à ce qu ' il ne soit pas possible d'avoir une transition vers un même état, la formule (4) est complétée par les deux conditions (5) et (6) suivantes : (5) E(i) = 2 si E(i-1 ) = 0 et b = 0.
(6) E(î) = 0 si E(i-1 ) = 7 et b = 1 .
En effet, la condition (5) permet d'éviter une transition d'un état E(i-1 )=0 vers un état suivant E(i)=0 avec la formule (4), dans le cas où un bit d'entrée 0 serait à coder,
Similairement, la condition (6) permet d'éviter une transition d'un état E(i- 1 )=7 vers un état suivant E(i)=7 avec la formule (4), dans le cas où un bit d'entrée 1 serait à coder.
Chaque transition dans le treillis est associée à un symbole de marquage M,, choisi dans l'ensemble {IV , M n } en fonction du symbole d'entrée b et de l'état de départ E(i-1 ) de la transition. Ce choix du symbole M, à associer à chaque transition peut être fait de façon pseudo-aléatoire. On peut par exemple utiliser une fonction déterministe prenant en entrée un symbole b, un état E(i-1 ) et un symbole MM et rendant en sortie un symbole M, sans lien apparent avec les données d'entrée.
De façon avantageuse, l'association de la transition à un symbole de marquage Mj est faite en fonction du symbole MM associé à la transition précédente permettant d'arriver à l'état de départ E(i-1 ).
En particulier, pour chaque transition partant d'un état E(i-1 ), le symbole M, associé à une telle transition doit être différent du symbole MM associé à la transition précédente amenant à cet état E(i-1 ), de façon à ce qu'il n'y ait jamais deux fois le même symbole M, choisi consécutivement.
Ce choix spécifique permet de réserver la répétition de symboles à la seule redondance d'insertion du symbole de marquage dans un ensemble de données marqué C(i), ce qui permet de mieux déterminer la nature de l'erreur lorsque celle-ci est détectée.
La figure 2E illustre le codage d'une séquence Id de données d'entrée avec le treillis de codage dont une étape est illustrée sur la figure 2D. Sur cette figure 2E, la séquence de données d'entrée Id est de forme binaire et vaut 01 101 1 10. Cette séquence va être encodée en une séquence de symboles de marquages M(i) choisis entre les quatre symboles A,B,C et D. Par convention, on impose A comme premier symbole.
Dans ce treillis, la transition 0→2 est associée au symbole « D », la transition 2→4 est associée au symbole « B » , la transition 4→1 est associée au symbole « C », la transition 1→ 2 est associée au symbole « D » la transition 2→5 est associée au symbole « A », la transition 5→ 3 est associée au symbole « B », la transition 3→7 est associée au symbole « A » et la transition 7→6 est associée au symbole « C ».
En appliquant les formules (4), (5) et (6) décrites ci-avant, on obtient à partir de la séquence d'entrée binaire 01 101 1 10 la suite de symboles de marquage M(i) suivante : A, D, B, C, D, A, B, A, C. Le temps d'encodage est extrêmement rapide, car il suffit de suivre un chemin et non de parcourir exhaustivement le treillis.
Dans le contexte du tatouage par bloc, on construit alors un fichier de données marqué Cj en ajoutant, pour chaque symbole de marquage sélectionné, un ensemble marqué de données comprenant un nombre p d'occurrences du symbole de marquage.
Ainsi, dans l'exemple précédent, on associe respectivement à chacun des quatre symboles de marquage A, B, C et D possibles un ensemble de données marquées CA, C B , Ce et CD comprenant deux occurrences du symbole de marquage (i.e. p = 2).
Le fichier de données marqué C T , obtenu à partir de la suite de symboles de marquage ADBCDABAC, sera alors C T = C A CDCBCCCDCACBC A CC et contiendra la séquence (7) suivante d'occurrences de symboles de marquage :
(7) AADDBBCCDDAABBAACC
Chacun des ensembles marqués de données C(i) sélectionné peut consister en un sous-ensemble d ' un ensemble marqué de données, ce qui est particulièrement applicable au cas du marquage transactionnel. En effet, dans le cas où la séquence CT d'ensembles à obtenir doit correspondre à un fichier vidéo compressé à marquer avec une séquence de k symboles d'entrée, il est possible d'obtenir une telle séquence CT par agrégation de k ensembles marqués de données C(i) successifs correspondants chacun à une des parties d'un fichier compressé et marqué par l'un des symboles de marquage, prise dans l'ordre permettant de restituer le film dans son entier.
Il est important de noter que chaque bloc C, contient plusieurs fois la marque M(i) sélectionné. Par exemple, avec une taille de bloc d'une longueur temporelle L de 8 secondes, il convient d'insérer un symbole de marquage M(i) avec une période inférieure ou égale à LJ2, c'est-à-dire dans l'exemple présent toutes les 4 secondes au maximum. Dans le cas contraire, un ré- échantillonnage temporel suffirait à détériorer fortement la marque. La séquence (7) obtenue est donc une version « allongée » de la suite de symboles de marquage sélectionnés.
Une telle séquence (7) est résistante à une erreur de d'effacement, contrairement aux codes correcteurs d'erreur classiques. En effet, si le quatrième symbole est effacé lors de la transmission de l'ensemble C T , la séquence (8) suivante sera reçue :
(8) AADBBCCDDAABBAACC
Tous les symboles de marquage étant censés être dupliqués, le fait de ne recevoir qu'un seul symbole « D » alors que les symboles avant et après celui- ci sont en double est indicatif d'une erreur d'effacement.
Il est apparent, au travers de cet exemple, que plus le nombre p d'occurrences est élevé, plus la séquence de symboles de marquage est résistante aux erreurs d'effacement, au détriment de la complexité de calcul engendrée.
Ainsi, dans le cas précédent, pour une longueur L d'ensemble de données C(i) de 8 secondes par exemple, un symbole de marquage est inséré toutes les 4 secondes pour obtenir deux occurrences de marquage par ensemble de données C(i). Cependant, on peut aussi insérer un symbole de marquage toutes les 2 secondes, toutes les secondes, etc. afin d'obtenir respectivement quatre ou huit occurrences de marquage, selon la résistance du code recherchée.
On se réfère maintenant à la figure 3A sur laquelle sont illustrées les étapes d'un procédé 200 de décodage d'une séquence d'ensembles marqués de données afin d'obtenir une séquence de symboles d'entrée.
Dans ce procédé de décodage 200, une séquence CT composée de k ensembles marqués de données C(i) est reçue, chacun de ces de k ensembles marqués de données C(i) comprenant une pluralité p d'occurrences d'un symboles de marquage M(i). Une telle séquence peut donc avoir été générée au moyen du procédé de codage selon la présente invention.
Au sein de cette séquence CT, les symboles de marquage M(j) successifs vont être détectés lors d'une étape de détection 205, en utilisant une fonction de lecture de marque à partir d'un bloc de données. Une telle fonction de lecture prend en entrée un ensemble marqué de données C(i) et sort en sortie les symboles de marquage M(j) qui y sont détectés. Une telle fonction de lecture peut être ainsi considérée comme étant le pendant de la fonction de marquage illustrée sur la figure 1A.
S'ensuite une étape 210 de vérification utilisant un treillis de décodage, pendant laquelle on vérifie que le symbole de marquage M(j) détecté correspond bien à une transition partant d'un état E(j') dans le treillis de décodage.
Pour ce faire, le treillis de décodage utilisé correspond au treillis de codage utilisé lors de l'encodage de la séquence CT. Cependant, afin de tenir compte de l'introduction d'un nombre p de redondances de chaque symbole de marquage dans cette séquence CT, une transition est rajoutée pour chaque état initial de décodage E(j') vers un état suivant de décodage E(j'+1 ) identique à l ' état initial E(j'), cette transition dite « de répétition » étant associée à la répétition du symbole de marquage. Si la vérification 210 est positive, c'est-à-dire si pour un état de décodage E(j'-1 ), il existe une transition associée au symbole de marquage M(j) détecté, une étape de détection 220 d'une répétition a lieu afin de déterminer si la transition E(j'-1 )→E(j') correspond à une répétition du symbole de marquage. Si tel est le cas, le symbole de marquage M(j) détecté est ignoré, puisqu'il ne correspond qu'à la répétition artificiellement ajoutée lors du codage, et l'on passe au symbole de marquage détecté M(j+1 ) suivant, au moyen de la boucle récursive indiquée par l'incrémentation 225 dans la figure 3A.
Si, par contre, l'étape de détection 220 révèle que la transition E(j'- 1 )→E(j') ne correspond pas à la répétition d'un symbole de marquage M(j) (i.e. que l'état de décodage E(j') est différent de l'état de décodage E(j'-1 ) précédent), alors on détermine le symbole d'entrée ld(i) associé à cette transition dans le treillis de décodage, lors d'une étape 230 et l'on passe au symbole de marquage détecté M(j+1 ) suivant, au moyen de la boucle récursive indiquée par l'incrémentation 225 dans la figure 3A.
D'autre part, si la vérification 210 s'avère négative, c'est-à-dire si pour un état de décodage E(j'-1 ), il n'existe pas de transition associée au symbole de marquage M(j) détecté, cela signifie qu'il y a une erreur dans la séquence des symboles de marquage détectés.
On va alors procéder à la vérification (étape 240) successive de chaque symbole de marquage détecté M(j'+1 ), M(j'+2), etc. suivants, vérification durant laquelle on vérifié si le symbole de marquage détecté correspond à une transition du treillis de décodage, de façon similaire à l'étape 210.
Cette vérification successive 240 est réalisée jusqu'à trouver un symbole de marquage M(j'+I) correspondant à une transition partant d'un certain état de décodage E(j'+I') et se fait au moyen d'une boucle récursive indiquée par l'incrémentation 235 dans la figure 3A.
Une fois cet état de décodage E(j'+I') trouvé, un processus de sélection 250 d'un certain chemin d'états de décodage E(j')→E(j'+1 )→, ..→E(j'+l') successifs dans le treillis de décodage est effectué, processus durant lequel les états de décodage successifs correspondant au meilleur chemin allant de l'état de décodage (E(j')) à l'état de décodage (E(j'+I')) sont déterminés.
Ce processus de sélection 250 consiste ainsi à retrouver la séquence d'états de décodage valide qui apparaît la plus probable par rapport à celle qui est observée et utilise le treillis de décodage particulier de la présente invention, par exemple en choisissant le chemin d'états de décodage minimisant le nombre d'erreur. Un tel processus de sélection 250 peut être basé, avantageusement, sur l'algorithme de Viterbi à cet effet.
L'algorithme de Viterbi est un algorithme de décodage qui s'appuie sur la programmation dynamique pour offrir un temps de décodage linéaire au lieu de faire une recherche exhaustive parmi toutes les séquences possibles. L'organisation du treillis en états permet d'élaguer l'arbre de recherche : à chaque itération et pour chaque état, seule la séquence la plus probable est conservée. L'utilisation de cet algorithme de Viterbi est donc particulièrement efficace, ici, en termes de temps de calcul.
Une fois le meilleur chemin d'états de décodage E(j')→E(j'+1 )→...→E(j'+P) déterminé à l'étape de sélection 250, on peut déterminer un certain nombre de symboles d'entrée ld(i) lors d'une étape de détermination 230, comme indiqué précédemment.
Toutes les étapes ci-avant sont reconduites jusqu'au dernier symbole de marquage M(j) détecté, comme indiqué par l'étape 260 de vérification de la fin du procédé de décodage, qui renvoie au symbole détecté M(j+1 ) suivant si le dernier symbole M(j) étudié n'est pas le dernier détecté.
Si. par contre, le dernier symbole détecté M(j) a été considéré, on obtient la séquence de symboles d'entrée Id en rassemblant tous les symboles d'entrée ld(i) successivement détectés. Ce rassemblement peut se faire une fois pour toutes à la fin, après avoir mémorisé chaque symbole d'entrée individuel ld(i) lors des étapes de détermination 230 successives, ou bien en mémorisant progressivement une séquence temporaire Id complétée lors de chacune des étapes de détermination 230 successives. Le treillis utilisé pour le procédé de décodage 200 se comprendra mieux à la lumière de la figure 3B, laquelle illustre une étape de treillis correspondant à l'étape de treillis du procédé de codage illustrée à la figure 2B.
Sur cette figure 3B, qui constitue un exemple non limitatif, il y a toujours huit états de codage possible (e = 8) et les symboles d'entrée à retrouver sont toujours de forme binaire, i.e. les symboles d'entrée à retrouver sont des bits prenant la valeur 0 ou 1 . Cette étape de treillis illustre toutes les transitions d'état de décodage possibles entre un instant j'-1 et un instant j', c'est-à-dire toutes les transitions d'un état de décodage E(j'-1 ) à un état de décodage E(j'),
On voit bien, par comparaison de cette figure 3B avec la figure 2B, que les transitions utilisées dans le treillis de codage de la figure 2B sont toutes reprises dans le treillis de décodage de la figure 3B.
Cependant, pour chaque état possible de E(j'-1 ), une nouvelle transition dite « de répétition » est ajoutée afin de tenir compte des occurrences des symboles de marquage volontairement introduites lors du codage de la séquence de symboles de marquage. Cette transition de répétition correspond à un arc horizontal, dans le treillis, reliant chacun des états possible E(j'-1 ) au même état E(j') à l'instant suivant.
L'ajout de cette transition de répétition permet de corriger une erreur de répétition. En effet, si un symbole de marquage est dupliqué, l'algorithme de décodage va alors suivre un arc horizontal et corriger cette erreur. Les décalages dans le décodage sont ainsi automatiquement compensés par l'ajout de ces arcs horizontaux dans le treillis.
La figure 3C illustre le décodage d'une séquence de symboles de marquage avec le treillis dont une étape est illustrée sur la figure 3B.
Dans cette figure 3C, la séquence AA DD BB CC DD AA BB AA CC obtenue dans l'exemple précédent grâce au codage de la séquence d'entrée 00101 1 10 est considérée.
Le décodage d'une telle séquence de symboles de marquage, quand celle-ci n'est pas altérée par une erreur, permet de retrouver la séquence d'entrée 00101 1 10, grâce par exemple à l'application de l'algorithme de Viterbi utilisant le treillis de décodage tel que défini ci-avant. Dans ce treillis, une transition horizontale ne donne pas de bit en sortie de décodage (et est indiqué par « r » dans la figure 3C).
Imaginons maintenant que la séquence de symbole de marquage est altérée par les trois erreurs suivantes avant d'être soumise au décodage :
- une erreur de substitution, au cours de laquelle le symbole A en deuxième position est changé pour un symbole B ;
- une erreur de répétition, au cours de laquelle le symbole B est rajouté en septième position ; et
- une erreur de suppression, au cours de laquelle le symbole A en douzième position est supprimé.
La séquence altérée se présente alors sous la forme suivante, où le soulignement indique la position des différentes erreurs :
AB DD BB BC CD DA_BB AA CC
Une telle séquence altérée ne peut pas être corrigée au moyen des codes correcteurs traditionnels.
Si l'on applique le procédé de la présente invention, au moyen du treillis décrit ci-avant, le procédé se déroule de la façon décrite ci-après.
Tout comme pour le procédé de codage, pour j' = 0, l'état de décodage E(0) vaut 0 et le premier symbole est A par convention. Pour ce premier état E(0). le treillis indique qu'il y a trois transitions possibles, respectivement associées au symbole D (correspondant au bit 1 ), au symbole C (correspondant au bit 0) et au symbole A (correspondant à une répétition sans bit).
Aucune des transitions proposées ne correspond aux deux premiers symboles reçus (AB) : il y a donc forcément une erreur dans la séquence.
À l'instant j' = 1 , il est possible d'examiner les transitions possibles depuis les états 0. 1 et 2 dans le treillis de décodage, grâce à l'algorithme de Viterbi. La transition de l'état 0 vers 2 est associée à D, ce qui correspond bien à au symbole reçu en troisième position. Les autres transitions sont associées à d'autres symboles et donnent donc une nouvelle erreur.
À ce stade, le chemin d'états 0→ 0→ 2 a une donc seule erreur, alors que tous les autres chemins d'états en ont deux. L'algorithme de Viterbi permet d'éliminer les chemins 0→1→2 et 0→2→2, car il y a un meilleur chemin qui mène à cet état 2. Comme seul le chemin d'états 0→0→2 est conservé et que la première transition 0→0 correspond à la répétition du symbole « A », le début de séquence altéré « ABD » est ainsi corrigé en un début de séquence correct « AAD ».
Dans les itérations suivantes, les chemins avec trop d'erreurs vont être élagués de façon similaire et le chemin commençant par 0→0→2 va être conservé, ce qui permet de corriger la première erreur de substitution.
Il apparaît par ailleurs, dans la figure 3C, que les altérations par répétition de symboles n'influent pas sur le bon déroulement de l'algorithme de décodage, grâce aux arcs horizontaux ajoutés dans le treillis de décodage. Par exemple, malgré la répétition du symbole « B » trois fois en cinquième, sixième et septième positions, l'utilisation de l'algorithme de Viterbi permet de retrouver le bon chemin dès l'apparition du symbole C en huitième position.
Il en va de même pour la suppression du symbole A, en douzième position, l'algorithme de Viterbi permettant alors de retrouver le bon chemin qui permet de déduire la séquence « AA » au lieu de la séquence altérée « AB » reçue.
Ainsi, à l'issue du décodage illustré à la figure 3C, le bon chemin est retrouvé et la séquence initiale de symboles d'entrée 00101 1 10 est décodée sans erreur.
La figure 4 illustre un système de transmission 300 utilisant les procédés de codage 100 et de décodage 200 précédemment décrits.
Dans ce système de transmission 300, une unité de transmission 310 comprend un dispositif de codage 320 connecté à une unité de transmission 330 qui va servir à retransmettre la séquence d'ensembles marqués de données sur un canal de transmission qui peut être filaire ou sans fil.
Le dispositif de codage 320 comprend des moyens adaptés pour mettre en œuvre le procédé de codage 100 ci-avant. En particulier, le dispositif de codage 320 peut comprendre un module de codage 321 adapté pour sélectionner une séquence de symboles de marquages M(i) en fonction des symboles d'entrée ld(i) et un module de sélection 323 des ensembles marqués C(i) de données, en fonction de la séquence de symboles de marquages M(i) sélectionnés, pour obtenir une séquence Cj d'ensembles marqués de données.
Le module de sélection 323 peut être connecté à un module de mémorisation 325 servant à mémoriser les différents ensembles marqués C(i) de données possibles, lesquels peuvent être obtenus à partir d'un unique fichier F reçu par un module de préparation 327, lequel va fournir n versions du fichier F marquées par un symbole différent de marquage. Un module de compression 329 peut également être connecté entre le module de préparation 327 et le module de mémorisation 325, afin de compresser les n version marquées du fichier F avant de les mémoriser, ce qui est particulièrement adapté au marquage transactionnel par bloc.
Une fois la séquence CT d'ensembles marqués de données transmises, elle peut être récupérée ultérieurement par une unité de réception 340 qui comprend un module de réception 350, adaptée au canal de transmission utilisé par l'unité de transmission 330, ainsi qu'un dispositif de décodage 360 apte à mettre en œuvre le procédé de décodage 200 ci-avant.
En particulier, le dispositif de décodage 360 peut comprendre un module de détection 361 adapté pour détecter, dans la séquence C T d'ensembles marqués de données reçues, les symboles de marquages M(j) successifs. Ce module de détection 361 envoie les symboles de marquages détectés M(j) vers un module de décodage 363 qui va retrouver, à partir de ces symboles M(j) et du treillis de décodage décrit précédemment, la séquence Id de symbole de données, correspondant par exemple à l ' identifiant d'un client ayant commandé et reçu la séquence C r. Par ailleurs, l'invention vise aussi un programme, susceptible d'être exécuté par un ordinateur ou par un processeur de données, ce programme comportant des instructions pour commander l'exécution des étapes d'un procédé tel que mentionné ci-dessus.
Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme d'un code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable.
L'invention vise aussi un support d'informations lisible par un ordinateur ou processeur de données, et comportant des instructions d'un programme tel que mentionné ci-dessus.
Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD-ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette ou un disque dur.
D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet.
Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question
Comme déjà indiqué, la présente invention trouve avantageusement une application au tatouage transactionnel par bloc, c'est-à-dire au tatouage par bloc lors d'une transaction avec un client auquel est associé un identifiant sous forme d'une séquence de symboles. Cette séquence de symboles (par exemple binaire) identifiant le client est alors utilisée en tant que séquence de symboles d'entrée de la façon décrite précédemment pour tatouer le fichier faisant l'objet de la transaction. Une fois ce fichier tatoué de la sorte, il est possible de retrouver ultérieurement, grâce à un procédé de décodage tel que décrit aux figures 3A-3C, la séquence identifiant le client et donc l'identité de ce client.
La présente invention trouve donc, par exemple, une application intéressante, sans toutefois s'y limiter, au marquage de films dans le cadre d'une plateforme de distribution de vidéo, en vue de tracer des fuites. Si un client redistribue illégalement le film qu'il a loué, par exemple en le mettant à disposition sur un réseau pair-à-pair, son identité peut être retrouvée grâce au marquage inséré selon la présente invention dans le fichier. Un tel marquage, outre son effet technique premier, présente aussi un effet dissuasif important.
Bien entendu, l'invention n'est pas limitée aux exemples de réalisation ci- dessus décrits et représentés, à partir desquels on pourra prévoir d'autres modes et d'autres formes de réalisation, sans pour autant sortir du cadre de l'invention.
Ainsi, plus généralement, les procédés de codage et de décodage présentés peuvent s'appliquer à la correction d'erreur de tous types de fichiers transmis dans des canaux de transmission présentant les mêmes caractéristiques que les séquences du tatouage par bloc, c'est-à-dire présentant des erreurs combinées de substitution, de duplication et d'effacement de symboles.
De plus, les ensemble de données C(i) utilisés dans les procédés de la présente invention peuvent être des fichiers entiers ou des parties de fichiers, par exemple d'images, de son ou de vidéos. Le fait d'insérer des symboles de marquage dans de tels fichiers génère un certain bruit, aussi la présente invention sera spécialement adapté aux fichiers de large taille et/ou s'appliquant à des contextes où le bruit a moins d'importance, comme les fichiers compressés de vidéo, par exemple au format MPEG, ou les fichiers compressés de musique, par exemple aux formats MP3 et AAC.