FR3095094A1 - Procedes de multi-diffusion et d'obtention de contenus numeriques dans un reseau, dispositif et systeme associes - Google Patents

Abstract

L'invention concerne un procédé de multidiffusion et un procédé d'obtention de fragments de fichiers manquants à une pluralité de récepteurs de manière à optimiser les débits et temps de transmission à travers un réseau de communication. Les fragments de fichiers manquants pour chaque récepteur sont régroupés ou répartis en blocs en tenant compte de la capacité de décodage de chaque récepteur puis combinés par addition binaire (XOR) et codés par application d'un code polaire avant d'être émis sur le canal de transmission. En réception, les récepteurs disposant d'une mémoire cache font usage des données contenues dans leur mémoire de manière à déterminer des bits gelés (frozen bits) utilisés pour décoder les bits reçus. Figure pour l' abré g é : Figure 2.

Description

PROCEDES DE MULTI-DIFFUSION ET D'OBTENTION DE CONTENUS NUMERIQUES DANS UN RESEAU, DISPOSITIF ET SYSTEME ASSOCIES

Domaine technique de l'invention

La présente invention se situe dans le domaine des communications numériques et concerne plus particulièrement une technique de codage et de décodage pour la transmission de données numériques à une pluralité de récepteurs dans un réseau de communication.

Elle trouve une application privilégiée pour la multidiffusion (multicasten anglais) de contenus numériques, en particulier dans des réseaux radio-mobiles de type 4G ou 5G.

Par la suite, on désignera de manière générale parcontenu numériquetoute séquence d'éléments binaires sélectionnés parmi l'ensemble {0, 1}. Cette séquence est généralement structurée sous la forme de fichiers ou de fragments de fichiers selon un format donné (e.g .mpeg, mp4, jpeg,etc). De préférence, la nature des contenus numériques est de type audio et/ou vidéo.

Par la suite, on désignera de manière générale parr écepteurtout type de nœud du réseau adapté à communiquer avec d'autres nœuds du réseau et destiné à recevoir des contenus numériques d'un ou plusieurs nœuds du réseau (i.e.nœud source ou serveur). Un récepteur peut être constitué par un terminal d'un utilisateur, tel qu'une tablette, un téléphone portable, un ordinateur ou tout autre objet connecté au réseau de communication.

Arrière-plan technique

Stockage préalable (caching, prefetching)

Pour diffuser efficacement des contenus numériques à une pluralité de récepteurs dans un réseau de communication, il est connu de stocker temporairement tout ou partie de ces contenus dans des mémoires temporaires dites mémoires caches des récepteurs. Cette opération de stockage est connue sous le nom decachingen anglais.

Par la suite, on désignera parm émoire cacheou antémémoire, toute mémoire destinée à stocker temporairement tout type de données numériques, tels que des fichiers ou fragments de fichiers de données.

De manière connue, les mémoires caches sont utilisées pour stocker préalablement, au plus près des utilisateurs, des fichiers populaires (i.e.susceptibles d'être demandés ultérieurement par ces utilisateurs).

Par anticipation, les contenus numériques sont avantageusement stockés dans les mémoires caches d'une pluralité de récepteurs, de préférence lorsque le trafic est minimal au sein du réseau, de manière à limiter les risques de saturation du réseau pendant des périodes de pointe (i.e.lorsque le réseau est fortement sollicité).

Dans la mesure où une partie des contenus numériques a été préalablement stockée localement au niveau des récepteurs, il ne reste qu'à transmettre les contenus numériques manquants de chacun des fichiers requis par les utilisateurs au moment où ceux-ci souhaitent disposer de l'intégralité de ces fichiers.

Par la suite, cette étape de transmission des contenus numériques manquants sera désignée par étape delivraison(i.e. deliveryen anglais). Cette étape est exécutée en réponse à une requête d'un utilisateur émise à partir d'un terminal (e.g .téléphone portable) et à n'importe quel moment, par exemple pendant une période où le trafic est relativement élevé à travers le réseau.

Cette étape de stockage préalable ditepr é -stockageest mise en œuvre au moyen d'algorithmes intelligents de pré-extraction de données connus adaptés à aller chercher par anticipation (prefetchingen anglais) auprès d'un ou plusieurs nœuds sources, des fragments de fichiers à stocker dans les mémoires caches des récepteurs avant de recevoir une requête d'un utilisateur pour l'obtention des fragments manquants.

Ces algorithmes, qualifiés deprefetchingen anglais, sont tels que ceux décrits, par exemple, par M.A. Maddah-Ali et U. Niesen dans un article intitulé" Fundamental limits of caching ",publié dansIEEE Transactions on Information Theory,2014. Ce type d'algorithme se distingue notamment en ce qu'il permet de diversifier les contenus numériques pré-stockés à travers les terminaux (e.g .tablettes, téléphones portables, ordinateurs) d'utilisateurs ou de groupes d'utilisateurs, tout en augmentant considérablement les gains en termes de débit ou de temps de transmission en comparaison avec les algorithmes deprefetchingtraditionnels, selon lesquels tous les récepteurs obtiennent dans leur mémoires caches un même contenu numérique.

La présente invention concerne plus particulièrement la phase de livraison, lors de laquelle les utilisateurs des récepteurs R_irequièrent les fichiers W_i, en supposant que leurs mémoires caches respectives ont déjà été préalablement alimentées en fragments de fichiers par au moins un nœud source T, lors de l'étape deprefetchingexécutée selon un algorithme connu.

Autrement dit, dans le cadre de la présente invention, on fait l'hypothèse qu'il existe au sein du réseau plusieurs récepteurs R_icomprenant chacun une mémoire cache M_i, dans laquelle ont été préalablement stockés des fragments de fichiers W_i ^j.

Combinaison de fragments de fichiers : X-OR

Afin d'optimiser le nombre de paquets de données transmis dans le réseau, il est connu de combiner au sein d’un même paquet de données plusieurs fragments de fichiers destinés respectivement à différents récepteurs, ce même paquet étant transmis à l’ensemble des récepteurs requérant les fragments manquants d’un même fichier.

De manière classique, la combinaison des fragments de fichiers consiste en une addition binaire de l’ensemble des fragments à transmettre, en utilisant l’opérateur logique OU exclusif (X-OR :eXclusive ORen anglais) désigné par le symbole . L’application cet opérateur X-OR constitue une opération de codage.

Selon le scénario de l'art antérieur illustré à lafigure 1, on suppose que, lors de l’étape préalable decachingouprefetching, un émetteur T (ou nœud source), tel qu'une station de base radio-mobile 4G ou 5G, a découpé les fichiers W₁, W₂, W₃en une pluralité depfragments (e.g .p=3) notés respectivement {W₁ ¹, W₁ ², W₁ ³}, {W₂ ¹, W₂ ², W₂ ³}, {W₃ ¹, W₃ ², W₃ ³} et distribué certains de ces fragments de fichiers dans les mémoires caches M₁, M₂, M₃respectives de trois récepteurs R₁, R₂, R₃. Chaque fragment de fichier est noté W_k ^l, où le sous-indicekdésigne le k^èmerécepteur R_ket le sur-indicelidentifie un fragment parmi l'ensemble depfragments du fichier W_krésultant du découpage de ce fichier.

Par exemple, on suppose que les fragments de sur-indice l=1(i.e.W₁ ¹ , W₂ ¹ , W₃ ¹ ) sont envoyés aux récepteurs R₁et R₂, que les fragments de sur-indice l=2(i.e.W₁ ² , W₂ ² , W₃ ³ ) sont envoyés aux récepteurs R₂et R₃et que les fragments de sur-indice l=3(i.e.W₁ ³ , W₂ ³ , W₃ ³ ) sont envoyés aux récepteurs R₁et R₃.

A cet effet, chacun des trois récepteurs R₁, R₂, R₃émet préalablement une requête à destination du nœud source T pour requérir la connaissance complète d’un fichier particulier,e.g .W₁, W₂, W₃respectivement.

Par exemple, le premier récepteur R₁requiert le fichier complet W₁(i.e.le fragment manquant W₁ ²), le deuxième récepteur R₂requiert le fichier complet W₂(i.e.le fragment manquant W₂ ³) et le troisième récepteur R₃requiert le fichier complet W₃(i.e.le fragment manquant W₂ ³). Ainsi, l’envoi, par le nœud source T, d’un unique paquet contenant la combinaison des fragments de fichiers manquants W₁ ², W₂ ³, W₃ ¹notée W₁ ² W₂ ³ W₃ ¹permet simultanément :

au premier récepteur R₁disposant préalablement dans sa mémoire cache M₁des fragments {W ₁ ¹ , W₂ ¹, W₃ ¹;W ₁ ³ , W₁ ³, W₁ ³} d’obtenir, à partir de ces fragments et de ladite combinaison, le fragment manquantW ₁ ² et ainsi reconstituer le ficher W₁dans son intégralité (W₁ ¹| W₁ ²| W₁ ³);

au deuxième récepteur R₂disposant préalablement dans sa mémoire cache M₂des fragments {W₁ ¹,W ₂ ¹ , W₃ ¹; W₁ ²,W ₂ ² , W₃ ²} d’obtenir, à partir de ces fragments et de ladite combinaison, le fragment manquantW ₂ ³ et ainsi reconstituer le ficher W₂dans son intégralité (W₂ ¹| W₂ ²| W₂ ³); et

au troisième récepteur R₃disposant préalablement dans sa mémoire cache M₃des fragments {W₁ ², W₂ ²,W ₃ ² ; W₁ ³, W₂ ³,W ₃ ³ } d’obtenir, à partir de ces fragments et de ladite combinaison, le fragment manquantW ₃ ¹ et ainsi reconstituer le ficher W₃dans son intégralité (W₃ ¹| W₃ ²| W₃ ³).

Cette technique de multidiffusion codée, communément désignéecoded multicastingen anglais, a été décrite, par exemple, par M. A. Maddah-Ali et U. Niesen, dans leur article intitulé"Fundamental limits of caching"et publié dans la revueIEEE Transactions on Information Theory,vol. 60, no. 5, pp. 2856-2867, May 2014. Dans les prototypes actuels, l'application de l'opérateur X-OR permet, lors de l'étape de livraison, de combiner des fragments de contenus numériques pour offrir la possibilité de multidiffusion (i.e.envoi d'une même séquence de bits utiles à plusieurs récepteurs). Toutefois, les inventrices ont démontré, lors de leurs travaux, que ces prototypes présentent des limitations en termes de performances de transmission, (débits faibles ou temps de transmission relativement élevé). Les inventrices ont identifié que cet inconvénient est principalement dû au fait que la façon dont les fragments de fichiers sont combinés ne tient pas compte de la façon dont les fragments sont ensuite transmis sur le canal de propagation.

