La présente invention concerne un procédé de codage d'un vecteur d'un réseau représentatif d'un signal quantifié. Un tel vecteur est par exemple obtenu par une opération de quantification vectorielle sur réseau. II peut également être délivré par un système de transmission de vecteurs ou de blocs de données.

Un procédé de quantification vectorielle sur réseau est connu et est généralement utilisé dans des systèmes de compression de signaux audio, vidéo et multimédia au sens large. La quantification vectorielle sur réseau est l'extension multidimensionnelle de la quantification scalaire uniforme. Cette dernière consiste à quantifier séparément un signal, par exemple représentatif de chaque pixel d'une image, en 2N niveaux où N est le nombre de bits alloués au quantificateur. Quant à la quantification vectorielle sur réseau, elle est associée à un réseau régulier et permet de déterminer un vecteur de quantification, ou vecteur quantifié, appartenant au réseau en question dont les composantes sont représentatives des valeurs prises par les signaux à coder.

Plus précisément, l'opération de quantification consiste donc à déterminer, à partir d'un vecteur originel dont chacune des composantes est représentative de la valeur prise par un signal à coder et appartient de ce fait à un ensemble non dénombrable, tel que 1'ensemble des nombres réels R, un vecteur quantifié x dont chacune des composantes appartient à un ensemble dénombrable tel que 1ensemble des nombres relatifs Z. Un tel procédé est par exemple décrit par CONWAY J. H et SLOANE N. J. A. dans un article intitulé"Fast quantizing and decoding algorithms for lattice quantizers and codes"paru dans IEEE Transaction on Information Theory de mars 1982. Par exemple, si le vecteur originel est le vecteur {1.3,2.6,-3.2}, le vecteur quantifié sur un réseau D3 est le vecteur x = {1, 2,-3}.

Un réseau est un ensemble de vecteurs d'un espace de dimension n formant un groupe additif, au sens mathématique du terme. On trouvera de plus amples détails sur les réseaux dans un livre écrit par CONWAY J. H et SLOANE N. J. A. intitulé"Sphere Packings, Lattices and groups"paru en 1993 aux éditions Springer Verlag (New-York, NY). Les réseaux pour lesquels la présente invention trouve une application optimale vérifient la condition suivante : si un vecteur v, à n composantes, appartient au réseau considéré, alors tous les vecteurs u obtenus par des permutations réalisées sur les composantes du vecteur v appartiennent également au réseau. Par exemple, si le vecteur {1,2,1,0} appartient au réseau alors le vecteur {2,1,0,1} aussi. Par exemple, les différents types classiques de réseaux vérifiant cette présente condition, sont ceux connus dans la littérature sous les noms de réseau Zn, An, Dn, le réseau cubique à face centré (D3), et le réseau Eg, ou le réseau de Gosset, qui est décrit par T.

GOSSET dans un article intitulé"On the regular and semi-regular figures in space of n dimensions"paru dans Messenger Math., vol 29,1900.

Une fois le vecteur quantifié x obtenu, il reste à lui affecter, généralement par une opération d'indexation, encore appelée numérotage ou étiquetage de vecteurs, un code.

Cette opération d'indexation d'un vecteur consiste, à partir de celui-ci, à chercher son index dans un dictionnaire. Pour le décodage, on effectue l'opération inverse qui se fait donc à partir d'un index et qui permet de retrouver dans le même dictionnaire le vecteur considéré. Du fait qu'en général les signaux ainsi traités ont des propriétés statistiques particulières et, afin de diminuer les coûts de recherche dans le dictionnaire qui est en général de grande taille, on utilise des procédés d'indexation particuliers.

Un procédé connu sous le nom de procédé de codage produit à deux composantes, de codage polaire, ou de quantification vectorielle sphérique consiste à

transmettre un code à deux composantes : I'une est relative à la norme du vecteur quantifié tandis que l'autre est relative à sa phase, appelée angle en dimension n = 2. On associe donc à tout vecteur quantifié x un code produit de la forme (px, ax). Si cette méthode permet d'obtenir un gain en terme de temps de calcul de la procédure de recherche du code et en terme de débit nécessaire à la transmission de ce code, il n'en reste pas moins qu'il est nécessaire d'avoir un dictionnaire comprenant tous les vecteurs susceptibles d'être utilisés par l'application.

On connaît également une méthode qui utilise la notion de vecteur dit leader. Elle est décrite par LAMBLIN et ADOUL dans un article intitulé"Algorithme de quantification vectorielle sphérique à partir du réseau de Gosset d'ordre 8"paru dans les Annales des Télécommunications, vol. 43, n° 3-4 de 1988.

Selon cette méthode, en partant de chaque vecteur du réseau, on considère 1'ensemble des vecteurs qui sont obtenus par permutations des composantes dudit vecteur. Parmi ces vecteurs, on définit un représentant qui est alors nommé vecteur leader et qui est noté l. On peut montrer que cet ensemble de vecteurs est une classe d'équivalence, au sens mathématique du terme. Généralement, le vecteur leader I choisi pour représenter les autres vecteurs est celui dont les n composantes sont ordonnées de manière décroissante telles que 1 (0) >I (I) >... I (n-1).

Dans la suite de la description, on désignera un ensemble dont les vecteurs qui le constituent ont des composantes identiques mais dans un ordre différent par le terme de classe d'équivalence.

On a représenté à la Fig. 1, un diagramme illustrant un procédé de quantification et codage. L'opération de quantification proprement dite est réalisée, à partir d'un signal à coder s, par une unité de quantification 10 qui délivre le vecteur quantifié x.

Celui-ci fait l'objet, d'une part, d'une recherche du vecteur leader l représentant de 1'ensemble des vecteurs qui ont les mêmes composantes que ledit vecteur quantifié x par l'unité 20 et, d'autre part, d'un calcul du rang t de ce vecteur quantifié x dans cet ensemble par l'unité 30. A partir du vecteur leader 1, une unité 40 détermine l'indice i du vecteur leader l trouve par l'unité 20 et l'unité 50 détermine, à partir de cet indice i et du rang t du vecteur leader 1, le code c du vecteur quantifié x.

