Brevet FR2703544A1 — publié le 19941007

Procédé de réduction de la taille mémoire et du temps nécessaires à la correction des erreurs dans un réseau temporel asynchrone La présente invention concerne un procédé de réduction de la taille mémoire et du temps nécessaires à la correction des erreurs dans un réseau temporel asynchrone. Elle s'applique notamment à la protection de services audiovisuels distributifs et interactifs contre les erreurs bits et les pertes de cellules utiisant des réseaux temporels asynchrones. Dans ces réseaux1 les informations numériques sont transmises de façon discontinue sous forme de paquets, appelés "cellules d'informations" ou 'cellules ATM", ATM étant l'abréviation de "Asynchronous Transfer Mode" dans le langage anglo-saxon. Le mode de transmission consiste, au lieu d'émettre octet par octet, à constituer dans l'équipement terminal émetteur un paquet de bits au fur et à mesure de la création des données numériques, et à attendre d'avoir suffisamment d'informations pour constituer une cellule d'information complète pour envoyer celle-ci sur le réseau. En télévision numérique, ce mode de transmission est régi par les recommandations CCITT 1.361 et 1.363 qui définissent respectivement la couche d'adaptation ATM, quatre classes de services différenciées par leurs débits, leurs modes de connexion et les niveaux de relation temporelle entre émetteurs et récepteurs ainsi que quatre types d'adaptation utilisables dans chaque classe de service. Les transmissions audiovisuelles sont caractérisées par des débits d'information variant sur une large échelle: 64 Kbitls pour le visiophone basse qualité, 2 Mbitls pour la vidéo surveillance et le visiophone haute qualité, 8 Mbitls à 20 Mbitls pour la télévision standard et 30 à 140 Mbit/s pour la télévision haute définition.Ce dernier débit, associé aux contraintes de temps réel inhérentes à la transmission du signal vidéo interdisent la réémission des informations lorsque dans le train binaire transmis des erreurs sont détectées. Ce problème peut malgré tout, et dans de nombreux cas, être résolu en effectuant des masquages des informations erronées. Cependant la multiplicité des techniques de masquage temporel ou spatial employées en vidéo et la difficulté de réalisation de masquage sur le signal audio sont telles que la sensibilité admise aux erreurs de transmission, en termes d'erreurs résiduelles est très variable et évolue communément d'une erreur toutes les 10 minutes à une erreur toutes les 2 heures. Naturellement la solution à ces problèmes est d'autant plus délicate à trouver du fait du caractère parfaitement aléatoire de ces erreurs et du fait que celles-ci peuvent se présenter en paquets ou en rafales. Bien qu'il soit en principe possible de garantir des taux d'erreurs de 10-12 pour la TVHD, de 10-11 pour la télévision standard et 10-10 pour la vidéo surveillance à l'interface utilisateur-réseau en mettant en oeuvre différents codes de détection et correction d'erreurs tels que les codes Reed Solomon par exemple qui possèdent une puissance de correction très importante et une extrême simplicité de mise en oeuvre, ces codes ne permettent cependant pas de remédier au problème soulevé par la perte de cellules car celles-ci, de par leur format qui comporte classiquement 48 octets d'informations, demandent des codes correcteurs d'erreurs trop puissants et trop redondants pour permettre des corrections intracellules. La Recommandation 1.363 du CCITT propose une méthode pour pallier les inconvénients précités. Cette méthode est basée sur l'utilisation d'un code Reed-Solomon (128, 124) sur GF (256) et d'un entrelaceur d'ordre 47 et est dédiée à la distribution de signaux vidéo de débits supérieurs ou égaux à 10 Bits. Cette méthode présente cependant les inconvénients suivants: - un délai de traitement proportionnel à la taille de la mémoire d'entrelacement et inversement proportionnel au débit du service auquel elle s'applique At = (Taille mémoire entrelaceur) débit du service ce qui s'avère mal adapté aux services audiovisuels à faible débit, d'autant plus si ceux-ci sont interactifs (visiophonie) - la nécessité d'utiliser une mémoire de travail double de la taille de la matrice d'entrelacement (fonctionnement en flip-flop) - la mauvaise utilisation des capacités de correction des codes Reed Solomon due au choix fixe d'une profondeur d'entrelacement égale à la taille du bloc d'informations utiles de la cellule ATM, à savoir 47. Le but de l'invention est de pallier les inconvénients précités. A cet effet, I'invention a pour objet un procédé de correction contre les erreurs bits et les pertes de cellules pour services audiovisuels distributifs et interactifs dans un réseau temporel asynchrone consistant à protéger chaque symbole d'informations à transmettre sur le réseau par un code détecteur correcteur d'erreurs type Reed-Solomon, à effectuer un entrelacement des informations codées Reed-Solomon avant leur transmission en paquets ou cellules sur le réseau, à effectuer à la réception un désentrelacement des informations contenues dans les paquets ou cellules et à corriger les erreurs et les effacements dans les symboles restitués au moyen du code Reed-Solomon, caractérisé en ce que l'entrelacement consiste à mémoriser ligne par ligne les informations par mots de Reed Solomon de N symboles dans une mémoire d'entrelacement de capacité C1 (respectivement C2) \ et à lire ces informations diagonale par diagonale pour former les champs SAR-SDU des cellules ATM. L'originalité de l'invention consiste en la technique de lecture écriture de la matrice d'entrelacement qui permet de diviser par 2 le délai de traitement des données, à longueur de code N et profondeur d'entrelacement R égales et par environ 4 la taille mémoire nécessaire au mécanisme d'entrelacement. D'autres caractéristiques et avantages de l'invention apparaîtront ciaprès à la lumière de la description qui suit faite en regard des dessins annexés qui représentent: - La figure 1 les différentes étapes du procédé selon l'invention mises sous la forme d'un organigramme. - La figure 2 un schéma d'organisation d'un dispositif d'entrelacement permettant la mise en oeuvre du procédé selon la figure 1. - La figure 3 un schéma illustrant à l'aide d'un exemple simple la méthode d'entrelacement. - La figure 4 un schéma illustrant à l'aide d'un exemple simple la méthode de désentrelacement. - La figure 5 un schéma décrivant l'organisation de l'espace mémoire des dispositifs d'entrelacement et le désentrelacement des figures 3 et 4 ainsi que les séquences d'adressage de ces mémoires. - La figure 6 un schéma comparant les délais de traitement dans le cas d'un entrelacement classique et dans celui d'un entrelacement tel qu'il est décrit dans les figures 3 et 4. - La figure 7 un format de segmentation de cellules ATM, pour une adaptation de type 1 selon la recommandation 1.363 du CCITT. Le procédé de protection contre les erreurs et pertes de cellules ATM selon l'invention est illustré par les étapes 1 à 10 de la figure 1. Il consiste à l'étape 1 à convertir les symboles ou octets représentatifs du signal vidéo en mots de code Reed-Solomon de la façon décrite par exemple page 207 du livre de G. Cullmann ayant pour titre "Codes détecteurs et correcteurs d'erreurs" publié par DUNOD 1967 dans la collection "Initiation aux nouveautés de la science" ou encore de la façon décrite pages 304-308 du livre de Bernard Sklar intitulé "DIGITAL COMMUNICATIONS Fondamentals and Applications" publié par Prentice Hall 1988. Les informations codées obtenues sont des mots de code de longueur N en nombre de symboles et renfermant K symboles d'informations utiles. Le code est noté C(N,K,D) où D est la distance de Hamming. Ces informations sont entrelacées à l'étape 2 au moyen d'un dispositif d'entrelacement agencé suivant le schéma de principe de la figure 2. Suivant ce dispositif, les mots de N symboles sont mémorisés horizontalement dans la mémoire d'entrelacement d'une capacité égale à: C1 = aR(R+1) + b(b+1) 2 2 avec N = aR+b et b Le calcul de l'insertion de numéros de séquences qui est effectué à l'étape 3 conduit à une segmentation des cellules (SAR-PDU) suivant un format représenté à la figure 7 conforme à la recommandation CCITT 1.363. Ce format comporte 40 bits d'en-tête "Header", 384 bits de SAR-PDU dont 4 bits SN de numéro de séquence 4 bits SNP de protection de champ SN contre les erreurs et un champ de 376 bits d'informations formant une cellule 5 + 48 = 53 octets. La numérotation de séquence permet le repérage des cellules et une cellule perdue peut ainsi être détectée au récepteur et remplacée par une cellule "fantôme" dans le dispositif de désentrelacement. En réception le dépaquetage des cellules est effectué à l'étape 6. Les cellules sont restituées dans le format SAR-PDU de la figure 7 et une correction de la numérotation des séquences a lieu à l'étape 7 suivi à l'étape 8 d'une insertion éventuelle de paquets "fantômes" ou d'une destruction de paquets insérés. Un désentrelacement des cellules a alors lieu à l'étape 9 au moyen d'un dispositif de désentrelacement symétrique du dispositif de l'étape 2 utilisant une mémoire de désentrelacement de capacité: C2 = aR(R+ 1) + b(b-1) 2 2 +bR- 2 et qui consiste en l'écriture en diagonale des champs SAR-SDU des cellules reçues suivi de la lecture horizontale des mots de code Reed Solomon reconstitués. Ces codes sont ensuite analysés à l'étape 10 pour effectuer les corrections d'erreurs et d'effacements. Naturellement l'opération de désentrelacement de l'étape 9 doit être en synchronisme avec l'insertion des paquets fantômes et ou la destruction des paquets insérés de l'étape 8. Le procédé et le dispositif de l'invention qui viennent d'être décrits s'appliquent à des configurations de codes très différentes. Un exemple est présenté dans les figures 3 et 4 qui permet de comprendre l'originalité du dispositif d'entrelacement. Dans cet exemple les valeurs des différents paramètres sont volontairement faibles, ceci dans un souci de simplicité de présentation de la méthode. Si N est la longueur du code, R la profondeur d'entrelacement, L la longueur des paquets issus de la mémoire d'entrelacement et destinés à être transmis, on a choisi ici N=10, R = 4 et L = 5. Dans le cas des réseaux ATM, la longueur L du champ SAR SDU de la cellule ATM est égale à 47 et N et R peuvent être par exemple choisis respectivement égaux à 235 et 24. K, le nombre d'octets utilisés dans le mode de code Reed-Solomon et par conséquent D, distance de Hamming du code de Reed-Solomon ne modifient en rien le principe d'entrelacement. On rappelle que dans le cas où R R De façon formelle, en régime établi: - les mots de code successifs sont notés Mj = {i,j)}j=1 1 à N - les cellules successives à transmettre sont notées Ckl, I = 1 à N/L et Ckî = {k,l,m)}m=1 à L Au niveau de la mémoire d'entrelacement, les opérations sont les suivantes: Au codeur * étape 1: écriture de MI * étape 2 : lectures de CII pour I = 1 à N/L en utilisant les mots de code Mi pour i = I-R+1 ài * étape 3 : 1=1+1 et rebouclage à l'étape 1. Au décodeur * étape 1: écriture des Cki pour I = 1 à N/L * étape 2 : lecture de MK-R+1 en utilisant les cellules CkI pour k = K R+1 à K * étape 3: K = K+1 et rebouclage à l'étape 1. Au décodeur, comme au codeur pour avoir les Ck = {(k,l,m)} en fonction des M1 = {(i,j)}, et inversement, on a les relations (1) suivantes: j = (l-1)L+m, m Au codeur on cherche les (i,j) qui correspondent aux (k,l,m) pour constituer les cellules Ckl et au décodeur les (k11,m) qui correspondent aux (i,j) pour reconstruire les mots de code RS, Mi. Dans notre exemple, en régime établi au codeur: on écrit M4 = {(4,1)(4,2)... (4,10)} on lit C41 {(4, 1, 1) ... (4, 1, 5)} et C42 = {(4, 2, 1)... (4, 2, 5)} on écrit M5, on lit C51 et C52, etc... Pour lire C41 et C42 on utilise M1, M2, M3, M4. On a alors conformément aux équations (1) qui deviennent: j = 5(1-1)+m, L pour C41: (4,1,1) = (4,1) pour C42: (4,2,1) = (3,6) (4,1,2)=(3,2) (4,2,2)=(2,7) (4,1,3)=(2,3) (4,2,3)=(1,8) (4,1,4) = (1,4) (4,2,4) = (4,9) (4,1,5)=(4,5) (4,2,5)=(3,10) Les figures 4 et 5 illustrent ces calculs. Dans la pratique, il suffit de choisir une taille de mémoire d'entrelacement égale à C1 (respectivement C2) et une taille de mémoire de désentrelacement égale à C2 (respectivement C1), avec C1 et C2 définis comme précédemment, soit au total entre codeur et décodeur une taille mémoire égale à: C=C1+C2= N(R+1) Les valeurs habituelles de N et R donnent une taille de mémoire d'entrelacement égale environ à la moitié de celle utilisée actuellement. Quelques exemples sont donnés dans le tableau ci-dessous. Code N R a b Taille mémoire Taille mémoire Gain méthode classique nouvelle méthode RS(235,227)x24 235 24 9 19 11280 5875 +1,92 RS(128,127)x47 128 47 22 34 12032 6144 +1,96 RS(235,219)x6 235 6 39 1 2820 1645 .1,71 La taille est donnée en octets et correspond à la taille mémoire codeur+décodeur. D'autre part, grâce au principe de lecture écriture en continu il n'est plus nécessaire d'attendre l'écriture complète de la matrice avant de commencer la lecture. Le principe du "flip-flop" n'est plus nécessaire avec cette gestion dynamique. La taille de la mémoire d'entrelacement et de désentrelacement se trouve divisée une nouvelle fois par 2. Globalement le gain est une division par 4 de la mémoire. Rigoureusement la taille mémoire est divisée par R =4(R+1) En ce qui concerne le temps de traitement, I'observation des figures 3, 4 et 6 permet de constater qu'il est divisé par 2 par rapport à la méthode classique. Ce temps de traitement dans les mémoires d'entrelacement correspond à la différence entre l'instant où le mot de code Mi est extrait du désentrelacement et l'instant où il avait été écrit dans l'entrelaceur. At = KR/D au lieu deAt = 2KR/D dans le cas classique avec D le débit des informations utiles avant l'entrée dans le codeur Reed-Solomon. Cette méthode nécessite une gestion dynamique de la mémoire plus complexe. En pratique les choses se passent de la façon suivante, par exemple au codeur: on écrit le mot de code Mi, on lit les cellules Ci1, Ci2, Ci N/L, puis on écrit le mot de code Mi+1, puis on lit les cellules Ci+1,1, Cj+1,2 ... Ci+1,N/L, etc. Au niveau de la mémoire, après la lecture des N/L cellules, le mot de code RS suivant est écrit dans la mémoire à l'emplacement laissé libre par les cellules lues. En opérant de la sorte on constate facilement que le pointeur d'adressage de la mémoire pour les opérations de lecture-écriture décrit une suite de façon cyclique. Ce cycle est d'ailleurs très long (= R * PPCM (R, R-1, R-2, ..., 1)). La suite des adresses n'est par contre pas faite au hasard. Si l'on représente la mémoire en pages correspondant chacune à une colonne de notre entrelaceur et en lignes au sein de chaque page correspondant aux cases de chaque colonne i: Dans notre exemple on a 10 pages qui ont respectivement 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, lignes au codeur et 4, 3, 2, 1, 4, 3, 2, 1, 4 et 3 lignes au décodeur. De manière générale la page i a un nombre de lignes égal à: au codeur et égal à au décodeur, où E(a) est la partie entière de a. La séquence d'adresse de lecture-écriture de la mémoire est donc la suivante: * lecture puis écriture de la ligne jj de la page i * i = i+1 modulo N, nombre de pages *ji = jj + 1 modulo le nombre de lignes dans la page La figure 5 décrit l'organisation de la mémoire et le séquencement des adresses sur l'exemple traité dans les figures 3 et 4. REVENDICATIONS 1. Procédé de protection contre les erreurs bits et les pertes de cellules dans un réseau temporel asynchrone pour services audiovisuels consistant à protéger (1) chaque symbole d'informations à transmettre sur le réseau par un code détecteur correcteur d'erreurs type Reed-Solomon, à effectuer (2) un entrelacement des informations codées Reed-Solomon avant leur transmission en paquets ou cellules sur le réseau, à effectuer à la réception un désentrelacement (9) des informations contenues dans les paquets ou cellules et à corriger (10) les erreurs et les effacements dans les symboles restitués au moyen du code Reed-Solomon, caractérisé en ce que l'entrelacement consiste à mémoriser ligne par ligne les informations par mots de Reed-Solomon de N symboles dans une mémoire d'entrelacement de capacité C1 et à lire ces informations diagonale par diagonale pour former les champs SAR-SDU des cellules ATM. 2. Procédé selon la revendication 1 caractérisé en ce que le désentrelacement consiste à mémoriser diagonale par diagonale les champs SAR-SDU des cellules ATM dans une mémoire de désentrelacement de capacité C2 et à lire ces informations ligne par ligne pour reformer les mots de code de Reed-Solomon du procédé 2. 3. Procédé selon les revendications 1 et 2 caractérisé en ce que C1+C2 = N (R+1) avec C1 = aR(R+1) b(b+1) et C2 = aR(R+1) + bR- b(b-1) où N= aR+b et b 2 2 2 2 où R est la profondeur d'entrelacement et où a et b sont respectivement le quotient et le reste de la division euclidienne de N par R. 4. Procédé selon l'une quelconque des revendications 1 à 3 caractérisé en ce que les codes Reed-Solomon sont des codes RS (N, K, D) de longueur de code (N), d'informations utiles (K) et de distance de Hamming (D). 5. Procédé selon l'une quelconque des revendications 1 à 4 caractérisé en ce qu'il consiste à utiliser la capacité de correction des effacements. 6. Procédé selon les revendications 1 à 5 caractérisé en ce qu'il consiste à choisir une profondeur d'entrelacement R inférieure ou égale à la longueur L = 47 du champ SAR-SDU de la cellule ATM. 7. Procédé selon l'une quelconque des revendications 1 à 6 caractérisé en ce que chaque symbole d'information a la dimension d'un octet. 8. Procédé selon l'une quelconque des revendications 1 à 7 caractérisé en ce qu'il consiste à insérer des cellules fantômes dans un tableau de désentrelacement en marquant chaque octet pour qu'il soit interprété comme un effacement par le décodage Reed-Solomon.