Codage de canal

Dans un réseau de communication radio-mobile, il est bien connu que tous les récepteurs ne sont pas équivalents en termes de capacité de réception, étant donné notamment que les conditions de canal peuvent varier en fonction du récepteur considéré. De ce fait, il existe des récepteurs faibles, qui limitent naturellement le débit de réception de tous les autres récepteurs, créant ainsi un goulot d'étranglement pour des transmissions utilisant des techniques de codage/décodage de canal conventionnelles.

En matière de communication sans fil, notamment radio-mobile selon le standard 4G ou 5G, lecodage de canalest communément utilisé pour protéger les informations émises contre des erreurs de transmission pouvant être causées par la présence de bruit et/ou d’interférences sur le canal de transmission du récepteur concerné ou par une puissance du signal reçu insuffisante.

De manière connue, un codeur de canal est mis en œuvre par le nœud source ou émetteur (e.g .station de base 4G ou 5G) de manière à coder l’information à transmettre sur le canal de transmission. Un décodeur de canal est mis en œuvre par le récepteur (e.g .terminal mobile) de manière à mitiger les erreurs de transmission et récupérer avec fiabilité l’information émise par l'émetteur après transmission sur le canal bruité.

Au cours des dernières décennies, plusieurs codes de canal à haute performance ont été développés pour transmettre des données de manière fiable et à des débits approchant la limite théorique imposée par la capacité de transmission du canal selon le théorème de Shannon. En particulier, les turbo-codes ont été exploités dans les standards de communication radio-mobile de troisième et quatrième générations (3G, 4G) tandis que les codes LDPC (Low Density Parity Check) ont été adoptés dans le standard Wi-Fi (e.g .IEEE 802.11 a/b/g) et dans les standards de communication par satellite.

Plus récemment sont apparus les codes polaires, ditsPolar Codesen anglais, offrant de bonnes performances de correction d’erreurs pour la réception de messages courts. Les inventrices ont constaté, au cours de leurs travaux de recherche, que les codes polaires n’ont pas encore été appliqués spécifiquement dans le cadre de la phase de livraison de contenus numériques (e.g .fragments de fichiers manquants lors de la phase de livraison), notamment dans des réseaux radio-mobiles.

Un problème technique visé par la présente invention est de fournir un procédé de multi-diffusion qui, lors de l'étape de livraison, permet de transmettre les fichiers ou les fragments de fichiers manquants à chacun des récepteurs, de manière à minimiser le temps de livraison à travers le réseau de communication ou de manière équivalente à maximiser le débit de transmission pour l'ensemble des récepteurs.

En réponse à ce problème, les inventrices proposent un procédé de multi-diffusion et un procédé d'obtention de fragments de fichiers mettant en œuvre une technique de codage/décodage améliorée qui tient compte des limitations liées aux différents récepteurs (e.g .conditions de canal de transmission), lors du codage du contenu numérique à transmettre aux récepteurs.

Selon l’approche suivie par les inventrices, il s'agit d’envoyer un même paquet de données numériques (i.e.une même séquence de bits codés) simultanément à différents récepteurs, de sorte que ce paquet puisse être décodé sans erreur par les récepteurs plus faibles, sans provoquer de limitation en termes de débit ou temps de transmission auprès des autres récepteurs.

La technique de codage proposée dans le cadre de la présente invention fait en sorte que les récepteurs les plus faibles ne créent pas de goulot d'étranglement en termes de débit binaire (Mbit/s) ou de manière équivalente ne créent pas des ralentissements de transmission, en particulier vis-à-vis des récepteurs les plus forts. Selon l'invention, chaque récepteur peut être servi à un débit adapté aux conditions de canal qui lui sont propres.

De manière générale, le termecodagepourra se référer à la manière de combiner plusieurs fragments de fichiers destinés à des récepteurs différents et/ou au codage de canal tel que défini ci-avant.

Ainsi, un objet de la présente invention est un procédé de multidiffusion de fragments manquants de fichiers numériques à un ensemble de récepteurs comprenant une pluralité de récepteurs faibles comprenant chacun une mémoire cache dans laquelle sont stockés un ou plusieurs fragments de fichiers numériques pré-stockés, les fragments manquants de fichiers destinés à être diffusés n'étant pas préalablement stockés dans la mémoire cache des récepteurs respectifs (i.e.de tous les récepteurs faibles) requérant ces fichiers.

Le procédé comprenant les étapes suivantes :

sélection d'un sous-ensemble de récepteurs faibles ;

pour chaque récepteur dudit sous-ensemble, identification d'au moins un fragment d'un fichier requis par ledit chaque récepteur et tel que ledit au moins un fragment est présent dans la mémoire cache de tous les autres récepteurs faibles appartenant audit sous-ensemble ;

pour chaque récepteur dudit sous-ensemble et pour chacun dudit au moins un fragment de fichier identifié lors de l'étape précédente, regroupement/répartition dudit au moins un fragment du fichier en une pluralité de blocs b de taille m_iégale à la capacité de décodage dudit récepteur ;

combinaison des blocs issus de l'étape c) de manière à fournir une séquence de bits combinés W_G,b;

codage d'une séquence de bits à transmettre comprenant la séquence de bits combinés W_G,b, par application d'une technique de codage, de manière à fournir une séquence de bits codés W_c; et

envoi de ladite séquence de bits codés W_cà un ensemble de récepteurs comprenant le sous-ensemble de récepteurs faibles.

Ainsi, le regroupement ou la répartition des fragments de fichiers tient compte de la capacité de décodage m_ide chaque récepteur R_i, cette capacité étant directement liée aux conditions de canal entre l'émetteur et le récepteur. Ceci permet avantageusement d'éviter aux récepteurs disposant des capacités de décodage les plus faibles de limiter le débit de transmission de tous les autres récepteurs, en évitant ainsi un goulot d'étranglement dans des réseaux de communication utilisant des techniques de codage/décodage conventionnelles (e.g .réseaux radio-mobiles de type 4G).

Par ailleurs, le procédé selon l'invention permet, par l'envoi d'une unique séquence de bits codée, de servir simultanément l'ensemble des récepteurs concernés évitant l'envoi de séquences multiples différentes propres à chaque récepteur. En réduisant le nombre de paquets transmis, le procédé selon l'invention contribue à optimiser les ressources du réseau (e.g .réduction de la signalisation,etc).

Selon une caractéristique de l'invention, chacun desdits blocs obtenus lors de l'étape c) est rempli par des bits "0" lors d'une étape de remplissage de sorte que la taille du bloc soit égale à la capacité de décodage maximale m_Gdes récepteurs faibles du sous-ensemble.

Ainsi, les blocs dans lequels sont regroupés un ou plusieurs fragments de fichiers ont tous la même taille et peuvent être facilement combinés entre eux lors de l'étape de combinaison d).

Selon une autre caractéristique de l'invention, l'étape de combinaison est mise en œuvre par application de l'opérateur logique OU exclusif (X-OR).

De manière avantageuse, l'opérateur OU exclusif est relativement simple à mettre en œuvre et nécessite une puissance de calcul modérée permettant ainsi d'optimiser l'architecture des émetteurs et des récepteurs associés.

Selon une autre caractéristique de l'invention, la technique de codage utilisée lors de l'étape de codage est une technique de codage polaire configurée pour recevoir en entrée les bits de ladite séquence de bits à transmettre.

A cet égard, les inventrices ont constaté que la sélection d'un code polaire parmi l'ensemble des codes utilisés pour mettre en œuvre un codage de canal existants pour coder la séquence de bits à transmettre à travers le canal de transmission est particulièrement efficace en termes de débits, dès lors que la séquence de bits à transmettre tient compte de la capacité de décodage de chacun des récepteurs comme décrit ci-avant. L'utilisation de codes polaires facilite l'envoi simultané de bits destinés à un ensemble de récepteurs faibles et de bits destinés à des récepteurs plus forts.