On a représenté à la Fig. 2 un diagramme illustrant un procédé de décodage.

L'unité 60 détermine à partir du code c reçu, d'une part, l'indice i duquel elle déduit le vecteur leader/, et, d'autre part, le rang t. A partir de ces deux éléments I et t, une unité

70 détermine le vecteur quantifié x. Ensuite une unité 80 reconstitue le signal s qui avait été codé en 10.

Pour le codage, notamment pour la détermination de l'indice i du vecteur leader/ correspondant au vecteur quantifié x, on utilise un dictionnaire de vecteurs leader l. De même, pour le décodage, notamment pour recouvrer à partir de l'indice i déduit du code c reçu, le vecteur leader l concerné, on utilise également un dictionnaire de vecteurs leader 1.

Ces dictionnaires sont normalement, dans l'état de la technique antérieure, mémorisés de manière permanente dans des mémoires respectives du codeur et du décodeur utilisés. Or, même s'ils sont de dimension réduite par rapport à un dictionnaire exhaustif de vecteurs, les dictionnaires de vecteurs leaders obligent à la mise en oeuvre d'une capacité de mémorisation relativement importante.

Le but de la présente invention est de proposer un procédé qui permette de résoudre ce problème et ainsi d'éviter l'utilisation d'une grande capacité de mémoire pour la mémorisation des vecteurs leaders.

A cet effet, un procédé de codage d'un vecteur, dit vecteur quantifié, est caractérisé en ce que ledit indice représentatif dudit vecteur leader est déterminé à partir d'un dictionnaire donnant pour chaque vecteur leader ayant même norme que ledit vecteur quantifié son indice, lesdits vecteurs dudit dictionnaire étant déterminés par calcul et stockés temporairement au moment de la formation dudit code.

Selon une autre caractéristique de l'invention, ledit procédé de codage consiste à scruter 1'espace correspondant à l'hypercadran positif de l'hypersphere de rayon égal à la norme désirée et à mémoriser, dans un ordre prédéterminé, les vecteurs de cet espace qui sont des vecteurs leaders absolus.

Selon une autre caractéristique de l'invention ledit procédé de codage consiste à scruter 1'espace correspondant à l'hypersphere de rayon égal à la norme désirée et à mémoriser, dans un ordre prédéterminé, les vecteurs de cet espace qui sont des vecteurs leaders.

Selon une autre caractéristique de l'invention, ledit procédé de codage d'un vecteur consiste à considérer, à chaque étape d'un processus de scrutation constitué d'étapes successives, un vecteur et à ne 1'enregistrer dans le dictionnaire que s'il présente la norme désirée, et en ce que ledit processus de scrutation consiste : à une première étape, à considérer le vecteur I =a, 0,..., 0} dont toutes les composantes sont nulles à l'exception de la première composante, dont la norme iiiii est

inférieure ou égale à la norme désirée p et qui est tel que la norme du vecteur l' (a + l, 0,..., 0) dont la première composante est égale à la valeur de la première composante a augmentée d'une unité soit supérieure à la norme désirée p, à une seconde étape, à considérer le vecteur l= {l,..., a-l} dont toutes les composantes sont égales à la première composante du vecteur précédemment considéré décrémentée d'une unité, à décrémenter, par étapes successives, d'une unité à chaque fois, la dernière composante du vecteur considéré jusqu'à obtenir la valeur zéro, tout en maintenant les autres composantes à leurs valeurs respectives, puis pour toutes les composantes des vecteurs ainsi obtenus, à décrémenter d'une unité la composante juste à gauche de la composante qui vient d'être annulée à l'étape précédente, puis égaler toutes les composantes à droite de ladite composante décrémentée à la valeur de ladite composante, à recommencer les étapes successives de décrémentation de la dernière composante.

Selon une autre caractéristique de l'invention, le processus de scrutation des vecteurs est interrompu lorsque le vecteur considéré est le vecteur nul.

Selon une variante, le processus de scrutation des vecteurs est interrompu lorsque le vecteur considéré est le vecteur dont, la première composante étant négative, la norme est supérieure à la norme désirée.

Selon une autre caractéristique de l'invention, lesdits vecteurs dudit dictionnaire sont déterminés et mémorisés en considérant d'abord le vecteur dont seule la première composante n'est pas nulle, la valeur de ladite première composante étant déterminée de manière, d'une part, que la norme dudit vecteur soit inférieure à la norme désirée et, d'autre part, que la norme du vecteur dont seule la première composante n'est pas nulle et est égale à ladite valeur augmentée d'une unité soit supérieure à ladite norme désirée, puis en lançant une fonction S pour une variable de position égale à zéro, pour un vecteur donné égal audit vecteur ainsi considéré et pour la norme désirée, ladite fonction S, pour la variable de position égale à une valeur quelconque d et un vecteur donné, étant prévue pour a) déterminer un vecteur, dit vecteur analysé, qui, si la variable de position est nulle, est égal audit vecteur donné et, qui, dans le cas contraire, est égal audit vecteur donné avec la d'e"'e composante égale à la (d-l) ième composante dudit vecteur donné,

b) mémoriser ledit vecteur analysé si sa norme est égale à la norme désirée, ou, si la norme dudit vecteur est inférieure à la norme désirée, lancer la même fonction S pour une valeur de la variable de position incrémentée d'une unité et pour un vecteur donné égal audit vecteur analysé, c) déterminer un nouveau vecteur analysé en décrémentant d'une unité la valeur de la d" !'n' composante et d) recommencer à l'étape b).

Selon une autre caractéristique de l'invention, à l'étape d) dudit procédé, il consiste à recommencer à l'étape b) tant que la dièmt composante n'est pas inférieure à une valeur pour laquelle la norme dudit vecteur analysée est supérieure à la norme désirée, sinon sortir de la fonction S.

