FR 2710166 A1 19950324 FR 9310865 A 19930913 DISPOSITIF DE DECISION POUR MODULATIONS CODEES ET MODEM COMPORTANT UN TEL DISPOSITIF Description La présente invention concerne un dispositif de décision, pour modulations codées en treillis utilisant une constellation décomposée en N sous-ensembles, qui permet de déterminer le point le plus proche d'un symbole reçu dans chaque sous-ensemble de la constellation, lui associant ainsi une combinaison de N points. L'invention concerne également un modem comportant un tel dispositif de décision. Le codage en treillis trouve actuellement d'importantes applications dans le domaine des modulations numériques. Il consiste à décomposer la constellation en sous-ensembles qui sont choisis de telle sorte que la distance euclidienne carrée minimum séparant deux points d'un même sousensemble soit maximale. Il est donc possible de diviser plusieurs fois la constellation jusqu'à obtenir la distance souhaitée. Ainsi, pour transmettre Q éléments binaires d'information, on ajoute P éléments binaires de redondance utilisant donc une constellation de 2Q+P points (dans la pratique P est en général fixé égal à 1): M des Q éléments binaires d'information sont alors utilisés par un codeur convolutif de taux M/M+P (ce qui correspond à l'ajout de P éléments binaires de redondance) pour désigner l'un des 2M+P sous-ensembles de la constellation; et les Q- M éléments binaires restant servent à déterminer, à l'intérieur d'un sous-ensemble désigné, l'un des 2Q-M points. Le comportement d'un codeur convolutif est décrit par un treillis dont chaque branche représente la transition d'un état à un autre du codeur convolutif par transmission d'un point d'un sous- ensemble donné de la constellation. L'algorithme de Viterbi est connu pour être une méthode optimale de décodage de ces codes convolutifs. Son principe est décrit dans l'article "The Viterbi Algorithm" de G. David Forney paru le 3 mars 1973 dans la revue "Proceedings of the IEEE". Rappelons simplement que la première étape de cet algorithme consiste, pour chaque symbole reçu, à déterminer le symbole qui en est le plus proche, au sens de la distance euclidienne, dans chaque sous-ensemble de la constellation. Pour cela, il est connu de calculer, pour chacun des sous-ensembles de la constellation, les distances séparant le symbole reçu de chacun des points du sous-ensemble considéré, puis de choisir le symbole de ce sousensemble qui correspond à la distance minimale. Cette méthode nécessite donc d'effectuer un nombre important de calculs, directement proportionnel à la taille de la constellation utilisée. Par exemple, lorsqu'on passe d'une vitesse de transmission de 12000 eb/s (ce qui correspond à une constellation de 8 sous-ensembles de 8 points) à une vitesse de 14400 eb/s (ce qui correspond à une constellation de 8 sous-ensembles de 16 points), le nombre de calcul double. Ainsi, pour des vitesses de transmission élevées, le nombre de calculs à effectuer augmente de façon considérable. De plus, la recherche du symbole correspondant à la distance minimale doit être effectuée autant de fois qu'il y a de sous-ensembles. L'invention a pour but de proposer un dispositif de décision pour modulations codées qui ne présente pas ces inconvénients. Pour cela, un dispositif selon l'invention et tel que décrit dans le paragraphe introductif est caractérisé en ce que la constellation étant découpée en zones correspondant chacune à une combinaison donnée de N points, il comporte un module de recherche de la zone dans laquelle se situe le symbole reçu, et une table dont la lecture fournit la combinaison correspondant à cette zone. Ainsi, un dispositif selon l'invention ne met en oeuvre aucun calcul de distance. Seules une recherche de la zone du plan complexe qui contient le symbole reçu, et une unique lecture de table sont nécessaires pour déterminer la combinaison de N points associée au symbole reçu. Dans un mode de réalisation préférentiel du dispositif selon l'invention, le module de recherche de zone détermine la zone recherchée par dichotomie relativement aux frontières des différentes zones. Et de façon avantageuse, les frontières utilisées sont des droites. Seuls quelques tests sont donc nécessaires pour déterminer la zone recherchée. Dans un autre mode de réalisation avantageux, de façon à en simplifier la mise en oeuvre, un dispositif selon l'invention comporte un module de pré-traitement qui permet de ramener par symétrie tout point reçu dans un des quatre quadrants du plan, choisi comme référence pour y effectuer la recherche, et dit quadrant de référence, et en ce que les numéros de zone dans chacun des quadrants sont choisis de telle sorte qu'une opération mathématique "addition d'une constante" permette de passer du numéro de zone obtenu dans le quadrant de référence aux numéros des zones qui lui sont symétriques par rapport aux axes du plan de la constellation dans les autres quadrants. D'autres particularités, détails et avantages de l'invention seront mis en évidence par la description qui va suivre en regard des dessins annexés qui sont donnés à titre d'exemples non limitatifs et dans lesquels: - la figure 1 représente la constellation utilisée dans la recommandation V32/V32bis pour des modulations codées en treillis à 9600eb/s, - la figure 2 représente un exemple de découpage en zones d'un quadrant du plan pour cette même constellation, - la figure 3 est un schéma d'un exemple de dispositif de décision selon l'invention, la figure 4 représente l'organigramme d'un exemple d'algorithme de recherche de zones, - la figure 5 représente un modem comportant un dispositif de décision selon l'invention. Dans la suite de la description, on a choisi de considérer un débit binaire de 9600eb/s pour la simplicité de l'exposé. Toutefois, il ne faut pas perdre de vue que le dispositif de décision selon l'invention est d'autant plus avantageux que le nombre de points de la constellation est élevé, c'est-à-dire que le débit binaire est important. La figure 1 représente la constellation utilisée par la recommandation V32/V32bis pour les modulations codées en treillis à 9600eb/s. Cette constellation comporte 32 points répartis en huit sous-ensembles de quatre points chacun. Ces sous-ensembles sont référencés par les lettres A à H, et à l'intérieur de chacun d'eux les points sont numérotés de 0 à 3. A chaque point de la constellation est associé un mot binaire Y0 Y1 Y2 Q3 Q4, les éléments binaires Y0, Y1 et Y2 d'une part et Q3 et Q4 d'autre part étant respectivement utilisés pour coder le sous-ensemble et le point à l'intérieur de ce sous-ensemble. Les tableaux 1 et 2 donnés ci-dessous indiquent la correspondance entre les références utilisées sur les figures (A0 à H3) et les mots binaires fixés par la recommandation V32bis. sous-ensemble Y Y1 Y2 A 0 0 0 B 0 0 1 C O 1 O0 D 0 1 1 E 1 0 0 F 1 0 1 G 1 1 0 H 1 1 i TABLEAU 1 point Q3 Q4 0 0 0 1 1 0 O O O 2 0 1 3 1 1 TABLEAU 2 La figure 2 représente le découpage en treize zones du quadrant (X>0, Y> 0) servant de référence pour les calculs de recherche de zone. Ces treize zones ont été délimitées en calculant pour un grand nombre de points reçus très proches les uns des autres, les distances euclidiennes qui les séparent de tous les points de la constellation de façon à déterminer la combinaison des huit points les plus proches associée à chacun d'eux. Chaque zone est ensuite formée par l'ensemble des points reçus pour lesquels une même combinaison a été déterminée. Ces zones sont numérotées ZO à Z12. Les numéros des zones des quadrants (X 0), (X 0, Y 0) symétrique de la zone ZO par rapport à l'axe imaginaire est numérotée Z13, la zone du quadrant (X O, Y symétrique de la zone ZO par rapport à l'axe réel est numérotée Z39. Cette numérotation permet, à partir du numéro d'une zone calculé dans le quadrant de référence, d'obtenir facilement le numéro d'une autre zone qui lui est symétrique dans un autre quadrant. Le tableau 3 indique les combinaisons de huit points obtenues pour chaque zone de chaque quadrant. D'après la figure 3, le dispositif de décision selon l'invention comporte un module 1 de pré-traitement relié à une entrée 0 délivrant les coordonnées d'un point reçu, et un module 2 de recherche de zone qui commande la lecture d'une table 3 contenant les combinaisons de huit points associées à chaque zone de la constellation. Les seize éléments binaires résultant d'une telle lecture sont délivrés sur une sortie 4. Le module 1 de pré-traitement dispose en entrée des coordonnées Xr et Yr du point reçu R. Il localise ce point reçu R dans l'un des quatre quadrants du plan complexe en testant ces coordonnées Xr et Yr par rapport à l'origine (0, 0). Dans le cas o le quadrant obtenu est autre que le quadrant de référence (X>0, Y>0), le point reçu R est y ramené par symétrie par rapport aux axes imaginaire et/ou réel du plan complexe (Xr devient -Xr et/ou Yr devient -Yr). Un nouveau point R' de coordonnées Xr' et Yr' est ainsi obtenu. Le quadrant initial du point reçu R est ensuite mémorisé par l'intermédiaire d'une variable index de la façon suivante: - si R est dans le premier quadrant (Xr>0, Yr>0): index = 0, - si R est dans le second quadrant (Xr 0): index = 13, - si R est dans le troisième quadrant (Xr - si R est dans le quatrième quadrant (Xr>0, Yr Les coordonnées Xr' et Yr' du point R' et la variable index sont transmises au module 2 de recherche de zone. 1er quadrant zone 0 A1 B1 C3 D2 E3 F2 G1 Hi 1 A1 B1 C3 D2 E3 F0 G1 H2 2 A3 BO C3 D2 E3 F0 G1 H2 3 A1 B2 C1 D2 E3 F2 G1 H1 4 Al B2 C1 D2 E3 F0 G1 H2 A3 BO C1 D2 E3 F0 G1 H2 6 A3 B2 C1 D2 E3 F0 G1 H2 7 A1 B2 Ci D2 E3 F2 GO H3 8 A1 B2 Ci D2 E3 F0 GO H2 9 A3 B2 C1 D2 E3 F0 GO H2 A3 B0 C1 D2 E3 F0 GO H2 11 A1 B2 Ci D2 E3 F0 GO H3 12 A3 B2 Ci D2 E3 F0 GO H3 2èmequadrant zone 13 A1 B1 C2 D3 E3 F2 G1 Hi A0 B3i C2 D3 E1l F2 G2 H1 AO B3 02 D3 El F2 G2 Hi 16 A1 B2 CO D3 E3 F2 Gi Hi 17 A1 B2 CO D3 E1 F2 G2 Hi | 18 AO B3 CO D3 E1 F2 G2 Hi 19 AO B2 CO D3 E1 F2 G2 Hi A1 B2 CO D3 E3 F2 GO H3 21 A1 B2 CO D3 E1 F2 G2 H3 22 AO B2 CO D3 E1 F2 G2 H3 23 AO B3 CO D3 E1 F2 G2 H3 24 A1 B2 CO D3 E1 F2 GO H3 AO B2 C0 D3 E1 F2 GO H3 3emequadrant zone 26 A1 B1 C2 D3 E2 F3 G1 Hi 27 A1 B1 C2 D3 EO F3 G2 Hi 28 AO B3 C2 D3 EO F3 G2 Hi 29 A2 B1 C2 D1 E2 F3 G1 Hi A2 B1 C2 D1 EO F3 G2 H1 31 AO B3 C2 D1 EO F3 G2 Hi 32 A2 B3 C2 D1 E0 F3 G2 Hi 33 A2 B1 C2 D1 E2 F3 G3 HO 34 A2 B1 C2 D1 E0 F3 G2 HO A2 B3 C2 D1 EO F3 G2 H0 36 AO B3 C2 D1 EO F3 G2 H0 37 A2 B1 C2 D1 E0 F3 G3 H0 38 A2 B3 C2 D1 EO F3 G3 HO 4èmequadrant zone 39 A1 B1 C3 D2 E2 F3 G1 Hi A1 B1 C3 D2 E2 F1 G1 H2 41 A3 BO C3 D2 E2 F1 G1 H2 42 A2 B1 C3 DO E2 F3 G1 H1 43 A2 B1 C3 DO E2 F1 Gi H2 44 A3 BO C3 DO E2 F1 G1 H2 A2 BO C3 DO E2 F1 G1 H2 46 A2 B1 C3 DO E2 F3 G3 HO 47 A2 B1 C3 DO E2 F1 G3 H2 48 A2 BO C3 DO E2 F1 G3 H2 49 A3 BO C3 DO E2 F1 G3 H2 A2 B1 C3 DO E2 F1 G3 HO 51 A2 BO C3 DO E2 F1 G3 H0 TABLEAU 3 Ce module 2 de recherche de zone détermine la zone du quadrant de référence à laquelle appartient le point R' par dichotomie selon l'algorithme représenté sur la figure 4 par exemple. D'autres algorithmes équivalents sont utilisables. Chaque étape de l'algorithme consiste à faire un test sur les coordonnées Xr' et Yr' du point R' pour le situer d'un côté ou de l'autre des droites d'équations Y=4, Y=X+2, X=2, X=4, Y=2, et Y=X-2 qui constituent les frontières qui délimitent les différentes zones dans le plan complexe. Le numéro de la zone contenant le point R' étant déterminé, le module 2 l'ajoute à la variable index de façon à obtenir le numéro Zr de la zone du quadrant initial qui contient le point R reçu. Le module 2 commande alors la lecture de la ligne Zr de la table 3 qui délivre ainsi sur la sortie 4 les 16 éléments binaires relatifs aux huit points de la constellation les plus proches du point R. Par exemple, si le point reçu R appartient à la zone Z0, la ligne 0 de la table fournit les 16 éléments binaires formés par la succession des deux éléments binaires Q3 et Q4 des huit points appartenant respectivement aux sous-ensembles A à H, c'est-à-dire A1, B1, C3, D2, E3, F2, G1, et Hi. Ce sont ces 16 éléments binaires qui sont fournis en sortie du dispositif de décision selon l'invention. Le module 2 de recherche de zone par dichotomie met donc en oeuvre quatre tests simples dans le pire des cas, ce qui signifie, en prenant en compte le test sur le quadrant initial réalisé par le module 1 de prétraitement, que seuls cinq tests et une unique lecture de table sont nécessaires pour déterminer les huit points les plus proches du point reçu R. Pour un débit de transmission supérieur, et donc pour une constellation plus importante, seuls quelques tests supplémentaires seront nécessaires. Par exemple, lorsque la vitesse de transmission double, il suffit d'effectuer un test supplémentaire. Dans un mode de réalisation particulièrement avantageux, le dispositif selon l'invention comporte un ensemble à microprocesseur 11 comprenant un microprocesseur proprement dit 12, une mémoire vive de travail 13, et une mémoire morte 14 contenant des instructions nécessaires à la mise en oeuvre du dispositif de décision tel que décrit ci-dessus. Les modems haut débit qui utilisent des modulations codées en treillis constituent une application particulièrement intéressante du dispositif de décision selon l'invention. D'après la figure 5, un tel modem, qui porte la référence 6, permet de connecter un terminal numérique 5 à une ligne de transmission de type ligne téléphonique 7. Ce modem comporte des ensembles à microprocesseurs 10 et 11, un premier circuit d'interface 15 qui permet de le relier au terminal 5, et un second circuit d'interface 20 qui permet de transformer les signaux en provenance de la ligne téléphonique 7 en signaux numériques et réciproquement. Ce circuit d'interface 20 est décrit dans le brevet européen n 0318105. L'ensemble à microprocesseur 10 est affecté à la gestion du modem, et l'ensemble 11 qui assure les opérations de transmission, comporte un microprocesseur 12, une mémoire vive de travail 13 et une mémoire morte 14 contenant en outre les instructions permettant de mettre en oeuvre le dispositif selon l'invention. Le dispositif de décision selon l'invention permet en particulier de réaliser un modem à 19200eb/s avec une charge de calcul très peu supérieure à celle d'un modem selon l'art antérieur à 14400eb/s, conforme à la recommandation V32bis, ce qui permet de conserver la même architecture: seule la mémoire morte 14 doit être remplacée pour passer par exemple d'un modem à 14400eb/s selon l'art antérieur à un modem à 19200eb/s selon l'invention. Ceci est un avantage particulièrement important d'un point de vue commercial du dispositif selon l'invention. Il va de soi que des modifications peuvent être apportées au mode de réalisation qui vient d'être décrit, notamment par substitution de moyens techniques équivalents, sans que l'on sorte pour cela du cadre de la présente invention. REVENDICATIONS 1. Dispositif de décision pour modulations codées en treillis utilisant une constellation décomposée en N sous-ensembles, qui permet de déterminer le point le plus proche d'un symbole reçu dans chaque sous- ensemble de la constellation, lui associant ainsi une combinaison de N points, caractérisé en ce que, la constellation étant découpée en zones correspondant chacune à une combinaison donnée de N points, il comporte un module (2) de recherche de la zone dans laquelle se situe le symbole reçu, et une table (4) dont la lecture fournit la combinaison correspondant à cette zone. 2. Dispositif de décision selon la revendication 1, caractérisé en ce que le module de recherche de zone détermine la zone recherchée par dichotomie relativement aux frontières des différentes zones. 3. Dispositif de décision selon la revendication 2, caractérisé en ce que les frontières des différentes zones sont des droites. 4. Dispositif de décision selon l'une des revendications 1 à 3, caractérisé en ce qu'il comporte un module (1) de pré- traitement qui permet de ramener par symétrie tout point reçu dans un des quatre quadrants du plan, choisi comme référence pour y effectuer la recherche, et dit quadrant de référence, et en ce que les numéros de zone dans chacun des quadrants sont choisis de telle sorte qu'une opération mathématique "addition d'une constante" permette de passer du numéro de zone obtenu dans le quadrant de référence aux numéros des zones qui lui sont symétriques par rapport aux axes du plan de la constellation dans les autres quadrants. 5. Dispositif de décision selon la revendication 4, caractérisé en ce que les modules (1) et (2) de pré-traitement et de recherche de zone, et la table (3) sont formés à partir d'un ensemble à microprocesseur. 6. Modem caractérisé en ce qu'il comporte un dispositif de décision selon l'une des revendications 1 à 5.