Ainsi, l'application d'un code polaire classique sur une séquence de bits construite de manière à prendre en compte la capacité de décodage de chaque récepteur du sous-ensemble comme décrit ci-avant est particulièrement avantageuse pour accroître les débits de transmission et par conséquent réduire le temps nécessaire pour permettre aux récepteurs de récupérer les fragments de fichiers manquants à travers le réseau.

Selon une autre caractéristique de l'invention, l'étape de codage comprend une sous-étape d'ordonnancement, lors de laquelle les bits de la séquence de bits à transmettre sont agencés par ordre croissant de leur probabilité d'erreur avant l'application de la technique de codage.

Ainsi, lors du codage de canal, le premier bit de la séquence de bits à transmettre est codé par le bit le plus fiable du code de canal, le deuxième bit de la séquence de bits à transmettre est codé par le deuxième bit le plus fiable du code de canal. Autrement dit, avant d'émettre, les bits du code de canal sont agencés par ordre croissant de leur paramètre Z (ou par probabilité d'erreur croissante) de manière à être envoyés dans cet ordre sur le canal de transmission.

Cette caractéristique est particulièrement avantageuse lorsque la technique de codage est basée sur un code polaire pour tenir compte des propriétés du canal. De cette façon, les récepteurs les plus faibles pourront bien décoder les bits qui leur sont dédiés.

Selon une autre caractéristique de l'invention, le procédé comprend en outre les étapes suivantes :

- sélection d'au moins un récepteur fort parmi ledit ensemble de récepteurs, ledit au moins un récepteur fort ne disposant pas de mémoire cache et requérant un fragment de fichier W_j,b(G) contenu dans les mémoires cache de récepteurs faibles du sous-ensemble G, de préférence, ledit récepteur fort ayant une capacité de décodage m_jsupérieure à la capacité de décodage maximale m_Gdes récepteurs faibles (m_j>m_G);

- concaténation de la séquence de bits combinés W_G,b avec le fragment de fichier W_j,b(G) de manière à former la séquence de données à transmettre destinée à être codée lors de l'étape de codage.

Selon cette particularité de l'invention, le procédé permet de servir également les récepteurs forts (i.e. ne disposant pas de mémoire cache) en incluant dans la séquence de bits à coder des fragments de fichiers destinés à ces récepteurs.

Un autre objet de l'invention est un procédé d'obtention (ou de lecture) d'au moins un fragment de fichier à partir d'une séquence de bits reçue Y_kcorrespondant à la séquence de bits codés W_cémise par un émetteur conformément au procédé de multidiffusion tel que décrit ci-dessus et transmise à travers un canal de transmission.

Le procédé d'obtention comprend en outre, pour chaque récepteur faible R_kappartenant au sous-ensemble G, les étapes suivantes:

réception de ladite séquence de bits reçue Y_k;

combinaison des fragments de fichiers destinés aux autres récepteurs faibles appartenant au sous-ensemble G, ces fragments étant stockés dans la mémoire cache M_kdu récepteur faible R_kde manière à obtenir une séquence combinée W_k,b,XOR(G);

sélection des m_kpremiers bits de ladite séquence combinée W_k,b,XOR(G), de manière à former une séquence combinée d'information W_k,b,XOR,data, les bits restant de la séquence combinée formant une séquence de bits gelés W_{k,b,XOR,frozen} ;

décodage de canal des m_kpremiers bits de la séquence de bits reçue en utilisant la séquence de bits gelés W_{k,b,XOR,frozen} de manière à former une séquence de bits décodés X_k, le décodage étant basé sur un code utilisé par l'émetteur T lors de l'étape de codage ;

combinaison de la séquence combinée d'information W_k,b,XOR,dataet de la séquence de bits décodée X_kde manière à obtenir les fragments de fichiers W_k,b(G\{k}) requis par le récepteur R_k.

Un autre objet de l'invention est un procédé de communication mis en œuvre dans un réseau comprenant une pluralité de nœuds de communication, le procédé comprenant les étapes du procédé de multidiffusion et les étapes du procédé d'obtention tels que décrits ci-dessus.

Un autre objet de l'invention est un dispositif de traitement de l’information comprenant des moyens pour mettre en œuvre les étapes du procédé de multidiffusion et/ou les étapes du procédé d'obtention tels que décrits ci-dessus.

Un autre objet de l'invention est un système de multidiffusion comprenant au moins un serveur configuré pour mettre en œuvre les étapes du procédé de multidiffusion tel que décrit ci-dessus et une pluralité de dispositifs clients configurés pour mettre en œuvre les étapes du procédé d'obtention tel que décrit ci-dessus.

L’invention concerne également un programme d’ordinateur comprenant des instructions adaptées à la mise en œuvre de chacune des étapes du procédé de multidiffusion et/ou du procédé d'obtention selon l’invention tels que décrits ci-dessus, lorsque ledit programme est exécuté sur un ordinateur ou tout autre dispositif équivalent.

L’invention concerne également un moyen de stockage d'informations, amovible ou non, partiellement ou totalement lisible par un ordinateur ou un microprocesseur comportant des instructions de code d'un programme d'ordinateur pour l'exécution de chacune des étapes du procédé de multidiffusion et/ou du procédé d'obtention selon l’invention.

Dans un mode particulier de réalisation, des étapes du procédé de multidiffusion et/ou du procédé d'obtention précité(s) sont déterminées par des instructions de programmes d'ordinateur.

En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre par un microprocesseur, ce programme comprenant des instructions adaptées à la mise en œuvre des étapes du procédé de multidiffusion et/ou du procédé d'obtention tels que mentionnés ci-dessus.

Ce programme peut utiliser n'importe quel langage de programmation et être sous la forme de 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 ou moyen de stockage d'informations, amovible ou non, partiellement ou totalement lisible par un microprocesseur, et comprenant des instructions de code d'un programme d'ordinateur pour l'exécution de chacune des étapes du procédé multidiffusion et/ou des étapes du procédé d'obtention tels que décrits ci-dessus.

Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comprendre un moyen de stockage, tel qu'une ROM, par exemple une ROM de microcircuit, ou encore un moyen d'enregistrement magnétique, par exemple un disque dur, ou encore une mémoire flash.

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 une plateforme de stockage d’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.

Le support d'informations et le programme d'ordinateur précités présentent des caractéristiques et avantages analogues au procédé qu'ils mettent en œuvre.

Brève description des figures

D'autres particularités et avantages de l'invention apparaîtront encore dans la description ci-après, en relation avec les dessins annexés, donnés à titre d'exemples non limitatifs.

La figure 1 illustre un scenario mettant en œuvre un procédé de multidiffusion codée connu de l’art antérieur.

La figure 2 illustre un scenario de multidiffusion codée dans lequel est mise en œuvre la présente invention.

La figure 3 illustre un exemple de combinaison de fragments de fichiers à destination de deux récepteurs faibles selon un premier mode de réalisation du procédé de multidiffusion selon l'invention.

La figure 4 illustre un exemple de combinaison de fragments de fichiers à destination de deux récepteurs faibles et d'un récepteur fort selon un deuxième mode de réalisation du procédé de multidiffusion selon l'invention.

La figure 5 illustre de manière schématique un exemple de mise en œuvre du codage de canal par l'émetteur et du décodage de canal par le récepteur après transmission sur le canal de transmission selon un mode de réalisation de l'invention.

La figure 6 illustre un mode de réalisation particulier du procédé de multidiffusion de l'invention.

La figure 7 illustre un exemple de mise en œuvre du procédé de multidiffusion de l'invention dans un réseau comprenant une pluralité de récepteurs faibles et une pluralité de récepteurs forts.

La figure 8 illustre un mode de réalisation particulier du procédé d'obtention de fragments de fichiers par un récepteur faible selon l'invention.

La figure 9 illustre un exemple de mise en œuvre du procédé d'obtention de fragments de fichiers par un récepteur faible selon l'invention, dans un réseau comprenant une pluralité de récepteurs faibles et une pluralité de récepteurs forts.

La figure 10 illustre de manière schématique les séquences de bits obtenues lors de l'exécution du procédé d'obtention selon l'exemple illustré à la figure 9.

La figure 11 illustre les résultats de performances obtenus grâce à l'invention en comparaison avec ceux obtenus par une technique de l'art antérieur.

La figure 12 est un bloc-diagramme schématique d'un dispositif de traitement de l’information pour la mise en œuvre d'un ou plusieurs modes de réalisation de l'invention.

Description détaillée de l'invention

Selon un aspect de l'invention, il s'agit de regrouper (ou répartir) les fragments de fichiers manquants à transmettre à un ensemble de récepteurs, en tenant compte de la capacité de décodage propre à chacun de ces récepteurs, avant de les combiner, par exemple, par l'application de l'opérateur X-OR.

Selon une particularité de l'invention, l'application d'une technique de codage de canal basée sur des codes polaires pour coder la séquence de bits préalablement combinés est particulièrement simple par rapport à d'autres techniques de codage de canal pour obtenir les meilleurs débits de transmission.

