Brevet FR2859850A1 — publié le 20050318

L'invention concerne un procédé de transmission d'information. II s'applique notamment dans tous les cas où les moments de transmission effectifs ne sont pas explicitement contrôlés. Cela comprend par exemple les cas suivants: É Le récepteur utilise une information en boucle, le récepteur pouvant commencer son écoute à n'importe quel instant avec un canal supposé suffisamment brouillé pour que la simple émission en boucle de l'information ne soit pas une stratégie efficace. Ce système est notamment adapté aux cas où il existe des trous dans l'émission (évanouissement ou fading en termes anglo-saxon, code détecteur d'erreur). É Une même information est, ou peut être diffusée par plusieurs émetteurs, et toutes les informations émises doivent pouvoir être utilisées. Il est connu de l'art antérieur de transmettre les informations en utilisant des codes correcteurs d'erreurs linéaires. Dans ce cas, un mot de taille fixe est transformé en un autre mot de taille fixe. Les codes utilisés sont par exemple des codes convolutifs variant dans le temps, éventuellement avec entrelacement. Cependant, même ces codes ne considèrent que des variations locales des combinaisons linéaires et n'englobent pas la dépendance potentielle de toutes les entrées. De plus, le processus de décodage se base sur un algorithme général de résolution de système linéaire et non sur un processus spécifique. Dans le cas où l'information à transmettre est un message donné à émettre, une autre stratégie consiste à ré-émettre continuellement le message. Cette stratégie peut être efficace si le taux d'erreur est faible, et si une seule source d'émission est présente à un instant. Dans ce cas, le temps moyen pour obtenir l'ensemble des données peut se rapprocher de la taille des données. Par contre, dès que la probabilité d'erreur augmente, le temps d'écoute nécessaire peut augmenter notablement. L'invention concerne notamment un procédé pour transmettre de l'information, l'information contenant n cellules porteuses de l'information, avec n supérieur ou égal à 2. II est caractérisé en ce qu'il comporte au moins les étapes suivantes: a) générer un masque {Mi} i=1,n de n cellules correspondant aux n cellules porteuses d'information, b) effectuer une combinaison linéaire d'au moins toutes les n cellules 10 avec les n cellules du masque généré pour obtenir un mot résultant, c) réaliser une opération linéaire des n cellules du mot résultant pour obtenir une cellule BT,i à transmettre. Le procédé peut comporter les étapes suivantes: d) pour chaque cellule BT, 1 reçue déterminer le masque {Mi)i=1,n 15 correspondant, e) inverser le système linéaire formé des p cellules reçues. Une cellule est par exemple un bit ou un symbole. Le procédé peut comporter une étape préalable où les paquets de l'information à transmettre sont décomposés en plusieurs sous-paquets. Le procédé offre notamment les avantages suivants: É Il diminue le temps de reconstitution des données au niveau du récepteur. Selon différentes hypothèses sur le système, il est par exemple possible de gagner un temps de l'ordre de K log(N) , où N est le nombre de bits de la donnée à transmettre et où K est typiquement compris entre 1 et 2. É Ce système permet d'utiliser plusieurs émetteurs. É Dans le cas d'une émission en boucle, le récepteur peut se mettre en écoute aux moments où il le désire. D'autres caractéristiques et avantages de l'invention apparaîtront mieux à la lecture d'un exemple de réalisation donné à titre d'exemple non limitatif, illustré de la figure 1 unique qui représente un système permettant l'échange d'information entre un émetteur et un récepteur. De manière à mieux faire comprendre le principe mis en oeuvre par l'invention, l'exemple donné ci-après concerne un procédé pour la transmission d'information entre un émetteur et un récepteur. L'information à transmettre se présente sous la forme de bits porteurs de l'information et le procédé suppose que l'émetteur et le récepteur partagent une information commune d'indexation des données émises, telle que le temps, le numéro de trame, etc. Cette information commune référence le bit. Sans sortir du cadre de l'invention, le système peut comporter plusieurs émetteurs. Le procédé suppose, a priori, que le récepteur ne peut communiquer en retour avec l'émetteur pour lui indiquer les paquets qu'il a reçus. Cela peut être le cas lors de la diffusion à un grand nombre de récepteurs. Dans la description qui suit, on utilise le terme bit et les opérations logique ET et XOR. Les principes s'appliquent toutefois à toute cellule élémentaire porteuse d'information et avec toute forme de loi linéaire. La figure 1 schématise un exemple de système de transmission d'information selon l'invention comportant par exemple: É un émetteur 1 comprenant un premier bloc 2 correspondant aux données à transmettre, un dispositif 3 selon l'invention adapté à la génération de masques, à la fabrication des combinaisons linéaires, ce bloc 3 a accès aux informations partagées, un codeur de canal 4 quelconque adapté au canal effectif, É un récepteur 5 comprenant un décodeur de canal 6, un dispositif 7 d'analyse des données reçues, ce dispositif ayant accès à l'information partagée et une partie 8 adaptée à effectuer une analyse linéaire selon les étapes du procédé. Le procédé selon l'invention comporte au moins les étapes décrites ciaprès: Au niveau de l'émetteur A partir de l'information commune référençant les bits émis, pour chaque bit 5 bi émis, le procédé effectue plusieurs combinaisons linéaires des données à transmettre, de la manière suivante a) Par exemple, pour une information commune constituée d'un numéro T de trame et d'un numéro de bit j, et pour des données à transmettre se présentant sous la forme de nbits {Di}i=1,n, le procédé définit une loi désignée Deriv permettant, à partir de l'information commune ici le numéro de trame, de dériver un masque M de n bits: {Mi}i=1,n = Deriv(T,j) (1) b) Effectuer une combinaison linéaire en opérant une fonction logique, par exemple la fonction ET , ceci bit à bit entre un bit j des données à transmettre et le bit correspondant Mj du masque généré. Cette opération est réalisée n fois, ce qui permet d'obtenir un mot résultant comportant n bits. Effectuer un XOR de tous les bits du mot résultant afin d'obtenir un bit BT BT, i = O+ (D; A M; ) =1,n Les bits de données à transmettre peuvent être bufférisées pour réaliser l'étape b). Au niveau du récepteur Le procédé reconstitue l'information après avoir obtenu un nombre p suffisant de bits d'information. Le nombre p de bits est par exemple au moins égal au nombre n de bits de l'information transmise. c) Pour chaque bit BT,i reçu, le procédé calcule le masque correspondant {Mi}i=1,n selon la relation (1). Le bit reçu BT,1 et le masque 30 correspondant Mj, forment une équation linéaire. Après avoir reçu p bits, le système linéaire ainsi constitué (bit reçu BTJ avec j variant de 1 (2) à p, et les p masques correspondants) est inversible avec une probabilité élevée, lorsque le nombre p de bits reçus est supérieur ou égal au nombre n de bits à émettre. d) Inverser le système linéaire pour retrouver les bits émis. Selon une variante de réalisation, lorsque l'information à transmettre est constituée de paquets ayant des tailles importantes, le procédé comporte une étape préalable où les paquets sont découpés en sous-paquets selon des méthodes connues de l'Homme du métier. Par exemple, une taille de paquet de 64 bits permet de conserver des 1 o performances intéressantes, tout en limitant la complexité de résolution des systèmes linéaires. L'information commune est alors également utilisée pour déterminer le bloc de données à considérer. II est aussi possible d'utiliser des contrôles de CRC pour des paquets de taille importante. L'exemple chiffré donné pour un système à un émetteur qui suit permet d'illustrer le procédé selon l'invention: On considère par exemple un système composé d'un émetteur, devant transmettre une information D de taille connue, avec une référence temporelle commune (T,D, référençant chaque bit à émettre. L'émetteur possède un identifiant No. L'information D est découpée en N blocs de 64 bits. L'algorithme de chiffrement DES ([DES]) est utilisé. La clé choisie est l'identifiant No. Pour chaque bit j à transmettre, l'émetteur calcule le chiffré de l'information temporelle (T,j) indiçant le bit: M = DESNo((T,j) ). Ce calcul fournit 64 bits en sortie. L'émetteur opère alors le produit scalaire entre M et les données du bloc (T %N). Le bit émis est le bit résultat de ce produit scalaire. Le récepteur opère également le calcul: DESNo((T,j)), ainsi que le calcul du modulo (T %N). II dispose ainsi des paramètres de la combinaison et du résultat. Ces données alimentent un ensemble de résolution de systèmes linéaires. Après un nombre d'observations suffisant, ces systèmes permettent de retrouver l'information à transmettre. L'algorithme de chiffrement [DES] NBS FIPS PUB 46 est décrit 5 par exemple dans le document intitulé Data Encryption Standard National Bureau of Standards, U. S. Department of Commerce, Jan. 1977 Sans sortir du cadre de l'invention, le système selon l'invention comporte plusieurs émetteurs. Les lois et les étapes mises en oeuvre sont identiques à celles décrites dans le cadre d'un émetteur, l'identifiant No différenciant les émetteurs. Dans ce cas, si le récepteur peut physiquement obtenir simultanément des données provenant de plusieurs émetteurs, la transmission est accélérée d'autant. En effet, les combinaisons linéaires dépendant du numéro d'émetteur sont différentes d'un émetteur à l'autre, et donc les équations linéaires obtenus peuvent être exploitées indépendamment. REVENDICATIONS 1 Procédé pour transmettre de l'information, l'information contenant n cellules porteuses de l'information, avec n supérieur ou égal à 2 caractérisé en ce qu'il comporte au moins les étapes suivantes: a) générer un masque {Mi}i=1,n de n cellules correspondant aux n cellules porteuses d'information, b) effectuer une combinaison linéaire d'au moins toutes les n cellules avec les n cellules du masque généré pour obtenir un mot résultant, c) réaliser une opération linéaire des n cellules du mot résultant pour obtenir une cellule BT.i à transmettre. 2 Procédé selon la revendication 1 caractérisé en ce qu'il comporte les étapes suivantes: d) pour chaque cellule BT,J reçue déterminer le masque {Mi}i.1,n correspondant, e) inverser le système linéaire formé des p cellules reçues. 3 Procédé selon l'une des revendications 1 ou 2 caractérisé en ce que l'on dérive un masque M de n bits à partir d'une information commune aux cellules émises et en utilisant une loi Deriv telle que {Mi}i=1,n = Deriv(T, j). 4 Procédé selon l'une des revendications 1 à 3 caractérisé en ce qu'une cellule est un bit. Procédé selon l'une des revendications 1 à 3 caractérisé en ce qu'une cellule est un symbole. 6 Procédé selon l'une des revendications 1 ou 2 caractérisé en ce que la combinaison linéaire est effectuée en opérant une fonction logique, telle que la fonction ET . 7 Procédé selon l'une des revendications 1 ou 2 caractérisé en ce que l'opération linéaire des n cellules du mot résultant est une opération XOR . 8 Procédé selon l'une des revendications 1 à 7 caractérisé en ce qu'il comporte une étape préalable où les paquets de l'information à transmettre sont décomposés en plusieurs sous-paquets. 9 Dispositif de transmission d'information caractérisé en ce qu'il comporte au moins: É un émetteur adapté à générer un masque {Mi};=1,n de n cellules correspondant aux n cellules porteuses d'information, effectuer une combinaison linéaire d'au moins toutes les n cellules avec les n cellules du masque généré pour obtenir un mot résultant, et réaliser une opération linéaire des n cellules du mot résultant pour obtenir une cellule BT,i à transmettre, É un récepteur adapté à déterminer le masque {Mi}i=1,n correspondant, pour chaque cellule BT,1 reçue et inverser le système linéaire formé des p cellules reçues.