Selon une autre caractéristique de l'invention, à l'étape d), il consiste à recommencer à l'étape b) tant que la d'e composante n'est pas nulle, sinon sortir de la fonction S.

La présente invention concerne également un procédé de décodage d'un code normalement constitué, d'un indice représentatif d'un vecteur, dit vecteur leader, dont les composantes sont les composantes du vecteur quantifié à recouvrer mais pas nécessairement dans le même ordre, et d'une caractéristique dudit vecteur quantifié à recouvrer qui le discrimine des autres vecteurs appartenant à l'ensemble formé des vecteurs qui ont les mêmes composantes que ledit vecteur leader, ledit procédé consistant à déterminer, à partir dudit indice le vecteur leader correspondant, puis, à partir de ladite caractéristique et dudit vecteur leader, ledit vecteur quantifié à recouvrer.

Selon l'invention, ledit procédé de décodage est caractérisé en ce que ledit vecteur leader correspondant à l'indice contenu dans ledit code est déterminé a partir d'un dictionnaire donnant pour chaque vecteur leader ayant même norme que ledit vecteur quantifié son indice, lesdits vecteurs dudit dictionnaire étant déterminés par calcul et stockés temporairement au moment de la recherche dudit vecteur leader.

Selon une autre caractéristique de l'invention, ledit procédé de décodage consiste à scruter 1'espace correspondant à l'hypercadran positif de l'hypersphère de rayon égal à la norme désirée et à mémoriser, dans un ordre prédéterminé, les vecteurs de cet espace qui sont des vecteurs leaders absolus.

Selon une variante, ledit procédé de décodage consiste à scruter 1'espace correspondant à l'hypersphére de rayon égal à la norme désirée et à mémoriser, dans un ordre prédéterminé, les vecteurs de cet espace qui sont des vecteurs leaders.

Selon une autre caractéristique de l'invention, ledit procédé de décodage consiste à considérer, à chaque étape d'un processus de scrutation constitué d'étapes successives, un vecteur et à ne l'enregistrer dans le dictionnaire que s'il présente la norme désirée, et en ce que ledit processus de scrutation consiste : à une première étape, à considérer le vecteur l= {=, 0,..., 0/dont toutes les composantes sont nulles à l'exception de la première composante, dont la norme 11111 est inférieure ou égale à la norme désirée p et qui est tel que la norme du vecteur 1'(+ l, 0,..., 0) dont la première composante est égale à la valeur de la première composante a augmentée d'une unité soit supérieure à la norme désirée p, à une seconde étape, à considérer le vecteur l= {« dont toutes les composantes sont égales à la première composante du vecteur précédemment considéré décrémentée d'une unité, à décrémenter, par étapes successives, d'une unité à chaque fois, la dernière composante du vecteur considéré jusqu'à obtenir la valeur zéro, tout en maintenant les autres composantes à leurs valeurs respectives, puis pour toutes les composantes des vecteurs ainsi obtenus, à décrémenter d'une unité la composante juste à gauche de la composante qui vient d'être annulée à l'étape précédente, puis égaler toutes les composantes à droite de ladite composante décrémentée à la valeur de ladite composante, à recommencer les étapes successives de décrémentation de la dernière composante.

Selon une autre caractéristique de l'invention, le processus de scrutation des vecteurs est interrompu lorsque le vecteur considéré est le vecteur nul.

Selon une variante, le processus de scrutation des vecteurs est interrompu lorsque le vecteur considéré est le vecteur dont, la première composante étant négative, la norme est supérieure à la norme désirée.

Selon une autre caractéristique de l'invention, lesdits vecteurs dudit dictionnaire sont déterminés et mémorisés en considérant d'abord le vecteur dont seule la première composante n'est pas nulle, la valeur de ladite première composante étant déterminée de manière, d'une part, que la norme dudit vecteur soit inférieure à la norme désirée et, d'autre part, que la norme du vecteur dont seule la première composante n'est pas nulle

et est égale à ladite valeur augmentée d'une unité soit supérieure à ladite norme désirée, puis en lançant une fonction S pour une variable de position égale à zéro, pour un vecteur donné égal audit vecteur ainsi considéré et pour la norme désirée, ladite fonction S, pour la variable de position égale à une valeur quelconque d et un vecteur donné, étant prévue pour a) déterminer un vecteur, dit vecteur analysé, qui, si la variable de position est nulle, est égal audit vecteur donné et, qui, dans le cas contraire, est égal audit vecteur donné avec la dième composante égale à la (d-1)'e"'e composante dudit vecteur donné, b) mémoriser ledit vecteur analysé si sa norme est égale à la norme désirée, ou, si la norme dudit vecteur est inférieure à la norme désirée, lancer la même fonction S pour une valeur de la variable de position incrémentée d'une unité et pour un vecteur donné égal audit vecteur analysé, c) déterminer un nouveau vecteur analysé en décrémentant d'une unité la valeur de la dleme composante et d) recommencer à l'étape b).

Selon une autre caractéristique de l'invention, à l'étape d), il consiste à recommencer à l'étape b) tant que la dième composante ntest pas inférieure à une valeur pour laquelle la norme dudit vecteur analysée est supérieure à la norme désirée, sinon sortir de la fonction S.

Selon une variante, à l'étape d), il consiste à recommencer à l'étape b) tant que la dième composante n'est pas nulle, sinon sortir de la fonction S.

La présente invention concerne encore un procédé d'élaboration d'un dictionnaire partiel de vecteurs qui ont tous pour norme une norme désirée, par exemple, la norme d'un vecteur donné et dont les composantes sont ordonnées d'une manière décroissante de gauche vers la droite, lesdits vecteurs étant alors dits vecteurs leaders.