L'invention va être maintenant décrite dans le cadre de la multidiffusion de fragments de fichiers à une pluralité de récepteurs sur un réseau de communication de préférence radio-mobile, selon différents modes et variantes de réalisation donnés à titre d'exemple dans le cadre du scénario illustré sur lafigure 2.

De manière générale, on considère une communication, selon laquelle un unique émetteur T envoie du contenu numérique à une pluralité de récepteurs R₁,...R_Koù K désigne un entier naturel tel que K>2. L'objectif de cette communication est de fournir les fragments de fichiers manquants aux différents récepteurs, de sorte que les récepteurs R₁,...,R_Kobtiennent la connaissance complète des fichiers W₁,...,W_Krespectivement.

Pour des raisons de simplicité, l'invention est décrite uniquement pour un unique nœud source mais bien évidemment, l'invention s'applique également dans le cas où plusieurs nœuds sources sont destinés à diffuser des contenus numériques. Dans ce cas, un module de coordination pourra être fourni de manière à coordonner les émissions simultanées des différents nœuds sources à destination des récepteurs. Parmi l'ensemble des K récepteurs, un sous-ensemble de L récepteurs désignés R₁,...,R_Ldisposent d'une mémoire cache M₁,...,M_Ldédiée à la communication, où L désigne un entier naturel tel que L≤K. Par la suite, ces récepteurs sont dénommésr écepteurs faibles.

On suppose que les mémoires caches M₁,...,M_Lde ces L récepteurs faibles R₁,...,R_Lont été préalablement alimentées en fragments de fichiers par un nœud source ou émetteur T, lors d'une étape deprefetchingtelle que décrite précédemment.

A cet effet, l'émetteur T a préalablement découpé chaque fichier W_kde taille F_kcontenu dans une base de données 1, en un nombre entierpde fragments, tel que W_k=[W_k ¹,...,W_k ^p], où chaque fragment de fichier W_k ^l (avec 1≤l≤p) est constitué par Δ_k=F_k/p éléments binaires (ou bits appartenant à l'ensemble {0,1}). Autrement dit, chaque fichier W_kest découpé enpfragments de taille Δ_k.

L'émetteur T a la connaissance des fragments de fichiers envoyés à chaque récepteur lors de l'étape deprefetching. Cette connaissance est stockée, par exemple sous la forme d'une table dans la base de données 1 associant à chaque récepteur (e.g .R₁, R₂) les fragments de fichiers comme illustré sur la figure 2 que l'émetteur lui a précédemment envoyés. Cette table peut être mise à jour à chaque nouvel envoi de fragments de fichiers par l'émetteur T.

De manière générale, on suppose que parmi les K-L récepteurs restants, il existe des récepteurs désignés R_L+1,...,R_Kqui ne disposent pas de mémoire cache. Par la suite, on dénommera ces récepteurs parr écepteurs forts.

Dans l'exemple de lafigure 2(cas particulier simplifié où L=2 et K=3), le récepteur R₃est fort contrairement à R₁et R₂qui sont des récepteurs faibles disposant d'une mémoire cache M₁et M₂respectivement.

De manière générale, on suppose que l'émetteur T et l'ensemble des récepteurs R₁,...,R_Ksont configurés pour obtenir des informations relatives à l'état de leur canal de transmission utilisé pour la diffusion des contenus numériques. Pour chacun des récepteurs, ces informations incluent notamment la capacité C_kd'un canal de communication entre l'émetteur T et le récepteur R_kconsidéré.

Ainsi, pour une communication mettant en œuvre un codage de canal, le récepteur R_kest capable de décoder tout ensemble de m_k< n×C_kbits, oùnest un entier naturel non nul désignant la longueur du code de canal utilisé pour coder les informations transmises sur le canal de transmission.

Ces informations dites de canal sont obtenues de manière conventionnelle, par exemple pendant une phase de signalisation préalable, lors de laquelle l’émetteur envoie un signal de référence dit "pilot signal" en anglais. Ayant connaissance de ce signal de référence et en fonction du signal reçu, chaque récepteur R_k(faible ou fort) est adapté à estimer la capacité associée à son propre canal de transmission. Il envoie alors cette information sur un lien en voie de retour à l’émetteur. Sur réception de ces informations, l'émetteur T les stocke dans une mémoire, par exemple dans la base de données 1, de manière à maintenir à jour les capacités de décodage de chacun des récepteurs.

Selon l'exemple simplifié de la figure 2, le système de communication mis en œuvre pour la multidiffusion de fragments de fichiers comprend deux récepteurs faibles R₁, R₂, un récepteur fort R'₃,i.e.L=2 et K=3, au moins un nœud d'émission T et au moins un réseau de communication (non illustré).

On suppose que les trois fichiers W₁, W₂, W₃(i.e.k={1; 2; 3}) destinés respectivement aux trois récepteurs R₁, R₂, R'₃sont préalablement découpés chacun en trois fragments (i.e.p=3: l={1, 2, 3}),i.e.: W₁=[W₁ ¹,W₁ ²,W₁ ³] ; W₂=[W₂ ¹,W₂ ²,W₂ ³] ; W₃=[W₃ ¹,W₃ ²,W₃ ³].

Comme décrit ci-avant, ces fragments sont stockés dans la base de données 1. Ils sont ensuite distribués aux récepteurs R₁et R₂, par exemple, de sorte que les fragments de sur-indice l=1(i.e.W₁ ¹ , W₂ ¹ , W₃ ¹ ) sont envoyés au récepteur R₁, les fragments de sur-indice l=2(i.e.W₁ ² , W₂ ² , W₃ ² ) sont envoyés aux récepteur R₂et les fragments de sur-indice l=3(i.e. W₁ ³ , W₂ ³ , W₃ ³ ) sont envoyés aux récepteurs R₁et R₂. Dans ce contexte, on suppose que :

- le premier récepteur R₁ayant requis le fragment de fichier W₁ ², dispose d'une capacité de décodage m₁et comprend dans sa mémoire cache M₁les fragments de fichiers {W₁ ¹, W₂ ¹, W₃ ¹ ; W₁ ³, W₂ ³, W₃ ³} ;

- le deuxième récepteur R₂ayant requis le fragment de fichier W₂ ¹, dispose d'une capacité de décodage m₂et comprend dans sa mémoire cache M₂les fragments de fichier W₁ ², W₂ ², W₃ ³; W₁ ³, W₂ ³, W₃ ³}; et

- le troisième récepteur R'₃ayant requis le fragment de fichier W₃ ², dispose d'une capacité de décodage m₃mais ne comprend aucune mémoire cache (i.e.récepteur fort).

Les capacités de décodage m₁, m₂, m₃sont préalablement déterminées comme décrit ci-avant et associées respectivement aux récepteurs R₁, R₂, R'₃dans la base de données 1.

Un mode de réalisation particulier du procédé de multidiffusion selon l'invention va être maintenant décrit en référence à lafigure 6.

Lors d'une étape de sélection E1, l'émetteur T sélectionne un groupe ou sous-ensemble G de récepteurs parmi l'ensemble des L récepteurs disposant d'une mémoire cache (i.e.sous-ensemble de récepteurs faibles). D'après l'exemple de lafigure 2, le groupe G est constitué par l'ensemble des récepteurs faibles R₁et R₂.

Lors d'une étaped'identification E3, le nœud source T identifie, pour chaque récepteur R_iappartenant au groupe ou sous-ensemble G, les fragments du fichier W_iqui sont stockés dans les mémoires caches M_λde tous les autres récepteurs du sous-ensemble G (i.e.G\{i}).

Selon l'exemple détaillé illustré sur lafigure 7, cet ensemble de fragments est désigné par W_i(G\{i}), tel que W_i(G\{i})_{λ  G\{i}}M_λ, où désigne l'opérateur ensembliste "intersection". Ainsi, selon le scénario de lafigure 2, le nœud source T est adapté à identifier que pour le premier récepteur R₁, le fragment W₁ ²du fichier W₁est stocké dans la mémoire cache M₂du deuxième récepteur R₂et que pour le deuxième récepteur R₂, le fragment W₂ ¹du fichier W₂est stocké dans la mémoire cache M₁du premier récepteur R₁. Cette étape d'identification E3 servira avantageusement à récupérer les fragments de fichiers manquants lors l'étape de décodage qui sera décrite ultérieurement.

Lors d'une étape de regroupement (ou répartition) E5, le nœud source T est adapté à regrouper (ou répartir) les ensembles de fragments de fichiers W_i(G\{i}) préalablement identifiés lors de l'étape d'identification E3. Le regroupement (ou la répartition) des fragments de fichier est effectuée par le nœud source T en tenant compte de la capacité de décodage m_ide chacun des récepteurs R_i, ce qui permet avantageusement de maximiser les débits de transmission ou de manière équivalente de minimiser le temps de transmission pour l'acquisition des fragments de fichiers manquants par les différents récepteurs.

