Brevet FR2898000A1 — publié le 20070831

PROCEDE ET SYSTEME PERMETTANT DE GERER DES INTERRUPTIONS ERRATIQUES DANS UN SYSTEME DE TRANSMISSION L'invention concerne notamment un procédé et un système de gestion des interruptions lors de la réception d'un signal dans un système de transmission. L'un des problèmes posés dans les systèmes de transmission d'information est la manière de gérer les pertes d'information dues aux interruptions dans la communication, interruptions qui peuvent être erratiques. Suite à une émission ou à une réception erratique , un récepteur peut ne pas avoir accès à plusieurs paquets du message transmis et ne pas pouvoir émettre de requête en direction de l'émetteur pour demander les paquets manquants. Les pertes de paquets n'étant pas prédictibles, le message peut être transmis plusieurs fois pour éviter des pertes d'informations. Une méthode simple consiste, par exemple, à répéter le message. Le récepteur perdant plusieurs paquets doit écouter, éventuellement plusieurs fois, la totalité du message. Pour des messages longs et/ou dans le cas de faible largeur de bande passante, cette manière d'opérer peut devenir problématique. Dans tous les cas, elle conduit à une perte de temps importante. L'invention concerne un procédé pour gérer des interruptions erratiques dans un système de transmission où les messages à transmettre sont composés de paquets de données et s'expriment au moyen d'un polynôme de degré t-1, les émetteurs et les récepteurs partageant une information permettant de référencer les paquets de données caractérisé en ce qu'il comporte au moins les étapes suivantes : 2 • au cours de la transmission du message, générer au moins t points Ai et les évaluations P(Ai) du polynôme P pour les t points Ai, • transmettre les évaluations P(Ai) des t points vers le ou les récepteurs concernés, • vérifier que les t évaluations sont valables, • utiliser l'information référençant les paquets et les t évaluations valables du polynôme pour déterminer les points Ai correspondant au paquet de données référencé par I, • à partir des P(Ai) et des Ai déterminer le polynôme P utilisé, et à partir du polynôme en déduire le message. On peut utiliser une fonction d'interpolation pour déterminer le polynôme. Le message est, par exemple, divisé en plusieurs parties et on applique les étapes du procédé énoncé ci-dessus sur chaque partie. Lors de la détection d'erreur, les évaluations P(Ai) contenues dans une page erronées sont par exemple supprimées et le récepteur reste à l'écoute de nouvelles pages. On transmet par exemple la signalisation CO associée à un message C, la signalisation étant composée de TO*NO bits et vue comme un polynôme de degré (TO-1) et à la réception : • on collecte TO pages ne contenant pas d'erreurs, et chaque page utilisant un point différent des autres pages, on reconstitue à partir de ces pages la signalisation CO à partir de ces pages en utilisant une interpolation polynomiale, • on déduit à partir de CO, la longueur du message C et la manière dont on a découpé le message C en F trames, chaque trame découpée en q mots, chacun des mots étant représenté par un polynôme de degré (T-1), • pour chaque polynôme correspondant à un mot on collecte T évaluations sans erreurs du polynôme, et • en utilisant des points distincts, on reconstitue le message C en utilisant l'interpolation polynomiale. Les étapes du procédé s'appliquent dans un système de transmission comprend un satellite de communication. L'invention concerne aussi un système pour gérer des interruptions erratiques dans un système de transmission comprenant un ou plusieurs émetteurs Ej et un ou plusieurs récepteurs Rk, où les messages à transmettre sont composés de paquets de données et s'expriment au moyen d'un polynôme de degré t-1, les émetteurs et les récepteurs partageant une information permettant de référencer les paquets de données caractérisé en ce qu'il comporte au moins les éléments suivants : un centre de formatage et les récepteurs étant pourvus de moyens adaptés à exécuter les étapes du procédé énoncé. Le procédé selon l'invention présente notamment les avantages suivants : • Il offre une résistance aux interruptions éventuelles lors de la transmission d'informations, • Il permet d'augmenter la bande passante apparente en prenant en compte la diversité des émetteurs. D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description qui suit d'un exemple de réalisation donné à titre illustratif et nullement limitatif annexé des figures qui représentent : • La figure 1 un exemple d'architecture d'un système pour lequel s'applique l'invention, et • La figure 2 le multiplexage des informations concernant le message et de la signalisation lorsqu'elle existe. Afin de mieux faire comprendre le principe mis en oeuvre dans l'invention, la description est donnée à titre illustratif pour un système comprenant un ou plusieurs émetteurs Ej, un centre 1 de gestion ou de formatage des messages et un ou plusieurs récepteurs Ftk. Le centre de formatage 1 est équipé d'un processeur 2 adapté à exécuter les étapes du procédé selon l'invention détaillées ci-après et à générer des signaux. Les récepteurs sont aussi pourvus de moyens tels que des microprocesseurs (non représentés pour des raisons de simplification) adaptés à exécuter les calculs mis en oeuvre dans le procédé. Le centre de gestion 1 formate les messages dans des paquets de données appelés pages . Il transmet les paquets de données ou pages à un ou plusieurs émetteurs, les émetteurs transmettant ces derniers aux récepteurs. Dans le cadre de l'exemple, on fait l'hypothèse que les émetteurs et les récepteurs partagent une information appelée [page ref] , permettant ainsi de référencer chaque page. Cette information peut être, par exemple, une référence temporelle connue par chacun (émetteurs et récepteurs), ou un champ spécifique inclus dans la page comme un numéro de page. De manière générale, toute information permettant de référencer un paquet de données pourra être utilisée. De manière simplifiée, le procédé selon l'invention repose sur le principe suivant : un message M qui doit être transmis à un ou plusieurs récepteurs est décomposé par le centre de formatage en t symboles SO,S1,...,St-1• Chaque symbole s; est représenté par un élément dans un corps fini GF, c'est-à-dire dans un ensemble GF ayant un nombre fini d'éléments et muni de 2 opérations + (l'addition) et * (la multiplication). Pour des raisons de simplifications, on fait l'hypothèse que ce corps fini est GF(2n), c'est-à-dire le corps ayant 2n éléments (sans sortir du cadre de l'invention tout corps fini peut convenir). Ainsi les symboles sont composés de n bits et la taille du message M est de n*t bits. Le message M est représenté par le polynôme : P(X)=so + s1 X + s2 X2 + ...+ st_1Xt 1 à coefficients dans GF(2n). L'idée de la présente invention utilise notamment des évaluations du polynôme P en t points distincts A0, A1,...,At_1, c'est-à-dire P(Ao), P(A1), ..., P(At_1), pour déterminer les t coefficients so,s1,...,st_1.. du polynôme représentant le message. Ces évaluations P(Ai) sont des symboles de n bits dans GF(2n). Le centre de formatage va remplir les pages (ou paquets de message) avec des évaluations du polynôme P en plusieurs points Ai différents. Le nombre d'évaluations de polynôme P(Ai) est notamment choisi en fonction du degré du polynôme. Cette façon de procéder n'affecte pas le nombre total de bits (n*t) que le récepteur mémorise de façon à reconstituer l'ensemble du message M. Le centre de formatage 1 génère plusieurs points Ai à partir du paramètre [page ref] d'une page. Pendant la session entière de la transmission du message, (session entière qui correspond à la transmission du message d'un émetteur vers un récepteur) le centre de formatage génère des points qui sont différents pour chaque page (ou qui ont une grande probabilité d'être différents). En particulier, le centre génère plus de (n*t) points Ai et évaluations du polynôme P(Ai) pour les points Ai correspondants. Le nombre de points générés dépend de la longueur de la session. Le(s) émetteur(s) envoie(nt) les évaluations P(Ai) au(x) récepteur(s). Ainsi, un récepteur Ri a uniquement à mémoriser t différentes 30 évaluations P(Ai) pour être capable de reconstituer la totalité du message M, ceci, quels que soient les instants où il les reçoit (qu'il y ait des interruptions ou non dans la réception des pages). Le nombre minimum t qu'un récepteur doit mémoriser est fonction du degré du polynôme utilisé pour le message. L'indicateur [page ref] permet au récepteur de calculer les points Ai correspondant aux évaluations P(Ai) qu'il reçoit. Si le récepteur est capable d'écouter en parallèle plusieurs émetteurs, et que chacun d'eux envoie des évaluations différentes, alors le temps de réception nécessaire pour récupérer t évaluations correspond aux temps de réceptions s'il n'y avait qu'un seul récepteur, divisé par le nombre de récepteurs. Etapes de reconstitution du message Pour reconstituer le message, un récepteur doit avoir acquis au moins t évaluations d'un polynôme P valables correspondant à t points distincts Ao, A1,...,At_1 avec, zo= P(Ao), z1= P(A1), ..., zt_1= P(At_1), qui sont des éléments du corps fini GF. La validité des points est contrôlée, par exemple, en utilisant des méthodes connues de l'Homme du métier dont des exemples sont donnés ci-après. Connaissant les points et les évaluations correspondantes, il 20 utilise par exemple l'interpolation du polynôme de Lagrange Li(X) pour déterminer le polynôme P de la manière suivante : P(X)=zo * Lo(X) + z1 * L1(X) + ...+ zt-1 * Lt-1(X) où, pour 0 k 25 Concrètement, le polynôme Li(X) se calcule de la façon suivante : Li(X)=B(j)*(le produit de t-1 monômes (X-Ak), tel que 0 j) B(j) est l'élément de GF(2n) qui est l'inverse dans GF(2") du produit des t-1 elements (Ai ù Ak) pour 0 j. Connaissant le polynôme, un récepteur connaît alors le message. Les étapes de traitement décrites ci-dessus s'appliquent pour des messages suffisamment courts. Pour les longs messages, il est possible de découper ce message en parties ayant une longueur adéquate et d'appliquer le principe de base sur chacune des parties. La description détaillée d'un exemple de réalisation ci-dessous indique, entre autre, une manière pour choisir les différents paramètres pour avoir une longueur adéquate des parties du 1 o message. Par ailleurs, le récepteur doit être capable de détecter les erreurs éventuelles dues à une mauvaise transmission ou réception des pages. Un mécanisme de correction d'erreur n'est pas obligatoire, une simple détection d'erreur est suffisante. Les pages erronées seront simplement effacées par 15 le récepteur, et celui-ci devra rester à l'écoute de(s) émetteur(s) pour récupérer d'autres pages (n'importe lesquelles). La suite de la description donne un exemple appliqué à un message C transmis à un récepteur pendant une session, le récepteur n'ayant pas d'information prédéfinie sur le message C (longueur, nature, etc.) 20 II est alors nécessaire de transmettre aussi une signalisation CO contenant l'information utile au sujet de C. Le format de page est, par exemple, le suivant : [Page ref] [champ de Signalisation] [champ de message utile] [MAC / CRC]. Où 25 • [Page ref] indique le numéro de page qui identifie la page. Ce paramètre peut aussi être utilisé pour chiffrer la page en mode "compteur", • [Champ Signalisation] donne une information sur la signalisation CO, • [champ message utile] donne une information sur le message C, • [MAC / CRC] contient un MAC ( Message Authentication Code ) ou un CRC ( Cyclic Redundancy Check ) permettant de détecter les erreurs au niveau de la page. Il peut aussi être utilisé pour l'authentification. Une façon simple d'implémenter le principe de diversité comprend, 10 par exemple, les étapes suivantes : • la donnée utile d'une page est composée de N_p=NO+q*N bits, i.e, composé de NO bits pour le champ [Champ Signalisation] et q paquets de N bits pour le champ [champ message utile]. Les paramètres (NO , N, q) sont discutés après dans la description, 15 • la signalisation CO est composée par exemple de TO*NO bits et est vue comme un polynôme de degré (TO-1) dans GF(2N0). Le champ [champ signalisation] d'une page contient une évaluation du polynôme en un point, ce point étant calculé à partir de [page ref], • le message C est composé de F trames, chaque trame est composée de 20 q mots, chaque mot est composé de T*N bits et est vu comme un polynôme de degré (T-1) dans GF(2N). Le champ [champ signalisation] d'une page contient q paquets donnant une information sur une trame de C sélectionnée grâce au paramètre [Page ref]. Chacun de ces q paquets est une évaluation d'un polynôme en un point calculé à partir du 25 paramètre [Page ref], • pour une session donnée et un message donné C, le centre calcule les pages donnant l'information sur C comme il a été décrit précédemment. Un mode de transmission est, par exemple, obtenu lorsque le centre transmet des pages à plusieurs émetteurs et chaque érnetteur transmet au récepteur des pages qui sont différentes de celles transmises par les autres émetteurs. Une manière simple d'obtenir cette diversité de signaux est de forcer le centre à distribuer différentes pages à différents émetteurs. Le traitement de la page au niveau d'un récepteur comprend, par exemple, les étapes suivantes : • la taille NO*TO de la signalisation est prédéfinie et connue par le récepteur. Le récepteur collecte TO pages, telles que chaque page ne 10 contient aucune erreur (contrôle avec [MAC/CRC]) et chaque page utilise un point différent des autres pages (point calculable à partir de [page ref]). Le récepteur reconstitue la signalisation CO à partir de ces pages en utilisant l'interpolation polynomiale de Lagrange comme il est explicité ci-après, 15 • grâce à CO, le récepteur connaît la longueur du message C. Il collecte T pages de chaque trame de C (pages sans erreur et en utilisant des points distincts) . Ensuite il reconstitue le message C en utilisant l'interpolation polynomiale de Lagrange. La suite de la description détaille le choix de:s paramètres, la 20 signalisation CO, le multiplexage détaillé de C et CO dans les pages utilisant le principe de diversité, et une méthode pour le récepteur pour reconstituer la totalité du message à partir des pages. Choix des paramètres5 On note : • N_p le nombre de bits par page qui sont réservés exclusivement pour les données effectives, c'est-à-dire, pour les champs [Champ Signalisation] et [champ message utile], • N un nombre inférieur ou égal au nombre de bits de [Page ref], • NO et q sont des nombres tels que N_p=q*N +NO. De façon à avoir un paramètre d'efficacité proche de 1, les paramètres N et NO seront choisis par exemple pour vérifier : 2N/2 > Mot =T et 2N /2 > =T0 N N où COI est la taille de CO, et IMotl est la taille d'un mot contenu dans C. Ces deux conditions ne sont pas obligatoires mais assurent qu'il n'y a pas de collision entre les points sélectionnés de [Page ref], avec une probabilité élevée. La condition la plus importante est la première. La seconde peut être aisément assouplie (TO peut être un peu plus grand que 2N0'2) car la signalisation CO est la plupart du temps plus courte que le message C. Dans tous les cas il faut impérativement que 2NT et 2N0 TO pour assurer que le nombre de symboles du message est inférieur au nombre de total de points. Pour un nombre donné N_p, ces conditions règlent les paramètres N et NO, ainsi que les autres paramètres, i.e, TO si COI est fixé, IMotl et T. Format du message C et signalisation CO Le message C est divisé en une ou plusieurs trames de q*T*N bits. Pour assurer cette taille de format, le message C est par exemple formatté avec un champ "padding" de taille variable servant de bourrage. Un en-tête donnant la taille du "padding" peut être inclus dans le message C ou dans la signalisation CO. 10 Signalisation CO La longueur COI de CO est un multiple de NO. On note TO le nombre de parties de NO bits dans CO, i.e. tel que ICOI=TO*NO. Ce message peut contenir, par exemple, l'information suivante : Champs CO Description [Type de message] Code plusieurs types prédéfinis de message [Longueur de C] Code la longueur du message C (voir ci-dessous) [Information Indique la date (ou l'heure) de début et de fin de la Temporelle sur C] session pendant laquelle le message C est émis [Padding] Bourrage (éventuel) permettant d'avoir une taille ICOI qui soit un multiple de NO [MAC] MAC permettant au récepteur de vérifier que CO a été reçu correctement Champ [Longueur de C] Un message C est divisé en F trames de q*T*N bits. Les paramètres N et q sont fixes et connus du récepteur. La longueur du message C est donné par 10 les deux champs suivants : • [taille d'un mot dans C (N/2 bits)] : valeur de T-1, où T est le nombre de symboles de N bits dans un mot, 1 T 15 Définition du multiplexage Les bits d'information de CO et C sont multiplexés dans les N_p bits des pages en cours. Le paquet utile de N_p bits est décomposé en (1+q) parties notées : M(0), M(1), m(2), ..., M(q). Dans la suite du document on appelle N-symbole un symbole de N bits, celui-ci pouvant être vu comme un élément du corps fini GF(2"). On définit de-même un NO-symbole comme un symbole de NO bits, pouvant être vu comme un élément du corps fini GF(2N0) La première partie M(0) est un NO-symbole calculé à partir de CO. Les q autres parties sont calculées à partir d'une trame sélectionnée d'un message C, et chaque partie étant un N-symbole. Le nombre de bits utiles par page est donc de N_p=NO+q*N. Le message CO est décomposé en TO parties de NO bits notés : W(0), W(1), 10 , W(TO-1). Le message C est décomposé en F trames, chaque trame en q mots, chaque mot en T N-symboles. En notant : f étant l'index de la trame dans le message, 0 j. Li(X) = B(j) * (le produit de TO-1 monomials (X ûA'k), tel que 0 j.) B(j) est l'élément de GF(2NO) qui est l'inverse dans GF(2N0) du produit deTO-1 éléments (A'i û A'k) , 0 j. 2) le vecteur de TO NO-symbols (W(0), .,W(TO-1)), considérés comme le 10 polynôme P(X), est ensuite calculé de la manière suivante : P(X) = Z(0) * Lo(X) + Z(1) * L1(X) + ... + Z(TO-1) * LTO-1(X). Extraction de l'information de C dans la page courante: Soit F le nombre de trame dans C, q le nombre de mots dans une trame et T le nombre de N-symboles dans un mot. 15 Les paramètres F et T sont calculés à partir du champ "longueur du message" inclus dans la signalisation CO. Le paramètre q est fixe (indépendant du message) et connu du récepteur. Les q N-symboles M(1)...M(q) de la page courante sont respectivement des informations sur les q mots enfouis dans une trame spécifique de C. L'index 20 de la trame sélectionnée et la nature du N-symbole de l'information sur ses mots sont définis sans ambiguïté avec le paramètre [page ref]. Tout N-symbole (N bits) est considéré aussi comme un élément du corps fini ayant2N éléments GF(2"). Un N-symbole d'information sur un mot contenant T N-syrboles sera une 25 combinaison linéaire de ses T N-symboles considérés dans GF(2N). Plus précisément : L'index de la trame sélectionnée dans M est : f=H5[page ref]. La fonction H5 est, par exemple, telle que f=H5([page ref]) est à peu près équidistribuée dans [0,...F-1] lorsque [page ref] change de manière aléatoire...DTD: Posons A=H2([Page ref]) un N-symbole calculé à partir de [Page Ref] avec une fonction H2. .La fonction H2 est, par exemple, telle que H2([Page ref]) est à peu près équidistribué dans l'ensemble des N-symboles lorsque [page ref] change de manière aléatoire. Soient : • W(0,0), W(0,1),..., W(O,T-1), les T N-symboles du mot TRAME[f][0] dans la trame concernée f; • W(1,0), W(1,1),..., W(1,T-1), les T N-symboles du mot TRAME[f][1] dans la trame concernée f; • • W(q-1,0),...,W(q-1,T-1), les T N-symboles du mot TRAME[f][q-1] dans la trame concernée f Pour 1 ., W(0,T-1)), les T N-symboles du mot TRAME[f][0] dans la trame concernée f, • (W(k,O), ..., W(k,T-1)), les T N-symboles du mot TRAME[f][k] 20 dans la trame concernée f, • (W(q-1,0), ..., W(q-1,T-1)) les T N-symboles du mot TRAME[f][q-1] dans la trame concernée f. C) Calcul de la sortie à partir de l'entrée 25 Chaque mot de T N-symboles (W(k,O), W(k,1), ...W(k,T-1)) à récupérer est aussi considéré comme un polynôme de GF(2N )[X] de degré T-1 : Pk(X) = W(k,O) + W (k,1) X + ... + W(k,T-1) XT-1 Pk(X) est récupéré par interpolation comme étant l'unique polynôme de degré T-1 tel que Pk(Aj) = Z(j,i), pour 0 j. Lj(X) = B(j) * (le produit de T-1 monômes(X ûAk), tel que 0 j.) B(j) est l'élément de GF(2") qui est l'inverse dans GF(2") du produit de T-1 éléments (Aj û Ak) , 0 j. 2) Le mot courant de T N-symbols (W(k,O), ...,W(k,T-1)), considéré comme le polynôme Pk(X) 0 REVENDICATIONS 1 ù Procédé pour gérer des interruptions erratiques dans un système de transmission où les messages à transmettre sont composés de paquets de données et s'expriment au moyen d'un polynôme de degré t-1, les émetteurs et les récepteurs partageant une information permettant de référencer les paquets de données, caractérisé en ce qu'il comporte au moins les étapes suivantes : • au cours de la transmission du message, générer au moins t 10 points Ai et les évaluations P(Ai) du polynôme P pour les t points Ai, • transmettre les évaluations P(Ai) des t points vers le ou les récepteurs concernés, • vérifier que les t évaluations sont valables, 15 • utiliser l'information référençant les paquets et les t évaluations valables du polynôme pour déterminer les points Ai correspondant au paquet de données référencé par i, • à partir des P(Ai) et des Ai déterminer le polynôme P utilisé, et à partir du polynôme en déduire le message. 20 2 ù Procédé selon la revendication 1, caractérisé en ce que l'on utilise une fonction d'interpolation pour déterminer le polynôme. 3 ù Procédé selon la revendication 1, caractérisé en ce que l'on divise le 25 message en plusieurs parties et on applique les étapes du procédé selon la revendication 1 sur chaque partie. 4 ù Procédé selon la revendication 1, caractérisé en ce que lors de la détection d'erreur, les évaluations P(Ai) contenues dans une page 30 erronées sont supprimées et le récepteur reste à l'écoute de nouvelles pages.5 û Procédé selon la revendication 1, caractérisé en ce que l'on transmet une signalisation CO associée à un message C, la signalisation étant composée de T0*N0 bits et vue comme un polynôme de degré (TO-1) et en ce que à la réception : • on collecte TO pages ne contenant pas d'erreurs, et chaque page utilisant un point différent des autres pages, on reconstitue à partir de ces pages la signalisation CO à partir de ces pages en utilisant une interpolation polynomiale, • on déduit à partir de CO, la longueur du message C et la manière dont on a découpé le message C en F trames, chaque trame découpée en q mots, chacun des mots étant représenté par un polynôme de degré (T-1), • pour chaque polynôme correspondant à un mot on collecte T évaluations sans erreurs du polynôme, et • en utilisant des points distincts, on reconstitue le message C en utilisant l'interpolation polynomiale. 6 û Procédé selon l'une des revendications 1 à 5, caractérisé en ce que le 20 système de transmission comprend un satellite de communication. 7 û Système pour gérer des interruptions erratiques dans un système de transmission comprenant un ou plusieurs émetteurs Ej et un ou plusieurs récepteurs Rk, où les messages à transmettre sont composés de paquets de 25 données et s'expriment au moyen d'un polynôme de degré t-1, les émetteurs et les récepteurs partageant une information permettant de référencer les paquets de données, caractérisé en ce qu'il comporte au moins les éléments suivants : un centre de formatage (1) et les récepteurs étant pourvus de moyens (2) adaptés à exécuter les étapes du procédé selon l'une des 3o revendications 1 à 5.