Selon une caractéristique de l'invention, ledit procédé d'élaboration d'un dictionnaire consiste à considérer, à chaque étape d'un processus de scrutation constitué d'étapes successives, un vecteur et à ne l'enregistrer dans le dictionnaire que s'il présente la norme désirée, et en ce que ledit processus de scrutation consiste : à une première étape, à considérer le vecteur l= {ex, 0,..., 0, dont toutes les composantes sont nulles à l'exception de la première composante, dont la norme 11/11 est inférieure ou égale à la norme désirée p et qui est tel que la norme du vecteur l'(α + l, 0,..., 0) dont la première composante est égale à la valeur de la première composante a augmentée d'une unité soit supérieure à la norme. désirée p,

à une seconde étape, à considérer le vecteur l= {a-1,..., X dont toutes les composantes sont égales à la première composante du vecteur précédemment considéré décrémentée d'une unité, à décrémenter, par étapes successives, d'une unité à chaque fois, la dernière composante du vecteur considéré jusqu'à obtenir la valeur zéro, tout en maintenant les autres composantes à leurs valeurs respectives, puis pour toutes les composantes des vecteurs ainsi obtenus, à décrémenter d'une unité la composante juste à gauche de la composante qui vient d'être annulée à l'étape précédente, puis égaler toutes les composantes à droite de ladite composante décrémentée à la valeur de ladite composante, à recommencer les étapes successives de décrémentation de la dernière composante.

Selon une autre caractéristique de l'invention, le processus de scrutation des vecteurs est interrompu lorsque le vecteur considéré est le vecteur nul.

Selon une variante, le processus de scrutation des vecteurs est interrompu lorsque le vecteur considéré est le vecteur dont, la première composante étant négative, la norme est supérieure à la norme désirée.

Selon une autre caractéristique de l'invention, lesdits vecteurs dudit dictionnaire sont déterminés et mémorisés en considérant d'abord le vecteur dont seule la première composante n'est pas nulle, la valeur de ladite première composante étant déterminée de manière, d'une part, que la norme dudit vecteur soit inférieure à la norme désirée et, d'autre part, que la norme du vecteur dont seule la première composante n'est pas nulle et est égale à ladite valeur augmentée d'une unité soit supérieure à ladite norme désirée, puis en lançant une fonction S pour une variable de position égale à zéro, pour un vecteur donné égal audit vecteur ainsi considéré et pour la norme désirée, ladite fonction S, pour la variable de position égale à une valeur quelconque d et un vecteur donné, étant prévue pour a) déterminer un vecteur, dit vecteur analysé, qui, si la variable de position est nulle, est égal audit vecteur donné et, qui, dans le cas contraire, est égal audit vecteur donné avec la d""* composante égale à la (d-1)' composante dudit vecteur donné, b) mémoriser ledit vecteur analysé si sa norme est égale à la norme désirée, ou, si la norme dudit vecteur est inférieure à la norme désirée, lancer la même fonction S pour une valeur de la variable de position incrémentée d'une unité et pour un vecteur donné égal audit vecteur analysé,

c) déterminer un nouveau vecteur analysé en décrémentant d'une unité la valeur de la dième composante et d) recommencer à l'étape b).

Selon une autre caractéristique de l'invention, à l'étape d), il consiste à recommencer à l'étape b) tant que la dième composante n'est pas inférieure à une valeur pour laquelle la norme dudit vecteur analysée est supérieure à la norme désirée, sinon sortir de la fonction S.

Selon une variante, à l'étape d), il consiste à recommencer à l'étape b) tant que la dième composante n'est pas nulle, sinon sortir de la fonction S.

Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, apparaîtront plus clairement à la lecture de la description suivante de deux exemples de mise en oeuvre faite en relation avec les dessins joints parmi lesquels : la Fig. 1 est un diagramme illustrant un procédé de quantification et de codage pour lequel peut être mis en oeuvre un procédé de l'invention, la Fig. 2 est un diagramme illustrant un procédé de décodage pour lequel peut être mis en oeuvre un procédé de l'invention, les Figs. 3a et 3b sont des listes de vecteurs avec leurs rangs respectifs qui appartiennent à une même classe d'équivalence représentée respectivement par un vecteur leader l = ta, b, c, d) et un vecteur leader I = {2, 1, 0,- la Fig. 4 illustre le processus de scrutation de l'espace tel qu'il est opéré selon un procédé selon l'invention, la Fig. 5 illustre un procédé de détermination de dictionnaire partiel de vecteurs leaders selon l'invention, la Fig. 6 est un organigramme de l'étape de mémorisation d'un procédé selon l'invention, la Fig. 7 est un organigramme d'une fonction qui est mise en oeuvre dans un procédé de détermination de dictionnaire partiel de vecteurs leaders absolus selon l'invention, et la Fig. 8 est un organigramme d'une fonction qui est mise en oeuvre dans un procédé de détermination de dictionnaire partiel de vecteurs leaders signés selon l'invention.

Selon l'invention, les dictionnaires nécessaires à l'opération de codage ou à l'opération de décodage ne sont pas mémorisés de manière permanente mais, seule une partie de ceux-ci, au moment de leur utilisation, est calculée et puis mémorisée. Cette

partie du dictionnaire est celle qui répertorie tous les vecteurs leaders qui ont même norme que le vecteur quantifié.

Dans la suite de la description, on appellera vecteur leader 1 un vecteur qui est le représentant d'un ensemble de vecteurs qui ont tous les mêmes composantes, dans un ordre différent. Ce qui lui confère sa propriété de représentant de cet ensemble, c'est que ses composantes sont ordonnées, par exemple mais non nécessairement dans le sens décroissant.

Par exemple, si l'on considère un vecteur {1,2,-1,0/, il appartient à un ensemble de vecteurs qui ont tous les composantes 2,1,0 et-1 mais dans un ordre différent les uns des autres. Ainsi, le vecteur {-1,2,0, appartient également à cet ensemble. Cet ensemble est représenté par le vecteur qui a également les mêmes composantes, mais ordonnées, par exemple dans le sens décroissant. Il s'agit donc ici du vecteur, dit vecteur leader, 2,1,0,-1}.