Selon l'exemple détaillé de lafigure 7, les fragments de fichiers de chaque ensemble W_i(G\{i}) destinés au récepteur R_isont regroupés (ou répartis) au sein de b_iblocs de fragments de fichiers. La représentation binaire d'un bloc est désignée par W_i,j(G\{i}), où 1≤j≤b_ide sorte que W_i(G\{i})={W_i,1(G\{i}),...,W_{i,b i}(G\{i})}. Ainsi, W_{i, 1} (G\{i}) est la représentation binaire du bloc n°1de l'ensemble W_i(G\{i}), tandis que W_{i, b} (G\{i}) est la représentation binaire du bloc n°bde l'ensemble W_i(G\{i}) et W_{i, bi} (G\{i}) est la représentation binaire du bloc n°b _i de l'ensemble W_i(G\{i}).

Par exemple, le nombre de blocs b_iest calculé en divisant le nombre de fragments dans l’ensemble W_i(G\{i}) associé au fichier W_istockés dans toutes les mémoires caches des récepteurs de G\{i} par le nombre q_i=m_i/Δ_ide fragments du fichier W_ique le récepteur R_ipeut décoder de façon fiable pendant la durée d’un mot de code, le résultat de cette division étant arrondi à l'entier supérieur le plus proche. Ainsi, chacun des ensembles de fragments de fichiers W_i(G\{i}) est assemblé en blocs de taille égale au nombre de bits maximal m_ique chaque récepteur R_ipeut décoder pendant la durée d’un mot de code, ce qui permet avantageusement de tenir compte par la suite des conditions du canal entre l'émetteur T et le récepteur R_inotamment lors de l'étape de codage de canal décrite ci-après.

Par exemple, si l'ensemble W_i(G\{i}) comprend 10 000 fragments de fichiers, l'étape de regroupement E5 permet d'assembler (ou de répartir) ces fragments en 10 blocs de 1000 fragments chacun, en supposant que le récepteur R_ipeut décoder au maximum 1000 fragments par unité de temps de référence sans faire d'erreur.

Le regroupement des ensembles de fragments en blocs par le nœud source T va être maintenant décrit de manière détaillée en référence aux figures 3 et 4 selon le scénario de la figure 2.

Lafigure 3illustre un premier mode de réalisation, selon lequel les fragments de fichiers destinés aux deux récepteurs faibles R₁et R₂sont combinés sans tenir compte du récepteur fort R₃(e.g .absence de récepteurs forts). Par exemple, l'ensemble des fragments de fichiers destinés au premier récepteur R₁(i.e.W₁(G\{1}) est réparti en 3 blocs de taille égale à m₁, tandis que l'ensemble des fragments de fichiers destinés au deuxième récepteur R₂(i.e.W₂(G\{2}) est réparti en 2 blocs de taille égale à m₂>m₁. La capacité maximale de décodage des récepteurs du sous-ensemble G est égale à m_g(i.e.m_g=Max{m₁, m₂}). Dans cet exemple particulier, on considère que m_g=m₂.

Selon la représentation particulière de lafigure 3, le fragment de fichier W₁ ²appartenant à l'ensemble de fragments de fichiers W₁(G\{1}) destiné au premier récepteur R₁est inclus intégralement dans l'un des trois blocs représentés, chacun de ces blocs étant destiné à recevoir un ou plusieurs fragments de fichiers de l'ensemble W₁(G\{1}). De même, le fragment de fichier W₂ ¹appartenant à l'ensemble de fragments de fichiers W₂(G\{2}) destinés au deuxième récepteur R₂est inclus intégralement dans un des deux blocs représentés, chacun de ces blocs étant destiné à recevoir un ou plusieurs fragments de fichiers de l'ensemble W₂(G\{2}.

Selon l'exemple ci-dessus, un bloc contient un fragment de fichier. Toutefois, on pourra considérer d'autres façons de répartir les fragments de fichiers à travers les blocs, en particulier en faisant en sorte que les blocs comprennent une pluralité de fragments de fichiers.

Dans le scénario décrit en référence à lafigure 2, seul un fichier manquant a été identifié pour chacun des récepteurs R₁, R₂, R'₃pour des raisons de simplicité de description. Toutefois en pratique, il est prévu de fournir simultanément plusieurs fragments de fichiers manquants à un récepteur respectif ou à plusieurs récepteurs ayant requis ces fragments. Dans ce cas (non illustré), on considérera que chacun des ensembles de fragments de fichiers W₁(G\{1}), W₂(G\{2}) et W₃(G\{2}) et de manière générale, l'ensemble de fragments de fichiers W_i(G\{i}) destinés au récepteur R_icomprend une pluralité de fragments de fichiers, chacun de ces fragments de fichiers pouvant être regroupés (ou répartis) dans un ou plusieurs blocs b de taille m_ilors de l'étape E5.

Lafigure 4illustre un premier mode de réalisation selon lequel les fragments de fichiers W₁ ², W₂ ¹destinés respectivement aux deux récepteurs faibles R₁et R₂sont combinés en tenant compte du récepteur fort R'₃. Le récepteur fort R'₃dispose d'une capacité de décodage m₃supérieure à la capacité de décodage maximale des récepteurs faibles (i.e.m₃>Max(m₁, m₂)=m₂, oùMax()désigne la fonction qui fournit en sortie la valeur maximale de ses arguments d'entrée).

De manière générale, lors de l'étape de regroupement (ou de répartition) E5, l’ensemble de fragments de fichiers W_i(G\{i}) sont regroupés (ou répartis) dans un ensemble de b_iblocs de fragments de fichiers, chaque bloc b ayant pour représentation binaire W_i,b(G\{i}) tel que 1≤ b ≤b_i. Par exemple, chacun des blocs comprend q_i(q_i=m_i/Δ_i) fragments de fichiers.

Ainsi, pour chaque récepteur R_i, la répartition des fragments de fichiers dans chacun des blocs tient compte avantageusement de la capacité de décodage m_ide chaque récepteur R_i.

Le nœud source T est adapté pour identifier le plus volumineux bloc b_Gde données (i.e.bloc de fragments de fichier) à transmettre à destination des récepteurs du sous-ensemble G, tel que b_G=Max(b_λ) avec 1≤λ≤L.

Lors d'une étape de remplissage E6 (i.e paddingen anglais) selon lafigure 6, le nœud source T complète les représentations binaires des blocs W_i,b(G\{i}) en y insérant des bits nuls "0", de telle sorte que la taille de chaque bloc b soit égale au nombre de bits que les récepteurs appartenant au sous-ensemble G sont capables de décoder sur un mot de code de canal, cette taille étant égale à m_G=Max(m_λ) avec 1≤λ≤L. Ainsi, à l'issue de l'étape de remplissage E6, tous les blocs b[1,...,b_i] ont une même taille égale à m_G. Cette étape de remplissage permet avantageusement de préparer l'étape de combinaison des représentations binaires des blocs b telle que décrite ci-après.

Lors d'une étape de combinaison E7, les blocs de taille m_Gaprès avoir été éventuellement complétés par des bits nuls (i.e."0") lors de l'étape de remplissage E6 sont combinés bit par bit en appliquant l'opérateur X-OR tel que décrit ci-avant. Par exemple, on notera W_G,b= _{i  G \{i}}W_i,b(G\{i}) la séquence de bits combinés résultant de l'étape de combinaison E7.

D'après l'exemple de lafigure 7, le procédé de multidiffusion selon l'invention est adapté pour servir également des récepteurs forts, tel que le récepteur R'₃selon le scénario de la figure 2, de manière à lui fournir le fragment de fichier manquant W₃ ².

Ainsi, dans ce mode de réalisation particulier, le nœud source T sélectionne, lors d'une étape de sélection E8, un récepteur R_jparmi les récepteurs ne disposant pas de mémoire cache (e.g .L+1≤j≤K). De préférence, ce récepteur fort R_ja une capacité de décodage m_jsupérieure à celle de n'importe quel des récepteurs faibles,i.e.appartenant à l'ensemble G (i.e.m_j> m_G). Par exemple, le récepteur R_jsélectionné est tel qu'il requiert des fragments d'un fichier W_jstockés dans les mémoires caches de tous les récepteurs faibles appartenant à l'ensemble G, ces fragments étant désignés par l'ensemble W_j(G). On suppore qu'au moins une partie de ces fragments n'a pas encore été envoyée audit récepteur R_j.

Par exemple, pour chaque bloc b[1,...,b_G], on désignera par W_j,b(G) tel que W_j,b(G)_{λ  [1,...,L]}M_λ≠, l'ensemble des fragments de fichiers (non vide) requis par le récepteur fort R_jet contenus dans les mémoires caches des récepteurs du sous-ensemble G. Si plus de m_j-m_Gbits de W_j(G) n'ont pas encore été envoyés au récepteur R_j, le nœud source sélectionne les z_bprochains fragments de W_j,b(G) tels que z_{b *}Δ_k≤m_j-m_G.

Lors d'une étape de concaténation E8.1, le nœud source T est adapté à concaténer, pour chaque bloc b[1,...,b_G], la séquence binaire W_G,bobtenue à l'issue de l'étape de combinaison E7 et la séquence binaire W_j,b(G) de taille m_j-m_Gsélectionnée parmi l'ensemble W_j(G) de manière à obtenir la séquence concaténée W_G,b,final=[W_G,b|W_j,b(G)] dans laquelle les séquences binaires W_G,bet W_j,b(G) sont mises bout à bout. Par la suite, le symbole | désignera l'opération de concaténation de deux séquences binaires.

