Brevet FR2373192A1 — publié le 19780630

L'invention se rapporte aux procédés de codage-décodage detinés la diffi.slon de données numériques émises par une source d d'information sous la forme d'une séquence de bits. Un véhicule de l'information approprié à transmission ou à la memorisation d'une grandeur analogique est utilisé et le code revenu permet d'assurer la correction des erreurs affectant ladite grandeur analogique. Les erreurs introduites par un canal de transmission ou un système de mémorisation peuvent être classées en deux catégories - des erreurs aléatoires : il s'agit du bruit qui peut être du bruit gaussien, c'est-à-dire dont la répartition obéit à une loi gaussienne, ou bien du bruit impulsionnel caractérisé par de longs intervalles de temps sans pertubation, suivis de salves provoquant des erreurs sur un certain nombre de valeurs consé cutives ; - des erreurs non aléatoires et par conséquent systématiques, par exemple les non linéarités, les distorsions, etc... Chaque type d'erreur nécessite des moyens de détection, et éventuellement de correction, différents. Les procédés de codage permettent de corriger l'une ou l'autre des formes de bruit. On peut également prévoir en vue de la correction, des moyens de détection des erreurs systématiques. Dans la mise en oeuvre d'un procédé de codage-décodage avec correction d'erreurs, un système de codage groupe les données numériques en blocs de k bits consécutifs, auxquels sont ajoutés un certain nombre de bits de parité qui introduisent une redondance de l'information à des fins de détection et éventuellement de correction d'erreurs. Les bits de parité sont pris en canpte par un organe logique pour chaque bloc en fonction des k bits d'information. Les blocs obtenus, comprenant n bits, sont ensuite transformés en grandeurs analogiques. Lors de la réception, les blocs de n bits sont restitués.Certains de ces bits sont eventuellement différents des bits émis. ü circuit de décision, recevant à la fois les bits d'information et les bits de parité, corrige les erreurs et émet en sortie les bits d'information, avec un taux d'erreur qui dépend de la redondance du code choisi et de la répartition de probabilité des différents types d'erreurs. Ces procédés nécessitent de découper l'information en blocs Chaque bloc est ensuite traité, code, transmis ou mémorisé, décodé, corrigé séparément, ce qui pellt ne pas tomber en accord avec la morphologie du signal à diffuser. Plus le taux d'erreurs introduites par le véhicule d'information est élevé et plus on désire le réduire, plus la redondance à prévoir doit être importante, c'est-à-dire le rapport k élevé. k Ceci peut nécessiter dans certains cas des blocs contenant un grand nombre de bits et de algorithmes compliqués. Le temps de décodage limite le débit maximal des données émises. Par ailleurs, le nombre n de bits pouvant être codés sur une meme valeur analogique est limité par le rapport signal sur bruit R du canal ou du système de mémorisation analogique. En effet, le rapport signal R sur bruit R' affectant les données numériques est égal à 2n - 1 Le procédé de codage-décodage selon l'invention vise à pallier les inconvénients du découpage par blocs en appliquant sur chaque bit émis les opérations de codage et de décodage : le dédiit des grandeurs analogiques obtenues après le codage est égal au débit drémission des bits par la source.En d'autres termes, à chaque bit d'information est associée une grandeur analogique k = 1. Les bits de parité sont obtenus de façon très simple puisqu ils sont la répétition de n - î bits précédemment émis. I1 n'est donc pas besoin d'organe logique de codage, mais seulement de mémoires. Lors de la conversion des grandeurs analogiques en groupes de bits, il est possible d'utiliser la connaissance préalable de n - 1 de ces bits pour obtenir le dernier bit inconnu avec une incertitude molndre. La simplicité de l'algorithme ce incision et de correction conduit à des temps de décodage très courts, ce qui permet un débit d'émission élevé. L'utilisa tion-d'êléments simples, comme de mémoires programmables permet notamment de modifier l'algorithme de correction en changeant seulement un élément. Le procédé de codage-décodage selon l'invention est part cullèrement adapté à la correction des erreurs de bruit gaussien. Une variante du procédé permet de corriger les erreurs de salves. Enfin, une détection de validité peut-être prévue, afin de débecter, de façon certaine, certains types d'erreurs systématiques invention vise également des dispositifs de diffusion mettant en oeuvre ledit procédé. D'autres caractéristiques et avantages de invention apparaîtront au moyen de 13 description ci-après et des figures annexées parmi lesquelles - la figure 1 est un schéma générai d'un système de diffusion ; - les figures 2, 3 et 4 sont des schémas de détail du codeur selon l'invention ; - la figure 5 est un schéma explicatif du codage - les figures 6, 7 et 8 sont des schémas de détail du décodeur selon l'invention. La figure 1 représente le schéma général de tout système de transmission de données numériques mises sous forme analogique avec correction d'erreurs. Des données numériques arrivent en A sous la forme de bits successifs. Les données sont traitées dans un organe logique 1 que nous appellerons codeur série-parallèle qui groupe les bits, introduit la redondance, et délivre en B n bits en parallèle. Les n bits sont transformés en une grandeur analogique présente en C par un convertisseur numérique-analogique. Les grandeurs analogiques sont transmises par un canal 3 auquel on suppose associé une source de bruit, de sortie q 'à la sortie, en D, on ne trouve pas toujours les mêles valeurs qu'en C. Les grandeurs analogiques reçues sont transformees en groupe de bits formant un ensemble redondant par un organe logique 9 que nous appellerons décodeur. Un organe de décision 5 détermine à partir de tous les bits reçus, ceux qui ont la plus grarlde probabilité d'être@égaux aux bits émis en A. Les systèmes de mémorisation fonctionnent de façon semblable. A la place du canal 3, on a un dispositif d'enregistrement sur un support de signaux analogiques à 2n niveaux et un dispositif de lecture du support délivrant des signaux analogiques. Les opérations de codage et enregistrement d'une part, de lecture, décodage et correction d'autre part s'effectuent alors avec un décalage dans le temps. Dans la suite de la description, tout ce qui traite des systèmes de transmission pourra être appliqué aux systèmes de mémorisation. Les figures 2, 3 et 4 précisent le schéma général. de la figure 1 dans le cadre de l'invention. Sur la figure 2 est représenté le schema général du codeur série-parallèle 2 selon l'invention. Les bits arrivant en A sont mémorisés pendant un certain temps par une mémoire tampon 10. N bits successifs étant conservés en mémoire, on affecte à chaque'bit b arrivant en A un indice i selon l'ordre chronologique, i étant un entier crois- sant, lorsque le bit appele bi arrive en A, la mémoire 10 conser- ve les bits b. N à bi-1 Un élément logique 11 que nous appellerons portier commandé par des signaux logiques générés par un générateur d'adresse 12 sélectionne n bits, n étant un entier inférieur ou égal à N se trouvant à des adresses prédéterminées de la mémoire 10. L'avance des bits dans la mémoire et la générationdes adresses sont en synchronisme avec le flux des bits arrivant en A grâce à une horloge fonctionnant à la fréquence f. A la sortie du compteur, en B, on dispose de blocs de n bits, émis sur n voies B1 à Bn à la fréquence f. Ces n bits sont destinés à être conver@is en une valeur analogique par le convertisseeur 2 selon un code connu, par exemple le code binaire-décimal, ou le code binaire-réfléchi. Un exemple de réalisation très simple de codeur fonctionnant selon le principe décrit ci-dessus est représenté sur la figure 3. La mémoire tampon est @n registre à décalage comportant N bascules. Le portier 11 est inutile p@isq@e @@ = n. La fig@re représente le cas où n = 2. Chaque bloc de 2 bits est codé en une grandeur analogique qui peut prendre 4 valeurs distinctes. Si à un instant donné, le bloc (bi, bi-1) est transformé en une grandeur Ai, à l'instant suivant déterminé par l'horloge, le bloc (bi+1, bi) est transformé n une grandeur Ai+1. Chaque bit b1 est associée à 2 grandeurs analogiques Ai et Ai+1 en 2 instants consécutifs. Un deuxième exemple de réalisation est représenté sur la figure 4. La mémoire tampon 10 est un registre à décalage comportant N bascules , N étant un entier multiple de n. La figure représente le cas où n = 2 et N = 10. Les sorties des bascules sont numérotées dans 1 t ordre alphabétique de a à j. Le portier il est constitué de deux multiplexeurs 111 et 112, chacun ayant deux entrées et sélectionnant alternativement l'une des deux entrées sous la commande d'un signal H1 obtenue par division par 2 du signal d'horloge.P-ar exemple lorsque H1 = O, les sorties B1 et B2 des-multiplexeurs 111 et 112 sont B1 = b, B2 = a et lorsque H1 = I, B2 = j., B1 = I Le diagramme des temps de la figure 5 représente les différents bits présents en divers points du système en fonction du temps t, à savoir en (a) H, en (b): H1, en (c): les bits bi arrivant en A, en (d)et (e)les bits arrivant respectivement en B2 et B1. Les flèches indiquent l'origine de ces bits parmi les données arrivant en A. En (f),est représentée l'allure de la courbe en fonction du temps des grandeurs analogiques Ai. On peut remarquer que deux grandeurs analogiques associées au même bit (bi est associé à Ai et Ai+1 sont séparées alternativement de 7 ou de 9 temps d'horloge. L'avantage du m@@- d'adressage par multiplexage est de code, rager en merle temps les erreurs de bruit aléatore et les erreurs de salves. En effet, si la durée des salves est inférieur à une certaine limite, la même salve portera sur k grandeurs analogiques associées à des bits différents. Au contraire, avec le premier procédé décrit, une même salve peut porter sur toutes les grandeurs analogiques associées au même bit et les erreurs ne peuvent être corrigées. Quelque soit la v@@iante adoptée, on dispose à chaque instant à l'entrée du convèrtisseur numérique-analogique de bits successifs bi, bi+1,..., bi+n-1 sur n voies B1 à Bn. Le code de conversion le plus courant est le code binaire décimal. Pour n = 4, la valeur analogique obtenue en C associée aux bits bi, bi-1, bi-2, bi-3 est Ui = Uo [8 bi + 4 bi-1 + 2 bi-2 + bi-3] Uo étant le pas de l'échelle des grandeurs analogiques. En D, on reçoit une valeur U'i égale à Ui + Xi, Xi étant la valeur du bruit lors de la transmission de Ui ; c'est une grandeur aléatoire. Un convertisseur analogique-numérique fonctionne schématiquement de la façon suivante pour n = 4, il délivre b'i = (U'i > 8 U ) b'i-1 = (U'i - 8 b'i > 4 Uo) b'i-2 = (U'i - 8 b'i - 4 b'i - 4 b'i-1 > 2 Uo b'i-3 = (U'i - 8 b'i - 4 b'i-1 - 2 b'i-2 > Uo Si l'on veut minimiser le taux d'erreur, il faut faire en sorte que pour une même valeur de bruit X, le nombre de bits erronés soit le plus faible possible. Le meilleur code est alors le code binaire-réfléchi, avec lequel deux grandeurs U'et U' + Uo ne diffèrent que d'un bit Ainsi, supposons que X = Uo. Avec le code binaire-décimal, le nombre de bits erronés dépend de la valeur de U. Si U = 7 Uo (grandeur associée au groupe de bits 0111), on aura J = 8 Uo (groupe de bit assolé : 1000).Les 4 bits @ errronés. Avec le code de Gray, quelque soit la valeur de U, un seul bit est erroné. 5-r la figure 6 est représenté le schéma général du décodeur 9 selon l'invention. Les grandeurs analogiques reçues en D sont co@verties en blocs de bits en parallèle sur n voies E1 à En Ces blocs sont remis en ordre, si nêcessaîre,-au moyen de n ensembles mémoires-tampon 911 à 91n et portiers 921 à 92n fonction nant de la même façon que dans le codeur. Les bits de chaque voie Fi sont mémorisés respectivement pendant i fois le temps d'horloge de façon que sur les sorties G1 à Gn des mémoires 941à 94n, on obtienne les n représentations éventuellement erronées du même bit.Ces mémoires sont par exemple des.registre-s à décalage de 1 à n bits. La structure du décodeur dépend de celle du codeur auquel il est associe. Ainsi, au codeur de la figure 3, correspond le décodeur de la figure 7 et au codeur de la figure 4 correspond le décodeur ue-la figure 8. Le diagramme des temps de la figure 9 représente dans le cas n = 2, N = 10 en (a) : les grandeurs analogiques reçues en D, en (b) et (d) : les bits présents respectivement en E2 et E1, en (c) et (e) : les bits présents respectivement en F2 et F1, en (f) : les bits présents en G2 qui sont les mêmes que ceux pré- sents en G1. On-vérifie aisément que l'ordre des bits a été rétabli et qu'en G1 et G2, on a les deux représentations de la même donnée. L'organe de décision 5 reçoit en-parallèle à chaque temps d'horloge n représentations de la même donnée. Sa fonction est d'effectuer une sélection parmi ces n représentations de façon à optimiser la correction. Pour cela, la règle la-plus simple est de choisir la valeur majoritaire, si elle existe, ou sinon, la valeur du bit transmis sous forme analogique avec le poids le plus élevé, c'est-à-dire Gn En effet, on a vu que c'était le bit le plus sur. Le circuit de décision peut être un circuit com- binatoire formé de portes logiques et réalisant la fonction souhaitée. Ce peut être aussi une mémoire programmable. Le fonctionnement du système de décodage nécessite une horloge de fréquence f, synchrone avec l'arrivée des données en D. Un procédé simple de restitution de l'horloge consiste en un oscillateur asservi en phase sur des impulsions declenchées par les transitions du signal analogique. La correction est unélicrée si, lors de la sélection, on élimine les bits détectés très suspects ou faux par un détecteur de validité branché en D, selon le schéma de la figure 10. On dispose d'un détecteur 7 recevant les graux analogiques et émettant en V pour chaque grandeur analogique un bit de validité V. Le détecteur a pour fonction de détecter certains types d'erreurs non aléatoires : parasites, dépassement de dynamique, etc. Supposons par exemple que les grandeurs analogiques occupent la gamme O a UN Le détecteur peut être un comparateur qui délivre un signal logique "haut" lorsque, la valeur U reçue en D est comprise dans la gamme et un signal logique "bas" dans le cas contraire. Les bits V subissent les mêmes transformations que les bits des voies E1 à En et traversent donc une mémoire tampon 910 et un portier 920. On mémorise les bits reçus, en Fo, de façon à disposer en Y1, Y2,..., n des n bits de validité associés aux bits présents en G1, G.,..., tin. Pour la décision, seuls les bits dits valides correspondant à des grandeurs analogiques réputdes valides (V r 1) sont considérés . La valeur majoritaire ou la valeur du bit de poids le plus élevé sont choisies parmi les bits valides. Un cas est indéterminé et est donc une cause d'erreurs indétectables : celui où aucune représentation de la même donnée n'est valide.La variante décrite permet de réduire le taux d'erreur final, surtout lorsque le taux d'erreurs indétectables est très inférieur au taux d'erreurs détectables. Supposons, par exemple, que l'on veuille transmettre des signaux avec un taux @'erreurs maximal égal à 10-8 et que l'on ch@i@isse n = 4. Le taux maximal admissible d'erreurs détectables du canal T1 est tel que 4 erreurs n'apparaissent pas dans un groupe de 4 valeurs analogiques avec une probabilité supérieure à 10-8, d'où T X Le t@ux maximal admissible d'erreurs indétectable @2 est qu'il n'apparaisse pas 2 erreurs ou plus dans un groupe de 4 valeurs analogiques avec ui= orobabilité supérieure à 10-@, d'où #2 I1 apparait nettement que les taux d'erreurs admissibles sont fonction de la valeur de n. Or ce nombre est limité par la valeur du rapport signal sur bruit du canal R. R est généralement de l'ordre de 30 dB. Si l'on veut que le rapport signal sur bruit affectant les données numériques R'ne soit pas inférieur à 3, R étant donné que R' = , on obtient n inférieur ou égal à 4. 2n - 1 Une variante du décodage permet de diminuer le taux d'er- reurs sur chaque bit, et en particulier sur les composants de poids le plus élevé qui, on l'a vu, sont les plus importantes. Selon cette variante, les composantes de chaque grandeur analogique Ui sont calculées à partir de Ui et aussi des composantes de Ui-1, du moins si Ui-1 est une grandeur valide, n-1 des composantes de Ui et de Ui-1 étant des représentations du même bit, on admet, et cela peut se vérifier, que les représentations provenant de Ui-1 sont plus sûres que- celles provenant de U. car elles ont des poids respectivement plus élevé. Le procédé de décodage est alors le suivant : chaque grandeur Ui est convertie sous forme numérique en n bits bii, bi-1i,..., bi-n+1i, comme précédemment. Mais ces composantes sont éventuellement modifiées selon l'algorithme suivant (n = 4). b'ii =(Ui/Uo > b'i-1i-1 + 2 b'i-2i-1 + b'i-3i-1 + 4) # Vi-1 bii # Vi-1 b'i-1i = (Ui/Uo - 8 b'ii > 2 b'i-2i-1 + b'i-3i-1 + 2) # Vi-1 + b i-1i # V b'i-2i = (Ui/Uo - 4 b'i-1i > b'i-3i-@ + 1) # Vi-1 + bi-2i # Vi-1 b'i-3i = bi-3i Pour réaliser cet algoritheme on peut utiliser une mémoire programmable 6, selon lo schéma de la figure 11, représentant le cas où n = 4. Les entrées F1, F2, F3, F4, I1, I2, I3, I4 reçoivent respectivement les bits bi-3i, bi-1i, bii, bi-3i-1, bi-2i-1, bi-1i-1 Vi-1. Les scrites J1, J2, J3i, J4 fournissent respectivement les bits b'i-3i, b'i-2i, b'i-1i, b'ii. Bien entendu, l'invention n'est pas limitée aux modes de réalisation décrits ci-dessus. En particulier, les algorithmes de décodage peuvent varier. On les choisira-en fonction des performances souhaitées pour l'application envisagée. L'invention s'applique notamment à la transmission de signaux téléphoniques, d la memorisation de signaux de télévision sur magnetoscope ou disques vidéo. L'invention est intéressante par les débits élevés qu'elle permet, avec des taux d'erreurs faibles. REVENDICATIONS 1. Procédé de codage-décodage d'information emise sous forme d'une séquence de bit de donnée par une source d'information, destinée à être reçue sous forme d'une séquence de bits réalisant une concordance optimale avec la séquence d'émission, le transit des informations se faisant pa des moyens de diffusion de signaux analogiques, ledit procédé comprenant les étapes suivantes ; - réartition de l'information par blocs de p bits de donnée, auxquels sot associes n-p bits de parité, n et p étant des ontlers tels que n > p > o ; - conversion de chaque bloc en une valeur analogique ; - conversion de chaque valeur analogique diffusée en un bloc de n bits ;; - détermination des bits de la séquence reçue en vue de réaliser ladite concordance, ledit procédé tant caractérisé en ce que p = 1, en ce que les n - 1 bits de prit associés à chaque bit de donnée sont la répétition de bits de donnée précédemment émis, de façon que chaque bit émis soit présent avec des poids différents dans n blocs distincts et en ce que les blocs successifs reçus sont stockés dans une mémoire donnant accès aux- n valeurs numériques assignées à chaque bit de donnée, la correction comportant un choix entre ces n valeurs, selon un critère prédéterminé. 2. Procédé de codage-décodage s@lcn la revendication 1, caractérisé en ce que la répartition de l'information par blocs s'effectue au moyen d'une mémoire recevant la séquence d'émission et donnant accès à n bits consécutifs de ladite séquence. 3. Procédé de codage-décodage selon la revendication 2, caractérisé en ce que la répartition de l'information par blocs réalise un brassage des blocs, de façon que les n valeurs analogiques contenant un même bit de donnée soit diffusées de façon non consécutive. Procédé de codage-décodage selon la revendication 3, caractérisé en ce que le brassage est réalisé par une mémoire donnant accès à n groupes de n bits consécutifs de la séquence d'émission, chaque groupe étant sélectionné par un élément logi- que, de façon cyclique e synchror.isme avec l'émission des bits de donnée. 5. Procédé de codage-décodage selon la revendication 4, caractérisé en ce que les blocs de bits issus de la. conversion analogique-numérique sont remis en ordre par n @émoires d~nrar.t accès à n bits sélectionnés de façon cyclique par un élément logique, en synchronisme avec la diffusion) de façon à obtenir n séquences de valeurs assignées à n bits de donnée, dans l'ordre de la séquence dtémission. 6. Procédé de codage-décodage selon l'une des revendications 1 à 5, caractérisé en ce que les conversions numériques-analogique et analogique-numérique s'effectuent selon le code binaire décimal. 7. Procédé de codage-décodage selon l'une des revendications 1 à 5, caractérisé en ce que les conversiois numérique-analogique et analogique-numérique s t effectuent selon le code binaire-réfléchi. 8. Procédé de codage-décodage selon ltune au moins des revendications 1 à 7, caractérisé en e que le critère de choix pour la correction consiste à sélectionner parmi les valeurs numériques assignées à chaque bit de donné, au moyen d'un organe logique de décision, l'une des valeurs constituées par la valeur numérique prépondérante, et à défaut, la valeur de poids le plus élevé. r Procédé de codage-décodage selon la revendication 8, caractérisé en ce que l'organe logique de décision est formé de portes logiques, agencées de façon à effectuer ladite sélection. 10. Procédé de codage-décodage selon la revendication 8, caractérisé en ce que organe logique de décision comprend une mémoire programmée de façon à effectuer ladite sélection. 11. Procédé de codage-decodage selon l'une au moins des revendications 1 à 10, caractérisé en ce qu'il comprend en outre une phase de détection de validité des signaux analogiques diffusés, en vue d'éliminer, lors de la correction, les bits provenant de la conversion de valeurs analogiques jugées non valides lors de la détection. 12. Procédé de codage-décodage selon la re@endication '', caractérisé en ce qu'une valeur analogique es@ jugée valide lorsqu'elle appartient une plage de valeurs p@édéterminée. 13. Procédé de codage-décodage selon la rerendication 11, caractérisé en ce que préalablenent à la phase de sélection, il comporte une phase de confirmation-invalidation des valeurs numériques des n bits de chaque bloc diffusé, à partir des valeurs numériques de poids plus levé, présentes dans un bloc précédem- ment reçu. IL. Dispositif de diffusion mettant en oeuvre le procéda de codage-décodage selon l'une au moins des revendications 1 à 13, caractérisé en ce que les moyens de diffusion comprennent une ligne de transmission de signaux électriques. 15. Dispositif de diffusion mettant en oeuvre le procédé de codage-decodage selon l'une au moins des revendications 1 à 13, caractérisé en ce que les moyens de diffusion comprennent un support d'information capable de transcrire au mois 2 états différents, des moyens d'enregistrement de signaux analogiques sur ledit support et des moyens de lecture dudit support restituant des signaux analogiques.