On peut montrer que 1'ensemble des vecteurs qui ont mêmes composantes et qui sont représentés par un même vecteur leader I forme une classe d'équivalence, au sens mathématique du terme. De plus, tous les vecteurs qui appartiennent à une même classe d'équivalence peuvent être ordonnés si bien qu'il est possible de leur associer un rang, noté r, qui correspond à leur numéro d'ordre dans la classe d'équivalence à laquelle ils appartiennent.

A titre d'exemple, on donne à la Fig. 3a, la liste des vecteurs appartenant à une classe d'équivalence dont le vecteur leader est ta, b, c, dX ainsi que leurs rangs respectifs.

On donne également à la Fig. 3b, la liste des vecteurs appartenant à une classe d'équivalence dont le vecteur leader est/2, 7, 0,-7 ainsi que leurs rangs respectifs. On notera que le vecteur leader signé est le vecteur t2, 1, 0,-1}.

Dans la suite de la description, on nommera classe d'équivalence, 1'ensemble des vecteurs qui ont même composantes qu'un vecteur x donné et qui sont représentés par un même vecteur leader signé 1.

Un autre type de vecteur leader peut être utilisé pour les opérations de codage et de décodage. Il s'agit des vecteurs leaders absolus.

On appelle vecteur leader absolu un vecteur qui se déduit d'un vecteur leader I en prenant les valeurs absolues des composantes de ce dernier, puis en les ordonnant à la manière des vecteurs leaders. Les composantes d'un vecteur leader absolu appartiennent toutes à 1'ensemble des nombres entiers N. Les vecteurs leaders desquels

sont déduits les vecteurs leaders absolus sont dits vecteurs leaders signés, car leurs composantes appartiennent à l'ensemble des nombres relatifs Z.

On peut montrer que l'ensemble constitué de l'union de toutes les classes d'équivalence engendrées par les vecteurs leaders signés I desquels on peut déduire un unique vecteur leader absolu 1 forme également une classe d'équivalence, dit également surclasse d'équivalence, dont ledit vecteur leader absolu peut être le représentant. De plus, toutes les classes d'équivalence qui appartiennent à une même surclasse d'équivalence sont ordonnés et il est ainsi possible de leur associer un rang qui correspond à leur numéro d'ordre dans la surclasse d'équivalence à laquelle ils appartiennent.

L'utilisation des vecteurs leaders absolus, au lieu de vecteurs leaders signés, pour les opérations de codage et de décodage présente un avantage certain car leur dictionnaire est nécessairement restreint par rapport à un dictionnaire de vecteur leaders signés.

On notera que dans ce cas, les unités 40 et 60 des Figs. 1 et 2 déterminent un vecteur leader absolu au lieu d'un vecteur leader signé.

Pour la création d'un dictionnaire de vecteurs leaders absolu de même norme égale à une norme désirée, le procédé de l'invention consiste à scruter l'hypercadran positif de l'hypersphère de rayon égal à la norme désirée. Par ce processus de scrutation, on recherche les vecteurs leaders qui ont une norme désirée et ce, dans un ordre donné.

Pour ce faire, dans une première étape (voir Fig. 4), on commence par considérer le vecteur I =a, 0,..., 0 dont toutes les composantes sont nulles à l'exception de la première composante, dont la norme | est inférieure ou égale à la norme désirée p et qui est tel que la norme du vecteur/Yo'+7,0,....6 dont la première composante est égale à la valeur de la première composante a augmentée d'une unité soit supérieure à la norme désirée p. Puis, on considère, dans une seconde étape, le vecteur /=cr-/,..., a-7 dont toutes les composantes sont égales à la première composante du vecteur précédemment considéré décrémentée d'une unité. On va ensuite, dans des étapes suivantes successives, décrémenter d'une unité à chaque fois la dernière composante du vecteur considéré jusqu'à ce qu'elle devienne nulle, tout en maintenant les autres composantes à leurs valeurs respectives. On a alors le vecteur l= {a-l,..., a-l, 0y. L'avant-dernière composante est ensuite décrémentée d'une unité et la composante sur sa droite est égalée à elle. On a maintenant le vecteur l = {α-1, ...,

a-2, a-21. Comme précédemment, on décrémente ensuite de nouveau la dernière composante du vecteur considéré d'une unité à chaque fois jusqu'à ce qu'elle devienne nulle, tout en maintenant les autres composantes à leurs valeurs respectives.

L'avant-dernière composante est de nouveau décrémentée d'une unité. Le même processus est mis en oeuvre jusqu'à ce que cette avant-dernière composante devienne elle aussi nulle. On a alors le vecteur l =a l,..., a-l, 0, 0. Alors, c'est la composante qui se trouve toute de suite à la gauche des deux composantes nulles qui est décrémentée et les composantes sur sa droite sont égalées à elle.