Lors d'une étape de codage de canal E9, le nœud source T est adapté à appliquer une technique de codage de canal basée de préférence sur un code polaire (i.e. Polar Codeen anglais). En effet, une particularité de l'invention réside précisément dans la sélection des codes polaires parmi l'ensemble des codes existants pour coder la séquence de bits combinés W_G,bà l'issue de l'étape de combinaison E7 et en particulier pour coder la séquence concaténée W_G,b,finalà l'issue de l'étape de concaténation E8.1 dans le cas il est prévu de servir un ou plusieurs récepteurs forts.

En effet, les inventrices ont constaté, lors de leurs travaux de recherche, d'une part que les solutions de l'art antérieur appliquent un codage de canal indépendamment de la manière dont les paquets envoyés sur le réseau ont été créés ou obtenus et d'autre part que les codes polaires n'ont pour l'instant pas encore été exploités dans le cadre de la multidiffusion de fragments de fichiers à travers un réseau, notamment un réseau radio-mobile.

Selon une particularité de l'invention, un code polaire est appliqué à une séquence de bits finale contenant des blocs de fragments de fichiers destinés à être transmis à l'ensemble des récepteurs. Cette séquence de bits finale, désignée W_G,bou W_G,b,finalen fonction du cas de figure considéré, a été formée en tenant compte de la capacité de décodage m_ide chacun des récepteurs R_icomme décrit ci-avant. Ainsi, le codage polaire est appliqué sur une séquence de bits particulière qui a été obtenue par combinaison des fragments de fichiers à destination des récepteurs faibles et éventuellement des récepteurs forts, cette séquence ayant la particularité de tenir compte des conditions de canal pour chacun des récepteurs de manière à optimiser les débits de réception des fragments de fichier.

Selon le premier mode de réalisation tel que décrit en référence à lafigure 3, la séquence finale W_G,b,finalcorrespond à la séquence de bits W_G,bobtenue par regroupement (ou répartition), remplissage puis combinaison (X-OR) des fragments de fichiers incluant notamment W₁ ², W₂ ¹destinés respectivement aux premier R₁et deuxième R₂récepteurs.

Selon l'exemple détaillé de lafigure 7, la séquence finale W_G,b,finalcorrespond à la séquence de bits obtenue par concaténation de la séquence de bits W_G,b et de la séquence de bits W_j,b(G), de sorte que W_G,final=[W_G,b| W_j,b(G)].

Comme illustré sur lafigure 5, le nœud source (ou émetteur) T est configuré pour mettre en œuvre un dispositif de codage de canal 20 de manière à coder la séquence de bits à émettre telle que décrite ci-dessus. Chaque récepteur R_iest configuré pour mettre en œuvre un dispositif de décodage de canal 40 de manière à décoder la séquences de bits reçue de l'émetteur T après transmission à travers le canal. Par exemple, le dispositif de codage 20 et le dispositif de décodage 40 sont configurés pour appliquer une technique de codage et décodage basée sur le même code polaire, ce code pouvant être sélectionné parmi une liste de codes préinstallés.

Selon une particularité de l'invention, le dispositif de codage de canal 20 est configuré de telle sorte que le premier bit de la séquence finale W_G,b,finalest codé par le premier bit le plus fiable dans le code polaire u₁tandis que le second bit de la séquence concaténée W_G,b,finalest codé par le second bit le plus fiable dans le code polaire u₂, et ainsi de suite pour lesm _j bits de la séquence fournis en entrée du codeur, où l'indice j indique le récepteur fort choisi lors de l’étape E8 décrite auparavant.

Si aucun récepteur fort n’a été choisi lors de l’étape E8, la séquence concaténée W_G,b,finalest de longueur m_Gbits. Pour déterminer la fiabilité des bits (ou bits variés) du codage de canal, on peut se baser sur des algorithmes standards, qui ordonnent les bits par exemple par ordre croissant de leur paramètre Z. Par exemple, l’ordonnancement des bits d’entrées du code polaire peut être stocké sous la forme d'une base de données 4 dans une mémoire du récepteur.

Ainsi, selon l'exemple de lafigure 5, les bits d'information de la séquence finale W_G,b,finalsont agencés par ordre croissant de probabilités d'erreur au moyen d'un module d'ordonnancement 20.1 adapté à fournir en entrée du codeur de canal 20.3 une séquence de bits u₁, u₂, u₃, u₄, u₅ordonnés par ordre croissant de leur erreur de probabilité. Par exemple, les probabilités d'erreur auxquelles le module d'ordonnancement a accès sont stockées sous la forme d'une base de données 2.

De manière générale, le code utilisé pour le codage de canal a une taille optimale égale àn, oùndésigne un entier naturel non nul. Le codeur de canal 20.3 dispose au total denentrées et par conséquent est capable de coder au plusnbits simultanément.

Dans l'exemple de lafigure 5, on suppose que le codeur de canal 20.3 est configuré avec un code de taille n=8 mais que seuls m₃=5 bits d'informations sont codés, où 5=n × C_3,selon le scénario de la figure 2. De manière générale, on rappelle qu'un récepteur R_kpeut décoder m_kbits simultanément de façon fiable,i.e.avec probabilité d’erreur très faible.

Lors de l'étape de codage de canal E9, le codeur de canal 20.3 de l'émetteur T applique un code polaire à la séquence de bits ordonnés {u₁, u₂, u₃, u₄, u₅} de manière à obtenir une séquence de bits codés par codage polaire {x₁, x₂, x₃, x₄, x_5,x_{6 ,}x_7,x₈}. Dans cet exemple, les trois derniers bits u₆, u₇, u₈de la séquence ordonnée fournie en entrée du codeur de canal 20.3 sont fixés à une valeur de référence, connue par tout le monde, en générale fixée à “0”. Seuls les cinq premiers bits u₁, u₂, u₃, u₄, u₅ sont des bits d'information tandis que les trois derniers bits u₆, u₇, u₈ sont des bits gelés (ditsfrozen bitsen anglais), par exemple de valeur égale à "0".

Ainsi, pour communiquer avec un récepteur de capacité C_k, les bits sont répartis en deux groupes : i) un groupe de m_k<n*C_kbits d'information destinés à être décodés par le récepteur et ii) un groupe de n-m_kbits gelés, fixés par défaut à une valeur connue par tout le monde (typiquement “0”).

Lors d'une étape d'émission E11, l'émetteur T envoie à travers le réseau la séquence de bits codés {x₁, x₂, x₃, x₄, x_5,x_6,x_7,x₈} à l'ensemble des récepteurs, par exemple, dans un même paquet de données transmis à travers un réseau 4G ou 5G. Le nombre et la valeur des bits gelés peuvent être également transmis par l'émetteur T aux récepteurs, par exemple lors de cette étape d'émission E11 ou bien peuvent être calculés par chaque récepteur comme décrit ci-après.

En pratique, l'émetteur envoie les données sous la forme d'un paquet comprenant une entête et un champs de données. Le champ de données comprend la séquences de bits codés. L'entête comprend des indices permettant d'identifier les blocs de fragments de fichiers codés et les récepteurs auxquels ils sont destinés.

Par exemple, l'entête comprend les indices i appartenant à l'ensemble {i₁,…,i_t} désignant les récepteurs faibles du sous-ensemble G pour lesquels b_i≥b, les indices {d_i,b,1,...,d_i,b,qi} associés à ces récepteurs des blocs des fragments de fichiers codés dans le champ de données du paquet. L'entête comprend en outre les indices désignant les récepteurs forts R_j, tel que L+1≤j≤K, ainsi que les indices {d_j,b,1,...,d_j,b,zb} associés à leurs blocs des fragments de fichiers codés dans le champ de données du paquet.

Selon l'exemple de la figure 7, l'émetteur T envoie, lors de l'étape d'émission E13, les fragments du fichier W_jrestants à destination des récepteurs forts R_joù L+1≤j≤K.

Après transmission sur le canal C_i, la séquence de bits codés est reçue par le récepteur R_i. On suppose que la séquence reçue est Y_i={y₁, y₂, y₃, y₄, y_5,y_6,y_7,y₈} et que le récepteur connaît le nombre et la valeur des bits gelés. Dans l'exemple de la figure 5, le récepteur détermine que les trois derniers bits de la séquence reçue sont des bits nuls (i.e.y₆=y₇=y₈=0).

Le procédé de décodage mis en œuvre par un récepteur faible va maintenant être décrit selon un mode de réalisation particulier tel qu'illustré à lafigure 9.

Lors d'une étape de réception E20, le récepteur R_kreçoit un paquet de données correspondant au paquet émis par l'émetteur T après transmission sur le canal. Le paquet reçu comprend un entête et un champ de données, comme pour le paquet émis tel que décrit ci-dessus. Le champ de données du paquet reçu comprend la séquence Y_i.

Sur réception du paquet, chaque récepteur faible R_k(1≤k≤L) détermine lors d'une étape de test E21 si ce paquet le concerne. A cet effet, le récepteur R_kextrait les indices des récepteurs du sous-ensemble G, les indices des récepteurs forts R_j(L+1≤j≤K) et les indices de blocs de fragments de fichiers associés à ces récepteurs,i.e.respectivement {d_i,b,1, ..., d_i,b,qi} et {d_j,b,1,...,d_j,b,zb} tels que définis précédemment. Si le récepteur R_kn'appartient pas au groupe G, le paquet reçu est ignoré. Sinon, il procède aux étapes suivantes.

