FR 2616606 A1 19881216 FR 8807847 A 19880613 26 1 6606 APPAREIL ET PROCEDE DE TRANSMISSION DE DONNEES La présente invention concerne des constellations de signal pour des systèmes de communication. Dans des systèmes de communication utilisant par exemple des modems, on émet des données sur un canal affec- té par du bruit, en modulant un porteur conformément à une série de points de signal choisis dans une constellation de points de signal disponibles. Dans un système de modulation d'amplitude en quadrature (MAQ), la constellation est bidi- mensionnelle. On sait qu'on peut obtenir-certains avantages en utilisant des constellations ayant un plus grand nombre de dimensions, pour définir les points à émettre. Une constellation C à N dimensions (avec N supé- rieur à 2) est un ensemble fini de N-uples (c'est-à-dire des points ayant chacun N coordonnées qui définissent en- semble une position dans un espace à N dimensions). Les principales caractéristiques d'une telle constellation sont le nombre ICi de ses points, la distance au carré minimale min(C) entre ses points, et son énergie moyenne (ou norme euclidienne moyenne) P(C). Pour un nombre de points donné, le facteur de mérite d'une constellation utilisée pour la transmission de signaux est P(C)/d min(C) (il est d'autant meilleur qu'il est plus petit). Un procédé général connu pour construire une bonne constellation (c'est-àdire une constellation avec un faible facteur de mérite) ayant un nombre désiré de points, consis- te à choisir un ensemble fini de points dans ce qu'on appel- 26 1 66( C le un réseau à N dimensions A dense (c'est-à-dire dont les éléments sont serrés), ou dans un co-ensemble de A (c'est- à-dire une version de A qui résulte d'une translation). On peut sélectionner les points en définissant une région R dans l'espace à N dimensions qui est juste suffisamment grande pour contenir le nombre de points désiré. La distance au carré minimale d2 in(C) de la constellation est la distan- min_ ce au carré minimale d. in(A) du réseau A; en général, pour min minimiser l'énergie moyenne P(C), la région R doit ressem- bler le plus exactement possible à une sphère à N dimensions centrée sur l'origine. Dans le document "A Fast Encoding Method for Lat- tice Codes and Quantizers", IEEE Trans. Inform. Theory, vol. IT-29, pages 820-824, 1983, Conway et Sloane proposent de procéder de la manière suivante pour définir une telle région contenant le nombre de points désiré. On suppose qu'un réseau à N dimensions A donné possède, en tant que sous-réseau, une version proportionnelle MA du même réseau, en désignant par M un facteur de proportionnalité ou d'échel- le entier. Le sous-réseau est ainsi un sous-ensemble des points du réseau, qui est sélectionné de façon que le sous- réseau soit simplement une version à plus grande échelle du réseau. (On notera que MA et À sont des réseaux du même type.) Il y alors MN classes d'équivalence de points dans le réseau d'origine A (ou dans tout co-ensemble de A), mo- dulo MJ. On note que deux N-uples sont équivalents modulo MA (et appartiennent donc à une classe d'équivalence) si leur différence est un point dans MA. On appelle région de Voronoi du réseau M A l'en- semble de points dans l'espace à N dimensions qui sont au moins aussi près de l'origine que tout autre point du réseau dans MA. On peut définir l'intérieur de la région de Voronoi comme étant l'ensemble de points plus proches de l'origine que de tout autre point du réseau; la frontière de la région de Voronoi est l'ensemble de points pour les- quels l'origine est l'un des points les plus proches dans le réseau, mais pour lesquels il y a d'autres points du réseau également proches. En général, la frontière est une surface fermée dans l'espace a N dimensions, qui est cons- tituée par un certain nombre de faces à (N-1) dimensions, qui sont des portions d'hyperplans équidistants entre deux points du réseau voisinsdans MA. (Par exemple, la région de Voronoi d'un réseau d'entiers à N dimensions, ZN, est un cube à N dimensions de côté 1, dont les faces sont des cubes à (N-1) dimensions de côté 1. Les intersections des faces sont des figures à N-2 dimensions, ou moins, et elles ont plus de deux voisins les plus proches.) Par conséquent, si A + c est un co-ensemble du réseau d'origine (en désignant par c le vecteur de transla- tion), qui est choisi de façon à ne pas comporter de points sur la frontière de la région de Voronoi du réseau propor- tionnel MA, la région de Voronoi contient MN points du co-ensemble A + c, à raison d'un provenant de chaque clas- se d'équivalence modulo MA, et la région de Voronoi à MN points peut être utilisée en tant que constellation de si- gnal, qu'on appelle une constellation de Voronoi (Conway et Sloane l'appellent un code de Voronoi). De telles cons- tellations sont caractérisées par une énergie moyenne rela- tivement faible, et elles peuvent être mises en oeuvre de façon relativement simple. Une caractéristique générale de l'invention, pour la transmission de données sur un canal, comprend la sélec- tion d'une série de points de signal dans une constellation comprenant des points d'un réseau A (ou d'un co-ensemble de A), qui se trouvent à l'intérieur d'une région de Voronoi d'un sous-réseau À' de A, le sousréseau J' n'étant pas une version proportionnelle de k, et la modulation d'un porteur sur le canal conformément à la série sélectionnée de points de signal. Des modes de réalisation préférés comprennent les caractéristiques suivantes. Le sous-réseau A' est d'un type différent du réseau A. La constellation est basée sur des points dans une région fondamentale du sous-réseau A', com- penant une sélection avec prédétermination maximale de moins que la totalité des points dans la région de Voronoi. Cer- tains points de la région fondamentale se trouvent sur une frontière de la région de Voronoi. Le réseau A est une ver- sion d'un réseau d'entiers zN, en désignant par N un nombre entier. Le sous-réseau A' peut être une version d'un réseau de Schlâfli D4, ou une version d'un réseau de Barnes-Wall A 16- Une autre caractéristique générale de l'invention consiste à sélectionner une série de points de signal à par- tir d'une constellation de points disponibles, sur la base d'un code, la constellation étant une constellation de Voronoi et le code étant un code de co-ensemble, et à moduler un porteur conformément à la série sélectionnée de points de signal. Des modes de réalisation préférés comprennent les caractéristiques suivantes. Le code de co-ensemble peut avoir le même nombre de dimensions (par exemple 4) que la constel- lation de Voronoi, ou bien un nombre de dimensions différent (par exemple, le code de co-ensemble peut avoir 4 dimensions et la constellation de Voronoi peut avoir 16 dimensions). Une autre caractéristique générale de l'invention procure un procédé de projection de m bits de données dans une constellation de Voronoi à 2m points, pour la transmis- sion de ces bits sur un canal, sur la base d'une partition de réseau à N dimensions A/A', le sous-réseau A' étant autre qu'une version proportionnelle du réseau A, ce procé- dé comprenant les opérations suivantes: (i) on projette les m bits vers l'un des 2m mots de données x, chaque mot de données x comprenant N coordonnées (x1,..., xn), chaque coordonnée prenant une valeur d'un ensemble de valeurs pré- déterminé, le nombre d'éléments dans de tels ensembles dif- 6 66 Xc férents de valeurs de coordonnées n'étant pas identique, et chaque mot de données étant un point dans un co-ensemble de A, qui appartient à une classe d'équivalence distincte mo- dulo A '; (ii) on décode le mot de données x pour donner un point A dans A'!; et (iii) on utilise l'erreur apparente e = x - ? (ou une version translatée e - c de l'erreur appa- rente) en tant que coordonnées du pointde la constellation à transmettre. On peut construire des constellations ayant un nombre de pointsl. e l autre que simplement la N-ième puissance d'un entier (MN), en désignant par IA'/ I l'ordre de la partition (groupe de quotient). Même si le réseau d'origine A n'est pas un réseau dense (par exemple le réseau d'entiers à N dimensions zN), ce qui peut avoir des avanta- ges dans certaines techniques de codage (par exemple des codes de co-ensembles), on peut utiliser la région de Voro- noi a'un réseau dense J'' pour définir la frontière de la constellation, ce qui procure l'avantage d'une constellation quasi-sphérique. Le procédé de projection de mots de données vers des points de la constellation de Voronoi est simple à mettre en oeuvre. L'invention sera mieux comprise à la lecture de la description qui va suivre d'un mode de réalisation, donné à titre d'exemple non limitatif. La suite de la description se réfère aux dessins annexés sur lesquels: La figure 1 est un organigramme pour la formation d'une constellation de Voronoi. La figure 2 est un organigramme pour la génération d'une région fondamentale. La figure 3 montre trois constellations de type Voronoi non translatées. La figure 4 est un organigramme pour le décodage. La figure 5 est un schéma synoptique qui illustre un code de co-ensemble généralisé. La figure 6 est un schéma synoptique illustrant un 26166C code de co-ensemble. La figure 7 est un schéma synoptique illustrant un code de co-ensemble du type Wei. Les figures 8, 9 sont des schémas synoptiques d'un émetteur et d'un récepteur de modem. On va tout d'abord exposer un procédé général pour engendrer des constellations de Voronoi optimales. A titre préliminaire, on définit une région fonda- mentale d'un réseau A comme étant une région qui contient un point et un seulement de toutes les classes d'équivalence de N-uples modulo t. Toutes les régions fondamentales ont le même volume V(A). La région de Voronoi d'un réseau A contient une région fondamentale de A, qui comprend tous les points à l'intérieur, plus un sous-ensemble de points sur la frontiè- re, de façon que le sous-ensemble contienne un point et un seulement de chaque classe d'équivalence modulo A. En fait, la frontière de la région contient également des points sup- plémentaires qui ne sont pas dans la région fondamentale. On désigne par A un réseau, par A' un sous-réseau quelconque de A, et par jA/X l l'ordre de la partition de réseau (groupe de quotient) A / A-. On désigne par R une région fondamentale de A' qui contient l'intérieur de la région de Voronoi de A', ainsi qu'un sous-ensemble de la frontière. Dans ces conditions, R contient précisément IA/ A points de A. Les points contenus dans R formeront la base de la constellation. Du fait que le frontière contient plus de points qu'il n'est nécessaire pour former entièrement la région R, on doit effectuer un certain choix parmi les points sur la frontière. On effectue de préférence le choix d'une manière telle que les points sélectionnés présentent (ce qu'on ap- pellera) une prédétermination maximale, en procédant de la manière suivante. Soit b un point quelconque sur la fron- tière de la région de Voronoi de A', et soit cl(b) l'en- semble de points sur la frontière qui équivalent à b modulo A'. (La taille de cet ensemble sera égale au nombre de voi- sins les plus proches de b dans A'; en outre, les vecteurs reliant b à ses voisins les plus proches correspondent aux éléments de cl(b), ce qui fait que chaque point de cl(b) a la même norme.) On doit choisir un seul des points dans l'ensemble cl(b), pour l'inclusion dans la constellation. Soit cl1(b) le sous-ensemble de points de cl(b) qui ont la plus grande première coordonnée; soit c12(b) le sous-ensem- ble de points de cll(b) qui ont la plus grande seconde coor- donnée, et ainsi de suite. Finalement, pour une certaine valeur de i, cli(b) n'aura qu'un seul point; on le choisit comme étant le seul point de cl(b) à inclure dans R. On ré- pète le même processus jusqu'à ce qu'on ait traité tous les points sur la frontière. On désigne par CO l'ensemble (constellation) de A / A' points de A dans la région R qui résulte de ce pro- cessus de sélection de points. Si c est la moyenne des points, l'étape suivante consiste à faire en sorte que la constellation de Voronoi C soit une translation de C0 par c, de manière que la moyenne de C soit égale à 0. C est donc un ensemble de 1A/' i points du co-ensemble A- c de A. En considérant la figure 1, on peut résumer de la manière suivante le processus de formation de la constella- tion de Voronoi: on sélectionne un réseau A(10); on sé- lectionne un sous-réseau approprié A'(12); on délimite la région de Voronoi du sous-réseau (14); on sélectionne un point dans chaque classe d'équivalence sur la frontière de la région de Voronoi, pour engendrer une constellation C0, représentant des points de A qui se trouvent à l'intérieur d'une région fondamentale R de A' (16), de préférence en procédant avec une prédétermination maximale; et on trans- late d'un vecteur c, si nécessaire, des points de la cons- tellation C0, pour créer une constellation C = C0 - c pour laquelle la moyenne est égale à-0 (18). La raison pour laquelle on engendre la constellation de Voronoi par la technique de prédétermination maximale est la suivante. L'énergie moyenne P(C) des points dans C est la variance de la norme des points dans C0, qui est leur norme moyenne P(C)0 moins la norme de leur moyenne c. Par notre sé- lection avec prédétermination maximale des points de la fron- tière qui doivent être dans R, on essaie de maximiser pre- mièrement la première coordonnée de c, ensuite la seconde coordonnée, et ainsi de suite. Si on a résolu tous les con- flits de classe d'équivalence (de A modulo A') sauf un, de façon qu'en l'absence de la résolution de la dernière classe, la moyenne c ait des coordonnées décroissantes positives, la résolution de la dernière classe de la manière spécifiée ci- dessus est telle qu'elle maximise la norme du vecteur c final. Mais ceci est précisément ce qu'on désire pour minimiser la variance de la norme dans C0, et donc l'énergie moyenne P(C) de C. On pense que la sélection d'une constellation de Voronoi en procédant de cette manière (c'est-à-dire une sé- lection à prédétermination maximale) conduit à une constella- tion optimale; c'est-à-dire une constellation avec l'énergie P(C) minimale parmi toutes les constellations de Voronoi pos- sibles basées sur la partition de réseau A/1'. Cependant, lorsque le nombre \A/ A'I de points de la constellation est grand, la manière selon laquelle les conflits à la frontière sont résolus n'a pas grande importance, du fait que dans toutes les constellations de Voronoi C, l'énergie P(C) sera approximativement égale à P(C0). On peut alors résoudre les conflits à la frontière par d'autres critères, tels que la symétrie, lorsque c'est souhaitable pour des applications particulières. Décodeurs pour des constellations de Voronoi Un décodeur (ou quantificateur) d'un réseau A est une projection faisant passer d'au moins certains points r dans l'espace à N dimensions, à des points de réseau dans le réseau A. Un décodeur exhaustif est un décodeur qui projette chaque point dans l'espace à N dimensions vers un point du réseau. Un décodeur à distance minimale est une projection qui donne toujours un point de réseau le plus proche de r. Un décodeur régulier est un décodeur tel que si r est projeté vers X, et A' est un point quelconque du réseau, r + A' est projeté vers A + A'. On peut utiliser une région fondamentale R de A' qui contient l'intérieur d'une région de Voronoi de A.', pour définir un décodeur régulier, exhaustif, à distance minimale (REDM), en procédant de la manière suivante. Tout point r dans l'espace à N dimensions (appartenant ou non à la région R) équivaut à un point spécifique a dans R, et est donc égal à un point a +A spécifique pour un certain point de réseau A de A'. La projection qui associe ce à chaque r est le décodeur désiré. Inversement, tout décodeur REDM de A' définit une région fondamentale R de A' qui contient l'intérieur d'une région de Voronoi de e, c'est-à-dire l'ensemble de tous les points r qui sont projetés vers 0. On appellera décodeur à prédétermination maximale un décodeur REDM pour lequel cette région fondamentale est du type à prédétermination ma- ximale. On connaît déjà pour de nombreux réseaux des déco- deurs à distance minimale efficaces (voir par exemple les documents suivants: Conway et Sloane, "Fast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes", IEEE Trans. Inform. Theory, vol. IT-28, pages 227-232, 1982; Forney et col. "Efficient Modulation for Band-Limited Chan- nels", IEEE J. Select. Areas Commun., vol. SAC-2, pages 632- 647, 1984; Conway et Sloane, "Decoding Techniques for Codes and Lattices, Including the Golay and the Leech Lattice", IEEE Trans. Inform. Theory, vol. IT-32, pages 41-50, 1986; et Forney, demande de brevet US-828 397, déposée le 11 fé- vrier 1986, cédée à la demanderesse.) Pour rendre ces déco- deurs exhaustifs, il est nécessaire de spécifier une règle de décision lorsqu'il existe plus d'un voisin le plus proche de r. Dans le cas qui nous occupe, on désire une règle de décision qui rende le décodeur régulier et à prédétermina- tion maximale. Une telle règle est la suivante: choisir le voisin le plus proche A de façon que l'erreur apparente e = r -A soit aussi grande que possible dans la première coordonnée, ensuite dans la seconde, etc. Ceci peut s'énon- cer de la façon équivalente suivante: résoudre des conflits en faveur du point A du réseau qui est le voisin le plus proche ayant la plus petite première coordonnée, ensuite la plus petite seconde coordonnée, etc. On peut utiliser ces décodeurs connus, complétés avec une telle règle de décision, pour construire efficace- ment des constellations de Voronoi et pour projeter des symboles de données vers des points de la constellation. En considérant la figure 2, on note que pour cons- truire une constellation de Voronoi, en disposant d'un ré- seau A, d'un sous-réseau Ae et d'un décodeur REDM à prédé- termination maximale pour A', on peut décoder les points de t par ordre de norme croissante (20), conserver (22) ceux dont le décodage conduit à 0, et rejeter tous ceux dont le décodage ne conduit pas à 0 (c'est-à-dire qui sont des équi- valents de points conservés, modulo A') (22), jusqu'à ce qu'on obtienne IA/IAI points, à raison d'un point provenant de chaque classe d'équivalence (26). Les normes qu'on doit considérer sont bornées par rmax2, c'est-à-dire la distance maxÀ au carré maximale entre un point r quelconque dans l'espace à N dimensions et un point dans J'. Ceci donne la constel- lation non translatée C0; en soustrayant sa moyenne c (éta- pe 18, figure 1), on obtient C. Selon une variante, on peut partir d'un ensemble de |A/ A'lpoints de A, dont on sait qu'il contient un point provenant de chaque classe d'équivalence; et de eNgN, qui est l'ensemble de points de X qui se trouvent à l'inté- 1 1 rieur d'une certaine région fondamentale connue R de '. Si on décode chaque point a de ce type en un point de réseau \ de A', l'erreur apparente e = a - à est le point corres- pondant qui équivaut à a dont le décodage conduit à 0; les erreurs apparentes définissent donc les points dans C0. Dans l'article "A Fast Encoding...", précité, Conway et Sloane notent que lorsque A' = MA, chacun des MN N-uples d'entiers modulo M est projeté vers une classe d'équivalence différente de A/MI, la projection s'effec- tuant vers le terme a qui est la somme des produits des coordonnées des N-uples avec les N générateurs de A. Un dé- codeur pour A' peut alors projeter a vers le point e cor- respondant dans C0. Ceci est une projection efficace dirigée d'un mot de données, représenté par un N-uple d'entiers modulo M, vers des points dans C0. Pour effectuer une pro- jection vers des points dans C, on applique une translation par c. En retournant au cas d'un sous-réseau général A' (dans lequel A' n'est pas nécessairement MA), on note que si on connait une projection simple de façon similaire de l'un des [A/i A mots de données vers des points a dans dif- férentes classes d'équivalences de A/A', cette projection plus un décodeur efficace constituent une projection effica- ce faisant passer de mots de données vers des points dans une constellation de Voronoi C. Le réseau hexagonal bidimensionnel A2 A titre d'exemple d'une constellation de Voronoi bidirectionnelle, on considérera le réseau hexagonal bidi- mensionnel A2 qui est défini comme étant l'ensemble de tous les points qui sont des sommes de produits entiers des deux générateurs (1,0) et (1/2, \r/2). Dans cette forme, on a pour ce réseau dmin=l. Ce réseau et la constellation à 16 points qui est associée à la partition A2/4A2 ont été envisag par Conwayet cie dans l'article "A Fast Encoding..." précité. On les envisa- 26' 6É06 ge à nouveau ici dans un but de comparaison et du fait que le cas 2D est aisé à visualiser. La ragion de Voronoi de A2 est un hexagone avec des côtés de longueur \F/3 et une aire de \F/2. La région fon- damentale R de A2 qui est en accord avec le procédé général envisagé ci-dessus (c'est-à-dire qui est prédéterminéede fa- çon maximale), est la région qui comprend l'intérieur de cet hexagone plus les points qui se trouvent sur la frontière avec une première coordonnée strictement positive; c'est-à-dire que seuls les deux sommets (1/2 + \ f/6) sont inclus. Le réseau MA est un sous-réseau de A2 d'ordre M2 2 22 pour tout entier M tel que M soit une norme d'un point dans A2. Ceci inclut tout M qui est une puissance de deux, pour lequel A2/MA2 est une partition dont l'ordre est une puissance de 4. Les constellations C0 à 4 points, 16 points et 64 points correspondant aux partitions de réseau A2/2A2, A2/4A2, et A2/ 8A2 sont représentées sur la figure 3, avec la région fonda- mentale associée de A2. Dans chaque cas, les cercles pleins représentent des points dans C0, les cercles vides représen- tent des points dans la région de Voronoi du sous-réseau MA2, mais non dans la région fondamentale, et la ligne continue représente la frontière de la constellation. Les axes de la constellation C0 sont représentés en traits continus; l'axe Y de la constellation translatée C est représenté en pointil- lés. Ces constellations ont respectivement des puissances moyennes.P(C0) de 3/4 = 0,75 (-1,25 dB), 9/4 = 2,25 (3,52 dB), et 9 (9,54 dB); leurs moyennes sont c = (1/2,0), (1/4,0), et (3/8,0); et par conséquent les constellations de Voronoi C correspondantes ont des puissances moyennes P(C) égales à 1/2=0,5 (-3,01 dB), 35/16=2,19 (3,40 dB), et 567/64 = 8,86 (9,47 dB). (Les estimations de P(C) qui sont données par "l'approximation intégrald'de Forney et col. dans le document précité intitulé "Efficient Modulation for Band Limited Channels", sont respectivement: 0,56 (-2,55 dB), 2,22 (3,47 dB), et 8,89 (9,49 dB)). La constellation à 4 points 26 166 t 6 A2/2A2 est ancienne. La constellation à 16 points A2/4A2 est représentée dans le document précité de Conway et Sloane, intitulé "A Fast Encoding Method... Deux constellations à 64 points qui ne sont pas du type de Voronoi, avec une éner- gie P(C) légèrement meilleure, sont représentées dans le document de Forney et col. intitulé "Efficient Modulation..." Les constellations de la figure 3 illustrent quel- ques propositions générales concernant des régions fondamen- tales R qui sont à prédétermination maximale. De telles ré- gions comprennent tous les points à l'intérieur de la région de Voronoi, plus les intérieurs de la moitié des faces(du fait que l'intérieur de chaque face n'a que deux voisins les plus proches). Un point qui estcontenu dans l'intersection de deux faces ou plus est dans R si et seulement si les in- térieurs de toutes ces faces sont dans R. La frontière de R est donc une surface compacte, ouverte, à (N-1) dimensions, dans un espace à N dimensions, dont le volume est égal à la moitié du volume qui correspond à la surface de la région de Voronoi. En fait, ce volume essaie de ressembler le plus possible à une demi-sphère. Une constellation de Voronoi à 4 dimensions On considérera le réseau de Schlâfli à quatre di- mensions, D4, qui est défini comme étant l'ensemble de tous les 4-uples d'entiers contenant un nombre pair d'entiers im- pairs. Dans cette forme, il a d2. = 2. min En considérant la figure 4, on peut définir de la façon suivante un procédé'de décodage à distance minimale simple pour D4 (voir l'article de Conway et Sloane intitulé "A Fast Encoding Method...", et l'article de Forney et col., tous deux cités ci-dessus). Pour tout r, trouver tout d'abord le 4-uple d'entiers a le plus proche de r (30). Déterminer ensuite si a contient un nombre pair d'entiers impairs (32). Dans l'affirmative, accepter a (34). Dans la négative, rem- placer une coordonnée de a par l'entier suivant le plus proche, dans la coordonnée pour laquelle ceci donnera le *2 6 1 06 plus petit changement (36), et effectuer le décodage de r pour obtenir le a changé (38). La règle de décision (lorsque deux points du réseau sont également proches du point r) qui correspond à la prédé- termination maximale est la suivante. A la première étape de décodage, arrondir par valeur inférieure en prenant l'entier immédiatement inférieur, en procédant coordonnée par coor- donnée; c'est-à-dire si une coordonnée est égale à a + 1/2, en désignant par a un entier, prendre la décision en faveur de a plutôt que de a + 1. Dans la seconde étape, on désigne par e = r - a le N-uple d'erreur apparente, et on désigne par s l'ensemble de coordonnées dans lequel e a la valeur maximale. Si a n'est pas un élément de D4 et si S contient plus d'un élément, réduire a de 1 dans la première coordonnée dans S pour laquelle e passe ensuite d'une valeur négative à une valeur positive. S'il n'y a pas de coordonnée négative de e dans S, augmenter a de 1 dans la coordonnée qui corres- pond à la dernière coordonnée de S. Il y a 24 points dans D4 qui ont la norme minimale 2, correspondant à toutes les permutations possibles et à tous les changements de signe possibles du 4-uple (+1, +1, 0,0). La région de Voronoi de D4 n'a que 24 faces, avec l'une d'elles correspondant à chacun de ces points. La ré- gion fondamentale R correspondant à la règle de décision précitée comprend l'intérieur de la région de Voronoi, plus les intérieurs des 12 faces correspondant aux points à norme égale à 2, dont la première coordonnée non nulle a un signe positif, plus les points qui sont aux intersections des faces incluses. Cette région fondamentale forme la base de constel- lations de Voronoi, de la manière suivante. En quatre dimensions, Z4/D4/RZ4/RD4/2Z4/2D4/2RZ4/ 2RD4/4Z4/ED4/... est une chaîne infinie de partitions de ré- seau en deux, dans laquelle R est la transformation orthogo- nale de doublement de norme qui est donnée par la matrice 4 x 4 R = 1 0 0 1 -1 0 0 0 0 1 1 O 0 1 -1 On note que D4 est formé par les points dans Z qui ont une norme paire, et est un sous-réseau d'ordre 2 du ré- 4 4 4 seau Z4. On obtient RZ4 à partir de Z par rotation et multi- plication par un facteur d'échelle. En prenant une paire ap- propriée de réseaux dans cette chaîne, on peut engendrer des constellations de Voronoi avec un nombre de points égal à une puissance quelconque de deux, et non simplement un certain nombre M4 (M étant un entier). Par exemple, le choix de la partition de réseau Z /4D4 donne une constellation de Voronoi à 512 points dont les points sont indiqués dans le Tableau I ci-après. La liste des points est présentée par forme, en ordre de norme crois- sante, la forme d'un 4-uple étant l'ensemble des grandeurs de ses éléments. Pour chaque forme, on indique également sa nor- me r2; le nombre total n de points dans Z4 de cette forme qu'on peut obtenir par des permutations et des changements de signe, le nombre # de voisins les plus proches dans 4D4, pour tout 4-uple de cette forme; le nombre n/ t de 4-uple de cette forme qui sont inclus dans une région fondamentale R; et en- fin la moyenne c des éléments de cette forme qui tombent dans une région fondamentale à prédétermination maximale R. (On note que pour toute forme qui se trouve à l'intérieur de la région de Voronoi, * = 1 et c = 0 = (0, 0, 0, 0).) 26166C6 Tableau I Constellation de Voronoi déterminée par la partition Z4/4D4 Forme r2 n # n/* Moyenne 0000 0 1 1 1 0O 1000 1 8 1 8 0 1100 2 24 1 24 0 1110 3 32 1 32 0 1111 4 16 1 16 0 2000 4 8 1 1 0 2100 5 48 1 48 0 2110 6 96 1 96 0 2111 7 64 1 64 0 2200 8 24 2 12 (1,2/3,1/3,0) 2210 9 96 2 48 (1,2/3,1/3,0) 3000 9 8 1 8 0 2211 10 96 2 48 (1,2/3,1/3,0) 3100 10 48 2 24 (1,2/3,1/3,0) 3110 11 96 3 32 (3/2,1,1/2,0) 2220 12 32 4 8 (3/2,3/2,1,0) 3111 12 64 4 16 (2,1,1/2,0) 2221 13 64 4 16 (2,1,1/2,0) 2222 16 16 8 2 (2,2,2,0) 4000 16 8 8 1 (4,0,0,0) On peut déterminer à partir du Tableau I que P(C0) = 233/32 = 7,28 (8,62 dB), c = (1/2,11/32,3/16,0), ce qui donne JcJ12 = 413/1024 = 0,40 et P(C) = 7043/1024 = 6,88 (8,37 dB). (L'estimation asymptotique pour P(C) donnée par le procédé "d'approximation intégrale" est 6,93 (8,41 dB), si bien qu'à 512 points, P(C) est déjà à 0,04 dB de l'asymptote.) Utilisation de constellations de Voronoi à 4 dimensions Des constellations de Voronoi obtenues par exemple à partir de partitions de réseau de la forme Z4/1', dans laquelle A' est une version proportionnelle de D4 ou RD4, comme la constellation à 512 points basée sur la partition 4 - Z /4D4 qu'on vient de décrire, sont utiles, par exemple, avec les codes de modulation à codage par treillis du genre décrit et revendiqué dans la demande de brevet US 727398 (Wei) déposée le 25 avril 1985 et maintenant délivrée, qui a été cédée à la demanderesse. Les codes de Wei sont ce qu'on appelle des codes de co-ensembles (binaires). On définit un code de co-ensemble par un réseau à N dimensions t, un sous-réseau L à N dimen- sions de A, dans lequel la partition (groupe de quotient) A /L a l'ordre 2k +t, un codeur binaire E de taux k/(k+t), et une constellation de signal C à 2n+t points, formée par des k.t points dans un co-ensemble de A, comprenant 2k+t sous-en- sembles de 2n-k points chacun, chaque sous-ensemble étant constitué par des points d'un co-ensemble distinct de L. En considérant la' figure 5, on note que dans un circuit destiné à mettre en oeuvre un code de coensemble généralisé, un codeur 80 prend k bits par symbole à N dimensions, et émet k+t bits codés, qui sélectionnent un sous-ensemble (l'un des 2k+ t co-ensembles de L), dans un sélecteur de co-ensemble 82, sur la base de la partition de réseau N/L. n-k bits non codés supplémentaires par symbole à N dimensions sélectionnent en- suite (dans un sélecteur de point 84) un point de signal par- ticulier dans ce sous-ensemble. Le point de signal à N di- mensions est déterminé par N coordonnées (z1, z2,-... Zn), qui peuvent être transmises par N/2 utilisations d'un modu- lateur MAQ 86 (en supposant que N soit-pair). Un tel code de co-ensemble transmet n bits par point de signal à N dimen- sions. En considérant la figure 6, on note que les codes de co-ensembles à quatre dimensions de Wei ont les caracté- 26166C6 ristiques générales suivantes. Pour émettre un nombre entier pair n de bits par symbole de données à quatre dimensions, on groupe pour le codage n bits de données d'entrée (101) à la fois. Un codeur (102) (qui peut accomplir un certain nom- bre d'opérations, telles que le codage par convolution (t=1) à taux 2/3, le codage différentiel et/ou l'embrouilla- ge), engendre n+1 bits codés 103, qui doivent sélectionner un point parmi 2n+1 points (mots de données), dans une cons- tellation de signal C dont les points sont extraits d'un co- ensemble du réseau d'entiers à quatre dimensions Z4. On note que le codeur 102 de la figure 6 correspond au codeur 80 de la figure 5, si on considère que les n-k bits non codés pas- sent également par le codeur 80. Le sélecteur 104 correspond aux sélecteurs 82, 84 de la figure 5. A titre d'exemple, on peut mettre en oeuvre un code de co-ensemble du type de Wei, pour émettre 8 bits par symbole de données à 4 dimensions, dans lequel A= Z4 (N = 4), L = RD4, k = 2, k+t = 3 (t=1), et n = 8, en utili- sant la constellation de Voronoi C à 29 (=512) points, dont les points appartiennent à un co-ensemble de Z4, en procé- dant de la façon suivante. (On note que le procédé de Conway et Sloane ne peut pas produire des constellations à 22k+1 points dans 4 dimensions.) La constellation se divise de façon égale en lZ4/RD4 4 = 2k+t = 23 = 8 sous-ensembles, chacun d'eux comprenant 26 points extraits d'un coensemble distinct de RD4. En général, de telles constellations de Voronoi sontdavantage sphériques et exigent donc moins d'énergie moyenne que les constellations croisées générali- sées données par Wei. Par exemple, la constellation croisée généralisée à quatre dimensions et à 512 points qui est construite à partir de la constellation bidimensionnelle à 24 points comprenant les 16 "points intérieurs" demi-entiers de plus faible énergie et les 8 "points extérieurs", à une énergie moyenne de 7 (8,45 dB), soit un écart défavorable d'environ 0,08 dB par rapport à la constellation de Voronoi qui est spécifiée par le Tableau I. On obtient ces avantages en construisant la constellation de Voronoi sur la base de la région de Voronoi d'un sous-réseau A' de A, ce sous- réseau (par exemple 4D4) étant autre qu'une version propor- tionnelle du réseau A (par exemple Z4). Les huit co-ensembles à partir desquels on extrait les huit sous-ensembles sont respectivement définis comme étant les points dans RD sommés avec l'un des représentants de coensemble suivants: ' (0, 0, 0, 0) (1, 0 0, 0) (0, 1, 0, O) (1, 1, 0, 0) (0, 0, 1, 0) (0 1, 0, 0) (0, 1, 1, O) (1, 1, 1, 0) On note que les représentants de co-ensemble sont tous les huit des quatre-uples dans lesquels les trois pre- mières coordonnées sont 1 ou 0 et la dernière coordonnée est 0 (ce qui correspond à la région fondamentale suivante de RD4: {r: 0 En considérant la figure 7, on note que deux des huit bits d'origine sont codés sous la forme de trois bits (dans le codeur à 16 états 122), et sont utilisés (dans le sélecteur 124) pour sélectionner l'un des huit coensembles dans la partition en huit Z4/RD4. Les six autres bits sélec- tionnent (dans le sélecteur 126) l'un des 64 points dans le co-ensemble choisi, chacun des 64 points appartenant à l'un des 64 co-ensembles de la partition en 64 |RD4/4D41. Plus précisément, le mot de données x comprend une première coor- donnée x1, qui est l'un des 8 entiers dans la plage 0 nées supplémentaires à 4 valeurs x2, x3, x4fi0, 1, 2, 3}. Chacun de ces 8 x 4 x 4 x 4 = 512 mots de données (x1., x2, x3, x4) est dans une classe d'équivalence modulo 4D4 diffé- rente. On peut exprimer de la manière suivante, en représen- tation binaire classique, les quatre coordonnées du mot de données que fournit le sélecteur 126: X13 x12 x22 x32 x42 xli x21 x31 x41 chaque colonne représentant les bits successifs de l'une des coordonnées (par exemple x12 est le second bit de la première coordonnée). Le sélecteur 124 utilise les trois bits codés pour spécifier des bits x11, x21, x31, de façon que les co-ensembles de RD4 soient spécifiés conformément au code de Wei, comme on l'examinera ci-après de façon plus dé- taillée. Le sélecteur 126 utilise les six bits non codés pour spécifier les coordonnées restantes x13, x12, x23, x32, et x42, et x41. En considérant à nouveau la figure 7, on note que le mot de données x est décodé (dans le décodeur 128) de façon à donner le point le plus proche dans 4D4, en utili- sant le décodeur à prédétermination maximale. Le vecteur d'erreur apparente résultant e (129) est le point de la classe d'équivalence définie par le mot de données qui se trouve dans C0. On applique une translation de valeur c (130) pour atteindre le point correspond dans C (109). En- fin, z = e - c est émis par un émetteur MAQ 110 qui est utilisé deux fois. De façon similaire, il est nécessaire dans le ré- cepteur de trouver le mot de données qui correspond à un point de constellation de Voronoi décodé déterminé. Dans ce but, on applique une translation de valeur c et on trouve ensuite les résidus des quatre coordonnées, modulo 4. Ceci détermine les trois dernières coordonnées; la première coor- donnée est soit le résidu ainsi déterminé, soit ce résidu 6 166C plus 4, la valeur prise étant celle qui est dans la même classe d'équivalence que le point décodé et translate, modulo 4D4. On peut déterminer ceci en soustrayant les ré- sidus du point décodé et translaté, et en déterminant si la différence (dont toutes les coordonnées sont des multiples de 4) contient un nombre pair ou impair de multiples de 4; l'addition de 4 à la première coordonnée est nécessaire dans ce dernier cas. Il n'est pas nécessaire que la dimension de la constellation de Voronoi soit égale à la dimension des ré- seaux qui sont utilisés dans le code. Par exemple, une sé- quence de quatre symboles à 4 dimensions provenant du code de Wei (représentés par 4n + 4 bits codés) peut être proje- tée vers un point de signal d'une constellation de Voronoi à 16 dimensions, basée sur une partition de réseau Z 16/', en appelant A' un réseau à 16 dimensions du type du réseau de Barnes-Wall (Forney et col., 1984). A titre d'exemple, pour n = 8, il existe des constellations de Voronoi à 236 points basées sur la partition de réseau Z16/2R A16 qu'on peut utiliser avec le code de Wei. Pour effectuer le pro- jection de bits vers des points, on crée tout d'abord un mot de données à 16 dimensions avec cinq -coordonnées prenant une valeur parmi 8, dix coordonnées prenant une valeur parmi 4 et une coordonnée prenant une valeur parmi deux, de façon 36 _5 10 que chacun des 236 = 8 x 410 x 2 mots de données résultants tombe dans une classe d'équivalence distincte de 2RA 16' On décode ensuite de façon que le résultat du décodage soit le point le plus proche dans 2RA16 (voir la demande de brevet US 828397 précitée), et on émet le vecteur d'erreur apparen- te résultant e, sous la forme de 8 symboles MAQ successifs. Une telle constellation à 16 dimensions peut gagner de l'or- dre de 0,5 dB sur une constellation à 4 dimensions. La description ci-dessus indique de façon générale comment on peut utiliser une constellation de Voronoi avec un code de co-ensemble du type de Wei. On va maintenant in- 26166C diquer brièvement la façon de procéder pour convertir le mode de réalisation particulier décrit dans la demande de brevet de Wei, pour l'utilisation avec une constellation de Voronoi. Le mode de réalisation particulier de Wei comprend une caractéristique de codage différentiel. Les modifica- tions suivantes sont nécessaires pour mettre en oeuvre le codage différentiel. On doit choisir la constellation C dans le co-ensemble de Z4 qui est constitué par les 4-uples de demi-entiers, c'est-à-dire z4+ (1/2, 1/2, 1/2, 1/2). Le codeur prend maintenant pour chaque point de signal à 4 di- mensions 3 bits qu'on appelle Il n, I2n, I3 (comme sur la figure 7 de Wei) . Un codeur différentiel convertit I2n, I3, n112n', I3n. Un codeur à convolution de taux 2/3 et à 16 états engendre un bit de parité YO n. Les quatre bits YOn nnn' n 11n' '2A' '3A sont convertis en quatre bits ZOnI Zn' ZOn+1' Z n+1 dans un convertisseur de bits. Les quatre coordonnées X1, x2, x3, x4 s'expriment alors en représenta- tion binaire classique sous la forme: x1 = x13x12Xl. 1 x2 x22 x21. 1 x3 x32 x31 x4 x42 x41. 1 dans laquelle le ".1" indique la fraction binaire 1/2. Les règles de projection sont: ZOnz1n x11X21 ZOn+lZ 1n+ 1 x3141 00 00 00 00 01 11 01 11 10 10 10 11 01 11 01 ce qu'on peut exprimer par les équations binaires (modulo 2) x21 = Zlni, x11 = ZOn+Z1n, etc. Les cinq bits restants 26U 6t6 x13, x12, x22, x32 et x42 sont spécifiés par 5 bits non codés. (Ceci a pour but d'émettre n = 8 bits par symbole à 4 dimensions.) Pour émettre n = 14 bits par symbole 4D, comme sur la figure 7 de Wei, on représente les coordonnées des mots de données par: x1 = X14X13X12X11.1 X2 = X24X23x22x21.1 x3 = x34x33X32X31.1 x4 = X43X42X41.1 x11, x21, x31 et x41 sont spécifiés comme ci-dessus (en utilisant 3 bits d'entrée Iln, I2n, I3n) et les 11 bits res- tants x14, x13, x12, x24, x23, x22, x34, x33, x32, x43, x42 sont spécifiés par les bits restants I1-7n+1, I4-7n. Circuits de modem On peut utiliser la constellation de Voronoi dans des circuits de modem pour émettre des données numériques sur un canal affecté par du bruit. En considérant la figure 8, on note que dans un émetteur de modem 111, un embrouil- leur 112 revoit le train de bits d'information série à émettre sur un canal 114. Les bits d'information embrouillés sont ensuite appliqués à un ensemble codeurs/dispositif de groupement 118, à raison de Q bits par intervalle de trans- mission de signal. On peut donc désigner par I1i à IQi les bits qui apparaissent à l'entrée de l'ensemble codeurs/ dispositif de groupement 118 pour un intervalle de trans- mission de signal donné (soit par exemple le i-ième inter- valle de transmission). Sur la base des bits d'information qui apparaissent pour un bloc d'un certain nombre N/2 d'in- tervalles de transmission de signal successifs (c'est-à-dire les bits d'information Ilq à IQq, pour q = i, i+1,..., i+N/2-1), l'ensemble codeurs/dispositif de groupement 118 fournit au modulateur 120 N/2 paires de coordonnées en phase et en quadrature, en série, à raison d'une paire dans chaque intervalle de transmission de signal, chaque paire corres- pondant à un point dans une constellation de signal bidimen- sionnelle (2D). Ces paires de coordonnées sont ensuite uti- lisées dans le modulateur 120 pour moduler un porteur. Le porteur modulé est ensuite soumis à un filtrage de mise en forme d'impulsions, puis à une conversion numérique-analo- gique, pour donner un signal analogique pour la transmission sur le canal 114, comme dans un système de porteur à Modula- tion d'Amplitude en Quadrature (MAQ) de type classique. A titre d'exemple, sur la figure 6, n/2 bits par intervalle de transmission de signal sont groupés et codés en un vecteur de code (z1, z2, z3, z4) qui est transmis sous la forme de deux symboles MAQ successifs. L'ensemble codeurs/ dispositif de groupement 118 est conçu, entre autres, pour projeter des mots de données vers les points de la constella- tion de Voronoi, et il contient donc une information à partir de laquelle on peut engendrer les points de la constellation de Voronoi. La projection peut être effectuée de la manière décrite précédemment. En considérant la figure 9, on note que dans le récepteur 140, le signal porteur modulé qui est reçu par le canal passe par un convertisseur analogique-numérique 142, un égaliseur adaptatif 144 et un démodulateur adaptatif 146. Le démodulateur 146 fournit en série à un décodeur 148 des paires de coordonnées égalisées et démodulées. Le décodeur 148 renvoie en rétroaction vers un calculateur de signal d'actualisation d'égaliseur/démodulateur des décisions pré- liminaires concernant les paires de coordonnées reçues. Ces décisions préliminaires sont traitées d'une manière classi- que dans le calculateur 145, pour engendrer des signaux d'actualisation pour l'égaliseur et le démodulateur. Les décisions préliminaires peuvent être retardées. Dans ce cas, le signal de sortie du démodulateur sera retardé de façon correspondante par l'élément de retard 147 avant d'être émis vers lecalcuiateur 145. Après un retard d'un certain nombre d'intervalles de transmission de signal, le décodeur 148 fournit également au désembrouilleur 152 des décisions fina- les concernant des bits d'information embrouillés qui ont été émis. Le signal de sortie du désembrouilleur 152 est le train de bits série d'origine. Le décodeur 148 est conçu, entre autres, pour dé- coder un signal reçu de façon à donner l'un des points dans la constellation de Voronoi, et à projeter chaque point pour redonner un mot de données. Le décodage et la projection peuvent être effectués de la manière décrite précédemment. Il va de soi que de nombreuses modifications peu- vent être apportées à l'appareil et au procédé décrits et représentés, sans sortir du cadre de l'invention. 26166(C REVENDICATIONS 1. Appareil pour la transmission de données sur un canal, caractérisé en ce qu'il comprend: un codeur (118) destiné à sélectionner une série de points de signal dans une constellation de points disponibles, cette constellation étant constituée par des points d'un réseau A (ou d'un co- ensemble de A) qui se trouvent à l'intérieur d'une région de Voronoi d'un sous-réseau A' de A, le sous-réseau A' étant autre qu'une version proportionnelle de A; et un mo- dulateur (120) destiné à moduler un porteur sur le canal conformément à la série sélectionnée de points de signal. 2. Appareil selon la revendication 1, caractérisé en ce que le sousréseau A' est d'un type différent du réseau. 3. Appareil selon la revendication 1, caractérisé en ce que la constellation est basée sur des points dans une région fondamentale du sous-réseau JA' qui est consti- tuée par une sélection ne comprenant pas tous les points de la région de Voronoi. 4. Appareil selon la revendication 3, caractérisé en ce que la sélection est du type à prédétermination maxi- male. 5. Appareil selon la revendication 3, caractérisé en ce que certains points de la région fondamentale se trou- vent sur une frontière de la région de Voronoi. 6. Appareil selon la revendication 1, caractérisé en ce que le réseau A est une version d'un réseau d'entiers zN, N étant un entier. 7. Appareil selon la revendication 1, caractérisé en ce que le sousréseau A' est une version d'un réseau de Schl1fli D4. 8. Appareil selon la revendication 1, caractérisé en ce que le sousréseau A' est une version d'un réseau de Barnes-Wall A16. 9. Appareil selon la revendication 1, caractérisé 261 6606 en ce que la série de points de signal est sélectionnée sur la base d'un code de co-ensemble. 10. Appareil pour la transmission de données sur un canal, caractérisé en ce qu'il comprend: un codeur (118) destiné à sélectionner une série de points de signal parmi une constellation de points disponibles, sur la bae d'un code, cette constellation étant une constellation ae Voronoi et le code étant un code de co-ensemble; et un modulateur (120) destiné à moduler un porteur conformément à la série sélectionnée de points de signal. 11. Appareil selon la revendication 10, caractéri- sé en ce que le code de co-ensemble a le même nombre de di- mensions que la constellation de Voronoi. 12. Appareil selon la revendication 11, caractéri- sé en ce que le nombre de dimensions est de quatre. 13. Appareil selon la revendication 10, caractéri- sé en ce que le code de co-ensemble a un nombre de dimen- sions différent de celui de la constellation de Voronoi. 14. Appareil selon la revendication 13, caractéri- sé en ce que le code de co-ensemble a quatre dimensions et la constellation de Voronoi a seize dimensions. 15. Procédé de projection de m bits de données vers un point tiré d'une constellation de Voronoi à 2m points, pour la transmission sur un canal, sur la base d'une partition de réseau à N dimensions A/ A', le sous- réseau A' étant autre qu'une version proportionnelle du réseau A, caractérisé en ce qu'il comprend les opérations suivantes: on projette les m bits vers l'un de 2m mots de données x, chaque mot de données x consistant en N coordon- nées (x1,..., Xn), et chaque coordonnée prenant une valeur d'un ensemble de valeurs prédéterminé, le nombre d'éléments dans tous ces ensembles de valeurs de coordonnées n'étant pas identique, et chaque mot de données étant un point dans un co-ensemble de A qui appartient à une classe d'équiva- lence distincte modulo A'; on décode le mot de données x pour donner un point ? dans A'; et on utilise l'erreur ap- parente e = x - \ (ou une version translatée e-c de cette erreur apparente) en tant que coordonnées du point de la constellation à transmettre. 16. Procédé de transmission de données sur un ca- nal, caractérisé en ce qu'il comprend les opérations sui- vantes: on sélectionne une série de points de signal à partir d'une constellation de points disponibles, la cons- tellation étant formée par des points d'un réseau A (ou d'un co-ensemble de A) qui se trouvent à l'intérieur d'une région de Voronoi d'un sousréseau A' de A, le sous-réseau A' étant autre qu'une version proportionnelle de A; et on module un porteur sur le canal confprmément à la série sé- lectionnée de points de signal. 17. Procédé de transmission de données sur un ca- nal, caractérisé en ce qu'il comprend l'opération consistant à sélectionner une série de points de signal dans une cons- tellation de points disponibles, sur la base d'un code, cet- te constellation étant une constellation de Voronoi, et le code étant un code de co-ensemble.