On a alors le vecteur I = {a-l,..., a-2, a-2, a-21. Le processus recommence.

De manière générale, lorsque toutes les composantes à droite d'une composante d'ordre i sont nulles, cette composante est décrémentée d'une unité et toutes celles qui se trouvent à sa droite sont égalées à elle. Puis, on décrémente d'une unité à chaque fois la dernière composante jusqu'à ce qu'elle devienne égale à zéro.

A chaque étape du processus de scrutation tel qu'il vient d'être décrit, si la norme est égale à la norme désirée, on enregistre le vecteur considéré.

Pour la création d'un dictionnaire de vecteurs leaders signés, le procédé de l'invention consiste à scruter l'hypersphère complète de rayon égal à la norme désirée.

Ce procédé se déroule de la manière décrite ci-dessus concernant le dictionnaire de vecteurs leaders absolus à la différence que l'on stoppe les décrémentations successives de chaque composante lorsque celle-ci étant négative, la norme du vecteur considérée est supérieure à la norme désirée.

On va décrire, en relation avec la Fig. 5, une mise en oeuvre particulière du procédé de détermination d'un dictionnaire partiels de vecteurs leaders selon l'invention.

Une première étape 100 est une initialisation dans laquelle, d'une part, une variable de calcul d représentative de la composante analysée ainsi qu'une variable d'ordre I sont égalées à zéro et, d'autre part, un vecteur l (a, 0,..., 0) dont la première composante a est initialisée à la valeur d'une variable d'initialisation telle que la norme de ce vecteur | soit inférieure ou égale à la norme désirée p du vecteur quantifié x et que la norme du vecteur 1' (a + 1,0,..., 0) dont la première composante est égale à la valeur de la variable d'initialisation a augmentée d'une unité soit supérieure à la norme p du vecteur quantifié x. On a donc : p<#l'##l##

Une seconde étape 200 consiste à mettre en oeuvre une fonction S (d, 1, p) qui est fonction de la valeur prise par la variable de calcul d, du vecteur leader considéré l et de la norme p considérée. Cette fonction est récursive dans le sens qu'elle s'appelle elle- même. Cette fonction est maintenant décrite, dans un premier mode de mise en oeuvre, en relation avec la Fig. 6.

Préliminairement, on appelle composante l (d) d'un vecteur I sa dième composante comptée à partir de la gauche, celle complètement à gauche ayant le numéro d'ordre 0.

Ainsi, pour un vecteur égal à l (x, y, z, w), on a : xl(0)= I (IJ ° Y l(2) z I (3) = w.

Dans une première étape 10, on vérifie que la valeur de la variable de calcul d est inférieure à la dimension du réseau n, sinon on sort de la fonction S (d, 1, p) en n'effectuant aucun calcul. A l'étape 20, on vérifie que la valeur de la variable de calcul d est égale à zéro. Si oui, cela signifie, comme on le comprendra par la suite que c'est la première fois que la fonction S est appelée. Dans ce cas, on garde les coordonnées du vecteur l telles qu'elles ont été définies lors de l'initialisation ou lors des étapes précédentes. Sinon, à l'étape 21, la dième composante du vecteur 1 est égalée à la valeur de la duvecteurl:l(d)=l(d-1).composante On vérifie à l'étape 30 que la dième composante du vecteur 1 n'est pas négative ou nulle, dans ce cas on sortirait de la fonction S (d, 1, p).

A l'étape 31, on compare la valeur de la norme X du vecteur 1 calculé jusqu'ici avec la valeur de la variable norme p.

Si ces deux valeurs sont égales, alors le vecteur l est un vecteur leader qui peut être mémorisé à l'étape 41, puisque précisément il a la norme p.

Si elles sont différentes, on vérifie, à l'étape 32, si la norme 1141 du vecteur I est inférieure à la valeur de norme p.

Si tel est le cas, on lance, à l'étape 42, la fonction S (d+l, I, p) pour une variable de calcul égale à la valeur actuelle de d augmentée d'une unité, pour le vecteur/ jusqu'ici calculé et toujours pour la valeur de la variable norme égale à p. On notera que c'est par cet appel de la fonction S que l'on peut dire qu'elle est récursive.

Si tel n'est pas le cas, on est conduit directement à l'étape suivante 50.

A l'étape 50, on décrémente d'une unité la d'"" composante du vecteur l (l (d) = l (d)-I) et on s'en retourne en amont de l'étape 30.

On explicite en relation avec la Fig. 7 le processus de mémorisation de l'étape 41.

Ce processus de mémorisation proprement dit a lieu à l'étape 412 où le vecteur 1 considéré est mémorisé de manière associée avec la valeur prise par la variable d'ordre I. On rappelle qu'à l'étape d'initialisation 100, la valeur de variable d'ordre I est initialisée à zéro. A l'étape 411 du processus de mémorisation 41, cette variable I est incrémentée d'une unité. Ainsi, à chaque nouvelle mise en oeuvre de la mémorisation, cette variable est incrémentée d'unité et donne par conséquent le numéro d'ordre de la mémorisation considérée.

On notera que l'association du vecteur I mémorisé et de la variable I est par exemple réalisée, soit explicitement dans le sens où ils sont tous les deux mémorisés dans une unique case quelconque d'une mémoire, soit implicitement dans le sens où le vecteur I est mémorisé dans une seule case d'une mémoire dont l'adresse est obtenue par addition d'une adresse de référence avec la valeur I.

A titre d'exemple, on va maintenant considérer la création du dictionnaire partiel de vecteurs leader de dimension 2 dont la norme est 5. On définit la norme ici comme étant la somme des valeurs absolues des composantes.

A l'étape 100, on initialise donc la variable de calcul d et la variable d'ordre I à la valeur 0 et le vecteur l est initialisé au vecteur {5,0}. En effet, on a #{5,0}# # 5 < #{6,0}# A l'étape 200, la fonction S (0, t5,0), est lancée. On a d<n et d=0. On est donc conduit à l'étape 30 où la dième composante du vecteur I est positive (I (d) >0) si bien que l'on est conduit à l'étape 31. Là, puisque la norme du vecteur I est égale à la valeur de la norme désirée p : #l# = p. On est donc conduit à l'étape 41 où le vecteur l = {5,0} est mémorisé puisqu'il a la norme désiré : #l# = p.

A l'étape 411, la variable d'ordre I devient égale à 1 et le vecteur t5, 0, 1 est mémorisé associé à la valeur I = 1.

A l'étape 50, on décrémente d'une unité la dième composante du vecteur I si bien que le vecteur analysé est maintenant l = {4,0}. On est ensuite ramené à l'étape 31 qui elle-même conduit (on a ß = 4 /7) à l'étape 32. La norme du vecteur I étant positive, la fonction S(d + 1.{4,0},5) = S(1,{4,0},5) est mise en oeuvre.

A l'étape 21 de la fonction S (l, (4, 0), 5), la valeur l (l) de la première composante du vecteur I est égalée à celle de la composante d'ordre zéro l(0) (l(1) = l(0)), si bien que le nouveau vecteur I analysé est maintenant le vecteur {4,4). La dième composante

du vecteur 1 est positive, mais sa norme est supérieure à la valeur de la norme désirée.

L'étape 50 est donc mise en oeuvre directement.

Le vecteur analysé est ensuite le vecteur {4, 3} puis, du fait d'une même succession d'étapes, les vecteurs {4, 2} et {4,1} sont également analysés. Ce dernier vecteur a sa norme #l# qui est égale à p = 5. II est donc mémorisé à l'étape 41.

A l'étape 411, la variable I est incrémentée d'une unité et devient égale à 2. A l'étape 412, le vecteur {4,1) est mémorisé en association avec la valeur I = 2.

A l'étape 50, la première composante/ ( du vecteur I est maintenant décrémentée pour devenir égale à 0. Le vecteur 1 devient donc le vecteur {4,0g. A l'étape 30, on sort de la fonction S (1, {4, 0y, 5), qui avait été lancée par l'étape 42, pour arriver à l'étape 50 de la fonction S (0, {4, 0g, 5). La composante l (0) d'ordre zéro du vecteur I est alors décrémentée d'une unité et le vecteur l analysé devient l = {3,0}. Les étapes 31 et 32 conduisent alors à l'étape 42 où la fonction S (l, (3, 0)), 5) est mise en oeuvre.

Là, à l'étape 21 de la fonction S(d + 1,{3,0},5), la première composante l (l) du vecteur l est égalée à la composante d'ordre zéro du vecteur l (l(1) = l(0)) si bien que le nouveau vecteur l analysé est maintenant le vecteur t3, 3}.

Ce vecteur a sa norme qui est supérieure à la norme désirée p. On est donc conduit directement à l'étape 50 où le vecteur analysé devient le vecteur t3,2v. Ce vecteur a sa norme qui est égale à 5 si bien qu'on est conduit à l'étape 31 qui elle-même conduit à l'étape 41 où le vecteur l = {3,2} est alors mémorisé avec la valeur de la variable I = 3. A l'étape 50, le vecteur I analysé devient le vecteur t3,1). La fonction S (2, (3, I), 5) est maintenant lancée à l'étape 42 mais revient immédiatement dans la mesure où la variable de calcul d est égale à 2, la dimension du réseau.

Ce retour se fait à l'étape 50 où le vecteur analysé I devient le vecteur'3, 0y. On sort alors de la fonction S (1,{3,0},5) On comprendra que le processus se poursuit jusqu'à ce que le dernier vecteur analysé soit le vecteur 00, 0,}. On sort donc de l'étape 200 de la Fig. 4. Les vecteurs suivants ont donc été stockés de manière à être associés à la valeur de la variable I qui donne l'ordre de ces vecteurs : ordre 1{5,0}= =2{4,1}ordreI ordre 3{3,2}=

Cela constitue un dictionnaire partiel de vecteurs leaders absolus qui peut être utilisé dans un procédé de codage ou dans un procédé de décodage.

On remarquera, d'une part, que les vecteurs mémorisés sont des vecteurs leaders, c'est-à-dire que leurs composantes sont ordonnées de manière que les composantes de valeurs les plus élevées soient dans les positions les plus faibles et que, d'autre part, eux-mêmes sont ordonnés.

On remarquera que 1'espace du réseau qui a été scruté par le procédé qui vient d'être décrit est celui pour lequel toutes les composantes des vecteurs qui s'y trouvent ont des valeurs positives. En conséquence, le dictionnaire partiel ainsi calculé est un dictionnaire de vecteurs leaders absolus.

On décrit maintenant, en relation avec la Fig. 6, un second mode de mise en oeuvre d'une fonction qui est utilisé dans un procédé selon l'invention qui diffère du précédent en ce que 1'espace qui est scruté est celui pour lequel les composantes des vecteurs peuvent prendre des valeurs négatives. En conséquence, il permet la formation d'un dictionnaire partiel de vecteurs leaders signés.

La différence essentielle, visible sur le diagramme de la Fig. 6, par rapport au procédé décrit en relation avec la Fig. 5 se trouve dans l'étape 30 où l'on vérifie maintenant que lorsque dième composante du vecteur I est négative, la norme du vecteur 1 n'est pas supérieure à la norme désirée. Si tel est le cas, alors on sort de la fonction S considérée, sinon on est conduit à l'étape 31.

Comme on le verra par la suite, cette nouvelle condition de l'étape 30, amène le procédé à scruter l'ensemble des vecteurs leaders qui sont compris dans 1'espace limité par l'hypersphére de rayon égal à la norme désirée.

A titre d'exemple, on a considéré ta création du dictionnaire partiel de vecteurs leader de dimension 2 dont la norme est 5. On définit la norme ici comme étant la somme des valeurs absolues des composantes du vecteur considéré.

A l'étape 100, on initialise donc la variable de calcul d à la valeur 0 et le vecteur/ est initialise au vecteur {5,0}. En effet, on a 11 {S, 0}# # 5 < j(6,o} A l'étape 200, la fonction S (O, tS, 0), est lancée. On a d<n et d=0. De plus, la dièse composante du vecteur I est positive (sa norme 1141 est inférieure à la norme désirée p) si bien que l'on est conduit à l'étape 31. Là, puisque la norme du vecteur ! est égale à la valeur de la norme désirée p ( ! !/ () =/ ?), on est conduit à l'étape 41 où le vecteur/=/3, 0 est mémorisé.

A l'étape 411, la variable d'ordre I devient égale à 1 et le vecteur l - {5,0} est mémorisé associé à la valeur I = 1.

A l'étape 50, on décrémente d'une unité la dième composante du vecteur 1 si bien que le vecteur analysé est maintenant/= (4, 0). On est ensuite ramené à l'étape 31 qui elle-même conduit, puisque la norme 11111 du vecteur est égale à 4 et est donc différente de p, à l'étape 32 et, de là, puisque la norme du vecteur l est inférieure à la valeur de la norme désirée p, à l'étape 42 où la fonction S(d + 1,{4,0},5) = S (1, {4, 0}, 5) est mise en oeuvre.

A l'étape 21 de la fonction S (l, (4, 0), 5), la valeur 1 (1) de la première composante du vecteur l est égalée à celle de la composante d'ordre zéro 1 (0) (1 (1) = 1 (0)), si bien que le nouveau vecteur l analysé est maintenant le vecteur (4, 4). La dième composante du vecteur l est toujours positive si bien que l'on est conduit à l'étape 31, puis, la norme de ce vecteur étant différente de la norme désirée, à l'étape 32 et enfin, la norme étant supérieure à la norme désirée, à l'étape 50 qui est donc mise en oeuvre. Le vecteur analysé est le vecteur {4, 3} puis, du fait d'une même succession d'étapes, les vecteurs {4, 2} et {4,1} sont ensuite analysés. Ce dernier vecteur a sa norme #l# qui est égale à p = 5. Il est donc mémorisé à l'étape 41.

A l'étape 411, la variable I est incrémentée d'une unité et devient égale à 2. A l'étape 412, le vecteur {est mémorisé en association avec la valeur I = 2.

A l'étape 50, la première composante/ ( du vecteur l est décrémentée pour devenir égale à 0. Le vecteur 1 devient donc le vecteur {4,0g.

Suite aux résultats des différentes étapes 30,31,32 et 33, la fonction S (2, {4,0g, 5) est mise en oeuvre. Néanmoins, dans celle-ci, l'étape 10 est telle que la sortie est immédiate.

L'étape 50 de la fonction S(1,{4,0},5) est alors mise en oeuvre et le vecteur analysé devient le vecteur {4,-1}. La dième composante du vecteur leader 1 analysé est donc négative. Sa norme n'est pourtant pas supérieure à la norme désirée p. A l'étape 30 on est donc conduit à l'étape 31 où, puisque la norme du vecteur I est égale à la norme désirée, I'on est conduit à l'étape 41 où ce vecteur est mémorisé avec la valeur de la variable I = 3.

Le vecteur suivant est le vecteur {4,-2} dont la dième composante est négative et dont la norme égale à 6 est supérieure à la norme désirée p = 5. II en résulte que l'on sort de la fonction S(1,{4,0},5) où l'on se retrouve à l'étape 50 de la fonction S (0, {4, 0}, 5) qui est donc mise en oeuvre. Le vecteur analysé devient alors le vecteur

{3,0}. Sa dième composante est positive mais sa norme t est inférieure à p, si bien que la fonction S(1,{3,0},5) est lancée à l'étape 42.

A l'étape 21 de cette fonction S (l, {3, 0y, 5), le nouveau vecteur analysé devient le vecteur/3. 3/. Sa dième composante est positive mais sa norme est supérieure à la norme désirée si bien que l'on est directement conduit à l'étape 50. Là, le vecteur analysé devient le vecteur {3, 2} dont la norme est égale à la valeur de la norme désirée p = 5, si bien qu'il est enregistré à l'étape 41, avec la valeur de la variable I qui est égale à 4.

Puis, vont être analysés successivement les vecteurs {3,1}, {3,0} et {3,-1} pour lesquels la norme est inférieure à la norme désirée p = 5, si bien que la fonction S avec d = 2 est lancée (la sortie est immédiate). Puis vient le vecteur {3,-21 dont la norme est égale à la norme désirée p = 5. Ce vecteur est alors enregistré à l'étape 41 avec la valeur de la variable I = 4. Le vecteur {3,-3} est ensuite analysé mais, sa dième composante étant négative et sa norme étant supérieure à la norme désirée, on sort de la fonction S pour venir analyser les vecteurs dont la composante d'ordre zéro est 2. Ainsi, seront analysés les vecteurs {2,2}, {2,1}, {2,0}, {2,-1}, {2,-2} et {2,-3). Ce dernier est le seul enregistré de cette liste et, ce avec la valeur I = 5.

Le processus se poursuit comme il vient d'être décrit. Les vecteurs {1,-4}, {0,-5}, {-1,-4} et {-2,-3} sont alors enregistrés avec respectivement les valeurs de la variable d'ordre I égales à 6,7,8 et 9.

On sort alors de l'étape 200. Les vecteurs suivants ont été mémorisés, et ce dans cet ordre : 0 {5,0} 1 (4, 0y 2 {4,-1} 3 {3,2} 4 {3,-2} 5 {2,-3} 6 {1,-4} 7 (0,-5) 8 {-1,-4} 9 {-2,-3}

Comme précédemment, on remarquera, d'une part, que les vecteurs mémorisés sont des vecteurs leaders signés, c'est-à-dire que leurs composantes sont ordonnées et que, d'autre part, eux-mêmes sont ordonnés. Ils forment donc un dictionnaire partiel de vecteurs leaders signés qui peut être utilisé, soit dans un procédé de codage, soit dans un procédé de décodage.

Les modes de mise en oeuvre de la présente invention permettent de trouver l'indice d'un vecteur leader signé ou absolu sans avoir recours à un dictionnaire permanent de vecteurs leaders. Par contre, sont utilisés des dictionnaires partiels de vecteurs leaders qui nécessitent une capacité mémoire moindre. Ainsi, le fait de ne scruter que 1'espace du réseau limité aux vecteurs de même norme permet de s'affranchir de l'utilisation de mémoires de grande capacité. En effet, par exemple, dans le cas d'un réseau D4, la taille du dictionnaire utilisé est divisée par 9 par rapport à celle d'un dictionnaire exhaustif.