Lors d'une première étape d'extraction E22, le récepteur R_kextrait de sa mémoire cache M_k, les blocs des fragments de fichiers désignés W_j,b(G) et destinés aux récepteurs forts R_j. Plus précisément, il extrait les fragments de fichiers associés aux indices d_j,b,1,...,d_j,b,zb.

Lors d'une deuxième étape d'extraction E23, le récepteur R_kextrait de sa mémoire cache M_k, les blocs des fragments de fichiers désignés W_i,b(G\{i}), pour tout indice i tel que le récepteur R_iappartenant à G\{k} et pour tout indice b appartenant à l'ensemble {1,…, b_i},i.e., tous les contenus numériques de sa propre mémoire cache qui sont exclusivement stockés aussi dans les mémoires caches de |G|-1 autres récepteurs appartenant au groupe G. Pour chaque indice i, les fragments de fichiers spécifiques à retirer sont désignés par les indices {d_i,b,1,...,d_i,b,qi}.

On notera que les première et deuxième étapes d'extraction E22 et E23 peuvent être exécutées simultanément ou bien séquentiellement dans n'importe quel ordre.

Par exemple, dans le cadre du scénario de lafigure 2, le premier récepteur R₁extrait de sa mémoire cache M₁les fragments W₁ ¹, W₂ ¹, W₃ ¹, W₁ ³, W₂ ³, W₃ ³tandis que le deuxième récepteur R₂extrait de sa mémoire cache M₂les fragments W₁ ², W₂ ², W₃ ², W₁ ³, W₂ ³, W₃ ³.

Lors d'une étape de combinaison E24, les fragments de fichiers extraits à l'issue de la deuxième étape d'extraction E23 sont combinés par addition binaire en appliquant l'opérateur OU exclusif (X-OR), de manière à obtenir une séquence de bits combinés W_k,b,XOR(G)=_{i  G\{k}}W_i,b(G\{k}).

A cet effet, ces blocs sont préalablement complétés lors d'une sous-étape de remplissage (non illustrée) par des bits nuls "0", de sorte que chacun de ces blocs soit de taille égale à la capacité de décodage maximale des récepteurs faibles appartenant au groupe G, cette capacité étant désignée m_G=Max(m_i)_{i  G}et pouvant être transmise à l'ensemble des récepteurs, par exemple dans l'entête du paquet.

Lors d'une étape de sélection E26, le récepteur R_ksélectionne les m_kpremiers bits de la séquence combinée de manière à former une séquence combinée d'information W_k,b,XOR,data, les bits restant de la séquence combinée formant une séquence de bits gelés W_{k,b,XOR,frozen .}Ainsi, la séquence de bits combinés W_k,b,XOR(G) est divisée en deux sous-ensembles de bits en fonction de la capacité de décodage m_kdu récepteur R_k: un premier sous-ensemble de bits d'information W_k,b,XOR,datacomprenant les m_kpremiers bits de la séquence de bits combinés W_k,b,XOR(G) et deuxième sous-ensemble de bits gelés (frozen bits) noté W_{k,b,XOR , frozen}comprenant les bits restants de la séquence de bits combinés W_k,b,XOR(G).

Le deuxième sous-ensemble W_{k,b,XOR , frozen}est ensuite concaténé à la séquence W_j,b(G) de manière à former une séquence finale de bits gelés : W_F=[W_{k,b,XOR , frozen}| W_j,b(G)] qui servira à décoder la séquence de bits reçus comme décrit ci-dessous.

Lors d'une étape de décodage de canal E28, le premier sous-ensemble W_k,b,XOR,dataest décodé par le décodeur de canal 40 du récepteur R_ken utilisant le même code (de préférence polaire) que celui utilisé par l'émetteur lors de l'étape de codage E9 et la séquence finale de bits gelés W_F. A l'issue de l'étape de décodage de canal E28, une séquence binaire décodée X_kest fournie en sortie du décodeur de canal du récepteur R_k.

Lors d'une étape de combinaison E30, le récepteur R_kcombine la séquence binaire décodée X_ket la séquence combinée d'information W_k,b,XOR,dataen appliquant l'opérateur OU exclusif (X-OR), ce qui a pour effet d'obtenir les fragments de fichiers requis par le récepteur R_kdénotés W_k,b(G\{k})=X_k W_k,b,XOR,data(G).

Lafigure 10illustre de manière schématique les différentes séquences binaires formées successivement lors du décodage selon le procédé décrit ci-avant pour l'obtention des fragments de fichiers W_k,b(G\{k}) requis par le récepteur R_ken utilisant la séquence de bits reçus Y_k, les fragments de fichiers W_i,b(G\{k}) contenus dans la mémoire cache M_k.

Lafigure 11illustre le débit en Mbit/s mesuré en fonction de la taille de la mémoire cache des récepteurs obtenu par le procédé selon l'invention utilisant un codage polaire en comparaison avec un procédé de codage classique. Les mesures ont été réalisées dans un système de diffusion comprenant 20 récepteurs où le canal de transmission vers chaque récepteur R_kest un canal binaire symétrique (BSC :Binary Symmetric Channelen anglais) avec une probabilité de croisement (crossover probabilityen anglais) égale à δ_k. Les mesures ont été effectuées dans le cas où le système comprend 10 récepteurs disposent d'une mémoire cache et ont une même probabilité de croisement δ=0,2431 tandis que les 10 autres récepteurs ne disposent pas de mémoire cache et ont une même probabilité de croisement δ'=0,0311. Ces résultats montrent notamment que pour une taille de mémoire cache donnée, le débit des données reçues selon le procédé de codage/décode selon l'invention est systématiquement plus élevé qu'avec le procédé de codage/décodage classique.

Le procédé de multidiffusion selon l'invention est mis en œuvre sur un dispositif d'émission appartenant à un réseau de communication tel qu'un réseau radiofréquence de type Wi-Fi (IEEE 802.11) ou un radio-mobile de type 4G ou 5G, et adapté à transmettre des données numériques.

De préférence, le dispositif d'émission est constitué par un point d'accès radio ou une station de base relié à un serveur de fichiers comprenant des moyens de stockage des fichiers destinés à être diffusés.

Le procédé d'obtention selon l'invention est mis en œuvre sur un dispositif de réception appartenant audit réseau de communication et à adapter à recevoir et décoder les fragments de fichiers émis par le dispositif d'émission.

De préférence, le dispositif de réception est constitué par un terminal mobile sélectionné parmi un ordinateur portable, un téléphone portable de typesmartphone, une tablette, un objet connecté ou tout autre dispositif comprenant des moyens de réception, des moyens de stockage et des moyens de traitement pour décoder la séquence de bits reçue en provenance du dispositif d'émission.

Dans le cas où le réseau de communication comprend une pluralité de nœuds de communication selon une architecture de type pair à pair (oupeer - to-peeren anglais), où chaque nœud du réseau peut jouer tour à tour le rôle d'émetteur et de récepteur. Dans ce cas, chaque nœud est adapté à mettre en œuvre les étapes du procédé de multidiffusion lorsqu'il joue le rôle d'émetteur et les étapes du procédé d'obtention lorsqu'il joue le rôle de récepteur.

Lafigure 12est un bloc-diagramme schématique d'un dispositif de traitement de l’information 4.0 pour la mise en œuvre d'un ou plusieurs modes de réalisation de l'invention. Le dispositif 4.0 de traitement de l’information peut être un périphérique tel qu'un micro-ordinateur, un poste de travail ou d'un terminal mobile de télécommunication. Le dispositif 4.0 comporte un bus de communication connecté à:

- une unité centrale de traitement 4.1, tel qu'un microprocesseur, notée CPU ;

- une mémoire à accès aléatoire 4.2, notée RAM, pour mémoriser le code exécutable du procédé de réalisation de l'invention ainsi que les registres adaptés à enregistrer des variables et des paramètres nécessaires pour la mise en œuvre du procédé de multidiffusion et/ou du procédé d'obtention selon des modes de réalisation de l'invention, la capacité de mémoire de celui-ci peut être complété par une mémoire RAM optionnelle connectée à un port d'extension, par exemple ;

- une mémoire morte 4.3, notée ROM, pour stocker des programmes informatiques pour la mise en œuvre des modes de réalisation de l'invention ;

- une interface réseau 4.4 est normalement connectée à un réseau de communication sur lequel des données numériques à traiter sont transmis ou reçus. L'interface réseau 4.4 peut être une seule interface réseau, ou composée d'un ensemble d'interfaces réseau différentes (par exemple filaire et sans fil, interfaces ou différents types d'interfaces filaires ou sans fil). Des paquets de données sont envoyés sur l'interface réseau pour la transmission ou sont lues à partir de l'interface de réseau pour la réception sous le contrôle de l'application logiciel exécuté dans le processeur 4.1 ;

- une interface utilisateur 4.5 pour recevoir des entrées d'un utilisateur ou pour afficher des informations à un utilisateur ;

- un support de stockage optionnel 4.6 noté HD ;

- un module d’entrée/sortie 4.7 pour la réception / l'envoi de données depuis / vers des périphériques externes tels que disque dur, support de stockage amovible ou autres.

Le code exécutable peut être stocké dans une mémoire morte 4.3, sur le support de stockage 4.6 ou sur un support amovible numérique tel que par exemple un disque. Selon une variante, le code exécutable des programmes peuvent être reçu au moyen d'un réseau de communication, via l'interface réseau 4.4, afin d'être stocké dans l'un des moyens de stockage du dispositif de communication 4.0, tel que le support de stockage 4.6, avant d'être exécuté.

L'unité centrale de traitement 4.1 est adaptée pour commander et diriger l'exécution des instructions ou des portions de code logiciel du programme ou des programmes selon l'un des modes de réalisation de l'invention, instructions qui sont stockées dans l'un des moyens de stockage précités. Après la mise sous tension, le CPU 4.1 est capable d'exécuter des instructions stockées dans la mémoire RAM principale 4.2, relatives à une application logicielle, après que ces instructions aient été chargées de la ROM par exemple. Un tel logiciel, lorsqu'il est exécuté par le processeur 4.1, provoque les étapes des organigrammes présentés dans les figures 6, 7, 8 ou 9 pour être exécutées.

Dans ce mode de réalisation, l'appareil est un appareil programmable qui utilise un logiciel pour mettre en œuvre l'invention. Toutefois, à titre subsidiaire, la présente invention peut être mise en œuvre dans le matériel (par exemple, sous la forme d'un circuit intégré spécifique ou ASIC).

Naturellement, pour satisfaire des besoins spécifiques, une personne compétente dans le domaine de l’invention pourra appliquer des modifications dans la description précédente.

Bien que la présente invention ait été décrite ci-dessus en référence à des modes de réalisation spécifiques, la présente invention n'est pas limitée aux modes de réalisation spécifiques, et les modifications qui se trouvent dans le champ d'application de la présente invention seront évidentes pour une personne versée dans l'art.

Claims (12)

1. Procédé de multidiffusion de fragments manquants (W_k ^p; W₁ ², W₂ ², W₃ ²) de fichiers numériques (W_k ; W₁, W₂, W₃) à un ensemble de récepteurs comprenant une pluralité de récepteurs faibles (R_i; R₁,...,R_L; R₁, R₂, R₃) comprenant chacun une mémoire cache (M_i; M₁,...,M_L; M₁, M₂, M₃) dans laquelle sont stockés un ou plusieurs fragments de fichiers numériques pré-stockés (W₁ ¹, W₂ ¹, W₃ ¹W₁ ³, W₂ ³, W₃ ³; W₁ ², W₂ ², W₃ ², W₁ ³, W₂ ³, W₃ ³), les fragments manquants (W_k ^p; W₁ ², W₂ ¹, W₃ ²) de fichiers destinés à être diffusés n'étant pas préalablement stockés dans la mémoire cache des récepteurs respectifs (R_i; R₁,...,R_L; R₁, R₂) requérant ces fichiers, ledit procédé étant caractérisé en ce qu'il comprenant les étapes suivantes :

   1. sélection (E1) d'un sous-ensemble (G) de récepteurs faibles ;
   2. pour chaque récepteur (R_i; R₁, R₂) dudit sous-ensemble (G), identification (E3) d'au moins un fragment (W_i ^p; W₁ ²; W₂ ¹) d'un fichier (W_i; W₁; W₂) requis par ledit chaque récepteur et tel que ledit au moins un fragment (W₁ ²; W₂ ¹) est présent dans la mémoire cache (M₁; M₂) de tous les autres récepteurs faibles (R₁, R₂) appartenant audit sous-ensemble (G);
   3. pour chaque récepteur (R_i; R₁, R₂) dudit sous-ensemble (G) et pour chacun dudit au moins un fragment de fichier (W_i ^p; W₁ ²; W₂ ¹) identifié lors de l'étape précédente, regroupement/répartition (E5) dudit au moins un fragment du fichier en une pluralité de blocs b de taille m_iégale à la capacité de décodage dudit récepteur (R_i; R₁, R₂) ;
   4. combinaison (E7) des blocs issus de l'étape c) de manière à fournir une séquence de bits combinés W_G,b;
   5. codage (E9) d'une séquence de bits à transmettre comprenant la séquence de bits combinés W_G,b, par application d'une technique de codage, de manière à fournir une séquence de bits codés W_c; et
   6. envoi (E11) de ladite séquence de bits codés W_cà un ensemble de récepteurs comprenant le sous-ensemble (G) de récepteurs faibles.
2. Procédé selon la revendication 1, caractérisé en ce que chacun desdits blocs obtenus lors de l'étape c) est rempli par des bits "0" lors d'une étape de remplissage (E4) de sorte que la taille du bloc soit égale à la capacité de décodage maximale m_Gdes récepteurs faibles du sous-ensemble G.
3. Procédé selon l'une quelconque des revendications 1 à 2, caractérisé en ce que l'étape de combinaison (E7) est mise en œuvre par application de l'opérateur logique OU exclusif (X-OR).
4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que la technique de codage utilisée lors de l'étape de codage (E9) est une technique de codage polaire configurée pour recevoir en entrée les bits de ladite séquence de bits à transmettre.
5. Procédé selon la revendication 4, caractérisé en ce que l'étape de codage (E9) comprend une sous-étape d'ordonnancement (E9.1), lors de laquelle les bits de la séquence de bits à transmettre sont agencés par ordre croissant de leur probabilité d'erreur avant l'application de la technique de codage.
6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il comprend en outre les étapes suivantes :
   - sélection (E8) d'au moins un récepteur fort (R_j) parmi ledit ensemble de récepteurs (R₁,...,R_K), ledit au moins un récepteur fort ne disposant pas de mémoire cache et requérant un fragment de fichier W_j,b(G) contenu dans les mémoires cache de récepteurs faibles (R₁,...,R_L) du sous-ensemble G;
   - concaténation (E8.1) de la séquence de bits combinés W_G,b avec le fragment de fichier W_j,b(G) de manière à former la séquence de données à transmettre destinée à être codée lors de l'étape de codage (E9).
7. Procédé d'obtention d'au moins un fragment de fichier à partir d'une séquence de bits reçue (Y_k) correspondant à la séquence de bits codés (W_c) émise par un émetteur conformément au procédé de multidiffusion selon l'une quelconque des revendications 1 à 6 et transmise à travers un canal de transmission, ledit procédé d'obtention étant caractérisé en ce qu'il comprend, pour chaque récepteur faible R_kappartenant au sous-ensemble G, les étapes suivantes:
   réception (E20) de ladite séquence de bits reçue (Y_k) ;
   combinaison (E24) des fragments de fichiers destinés aux autres récepteurs faibles appartenant au sous-ensemble G, ces fragments étant stockés dans la mémoire cache M_kdu récepteur faible R_kde manière à obtenir une séquence combinée W_k,b,XOR(G);
   sélection (E26) des m_kpremiers bits de ladite séquence combinée W_k,b,XOR(G), de manière à former une séquence combinée d'information W_k,b,XOR,data, les bits restant de la séquence combinée formant une séquence de bits gelés W_{k,b,XOR,frozen} ;
   décodage de canal (E28) des m_kpremiers bits de la séquence de bits reçue en utilisant la séquence de bits gelés W_{k,b,XOR,frozen} de manière à former une séquence de bits décodés X_k, le décodage étant basé sur un code utilisé par l'émetteur T lors de l'étape de codage (E9) ;
   combinaison (E30) de la séquence combinée d'information W_k,b,XOR,dataet de la séquence de bits décodée X_kde manière à obtenir les fragments de fichiers W_k,b(G\{k}) requis par le récepteur R_k.
8. Procédé de communication mis en œuvre dans un réseau comprenant une pluralité de nœuds de communication, ledit procédé étant caractérisé en ce qu'il comprend les étapes du procédé de multidiffusion selon l'une quelconque des revendications 1 à 6 et/ou les étapes du procédé d'obtention selon la revendication 7.
9. Dispositif de traitement de l’information comprenant des moyens pour mettre en œuvre les étapes du procédé de multidiffusion selon l'une quelconque des revendications 1 à 6 et/ou les étapes du procédé d'obtention selon la revendication 7.
10. Système de multidiffusion caractérisé en ce qu'il comprend au moins un serveur configuré pour mettre en œuvre les étapes du procédé de multidiffusion selon l'une quelconque des revendications 1 à 6 et une pluralité de dispositifs clients configurés pour mettre en œuvre les étapes du procédé d'obtention selon la revendication 7.
11. Programme d’ordinateur comprenant des instructions adaptées à mettre en œuvre chacune des étapes du procédé de multidiffusion selon l’une quelconque des revendications 1 à 6 et/ou les étapes du procédé d'obtention selon la revendication 7, lorsque ledit programme est exécuté sur un ordinateur.
12. Moyen de stockage d'informations, amovible ou non, partiellement ou totalement lisible par un ordinateur ou un microprocesseur comportant des instructions de code d'un programme d'ordinateur pour l'exécution de chacune des étapes du procédé de multidiffusion selon l'une quelconque des revendications 1 à 6 et/ou les étapes du procédé d'obtention selon la revendication 7.